Probabil antrenament aproximativ corect

Învățarea probabil aproximativ corectă ( învățarea PAC ) este o schemă de învățare automată care utilizează conceptele de fiabilitate asimptotică și complexitate computațională . Propus în 1984 de Leslie Valiant [1] .

În această schemă, profesorul primește mostre și trebuie să aleagă o funcție de generalizare (numită ipoteză ) dintr-o anumită clasă de funcții posibile. Scopul este o funcție care este foarte probabil (de unde „probabil” din nume) să aibă o eroare de generalizare scăzută (de unde „aproximativ corect” din nume). Profesorul ar trebui să fie capabil să predea un concept [2] oferind un factor de aproximare arbitrar, probabilitatea de succes sau distribuția eșantionului .

Ulterior, modelul a fost extins pentru a gestiona zgomotul (probele clasificate incorect).

O inovație importantă a schemei MIC este utilizarea conceptului de complexitate computațională a învățării automate. În special, se așteaptă ca profesorul să găsească funcții eficiente (care sunt limitate în timpul de rulare și spațiul necesar de un polinom al mărimii eșantionului), iar profesorul trebuie să implementeze o procedură eficientă (cerând un exemplu de dimensiune limitată de un polinom al dimensiunea conceptului, modificată prin aproximare și limite de probabilitate ).

Definiții și terminologie

Pentru o definiție formală, se folosește un anumit set dat , numit spațiu caracteristic sau codificarea tuturor mostrelor. De exemplu, în problema recunoașterii optice a caracterelor, spațiul caracteristic este , iar în problema găsirii unui interval (clasificarea corectă a punctelor din interiorul intervalului ca pozitive și din afara intervalului ca negative), spațiul caracteristicilor este mulțimea tuturor mărginite. intervale în . $X$ $X=\{0,1\}^{n}$ $\mathbb {R}$

Un alt concept folosit în schemă este conceptul - un subset . De exemplu, setul tuturor secvențelor de biți din care codifică modelul literei „P” este unul dintre conceptele din problema OCR. Un exemplu de concept pentru problema găsirii unui interval este setul de intervale deschise , fiecare dintre acestea conținând doar puncte pozitive. Clasa de concepte este un set de concepte peste . Acesta poate fi setul tuturor submulților din cadrul 4-connected matrice de biți (lățimea fontului este 1). $c\subset X$ $X=\{0,1\}^{n}$ $\{(a,b)\mid 0\leqslant a\leqslant \pi /2,\pi \leqslant b\leqslant {\sqrt {13}}\}$ $C$ $X$

Fie o procedură care generează un exemplu folosind o distribuție de probabilitate și dă eticheta corectă , care este 1 dacă și 0 în caz contrar. Acum, dat fiind , să presupunem că există un algoritm și un polinom din (și alți parametri relevanți de clasă ) astfel încât, dat un eșantion de dimensiune , extras conform , atunci cu probabilitate cel puțin rezultatul algoritmului este ipoteza , care are media eroare, mai mică sau egală cu pentru aceeași distribuție . În plus, dacă afirmația de mai sus pentru algoritm este adevărată pentru orice concept și pentru orice distribuție peste și pentru toate , atunci este (efectiv) VPK-learnable (sau VPK-learnable fără distribuție ). În acest caz, se consideră că este algoritmul de învățare VPK pentru . $EX(c,D)$ $X$ $D$ $c(x)$ $x\in c$ $0<\epsilon ,\delta <1$ $A$ $p$ $1/\epsilon ,1/\delta$ $C$ $p$ $EX(c,D)$ $1-\delta$ $A$ $h\în C$ $\epsilon$ $X$ $D$ $A$ $c\în C$ $D$ $X$ $0<\epsilon ,\delta <1$ $C$ $A$ $C$

Echivalență

În anumite condiții de regularitate, aceste trei condiții sunt echivalente:

Clasa de concept poate fi învățată prin VPK. $C$
Dimensiunea Vapnik-Chervonenkis a clasei este finită. $C$
$C$ este o clasă omogenă Glivenko-Cantelli .

Vezi și

Toleranță la erori (formare VPK)
Complexitatea eșantionului

Note

↑ Valiant1984 .
↑ Conceptele sunt subseturi adecvate ale setului de caracteristici admisibile.

Literatură

Valiant L. O teorie a învățatului // Comunicațiile ACM. - 1984. - Emisiune. 27 .
Kearns M., Vazirani U. O introducere în teoria învățării computaționale. - MIT Press, 1994. - ISBN 9780262111935 .
Balas Kausik Natarajan. învățare automată. O abordare teoretică. - Morgan Kaufmann Publishers, 1991. - ISBN 1-55860-148-1 .
D. Haussler. Prezentare generală a cadrului de învățare probabil aproximativ corect (PAC) Arhivat la 28 septembrie 2011 la Wayback Machine . O introducere la subiect.
L. viteaz. Probabil Aproximativ Corect. Cărți de bază, 2013. În carte, Valiant discută despre modul în care învățarea VPK descrie modul în care organismele se dezvoltă și învață.

Î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