Occam învață

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 2 iulie 2020; verificarea necesită 1 editare .

Învățarea Ockham în teoria învățării computaționale este un model de învățare algoritmică în care scopul învățării este de a obține o reprezentare concisă a datelor de antrenament disponibile. Metoda este strâns legată de învățarea aproape corectă (învățarea PC, ing. Învățarea probabil aproximativ corectă , învățarea PAC), unde profesorul evaluează capacitatea de predicție a setului de test.

Capacitatea de învățare a lui Occam implică învățarea pe computer, iar pentru o clasă largă de concepte, opusul este și adevărat – învățarea pe computer implică învățarea lui Occam.

Introducere

Învățarea lui Occam este denumită după termenul „ briciul lui Occam ”, care este principiul care afirmă că, presupunând că nu există entități suplimentare, o scurtă explicație a observațiilor ar trebui să fie preferată față de o explicație mai lungă (pe scurt: „Nu trebuie să înmulțim ființele inutil”). Teoria învăţării lui Occam este o perfecţionare formală şi matematică a acestui principiu. Blumer și colab. au fost primii care au arătat [1] că învățarea Occam implică învățarea pe computer, care este modelul standard de învățare în teoria învățării computaționale. Cu alte cuvinte, frugalitatea (ipoteza de ieșire) implică capacitatea de predicție .

Definiția lui Occam a învățării

Concizia unui concept dintr-o clasă de concept poate fi exprimată ca lungimea celui mai scurt șir de biți care poate reprezenta conceptul în clasă . Învățarea Ockham conectează concizia rezultatelor unui algoritm de învățare cu capacitatea sa de predicție. $c$ ${\mathcal {C}}$ $size(c)$ $c$ ${\mathcal {C}}$

Fie și fie clase de concepte care conțin concepte țintă și, respectiv, ipoteze. Atunci, pentru constante și , algoritmul de învățare este un algoritm -Occam pentru ipoteze dacă și numai dacă, având în vedere un set care conține instanțe etichetate conform , rezultatul algoritmului este o ipoteză , astfel încât ${\mathcal {C}}$ ${\mathcal {H}}$ $\alpha \geqslant 0$ $0\leqslant \beta <1$ $L$ $(\alpha,\beta)$ ${\mathcal {C}}$ ${\mathcal {H}}$ $S=\{x\)$ $m$ $c(x)\in {\mathcal {C))$ $L$ $h\in {\mathcal {H}}$

$h$ este de acord cu ( adică ) $c$ $S$ $h(x)=c(x),\forall x\in S$
$size(h)\leqslant (n\cdot size(c))^{\alpha}m^{\beta )$ [2] [1]

unde este lungimea maximă a oricărei instanțe de . Algoritmul lui Occam este numit eficient dacă rulează în timp polinomial de și . Spunem că o clasă de concepte este Occam-învățabilă în raport cu o clasă de ipoteze dacă există un algoritm Occam eficient pentru ipoteze . $n$ $x\în S$ $n$ $m$ $size(c)$ ${\mathcal {C}}$ ${\mathcal {H}}$ ${\mathcal {C}}$ ${\mathcal {H}).$

Relația dintre învățarea Occam și învățarea PC

Capacitatea de învățare Ockham implică capacitatea de învățare pe computer, așa cum arată teorema lui Blumer și colab .[2] :

Teorema ( învățarea lui Occam presupune învățarea PC )

Fie un algoritm eficient -Occam pentru ipoteze . Apoi există o constantă astfel încât pentru orice pentru orice distribuție , date date extrase din și etichetate conform conceptului fiecărui biți, algoritmul va produce o ipoteză astfel încât, cu probabilitate cel puțin $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$

. Aici ia în considerare conceptul și distribuția . Rezultă că algoritmul este un profesor PC al clasei de concepte din clasa ipotezelor . O formulare puțin mai generală: ${\ displaystyle error(h)}$ $c$ ${\mathcal {D}}$ $L$ ${\mathcal {C}}$ ${\mathcal {H}}$

Teorema ( învățarea lui Occam implică învățarea PC, versiunea de lungime )

Lasă . Fie un algoritm astfel încât, având în vedere un set de instanțe extrase dintr-o distribuție fixă, dar necunoscută și etichetate conform conceptului cu un șir de biți de lungime fiecare, rezultatul este o ipoteză compatibilă cu instanțele etichetate. Atunci există o constantă astfel încât, în cazul în care este garantat să se dea o ipoteză astfel încât cu probabilitate cel puțin . $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$

