Strengkerne

En strengkerne er en kernefunktion defineret på strenge , dvs. endelige sekvenser af tegn, der ikke nødvendigvis har samme længde. Stringkerner kan intuitivt forstås som funktioner, der måler ligheden mellem strengepar - jo mere ens to strenge a og b er, jo større er værdien af strengkernen K(a, b) .

Brugen af strengkerner med kerneindlæringsalgoritmer , såsom understøttende vektormaskiner, tillader sådanne algoritmer at operere på strenge uden at skulle konvertere dem til konstantlængde featurevektorer , der har reelle elementer [1] . Strengkerner bruges i områder, hvor en sekvens af data er grupperet eller klassificeret, såsom tekstdatabehandling og genanalyse [2] .

Uformel introduktion

Antag, at nogen automatisk vil sammenligne to stykker tekst og bestemme deres relative lighed. For mange applikationer kan det være tilstrækkeligt at finde nogle helt matchende søgeord. Et eksempel, hvor et sådant nøjagtigt match ikke altid er tilstrækkeligt, kan findes i spam- detektorer [3] . Et andet eksempel er computergenanalyse, hvor homologe gener har mutationer , hvor karakterer i den samlede sekvens kan slettes, indsættes eller erstattes.

Baggrund

Da nogle veletablerede metoder til at klynge, klassificere og udtrække information fra data (f.eks. understøtte vektormaskine) er designet til at arbejde med vektorer (dvs. dataene repræsenterer elementer af et vektorrum), tillader brugen af en strengkerne. disse metoder skal udvides til sekventielle data.

Strengekernemetoden står i kontrast til de almindelige tekstklassificeringsmetoder før dens fremkomst, hvor featurevektorerne kun viste tilstedeværelsen eller fraværet af et ord. Dette forbedrede ikke kun eksisterende tilgange, men er også et eksempel på, hvordan hele klassen af kerner tilpasser sig de datastrukturer, der begyndte at dukke op i det 21. århundrede. En gennemgang af sådanne metoder blev lavet af Gärtner [4] .

I bioinformatik bruges strengkerner til at transformere biologiske sekvenser såsom proteiner eller DNA til vektorer til videre brug i maskinlæringsmodeller. Et eksempel på en strengkerne til sådanne formål er profilkernen [5] .

Definition

Kernen i domænet D er en funktion , der opfylder nogle betingelser ( symmetrisk i argumenter, kontinuerlig , positiv bestemt i en eller anden forstand). $K:D\times D\to \mathbb {R}$

Mercers sætning siger, at K så kan udtrykkes som enc-funktion, derkortlægger argumenterne til et punktproduktrum . $K(x,y)=\varphi (x)\cdot \varphi (y)$ $\varphi$

Vi kan nu gengive definitionen af kernen af streng-undersekvenser [1] over strenge fra alfabetet . Den koordinatvise kortlægning er defineret som følger: $\Sigma$

\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.

Indeksene er multiindekser , og u er en streng med længde n - undersekvenser kan være diskontinuerlige, men huller straffes. Multiindekset angiver de matchende positioner for tegnene i u og s . er forskellen mellem første og sidste element i , altså hvor langt en delfølge i s er fra dens tilsvarende delfølge i u . Parameteren kan indstilles til en hvilken som helst værdi mellem 0 (gab er ikke tilladt, da kun 0 0 ikke er 0, men 1) og 1 (undersekvenser selv med store afstande vejer det samme som uden afstande, det vil sige som kontinuerlige undersekvenser), siden . $\mathbf{i}$ $\mathbf{i}$ $l(\mathbf {i} )$ $\mathbf{i}$ $\lambda$ $1^{l(\mathbf {i} )}=1$

For nogle vigtige algoritmer opnås dataene kun af algoritmen i udtryk, der bruger det skalære produkt af feature-vektoren, hvorfor de kaldes kernemetoder . Derfor er det ønskeligt, at det ikke er nødvendigt eksplicit at beregne transformationen , men det ville være muligt kun at beregne det skalære produkt gennem kernen, hvilket kan være meget hurtigere, især når man bruger tilnærmelse [1] . $\varphi(x)$

Noter

↑ 1 2 3 Lodhi, Saunders, Shawe-Taylor, Cristianini, Watkins, 2002 , s. 419-444.
↑ Leslie, Eskin, Noble, 2002 , s. 566-575.
↑ Amayri, Bouguila .
↑ Gartner, 2003 .
↑ Kuang, Ie, Wang et al., 2005 , s. 527-550.

Litteratur

Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, Chris Watkins. Tekstklassificering ved hjælp af strengkerner // Journal of Machine Learning Research. - 2002.
Leslie C., Eskin E., Noble WS Pacific Symposium on Biocomputing Proceedings. - 2002.
Ola Amayri, Nizar Bouguila. Forbedret online support vektormaskiner spamfiltrering ved hjælp af strengkerner // Fremskridt i mønstergenkendelse, billedanalyse, computersyn og applikationer. 14. Iberoamerican Conference on Pattern Recognition, CIARP 2009, Guadalajara, Jalisco, Mexico, 15.-18. november. — Springer. - T. 5856. - (Forelæsningsnotater i Datalogi).
Gärtner T. En undersøgelse af kerner til strukturerede data // ACM SIGKDD Exploration Newsletter. - ACM, 2003. - V. 5 , no. 1 .
Rui Kuang, Eugene Ie, Ke Wang, Kai Wang, Mahira Siddiqi, Yoav Freund, Christina Leslie. Profilbaserede strengkerner til fjernhomologidetektion og motivekstraktion // Journal of Bioinformatics and Computational Biology. - 2005. - Juni ( bind 3 , hæfte 3 ). — ISSN 0219-720 .

Machine learning og data mining
Opgaver	Klassifikationsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-Net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG