Minimum Description Length

Un file si comprime nella misura in cui è prevedibile, e prevederlo bene significa averne capito la struttura. Da questa coincidenza nasce un criterio per scegliere modelli, una rilettura informazionale del rasoio di Occam, e il legame formale che fa di ogni language model un compressore.

Perché questo capitolo

Nel 1951 un professore del MIT, Robert Fano, propone ai suoi studenti una scelta: sostenere l’esame finale del corso, oppure scrivere un term paper su un problema aperto. Il problema è trovare il codice ottimale — il modo di assegnare sequenze di bit ai simboli di un messaggio così da scriverlo nel minor numero possibile di bit.

Uno studente, David Huffman, sceglie il paper per evitare l’esame. Ci lavora per mesi, sul punto di arrendersi. Poi trova un algoritmo che batte quello del suo professore, sullo stesso problema che il professore non aveva risolto.

È un buon punto di partenza, perché racchiude la tensione di tutto questo capitolo. Comprimere dati sembra una questione ingegneristica — fare entrare più file su un disco, mandare un’immagine più in fretta su una rete.

Ma sotto c’è una domanda profonda: qual è il limite ultimo? Quanto si può accorciare un messaggio senza perderne un solo bit? La risposta, dimostrata da Claude Shannon nel 1948, lega la compressione all’entropia, cioè all’imprevedibilità della sorgente.

Da lì il filo si allunga fino a un’idea che attraversa il machine learning di oggi: per comprimere bene un testo bisogna prevederlo bene, e prevederlo bene significa, in un senso preciso, averlo capito.

È il principio che Jorma Rissanen chiamò Minimum Description Length nel 1978, ed è anche il principio che fa di un modello linguistico un compressore — al punto che, come vedremo, un modello addestrato solo su testo riesce a comprimere immagini e audio meglio dei programmi nati apposta per quei formati.

Chi lavora con l’AI incontra questo legame senza saperlo ogni volta che guarda la loss di un modello: quel numero è, letteralmente, un tasso di compressione. Capirne il perché trasforma una metrica opaca in qualcosa di interpretabile, e dà una chiave per leggere benchmark, regolarizzazione e overfitting sotto un’unica luce.

Contesto

Questo capitolo siede nella Parte XIII, dopo i tre che fissano il vocabolario dell’informazione. Informazione come riduzione di incertezza introduce l’entropia e il primo dei due teoremi di Shannon, il source coding theorem, che è esattamente il limite invalicabile della compressione lossless di cui qui si raccolgono le conseguenze. Canali, rumore, capacità si occupa dell’altro teorema, quello sulla trasmissione.

Ridondanza, error correction, robustezza studia poi la ridondanza come qualcosa che si aggiunge per proteggere un messaggio dal rumore; qui la ridondanza è ciò che si toglie per renderlo più corto. Sono due facce della stessa moneta, e il capitolo precedente lo annota esplicitamente nei suoi collegamenti.

Il personaggio fondante resta Claude Shannon (1916-2001, matematico e ingegnere dei Bell Labs, i laboratori di ricerca della compagnia telefonica AT&T), che nel 1948 dimostra che una sorgente con entropia $H$ bit per simbolo non si può comprimere, in media, sotto $H$ bit per simbolo senza perdere informazione.

È il pavimento. Tutto il lavoro successivo sugli algoritmi di compressione consiste nel costruire codici che si avvicinino a quel pavimento — e ciascuno dei nomi che seguono ha aggiunto un mattone in quella direzione.

Il primo passo concreto è di David Huffman (1925-1999, allora dottorando al MIT nel corso di Robert Fano, ingegnere italo-americano che aveva proposto un codice precedente, lo Shannon-Fano coding). Nel 1952 Huffman pubblica A Method for the Construction of Minimum-Redundancy Codes (Proceedings of the IRE, 40(9), pp. 1098-1101), l’algoritmo che assegna in modo ottimale i codici più corti ai simboli più frequenti.

Negli anni ‘70 arrivano due ulteriori spostamenti. Da un lato la codifica aritmetica, raffinata tra gli altri da Rissanen e resa pratica da Witten, Neal e Cleary nel 1987, che supera un limite intrinseco di Huffman.

Dall’altro Jacob Ziv e Abraham Lempel (ingegneri e informatici israeliani), che nel 1977 pubblicano A Universal Algorithm for Sequential Data Compression (IEEE Transactions on Information Theory, 23(3), pp. 337-343): l’algoritmo LZ77, capostipite della famiglia che oggi comprime quasi tutto ciò che passa per una rete — gzip, zip, il PNG.

Su un binario apparentemente diverso, due idee quasi gemelle nascono a metà anni ‘60. Ray Solomonoff (1926-2009, matematico americano) nel 1964 e Andrey Kolmogorov (1903-1987, matematico sovietico) nel 1965 propongono, indipendentemente, di misurare l’informazione di un singolo oggetto come la lunghezza del programma più corto capace di generarlo.

È la complessità di Kolmogorov, fondazionale ma non calcolabile, di cui questo capitolo dà solo i contorni — ha un suo capitolo dedicato, kolmogorov-complessita (in preparazione), proprio dopo questo nella Parte.

Solomonoff arriva a quell’idea da una domanda diversa ma profondamente imparentata: come dovrebbe ragionare un agente ideale che cerca di prevedere il futuro a partire dai dati visti? La sua risposta — l’inferenza induttiva basata sui programmi più corti consistenti con le osservazioni — è la radice teorica della tesi che comprimere e comprendere siano la stessa cosa, e tornerà più avanti come sfondo dello Hutter Prize. Compressione, induzione e predizione, in questa tradizione, sono tre nomi per lo stesso problema.

