String kernel - String kernel

Bij machine learning en datamining is een string-kernel een kernelfunctie die werkt op strings , dwz eindige reeksen symbolen die niet dezelfde lengte hoeven te hebben. String-kernels kunnen intuïtief worden begrepen als functies die de gelijkenis van paren strings meten: hoe meer twee strings a en b op elkaar lijken, hoe hoger de waarde van een string-kernel K ( a , b ) zal zijn.

Met behulp van touw kernels met kernelized leren algoritmen, zoals support vector machines toestaan dat deze algoritmen te werken met strijkers, zonder deze te vertalen naar een vaste lengte, met reële waarden feature vectoren . String-kernels worden gebruikt in domeinen waar sequentiegegevens moeten worden geclusterd of geclassificeerd , bijvoorbeeld bij text mining en genanalyse .

Informele inleiding

Stel dat men sommige tekstpassages automatisch wil vergelijken en hun relatieve overeenkomst wil aangeven. Voor veel toepassingen kan het voldoende zijn om enkele trefwoorden te vinden die exact overeenkomen. Een voorbeeld waarbij exact matchen niet altijd voldoende is, is de spamdetectie . Een andere zou zijn in computationele genanalyse, waarbij homologe genen zijn gemuteerd , resulterend in gemeenschappelijke subsequenties samen met verwijderde, ingevoegde of vervangen symbolen.

Motivatie

Aangezien verschillende beproefde methoden voor het clusteren van gegevens, classificatie en het ophalen van informatie (bijvoorbeeld ondersteunende vectormachines) zijn ontworpen om op vectoren te werken (dwz gegevens zijn elementen van een vectorruimte), maakt het gebruik van een string-kernel de uitbreiding van deze methoden mogelijk gegevens.

De string-kernel-methode moet worden gecontrasteerd met eerdere benaderingen voor tekstclassificatie, waarbij kenmerkvectoren alleen de aan- of afwezigheid van een woord aangeven. Het verbetert niet alleen deze benaderingen, maar het is ook een voorbeeld voor een hele klasse van kernels aangepast aan datastructuren, die begonnen te verschijnen aan het begin van de 21e eeuw. Een overzicht van dergelijke methoden is samengesteld door Gärtner.

In bio-informatica worden snaarpitten vooral gebruikt om biologische sequenties zoals eiwitten of DNA om te zetten in vectoren voor verder gebruik in machine learning-modellen. Een voorbeeld van een string-kernel die voor dat doel wordt gebruikt, is de profielkernel.

Definitie

Een kernel op een domein is een functie die aan bepaalde voorwaarden voldoet ( symmetrisch zijn in de argumenten, continu en positief semidefiniet in zekere zin). ${\ displaystyle D}$${\ displaystyle K: D \ maal D \ rightarrow \ mathbb {R}}$

Mercer stelling beweert dat kan dan worden uitgedrukt door het afbeelden van de argumenten in een inproductruimte . ${\ displaystyle K}$${\ Displaystyle K (x, y) = \ varphi (x) \ cdot \ varphi (y)}$${\ displaystyle \ varphi}$

We kunnen nu de definitie van een string-subreeks-kernel reproduceren op strings boven een alfabet . Coördinatengewijs wordt de mapping als volgt gedefinieerd: ${\ displaystyle \ Sigma}$

${\ displaystyle \ varphi _ {u}: \ left \ {{\ begin {array} {l} \ Sigma ^ {n} \ rightarrow \ mathbb {R} ^ {\ Sigma ^ {n}} \\ s \ mapsto \ sum _ {\ mathbf {i}: u = s _ {\ mathbf {i}}} \ lambda ^ {l (\ mathbf {i})} \ end {array}} \ right.}$

Het zijn multi-indices en is een string van lengte : subreeksen kunnen op een niet-aaneengesloten manier voorkomen, maar hiaten worden bestraft. De multiindex geeft de posities weer van de karakters die overeenkomen in . is het verschil tussen de eerste en laatste invoer in , dat wil zeggen: hoe ver uit elkaar in de subreeksovereenkomst . De parameter kan worden ingesteld op elke waarde tussen (hiaten zijn niet toegestaan, want alleen is niet maar ) en (zelfs wijdverbreide "occurrences" worden op dezelfde manier gewogen als verschijningen als een aangrenzende substring, zoals ). ${\ displaystyle \ mathbf {i}}$${\ displaystyle u}$${\ displaystyle n}$${\ displaystyle \ mathbf {i}}$${\ displaystyle u}$${\ displaystyle s}$${\ displaystyle l (\ mathbf {i})}$${\ displaystyle \ mathbf {i}}$${\ displaystyle s}$${\ displaystyle u}$${\ displaystyle \ lambda}$${\ displaystyle 0}$${\ displaystyle 0 ^ {0}}$${\ displaystyle 0}$${\ displaystyle 1}$${\ displaystyle 1}$${\ displaystyle 1 ^ {l (\ mathbf {i})} = 1}$

Voor verschillende relevante algoritmen komen gegevens alleen in het algoritme binnen in uitdrukkingen met een inproduct van kenmerkvectoren, vandaar de naam kernelmethoden . Een wenselijk gevolg hiervan is dat men de transformatie niet expliciet hoeft te berekenen , alleen het inproduct via de pit, wat veel sneller kan zijn, zeker bij benadering . ${\ displaystyle \ phi (x)}$

Referenties