Deși teoremele de mai sus arată că învățarea lui Occam este suficientă pentru învățarea pe computer, ele nu spun nimic despre necesitatea . Board și Pitt au arătat că pentru o clasă largă de concepte, învățarea Occam este necesară pentru învățarea PC [3] . Ei au arătat că pentru orice clasă de concepte care este închisă polinomial sub listele de excepții , capacitatea de învățare PC implică existența unui algoritm Occam pentru acea clasă de concepte. Clasele de concepte care sunt închise polinomial de liste de excepții includ formule booleene, lanțuri de însumare, automate finite deterministe , liste de decizie, arbori de decizie și alte clase de concepte bazate pe geometric.

O clasă de concepte este închisă polinomial în listele de excepții dacă există un algoritm polinomial de rulare , astfel încât, având în vedere o reprezentare a conceptului și o listă finită de excepții , rezultatul algoritmului este o reprezentare a conceptului , astfel încât conceptele şi convin cu excepţia excluderii elementelor mulţimii . ${\mathcal {C}}$ $A$ $c\in {\mathcal {C)}$ $E$ $c'\in {\mathcal {C}}$ $c$ $c'$ $E$

Dovada că învățarea lui Occam presupune învățarea pe computer

Mai întâi vom demonstra versiunea cu lungime. Numim ipoteza rea dacă , unde din nou ia în considerare conceptul adevărat și distribuția . Probabilitatea ca mulțimea să fie în concordanță cu nu depășește , în funcție de independența eșantioanelor. Pentru o mulțime completă, probabilitatea ca să existe o ipoteză proastă la nu depășește , care este mai mică decât dacă . Aceasta completează demonstrația celei de-a doua teoreme. $h\in {\mathcal {H}}$ $error(h)\geqslant \epsilon$ ${\ displaystyle error(h)}$ $c$ $\mathcal{D}$ $S$ $h$ $(1-\epsilon )^{m)$ ${\mathcal {H}}_{n,m}$ $|{\mathcal {H}}_{n,m}|(1-\epsilon )^{m}$ $\delta$ $\log |{\mathcal {H}}_{n,m}|\leqslant O(\epsilon m)-\log {\frac {1}{\delta }}$

Folosind a doua teoremă, o vom demonstra pe prima. Deoarece avem un algoritm -Occam, aceasta înseamnă că orice ipoteză de ieșire a algoritmului poate fi reprezentată de cel mult biți și apoi . Aceasta este mai mică decât dacă am seta o constantă . Apoi, conform versiunii teoremei cu lungime, va da o ipoteză consistentă cu o probabilitate de cel puțin . Aceasta completează demonstrația primei teoreme. $(\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$

Îmbunătățirea complexității eșantionului pentru probleme generale

Deși învățarea Occam și învățarea PC sunt echivalente, algoritmul lui Occam poate fi utilizat pentru a obține limite mai strânse ale complexității eșantionului pentru problemele clasice, inclusiv raționamentul logic [2] , raționamentul multivariabil [4] și listele de decizie [5] .

Extensii

S-a demonstrat că algoritmii Ockham funcționează cu succes pentru învățarea PT în prezența erorilor [6] [7] , a învățării conceptelor probabilistice [8] , a funcțiilor de învățare [9] și a exemplelor Markov de non-independență [10] .

Vezi și

Minimizarea riscului structural
Teoria învățării computaționale

Note

↑ 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 și Vazirani 1990 , p. 392-396.

Literatură

Kearns MJ, Vazirani UV capitolul 2 // O introducere în teoria învățării computaționale. - MIT press, 1994. - ISBN 9780262111935 .
Blumer A., Ehrenfeucht A., Haussler D., Briciul lui Warmuth M.K. Occam . - 1987. - T. 24 , nr. 6 . - doi : 10.1016/0020-0190(87)90114-1 .
Board R., Pitt L. Despre necesitatea algoritmilor Occam // Proceedings of the twoty-second annual ACM symposium on Theory of computing. — ACM, 1990.
Haussler D. Cuantificarea părtinirii inductive: algoritmi de învățare AI și cadrul de învățare al lui Valiant // Inteligența artificială. - 1988. - T. 36 , nr. 2 . Arhivat din original pe 12 aprilie 2013.
Liste de decizii Rivest RL Learning // Învățare automată. - 1987. - Vol. 2 , numărul. 3 .
Angluin D., Laird P. Learning from noisy examples // Machine Learning. - 1988. - Vol. 2 , numărul. 4 .
Kearns M., Li M. Learning in the present of malicious errors // SIAM Journal on Computing,. - 1993. - T. 22 , nr. 4 .

Kearns MJ, Schapire RE Învățare eficientă fără distribuție a conceptelor probabilistice // 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., 31th Annual Symposium // JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - 1994. - Emisiune. 48 . - S. 464-497 .
Razorul lui Natarajan BK Occam pentru funcții // Proceedings of the sixth annual Conference on Computational Learning Theory. — ACM, 1993.

Aldous D., Vazirani U. O extensie markoviană a modelului de învățare al lui Valiant // Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium. - IEEE, 1990.

Î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