Occam tanul

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. július 2-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Az Ockham-tanulás a számítógépes tanuláselméletben egy algoritmikus tanulási modell , ahol a tanulás célja a rendelkezésre álló képzési adatok tömör ábrázolása. A módszer szorosan összefügg a szinte helyes tanulással (PC tanulás, eng. Probably Approximately Correct learning , PAC learning), ahol a tanár értékeli a tesztkészlet előrejelző képességét.

Az Occam tanulhatósága magában foglalja a számítógépes tanulást, és a fogalmak széles skálájára ennek az ellenkezője is igaz – a számítógépes tanulás az Occam tanulását is magában foglalja.

Bevezetés

Az Occam tanulása az " Occam borotva " kifejezésről kapta a nevét, amely az az elv, amely kimondja, hogy további entitások hiányában a megfigyelések rövid magyarázatát előnyben kell részesíteni egy hosszabb magyarázattal szemben (röviden: "Nem szabad a lényeket feleslegesen szaporítani"). Occam tanuláselmélete ennek az elvnek a formális és matematikai finomítása. Blumer és munkatársai voltak az elsők, akik megmutatták [1] , hogy az Occam-tanulás magában foglalja a számítógépes tanulást is, amely a számítógépes tanuláselmélet standard tanulási modellje. Más szóval, a takarékosság (kimeneti hipotézis) előrejelző képességgel jár .

Occam definíciója a tanulásról

A fogalom tömörsége egy fogalomosztályban kifejezhető az osztály fogalmát reprezentáló legrövidebb bitsorozat hosszával . Az Ockham-tanulás összekapcsolja a tanulási algoritmus kimenetének tömörségét annak előrejelző képességével. $c$ ${\mathcal {C}}$ $size(c)$ $c$ ${\mathcal {C}}$

Legyen és legyen célfogalmakat és hipotéziseket tartalmazó fogalomosztályok. Ekkor a és konstansok esetén a tanuló algoritmus egy -Occam algoritmus hipotézisek szerint akkor és csak akkor, ha adott egy halmaz , amely szerint címkézett példányokat tartalmaz , az algoritmus kimenete egy hipotézis , így ${\mathcal {C}}$ ${\mathcal {H}}$ $\alpha \geqslant 0$ $0\leqslant \beta <1$ $L$ $(\alpha ,\beta )$ ${\mathcal {C}}$ ${\mathcal {H}}$ ${\displaystyle S=\{x\))$ $m$ $c(x)\in {\mathcal {C))$ $L$ $h\in {\mathcal {H}}$

$h$ egyetért azzal ( azaz ) $c$ $S$ $h(x)=c(x),\forall x\in S$
${\displaystyle size(h)\leqslant (n\cdot size(c))^{\alpha }m^{\beta ))$ [2] [1]

ahol a maximális hossza a . Az Occam-algoritmust hatékonynak nevezzük, ha az és polinomiális idejében fut . Azt mondjuk, hogy a fogalmak egy osztálya Occam-tanulható a hipotézisek osztályához képest, ha létezik hatékony Occam algoritmus a hipotézisekre. $n$ $x\in S$ $n$ $m$ $size(c)$ ${\mathcal {C}}$ ${\mathcal {H}}$ ${\mathcal {C}}$ ${\mathcal {H}).$

Az Occam tanulás és a számítógépes tanulás kapcsolata

Az Ockham-tanulhatóság magában foglalja a számítógépes tanulhatóságot is, amint azt Blumer és munkatársai [2] tétele mutatja :

Tétel ( Occam tanulása PC-s tanulással jár )

