Strängkärna

En strängkärna är en kärnfunktion definierad på strängar , dvs. ändliga teckensekvenser som inte nödvändigtvis har samma längd. Strängkärnor kan intuitivt förstås som funktioner som mäter likheten mellan par av strängar - ju mer lika två strängar a och b är, desto större är värdet på strängkärnan K(a, b) .

Användningen av strängkärnor med algoritmer för inlärning av kärnor , såsom stödvektormaskiner, tillåter sådana algoritmer att arbeta på strängar utan att behöva konvertera dem till funktionsvektorer med konstant längd som har verkliga element [1] . Strängkärnor används i områden där en sekvens av data är klustrade eller klassificerade, såsom textdatabearbetning och genanalys [2] .

Informell introduktion

Anta att någon automatiskt kommer att jämföra två textstycken och fastställa deras relativa likhet. För många applikationer kan det räcka med att hitta några helt matchande sökord. Ett exempel där en sådan exakt matchning inte alltid är tillräcklig kan hittas i skräppostdetektorer [3] . Ett annat exempel är datorgenanalys, där homologa gener har mutationer där tecken i den övergripande sekvensen kan raderas, infogas eller ersättas.

Bakgrund

Eftersom vissa väletablerade metoder för klustring, klassificering och extrahering av information från data (till exempel stödvektormaskin) är utformade för att fungera med vektorer (d.v.s. data representerar element i ett vektorrum), tillåter användningen av en strängkärna dessa metoder ska utvidgas till sekventiell data.

Strängkärnmetoden står i kontrast till de textklassificeringsmetoder som var vanliga innan dess uppkomst, där funktionsvektorerna endast visade närvaron eller frånvaron av ett ord. Detta förbättrade inte bara befintliga tillvägagångssätt, utan är också ett exempel på hur hela klassen av kärnor anpassar sig till de datastrukturer som började dyka upp på 2000-talet. En genomgång av sådana metoder gjordes av Gärtner [4] .

Inom bioinformatik används strängkärnor för att transformera biologiska sekvenser som proteiner eller DNA till vektorer för vidare användning i maskininlärningsmodeller. Ett exempel på en strängkärna för sådana ändamål är profilkärnan [5] .

Definition

Kärnan i domänen D är en funktion som uppfyller vissa villkor ( symmetrisk i argument, kontinuerlig , positiv definitiv i någon mening). $K:D\times D\to \mathbb {R}$

Mercers sats säger att K sedan kan uttryckas som enc-funktion sommappar argumenten till ett punktproduktutrymme . $K(x,y)=\varphi (x)\cdot \varphi (y)$ $\varphi$

Vi kan nu reproducera definitionen av kärnan av strängsubsekvenser [1] över strängar från alfabetet . Den koordinatvisa kartläggningen definieras enligt följande: $\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.

Indexen är multi- index , och u är en sträng med längd n - undersekvenser kan vara diskontinuerliga, men luckor straffas. Multiindexet anger matchande positioner för tecknen i u och s . är skillnaden mellan det första och sista elementet i , det vill säga hur långt en delföljd i s är från dess motsvarande delföljd i u . Parametern kan ställas in på vilket värde som helst mellan 0 (gap är inte tillåtna, eftersom endast 0 0 inte är 0, utan 1) och 1 (undersekvenser även med stora avstånd väger samma som utan avstånd, det vill säga som kontinuerliga undersekvenser), sedan . $\mathbf{i}$ $\mathbf{i}$ $l(\mathbf {i} )$ $\mathbf{i}$ $\lambda$ $1^{l(\mathbf {i} )}=1$

För vissa viktiga algoritmer erhålls data av algoritmen endast i uttryck som använder den skalära produkten av funktionsvektorn, vilket är anledningen till att de kallas kärnmetoder . Därför är det önskvärt att det inte skulle vara nödvändigt att explicit beräkna transformationen , utan det skulle vara möjligt att bara beräkna den skalära produkten genom kärnan, vilket kan vara mycket snabbare, speciellt när man använder approximation [1] . $\varphi(x)$

Anteckningar

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

Litteratur

Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, Chris Watkins. Textklassificering med hjälp av strängkärnor // Journal of Machine Learning Research. – 2002.
Leslie C., Eskin E., Noble WS Pacific Symposium on Biocomputing Proceedings. – 2002.
Ola Amayri, Nizar Bouguila. Förbättrat onlinestöd för vektormaskiner för skräppostfiltrering med hjälp av strängkärnor // Framsteg inom mönsterigenkänning, bildanalys, datorseende och applikationer. 14:e Iberoamerican Conference on Pattern Recognition, CIARP 2009, Guadalajara, Jalisco, Mexiko, 15-18 november. — Springer. - T. 5856. - (Föreläsningsanteckningar i datavetenskap).
Gärtner T. En undersökning av kärnor för strukturerad data // ACM SIGKDD Exploration Newsletter. - ACM, 2003. - V. 5 , nr. 1 .
Rui Kuang, Eugene Ie, Ke Wang, Kai Wang, Mahira Siddiqi, Yoav Freund, Christina Leslie. Profilbaserade strängkärnor för fjärrhomologidetektion och motivextraktion // Journal of Bioinformatics and Computational Biology. - 2005. - Juni ( vol. 3 , nummer 3 ). — ISSN 0219-720 .

Maskininlärning och datautvinning
Uppgifter	Klassificeringsproblem Lärande utan lärare Lärarassisterat lärande Regressionsanalys AutoML Föreningens regler Särdragsextraktion Egenskapsträning Ranking utbildning Grammatisk härledning Online lärande
Att lära sig med en lärare	k-närmaste granne metod Naiv Bayes klassificerare beslutsträd Stöd vektor maskin Linjär regression Logistisk tillbakagång perceptron Ensembler av modeller Säckväv förstärkning slumpmässig skog Relevant vektormetod
klusteranalys	k-betyder metod Fuzzy klustringsmetod Hierarkisk klustring EM algoritm BJÖRK BOTA DBSCAN OPTIK Genomsnittlig förskjutning
Dimensionalitetsreduktion	Faktoranalys Huvudkomponentmetoden CCA ICA LDA Icke-negativ matrisexpansion t-SNE
Strukturell prognos	Graph probabilistisk modell Bayesiskt nätverk Dold Markov-modell CRF
Anomali upptäckt	k-närmaste granne metod Lokal utsläppsnivå
Grafisk probabilistiska modeller	Bayesiskt nätverk Markov nätverk Dold Markov-modell
Neurala nätverk	Begränsad Boltzmann-maskin självorganiserande karta Aktiveringsfunktion Sigmoid softmax Radiell basfunktion Ryggförökningsmetod Djup lärning Flerskiktsperceptron Återkommande neurala nätverk långtidsminne Kontrollerat återkommande block Konvolutionellt neuralt nätverk U-nät Autokodare
Förstärkningsinlärning	Markov process Bellmans ekvation Girig algoritm Q-lärande SARSA Temporell skillnad (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beräkningslärandeteori Empirisk riskminimering Occam lär sig PAC-inlärning Statistisk inlärningsteori
Tidskrifter och konferenser	NeurIPS ICML ML JMLR ArXiv:cs.LG