Ydinmenetelmä

Ydinmenetelmät koneoppimisessa on hahmontunnistusalgoritmien luokka , jonka tunnetuin edustaja on tukivektorikone (SVM, eng. SVM ). Kuviontunnistuksen yleistehtävä on löytää ja oppia tietojoukoista yleisiä suhdetyyppejä (esim. klusterit , rankingit , pääkomponentit , korrelaatiot , luokitukset ). Monissa algoritmeissa, jotka ratkaisevat nämä ongelmat, raakadata muunnetaan eksplisiittisesti piirrevektoriesitykseen tietyn ominaisuuden jakautumismallin avulla , mutta ydinmenetelmät vaativat vain tietyn ytimen , ts. datapisteparien samankaltaisuusfunktiot raakaesityksessä.

Ydinmenetelmät ovat saaneet nimensä ytimen funktioiden käytöstä , joiden avulla ne voivat toimia korkeadimensionaalisessa implisiittisessä ominaisuusavaruudessa laskematta avaruudessa olevien tietojen koordinaatteja, yksinkertaisesti laskemalla kaikkien tietojen kuvien väliset pistetulot . paria ominaisuustilassa. Tämä operaatio on usein laskennallisesti halvempi kuin eksplisiittiset koordinaattilaskelmat. Tätä lähestymistapaa kutsutaan " ydintemppuksi " [1] . Ydinfunktiot on otettu käyttöön sarjatiedoille, kaavioille , teksteille, kuville ja myös vektoreille.

Ytimen kanssa toimivia algoritmeja ovat ydinperceptron , tukivektorikoneet, Gaussin prosessit , pääkomponenttianalyysi ( PCA ), kanoninen korrelaatioanalyysi , harjaregressio , spektriklusterit , lineaariset adaptiiviset suodattimet ja monet muut . Mikä tahansa lineaarinen malli voidaan muuntaa epälineaariseksi malliksi soveltamalla malliin ytimen temppua ja korvaamalla sen ominaisuudet (ennustajat) ydinfunktiolla.

Useimmat ytimen algoritmit perustuvat kuperaan optimointiin tai ominaisvektorien etsimiseen ja ovat tilastollisesti hyvin perusteltuja. Yleensä niiden tilastollisia ominaisuuksia analysoidaan tilastollisen oppimisteorian avulla (esim. Rademacherin kompleksisuutta ).

Syyt ja epävirallinen selitys

