Generaliseringsfel - Generalization error

För övervakade inlärnings applikationer i maskininlärning och statistisk inlärningsteori , generalisering fel (även känd som out-of-sample fel eller risk ) är ett mått på hur exakt en algoritm kan förutsäga utfallsvärden för tidigare osedda data. Eftersom inlärningsalgoritmer utvärderas på ändliga prover kan utvärderingen av en inlärningsalgoritm vara känslig för samplingsfel . Som ett resultat kan det hända att mätningar av förutsägelsesfel på aktuell data inte ger mycket information om förutsägbar förmåga på nya data. Generaliseringsfel kan minimeras genom att undvika överanpassning i inlärningsalgoritmen. Utförandet av en maskininlärningsalgoritm visualiseras genom tomter som visar värden på uppskattningar av generalisering felet genom inlärningsprocessen, vilka kallas inlärningskurvor .

Definition

I ett inlärningsproblem är målet att utveckla en funktion som förutsäger utgångsvärden för varje ingångsdatum . Prenumerationen indikerar att funktionen är utvecklad baserat på en datauppsättning med datapunkter. Den generalisering fel eller förväntad förlust eller risk , för en viss funktion över alla möjliga värden av och är: ${\ displaystyle f_ {n} ({\ vec {x}})}$${\ displaystyle y}$${\ displaystyle {\ vec {x}}}$${\ displaystyle n}$${\ displaystyle f_ {n}}$${\ displaystyle n}$${\ displaystyle I [f]}$${\ displaystyle f}$${\ displaystyle {\ vec {x}}}$${\ displaystyle y}$

${\ displaystyle I [f] = \ int _ {X \ gånger Y} V (f ({\ vec {x}}), y) \ rho ({\ vec {x}}, y) d {\ vec { x}} dy,}$

där betecknar en förlustfunktion och är den okända gemensamma sannolikhetsfördelningen för och . ${\ displaystyle V}$${\ displaystyle \ rho ({\ vec {x}}, y)}$${\ displaystyle {\ vec {x}}}$${\ displaystyle y}$

Utan att känna till den gemensamma sannolikhetsfördelningen är det omöjligt att beräkna . Istället kan vi beräkna felet på exempeldata, som kallas empiriskt fel (eller empirisk risk ). Med tanke på datapunkter är det empiriska felet för en kandidatfunktion : ${\ displaystyle \ rho}$${\ displaystyle I [f]}$${\ displaystyle n}$${\ displaystyle f}$

${\ displaystyle I_ {n} [f] = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} V (f ({\ vec {x}} _ {i}), y_ {i})}$

En algoritm sägs generalisera om:

${\ displaystyle \ lim _ {n \ rightarrow \ infty} I [f] -I_ {n} [f] = 0}$

Av särskild betydelse är generaliseringsfelet för den databeroende funktionen som hittas av en inlärningsalgoritm baserad på urvalet. Återigen, för en okänd sannolikhetsfördelning, kan inte beräknas. Istället är syftet med många problem i statistisk inlärningsteori att binda eller karakterisera skillnaden mellan generaliseringsfelet och det empiriska felet i sannolikhet: ${\ displaystyle I [f_ {n}]}$${\ displaystyle f_ {n}}$${\ displaystyle I [f_ {n}]}$

${\ displaystyle P_ {G} = P (I [f_ {n}] - I_ {n} [f_ {n}] \ leq \ epsilon) \ geq 1- \ delta _ {n}}$

Det vill säga målet är att karakterisera sannolikheten för att generaliseringsfelet är mindre än det empiriska felet plus något felbundet (i allmänhet beroende av och ). För många typer av algoritmer har det visat sig att en algoritm har generaliseringsgränser om den uppfyller vissa stabilitetskriterier . Specifikt, om en algoritm är symmetrisk (ingångsordningen påverkar inte resultatet), har begränsad förlust och uppfyller två stabilitetsvillkor, kommer den att generaliseras. Det första stabilitetsvillkoret, lämna en-ut-korsvalideringsstabilitet , säger att för att vara stabil måste förutsägelsefelet för varje datapunkt när korsvalidering för utlämning används konvergera till noll som . Det andra villkoret, förväntad-att-lämna-en-ut-felstabilitet (även känd som hypotesstabilitet om den fungerar i normen ) är uppfylld om förutsägelsen på en utelämnad datapunkt inte ändras när en enda datapunkt tas bort från utbildningsdataset. ${\ displaystyle 1- \ delta _ {n}}$${\ displaystyle \ epsilon}$${\ displaystyle \ delta}$${\ displaystyle n}$${\ displaystyle n \ rightarrow \ infty}$${\ displaystyle L_ {1}}$