Tra i due binari sta Jorma Rissanen (1932-2020, teorico dell’informazione finlandese, ricercatore IBM), che nel 1978 pubblica Modeling by Shortest Data Description (Automatica, 14(5), pp. 465-471) e fonda il principio MDL. È la versione operativa e calcolabile dell’idea di Kolmogorov: invece del programma più corto su una macchina universale (impossibile da trovare), si fissa una classe di modelli e si misura quanto ciascuno comprime i dati.

Rissanen non parte dal nulla: aveva un precedente nel Minimum Message Length di Chris Wallace e David Boulton del 1968, di matrice bayesiana, che aveva già legato la scelta del modello alla lunghezza del messaggio necessario a trasmetterlo.

L’intuizione

Prima di qualsiasi formula, due modi di guardare la compressione. Il primo la vede come rimozione di ridondanza; il secondo come ricerca del modello che genera i dati. Sono compatibili, e il secondo è quello che porta dritto a MDL e all’AI.

Angolo 1: comprimere è togliere ciò che era prevedibile

Un file si comprime nella misura in cui è prevedibile. Prendi un testo italiano: dopo la lettera “q” arriva quasi sempre una “u”; dopo “intelligen” arriva una manciata di possibilità (“za”, “te”, “ti”).

Quella prevedibilità è ridondanza, e la ridondanza non ha bisogno di essere scritta per intero: la si può ricostruire. Comprimere significa scrivere solo la parte imprevedibile, la sorpresa, e lasciare che il resto si rigeneri.

Il caso estremo opposto è il rumore casuale puro. Una sequenza di lanci di moneta equa non si comprime affatto: ogni bit è una sorpresa massima, niente è prevedibile, non c’è nulla da togliere.

Questa è la stessa idea dell’entropia vista in Informazione come riduzione di incertezza: l’entropia misura la sorpresa media della sorgente, e la sorpresa media è esattamente ciò che resta da scrivere dopo aver tolto ogni ridondanza. Da qui il pavimento di Shannon: sotto l’entropia non si scende, perché significherebbe buttare via informazione vera, non ridondanza.

C’è un legame diretto e quasi sorprendente con il capitolo sulla ridondanza e la correzione d’errore. Lì la ridondanza si aggiungeva di proposito per sopravvivere al rumore di un canale: bit in più, perché se qualcuno si perde gli altri ricostruiscono. Qui la ridondanza si toglie di proposito per occupare meno spazio.

Compressione e codifica di canale tirano la stessa corda in direzioni opposte, e un sistema reale fa entrambe le cose in sequenza: prima comprime per togliere il superfluo, poi aggiunge ridondanza controllata per proteggere ciò che resta. Non è una contraddizione: si toglie la ridondanza “involontaria” della sorgente e si aggiunge quella “progettata” del codice di canale, perfettamente calibrata sul rumore atteso.

Angolo 2: comprimere è trovare la regola che genera i dati

Ora capovolgi la prospettiva. Per togliere la ridondanza devi prima riconoscerla, e riconoscere una regolarità significa averne trovato la regola.

Considera la sequenza 2, 4, 6, 8, 10, ..., 1000. Scriverla tutta costa parecchio: cinquecento numeri. Ma c’è una descrizione molto più corta che la genera senza perdite: “i numeri pari da 2 a 1000”.

Quella frase è il modello dei dati, ed è anche la loro versione compressa. La compressione e la scoperta della struttura sono la stessa operazione vista da due lati. E se la sequenza avesse una sola eccezione — un 7 infilato in mezzo ai pari — la descrizione corta diventerebbe “i pari da 2 a 1000, tranne che al posto del 6 c’è un 7”: la regola più la sua eccezione, che è già, in miniatura, il two-part code di MDL.

Questo è il seme del principio MDL. Una descrizione completa dei dati ha sempre due parti: il costo di enunciare la regola (il modello) e il costo di enunciare ciò che la regola non cattura (le eccezioni, i residui).

Una sequenza con una regola pulita ha una descrizione corta perché la prima parte è breve e la seconda quasi vuota. Una sequenza di rumore non ha regola: la prima parte non aiuta, e si finisce per pagare l’intero costo dei dati grezzi.

L’aspetto interessante è cosa succede agli estremi. Un modello troppo semplice — “tutti zeri” per una sequenza che zeri non è — costa pochissimo a descrivere, ma lascia residui enormi: la seconda parte esplode. Un modello troppo complesso — uno che memorizza ogni singolo dato, rumore incluso — annulla i residui ma costa enormemente a descrivere: la prima parte esplode.

Il punto di minimo della somma sta nel mezzo, ed è esattamente il compromesso che chiamiamo rasoio di Occam: la spiegazione più semplice che rende conto dei dati. MDL non aggiunge Occam come euristica esterna; lo fa cadere fuori dalla matematica della lunghezza di descrizione. È una differenza di statuto importante, su cui si torna nella sezione finale: il rasoio qui non è un principio di gusto, ma una conseguenza di come si conta.

La meccanica

Adesso il formalismo, costruito per pezzi. Si parte dal limite teorico — l’entropia — poi si vedono i codici concreti che lo inseguono (Huffman, codifica aritmetica, Lempel-Ziv), e infine si arriva a MDL e all’identità che lega tutto all’AI.

L’ordine non è casuale: ogni pezzo prepara il successivo. Il limite dice dove si vuole arrivare; i codici dicono come avvicinarsi; MDL e l’identità con la log-loss dicono perché tutto questo riguarda i modelli predittivi, non solo i file su un disco.

Il limite: source coding theorem

Una sorgente emette simboli da un alfabeto, ciascuno con una probabilità. Sia $p(x)$ la probabilità del simbolo $x$ . L’entropia della sorgente è

H(p) = -\sum_x p(x) \log_2 p(x)

