Empirická minimalizace rizika

Empirická minimalizace rizik ( ERM) je princip statistické teorie učení , který definuje rodinu algoritmů učení a nastavuje teoretické hranice výkonu.

Základy

Zvažte následující situaci, která je základním nastavením mnoha řízených učebních úloh . Máme dva prostory objektů a rádi bychom trénovali funkci (často nazývanou hypotéza ), která mapuje objekt na objekt . K tomu máme k dispozici trénovací sadu instancí , kde je vstup a odpovídající odpověď, kterou od . $X$ $Y$ $\h:X\to Y$ $y\v Y$ $x\in X$ $n$ $\ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ $x_{i}\v X$ $y_{i}\in Y$ $\ h(x_{i})$

Formálněji předpokládejme, že existuje společné rozdělení přes a , a že trénovací množina se skládá z instancí , vybraných z nezávislých náhodných proměnných z . Všimněte si, že předpoklad společného rozdělení nám umožňuje simulovat nejistotu v predikci (například kvůli šumu v datech), protože nejde o deterministickou funkci , ale spíše o náhodnou veličinu s podmíněným rozdělením pro pevnou . $P(x, y)$ $X$ $Y$ $n$ $\ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ $P(x, y)$ $y$ $X$ $P(y|x)$ $X$

Předpokládejme také, že je nám dána nezáporná funkce reálných ztrát , která měří, jak odlišná je předpověď hypotézy od skutečného výstupu . Riziko spojené s hypotézou je pak definováno jako očekávaná hodnota ztrátová funkce: $L({\hat {y}},y)$ ${\hat {y))$ $y$ $h(x)$

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

Ztrátová funkce 0-1 se teoreticky často používá jako ztrátová funkce : , kde znamená indikátor . $L({\hat {y}},y)=I({\hat {y}}\neq y)$ $I(\dots )$

Nejvyšším cílem algoritmu učení je najít hypotézu v pevné třídě funkcí, pro kterou je riziko minimální: $h^{*}$ ${\mathcal {H}}$ $R(h)$

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

Empirická minimalizace rizika

Obecně nelze riziko vypočítat, protože algoritmus učení nezná distribuci (tato situace se nazývá agnostické učení ). Můžeme však vypočítat aproximaci nazývanou empirické riziko zprůměrováním ztrátové funkce přes trénovací množinu: $R(h)$ $P(x, y)$

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

Princip empirické minimalizace rizika (ERM) [1] uvádí, že algoritmus učení by měl zvolit hypotézu , která riziko minimalizuje: ${\klobouk {h}}$

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

Potom algoritmus učení definovaný na principu MED spočívá v řešení výše uvedeného optimalizačního problému .

Vlastnosti

Výpočetní složitost

Je známo, že empirická minimalizace rizika pro klasifikační problém se ztrátovou funkcí 0-1 je NP-obtížná i pro tak relativně jednoduchou třídu problémových funkcí, jako jsou lineární klasifikátory [2] . I když to lze efektivně vyřešit, když je minimální empirické riziko nulové, tj. data jsou lineárně oddělitelná .

V praxi se s tím algoritmy automatického učení vypořádávají buď konvexní aproximací k 0-1 ztrátové funkce (podobně jako po částech lineární ztrátová funkce pro stroje s podpůrnými prvky ), což je snazší optimalizovat, nebo vytvořením předpokladu o distribuci (a pak algoritmus učení přestane být agnostický). $P(x, y)$

Viz také

Metoda maximální pravděpodobnosti

Poznámky

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

Literatura

Vapnik V. Principy minimalizace rizik pro teorii učení // Pokroky v systémech zpracování nervových informací. — 1992.
Feldman V., Guruswami V., Raghavendra P., Yi Wu. Agnostic Learning of Monomials by Halfspaces je těžký // SIAM Journal on Computing. - 2012. - T. 41 , č. 6 . - S. 1558-1590 . - doi : 10.1137/120865094 .

Čtení pro další čtení

Vapnik V. Povaha statistické teorie učení. - 2000. - (Informační věda a statistika). - ISBN 978-0-387-98780-4 .

Strojové učení a dolování dat
Úkoly	Klasifikační problém Učení bez učitele Učení za pomoci učitele Regresní analýza AutoML Pravidla asociace Extrakce funkcí Trénink vlastností Žebříčkový trénink Gramatické odvozování Online učení
Učení s učitelem	metoda k-nejbližšího souseda Naivní Bayesův klasifikátor rozhodovací strom Podpora vektorového stroje Lineární regrese Logistická regrese perceptron Soubory modelů Pytlování posilování náhodný les Relevantní vektorová metoda
shluková analýza	metoda k-means Metoda fuzzy shlukování Hierarchické shlukování EM algoritmus BŘÍZA LÉK DBSCAN OPTIKA Střední posun
Redukce rozměrů	Faktorová analýza Metoda hlavní součásti CCA ICA LDA Nezáporná expanze matice t-SNE
Strukturální prognózy	Graf pravděpodobnosti modelu Bayesovská síť Skrytý Markovův model CRF
Detekce anomálií	metoda k-nejbližšího souseda Místní úroveň emisí
Grafové pravděpodobnostní modely	Bayesovská síť Markovská síť Skrytý Markovův model
Neuronové sítě	Limitovaný Boltzmannův stroj samoorganizující se mapa Aktivační funkce Sigmoid softmax Radiální základní funkce Metoda zpětného šíření Hluboké učení Vícevrstvý perceptron Rekurentní neuronová síť dlouhodobá krátkodobá paměť Řízený rekurentní blok Konvoluční neuronová síť U-Net Autokodér
Posílení učení	Markovský proces Bellmanova rovnice Chamtivý algoritmus Q-learning SARSA Časový rozdíl (TD)
Teorie	Vapnik-Chervonenkis teorie Dilema zkreslení Teorie počítačového učení Empirická minimalizace rizika Occam se učí PAC učení Statistická teorie učení
Časopisy a konference	NeurIPS ICML ML JMLR ArXiv:cs.LG