Generalizarea

Luați în considerare doi studenți care se pregătesc cu sârguință pentru examenul final. De obicei, această pregătire va consta în exersarea și testarea abilităților lor prin rezolvarea examenelor administrate în anii precedenți. Cu toate acestea, obținerea unui rezultat bun la examenele trecute nu este o garanție că vor excela atunci când contează. De exemplu, imaginați-vă o studentă, Ellie Extraordinara, a cărei pregătire a constat în întregime în memorarea răspunsurilor la întrebările de examen din anii precedenți. Chiar dacă Ellie ar fi înzestrată cu o memorie extraordinară și, prin urmare, ar putea reproduce perfect răspunsul la orice întrebare văzută anterior, ea ar putea totuși să se blocheze atunci când se confruntă cu o întrebare nouă (nevăzută anterior). Prin comparație, imaginați-vă o altă studentă, Irene Inductiva, cu abilități de memorare comparabil de slabe, dar cu un talent pentru a sesiza tipare. Rețineți că, dacă examenul ar consta într-adevăr din întrebări reciclate dintr-un an precedent, Ellie ar depăși-o cu ușurință pe Irene. Chiar dacă tiparele deduse de Irene ar produce predicții corecte în proporție de 90%, acestea nu ar putea concura niciodată cu reamintirea de 100% a lui Ellie. Totuși, chiar dacă examenul ar consta în întregime din întrebări noi, Irene și-ar putea menține media de 90%.

Ca specialiști în machine learning, scopul nostru este să descoperim tipare (patterns). Dar cum putem fi siguri că am descoperit cu adevărat un tipar general și nu am memorat pur și simplu datele noastre? De cele mai multe ori, predicțiile noastre sunt utile doar dacă modelul nostru descoperă un astfel de tipar. Nu vrem să prezicem prețurile acțiunilor de ieri, ci pe cele de mâine. Nu avem nevoie să recunoaștem boli deja diagnosticate pentru pacienții văzuți anterior, ci mai degrabă afecțiuni nediagnosticate anterior la pacienți nevăzuți anterior. Această problemă — cum să descoperim tipare care generalizează — este problema fundamentală a machine learning-ului și, probabil, a întregii statistici. Am putea privi această problemă ca fiind doar o parte a unei întrebări mult mai vaste care cuprinde întreaga știință: când suntem vreodată îndreptățiți să facem saltul de la observații particulare la afirmații mai generale?

În viața reală, trebuie să ne potrivim modelele folosind o colecție finită de date. Scările tipice ale acestor date variază enorm de la un domeniu la alt unskilled. Pentru multe probleme medicale importante, putem accesa doar câteva mii de puncte de date. Când studiem boli rare, am putea fi norocoși să accesăm sute. În schimb, cele mai mari seturi de date publice constând din fotografii etichetate, de exemplu ImageNet ¹⁾, conțin milioane de imagini. Și unele colecții de imagini neetichetate, cum ar fi setul de date Flickr YFC100M, pot fi chiar mai mari, conținând peste 100 de milioane de imagini ²⁾. Cu toate acestea, chiar și la această scară extremă, numărul de puncte de date disponibile rămâne infinitezimal de mic în comparație cu spațiul tuturor imaginilor posibile la o rezoluție de un megapixel. Ori de câte ori lucrăm cu eșantioane finite, trebuie să avem în vedere riscul de a potrivi datele noastre de antrenament, doar pentru a descoperi că nu am reușit să descoperim un tipar generalizabil.

Fenomenul de a se potrivi mai bine pe datele noastre de antrenament decât pe distribuția subiacentă se numește supra-ajustare (overfitting), iar tehnicile pentru combaterea supra-ajustării sunt adesea numite metode de regularizare. Deși nu este un substitut pentru o introducere adecvată în teoria învățării statistice (vezi ³⁾), vă vom oferi suficientă intuiție pentru a începe. Vom reveni la generalizare în multe capitole de-a lungul cărții, explorând atât ceea ce se știe despre principiile care stau la baza generalizării în diverse modele, cât și tehnici euristice care s-au dovedit (empiric) că sporesc generalizarea în sarcinile de interes practic.