dove la somma corre su tutti i simboli possibili e il logaritmo in base 2 dà il risultato in bit. In parole povere, $H$ è la sorpresa media: quanti bit, in media, serve scrivere per ogni simbolo se si codifica in modo ottimale.

Il source coding theorem di Shannon dice due cose. Primo: nessun codice lossless può usare, in media, meno di $H$ bit per simbolo. Secondo: esistono codici che si avvicinano a $H$ quanto si vuole.

L’entropia è il pavimento, e il pavimento è raggiungibile. Tutta l’arte della compressione lossless sta nel costruire codici concreti che ci arrivino vicino — il resto di questa sezione li mette in fila.

Codici prefisso e la disuguaglianza di Kraft

Per scrivere simboli con lunghezze diverse senza separatori serve un codice prefisso: nessuna codeword è il prefisso di un’altra. Così, leggendo i bit uno dopo l’altro, si sa esattamente quando una codeword finisce, senza ambiguità. Se “0” è un codice, nessun altro codice può iniziare con “0”.

I codici prefisso obbediscono alla disuguaglianza di Kraft: se $l_i$ è la lunghezza in bit della codeword del simbolo $i$ , allora

\sum_i 2^{-l_i} \le 1

In parole povere, le lunghezze non possono essere tutte cortissime: c’è un bilancio da rispettare, e dare un codice corto a un simbolo costa “spazio” che toglie agli altri.

Da questa disuguaglianza si ricava la regola d’oro: la lunghezza ottimale per il simbolo $i$ è $l_i = -\log_2 p_i$ . I simboli frequenti ( $p_i$ grande) ricevono codici corti; i rari, codici lunghi. È la traduzione operativa del fatto che un simbolo frequente sorprende poco e merita pochi bit.

Huffman: l’ottimo a lunghezza intera

L’algoritmo di Huffman costruisce il codice prefisso ottimale con una procedura greedy bottom-up.

1. crea una foglia per ogni simbolo, con peso = sua frequenza
2. ripeti finché resta un solo nodo:
     estrai i due nodi di peso minimo
     creane un padre con peso = somma dei due
     reinserisci il padre nell'insieme
3. l'albero risultante ha la radice in cima e i simboli nelle foglie;
   etichetta ogni ramo (0 a sinistra, 1 a destra)
4. il codice di un simbolo è la sequenza di rami dalla radice alla sua foglia

L’idea, riga per riga: i due simboli più rari finiscono in fondo all’albero, quindi hanno i cammini più lunghi e i codici più lunghi; i frequenti restano vicini alla radice e prendono codici corti.

Fondendo sempre i due pesi minori, Huffman garantisce che nessun altro codice prefisso a lunghezza intera faccia meglio in media. È un risultato di ottimalità, non un’euristica: l’algoritmo greedy trova davvero il minimo, in quella classe di codici.

Resta però una crepa, ed è importante. Huffman assegna a ogni simbolo un numero intero di bit, mentre la lunghezza ottimale $-\log_2 p_i$ raramente è intera.

Se un simbolo ha probabilità $0{,}9$ , il suo costo ideale è $-\log_2 0{,}9 \approx 0{,}15$ bit, ma Huffman non può scendere sotto un bit per quel simbolo. Su distribuzioni molto sbilanciate, questo arrotondamento può sprecare fino a quasi un bit per simbolo — in casi estremi anche più dell’entropia stessa. È esattamente il problema che la codifica aritmetica viene a risolvere.

Codifica aritmetica: frazioni di bit

La codifica aritmetica chiude quella crepa abbandonando l’idea di un codice separato per ogni simbolo. Codifica l’intero messaggio come un singolo numero in un sotto-intervallo di $[0, 1)$ .

Si parte dall’intervallo $[0, 1)$ . Ogni simbolo lo restringe in proporzione alla propria probabilità, e alla posizione del simbolo nell’ordinamento. Un simbolo molto probabile lo accorcia poco (resta tanto spazio), uno improbabile lo accorcia molto.

Dopo aver letto tutto il messaggio resta un intervallino: si trasmette un qualunque numero al suo interno, scritto in binario. Più l’intervallo è stretto, più cifre binarie servono per indicarne uno al suo interno — ed è proprio qui che i simboli improbabili pagano il loro costo in bit.

La lunghezza del numero necessaria a identificare un intervallo di ampiezza $P$ è circa $-\log_2 P$ bit. E l’ampiezza dell’intervallo finale è la probabilità dell’intero messaggio, cioè il prodotto delle probabilità dei singoli simboli. Quindi la lunghezza totale è

L \approx -\log_2 P(\text{messaggio}) = \sum_t -\log_2 p(x_t) \;\text{bit}

In parole povere, ogni simbolo costa esattamente la sua sorpresa $-\log_2 p$ , anche quando questa è una frazione di bit. Non c’è arrotondamento per simbolo: l’overhead totale, su tutto il messaggio, è di meno di due bit.

Quei due bit sono costanti, indipendenti dalla lunghezza, e quindi trascurabili su file di dimensione reale. È il motivo per cui la codifica aritmetica raggiunge il limite di Shannon dove Huffman si ferma poco prima — ed è anche, come si vedrà, l’anello che la collega ai modelli linguistici.

Lempel-Ziv: imparare il dizionario strada facendo

Huffman e la codifica aritmetica presuppongono di conoscere le probabilità dei simboli. Lempel-Ziv no: impara la struttura mentre legge, senza nessuna tabella di frequenze data in anticipo.

È questo che lo rende universale — converge al tasso ottimale per qualunque sorgente stazionaria, qualunque sia la sua statistica. Non devi dirgli nulla sul testo: scopre le sue ripetizioni da solo, una proprietà preziosa quando la sorgente è ignota o cambia da file a file.

