Metoda nucleara

Metodele nucleare în învățarea automată este o clasă de algoritmi de recunoaștere a modelelor , cel mai faimos reprezentant al cărora este mașina vector de suport (SVM, ing. SVM ). Sarcina generală a recunoașterii modelelor este de a găsi și de a învăța tipuri comune de relații (de exemplu , grupuri , clasamente , componente principale , corelații , clasificări ) în seturile de date. Pentru mulți dintre algoritmii care rezolvă aceste probleme, datele brute sunt convertite în mod explicit într-o reprezentare vectorială caracteristică printr-o schemă specifică de distribuție a caracteristicilor , dar metodele nucleului necesită doar un nucleu specific , de exemplu. funcțiile de similaritate ale perechilor de puncte de date în reprezentarea brută.

Metodele kernel și-au primit numele de la utilizarea funcțiilor kernel , care le permit să opereze într -un spațiu de caracteristici implicite de dimensiuni mari fără a calcula coordonatele datelor în spațiu, pur și simplu prin calcularea produselor punctiforme dintre imaginile tuturor datelor. perechi în spațiul caracteristic. Această operație este adesea mai ieftină din punct de vedere computațional decât calculele explicite de coordonate. Această abordare este numită „ smecheria nucleară ” [1] . Au fost introduse funcții kernel pentru date seriale, grafice , texte, imagini și, de asemenea, pentru vectori.

Printre algoritmii capabili să lucreze cu nuclee se numără perceptronul nuclear , mașinile vectoriale suport, procesele gaussiene , analiza componentelor principale ( PCA ), analiza corelației canonice , regresia crestei , gruparea spectrală , filtrele adaptative liniare și multe altele . Orice model liniar poate fi convertit într-un model neliniar prin aplicarea unui truc nucleu modelului, înlocuindu-i caracteristicile (predictorii) cu o funcție de nucleu.

Majoritatea algoritmilor nucleului se bazează pe optimizarea convexă sau pe găsirea vectorilor proprii și sunt bine fundamentate statistic. De obicei, proprietățile lor statistice sunt analizate folosind teoria învățării statistice (de exemplu, folosind complexitatea Rademacher ).

Cauze și explicație informală

