Eroare de generalizare - Generalization error

Pentru aplicațiile de învățare supravegheate în învățarea automată și teoria învățării statistice , eroarea de generalizare (cunoscută și sub numele de eroare din eșantion sau risc ) este o măsură a cât de precis este un algoritm capabil să prezică valorile rezultatelor pentru datele nevăzute anterior. Deoarece algoritmii de învățare sunt evaluați pe eșantioane finite, evaluarea unui algoritm de învățare poate fi sensibilă la eroarea de eșantionare . Ca rezultat, măsurătorile erorii de predicție pe datele actuale pot să nu furnizeze prea multe informații despre capacitatea de predicție a datelor noi. Eroarea de generalizare poate fi redusă la minimum evitând supraadaptarea în algoritmul de învățare. Performanța unui algoritm de învățare automată este vizualizată de grafice care prezintă valori ale estimărilor erorii de generalizare prin procesul de învățare, care se numesc curbe de învățare .

Definiție

Într-o problemă de învățare, scopul este de a dezvolta o funcție care prezice valorile de ieșire pentru fiecare datum de intrare . Indicele indică faptul că funcția este dezvoltată pe baza unui set de date de puncte de date. Eroarea generalizare sau pierderea așteptată sau riscul , unei anumite funcții pe toate valorile posibile ale și este: ${\ 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 \ times Y} V (f ({\ vec {x}}), y) \ rho ({\ vec {x}}, y) d {\ vec { x}} dy,}$

unde denotă o funcție de pierdere și este distribuția necunoscută a probabilității comune pentru și . ${\ displaystyle V}$${\ displaystyle \ rho ({\ vec {x}}, y)}$${\ displaystyle {\ vec {x}}}$${\ displaystyle y}$

Fără a cunoaște distribuția comună a probabilității , este imposibil de calculat . În schimb, putem calcula eroarea pe datele eșantionului, care se numește eroare empirică (sau risc empiric ). Având în vedere punctele de date, eroarea empirică a unei funcții candidate este: ${\ 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})}$

Se spune că un algoritm generalizează dacă:

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

O importanță deosebită este eroarea de generalizare a funcției dependente de date care este găsită de un algoritm de învățare bazat pe eșantion. Din nou, pentru o distribuție de probabilitate necunoscută, nu se poate calcula. În schimb, scopul multor probleme din teoria învățării statistice este de a lega sau de a caracteriza diferența erorii de generalizare și a erorii empirice de probabilitate: ${\ 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}}$

Adică, scopul este de a caracteriza probabilitatea ca eroarea de generalizare să fie mai mică decât eroarea empirică plus o anumită eroare legată (în general dependentă de și ). Pentru multe tipuri de algoritmi, s-a demonstrat că un algoritm are limite de generalizare dacă îndeplinește anumite criterii de stabilitate . Mai exact, dacă un algoritm este simetric (ordinea intrărilor nu afectează rezultatul), are o pierdere mărginită și îndeplinește două condiții de stabilitate, se va generaliza. Prima condiție de stabilitate, concediu one-out cross-validare a stabilității, spune că pentru a fi stabil, eroarea de predicție pentru fiecare punct de date atunci când validarea încrucișată iasă dintr - unul-out este folosit trebuie să conveargă la zero . Cea de-a doua condiție, stabilitatea erorii așteptate de a părăsi o singură ieșire (cunoscută și sub numele de stabilitate de ipoteză dacă funcționează în normă ) este îndeplinită dacă predicția pentru un punct de date rămas nu se modifică atunci când un singur punct de date este eliminat din set de date de antrenament. ${\ displaystyle 1- \ delta _ {n}}$${\ displaystyle \ epsilon}$${\ displaystyle \ delta}$${\ displaystyle n}$${\ displaystyle n \ rightarrow \ infty}$${\ displaystyle L_ {1}}$

Aceste condiții pot fi formalizate ca:

Stabiliți stabilitatea de validare încrucișată

Un algoritm are stabilitate dacă pentru fiecare , există un și astfel încât: ${\ 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)}}$