LZ77 (1977) usa una finestra scorrevole sul testo già visto. Quando incontra una sequenza che è già comparsa, non la riscrive: emette un riferimento, della forma (quanto indietro, quanto lunga, prossimo carattere).

La frase “nel mezzo del cammin di nostra vita, nel mezzo” codifica il secondo “nel mezzo ” come “torna indietro di N caratteri, copiane 10”. LZ78 (1978) e la sua variante LZW di Terry Welch (1984) costruiscono invece un dizionario esplicito che cresce simbolo dopo simbolo.

Questa famiglia è ovunque. Il formato DEFLATE — il cuore di gzip, di zip, e della compressione interna del PNG — è LZ77 seguito da Huffman: prima si sostituiscono le ripetizioni con riferimenti, poi si comprimono i riferimenti risultanti con un codice ottimale.

Due idee di questo capitolo, in cascata, nel file che hai probabilmente aperto un’ora fa. È anche un primo assaggio di come si combinano: un metodo a dizionario per togliere le ripetizioni grossolane, un codice a lunghezza variabile per spremere il resto.

MDL: la descrizione in due parti

Ora il principio. Dati $D$ e una classe di modelli, MDL sceglie il modello $M$ che minimizza la lunghezza di descrizione totale:

L(M) + L(D \mid M)

Il primo termine, $L(M)$ , sono i bit per descrivere il modello: i suoi parametri, codificati. Il secondo, $L(D \mid M)$ , sono i bit per descrivere i dati una volta noto il modello.

E qui scatta il legame con tutto il resto: codificare i dati con un modello probabilistico costa, in modo ottimale, $L(D \mid M) = -\log_2 P(D \mid M)$ bit — cioè la log-loss cumulata del modello sui dati. È la codifica aritmetica della sezione precedente, applicata ai dati con le probabilità che il modello assegna.

Questo è il two-part code, ed è la formalizzazione di Occam annunciata nell’intuizione. Un modello complesso fa scendere $L(D \mid M)$ (spiega bene i dati) ma fa salire $L(M)$ (costa molto a descriversi). Un modello semplice fa il contrario.

Il minimo della somma è il modello che comprime di più — e comprimere di più, per MDL, significa modellare meglio.

C’è una sottigliezza che il two-part code lascia aperta: come si codifica il modello? La scelta della codifica di $L(M)$ non è unica, e codifiche diverse possono favorire modelli diversi. Esistono per questo versioni raffinate — il refined MDL di Rissanen, basato sulla normalized maximum likelihood — che eliminano questa arbitrarietà definendo una lunghezza di descrizione canonica per un’intera classe di modelli. L’intuizione operativa, però, resta sempre quella del two-part code: paghi per la regola e paghi per le eccezioni, e cerchi il totale più basso.

L’identità che fa di un predittore un compressore

Mettiamo insieme codifica aritmetica e MDL, perché qui sta il cuore del ponte verso l’AI. Sia $p(x_t \mid x_{<t})$ la probabilità che un modello assegna al prossimo simbolo dato tutto ciò che lo precede. Dando questa distribuzione in pasto a un codificatore aritmetico, la lunghezza del file compresso è

L \approx \sum_t -\log_2 p(x_t \mid x_{<t}) \;\text{bit}

Quella somma ha un altro nome nel machine learning: è la cross-entropy cumulata, la log-loss totale del modello sul testo.

La loss media per simbolo, espressa in bit, è esattamente il tasso di compressione in bit per simbolo che quel modello otterrebbe. Non un’approssimazione: il numero su cui si addestra il modello e il numero che misura quanto comprime sono lo stesso numero.

La relazione tra log-loss e lunghezza di codice non è un’analogia né una somiglianza suggestiva: è un’identità, una conseguenza diretta del teorema di Shannon sulla codifica ottimale. Un modello che minimizza la cross-entropy è un modello che minimizza la lunghezza del file compresso. Predire bene e comprimere bene sono la stessa cosa misurata in due unità — questa è la classe di affermazione più forte del capitolo, e va tenuta distinta dalla tesi che incontreremo più avanti.

Ne segue subito un’altra quantità familiare. La perplexity è $2^{H}$ , dove $H$ è la cross-entropy media in bit: è il numero medio di alternative equiprobabili tra cui il modello esita a ogni passo.

Una perplexity bassa significa poche alternative effettive, cioè un testo molto comprimibile per quel modello: la perplexity è la comprimibilità esponenziata. La macchina ML di queste quantità — cross-entropy, KL come bit sprecati da un modello sbagliato — vive in Entropia, cross-entropy, KL divergence; qui se ne raccoglie il significato come lunghezza di codice.

Vale la pena fermarsi un istante su quanto questa identità sia stretta. Non si tratta di dire che “i modelli che predicono bene tendono a comprimere bene”, come fosse una correlazione empirica osservata sui dati. Si tratta di dire che le due quantità sono lo stesso numero, fino a un overhead trascurabile: la procedura di codifica aritmetica trasforma meccanicamente un predittore in un compressore, senza alcuna perdita e senza ipotesi aggiuntive.

La direzione opposta vale altrettanto: qualunque compressore lossless definisce implicitamente un modello probabilistico, quello per cui le sue lunghezze di codice sono ottimali. È il senso in cui Delétang e colleghi, nel titolo del loro lavoro, possono affermare che modellare il linguaggio è comprimere — non un’analogia, ma una traduzione esatta tra due vocabolari. Questa simmetria è ciò che dà sostanza a tutta la seconda metà del capitolo.

Esempi

Tre esempi eterogenei: uno numerico carta-e-penna, uno in codice, uno scenario reale documentato. Poi un quarto, più breve, su MDL come selezione di modello. Insieme percorrono la stessa idea dal caso più semplice (quattro simboli) al più sorprendente (un modello da 70 miliardi di parametri).