Metodele kernel pot fi considerate ca învățarea prin exemplu — în loc să învețe un set fix de parametri corespunzători caracteristicilor de intrare, ele „își amintesc” de al- lea exemplu de antrenament și se antrenează în funcție de greutățile acestuia . Predicția pentru intrare neetichetată, de ex. care nu este inclus în setul de antrenament este învățat folosind funcția de similaritate (numită nucleu ) între intrarea neetichetată și fiecare dintre intrările de antrenament . De exemplu, un clasificator binar nucleu calculează de obicei o sumă de similitudine ponderată folosind formula $i$ $(\mathbf {x} _{i}, y_{i})$ $w_{i}$ $k$ ${\mathbf {x'))$ $\mathbf {x} _{i)$

{\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k(\mathbf {x} _{i},\mathbf {X'} )

Unde

${\hat {y}}\in \{-1,+1\}$ este un clasificator binar nucleu al etichetei prezise pentru intrarea neetichetată a cărei etichetă corectă ascunsă este necesară; ${\mathbf {x'))$ $y$
$k\colon {\mathcal {X}}\times {\mathcal {X}}\la \mathbb {R}$ este o funcție de nucleu care măsoară asemănarea unei perechi de intrări ; $\mathbf {x} ,\mathbf {x'} \in {\mathcal {X)}$
suma rulează peste toate n exemple etichetate din setul de antrenament al clasificatorului cu ; $\{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n)$ $y_{i}\in \{-1,+1\)$
$w_{i}\in \mathbb {R}$ sunt ponderile exemplelor de antrenament, așa cum sunt determinate de algoritmul de învățare;
Funcția sgn determină dacă clasificarea prezisă va fi pozitivă sau negativă.

Clasificatorii nucleari au fost descriși la începutul anilor 1960 odată cu inventarea perceptronului nuclear [2] . Au câștigat o largă acceptare împreună cu popularitatea mașinilor vector de suport în anii 1990, când SVM s-a dovedit a fi competitiv cu rețelele neuronale în sarcini precum recunoașterea scrisului de mână .

Matematică: trucul nuclear

Trucul nucleului evită maparea explicită necesară pentru a obține un algoritm de învățare liniar pentru o funcție neliniară sau o limită de decizie . Pentru toate și în spațiul de intrare, unele funcții pot fi reprezentate ca un produs punctual într-un alt spațiu . Funcția este adesea denumită funcția kernel sau kernel . Cuvântul „nucleu” este folosit în matematică pentru a se referi la o funcție de greutate sau integrală . $\mathbf {x}$ ${\mathbf {x'))$ ${\mathcal {X}}$ $k(\mathbf {x} ,\mathbf {x'} )$ ${\mathcal {V))$ $k\colon {\mathcal {X}}\times {\mathcal {X}}\la \mathbb {R}$

Unele probleme de învățare automată au o structură suplimentară, mai degrabă decât o funcție de greutate . Calculele vor fi mult mai ușoare dacă nucleul poate fi scris ca o „mapping de caracteristici” care satisface egalitatea $k$ $\varphi \colon {\mathcal {X}}\to {\mathcal {V}}$

k(\mathbf {x} ,\mathbf {x'} )=\langle \varphi (\mathbf {x}),\varphi (\mathbf {x'} )\rangle _{\mathcal {V} }.

Principala constrângere aici este ceea ce trebuie să fie un produs punct potrivit. Pe de altă parte, nu este necesară o reprezentare explicită pentru, deoarece este un spațiu de produs punctual . Alternativa rezultă din teorema lui Mercer — există o funcție definită implicit dacă spațiul poate fi echipat cu o măsură adecvată care să asigure că funcția satisface condiția lui Mercer . $\langle \cdot ,\cdot \rangle _{\mathcal {V}}$ $\varphi$ ${\mathcal {V))$ $\varphi$ ${\mathcal {X}}$ $k$

Teorema lui Mercer este ca o generalizare a unui rezultat din algebra liniară care raportează produsul punctual la orice matrice definită pozitivă . De fapt, starea lui Mercer poate fi redusă la acest caz simplu. Dacă alegem ca măsură o măsură de numărare pentru toate , care numără numărul de puncte din interiorul mulțimii , atunci integrala din teorema lui Mercer se reduce la însumare $\mu (T)=|T|$ $T\subset X$ $T$

\sum _{i=1}^{n}\sum _{j=1}^{n}k(\mathbf {x} _{i},\mathbf {x} _{j})c_ {i}c_{j}\geq 0.

Dacă această inegalitate este valabilă pentru toate secvențele finite de puncte din și toate seturile de coeficienți cu valori reale (cf. Nucleu definit pozitiv ), atunci funcția satisface condiția lui Mercer. $(\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})$ ${\mathcal {X}}$ $n$ $(c_{1},\dots ,c_{n})$ $k$

Unii algoritmi care depind de legături arbitrare din spațiul inițial vor avea, de fapt, o reprezentare liniară în alte condiții - în spațiul interval . Interpretarea liniară ne oferă o idee despre algoritm. Mai mult decât atât, adesea nu este necesar să se calculeze direct în momentul calculării, așa cum este cazul mașinii vector suport . Unii consideră reducerea timpului datorită acestui fapt principalul avantaj al algoritmului. Cercetătorii îl folosesc pentru a rafina semnificația și proprietățile algoritmilor existenți. ${\mathcal {X}}$ $\varphi$ $\varphi$

Teoretic, matricea Gram în raport cu (uneori numită „matricea nucleului” [3] ), unde , ar trebui să fie semidefinită pozitivă [4] . Din punct de vedere empiric, pentru euristica învățării automate, alegerea unei funcții care nu satisface condiția lui Mercer poate fi totuși justificată dacă cel puțin aproximează ideea intuitivă de similaritate [5] . Indiferent dacă nucleul este sau nu Mercer, o poate continua să fie denumit „nucleul”. $\mathbf {K} \in \mathbb {R} ^{n\times n}$ $\{\mathbf {x} _{1},\dotsc,\mathbf {x} _{n}\)$ $K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})$ $k$ $k$ $k$ $k$

Dacă funcția de nucleu este și o funcție covariantă , care este utilizată într-un proces gaussian , atunci matricea Gram poate fi numită matrice de covarianță [6] . $k$ ${\mathbf {K}}$

Aplicații

Aplicațiile metodelor nucleare sunt diverse și includ geostatistica [7] , kriging , ponderarea distanței , reconstrucția 3D , bioinformatica , chimioinformatica , extragerea informațiilor și recunoașterea scrisului de mână .

Kernel-uri populare

Fisher kernel
Graph kernel
Nuclear Smoother
Nucleu polinom
Nucleu de funcție de bază radială
Sâmburi de șir

Note

↑ Theodoridis, 2008 , p. 203.
↑ Aizerman, Braverman, Rozoner, 1964 , p. 821–837.
↑ Hofmann, Scholkopf, Smola, 2007 .
↑ Mohri, Rostamizadeh, Talwalkar, 2012 .
↑ Sewell, Martin Support Vector Machines: Mercer's Condition . www.svms.org . (nedefinit)
↑ Rasmussen, Williams, 2006 .
↑ Honarkhah, Caers, 2010 , p. 487–517.

Literatură

Aizerman MA, Emmanuel M. Braverman, Rozoner LI Fundamentele teoretice ale metodei funcției potențiale în învățarea recunoașterii modelelor // Automatizare și control de la distanță. - 1964. - T. 25 . — S. 821–837 . Citat in articol
- Isabelle Guyon, B. Boser, Vladimir Vapnik. Reglarea automată a capacității clasificatoarelor de dimensiune VC foarte mari // Progrese în sistemele de procesare a informațiilor neuronale. — 1993.
Sergios. recunoasterea formelor. - Elsevier BV, 2008. - ISBN 9780080949123 .
Mehryar Mohri, Afshin Rostamizadeh și Ameet Talwalkar. . - Cambridge, Londra: MIT press, 2012. - (Adaptive Computation and Machine Learning). - ISBN 978-0-262-01825-8 .
Thomas Hofmann, Bernhard Scholkopf, Alexander J. Smola. Metode kernel în învățarea automată // Analele statisticilor. - 2007. - ianuarie ( vol. 36 , numărul 3 ).
Rasmussen CE, Williams CKI Gaussian Processes for Machine Learning. - Cambridge, Londra: MIT Press, 2006. - (Adaptive Computation and Machine Learning). — ISBN 0-262-18253-X .
Honarkhah M., Caers J. Stochastic Simulation of Patterns Using Distance-Based Pattern Modeling // Geoștiințe matematice . - 2010. - T. 42 . - doi : 10.1007/s11004-010-9276-7 .

Literatură

John Shawe-Taylor, Nello Cristianini. Metode nucleu pentru analiza modelelor. — Cambridge University Press, 2004.
Liu W., Principe J., Haykin S. Kernel Adaptive Filtering: A Comprehensive Introduction. Wiley, 2010.

Link

Kernel-Machines Org -site-ul comunității
www.support-vector-machines.org (literatură, recenzii, software, link-uri legate de Support Vector Machines - site academic)
onlineprediction.net Articol Metode Kernel

Î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