În cadrul standard de învățare supervizată, presupunem că datele de antrenament și datele de test sunt extrase independent din distribuții identice. Aceasta este numită în mod obișnuit ipoteza IID (Independent and Identically Distributed). Deși această ipoteză este puternică, merită menționat faptul că, în absența unei astfel de ipoteze, am fi într-un impas. De ce ar trebui să credem că datele de antrenament eșantionate din distribuția $P(X,Y)$ ar trebui să ne spună cum să facem predicții pe datele de test generate de o distribuție diferită $Q(X,Y)$? Realizarea unor astfel de salturi se dovedește a necesita ipoteze puternice despre modul în care $P$ și $Q$ sunt legate. Mai târziu vom discuta despre unele ipoteze care permit schimbări în distribuție, dar mai întâi trebuie să înțelegem cazul IID, unde $P(\cdot) = Q(\cdot)$.

Pentru început, trebuie să diferențiem între eroarea de antrenament $R_\textrm{emp}$, care este o statistică calculată pe setul de date de antrenament, și eroarea de generalizare $R$, care este o speranță matematică (expectation) luată în raport cu distribuția subiacentă. Vă puteți gândi la eroarea de generalizare ca fiind ceea ce ați vedea dacă ați aplica modelul dumneavoastră unui flux infinit de exemple de date suplimentare extrase din aceeași distribuție subiacentă de date. Formal, eroarea de antrenament este exprimată ca o sumă (cu aceeași notație ca în ):

$$R_\textrm{emp}[\mathbf{X}, \mathbf{y}, f] = \frac{1}{n} \sum_{i=1}^n l(\mathbf{x}^{(i)}, y^{(i)}, f(\mathbf{x}^{(i)})),$$

în timp ce eroarea de generalizare este exprimată ca o integrală:

$$R[p, f] = E_{(\mathbf{x}, y) \sim P} [l(\mathbf{x}, y, f(\mathbf{x}))] = \int \int l(\mathbf{x}, y, f(\mathbf{x})) p(\mathbf{x}, y) \;d\mathbf{x} dy.$$

Problematica este că nu putem calcula niciodată exact eroarea de generalizare $R$. Nimeni nu ne spune vreodată forma precisă a funcției de densitate $p(\mathbf{x}, y)$. Mai mult, nu putem eșantiona un flux infinit de puncte de date. Astfel, în practică, trebuie să estimăm eroarea de generalizare aplicând modelul nostru pe un set de test independent, constituit dintr-o selecție aleatorie de exemple $\mathbf{X}'$ și etichete $\mathbf{y}'$ care au fost reținute din setul nostru de antrenament. Aceasta constă în aplicarea aceleiași formule care a fost utilizată pentru calcularea erorii de antrenament empirice, dar pe un set de test $\mathbf{X}', \mathbf{y}'$.

În mod crucial, atunci când evaluăm clasificatorul nostru pe setul de test, lucrăm cu un clasificator fix (nu depinde de eșantionul setului de test) și, prin urmare, estimarea erorii sale este pur și simplu o problemă de estimare a mediei. Totuși, același lucru nu se poate spune despre setul de antrenament. Rețineți că modelul cu care ajungem depinde explicit de selecția setului de antrenament și, prin urmare, eroarea de antrenament va fi, în general, o estimare părtinitoare (biased estimate) a erorii reale pe populația subiacentă. Întrebarea centrală a generalizării este atunci când ar trebui să ne așteptăm ca eroarea noastră de antrenament să fie aproape de eroarea populației (și, prin urmare, de eroarea de generalizare).

În teoria clasică, atunci când avem modele simple și date abundente, erorile de antrenament și de generalizare tind să fie apropiate. Cu toate acestea, când lucrăm cu modele mai complexe și/sau mai puține exemple, ne așteptăm ca eroarea de antrenament să scadă, dar decalajul de generalizare (generalization gap) să crească. Acest lucru nu ar trebui să fie surprinzător. Imaginați-vă o clasă de modele atât de expresivă încât pentru orice set de date de $n$ exemple, putem găsi un set de parametri care se pot potrivi perfect pe etichete arbitrare, chiar dacă sunt atribuite aleatoriu. În acest caz, chiar dacă potrivim perfect datele noastre de antrenament, cum putem concluziona ceva despre eroarea de generalizare? Din câte știm, eroarea noastră de generalizare ar putea fi la fel ca o ghicire aleatorie.