Esempio 1 — Huffman su quattro simboli, e dove inciampa

Quattro simboli con probabilità $p(A)=0{,}5$ , $p(B)=0{,}25$ , $p(C)=0{,}125$ , $p(D)=0{,}125$ . L’entropia è

H = 0{,}5 \cdot 1 + 0{,}25 \cdot 2 + 0{,}125 \cdot 3 + 0{,}125 \cdot 3 = 1{,}75 \;\text{bit/simbolo}

L’algoritmo di Huffman fonde prima i due meno frequenti, $C$ e $D$ (peso combinato $0{,}25$ ), poi quel nodo con $B$ (peso $0{,}5$ ), infine con $A$ . I codici risultanti: $A=0$ (1 bit), $B=10$ (2 bit), $C=110$ (3 bit), $D=111$ (3 bit). La lunghezza media è

0{,}5 \cdot 1 + 0{,}25 \cdot 2 + 0{,}125 \cdot 3 + 0{,}125 \cdot 3 = 1{,}75 \;\text{bit/simbolo}

esattamente l’entropia. Un codice a lunghezza fissa userebbe 2 bit per ogni simbolo: il risparmio è del 12,5%. Qui Huffman è perfetto, ma solo perché tutte le probabilità sono potenze di $\tfrac{1}{2}$ e quindi le lunghezze ideali $-\log_2 p$ sono intere.

Nota come il codice si decodifica senza ambiguità, pur con lunghezze diverse: leggendo 0 sai subito che è $A$ e ricominci; leggendo 1 sai che devi proseguire; 11 impone un terzo bit. Nessuna codeword è prefisso di un’altra, ed è proprio la proprietà di prefisso che permette di leggere lo stream un bit alla volta senza separatori.

Cambia distribuzione, però, e la crepa appare. Due soli simboli, $p = 0{,}9$ e $p = 0{,}1$ . L’entropia è circa $0{,}47$ bit per simbolo.

Ma Huffman deve dare almeno un bit a ciascuno (i codici “0” e “1”), quindi usa esattamente 1 bit per simbolo: più del doppio dell’entropia. Per recuperare quel divario serve la codifica aritmetica, che spalma frazioni di bit, oppure raggruppare i simboli in blocchi prima di applicare Huffman.

Esempio 2 — un language model come compressore (in codice)

Lo schema per comprimere un testo con un modello e un codificatore aritmetico è breve.

def compress(text, model):
    coder = ArithmeticEncoder()   # mantiene un intervallo [low, high)
    context = []
    for token in text:
        probs = model.predict(context)  # distribuzione sul prossimo token
        coder.encode(token, probs)      # restringe l'intervallo di ~ -log2 p(token)
        context.append(token)
    return coder.finish()         # bit totali ~ somma di -log2 p(token)

La decompressione usa lo stesso modello: dato lo stesso contesto, model.predict restituisce le stesse probs, e il decodificatore ripercorre gli intervalli a ritroso ricostruendo i token uno a uno.

Il punto cruciale è che il modello deve essere identico e deterministico ai due capi — un singolo bit di differenza nelle probabilità predette manda fuori sincrono l’intero stream. Se chi decomprime ha già il modello, questo non viaggia col file: il file contiene solo la sorpresa residua, $-\log_2 p$ sommata sui token.

Se invece il modello deve viaggiare col messaggio, la sua dimensione entra nel conto — e a quel punto si sta facendo esattamente MDL: $L(\text{modello}) + L(\text{dati} \mid \text{modello})$ . È la stessa contabilità del two-part code, vista dal lato dell’ingegneria.

C’è anche una variante in cui il modello non è fissato a monte ma si adatta mentre legge, come fa Lempel-Ziv col suo dizionario: compressore e decompressore aggiornano il modello in parallelo sugli stessi dati già visti, restando sincronizzati senza bisogno di trasmettere nulla del modello. È il regime della compressione adattiva, e mostra che il confine tra “il modello” e “i dati” è meno rigido di quanto la formula suggerisca: parte del modello può essere ricostruita dai dati stessi.

Esempio 3 — Chinchilla 70B batte PNG e FLAC (scenario reale)

Nel 2023 un gruppo di DeepMind pubblica Language Modeling Is Compression (Delétang et al., arXiv:2309.10668, poi a ICLR 2024), che porta l’identità precedente alle sue conseguenze sperimentali.

Prendono Chinchilla 70B, un modello linguistico da 70 miliardi di parametri addestrato essenzialmente su testo, e lo usano come compressore lossless via codifica aritmetica — esattamente lo schema dell’esempio 2.

Niente di nuovo nel meccanismo: cambia solo che il predittore è enorme e addestrato su un’enorme fetta del testo prodotto dall’umanità. È lo stesso codificatore aritmetico dell’esempio precedente, alimentato con probabilità molto migliori.

Il risultato documentato: Chinchilla comprime patch di immagini ImageNet al 43,4% della dimensione grezza, contro il 58,5% del PNG; e campioni audio di LibriSpeech al 16,4%, contro il 30,3% del FLAC. Un modello che non ha mai visto un’immagine o una forma d’onda durante l’addestramento batte i compressori nati apposta per quei formati.

La morale, nel quadro di questo capitolo: un buon predittore general-purpose è un buon compressore general-purpose, anche fuori dal dominio su cui è stato addestrato, perché ha imparato regolarità di basso livello — ripetizioni, strutture locali, correlazioni tra simboli vicini — che valgono ben oltre il testo.

