Nucleu șir

Un nucleu de șir este o funcție de nucleu definită pe șiruri de caractere , adică secvențe finite de caractere care nu au neapărat aceeași lungime. Nuezele de șiruri pot fi înțelese intuitiv ca funcții care măsoară asemănarea perechilor de șiruri - cu cât două șiruri a și b sunt mai asemănătoare, cu atât valoarea nucleului de șiruri K(a, b) este mai mare .

Utilizarea nucleelor de șir cu algoritmi de învățare a nucleului , cum ar fi mașinile de vectori de suport, permite unor astfel de algoritmi să opereze pe șiruri de caractere fără a fi nevoie să le convertească în vectori caracteristici de lungime constantă care au elemente reale [1] . Nuezele de șiruri sunt utilizate în zonele în care o secvență de date este grupată sau clasificată, cum ar fi procesarea datelor de text și analiza genelor [2] .

Introducere informală

Să presupunem că cineva va compara automat două bucăți de text și va determina similaritatea lor relativă. Pentru multe aplicații, poate fi suficient să găsiți câteva cuvinte cheie care se potrivesc complet. Un exemplu în care o astfel de potrivire exactă nu este întotdeauna suficientă poate fi găsit în detectoarele de spam [3] . Un alt exemplu este analiza genelor computerizate, în care genele omoloage au mutații în care caracterele din secvența generală pot fi șterse, inserate sau înlocuite.

Fundal

Deoarece unele metode bine stabilite de grupare, clasificare și extragere a informațiilor din date (de exemplu, mașina de suport vector) sunt concepute pentru a funcționa cu vectori (adică, datele reprezintă elemente ale unui spațiu vectorial), utilizarea unui nucleu de șiruri permite aceste metode să fie extinse la date secvenţiale.

Metoda nucleului șirurilor contrastează cu abordările de clasificare a textului obișnuite înainte de apariția sa, unde vectorii de caracteristică au arătat doar prezența sau absența unui cuvânt. Acest lucru nu numai că a îmbunătățit abordările existente, dar este și un exemplu al modului în care întreaga clasă de nuclee se adaptează la structurile de date care au început să apară în secolul 21. O trecere în revistă a unor astfel de metode a fost făcută de Gärtner [4] .

În bioinformatică, nucleele de șir sunt folosite pentru a transforma secvențe biologice, cum ar fi proteinele sau ADN-ul, în vectori pentru a fi utilizate în continuare în modelele de învățare automată. Un exemplu de nucleu de șir pentru astfel de scopuri este nucleul de profil [5] .

Definiție

Nucleul domeniului D este o funcție care îndeplinește anumite condiții ( simetric în argumente, continuu , definit pozitiv într-un anumit sens). $K:D\times D\to \mathbb {R}$

Teorema lui Mercer afirmă că K poate fi exprimat apoi ca ofuncție c caremapează argumentele la un spațiu de produs punctual . $K(x,y)=\varphi (x)\cdot \varphi (y)$ $\varphi$

Acum putem reproduce definiția nucleului de subsecvențe de șiruri [1] peste șiruri din alfabet . Maparea în funcție de coordonate este definită după cum urmează: $\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.

Indicii sunt multi -indici , iar u este un șir de lungime n - subsecvențele pot fi discontinue, dar golurile sunt penalizate. Multi-indexul specifică pozițiile de potrivire ale caracterelor din u și s . este diferența dintre primul și ultimul element din , adică cât de departe este o subsecvență din s de subsecvența corespunzătoare din u . Parametrul poate fi setat la orice valoare între 0 (nu sunt permise goluri, deoarece doar 0 0 nu este 0, ci 1) și 1 (subsecvențele chiar și cu distanțe mari cântăresc la fel ca și fără distanțe, adică ca subsecvențe continue), din moment ce . $\mathbf{i}$ $\mathbf{i}$ $l(\mathbf {i} )$ $\mathbf{i}$ $\lambda$ $1^{l(\mathbf {i} )}=1$

Pentru unii algoritmi importanți, datele sunt obținute de algoritm numai în expresii care utilizează produsul scalar al vectorului caracteristic, motiv pentru care sunt numite metode kernel . Prin urmare, este de dorit ca nu ar fi necesar să se calculeze explicit transformarea , dar ar fi posibil să se calculeze numai produsul scalar prin nucleu, care poate fi mult mai rapid, mai ales când se utilizează aproximarea [1] . $\varphi(x)$

Note

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

Literatură

Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, Chris Watkins. Clasificarea textului folosind nuclee de șir // Journal of Machine Learning Research. — 2002.
Leslie C., Eskin E., Noble WS Pacific Symposium on Biocomputing Proceedings. — 2002.
Ola Amayri, Nizar Bouguila. Filtrarea de spam a mașinilor vectoriale de asistență online îmbunătățită folosind nuclee de șir // Progres în recunoașterea modelelor, analiza imaginilor, viziunea computerizată și aplicațiile. 14th Iberoamerican Conference on Pattern Recognition, CIARP 2009, Guadalajara, Jalisco, Mexic, 15-18 noiembrie. — Springer. - T. 5856. - (Note de curs în Informatică).
Gärtner T. Un studiu asupra nucleelor pentru date structurate // Buletin informativ de explorare ACM SIGKDD. - ACM, 2003. - V. 5 , nr. 1 .
Rui Kuang, Eugene Ie, Ke Wang, Kai Wang, Mahira Siddiqi, Yoav Freund, Christina Leslie. Miezuri de șir bazate pe profil pentru detectarea la distanță a omologiei și extracția motivelor // Journal of Bioinformatics and Computational Biology. - 2005. - Iunie ( vol. 3 , numărul 3 ). — ISSN 0219-720 .

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbarea medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG