Kernemetode - Kernel method

En del af en serie om
Machine learning og data mining
Problemer Klassifikation Klyngedannelse Regression Anomali detektion AutoML Foreningsregler Forstærkning læring Struktureret forudsigelse Funktionsteknik Feature learning Online læring Semi-overvåget læring Uovervåget læring At lære at rangere Grammatikinduktion
Overvåget læring ( klassificering  • regression ) Beslutningstræer Ensembler Bagging Boosting Tilfældig skov k -NN Lineær regression Naive Bayes Kunstige neurale netværk Logistisk regression Perceptron Relevansvektormaskine (RVM) Support vector machine (SVM)
Klyngedannelse BIRK HELBREDE Hierarkisk k- betyder Forventning – maksimering (EM) DBSCAN OPTIK Gennemsnit-skift
Dimensionalitetsreduktion Faktoranalyse CCA ICA LDA NMF PCA PGD t-SNE
Struktureret forudsigelse Grafiske modeller Bayes net Betinget tilfældigt felt Skjult Markov
Anomali detektion k -NN Lokal afvigende faktor
Kunstigt neuralt netværk Autokoder Kognitiv computing Dyb læring DeepDream Multilayer perceptron RNN LSTM GRU ESN Begrænset Boltzmann-maskine GAN SOM Konvolutions neurale netværk U-Net Transformer Spiking neuralt netværk Memtransistor Elektrokemisk RAM (ECRAM)
Forstærkning læring Q-læring SARSA Temporal forskel (TD)
Teori Bias – varians afvejning Computational learning theory Empirisk risikominimering Occam læring PAC-læring Statistisk læring VC teori
Maskinindlæringssteder NeurIPS ICML ML JMLR ArXiv: cs.LG
Relaterede artikler Ordliste over kunstig intelligens Liste over datasæt til maskinlæringsforskning Oversigt over maskinlæring
v t e

I maskinindlæring er kernemaskiner en klasse algoritmer til mønsteranalyse , hvis bedst kendte medlem er support-vector machine (SVM). Den generelle opgave med mønsteranalyse er at finde og studere generelle typer relationer (for eksempel klynger , placeringer , hovedkomponenter , korrelationer , klassifikationer ) i datasæt. For mange algoritmer, der løser disse opgaver, skal dataene i rå repræsentation udtrykkeligt omdannes til funktionsvektorrepræsentationer via et brugerdefineret funktionskort : I modsætning hertil kræver kernemetoder kun en brugerdefineret kerne , dvs. en lighedsfunktion over par af datapunkter i rå repræsentation.

Kernemetoder skylder deres navn brugen af kernefunktioner , som gør det muligt for dem at operere i et højdimensionelt, implicit funktionsrum uden nogensinde at beregne koordinaterne for dataene i det rum, men snarere ved blot at beregne de indre produkter mellem billederne af alle par af data i funktionsområdet. Denne operation er ofte beregningsmæssigt billigere end den eksplicitte beregning af koordinaterne. Denne tilgang kaldes " kernetricket ". Kernefunktioner er blevet introduceret til sekvensdata, grafer , tekst, billeder såvel som vektorer.

Algoritmer, der er i stand til at operere med kerner, inkluderer kerneperceptron , support-vector-maskiner (SVM), Gaussiske processer , analyse af hovedkomponenter (PCA), kanonisk korrelationsanalyse , højderygsregression , spektral gruppering , lineære adaptive filtre og mange andre.

De fleste kernealgoritmer er baseret på konveks optimering eller egenproblemer og er statistisk velbegrundede. Typisk analyseres deres statistiske egenskaber ved hjælp af statistisk læringsteori (for eksempel ved anvendelse af Rademacher-kompleksitet ).

Motivation og uformel forklaring

