Minimalizacja ryzyka empirycznego - Empirical risk minimization

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii Czyszczenie danych AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY LECZYĆ Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v T mi

Empiryczna minimalizacja ryzyka (ERM) jest zasadą statystycznej teorii uczenia się, która definiuje rodzinę algorytmów uczenia się i służy do określenia teoretycznych granic ich wydajności. Podstawową ideą jest to, że nie możemy dokładnie wiedzieć, jak dobrze algorytm będzie działał w praktyce (prawdziwe „ryzyko”), ponieważ nie znamy prawdziwego rozkładu danych, na którym algorytm będzie działał, ale zamiast tego możemy mierzyć jego wydajność na podstawie znany zestaw danych uczących (ryzyko „empiryczne”).

Tło

Rozważ następującą sytuację, która jest ogólnym ustawieniem wielu nadzorowanych problemów w uczeniu się . Mamy dwie przestrzenie obiektów i chcielibyśmy nauczyć się funkcji (często nazywanej hipotezą ), która wyprowadza obiekt , dany . Aby to zrobić, mamy do dyspozycji zestaw treningowy z przykładów , gdzie jest wejście i jest odpowiedź, że chcemy dostać od . ${\ Displaystyle X}$${\ Displaystyle Y}$${\ Displaystyle \ h: X \ do Y}$${\ Displaystyle y \ w Y}$${\ Displaystyle x \ w X}$${\ Displaystyle n}$${\ Displaystyle \ (x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n})}$${\ Displaystyle X_ {i} \ w X}$${\ Displaystyle y_ {i} \ w Y}$${\ Displaystyle \ h (x_ {i})}$

Mówiąc bardziej formalnie, zakładamy, że istnieje łączny rozkład prawdopodobieństwa nad i , a zbiór uczący składa się z instancji wylosowanych z iid . Należy zauważyć, że założenie łącznego rozkładu prawdopodobieństwa pozwala nam modelować niepewność w przewidywaniach (np. z szumu w danych), ponieważ nie jest to funkcja deterministyczna , ale raczej zmienna losowa z rozkładem warunkowym dla ustalonego . ${\displaystyle P(x,y)}$${\ Displaystyle X}$${\ Displaystyle Y}$${\ Displaystyle n}$${\ Displaystyle \ (x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n})}$${\displaystyle P(x,y)}$${\displaystyle y}$${\displaystyle x}$ ${\ Displaystyle P (y | x)}$${\displaystyle x}$

Zakładamy również, że otrzymujemy nieujemną funkcję straty o wartościach rzeczywistych, która mierzy, jak różni się przewidywanie hipotezy od rzeczywistego wyniku . Ryzyko związane z hipotezą jest następnie definiowane jako oczekiwanie funkcji straty: ${\ Displaystyle L ({\ kapelusz {y}}, r)}$${\displaystyle {\kapelusz {y}}}$${\ Displaystyle y.}$${\ Displaystyle h (x)}$

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

Funkcja straty powszechnie stosowana w teorii to funkcja straty 0-1 : . ${\ Displaystyle L ({\ kapelusz {y}}, r) = {\ zacząć {przypadki} 1 i {\ mbox {jeśli}} \ quad {\ kapelusz {y}} \ neq r \ \ 0 i {\ mbox {jeśli }}\quad {\hat {y}}=y\end{przypadki}}}$

Ostatecznym celem algorytmu uczącego jest znalezienie hipotezy wśród ustalonej klasy funkcji, dla której ryzyko jest minimalne: ${\ Displaystyle h ^ {*}}$${\ Displaystyle {\ Mathcal {H}}}$${\ Displaystyle R (h)}$

${\ Displaystyle h ^ {*} = {\ underset {h \ w {\ mathcal {H}}} {\ operatorname {arg \ min}}} \ {R (h)}}.$

Minimalizacja ryzyka empirycznego

Ogólnie ryzyko nie może być obliczone, ponieważ rozkład jest nieznany algorytmowi uczącemu (sytuacja ta jest określana jako uczenie agnostyczne ). Możemy jednak obliczyć przybliżenie, zwane ryzykiem empirycznym , uśredniając funkcję straty na zbiorze uczącym: ${\ Displaystyle R (h)}$${\displaystyle P(x,y)}$

${\ Displaystyle \! R_ {\ tekst {emp}} (h) = {\ Frac {1} {n}} \ suma _ {i = 1} ^ {n} L (h (x_ {i}), y_ {i}).}$

Zasada minimalizacji ryzyka empirycznego mówi, że algorytm uczący powinien wybrać hipotezę, która minimalizuje ryzyko empiryczne: ${\ Displaystyle {\ kapelusz {h}}}$

${\ Displaystyle {\ kapelusz {h}} = {\ underset {h \ w {\ mathcal {H}}} {\ operatorname {arg \, min}}} \ R_ {\ tekst {emp}} (h) .}$

Zatem algorytm uczenia określony zasadą ERM polega na rozwiązaniu powyższego problemu optymalizacyjnego .

Nieruchomości

Złożoność obliczeniowa

Wiadomo, że minimalizacja ryzyka empirycznego dla problemu klasyfikacji z funkcją straty 0-1 jest problemem NP-trudnym, nawet dla tak stosunkowo prostej klasy funkcji, jak klasyfikatory liniowe . Można to jednak skutecznie rozwiązać, gdy minimalne ryzyko empiryczne wynosi zero, tj. dane są liniowo separowalne .

W praktyce algorytmy uczenia maszynowego radzą sobie z tym albo przez zastosowanie wypukłego przybliżenia do funkcji straty 0-1 (jak strata zawiasowa dla SVM ), która jest łatwiejsza do optymalizacji, albo przez narzucanie założeń na rozkład (i tym samym przestają być uczeniem agnostycznym algorytmy, których dotyczy powyższy wynik). ${\displaystyle P(x,y)}$

Zobacz też

• Szacowanie maksymalnego prawdopodobieństwa
• M-estymator

Bibliografia

Dalsza lektura

• Vapnik, V. (2000). Istota statystycznej teorii uczenia się . Informatyka i statystyka. Springer-Verlag . Numer ISBN 978-0-387-98780-4.