Dessa villkor kan formaliseras som:

Lämna en enstaka korsvalideringsstabilitet

En algoritm har stabilitet om det för varje finns en och sådan att: ${\ displaystyle L}$${\ displaystyle CVloo}$${\ displaystyle n}$${\ displaystyle \ beta _ {CV} ^ {(n)}}$${\ displaystyle \ delta _ {CV} ^ {(n)}}$

${\ displaystyle \ forall i \ in \ {1, ..., n \}, \ mathbb {P} _ {S} \ {| V (f_ {S ^ {i}}, z_ {i}) - V (f_ {S}, z_ {i}) | \ leq \ beta _ {CV} ^ {(n)} \} \ geq 1- \ delta _ {CV} ^ {(n)}}$

och och gå till noll som går till oändligheten. ${\ displaystyle \ beta _ {CV} ^ {(n)}}$${\ displaystyle \ delta _ {CV} ^ {(n)}}$${\ displaystyle n}$

Förväntat-lämna-en-ut-felstabilitet

En algoritm har stabilitet om det för varje finns en och en sådan att: ${\ displaystyle L}$${\ displaystyle Eloo_ {err}}$${\ displaystyle n}$${\ displaystyle \ beta _ {EL} ^ {m}}$${\ displaystyle \ delta _ {EL} ^ {m}}$

${\ displaystyle \ forall i \ in \ {1, ..., n \}, \ mathbb {P} _ {S} \ left \ {\ left | I [f_ {S}] - {\ frac {1} {n}} \ sum _ {i = 1} ^ {N} V \ vänster (f_ {S ^ {i}}, z_ {i} \ höger) \ höger | \ leq \ beta _ {EL} ^ {( n)} \ höger \} \ geq 1- \ delta _ {EL} ^ {(n)}}$

med och går till noll för . ${\ displaystyle \ beta _ {EL} ^ {(n)}}$${\ displaystyle \ delta _ {EL} ^ {(n)}}$${\ displaystyle n \ rightarrow \ infty}$

För utelämningsstabilitet i normen är detta detsamma som hypotesstabilitet: ${\ displaystyle L_ {1}}$

${\ displaystyle \ mathbb {E} _ {S, z} [| V (f_ {S}, z) -V (f_ {S ^ {i}}, z) |] \ leq \ beta _ {H} ^ {(n)}}$

med att gå till noll som går till oändligheten. ${\ displaystyle \ beta _ {H} ^ {(n)}}$${\ displaystyle n}$

Algoritmer med beprövad stabilitet

Ett antal algoritmer har visat sig vara stabila och har som ett resultat gränser för deras generaliseringsfel. En lista över dessa algoritmer och papper som visade stabilitet finns här .

Förhållande till överanpassning

Denna figur illustrerar förhållandet mellan överanpassning och generaliseringsfelet I [ f _n ] - I _S [ f _n ]. Datapunkter genererades från förhållandet y = x med vitt brus adderat till y- värdena. I den vänstra kolumnen visas en uppsättning träningspunkter i blått. En sjunde ordningens polynomfunktion passade träningsdata. I den högra kolumnen testas funktionen på data som samplats från den underliggande gemensamma sannolikhetsfördelningen av x och y . I den översta raden passar funktionen i ett exempel på 10 datapunkter. I den nedre raden passar funktionen på ett exempel på 100 datapunkter. Som vi kan se, för små provstorlekar och komplexa funktioner är felet på träningsuppsättningen litet men felet i den underliggande fördelningen av data är stort och vi har överträffat data. Som ett resultat är generaliseringsfelet stort. När antalet provpunkter ökar konvergerar prediktionsfelet vid träning och testdata och generaliseringsfelet går till 0.

Begreppen generaliseringsfel och överanpassning är nära besläktade. Överanpassning sker när den inlärda funktionen blir känslig för bruset i provet. Som ett resultat kommer funktionen att fungera bra på träningsuppsättningen men inte fungera bra på andra data från den gemensamma sannolikhetsfördelningen av och . Ju mer överanpassning inträffar, desto större generaliseringsfel. ${\ displaystyle f_ {S}}$${\ displaystyle x}$${\ displaystyle y}$

Mängden överanpassning kan testas med korsvalideringsmetoder , som delar provet i simulerade träningsprover och testprover. Modellen tränas sedan på ett träningsprov och utvärderas på testprovet. Testprovet är tidigare osynligt av algoritmen och representerar sålunda ett slumpmässigt urval från den gemensamma sannolikhetsfördelningen av och . Detta testprov gör det möjligt för oss att approximera det förväntade felet och som ett resultat uppskatta en viss form av generaliseringsfelet. ${\ displaystyle x}$${\ displaystyle y}$

