Minima lunghezza di descrizione

Il principio della minima lunghezza di descrizione (MLD) (in inglese minimum description length [MDL] principle) è una formalizzazione del Rasoio di Occam nella quale la migliore ipotesi per un determinato insieme di dati è quella che conduce alla migliore compressione dei dati. La MLD fu introdotta da Jorma Rissanen nel 1978.^[1] È un importante concetto nella teoria dell'informazione e nella teoria dell'apprendimento.^[2][3][4]

Panoramica

Qualunque insieme di dati può essere rappresentato da una stringa di simboli da un alfabeto finito (diciamo, binario).

[Il principio della MLD] si basa sulla seguente intuizione: qualsiasi regolarità in un determinato insieme di dati può essere usata per comprimere i dati, cioè per descriverlo usando meno simboli di quanto richiesti per descrivere i dati letteralmente". (Grünwald, 1998)^[5]

Per selezionare l'ipotesi che cattura la maggior parte della regolarità nei dati, gli scienziati cercano l'ipotesi con la quale si può raggiungere la migliore compressione. Per fare questo, si fissa un codice per comprimere i dati, più generalmente con un linguaggio informatico (Turing equivalente). Un programma per produrre i dati è scritto in quel linguaggio; pertanto il programma rappresenta efficacemente i dati. La lunghezza del programma più breve che produce i dati si chiama complessità di Kolmogorov dei dati. Questa è l'idea centrale della teoria idealizzata dell'inferenza induttiva di Ray Solomonoff.

Inferenza

Tuttavia, questa teoria matematica non fornisce un modo pratico di raggiungere un'inferenza. Le ragioni più importanti di questo sono:

• la complessità di Kolmogorov è incalcolabile: non esiste alcun algoritmo che, quando si inserisce una sequenza arbitraria di dati, produca il più breve programma che produce i dati.
• la complessità di Kolmogorov dipende da quale linguaggio di programmazione si usa. Questa è una scelta arbitraria, ma influenza davvero la complessità fino a qualche termine additivo costante. Per quella ragione, i termini costanti tendono ad essere trascurati nella teoria della complessità di Kolmogorov. In pratica, tuttavia, dove spesso è disponibile solo una piccola quantità di dati, tali costanti possono avere una grandissima influenza sui risultati dell'inferenza: i buoni risultati non possono essere garantiti quando si sta lavorando con dati limitati.

L'MLD tenta di rimediare a questi inconvenienti:

• Restringendo l'insieme dei codici consentiti in modo tale che diventi possibile (calcolabile) trovare la più breve lunghezza di codice dei dati, relativa ai codici consentiti, e
• Scegliendo un codice che sia ragionevolmente efficiente, qualunque siano i dati a disposizione. Questo punto è alquanto sfuggente e molte ricerche sono ancora in corso in questo settore.

Piuttosto che di "programmi", nella teoria della MLD di solito si parla di ipotesi, modelli o codici candidati. L'insieme di dati consentiti è poi chiamato classe di modelli. (Alcuni autori definiscono la classe di modelli come il modello.) Poi si seleziona il codice per il quale la somma della descrizione del codice e la descrizione dei dati che usano il codice è minima.

Una delle importanti proprietà dei metodi della MLD è che forniscono una salvaguardia naturale contro l'adattamento eccessivo (overfitting), perché attuano un compromesso tra la complessità dell'ipotesi (classe di modelli) e la complessità dei dati considerata l'ipotesi ^{[senza fonte]}.

Esempio di MLD

Si lancia una moneta 1.000 volte e si registra il numero di teste e di croci. Si considerino due classi di modelli:

• La prima è un codice che rappresenta gli esiti con uno 0 per le teste o un 1 per le croci. Questo codice rappresenta l'ipotesi che la moneta sia regolare. La lunghezza del codice secondo questa classe è sempre esattamente 1.000 bit.
• La seconda consiste di tutti i codici che sono efficienti per una moneta con una specifica distorsione, rappresentante l'ipotesi che la moneta non sia regolare. Diciamo che osserviamo 510 teste e 490 croci. Allora la lunghezza del codice secondo il miglior codice nella seconda classe di modelli è più corta di 1000 bit.

Per questa ragione un metodo statistico ingenuo potrebbe scegliere il secondo modello come migliore spiegazione per i dati. Tuttavia, un approccio MLD costruirebbe un unico codice basato sull'ipotesi, invece di usare semplicemente il migliore. Per fare questo, è più semplice usare un codice in due parti nel quale è specificato l'elemento della classe di modelli con la migliore prestazione. Poi si specificano i dati usando quel codice. Occorrono molti bit per specificare quale codice usare; pertanto la lunghezza totale del codice basato sulla seconda classe di modelli potrebbe essere più grande di 1.000 bit. Perciò la conclusione quando si segue un approccio di MLD è la seguente : è inevitabile che non vi siano abbastanza prove per sostenere l'ipotesi della moneta distorta, anche se il miglior elemento della seconda classe di modelli fornisce un miglior adattamento ai dati.

Notazione MLD

Centrale per la teoria della MLD è la corrispondenza biunivoca tra le funzioni di lunghezza del codice e le distribuzioni di probabilità. (Questo segue dalla disuguaglianza di Kraft-McMillan.) Per una qualsiasi distribuzione di probabilità ${\displaystyle P}$, è possibile costruire un codice ${\displaystyle C}$ tale che la lunghezza (in bit) di ${\displaystyle C(x)}$ sia uguale a ${\displaystyle -\log _{2}P(x)}$; questo codice minimizza la lunghezza attesa del codice. Viceversa, dato un codice ${\displaystyle C}$, si può costruire una distribuzione di probabilità ${\displaystyle P}$ tale che valga lo stesso risultato. (Le questioni di arrotondamento qui sono ignorate.) In altre parole, cercare un codice efficiente si riduce a cercare una buona distribuzione di probabilità, e viceversa.