Detto altrimenti: l’identità log-loss/lunghezza-di-codice non smette di valere quando si esce dal testo. Se il modello assegna probabilità ragionevoli a una sequenza di byte, comunque essa sia nata, la codifica aritmetica la comprime in proporzione a quelle probabilità. Il modello non sa di star comprimendo un’immagine: vede solo una sequenza di simboli su cui esprime aspettative, e le sue aspettative si rivelano abbastanza buone da battere PNG.

Va segnalato il caveat che gli stessi autori sollevano, perché è esattamente il punto di MDL. Per un confronto onesto bisognerebbe contare anche la dimensione del modello: Chinchilla è un compressore con un dizionario gigantesco già pagato a monte.

Se si misura la lunghezza di descrizione totale — il modello più i dati compressi, come prescrive il two-part code — il quadro cambia per file piccoli, dove i 70 miliardi di parametri dominano il conto. Il modello vince in modo netto solo quando i dati da comprimere sono molti rispetto alla sua dimensione.

Esempio 4 — MDL come scelta del grado di un polinomio

Hai $N$ punti rumorosi e vuoi adattarci un polinomio. Un polinomio di grado 1 (una retta) ha pochi parametri: $L(M)$ è piccola, ma se i dati hanno una curvatura reale i residui sono grandi e $L(D \mid M)$ è alta.

Un polinomio di grado $N-1$ passa invece esattamente per ogni punto: i residui sono nulli, $L(D \mid M)$ tende a zero, ma per descrivere $N$ coefficienti precisi serve $L(M)$ enorme — e quel polinomio ha memorizzato anche il rumore, cioè ha fatto overfitting.

MDL sceglie il grado intermedio che minimizza la somma. Non perché qualcuno abbia deciso a mano di “preferire i modelli semplici”, ma perché la lunghezza di descrizione totale ha un minimo lì.

È il rasoio di Occam che emerge come conseguenza matematica, non come principio aggiunto: e questa è un’equivalenza argomentata tra Occam e minima lunghezza di descrizione, non una semplice analogia.

Lo stesso meccanismo, va detto, è ciò che rende MDL utile fuori dai polinomi giocattolo: ovunque ci sia da scegliere quanta capacità dare a un modello — il grado di un polinomio, il numero di cluster, la profondità di un albero — c’è una curva a U di lunghezza di descrizione con un minimo da trovare. È il filo che lega un esempio scolastico alla scelta di modello nel machine learning reale.

Applicazioni pratiche

Le idee di questo capitolo non restano nei manuali di teoria dell’informazione: ricompaiono, spesso senza il loro nome, in quattro punti della pratica quotidiana di chi costruisce sistemi AI. Tre riguardano la compressione dei dati e dei modelli; uno la valutazione.

La loss di un modello è un tasso di compressione. Quando guardi la loss di pretraining di un LLM — un numero come $1{,}9$ — stai guardando una cross-entropy in nat. Diviso per il logaritmo naturale di 2 (circa $0{,}69$ ), sono circa $2{,}7$ bit per token: tanto costerebbe, in media, ogni token nel file compresso da quel modello via codifica aritmetica.

Le metriche bits-per-byte o bits-per-character su un corpus held-out sono letteralmente tassi di compressione, e si usano per confrontare modelli su una scala interpretabile.

Un modello con $1{,}0$ bit per byte comprime il testo a un ottavo (un byte è 8 bit); uno con $0{,}8$ bit per byte fa meglio. La perplexity è la stessa cosa esponenziata.

Questo trasforma una metrica astratta in qualcosa di concreto: un modello migliore comprime meglio i dati che non ha visto. E poiché la compressione su dati held-out non si può barare — o il file rimpicciolisce o non lo fa — è anche una metrica difficile da gonfiare, a differenza di molti benchmark a scelta multipla, dove un modello può azzeccare la risposta per ragioni che nulla hanno a che vedere con la comprensione.

MDL come criterio di selezione e regolarizzazione. Scegliere la complessità di un modello senza un validation set separato è possibile con criteri come MDL o il suo cugino approssimato BIC (Bayesian Information Criterion, una penalità di complessità derivata dall’approssimazione asintotica di MDL).

L’idea, vista sotto questa luce, illumina anche la regolarizzazione classica: penalizzare i pesi grandi con weight decay equivale, in una lettura informazionale, a preferire modelli con una descrizione più corta — pesi piccoli e regolari costano meno bit da specificare.

È un modo informazionale di dire la stessa cosa che il trade-off bias-varianza dice in termini statistici: troppa capacità memorizza il rumore invece della struttura. Due vocabolari, statistico e informazionale, per lo stesso fenomeno.

Benchmark di compressione come proxy di modellazione. Dal 2006 lo Hutter Prize (finanziato da Marcus Hutter, ricercatore in AI di formazione tedesca, autore di lavori sull’intelligenza artificiale generale basati sull’inferenza induttiva) offre un premio in denaro a chi comprime di più un estratto di Wikipedia.

In origine il bersaglio era enwik8 (i primi 100 MB di un dump di Wikipedia in inglese), oggi enwik9 (1 GB), con un montepremi che ha raggiunto i 500.000 euro e un premio per ogni 1% di miglioramento. Il regolamento conta nel file finale anche il decompressore stesso: un modo concreto di imporre la contabilità MDL, perché un compressore che bara memorizzando i dati nel proprio codice non guadagna nulla.

La tesi esplicita del concorso è che comprimere bene un testo richiede di modellarne la struttura — la grammatica, i fatti, le regolarità del mondo che vi sono descritte — e quindi che il tasso di compressione sia un proxy misurabile di capacità di modellazione. È un benchmark di compressione usato come benchmark di “comprensione”. Resta una scommessa, la stessa che la sezione finale invita a maneggiare con cautela, ma è una scommessa resa numerica e falsificabile.

Distillazione e quantizzazione come compressione del modello. C’è un secondo senso di compressione, che riguarda non i dati ma il modello stesso.