și și du-te la zero așa cum merge la infinit. ${\ displaystyle \ beta _ {CV} ^ {(n)}}$${\ displaystyle \ delta _ {CV} ^ {(n)}}$${\ displaystyle n}$

Așteptat-lăsați-o singură eroare Stabilitate

Un algoritm are stabilitate dacă pentru fiecare există un și un astfel încât: ${\ 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 \ left (f_ {S ^ {i}}, z_ {i} \ right) \ right | \ leq \ beta _ {EL} ^ {( n)} \ right \} \ geq 1- \ delta _ {EL} ^ {(n)}}$

cu și mergând la zero pentru . ${\ displaystyle \ beta _ {EL} ^ {(n)}}$${\ displaystyle \ delta _ {EL} ^ {(n)}}$${\ displaystyle n \ rightarrow \ infty}$

Pentru stabilitatea de tip „out-one-out” , aceasta este aceeași cu stabilitatea ipotezei: ${\ displaystyle L_ {1}}$

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

cu mersul la zero ca și la infinit. ${\ displaystyle \ beta _ {H} ^ {(n)}}$${\ displaystyle n}$

Algoritmi cu stabilitate dovedită

Un număr de algoritmi s-a dovedit a fi stabil și, ca urmare, au limite asupra erorii lor de generalizare. O listă a acestor algoritmi și a lucrărilor care au dovedit stabilitate este disponibilă aici .

Relația cu supra-dotarea

Această figură ilustrează relația dintre supraadaptare și eroarea de generalizare I [ f _n ] - I _S [ f _n ]. Punctele de date au fost generate din relația y = x cu zgomot alb adăugat valorilor y . În coloana din stânga, un set de puncte de antrenament este afișat în albastru. O funcție polinomială de ordinul al șaptelea s-a potrivit datelor de antrenament. În coloana din dreapta, funcția este testată pe date eșantionate din distribuția probabilității subiacente a x și y . În rândul de sus, funcția se potrivește pe un eșantion de set de date de 10 puncte de date. În rândul de jos, funcția se potrivește pe un eșantion de set de date de 100 de puncte de date. După cum putem vedea, pentru dimensiuni mici ale eșantionului și funcții complexe, eroarea la setul de antrenament este mică, dar eroarea la distribuția subiacentă a datelor este mare și avem supradimensionarea datelor. Ca urmare, eroarea de generalizare este mare. Pe măsură ce crește numărul de puncte de eșantionare, eroarea de predicție la datele de antrenament și test converge, iar eroarea de generalizare merge la 0.

Conceptele de eroare de generalizare și supraadaptare sunt strâns legate. Suprapunerea apare atunci când funcția învățată devine sensibilă la zgomotul din eșantion. Ca rezultat, funcția va funcționa bine pe setul de antrenament, dar nu va funcționa bine pe alte date din distribuția comună a probabilității și . Astfel, cu cât are loc o supraadaptare mai mare, cu atât este mai mare eroarea de generalizare. ${\ displaystyle f_ {S}}$${\ displaystyle x}$${\ displaystyle y}$

Cantitatea de supra-montare poate fi testată folosind metode de validare încrucișată , care împart eșantionul în probe de antrenament simulate și probe de testare. Modelul este apoi instruit pe un eșantion de instruire și evaluat pe eșantionul de testare. Eșantionul de testare este nevăzut anterior de algoritm și reprezintă un eșantion aleatoriu din distribuția comună a probabilității și . Acest eșantion de test ne permite să aproximăm eroarea așteptată și, ca rezultat, să aproximăm o anumită formă a erorii de generalizare. ${\ displaystyle x}$${\ displaystyle y}$

Există mulți algoritmi pentru a preveni supraadaptarea. Algoritmul de minimizare poate penaliza funcții mai complexe (cunoscute sub numele de regularizare Tikhonov ), sau spațiul ipotezei poate fi limitat, fie în mod explicit sub forma funcțiilor, fie prin adăugarea de constrângeri la funcția de minimizare (regularizarea Ivanov).

