Strengkerne - String kernel

I maskinindlæring og datamining er en strengkerne en kernefunktion, der fungerer på strenge , dvs. endelige sekvenser af symboler, der ikke behøver at have samme længde. Strengkerner kan intuitivt forstås som funktioner, der måler ligheden mellem par af strenge: jo mere ens to strenge a og b er ens , jo højere er værdien af ​​en strengkerne K ( a , b ).

Brug af strengkerner med kerneliserede indlæringsalgoritmer, såsom supportvektormaskiner, gør det muligt for sådanne algoritmer at arbejde med strenge uden at skulle oversætte disse til faste længdevirkelige funktionsvektorer . Strengkerner bruges i domæner, hvor sekvensdata skal grupperes eller klassificeres , f.eks. I tekstminedrift og genanalyse .

Uformel introduktion

Antag, at man ønsker at sammenligne nogle tekstpassager automatisk og angive deres relative lighed. For mange applikationer kan det være tilstrækkeligt at finde nogle nøgleord, der matcher nøjagtigt. Et eksempel, hvor nøjagtig matchning ikke altid er nok, findes i spamdetektering . En anden ville være i beregningsgenanalyse, hvor homologe gener er muteret , hvilket resulterer i fælles efterfølgende sammen med slettede, indsatte eller udskiftede symboler.

Motivering

Da flere velprøvede dataklyngemetoder, klassificering og informationssøgningsmetoder (f.eks. Understøttende vektormaskiner) er designet til at arbejde på vektorer (dvs. data er elementer i et vektorrum), gør det muligt at bruge en strengekerne udvidelse af disse metoder til at håndtere sekvens data.

Stringkernemetoden skal kontrasteres med tidligere fremgangsmåder til tekstklassificering, hvor funktionsvektorer kun angav tilstedeværelsen eller fraværet af et ord. Det forbedrer ikke kun disse tilgange, men det er et eksempel på en hel klasse kerner tilpasset datastrukturer, som begyndte at dukke op ved begyndelsen af ​​det 21. århundrede. En undersøgelse af sådanne metoder er udarbejdet af Gärtner.

I bioinformatik bruges strengkerner især til at omdanne biologiske sekvenser såsom proteiner eller DNA til vektorer til yderligere brug i maskinlæringsmodeller. Et eksempel på en strengkerne, der bruges til dette formål, er profilkernen.

Definition

En kerne på et domæne er en funktion, der opfylder visse betingelser (er symmetrisk i argumenterne, kontinuerlig og positiv semidefinit i en vis forstand). ${\ displaystyle D}$${\ displaystyle K: D \ times D \ rightarrow \ mathbb {R}}$

Mercers sætning hævder, at den derefter kan udtrykkes som ved at kortlægge argumenterne i et indre produktrum . ${\ displaystyle K}$${\ displaystyle K (x, y) = \ varphi (x) \ cdot \ varphi (y)}$${\ displaystyle \ varphi}$

Vi kan nu gengive definitionen af ​​en strengsekvens-kerne på strenge over et alfabet . Koordinatmæssigt defineres kortlægningen som følger: ${\ 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.}$

De er multiindices og er en længde streng : efterfølgelser kan forekomme på en ikke-sammenhængende måde, men huller straffes. Multiindex angiver placeringen af ​​de tegn, der matcher i . er forskellen mellem den første og sidste post i , det vil sige: hvor langt fra hinanden i den efterfølgende matchning er. Parameteren kan indstilles til en hvilken som helst værdi mellem (huller er ikke tilladt, da det kun ikke er men ) og (selv bredt spredte "forekomster" vægtes det samme som udseendet som en sammenhængende understreng, som ). ${\ 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}$

For flere relevante algoritmer indgår data kun i algoritmen i udtryk, der involverer et indre produkt af funktionsvektorer, deraf navnet kernemetoder . En ønskelig konsekvens af dette er, at man ikke behøver eksplicit at beregne transformationen , kun det indre produkt via kernen, hvilket kan være meget hurtigere, især når det tilnærmes . ${\ displaystyle \ phi (x)}$

Referencer