Legyen egy hatékony -Occam algoritmus a hipotézisek alapján . Ekkor van egy olyan állandó , hogy bármely eloszlás esetén, adott esetben az egyes bitek fogalma alapján levont és aszerint címkézett példányok esetén az algoritmus olyan hipotézist állít elő , hogy a valószínűsége legalább $L$ $(\alpha ,\beta )$ ${\mathcal {C}}$ ${\mathcal {H}}$ $a>0$ $0<\epsilon ,\delta <1$ ${\mathcal {D}}$ $m\geqslant a\left({\frac {1}{\epsilon }}\log {\frac {1}{\delta }}+\left({\frac {(n\cdot size(c)) )^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)$ $\mathcal{D}$ $c\in {\mathcal {C))$ $n$ $L$ $h\in {\mathcal {H}}$ $error(h)\leqslant \epsilon$ $1-\delta$

. Itt figyelembe veszi a koncepciót és az elosztást . Ebből következik, hogy az algoritmus a hipotézisek osztálya alatti fogalmak osztályának számítógépes tanára . Egy kicsit általánosabb megfogalmazás: $error(h)$ $c$ ${\mathcal {D}}$ $L$ ${\mathcal {C}}$ ${\mathcal {H}}$

Tétel ( Occam tanulása PC-s tanulást jelent, hosszú verzió )

Hadd . Legyen egy olyan algoritmus, amely egy rögzített, de ismeretlen eloszlásból húzott és a koncepció szerint bithosszúságú karakterlánccal felcímkézett példányok halmaza esetén a kimenet egy hipotézis, amely összhangban van a címkézett példányokkal. Ekkor létezik egy olyan konstans , amely esetén garantáltan olyan hipotézist adunk fel , amely valószínűséggel legalább . $0<\epsilon ,\delta <1$ $L$ $m$ $\mathcal{D}$ $c\in {\mathcal {C))$ $n$ $h\in {\mathcal {H}}_{n,m}$ $b$ $\log |{\mathcal {H}}_{n,m}|\leqslant b\epsilon m-\log {\frac {1}{\delta }}$ $L$ $h\in {\mathcal {H}}_{n,m}$ $error(h)\leqslant \epsilon$ $1-\delta$

Bár a fenti tételek azt mutatják, hogy az Occam tanulása elegendő a PC-s tanuláshoz, nem mondanak semmit a szükségességéről . Board és Pitt kimutatták, hogy a fogalmak széles osztályához az Occam tanulás szükséges a PC-s tanuláshoz [3] . Megmutatták, hogy a kivétellisták alatt polinomiálisan zárt fogalmak bármely osztálya esetén a PC tanulhatósága magában foglalja az Occam-algoritmus meglétét az adott fogalomosztályhoz. A kivétellisták által polinomiálisan lezárt fogalomosztályok közé tartoznak a logikai formulák, összegzési láncok, determinisztikus véges automaták , döntési listák, döntési fák és más geometriai alapú fogalomosztályok.

A fogalmak egy osztálya polinomiálisan zárt a kivétellistákban, ha létezik polinomiális futásidejű algoritmus , így a fogalom reprezentációja és a kivételek véges listája alapján az algoritmus kimenete a fogalom reprezentációja , így a fogalmakat és egyetértenek, kivéve a halmaz elemeinek kizárását . ${\mathcal {C}}$ $A$ $c\in {\mathcal {C))$ $E$ $c'\in {\mathcal {C}}$ $c$ $c'$ $E$

Bizonyíték arra, hogy az Occam tanulása számítógépes tanulást is magában foglal

Először a változatot fogjuk bizonyítani hosszúsággal. Rossznak nevezzük a hipotézist , ha itt is figyelembe veszi a valódi fogalmát és eloszlását . Annak a valószínűsége, hogy a halmaz konzisztens a mintákkal, nem haladja meg a -t , a minták függetlensége szerint. Egy teljes halmaz esetén annak a valószínűsége, hogy rossz hipotézis van a helyen , nem haladja meg a -t, ami kisebb, mint ha . Ezzel befejeződik a második tétel bizonyítása. $h\in {\mathcal {H}}$ $error(h)\geqslant \epsilon$ $error(h)$ $c$ $\mathcal{D}$ $S$ $h$ ${\displaystyle (1-\epszilon )^{m))$ ${\mathcal {H}}_{n,m}$ $|{\mathcal {H}}_{n,m}|(1-\epszilon )^{m}$ $\delta$ $\log |{\mathcal {H}}_{n,m}|\leqslant O(\epsilon m)-\log {\frac {1}{\delta }}$

A második tétel segítségével bebizonyítjuk az elsőt. Mivel van egy -Occam algoritmusunk, ez azt jelenti, hogy az algoritmus bármely kimeneti hipotézise legfeljebb bittel reprezentálható, majd . Ez kevesebb, mintha valamilyen állandót állítanánk be . Ekkor a tétel hosszúságú változata szerint konzisztens hipotézist ad legalább . Ezzel befejeződik az első tétel bizonyítása. $(\alpha ,\beta )$ $L$ $(n\cdot size(c))^{\alpha }m^{\beta }$ $\log |{\mathcal {H}}_{n,m}|\leqslant (n\cdot size(c))^{\alpha }m^{\beta }$ $O(\epsilon m)-\log {\frac {1}{\delta }}$ $m\geqslant a\left({\frac {1}{\epsilon }}\log {\frac {1}{\delta }}+\left({\frac {(n\cdot size(c)) )^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)$ $a>0$ $L$ $h$ $1-\delta$

A minta összetettségének javítása általános problémák esetén

Bár az Occam-tanulás és a PC-tanulás egyenértékűek, az Occam algoritmusa felhasználható arra, hogy szigorúbb határokat kapjunk a klasszikus problémák minta-összetettségére vonatkozóan, beleértve a logikai érvelést [2] , a többváltozós gondolkodást [4] és a döntési listákat [5] .

Kiterjesztések

Kimutatták, hogy az Ockham-algoritmusok sikeresen működnek a PT-tanulásban hibák [6] [7] , valószínűségi fogalmak [8] , tanulási függvények [9] és nem független Markov-példák [10] jelenlétében .

Lásd még

A strukturális kockázat minimalizálása
Számítógépes tanuláselmélet

Jegyzetek

↑ 1 2 Blumer, Ehrenfeucht, Haussler, Warmuth, 1987 , p. 377-380.
↑ 1 2 3 Kearns, Vazirani, 1994 .
↑ Board, Pitt, 1990 , p. 54-63.
↑ Haussler, 1988 , p. 177-221.
↑ Rivest, 1987 , p. 229-246.
↑ Angluin, Laird, 1988 , p. 343-370.
↑ Kearns, Li, 1993 , p. 807-837.
↑ Kearns, Schapire, 1990 , p. 382-391.
↑ Natarajan, 1993 , p. 370-376.
↑ Aldous és Vazirani 1990 , p. 392-396.

Irodalom

Kearns MJ, Vazirani UV, 2. fejezet // Bevezetés a számítógépes tanuláselméletbe. - MIT sajtó, 1994. - ISBN 9780262111935 .
Blumer A., Ehrenfeucht A., Haussler D., Warmuth M. K. Occam borotvája . - 1987. - T. 24 , sz. 6 . - doi : 10.1016/0020-0190(87)90114-1 .
Board R., Pitt L. Az Occam-algoritmusok szükségességéről // Proceedings of the huszonkettedik éves ACM symposium on Theory of computing. – ACM, 1990.
Haussler D. Az induktív torzítás számszerűsítése: AI tanulási algoritmusok és Valiant tanulási keretrendszere // Mesterséges intelligencia. - 1988. - T. 36 , sz. 2 . Archiválva az eredetiből 2013. április 12-én.
Rivest RL Tanulási döntési listák // Gépi tanulás. - 1987. - 2. kötet , szám. 3 .
Angluin D., Laird P. Tanulás zajos példákból // Machine Learning. - 1988. - 2. kötet , szám. 4 .
Kearns M., Li M. Tanulás rosszindulatú hibák jelenlétében // SIAM Journal on Computing,. - 1993. - T. 22 , sz. 4 .

Kearns MJ, Schapire RE Valószínűségi fogalmak hatékony elosztás nélküli tanulása // Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium . - Los Alamitos, CA: IEEE Computer Society Press, 1990.

- Kearns MJ, Schapire RE Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium // SZÁMÍTÓGÉP- ÉS RENDSZERTUDOMÁNYI FOLYÓIRAT. - 1994. - Kiadás. 48 . - S. 464-497 .
Natarajan BK Occam borotva funkcióihoz // Proceedings of the sixth Years Conference on Computational learning theory. – ACM, 1993.

Aldous D., Vazirani U. Valiant tanulási modelljének markovi kiterjesztése // Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium. – IEEE, 1990.

Gépi tanulás és adatbányászat
Feladatok	Osztályozási probléma Tanulás tanár nélkül Tanár által segített tanulás Regresszió analízis AutoML Egyesületi szabályzat Funkció kivonás Tulajdonságok képzése Rangsorképzés Nyelvtani levezetés Online tanulás
Tanulás tanárral	k-legközelebbi szomszéd módszer Naiv Bayes osztályozó döntési fa Támogatja a vektoros gépet Lineáris regresszió Logisztikus regresszió perceptron Modellek együttesei Zsákolás fellendítése véletlenszerű erdő Releváns vektoros módszer
klaszteranalízis	k-közép módszer Fuzzy klaszterezési módszer Hierarchikus klaszterezés EM algoritmus NYÍR GYÓGYMÓD DBSCAN OPTIKA Átlageltolás
Dimenziócsökkentés	Faktoranalízis Főkomponens módszer CCA ICA LDA Nem negatív mátrix kiterjesztése t-SNE
Strukturális előrejelzés	Grafikon valószínűségi modell Bayesi hálózat Rejtett Markov-modell CRF
Anomália észlelése	k-legközelebbi szomszéd módszer Helyi kibocsátási szint
Grafikon valószínűségi modellek	Bayesi hálózat Markov hálózat Rejtett Markov-modell
Neurális hálózatok	Limitált Boltzmann gép önszerveződő térkép Aktiválási funkció Szigma alakú softmax Radiális bázisfüggvény Hátsó szaporítási módszer Mély tanulás Többrétegű perceptron Ismétlődő neurális hálózat hosszú távú rövid távú memória Ellenőrzött visszatérő blokk Konvolúciós Neurális Hálózat U-Net Autoencoder
Megerősítő tanulás	Markov folyamat Bellman egyenlet Mohó algoritmus Q-learning SARSA Időbeli különbség (TD)
Elmélet	Vapnik-Chervonenkis elmélet Elfogultság-diszperziós dilemma Számítógépes tanuláselmélet Empirikus kockázatminimalizálás Occam tanul PAC tanulás Statisztikai tanuláselmélet
Folyóiratok és konferenciák	NeurIPS ICML ML JMLR ArXiv:cs.LG