Minimizarea riscului empiric

Minimizarea riscului empiric ( ERM) este un principiu al teoriei învățării statistice care definește o familie de algoritmi de învățare și care stabilește limitele teoretice ale performanței.

Fundații

Luați în considerare următoarea situație, care este setarea de bază a multor sarcini de învățare supravegheată . Avem două spații obiect și am dori să antrenăm o funcție (deseori numită ipoteză ) care mapează un obiect cu un obiect . Pentru a face acest lucru, avem la dispoziție un set de antrenament de instanțe în care este intrarea și este răspunsul corespunzător pe care îl dorim de la . $X$ $Y$ $\h:X\la Y$ $y\în Y$ $x\în X$ $n$ $\ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ $x_{i}\în X$ $y_{i}\în Y$ $\ h(x_{i})$

Mai formal, să presupunem că există o distribuție comună peste și , și că setul de antrenament constă din instanțe ale lui , selectate dintre variabile aleatoare independente din . Rețineți că ipoteza distribuției comune ne permite să simulăm incertitudinea în predicție (de exemplu, din cauza zgomotului din date), deoarece nu este o funcție deterministă a lui , ci mai degrabă o variabilă aleatorie cu o distribuție condiționată pentru un . $P(x, y)$ $X$ $Y$ $n$ $\ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ $P(x, y)$ $y$ $X$ $P(y|x)$ $X$

Să presupunem, de asemenea, că ni se oferă o funcție de pierdere cu valoare reală nenegativă , care măsoară cât de diferită este predicția ipotezei față de rezultatul real Riscul asociat cu ipoteza este apoi definit ca valoarea așteptată a ipotezei. functie de pierdere: $L({\hat {y}},y)$ ${\pălărie {y)}$ $y.$ $h(x)$

R(h)=\mathbf {E} [L(h(x),y)]=\int L(h(x),y)\,dP(x,y).

Funcția de pierdere 0-1 este adesea folosită ca funcție de pierdere în teorie : , unde reprezintă indicatorul . $L({\hat {y}},y)=I({\hat {y}}\neq y)$ $I(\dots )$

Cel mai înalt obiectiv al algoritmului de învățare este găsirea unei ipoteze într-o clasă fixă de funcții pentru care riscul este minim: $h^{*}$ ${\mathcal {H}}$ $R(h)$

h^{*}=\arg \min _{h\in {\mathcal {H)}}R(h).

Minimizarea riscului empiric

În general, riscul nu poate fi calculat deoarece distribuția este necunoscută algoritmului de învățare (această situație se numește agnostică a învățării ). Cu toate acestea, putem calcula o aproximare numită risc empiric prin medierea funcției de pierdere pe setul de antrenament: $R(h)$ $P(x, y)$

\!R_{\text{emp}}(h)={\frac {1}{n}}\sum _{i=1}^{n}L(h(x_{i}), y_ {i}).

Principiul minimizării riscului empiric (ERM) [1] prevede că algoritmul de învățare ar trebui să aleagă ipoteza care minimizează riscul: ${\hat {h}}$

{\hat {h}}=\arg \min _{h\in {\mathcal {H}}}R_{\text{emp}}(h).

Apoi algoritmul de învățare definit de principiul MED constă în rezolvarea problemei de optimizare de mai sus .

Proprietăți

Complexitate computațională

Se știe că minimizarea riscului empiric pentru o problemă de clasificare cu o funcție de pierdere 0-1 este NP-hard chiar și pentru o clasă relativ simplă de funcții problema ca clasificatorii liniari [2] . Deși poate fi rezolvată eficient atunci când riscul empiric minim este zero, adică datele sunt separabile liniar .

În practică, algoritmii de auto-învățare se ocupă de acest lucru fie prin aproximarea convexă la 0-1 a funcției de pierdere (similar cu funcția de pierdere liniară pe bucăți pentru mașinile cu elemente suport ), care este mai ușor de optimizat, fie făcând o ipoteză despre distribuție (și atunci algoritmul de învățare încetează să mai fie agnostic). $P(x, y)$

Vezi și

Metoda maximă de probabilitate

Note

↑ Vapnik, 1992 , p. 831–838.
↑ Feldman, Guruswami, Raghavendra, Wu, 2012 , pp. 1558-1590.

Literatură

Vapnik V. Principles of Risk Minimization for Learning Theory // Avansuri în sistemele de procesare a informațiilor neuronale. — 1992.
Feldman V., Guruswami V., Raghavendra P., Yi Wu. Învățarea agnostică a monomiilor prin semispații este grea // SIAM Journal on Computing. - 2012. - T. 41 , nr. 6 . - S. 1558-1590 . - doi : 10.1137/120865094 .

Lectură pentru lecturi suplimentare

Vapnik V. Natura teoriei învățării statistice. - 2000. - (Stiinta Informatiei si Statistica). - ISBN 978-0-387-98780-4 .

Î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