La distillation (in preparazione) addestra un modello piccolo a riprodurre il comportamento di uno grande: comprime la sua conoscenza in meno parametri. La quantizzazione (quantization-base, in preparazione) riduce i bit per parametro — da 16 a 8 a 4 — comprimendo i pesi.

Il legame con MDL è un’analogia strutturale, non un’identità formale: in entrambi i casi si cerca la rappresentazione più corta che preservi il comportamento.

Ma qui si comprime il modello, non i dati che il modello genera, e la matematica non è la stessa del two-part code. La distillazione non ha un teorema di Shannon che le garantisca un limite ottimale; è un processo di addestramento con le sue perdite e i suoi compromessi. Tenere distinte le due nozioni di compressione — dei dati e del modello — evita una confusione comune, in cui si presta alla seconda la solidità formale che spetta solo alla prima.

Dove si rompe

La compressione e MDL sono solidi e ben compresi. Ciò che si rompe è l’intuizione di chi tira l’idea oltre le sue ipotesi, o ne confonde le classi di affermazione.

Questa sezione raccoglie i fraintendimenti che fanno più danni — e sono parecchi, perché qui convivono un teorema (log-loss = lunghezza di codice), una tesi (compressione = intelligenza) e diverse analogie (la compressione del modello), tre classi di legame che è facilissimo scambiare l’una per l’altra. Buona parte degli errori che seguono nasce esattamente da quello scambio.

“Comprimere è capire” non è un teorema. È la confusione più pericolosa del capitolo, e merita di essere spezzata in due.

Da un lato c’è l’identità formale tra log-loss e lunghezza di codice: un modello con cross-entropy bassa produce, via codifica aritmetica, un file corto. Questo è un teorema, conseguenza diretta di Shannon.

Dall’altro c’è la tesi che “comprimere bene equivalga a essere intelligenti”, o a “comprendere”: questa è un’ipotesi di lavoro, sostenuta dalla scuola dell’algorithmic information theory (Hutter, Mahoney) e incarnata nello Hutter Prize, ma non è dimostrata e non è consenso.

Comprimere bene un testo richiede di modellarne le regolarità statistiche; che questo coincida con “capirlo” nel senso pieno della parola è una scommessa filosofica, non un risultato. Presentare la tesi come se fosse il teorema è l’errore che la disciplina delle classi di affermazioni esiste per impedire.

Entropia di Shannon e complessità di Kolmogorov non sono la stessa quantità. L’entropia misura la sorpresa media di una sorgente probabilistica: ha senso solo se c’è una distribuzione $p$ . La complessità di Kolmogorov $K(x)$ misura invece l’informazione di un singolo oggetto: la lunghezza del programma più corto che lo genera, senza bisogno di alcuna probabilità.

Sono legate — per sorgenti computabili, $K$ media è vicina a $H$ — ma concettualmente distinte, e una differenza è decisiva: $H$ si calcola se conosci $p$ , mentre $K$ è incomputabile, non esiste algoritmo che la trovi per ogni stringa (segue dall’indecidibilità del problema dell’arresto). MDL è proprio la mossa per aggirare questa incomputabilità: fissa una classe di modelli e rende il calcolo possibile. Il dettaglio sta in kolmogorov-complessita (in preparazione).

Non esiste il compressore che comprime tutto. L’intuizione “con un algoritmo abbastanza furbo comprimo qualunque file” è dimostrabilmente falsa, con un argomento di conteggio elementare.

Le stringhe di lunghezza $n$ sono $2^n$ ; le stringhe più corte sono in numero strettamente minore. Nessuna funzione può mappare in modo iniettivo $2^n$ input in meno di $2^n$ output distinti senza collisioni — e una collisione, in compressione lossless, significa che due file diversi si comprimono nello stesso, quindi la decompressione è ambigua.

Conseguenza: ogni compressore lossless che accorcia alcuni file ne deve necessariamente allungare altri. Funziona perché i file reali non sono casuali; sul rumore puro nessun compressore guadagna nulla.

Sotto l’entropia non si scende. È una variante della precedente, vista dal lato della sorgente. Un compressore può rimuovere ridondanza, non informazione.

Una volta arrivati al pavimento di Shannon, ogni bit ulteriore tolto è informazione vera persa, e la ricostruzione non è più esatta. Chi promette compressione lossless arbitrariamente spinta — il file da un terabyte ridotto a un kilobyte, e poi ancora di più ricomprimendolo — sta vendendo un perpetuum mobile. Ricomprimere un file già compresso non guadagna nulla: la ridondanza è già stata tolta.

Lossy non è “compressione migliore”, è un’altra cosa. I formati con perdita — JPEG per le immagini, MP3 per l’audio, i codec video come H.264 — comprimono molto di più dei formati lossless, ma lo fanno buttando via informazione: scartano i dettagli che l’occhio o l’orecchio umano non notano.

Non sono lossless più efficienti; sono un trade-off diverso, dove la domanda non è “quanto comprimo senza perdere nulla” ma “quanta perdita sono disposto ad accettare”. Questo trade-off ha una sua teoria, la rate-distortion, ed è il tema del prossimo capitolo — rate-distortion (in preparazione). Confondere i due regimi porta a paragonare numeri che non sono paragonabili.

La dimensione del modello non è gratis. Tornando all’esempio di Chinchilla: dire che un LLM “comprime enwik9 meglio di gzip” è vero solo se il decoder ha già i 70 miliardi di parametri da qualche parte.

In un confronto MDL onesto — il modello più i dati, come impone il two-part code — quei parametri vanno contati, e per file piccoli dominano il conto. L’errore è trattare il modello come un dato esterno gratuito quando invece è parte della descrizione. È lo stesso punto che separa l’identità formale dalla suggestione: la contabilità deve essere completa.