Många algoritmer finns för att förhindra övermontering. Minimeringsalgoritmen kan bestraffa mer komplexa funktioner (känd som Tikhonov- regularisering ), eller hypotesutrymmet kan begränsas, antingen uttryckligen i form av funktionerna eller genom att lägga till begränsningar för minimeringsfunktionen (Ivanov-reglering).

Tillvägagångssättet för att hitta en funktion som inte överträffar strider mot målet att hitta en funktion som är tillräckligt komplex för att fånga de specifika egenskaperna hos datan. Detta är känt som avvägning mellan bias och varians . Att hålla en funktion enkel för att undvika överanpassning kan införa en förspänning i de resulterande förutsägelserna, samtidigt som den blir mer komplex leder till överanpassning och en högre variation i förutsägelserna. Det är omöjligt att minimera båda samtidigt.

Referenser

Vidare läsning

• Bousquet, O., S. Boucheron och G. Lugosi. Introduktion till statistisk inlärningsteori . Avancerade föreläsningar om maskininlärningsföreläsningsanteckningar i artificiell intelligens 3176, 169-207. (Red.) Bousquet, O., U. von Luxburg och G. Ratsch, Springer, Heidelberg, Tyskland (2004)
• Bousquet, O. och A. Elisseef (2002), Stabilitet och generalisering, Journal of Machine Learning Research, 499-526.
• Devroye L., L. Gyorfi och G. Lugosi (1996). En probabilistisk teori om mönsterigenkänning. Springer-Verlag. ISBN   978-0387946184 .
• Poggio T. och S. Smale. Matematik för lärande: hantera data . Meddelanden från AMS, 2003
• Vapnik, V. (2000). Arten av statistisk inlärningsteori. Informationsvetenskap och statistik. Springer-Verlag. ISBN   978-0-387-98780-4 .
• Bishop, CM (1995), Neural Networks for Pattern Recognition , Oxford: Oxford University Press, särskilt avsnitt 6.4.
• Finke, M. och Müller, K.-R. (1994), " Uppskatta a-posteriori sannolikheter med hjälp av stokastiska nätverksmodeller ," i Mozer, Smolensky, Touretzky, Elman, & Weigend, eds., Proceedings of the 1993 Connectionist Models Summer School , Hillsdale, NJ: Lawrence Erlbaum Associates, pp. 324–331.
• Geman, S., Bienenstock, E. och Doursat, R. (1992), " Neural Networks and the Bias / Variance Dilemma ", Neural Computation , 4, 1-58.
• Husmeier, D. (1999), Neural Networks for Conditional Probability Estimation: Forecasting Beyond Point Predictions , Berlin: Springer Verlag, ISBN   1-85233-095-3 .
• McCullagh, P. och Nelder, JA (1989) Generaliserade linjära modeller , 2: a upplagan, London: Chapman & Hall.
• Mohri, M., Rostamizadeh A., Talwakar A., ​​(2018) Foundations of Machine learning , 2: a upplagan, Boston: MIT Press.
• Moody, JE (1992), " The Effective Number of Parameters: An Analysis of Generalization and Regularization in Nonlinear Learning Systems ", i Moody, JE, Hanson, SJ och Lippmann, RP, Advances in Neural Information Processing Systems 4, 847- 854.
• Ripley, BD (1996) Mönsterigenkänning och neurala nätverk , Cambridge: Cambridge University Press.
• Rohwer, R. och van der Rest, JC (1996), " Minsta beskrivningslängd, regularisering och multimodala data ," Neural Computation , 8, 595-609.
• Rojas, R. (1996), " Ett kort bevis på den bakre sannolikhetsegenskapen hos klassificerande neurala nätverk ," Neural Computation , 8, 41-43.
• White, H. (1990), " Connectionist Nonparametric Regression: Multilayer Feedforward Networks Can Learn Arbitrary Mappings ," Neural Networks , 3, 535-550. Omtryckt i vitt (1992).
• White, H. (1992a), " Nonparametric Estimation of Conditional Quantiles Using Neural Networks ", i Page, C. och Le Page, R. (red.), Proceedings of the 23rd Sympsium on the Interface: Computing Science and Statistics , Alexandria , VA: American Statistical Association, s. 190–199. Omtryckt i vitt (1992b).
• White, H. (1992b), Artificial Neural Networks: Approximation and Learning Theory , Blackwell.