Ytimen menetelmiä voidaan pitää esimerkin kautta oppimisena – sen sijaan, että oppisivat jonkin kiinteän syöttöominaisuuksia vastaavien parametrien joukon, ne "muistavat" harjoitusesimerkin ja harjoittelevat sen painojen mukaan . Ennuste merkitsemättömälle syötteelle, ts. ei sisälly harjoitussarjaan, opitaan käyttämällä samankaltaisuusfunktiota (kutsutaan ytimeksi ) merkitsemättömän syötteen ja kunkin opetussyötteen välillä . Esimerkiksi ytimen binääriluokittaja yleensä laskee painotetun samankaltaisuussumman käyttämällä kaavaa $i$ $(\mathbf {x} _{i},y_{i})$ $w_{i}$ $k$ ${\mathbf {x'))$ ${\displaystyle \mathbf {x} _{i))$

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

missä

${\hat {y}}\in \{-1,+1\}$ on ytimen binaariluokittaja ennustetulle nimikkeelle merkitsemättömälle syötteelle , jonka piilotettu oikea nimike tarvitaan; ${\mathbf {x'))$ $y$
$k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R}$ on ydinfunktio, joka mittaa syötteiden samankaltaisuutta ; $\mathbf {x} ,\mathbf {x'} \in {\mathcal {X))$
summa kulkee kaikkien n merkittyjen esimerkkien yli luokittelijan harjoitusjoukossa, jossa on ; ${\displaystyle \{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n))$ ${\displaystyle y_{i}\in \{-1,+1\))$
$w_{i}\in \mathbb {R}$ ovat harjoitusesimerkkien painot oppimisalgoritmin määrittämänä;
Sgn-funktio määrittää, onko ennustettu luokitus positiivinen vai negatiivinen.

Ydinluokittelijat kuvattiin 1960-luvun alussa ydinperceptronin keksimisen myötä [2] . Ne saivat laajan hyväksynnän tukivektorikoneiden suosion myötä 1990-luvulla, kun SVM:n havaittiin olevan kilpailukykyinen hermoverkkojen kanssa tehtävissä, kuten käsinkirjoituksen tunnistuksessa .

Mathematics: The Nuclear Trick

Ytimen temppu välttää eksplisiittisen mappauksen, jota tarvitaan lineaarisen oppimisalgoritmin saamiseksi epälineaariselle funktiolle tai päätösrajalle . Kaikille ja syöttöavaruudessa jotkin funktiot voidaan esittää pistetulona toisessa tilassa . Toimintoa kutsutaan usein ytimeksi tai ydinfunktioksi . Sanaa "ydin" käytetään matematiikassa viittaamaan painofunktioon tai integraaliin . $\mathbf {x}$ ${\mathbf {x'))$ ${\mathcal {X}}$ $k(\mathbf {x} ,\mathbf {x'} )$ ${\mathcal {V))$ $k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R}$

Joillakin koneoppimisongelmilla on enemmän rakennetta pelkän painofunktion sijaan . Laskelmat ovat paljon helpompia, jos ydin voidaan kirjoittaa "ominaisuuskartoituksena" , joka täyttää tasa-arvon $k$ $\varphi \colon {\mathcal {X}}\to {\mathcal {V}}$

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

Tärkein rajoitus tässä on se, minkä tulee olla sopiva pistetuote. Toisaalta nimenomaista esitystapaa ei tarvita, koska se on pistetuloavaruus . Vaihtoehto seuraa Mercerin lauseesta — implisiittisesti määritelty funktio on olemassa, jos avaruus voidaan varustaa sopivalla suurella, joka varmistaa , että funktio täyttää Mercerin ehdon . $\langle \cdot ,\cdot \rangle _{\mathcal {V}}$ $\varphi$ ${\mathcal {V))$ $\varphi$ ${\mathcal {X}}$ $k$

Mercerin lause on kuin yleistys lineaarialgebran tuloksesta, joka yhdistää pistetulon mihin tahansa positiiviseen määrättyyn matriisiin . Itse asiassa Mercerin tila voidaan supistaa tähän yksinkertaiseen tapaukseen. Jos valitsemme mittaamme kaikille laskevan suuren, joka laskee joukon sisällä olevien pisteiden määrän , niin Mercerin lauseen integraali pelkistyy summaksi $\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.

Jos tämä epäyhtälö pätee kaikkiin äärellisiin pistejonoihin ja kaikkiin reaaliarvoisten kertoimien sarjoihin (vrt. Positiivinen määrätty ydin ), funktio täyttää Mercerin ehdon. $(\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})$ ${\mathcal {X}}$ $n$ $(c_{1},\dots ,c_{n})$ $k$

Joillakin algoritmeilla, jotka ovat riippuvaisia mielivaltaisista linkeistä alkuperäisessä avaruudessa , on itse asiassa lineaarinen esitys muissa olosuhteissa - vaihtelevassa avaruudessa . Lineaarinen tulkinta antaa meille käsityksen algoritmista. Lisäksi usein ei ole tarpeen laskea suoraan laskentahetkellä, kuten tukivektorikoneen tapauksessa . Jotkut pitävät tästä johtuvaa ajan lyhenemistä algoritmin pääeduna. Tutkijat käyttävät sitä tarkentamaan olemassa olevien algoritmien merkitystä ja ominaisuuksia. ${\mathcal {X}}$ $\varphi$ $\varphi$

Teoreettisesti Gram-matriisin suhteessa (jota joskus kutsutaan "ytimen matriiksi" [3] ), jossa , pitäisi olla positiivinen puolidefiniitti [4] . Empiirisesti koneoppimisheuristiikassa sellaisen funktion valinta , joka ei täytä Mercerin ehtoa, voi silti olla perusteltua, jos se ainakin vastaa intuitiivista ajatusta samankaltaisuudesta [5] . Olipa ydin Mercer vai ei, sitä voidaan edelleen kutsua "ytimeksi". $\mathbf {K} \in \mathbb {R} ^{n\times n}$ ${\displaystyle \{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\))$ $K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})$ $k$ $k$ $k$ $k$

Jos ydinfunktio on myös kovarianssifunktio , jota käytetään Gaussin prosessissa , niin Gram-matriisia voidaan kutsua kovarianssimatriisiksi [6] . $k$ ${\mathbf {K}}$

Sovellukset

Ydinmenetelmien sovellukset ovat erilaisia ja sisältävät geostatistiikkaa [7] , krigingiä , etäisyyspainotusta , 3D-rekonstruktiota , bioinformatiikkaa , kemoinformatiikkaa , tiedon poiminta ja käsinkirjoituksen tunnistusta .

Suositut ytimet

Fisher-ydin
Graafiydin
Nuclear Smoother
Polynomiydin
Radiaalinen kantafunktion ydin
Merkkijonoytimet

Muistiinpanot

↑ 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 . (määrätön)
↑ Rasmussen, Williams, 2006 .
↑ Honarkhah, Caers, 2010 , s. 487–517.

Kirjallisuus

Aizerman MA, Emmanuel M. Braverman, Rozoner LI Mahdollisen funktion menetelmän teoreettiset perusteet hahmontunnistusoppimisessa // Automation and Remote Control. - 1964. - T. 25 . — S. 821–837 . Artikkelissa lainattu
- Isabelle Guyon, B. Boser, Vladimir Vapnik. Erittäin suurten VC-ulotteisten luokittimien automaattinen kapasiteetin viritys // Neuraalitietojen käsittelyjärjestelmien kehitys. – 1993.
Sergios. hahmontunnistus. - Elsevier BV, 2008. - ISBN 9780080949123 .
Mehryar Mohri, Afshin Rostamizadeh ja Ameet Talwalkar. . - Cambridge, Lontoo: MIT Press, 2012. - (Adaptive Computation and Machine Learning). - ISBN 978-0-262-01825-8 .
Thomas Hofmann, Bernhard Scholkopf, Alexander J. Smola. Ydinmenetelmät koneoppimisessa // The Annals of Statistics. - 2007. - tammikuu ( osa 36 , numero 3 ).
Rasmussen CE, Williams CKI Gaussian Processes for Machine Learning. - Cambridge, Lontoo: MIT Press, 2006. - (Adaptive Computation and Machine Learning). — ISBN 0-262-18253-X .
Honarkhah M., Caers J. Kuvioiden stokastinen simulointi etäisyyspohjaista kuviomallinnusta käyttäen // Mathematical Geosciences . - 2010. - T. 42 . - doi : 10.1007/s11004-010-9276-7 .

Kirjallisuus

John Shawe-Taylor, Nello Cristianini. Ytimen menetelmät kuvioanalyysiin. - Cambridge University Press, 2004.
Liu W., Principe J., Haykin S. Kernel Adaptive Filtering: A Comprehensive Introduction. Wiley, 2010.

Linkki

Kernel-Machines Org -yhteisön verkkosivusto
www.support-vector-machines.org (kirjallisuus, arvostelut, ohjelmistot, tukivektorikoneisiin liittyvät linkit – akateeminen sivusto)
onlineprediction.net Kernel Methods -artikkeli

Koneoppiminen ja tiedon louhinta
Tehtävät	Luokitteluongelma Oppiminen ilman opettajaa Opettajan avustama oppiminen Taantumisanalyysi AutoML Yhdistyksen säännöt Ominaisuuksien erottaminen Ominaisuuksien koulutus Ranking koulutus Kieliopillinen johtaminen Verkko-oppiminen
Opettajan kanssa oppimista	k-lähimmän naapurin menetelmä Naiivi Bayesin luokitin päätöspuu Tuki vektorikonetta Lineaarinen regressio Logistinen regressio perceptron Mallien kokoonpanot Pussittaminen tehostaa satunnainen metsä Asiaankuuluva vektorimenetelmä
ryhmäanalyysi	k-keinomenetelmä Sumea klusterointimenetelmä Hierarkkinen klusterointi EM-algoritmi KOIVU PARANTAA DBSCAN OPTIIKKA Keskimääräinen siirto
Mittasuhteiden vähentäminen	Tekijäanalyysi Pääkomponenttimenetelmä CCA ICA LDA Ei-negatiivinen matriisin laajennus t-SNE
Rakenteellinen ennustaminen	Graafinen todennäköisyysmalli Bayesin verkko Piilotettu Markovin malli CRF
Anomalian havaitseminen	k-lähimmän naapurin menetelmä Paikallinen päästötaso
Piirrä todennäköisyysmallit	Bayesin verkko Markovin verkko Piilotettu Markovin malli
Neuroverkot	Rajoitettu Boltzmann-kone itseorganisoituva kartta Aktivointitoiminto Sigmoidi softmax Radiaalinen kantafunktio Takaisin lisäysmenetelmä Syväoppiminen Monikerroksinen perceptroni Toistuva neuroverkko pitkä lyhytaikainen muisti Hallittu toistuva esto Konvoluutiohermoverkko U-Net Autoenkooderi
Vahvistusoppiminen	Markovin prosessi Bellmanin yhtälö Ahne algoritmi Q-oppiminen SARSA Aikaero (TD)
Teoria	Vapnik-Chervonenkis teoria Bias-dispersion dilemma Laskennallinen oppimisteoria Empiirinen riskin minimointi Occam oppii PAC-oppiminen Tilastollinen oppimisteoria
Lehdet ja konferenssit	NeurIPS ICML ML JMLR ArXiv:cs.LG