Abordarea de a găsi o funcție care nu se potrivește este în contradicție cu scopul de a găsi o funcție suficient de complexă pentru a surprinde caracteristicile particulare ale datelor. Aceasta este cunoscută sub denumirea de compromis-variație . Menținerea unei funcții simple pentru a evita supraadaptarea poate introduce o prejudecată în predicțiile rezultate, permițând în același timp o mai complexă, duce la depășirea și la o varianță mai mare a predicțiilor. Este imposibil să le minimizăm pe ambele simultan.

Referințe

Lecturi suplimentare

• Bousquet, O., S. Boucheron și G. Lugosi. Introducere în teoria învățării statistice . Prelegeri avansate despre învățarea automată Note de prelegere în inteligență artificială 3176, 169-207. (Eds.) Bousquet, O., U. von Luxburg și G. Ratsch, Springer, Heidelberg, Germania (2004)
• Bousquet, O. și A. Elisseef (2002), Stabilitate și generalizare, Journal of Machine Learning Research, 499-526.
• Devroye L., L. Gyorfi și G. Lugosi (1996). O teorie probabilistică a recunoașterii tiparelor. Springer-Verlag. ISBN   978-0387946184 .
• Poggio T. și S. Smale. Matematica învățării: tratarea datelor . Notificări ale AMS, 2003
• Vapnik, V. (2000). Natura teoriei învățării statistice. Știința informației și statisticile. Springer-Verlag. ISBN   978-0-387-98780-4 .
• Bishop, CM (1995), Rețele neuronale pentru recunoașterea modelelor , Oxford: Oxford University Press, în special secțiunea 6.4.
• Finke, M. și Müller, K.-R. (1994), „ Estimarea a-posteriori a probabilităților folosind modele de rețea stocastice ”, în Mozer, Smolensky, Touretzky, Elman și Weigend, eds., Proceedings of the 1993 Connectionist Models Summer School , Hillsdale, NJ: Lawrence Erlbaum Associates, pp. 324–331.
• Geman, S., Bienenstock, E. și Doursat, R. (1992), „ Rețelele neuronale și dilema Bias / Variance ”, Neural Computation , 4, 1-58.
• Husmeier, D. (1999), Rețele neuronale pentru estimarea probabilității condiționate: prognozarea dincolo de previziuni punctuale , Berlin: Springer Verlag, ISBN   1-85233-095-3 .
• McCullagh, P. și Nelder, JA (1989) Generalized Linear Models , ediția a II-a, Londra: Chapman & Hall.
• Mohri, M., Rostamizadeh A., Talwakar A., ​​(2018) Foundations of Machine learning , ediția a doua, Boston: MIT Press.
• Moody, JE (1992), „ Numărul efectiv de parametri: o analiză a generalizării și regularizării în sistemele de învățare neliniare ”, în Moody, JE, Hanson, SJ și Lippmann, RP, Progrese în sistemele de procesare a informațiilor neuronale 4, 847- 854.
• Ripley, BD (1996) Pattern Recognition and Neural Networks , Cambridge: Cambridge University Press.
• Rohwer, R. și van der Rest, JC (1996), " Lungimea descrierii minime, regularizarea și datele multimodale ", Neural Computation , 8, 595-609.
• Rojas, R. (1996), „ O scurtă dovadă a proprietății probabilității posterioare a rețelelor neuronale de clasificare ”, Neural Computation , 8, 41-43.
• White, H. (1990), „ Regresie nonparametrică conexionistă: rețelele multistrat avansate pot învăța mapări arbitrare ” , Rețele neuronale , 3, 535-550. Reeditat în alb (1992).
• White, H. (1992a), " Estimarea nonparametrică a cuantilelor condiționate folosind rețele neuronale ", în Page, C. și Le Page, R. (eds.), Proceedings of the 23rd Sympsium on the Interface: Computing Science and Statistics , Alexandria , VA: American Statistical Association, pp. 190-199. Reeditat în alb (1992b).
• White, H. (1992b), Rețele neuronale artificiale: aproximare și teorie a învățării , Blackwell.