În general, în absența oricărei restricții asupra clasei noastre de modele, nu putem concluziona, bazându-ne doar pe potrivirea datelor de antrenament, că modelul nostru a descoperit vreun tipar generalizabil ⁴⁾. Pe de altă parte, dacă clasa noastră de modele nu a fost capabilă să se potrivească pe etichete arbitrare, atunci trebuie să fi descoperit un tipar. Ideile teoretice despre complexitatea modelului au derivat o anumită inspirație din ideile lui Karl Popper, un influent filosof al științei, care a oficializat criteriul falsificabilității. Potrivit lui Popper, o teorie care poate explica orice observație nu este deloc o teorie științifică! La urma urmei, ce ne-a spus ea despre lume dacă nu a exclus nicio posibilitate? Pe scurt, ceea ce ne dorim este o ipoteză care nu ar putea explica orice observație pe care am putea-o face și care totuși se întâmplă să fie compatibilă cu acele observații pe care le facem de fapt.

Acum, ceea ce constituie cu exactitate o noțiune adecvată a complexității modelului este o chestiune complexă. Adesea, modelele cu mai mulți parametri sunt capabile să se potrivească pe un număr mai mare de etichete atribuite arbitrar. Totuși, acest lucru nu este neapărat adevărat. De exemplu, metodele kernel operează în spații cu un număr infinit de parametri, dar complexitatea lor este controlată prin alte mijloace ⁵⁾. O noțiune de complexitate care se dovedește adesea utilă este gama de valori pe care le pot lua parametrii. Aici, un model ai cărui parametri au voie să ia valori arbitrare ar fi mai complex. Vom reveni la această idee în secțiunea următoare, când vom introduce weight decay (decăderea ponderilor), prima dumneavoastră tehnică practică de regularizare. În mod special, poate fi dificil să compari complexitatea între membri ai unor clase de modele substanțial diferite (de exemplu, arbori de decizie vs. rețele neuronale).

În acest punct, trebuie să subliniem un alt punct important la care vom reveni când vom introduce rețelele neuronale profunde. Atunci când un model este capabil să se potrivească pe etichete arbitrare, eroarea de antrenament scăzută nu implică neapărat o eroare de generalizare scăzută. Cu toate acestea, nici nu implică neapărat o eroare de generalizare ridicată! Tot ceea ce putem spune cu certitudine este că eroarea de antrenament scăzută singură nu este suficientă pentru a certifica o eroare de generalizare scăzută. Rețelele neuronale profunde se dovedesc a fi tocmai astfel de modele: deși generalizează bine în practică, ele sunt prea puternice pentru a ne permite să concluzionăm prea multe doar pe baza erorii de antrenament. În aceste cazuri, trebuie să ne bazăm mai mult pe datele noastre reținute (holdout data) pentru a certifica generalizarea post-factum. Eroarea pe datele reținute, adică setul de validare, se numește eroare de validare.

Când comparăm erorile de antrenament și de validare, vrem să avem în vedere două situații comune. Mai întâi, vrem să fim atenți la cazurile în care eroarea de antrenament și eroarea de validare sunt amândouă substanțiale, dar există un decalaj mic între ele. Dacă modelul nu este capabil să reducă eroarea de antrenament, asta ar putea însemna că modelul nostru este prea simplu (adică insuficient de expresiv) pentru a surprinde tiparul pe care încercăm să îl modelăm. Mai mult, deoarece decalajul de generalizare ($R_\textrm{emp} - R$) între erorile noastre de antrenament și de generalizare este mic, avem motive să credem că am putea scăpa cu un model mai complex. Acest fenomen este cunoscut sub numele de sub-ajustare (underfitting).

Pe de altă parte, așa cum am discutat mai sus, vrem să fim atenți la cazurile în care eroarea noastră de antrenament este semnificativ mai mică decât eroarea noastră de validare, indicând o supra-ajustare severă. Rețineți că supra-ajustarea nu este întotdeauna un lucru rău. În special în deep learning, cele mai bune modele predictive funcționează adesea mult mai bine pe datele de antrenament decât pe datele reținute. În cele din urmă, de obicei ne pasă de reducerea erorii de generalizare și ne pasă de decalaj doar în măsura în care acesta devine un obstacol în acest scop. Rețineți că, dacă eroarea de antrenament este zero, atunci decalajul de generalizare este exact egal cu eroarea de generalizare și putem face progrese doar prin reducerea decalajului.