Kernemetoder kan betragtes som instansbaserede elever : I stedet for at lære nogle faste sæt parametre, der svarer til funktionerne i deres input, "husker" de i stedet det 5. træningseksempel og lærer en tilsvarende vægt for det . Forudsigelse for umærkede input, dvs. dem der ikke er i træningssættet, behandles ved anvendelse af en lighedsfunktion , kaldet en kerne , mellem den umærkede input og hver af træningsindgangene . For eksempel beregner en kerneliseret binær klassifikator typisk en vægtet sum af ligheder ${\ displaystyle i}$${\ displaystyle (\ mathbf {x} _ {i}, y_ {i})}$${\ displaystyle w_ {i}}$ ${\ displaystyle k}$${\ displaystyle \ mathbf {x '}}$${\ displaystyle \ mathbf {x} _ {i}}$

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

hvor

• ${\ displaystyle {\ hat {y}} \ in \ {- 1, + 1 \}}$er den kerneliserede binære klassificerings forudsagte etiket for den umærkede input, hvis skjulte ægte etiket er af interesse;${\ displaystyle \ mathbf {x '}}$${\ displaystyle y}$
• ${\ displaystyle k \ colon {\ mathcal {X}} \ times {\ mathcal {X}} \ to \ mathbb {R}}$er kernefunktionen, der måler ligheden mellem ethvert par input ;${\ displaystyle \ mathbf {x}, \ mathbf {x '} \ i {\ mathcal {X}}}$
• summen spænder over de n mærkede eksempler i klassificerings træningssættet med ;${\ displaystyle \ {(\ mathbf {x} _ {i}, y_ {i}) \} _ {i = 1} ^ {n}}$${\ displaystyle y_ {i} \ in \ {- 1, + 1 \}}$
• det er vægten til træningseksemplerne som bestemt af læringsalgoritmen${\ displaystyle w_ {i} \ in \ mathbb {R}}$
• det tegn funktionen bestemmer, om den forudsagte klassifikation kommer ud positiv eller negativ.${\ displaystyle \ operatorname {sgn}}$${\ displaystyle {\ hat {y}}}$

Kerneklassifikatorer blev beskrevet så tidligt som i 1960'erne med opfindelsen af kerneperceptronen . De steg til stor fremtrædende plads med populariteten af support-vector machine (SVM) i 1990'erne, da SVM viste sig at være konkurrencedygtige med neurale netværk om opgaver som håndskriftsgenkendelse .

Matematik: kernetricket

SVM med kerne givet af φ (( a , b )) = ( a , b , a ² + b ² ) og dermed K ( x , y ) = . Træningspunkterne kortlægges til et 3-dimensionelt rum, hvor et adskillende hyperplan let kan findes.${\ displaystyle \ mathbf {x} \ cdot \ mathbf {y} + \ left \ | \ mathbf {x} \ right \ | ^ {2} \ left \ | \ mathbf {y} \ right \ | ^ {2} }$

Kernetricket undgår den eksplicitte kortlægning, der er nødvendig for at få lineære indlæringsalgoritmer til at lære en ikke-lineær funktion eller beslutningsgrænse . For alle og i inputrummet kan visse funktioner udtrykkes som et indre produkt i et andet rum . Funktionen kaldes ofte en kerne eller en kernefunktion . Ordet "kerne" bruges i matematik til at betegne en vægtningsfunktion for en vægtet sum eller integral . ${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbf {x '}}$${\ displaystyle {\ mathcal {X}}}$${\ displaystyle k (\ mathbf {x}, \ mathbf {x '})}$${\ displaystyle {\ mathcal {V}}}$${\ displaystyle k \ colon {\ mathcal {X}} \ times {\ mathcal {X}} \ to \ mathbb {R}}$

Visse problemer i maskinindlæring har mere struktur end en vilkårlig vægtningsfunktion . Beregningen gøres meget enklere, hvis kernen kan skrives i form af et "funktionskort", der tilfredsstiller ${\ displaystyle k}$${\ displaystyle \ varphi \ colon {\ mathcal {X}} \ til {\ mathcal {V}}}$

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

Nøglebegrænsningen er, at det skal være et ordentligt indre produkt. På den anden side er en eksplicit repræsentation ikke nødvendig, så længe det er et indre produktrum . Alternativet følger af Mercer's sætning : en implicit defineret funktion eksisterer, når rummet kan udstyres med et passende mål, der sikrer, at funktionen opfylder Mercer's tilstand . ${\ displaystyle \ langle \ cdot, \ cdot \ rangle _ {\ mathcal {V}}}$${\ displaystyle \ varphi}$${\ displaystyle {\ mathcal {V}}}$${\ displaystyle \ varphi}$${\ displaystyle {\ mathcal {X}}}$${\ displaystyle k}$

Mercers sætning svarer til en generalisering af resultatet fra lineær algebra, der forbinder et indre produkt til enhver positiv-bestemt matrix . Faktisk kan Mercers tilstand reduceres til dette enklere tilfælde. Hvis vi vælger som mål det tællende mål for alle , der tæller antallet af punkter inde i sættet , reduceres integralet i Mercer's sætning til en summering ${\ displaystyle \ mu (T) = | T |}$${\ displaystyle T \ subset X}$${\ displaystyle T}$

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

Hvis denne opsummering gælder for alle endelige sekvenser af punkter i og alle valg af reelle værdiansatte koefficienter (jf. Positiv bestemt kerne ), så opfylder funktionen Mercer's tilstand. ${\ displaystyle (\ mathbf {x} _ {1}, \ dotsc, \ mathbf {x} _ {n})}$${\ displaystyle {\ mathcal {X}}}$${\ displaystyle n}$${\ displaystyle (c_ {1}, \ prikker, c_ {n})}$${\ displaystyle k}$

Nogle algoritmer, der afhænger af vilkårlige forhold i det oprindelige rum, ville faktisk have en lineær fortolkning i en anden indstilling: rækkevidden af . Den lineære fortolkning giver os indsigt i algoritmen. Desuden er der ofte ikke behov for at beregne direkte under beregningen, som det er tilfældet med support-vektor maskiner . Nogle nævner denne genvej til kørselstid som den primære fordel. Forskere bruger det også til at retfærdiggøre betydningen og egenskaberne ved eksisterende algoritmer. ${\ displaystyle {\ mathcal {X}}}$${\ displaystyle \ varphi}$${\ displaystyle \ varphi}$

Teoretisk set skal en Gram-matrix med hensyn til (undertiden også kaldet en "kernematrix") hvor , være positiv semidefinit (PSD) . Empirisk, for maskinlæringsheuristik, kan valg af en funktion , der ikke opfylder Mercer's tilstand, stadig udføre rimeligt, hvis i det mindste tilnærmer sig den intuitive idé om lighed. Uanset om der er en Mercer-kerne, kan den stadig kaldes en "kerne". ${\ displaystyle \ mathbf {K} \ in \ mathbb {R} ^ {n \ times n}}$${\ displaystyle \ {\ mathbf {x} _ {1}, \ dotsc, \ mathbf {x} _ {n} \}}$${\ displaystyle K_ {ij} = k (\ mathbf {x} _ {i}, \ mathbf {x} _ {j})}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle k}$

Hvis kernefunktionen også er en kovariansfunktion som anvendt i Gaussiske processer , kan Gram-matrixen også kaldes en kovariansmatrix . ${\ displaystyle k}$${\ displaystyle \ mathbf {K}}$

Ansøgninger

Anvendelsesområder for kernemetoder er forskellige og inkluderer geostatistik , kriging , invers afstandsvægtning , 3D-rekonstruktion , bioinformatik , kemoinformatik , informationsudvinding og håndskriftgenkendelse .

Populære kerner

• Fisher-kerne
• Grafkerner
• Kerne jævnere
• Polynom kerne
• Radial basis funktionskerne (RBF)
• Strengkerner
• Neural tangentkerne
• Neuss netværk Gaussisk proces (NNGP) kerne

Se også

• Kernemetoder til vektoroutput
• Estimering af kernetæthed
• Repræsenterer sætning
• Cover's sætning

Referencer

Yderligere læsning

• Shawe-Taylor, J .; Cristianini, N. (2004). Kernemetoder til mønsteranalyse . Cambridge University Press.
• Liu, W .; Principe, J .; Haykin, S. (2010). Kerneadaptiv filtrering: En omfattende introduktion . Wiley.
• Schölkopf, B .; Smola, AJ; Bach, F. (2018). Læring med kerner: Understøtter vektormaskiner, regulering, optimering og videre . MIT Tryk. ISBN 978-0-262-53657-8.

eksterne links

• Kernel-Machines Org -community hjemmeside
• onlineprediction.net Kernel Methods Article