Concetti correlati

L'MLD è collegata molto strettamente alla teoria delle probabilità e alla statistica attraverso la corrispondenza tra i codici e le distribuzioni di probabilità menzionata sopra. Ciò ha condotto ricercatori quali David MacKay a considerare l'MLD come equivalente all'inferenza bayesiana: la lunghezza del codice nel modello e la lunghezza del codice del modello e dei dati insieme nella MLD corrispondono rispettivamente alla probabilità a priori e alla verosimiglianza marginale nella cornice bayesiana.^[6]

Sebbene il meccanismo bayesiano sia spesso utile nel costruire codici MLD efficienti, la cornice MLD soddisfa anche altri codici che non sono bayesiani. Un esempio è il codice normalizzato della massima verosimiglianza di Shtarkov, che gioca un ruolo centrale nell'attuale teoria della MDL, ma non ha alcun equivalente nell'inferenza bayesiana. Inoltre, Rissanen sottolinea che non dovremmo fare nessuna assunzione circa il processo di generazione di dati veri: in pratica, una classe di modelli è tipicamente una semplificazione della realtà e pertanto non contiene nessun codice o distribuzione di probabilità che siano veri in un qualunque senso oggettivo.^[7][8] Nell'ultimo riferimento menzionato Rissanen basa il fondamento matematico della MLD sulla funzione di struttura di Kolmogorov.

Secondo la filosofia della MLD, i metodi bayesiani dovrebbero essere scartati se sono basati su precedenti che condurrebbero a risultati scadenti. I precedenti che sono accettabili da un punto di vista della MLD tendono ad essere favoriti anche nell'analisi bayesiana oggettiva; là, tuttavia, la motivazione di solito è diversa.^[9]

Altri sistemi

La MLD non fu il primo approccio informativo-teorico all'apprendimento; già nel 1968 Wallace e Boulton sperimentarono per primi un concetto correlato chiamato minima lunghezza del messaggio (MLM) (minimum message length [MML]). La differenza tra MDL ed MML è una fonte di perdurante confusione. Superficialmente, i metodi appaiono per la maggior parte equivalenti, ma ci sono alcune differenza significative, specialmente nell'interpretazione:

• La MLM è un approccio bayesiano completamente soggettivo: parte dall'idea che si rappresentino le proprie convinzioni circa il processo di generazione dei dati sotto forma di una distribuzione a priori. La MLD evita assunzioni circa il processo di generazione dei dati.
• Entrambi i metodi fanno uso di codici in due parti: la prima parte rappresenta sempre l'informazione che si sta tentando di apprendere, come l'indice di una classe di modelli (selezione dei modelli), o i valori dei parametri (stima dei parametri); la seconda parte è una codifica dei dati data l'informazione nella prima parte. La differenza tra i metodi è che, nella letteratura sulla MLD, si sostiene che i parametri indesiderati dovrebbero essere spostati nella seconda parte del codice, dove possono essere rappresentati con i dati usando un cosiddetto codice a una parte, che è spesso più efficiente di un codice a due parti. Nella descrizione originale della MLM, tutti i parametri sono codificati nella prima parte, così che si apprendono tutti i parametri.

Note

1. Jorma Rissanen, Modeling by shortest data description, in Automatica, vol. 14, n. 5, 1978, pp. 465–658, DOI:10.1016/0005-1098(78)90005-5.
2. Minimum Description Length, su mdl-research.org, Università di Helsinki. URL consultato il 2 luglio 2010 (archiviato dall'url originale il 18 febbraio 2010).
3. Peter Grünwald, the Minimum Description Length principle, MIT Press, giugno 2007. URL consultato il 3 luglio 2010 (archiviato dall'url originale il 16 giugno 2010).
4. Peter Grünwald, Advances in Minimum Description Length: Theory and Applications, MIT Press, aprile 2005. URL consultato il 3 luglio 2010 (archiviato dall'url originale il 30 novembre 2010).
5. Peter Grünwald, MDL Tutorial (PDF). URL consultato il 3 luglio 2010.
6. David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003. URL consultato il 3 luglio 2010.
7. Jorma Rissanen, Homepage of Jorma Rissanen. URL consultato il 3 luglio 2010 (archiviato dall'url originale il 17 novembre 2010).
8. Jorma Rissanen, Information and Complexity in Statistical Modeling, Springer, 2007. URL consultato il 3 luglio 2010.
9. Volker Nannen, A short introduction to Model Selection, Kolmogorov Complexity and Minimum Description Length. (PDF). URL consultato il 3 luglio 2010.

Bibliografia

• Minimum Description Length on the Web, by the University of Helsinki. Features readings, demonstrations, events and links to MDL researchers.
• Homepage of Jorma Rissanen, containing lecture notes and other recent material on MDL.
• Homepage of Peter Grünwald, containing his very good tutorial on MDL.
• J. Rissanen, Information and Complexity in Statistical Modeling, Springer, 2007.
• ISBN^{[collegamento interrotto]}0-262-07262-9.
• David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003.

Portale Informatica

Portale Matematica

Portale Statistica