Pentru a ilustra o anumită intuiție clasică despre supra-ajustare și complexitatea modelului, luați în considerare următoarele: având în vedere datele de antrenament constând dintr-o singură caracteristică $x$ și o etichetă corespunzătoare cu valoare reală $y$, încercăm să găsim polinomul de grad $d$

$$\hat{y}= \sum_{i=0}^d x^i w_i$$

pentru estimarea etichetei $y$. Aceasta este doar o problemă de regresie liniară în care caracteristicile noastre sunt date de puterile lui $x$, ponderile modelului sunt date de $w_i$, iar biasul este dat de $w_0$ deoarece $x^0 = 1$ pentru orice $x$. Deoarece aceasta este doar o problemă de regresie liniară, putem folosi eroarea pătratică ca funcție de pierdere.

O funcție polinomială de ordin superior este mai complexă decât o funcție polinomială de ordin inferior, deoarece polinomul de ordin superior are mai mulți parametri, iar gama de selecție a funcției modelului este mai largă. Fixând setul de date de antrenament, funcțiile polinomiale de ordin superior ar trebui să obțină întotdeauna o eroare de antrenament mai mică (în cel mai rău caz, egală) în raport cu polinoamele de grad mai mic. De fapt, ori de câte ori fiecare exemplu de date are o valoare distinctă a lui $x$, o funcție polinomială cu un grad egal cu numărul de exemple de date poate potrivi perfect setul de antrenament. Comparăm relația dintre gradul polinomului (complexitatea modelului) și ambele, sub-ajustarea și supra-ajustarea, în .

Așa cum indică deja limita de mai sus, un alt considerent important de reținut este dimensiunea setului de date. Fixând modelul nostru, cu cât avem mai puține eșantioane în setul de date de antrenament, cu atât este mai probabil (și mai sever) să întâlnim supra-ajustare. Pe măsură ce creștem cantitatea de date de antrenament, eroarea de generalizare scade de obicei. Mai mult, în general, mai multe date nu strică niciodată. Pentru o sarcină fixă și o distribuție a datelor, complexitatea modelului nu ar trebui să crească mai rapid decât cantitatea de date. Având mai multe date, am putea încerca să potrivim un model mai complex. În absența datelor suficiente, modelele mai simple pot fi mai greu de depășit. Pentru multe sarcini, deep learning depășește modelele liniare numai atunci când sunt disponibile mii de exemple de antrenament. În parte, succesul actual al deep learning-ului se datorează considerabil abundenței seturilor de date masive care provin de la companiile de Internet, stocării ieftine, dispozitivelor conectate și digitalizării ample a economiei.

De obicei, ne selectăm modelul final numai după evaluarea mai multor modele care diferă în diverse moduri (arhitecturi diferite, obiective de antrenament, caracteristici selectate, preprocesarea datelor, rate de învățare etc.). Alegerea dintre mai multe modele este numită pe bună dreptate selecția modelului.

În principiu, nu ar trebui să atingem setul nostru de test până când nu am ales toți hiperparametrii noștri. Dacă am folosi datele de test în procesul de selecție a modelului, există riscul să supra-ajustăm datele de test. Atunci am fi într-o mare problemă. Dacă supra-ajustăm datele noastre de antrenament, există întotdeauna evaluarea pe datele de test care să ne mențină onești. Dar dacă supra-ajustăm datele de test, cum am putea ști vreodată? Vezi ⁶⁾ pentru un exemplu despre modul în care acest lucru poate duce la rezultate absurde chiar și pentru modelele în care complexitatea poate fi controlată strâns.

Astfel, nu ar trebui să ne bazăm niciodată pe datele de test pentru selecția modelului. Și totuși, nu ne putem baza nici doar pe datele de antrenament pentru selecția modelului, deoarece nu putem estima eroarea de generalizare pe chiar datele pe care le folosim pentru a antrena modelul.

În aplicațiile practice, imaginea devine mai tulbure. Deși în mod ideal am atinge datele de test o singură dată, pentru a evalua cel mai bun model sau pentru a compara un număr mic de modele între ele, datele de test din lumea reală sunt rareori eliminate după o singură utilizare. Rareori ne putem permite un nou set de test pentru fiecare rundă de experimente. De fapt, reciclarea datelor benchmark timp de decenii poate avea un impact semnificativ asupra dezvoltării algoritmilor, de exemplu pentru clasificarea imaginilor și recunoașterea optică a caracterelor.

Practica obișnuită pentru abordarea problemei antrenării pe setul de test este de a împărți datele noastre în trei căi, încorporând un set de validare în plus față de seturile de date de antrenament și de test. Rezultatul este o afacere tulbure în care granițele dintre datele de validare și cele de test sunt îngrijorător de ambigue. Cu excepția cazului în care se specifică altfel, în experimentele din această carte lucrăm de fapt cu ceea ce ar trebui să se numească pe bună dreptate date de antrenament și date de validare, fără seturi de test reale. Prin urmare, acuratețea raportată în fiecare experiment al cărții este de fapt acuratețea de validare și nu o acuratețe reală a setului de test.

Când datele de antrenament sunt puține, s-ar putea să nu ne putem permite nici măcar să reținem suficiente date pentru a constitui un set de validare adecvat. O soluție populară la această problemă este utilizarea validării încrucișate cu $K$ straturi ($K$-fold cross-validation). Aici, datele de antrenament originale sunt împărțite în $K$ subseturi care nu se suprapun. Apoi, antrenarea și validarea modelului sunt executate de $K$ ori, de fiecare dată antrenând pe $K-1$ subseturi și validând pe un subset diferit (cel nefolosit pentru antrenare în acea rundă). În cele din urmă, erorile de antrenament și de validare sunt estimate prin calcularea mediei rezultatelor din cele $K$ experimente.

Această secțiune a explorat unele dintre fundamentele generalizării în machine learning. Unele dintre aceste idei devin complicate și contra-intuitive atunci când ajungem la modele mai profunde; aici, modelele sunt capabile să supra-ajusteze datele în mod serios, iar noțiunile relevante de complexitate pot fi atât implicite, cât și contra-intuitive (de exemplu, arhitecturi mai mari cu mai mulți parametri generalizând mai bine). Vă lăsăm cu câteva reguli de bază:

1. Utilizați seturi de validare (sau validarea încrucișată cu $K$ straturi) pentru selecția modelului;
2. Modelele mai complexe necesită adesea mai multe date;
3. Noțiunile relevante de complexitate includ atât numărul de parametri, cât și gama de valori pe care aceștia au voie să le ia;
4. Păstrând toate celelalte elemente egale, mai multe date conduc aproape întotdeauna la o generalizare mai bună;
5. Toată această discuție despre generalizare este bazată pe ipoteza IID. Dacă relaxăm această ipoteză, permițând distribuțiilor să se schimbe între perioadele de antrenament și de testare, atunci nu putem spune nimic despre generalizare în absența unei ipoteze suplimentare (poate mai blânde).

1. Când puteți rezolva exact problema regresiei polinomiale?
2. Oferiți cel puțin cinci exemple în care variabilele aleatorii dependente fac ca tratarea problemei ca date IID să fie neindicată.
3. Vă puteți aștepta vreodată să vedeți o eroare de antrenament zero? În ce circumstanțe ați vedea o eroare de generalizare zero?
4. De ce este validarea încrucișată cu $K$ straturi foarte costisitoare de calculat?
5. De ce este părtinitoare estimarea erorii prin validarea încrucișată cu $K$ straturi?
6. Dimensiunea VC este definită ca numărul maxim de puncte care pot fi clasificate cu etichete arbitrare $\{\pm 1\}$ de o funcție dintr-o clasă de funcții. De ce s-ar putea ca aceasta să nu fie o idee bună pentru măsurarea complexității clasei de funcții? Sugestie: luați în considerare magnitudinea funcțiilor.
7. Managerul dumneavoastră vă dă un set de date dificil pe care algoritmul dumneavoastră actual nu funcționează atât de bine. Cum i-ați justifica faptul că aveți nevoie de mai multe date? Sugestie: nu puteți crește datele, dar le puteți reduce.

Discuții