Huffman non è l’ottimo assoluto. È ottimo, ma solo tra i codici prefisso a lunghezza intera per simbolo, ed è una qualifica facile da dimenticare.

La codifica aritmetica fa strettamente meglio assegnando frazioni di bit, e su distribuzioni molto sbilanciate la differenza è grande — fino a quasi un bit per simbolo sprecato da Huffman, come nell’esempio $0{,}9 / 0{,}1$ . Chi cita “Huffman ottimale” senza la qualifica suggerisce un primato che non c’è.

Universale non vuol dire migliore su ogni file. Lempel-Ziv è universale nel senso asintotico: converge al tasso ottimale per qualunque sorgente stazionaria, al crescere della lunghezza del testo.

Su file corti, o su sorgenti la cui statistica cambia nel tempo, può comportarsi molto peggio di un metodo costruito ad hoc che conosca quella statistica in anticipo. L’universalità è una garanzia al limite, non una promessa su ogni singolo input — ed è una distinzione che vale per tutte le garanzie asintotiche, in compressione come altrove.

Universale, ma non immune dai dati patologici. Un corollario dell’argomento di conteggio: anche Lempel-Ziv, su un input scelto apposta per ingannarlo (per esempio dati già compressi, indistinguibili dal rumore), può produrre un output più lungo dell’originale.

I formati reali aggiungono per questo una clausola di sicurezza — se la compressione non guadagna nulla, memorizzano il blocco grezzo, pagando solo un bit di intestazione. È un promemoria che “compressione” è una scommessa sulla struttura dei dati, non una garanzia incondizionata.

Il grokking come “compressione” è un’ipotesi aperta, non un fatto. Vale la pena un cenno onesto, perché l’analogia circola.

Il grokking è il fenomeno, osservato da Power et al. nel 2022 su piccoli dataset algoritmici, per cui una rete prima memorizza il training set (overfitting) e poi, molto più tardi nell’addestramento, “scatta” improvvisamente verso la generalizzazione.

Una famiglia di spiegazioni lo legge in chiave MDL: la soluzione che memorizza è facile da trovare ma costosa da descrivere; quella che generalizza è una descrizione più corta, più compressa, e finisce per prevalere quando l’ottimizzazione continua a premere verso modelli più semplici.

È una lettura suggestiva, coerente con lo spirito di questo capitolo, e alcuni lavori successivi (tra cui analisi dei circuiti che la rete forma) le danno sostanza. Ma resta un’ipotesi di ricerca attiva, non un consenso consolidato: un cenno, non una tesi del capitolo. Lo cito qui proprio perché è il tipo di analogia che, se non marcata, scivolerebbe verso la tesi forte che questa intera sezione invita a non dare per scontata.

Collegamenti

Informazione come riduzione di incertezza: l’entropia e il source coding theorem sono il pavimento di tutta la compressione lossless. La sorpresa $-\log p$ del singolo evento è il costo in bit che la codifica aritmetica gli assegna.
Ridondanza, error correction, robustezza: la ridondanza che lì si aggiunge per robustezza, qui si toglie per efficienza. Due usi opposti della stessa grandezza, in cascata nei sistemi reali.
Entropia, cross-entropy, KL divergence: la cross-entropy come lunghezza di codice attesa, la KL come bit sprecati da un modello sbagliato. La macchina ML dell’identità log-loss/compressione.
Canali, rumore, capacità: l’altro teorema di Shannon, sulla trasmissione; complementare al limite sulla compressione raccolto qui.
Il trade-off bias-varianza: MDL come istanza informazionale dello stesso trade-off. Modello troppo complesso = overfitting = descrizione lunga.
kolmogorov-complessita (in preparazione): il prossimo capitolo della Parte. $K(x)$ , il programma più corto, l’incomputabilità, Solomonoff. MDL è il suo cugino calcolabile.
rate-distortion (in preparazione): la compressione lossy, dove si decide quanta perdita accettare. Il regime di JPEG, MP3 e video, complementare al lossless di questo capitolo.
ponte-informazione-llm (in preparazione): il ponte completo tra token prediction, compressione e rappresentazioni, di cui qui si pongono le fondamenta formali.
loss-perplexity (in preparazione, Parte Training): perplexity come comprimibilità esponenziata, e bits-per-byte come metrica di compressione su corpus held-out.
distillation, quantization-base (in preparazione, Parte Training): la compressione del modello (non dei dati), parente concettuale di MDL per analogia, non per identità formale.

Per andare oltre

Shannon, C. E. (1948). A Mathematical Theory of Communication, Bell System Technical Journal, 27, 379-423 e 623-656. Il paper fondante: entropia, source coding theorem, il pavimento della compressione.
Huffman, D. A. (1952). A Method for the Construction of Minimum-Redundancy Codes, Proceedings of the IRE, 40(9), 1098-1101. Tre pagine che danno il codice prefisso ottimale, nato come term paper per evitare un esame.
Rissanen, J. (1978). Modeling by Shortest Data Description, Automatica, 14(5), 465-471. Il paper che introduce MDL e lega la scelta del modello alla lunghezza di descrizione.
MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms, Cambridge University Press (gratis online). Il riferimento intuitivo per codifica aritmetica e per il legame compressione-inferenza, con esempi visivi.
Grünwald, P. D. (2007). The Minimum Description Length Principle, MIT Press. La trattazione monografica moderna di MDL: two-part code, refined MDL, MDL contro Bayes.
Delétang, G. et al. (2023). Language Modeling Is Compression, arXiv:2309.10668 (ICLR 2024). L’articolo che mostra gli LLM come compressori general-purpose, con i numeri su ImageNet e LibriSpeech — da leggere tenendo a mente il caveat sulla dimensione del modello.