Empirisk risikominimering

Empirisk risikominimering ( ERM) er et princip for statistisk læringsteori, der definerer en familie af læringsalgoritmer , og som sætter de teoretiske grænser for ydeevne.

Fundamenter

Overvej følgende situation, som er den grundlæggende indstilling for mange overvågede læringsopgaver . Vi har to objektrum og og vil gerne træne en funktion (ofte kaldet en hypotese ), der kortlægger et objekt til et objekt . For at gøre dette har vi til rådighed et træningssæt af instanser , hvor input er og er det tilsvarende svar, som vi ønsker fra . $x$ $Y$ $\h:X\to Y$ $y\i Y$ $x\i X$ $n$ $\ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ $x_{i}\i X$ $y_{i}\in Y$ $\ h(x_{i})$

Mere formelt antage, at der er en fælles fordeling over og , og at træningssættet består af forekomster af , udvalgt fra uafhængige stokastiske variable fra . Bemærk, at den fælles fordelingsantagelse giver os mulighed for at simulere usikkerhed i forudsigelsen (for eksempel på grund af støj i dataene), da det ikke er en deterministisk funktion af , men derimod en tilfældig variabel med en betinget fordeling for en fast . $P(x, y)$ $x$ $Y$ $n$ $\ (x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ $P(x, y)$ $y$ $x$ $P(y|x)$ $x$

Antag også, at vi får en ikke-negativ real- vurderet tabsfunktion , som måler, hvor forskellig forudsigelsen af hypotesen er fra det sande output . Risikoen forbundet med hypotesen , defineres derefter som den forventede værdi af tabsfunktion: $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).

Tabsfunktionen 0-1 bruges ofte som tabsfunktionen i teorien : , hvor står for indikatoren . $L({\hat {y}},y)=I({\hat {y}}\neq y)$ $I(\dots )$

Det højeste mål med indlæringsalgoritmen er at finde en hypotese i en fast klasse af funktioner , hvor risikoen er minimal: $h^{*}$ ${\mathcal {H}}$ $R(h)$

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

Empirisk risikominimering

Generelt kan risikoen ikke beregnes, fordi fordelingen er ukendt for læringsalgoritmen (denne situation kaldes læringsagnostisk ). Vi kan dog beregne en tilnærmelse kaldet empirisk risiko ved at tage et gennemsnit af tabsfunktionen over træningssættet: $R(h)$ $P(x, y)$

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

Princippet om empirisk risikominimering (ERM) [1] siger, at læringsalgoritmen skal vælge den hypotese , der minimerer risikoen: ${\hat {h}}$

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

Så består læringsalgoritmen defineret af MED-princippet i at løse ovenstående optimeringsproblem .

Egenskaber

Beregningsmæssig kompleksitet

Det er kendt, at empirisk risikominimering for et klassifikationsproblem med en 0-1 tabsfunktion er NP-hård selv for en så relativt simpel klasse af problemfunktioner som lineære klassifikatorer [2] . Selvom det effektivt kan løses, når den minimale empiriske risiko er nul, dvs. dataene er lineært adskillelige .

I praksis håndterer auto-læringsalgoritmer dette enten ved konveks tilnærmelse til 0-1 af tabsfunktionen (svarende til den stykkevise lineære tabsfunktion for støtteelementmaskiner ), som er nemmere at optimere, eller ved at lave en antagelse om fordelingen (og så holder læringsalgoritmen op med at være agnostisk). $P(x, y)$

Se også

Maksimal sandsynlighed metode

Noter

↑ Vapnik, 1992 , s. 831-838.
↑ Feldman, Guruswami, Raghavendra, Wu, 2012 , s. 1558-1590.

Litteratur

Vapnik V. Principper for risikominimering for læringsteori // Fremskridt i neurale informationsbehandlingssystemer. – 1992.
Feldman V., Guruswami V., Raghavendra P., Yi Wu. Agnostic Learning of Monomials by Halfspaces is Hard // SIAM Journal on Computing. - 2012. - T. 41 , no. 6 . - S. 1558-1590 . - doi : 10.1137/120865094 .

Læsning for yderligere læsning

Vapnik V. Naturen af statistisk læringsteori. - 2000. - (Informationsvidenskab og statistik). - ISBN 978-0-387-98780-4 .

Machine learning og data mining
Opgaver	Klassifikationsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-Net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG