Principiul lungimii minime a descrierii ( MDL ) este o formalizare a aparatului de ras Occam , în care cea mai bună ipoteză (modelul și parametrii acestuia) pentru un anumit set de date este cea care duce la o mai bună comprimare a datelor . Principiul MDL a fost propus de Jorma Rissanen în 1978 [1] . Principiul este un concept important în teoria informației și teoria învățării computaționale [2] [3] [4] .
Orice set de date poate fi reprezentat ca un șir de caractere dintr-un alfabet finit (să zicem, binar ) .
[Principiul MDL] se bazează pe următoarea realizare: orice model dintr-un anumit set de date poate fi utilizat pentru a comprima datele , adică pentru a descrie datele folosind un set de caractere mai mic decât este necesar pentru a descrie datele la propriu. (Grunwald, 1998) [5]
MDL este o teorie a inferenței și inferenței statistice care pornește de la ideea că toată învățarea statistică este despre descoperirea tiparelor în date, iar cea mai bună ipoteză pentru descrierea tiparelor în date este cea care comprimă cel mai mult datele. Similar altor metode statistice, principiul poate fi folosit pentru a antrena parametrii modelului folosind unele date. Deși, de obicei, metodele statistice standard presupun că forma generală a modelului este fixă. Principalul punct forte al principiului MDL este că poate fi utilizat pentru a selecta aspectul general al unui model și parametrii acestuia. O caracteristică cantitativă (uneori doar modelul, alteori doar parametrii, alteori atât modelul, cât și parametrii) se numește ipoteză. Ideea de bază este de a lua în considerare un cod în două etape (fără pierderi) care codifică datele prin codificarea mai întâi a ipotezei în setul de ipoteze luate în considerare și apoi codificarea „cu” . În contextul său cel mai simplu, aceasta înseamnă pur și simplu „codificarea abaterii datelor de la predicția obținută de” :
Ipoteza pe baza căreia se atinge minimul este atunci considerată cea mai bună explicație pentru date . Ca exemplu simplu, luați în considerare o problemă de regresie: să fie datele formate dintr-o succesiune de puncte , să fie mulțimea tuturor polinoamelor de la până la . Pentru a descrie un polinom de grad (să zicem) , trebuie mai întâi să discretizezi parametrii cu o anumită precizie, apoi trebuie să descriem această precizie ( un număr natural ). Apoi ar trebui să descriem gradul (un alt număr natural) și, în final, ar trebui să descriem parametrii. Lungimea totală va fi de . Apoi descriem punctele în utilizarea unui cod fix pentru valorile x și apoi folosirea unui cod pentru variații .
În practică, un model statistic este adesea folosit (dar nu întotdeauna) . De exemplu, asociați fiecare polinom cu distribuția condiționată corespunzătoare, indicând astfel că datele sunt distribuite în mod normal cu o medie și o anumită varianță , care pot fi fie fixate, fie adăugate ca parametri. Apoi setul de ipoteze este redus la un model liniar cu forma unui polinom.
Mai mult decât atât, adesea valorile specifice ale parametrilor nu sunt direct interesante, ci doar, de exemplu, gradul polinomului este interesant. În acest caz, mulțimea este setată egală cu , unde fiecare element reprezintă ipoteza că datele sunt cel mai bine descrise printr-un polinom de gradul j. Apoi codificați datele ipotezei date cu un cod dintr-o singură parte conceput astfel încât atunci când o ipoteză se potrivește bine datelor, codul este scurt. Dezvoltarea unor astfel de coduri se numește codare universală . Există diferite tipuri de coduri universale care pot fi utilizate, oferind adesea lungimi similare pentru secvențele lungi de date, dar diferite pentru secvențele scurte. Cele mai bune coduri (în sensul că au proprietatea de optimitate minimax) sunt coduri de maximă probabilitate normalizate (NML) sau coduri Shtarkov . O clasă foarte utilă de coduri sunt codurile bayesiene de probabilitate marginală. Pentru o familie de distribuții exponențiale, atunci când este utilizat priorul Jeffreys și spațiul parametrilor este constrâns corespunzător, acestea sunt asimptotic la fel ca codurile NML. Acest lucru aduce teoria MDL mai aproape de selecția obiectivă a modelului bayesian, căruia i se aplică uneori și priorul Jeffreys, deși din motive diferite.
Pentru a selecta ipoteza care surprinde cea mai mare regularitate în date, oamenii de știință caută ipoteza care oferă cea mai bună compresie. Pentru a face acest lucru, codul de compresie a datelor este fix. Poate că cel mai comun cod care poate fi folosit este un limbaj de computer ( complet Turing ) . Programul de ieșire este scris în acest limbaj. Apoi programul prezintă în mod eficient datele. Lungimea celui mai scurt program care scoate date se numește complexitatea Kolmogorov a datelor. Aceasta este ideea centrală a teoriei idealizate a inferenței a lui Ray Solomon , care este inspirația pentru MDL.
Cu toate acestea, această teorie matematică nu oferă o metodă practică pentru obținerea unei concluzii. Cele mai importante motive pentru aceasta sunt:
MDL încearcă să combată această problemă prin:
Una dintre cele mai importante proprietăți ale metodelor MDL este că oferă o protecție naturală împotriva supraajustării , deoarece implementează un compromis între complexitatea ipotezei (clasa de model) și complexitatea datelor [3] .
Moneda este aruncată de 1000 de ori și se înregistrează numărul de capete sau cozi. Luați în considerare două clase de modele:
Din acest motiv, o metodă statistică naivă poate alege al doilea model ca cea mai bună explicație pentru date. Cu toate acestea, abordarea MDL ar construi un cod bazat pe ipoteză în loc să folosească cel mai bun cod. Acest cod ar putea fi un cod de probabilitate maximă normalizată sau un cod bayesian. Dacă se folosește un astfel de cod, lungimea totală a codului bazat pe a doua clasă de modele ar fi mai mare de 1000 de biți. Prin urmare, concluzia care decurge inevitabil din abordarea MDL este că nu există suficiente dovezi pentru ipoteza monedei oblice, chiar dacă cel mai bun element din clasa a doua de modele oferă o potrivire mai bună datelor.
Esențial pentru teoria MDL este corespondența unu-la-unu dintre lungimile codului de funcție și distribuțiile de probabilitate (aceasta rezultă din inegalitatea Kraft-McMillan ). Pentru orice distribuție de probabilitate, puteți construi un cod astfel încât lungimea (în biți) să fie . Acest cod minimizează lungimea așteptată a codului. În schimb, dacă este dat un cod , se poate construi o distribuție de probabilitate astfel încât afirmația de mai sus să fie valabilă. ( Problemele de rotunjire sunt ignorate aici.) Cu alte cuvinte, găsirea unui cod eficient este echivalentă cu găsirea unei distribuții de probabilitate bune.
Principiul MDL este strâns legat de teoria și statistica probabilității prin potrivirea codului și distribuția probabilității menționate mai sus. Acest lucru i-a determinat pe unii cercetători la concluzia că principiul MDL este echivalent cu inferența bayesiană - lungimea codului modelului și datele din MDL corespund probabilității anterioare și probabilității marginale în schema bayesiană [6] .
În timp ce algoritmii bayesieni sunt adesea utili pentru construirea de coduri MDL eficiente, principiul MDL găzduiește și alte coduri non-bayesiene. Un exemplu este codul de probabilitate maximă normalizat al lui Starkov , care joacă un rol central în teoria actuală a MDL, dar nu are echivalent în inferența bayesiană. Mai mult, Rissanen subliniază că nu ar trebui să facem nicio presupunere cu privire la corectitudinea procesului de achiziție a datelor - în practică, o clasă de modele este de obicei o simplificare a realității și, prin urmare, nu conține coduri sau distribuții de probabilitate care sunt adevărate într-un obiectiv. sens [7] [8] . În ultima verigă, Rissanen aduce fundamentul matematic al principiului MDL la funcția de structură Kolmogorov .
Conform filozofiei MDL, metodele bayesiene ar trebui evitate dacă se bazează pe o probabilitate anterioară nesigură , ceea ce poate duce la rezultate slabe. Condițiile a priori acceptabile din punctul de vedere al MDL sunt de asemenea preferabile așa-numitei analize obiective bayesiene . Aici, însă, motivele sunt de obicei diferite [9] .
MDL nu a fost prima abordare de învățare teoretică informațională. În 1968, Wallace și Bolton au introdus un concept înrudit numit lungimea minimă a mesajului ( MML) . Diferența dintre MDL și MML este o sursă de confuzie constantă. Pe plan extern, metodele par a fi în mare parte echivalente, dar există unele diferențe semnificative, în special în interpretare:
Cele mai mici pătrate și analiza de regresie | |||||||||
---|---|---|---|---|---|---|---|---|---|
Statistica de calcul |
| ||||||||
Corelație și dependență |
| ||||||||
Analiza regresiei |
| ||||||||
Regresia ca model statistic |
| ||||||||
Descompunerea varianței |
| ||||||||
Studiu model |
| ||||||||
Cerințe preliminare |
| ||||||||
Planificarea experimentului |
| ||||||||
Aproximație numerică | |||||||||
Aplicații |
|