Nuklear metode

Nukleare metoder i maskinlæring er en klasse af mønstergenkendelsesalgoritmer , hvor den mest berømte repræsentant er støttevektormaskinen (SVM, eng. SVM ). Den generelle opgave med mønstergenkendelse er at finde og lære almindelige typer af relationer (f.eks. klynger , rangeringer , hovedkomponenter , korrelationer , klassifikationer ) i datasæt. For mange af de algoritmer, der løser disse problemer, konverteres rådata eksplicit til en funktionsvektorrepræsentation ved hjælp af et specifikt funktionsfordelingsskema , men kernemetoder kræver kun en specifik kerne , dvs. lighedsfunktionerne for par af datapunkter i den rå repræsentation.

Kernelmetoder har fået deres navn fra brugen af kernefunktioner , som giver dem mulighed for at operere i et højdimensionelt implicit trækrum uden at beregne koordinaterne for dataene i rummet, blot ved at beregne prikprodukterne mellem billederne af alle data par i feature-rummet. Denne operation er ofte beregningsmæssigt billigere end eksplicitte koordinatberegninger. Denne tilgang kaldes " atomtricket " [1] . Kernelfunktioner er blevet introduceret til serielle data, grafer , tekster, billeder og også for vektorer.

Blandt de algoritmer, der er i stand til at arbejde med kerner, er den nukleare perceptron , støttevektormaskiner, Gaussiske processer , principal komponentanalyse ( PCA ), kanonisk korrelationsanalyse , ridge regression , spektral clustering , lineære adaptive filtre og mange andre . Enhver lineær model kan konverteres til en ikke-lineær model ved at anvende et kernetrick på modellen, og erstatte dens funktioner (prædiktorer) med en kernefunktion.

De fleste kernealgoritmer er baseret på konveks optimering eller egenvektorfund og er statistisk velfunderede. Normalt analyseres deres statistiske egenskaber ved hjælp af statistisk læringsteori (for eksempel ved hjælp af Rademacher kompleksitet ).

Årsager og uformel forklaring

Kernelmetoder kan opfattes som læring ved eksempel - i stedet for at lære nogle faste sæt parametre svarende til inputfunktioner, "husker" de det te træningseksempel og træner i henhold til dets vægte . Forudsigelse for umærket input, dvs. ikke inkluderet i træningssættet læres ved hjælp af lighedsfunktionen (kaldet kernen ) mellem det umærkede input og hvert af træningsinputsene . For eksempel beregner en binær kerneklassifikator normalt en vægtet lighedssum ved hjælp af formlen $jeg$ $(\mathbf {x} _{i},y_{i})$ $w_{i}$ $k$ ${\mathbf {x'))$ ${\displaystyle \mathbf {x} _{i))$

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

hvor

${\hat {y}}\in \{-1,+1\}$ er en binær kerneklassificering af den forudsagte etiket for det umærkede input, hvis skjulte korrekte etiket er nødvendig; ${\mathbf {x'))$ $y$
$k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R}$ er en kernefunktion, der måler ligheden mellem et par input ; $\mathbf {x} ,\mathbf {x'} \in {\mathcal {X))$
summen løber over alle n mærkede eksempler i klassificeringssættets træningssæt med ; ${\displaystyle \{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n))$ $y_{i}\in \{-1,+1\}$
$w_{i}\in \mathbb {R}$ er vægten af træningseksemplerne, som bestemt af indlæringsalgoritmen;
sgn-funktionen bestemmer, om den forudsagte klassifikation vil være positiv eller negativ.

Nukleare klassifikatorer blev beskrevet i begyndelsen af 1960'erne med opfindelsen af den nukleare perceptron [2] . De opnåede bred accept sammen med populariteten af støttevektormaskiner i 1990'erne, da SVM viste sig at være konkurrencedygtig med neurale netværk på opgaver såsom håndskriftsgenkendelse .

Mathematics: The Nuclear Trick

Kerneltricket undgår den eksplicitte mapping, der er nødvendig for at få en lineær indlæringsalgoritme for en ikke-lineær funktion eller beslutningsgrænse . For alle og i inputrummet kan nogle funktioner repræsenteres som et prikprodukt i et andet rum . Funktionen omtales ofte som kernen eller kernefunktionen . Ordet "kerne" bruges i matematik til at henvise til en vægtfunktion eller integral . $\mathbf {x}$ ${\mathbf {x'))$ ${\mathcal {X}}$ $k(\mathbf {x} ,\mathbf {x'} )$ ${\mathcal {V))$ $k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R}$

Nogle maskinlæringsproblemer har yderligere struktur i stedet for blot en vægtfunktion . Beregningerne bliver meget nemmere, hvis kernen kan skrives som en "feature mapping" , der opfylder ligheden $k$ $\varphi \colon {\mathcal {X}}\to {\mathcal {V}}$

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

Hovedbegrænsningen her er, hvad der skal være et passende prikprodukt. På den anden side er en eksplicit repræsentation for ikke nødvendig, da det er et punktproduktrum . Alternativet følger af Mercers sætning — en implicit defineret funktion eksisterer, hvis rummet kan udstyres med et passende mål , der sikrer, at funktionen opfylder Mercers betingelse . $\langle \cdot ,\cdot \rangle _{\mathcal {V}}$ $\varphi$ ${\mathcal {V))$ $\varphi$ ${\mathcal {X}}$ $k$

Mercers sætning er som en generalisering af et resultat fra lineær algebra, der relaterer prikproduktet til enhver positiv bestemt matrix . Faktisk kan Mercers tilstand reduceres til dette simple tilfælde. Hvis vi vælger som vores mål et tællemål for alle , som tæller antallet af punkter inde i mængden , så reduceres integralet i Mercers sætning til summering $\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.

Hvis denne ulighed gælder for alle endelige sekvenser af punkter i og alle sæt af reelle koefficienter (jf. Positiv bestemt kerne ), så opfylder funktionen Mercers betingelse. $(\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})$ ${\mathcal {X}}$ $n$ $(c_{1},\dots,c_{n})$ $k$

Nogle algoritmer, der er afhængige af vilkårlige links i det oprindelige rum , vil i virkeligheden have en lineær repræsentation under andre forhold - i det varierede rum . Den lineære fortolkning giver os en idé om algoritmen. Desuden er det ofte ikke nødvendigt at beregne direkte på beregningstidspunktet, som det er tilfældet med støttevektormaskinen . Nogle anser reduktionen i tid på grund af dette som den største fordel ved algoritmen. Forskere bruger det til at forfine betydningen og egenskaberne af eksisterende algoritmer. ${\mathcal {X}}$ $\varphi$ $\varphi$

Teoretisk set bør Gram-matricen med hensyn til (nogle gange kaldet "kernematricen" [3] ), hvor , være positiv semidefinit [4] . Empirisk kan det for heuristik af maskinlæring stadig være berettiget at vælge en funktion, der ikke opfylder Mercers tilstand, hvis den i det mindste nærmer sig den intuitive idé om lighed [5] . Uanset om kernen er Mercer eller ej, kan o fortsat blive omtalt som "kernen". $\mathbf {K} \in \mathbb {R} ^{n\ gange n}$ ${\displaystyle \{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\))$ $K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})$ $k$ $k$ $k$ $k$

