Principiul lungimii minime a descrierii

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 12 martie 2021; verificarea necesită 1 editare .

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] .

Prezentare generală

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” : $D$ $H$ ${\cal {H}}$ $D$ $H$ $H$

{L(D)}=\min _{H\in {\cal {H))}\ (\ L(H)+L(D|H)\ )\

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 . $H$ $D$ $D$ $D=(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$ ${\cal {H}}$ $X$ $Y$ $H$ $k$ $k$ $k+1$ $L(H)$ $D$ $n$ $y_{i}-H(x_{i})$

Î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. $H$ $X$ $Y$ $H(X)$ $\sigma ^{2}$ ${\cal {H}}$ $Y=H(X)+\epsilon$ $H$

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. ${\cal {H}}$ ${\cal {H}}=\{{\cal {H}}_{0}, {\cal {H}}_{1},\ldots \}$ ${\cal {H}}_{j}$ $D$ ${\cal {H}}_{j}$ $H\in {\cal {H}}_{j}$ $L(D|H)$

MDL versus teoria inferenței lui Solomon

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.

Concluzie

Cu toate acestea, această teorie matematică nu oferă o metodă practică pentru obținerea unei concluzii. Cele mai importante motive pentru aceasta sunt:

Complexitatea Kolmogorov nu este calculabilă - nu există un algoritm care, având în vedere o secvență arbitrară de date, să producă cel mai scurt program care reproduce datele.
Complexitatea lui Kolmogorov depinde de limbajul de calculator folosit. Alegerea limbajului este arbitrară, dar afectează complexitatea printr-o constantă suplimentară. Din acest motiv, constanta din teoria complexității Kolmogorov este aruncată. În practică, totuși, este disponibilă doar o cantitate mică de date, astfel încât constantele pot avea un impact foarte mare asupra rezultatelor rezultate - rezultate bune nu sunt garantate atunci când se lucrează cu un set limitat de date.

MDL încearcă să combată această problemă prin:

Restricționarea setului de coduri permise astfel încât să devină posibilă (din punct de vedere computațional) să se găsească cea mai mică lungime de cod pentru date conform codurilor permise.
Selectarea codurilor care sunt rezonabil de eficiente indiferent de date. Ideea de „eficiență rezonabilă” se reflectă în ideea de „cod universal”.

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] .

Exemplu MDL

Moneda este aruncată de 1000 de ori și se înregistrează numărul de capete sau cozi. Luați în considerare două clase de modele:

Primul este un cod care scrie 0 pentru capete și 1 pentru cozi. Acest cod reprezintă ipoteza că moneda este simetrică (adică capul și cozile trebuie să fie la fel de probabile). Lungimea codului, conform acestei codificări, este întotdeauna exact 1000 de biți.
Al doilea constă din toate codurile care sunt eficiente pentru o monedă deformată și reprezintă ipoteza că moneda este denaturată. Să presupunem că vedem 510 capete și 490 de cozi. Apoi lungimea codului corespunzătoare celei mai bune codări din clasa a doua de modele este mai mică de 1000 de biți.

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.

Denumirea MDL

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. $P$ $C$ $C(x)$ $-\log _{2}P(x)$ $C$ $P$

Concepte înrudite

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] .

Alte sisteme

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:

MML este o abordare bayesiană complet subiectivă - începe cu ideea că există o anumită credință despre procesul de obținere a datelor sub forma unei distribuții prealabile. Principiul MDL evită orice presupunere cu privire la procesul de achiziție a datelor.
Ambele metode folosesc coduri din două părți - o parte reprezintă întotdeauna informațiile pe care încearcă să le antreneze, cum ar fi indexul modelului de clasă (în selecția modelului ) sau valorile parametrilor (în evaluarea parametrilor ). A doua parte conține date codificate conform informațiilor din prima parte. Diferența de metode este că literatura MDL recomandă introducerea parametrilor nedoriți în a doua parte a codului, unde aceștia pot fi reprezentați cu date folosind așa-numitul cod dintr-o singură parte , care este adesea mai eficient decât în două părți. cod. În descrierea MML originală, toți parametrii sunt codificați în prima parte, astfel încât toți parametrii sunt antrenați.
În schema MML, fiecare parametru este setat exact în poziția care are ca rezultat lungimea optimă a mesajului - exemplul dat s-ar întâmpla dacă unii parametri ar fi considerat inițial „posibil utili” pentru model, dar ulterior s-ar fi dovedit a fi incapabili. pentru a ajuta la explicarea datelor. Schema MDL se concentrează mai mult pe compararea claselor de model decât a modelelor în sine și este mai natural să puneți aceeași întrebare prin compararea claselor de model decât să includeți în mod explicit un astfel de parametru într-o clasă și să-l lăsați deoparte.