Hvis kernefunktionen også er en kovariansfunktion , som bruges i en gaussisk proces , så kan Gram-matricen kaldes kovariansmatricen [6] . $k$ ${\mathbf {K}}$

Ansøgninger

Anvendelser af nukleare metoder er forskellige og omfatter geostatistik [7] , kriging , afstandsvægtning , 3D-rekonstruktion , bioinformatik , kemoinformatik , informationsudtrækning og håndskriftsgenkendelse .

Populære kerner

Fisher kernel
Graph kernel
Nuclear Smoother
Polynomisk kerne
Radial basisfunktionskerne
Strenge kerner

Noter

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

Litteratur

Aizerman MA, Emmanuel M. Braverman, Rozoner LI Teoretisk grundlag for den potentielle funktionsmetode i mønstergenkendelseslæring // Automation and Remote Control. - 1964. - T. 25 . — S. 821–837 . Citeret i artiklen
- Isabelle Guyon, B. Boser, Vladimir Vapnik. Automatisk kapacitetsjustering af meget store VC-dimensionsklassifikatorer // Fremskridt i neurale informationsbehandlingssystemer. - 1993.
Sergios. mønster genkendelse. - Elsevier BV, 2008. - ISBN 9780080949123 .
Mehryar Mohri, Afshin Rostamizadeh og Ameet Talwalkar. . - Cambridge, London: MIT press, 2012. - (Adaptive Computation and Machine Learning). - ISBN 978-0-262-01825-8 .
Thomas Hofmann, Bernhard Scholkopf, Alexander J. Smola. Kernel Methods in Machine Learning // Statistikkens annaler. - 2007. - Januar ( bind 36 , hæfte 3 ).
Rasmussen CE, Williams CKI Gaussiske processer til maskinlæring. - Cambridge, London: MIT Press, 2006. - (Adaptive Computation and Machine Learning). — ISBN 0-262-18253-X .
Honarkhah M., Caers J. Stokastisk simulering af mønstre ved hjælp af afstandsbaseret mønstermodellering // Matematisk geovidenskab . - 2010. - T. 42 . - doi : 10.1007/s11004-010-9276-7 .

Litteratur

John Shawe-Taylor, Nello Cristianini. Kernelmetoder til mønsteranalyse. - Cambridge University Press, 2004.
Liu W., Principe J., Haykin S. Kernel Adaptive Filtering: A Comprehensive Introduction. Wiley, 2010.

Link

Kernel-Machines Org -fællesskabswebsted
www.support-vector-machines.org (litteratur, anmeldelse, software, links relateret til supportvektormaskiner - akademisk websted)
onlineprediction.net Kernel Methods artikel

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