Vezi și

Note

↑ Rissanen, 1978 , p. 465–658.
↑ Lungimea minimă a descrierii (downlink) . Universitatea din Helsinki . Preluat la 3 iulie 2010. Arhivat din original pe 18 februarie 2010. (nedefinit)
↑ 1 2 Grünwald, 2007 .
↑ Grünwald, Myung, Pitt, 2005 .
↑ Grünwald, 2004 .
↑ MacKay, 2003 .
↑ Rissanen, Jorma . Pagina de pornire a lui Jorma Rissanen . Arhivat din original pe 10 decembrie 2015. Preluat la 3 iulie 2010.
↑ Rissanen, 2007 .
↑ Nannen, 2010 .

Literatură

Rissanen J. Modelare după cea mai scurtă descriere a datelor // Automatica. - 1978. - T. 14 , nr. 5 . - doi : 10.1016/0005-1098(78)90005-5 .
Peter D. Grunwald. principiul lungimii minime de descriere. — Cambridge, Massachusetts; Londra, Anglia: MIT Press , 2007. - ISBN 978-0-262-07281-6 .
Progrese în lungimea minimă a descrierii: teorie și aplicații / Peter D. Grünwald, În Jae Myung, Mark A. Pitt. — Cambridge, Massachusetts; Londra, Anglia: MIT Press , 2005. - (Neural Information Processing). — ISBN 0-262-07262-9 .

Peter Grunwald. [1] . — 2004.
Rissanen J. Information and Complexity in Statistical Modeling . - Springer, 2007. - (Information Science and Statistics). - ISBN 0-387-36610-5 .
Volker Nannen. O scurtă introducere la selecția modelului, complexitatea Kolmogorov și lungimea minimă a descrierii // preprint. — 2010.
David Mackay. Teoria informațiilor, inferență și algoritmi de învățare . — Cambridge University Press , 2003.

Lectură pentru lecturi suplimentare

Lungimea minimă a descrierii pe web , de la Universitatea din Helsinki. Conține lecturi, demonstrații, evenimente și link-uri către cercetătorii MDL.
Pagina de pornire a lui Jorma Rissanen , care conține note de curs și alte materiale recente despre MDL.
Progrese în lungimea minimă a descrierii , MIT Press , ISBN 0-262-07262-9 .

Cele mai mici pătrate și analiza de regresie

Statistica de calcul

Metoda celor mai mici pătrate
MNC liniar
Cele mai mici pătrate neliniare
LSM cu recalcularea iterativă a greutăților

Corelație
și dependență

Coeficientul de corelație Pearson
Corelația rangului ( Spearman
Kendall )
Corelație parțială
Factorul de distorsionare

Analiza regresiei

MNC obișnuit
Metoda celor mai mici pătrate parțiale
Cele mai mici pătrate pline
Regresia crestei

Regresia ca model
statistic

Regresie liniara	Regresia liniară simplă MNC obișnuit Cele mai mici pătrate generalizate Cele mai mici pătrate ponderate Model liniar de bază
cadru predictiv	Regresia polinomială curba de crestere Regresia segmentată Regresia locală
Regresie personalizată	neliniară Neparametric semiparametrică durabil cuantilă izotonic
Erori non-standard	Model liniar generalizat Regresie binomială Regresia Poisson Regresie logistică

Descompunerea varianței

Analiza variatiei
Analiza covarianței
Analiza multivariată a varianței

Studiu model

C p Nalbi
Regresie în trepte
Alegerea unui model statistic
Validarea modelului de regresie

Cerințe preliminare

Răspuns mediu și așteptat
Teorema Gauss-Markov
Erori și abateri
Test statistic
Echilibrul studentizat
Eroare pătratică medie minimă

Planificarea
experimentului

Metodologia suprafeței de răspuns
Design optim al experimentului
Proiectare Bayesian Experiment

Aproximație numerică

Aplicații

Aproximare folosind curbe
Curba de calibrare
Filtrul Savitsky-Golay
Identificarea sistemului
Metoda deplasării celor mai mici pătrate