Scommettere sulla prossima parola: i modelli n-gram

San Pietroburgo, inverno 1913. Andrej Andreevič Markov, cinquantaseienne, matematico dell’Accademia Imperiale delle Scienze, ha davanti a sé l’Evgenij Onegin di Puškin (il romanzo in versi che ogni russo conosce a memoria) e una matita. Ricopia le prime 20.000 lettere, tutto il primo capitolo e parte del secondo, eliminando spazi e punteggiatura; le dispone in duecento tabelle da dieci righe per dieci colonne; poi conta, a mano, vocali e consonanti [Mar13]. Il primo numero è banale: il 43 per cento delle lettere sono vocali. Il secondo no: dopo una consonante, una vocale arriva circa due volte su tre (0,663); dopo un’altra vocale, appena una volta su otto (0,128). Le lettere di Puškin non sono estrazioni del lotto, indipendenti l’una dall’altra: ogni lettera ricorda quella che la precede.

Il movente era una polemica tutta matematica. C’è un risultato, la legge dei grandi numeri, che dice una cosa che tutti conosciamo per esperienza: se lanci una moneta dieci volte le teste possono essere sette, ma se la lanci diecimila volte la quota di teste si assesta vicinissima a metà. Il collega moscovita Pavel Nekrasov sosteneva che quella legge valesse solo per eventi indipendenti, cioè per prove che non si ricordano l’una dell’altra, come sono appunto i lanci di una moneta. Markov, polemista di rara costanza, costruì per smentirlo la teoria delle sequenze in cui ogni evento dipende dal precedente (oggi le chiamiamo catene di Markov, e sono quelle della sezione di matematica) e andò a cercare la dipendenza dentro un capolavoro della letteratura. Presentò i conteggi all’Accademia il 23 gennaio 1913.

Di quelle catene il libro si serve più volte, con nomi diversi. Nel capitolo sul Reinforcement Learning l’ambiente in cui si muove un agente è un processo decisionale di Markov, che è una catena di Markov con in più le azioni di qualcuno e le ricompense che ne seguono; nei modelli di diffusione sarà una catena che sporca un’immagine un poco alla volta, per poi imparare a rifare la strada al contrario e ripulirla. La struttura è sempre questa: il prossimo passo dipende solo da dove sei adesso.

Trentacinque anni dopo, Claude Shannon rovescia il gioco, nell’articolo del 1948 che abbiamo già incontrato nel capitolo sui richiami di matematica [Sha48]: non contare per capire un testo, ma contare per generarne uno.

Il suo metodo è artigianale quanto quello di Markov, e si può rifare stasera con un libro qualunque. Scrivi una lettera a caso su un foglio, mettiamo la g. Apri il libro a caso, scorri finché non trovi una g, e guarda che lettera viene subito dopo: se è una a, scrivi a sul tuo foglio. Adesso richiudi il libro, riaprilo da un’altra parte, cerca la prima a e copia la lettera che la segue. E avanti così: il foglio cresce una lettera per volta, e ogni lettera nuova è stata scelta da un pezzo di testo vero, ma da un punto del libro che non ha niente a che vedere con il precedente. Shannon chiamò queste stringhe «approssimazioni in serie», e salendo di ordine, cioè cercando nel libro l’ultima parola scritta invece dell’ultima lettera e copiando la parola che la segue, esce roba come «THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH WRITER THAT THE CHARACTER OF THIS POINT…»: ogni gruppetto di due o tre parole fila liscio, l’insieme non significa nulla. Tre anni dopo, con un gioco di predizione fatto in casa, Shannon stimerà quanto l’inglese sia prevedibile lettera per lettera [Sha51]: circa un bit a lettera, come abbiamo visto parlando di compressione. Un bit è una domanda da sì o no: vuol dire che, in media, chi conosce bene l’inglese indovina la lettera successiva con una domanda sola, purché ben scelta. Non perché le lettere siano due: perché quasi sempre quello che precede ha già ristretto il campo a una o due candidate (dopo «th» ci si aspetta una vocale, dopo «q» una «u»), e le rare volte in cui il campo resta largo si pagano su quella media.

L’idea che unisce il matematico che contava le lettere a Pietroburgo e l’ingegnere dei laboratori Bell è la tesi di questa sezione: il linguaggio si può modellare come una catena di scommesse. Nella sezione precedente il testo era un sacchetto di parole, e per il classificatore «Il gatto nero salta sul muro» e «Il muro nero salta sul gatto» erano gemelli indistinguibili. Qui l’ordine torna protagonista: costruiamo la macchina più semplice che scommette sulla parola successiva, il modello n-gram, che per mezzo secolo è stato il cuore del NLP statistico. Il nome dice quanto lungo è il gruppetto di parole che si guarda: due, e si chiama bigramma; tre, e si chiama trigramma; \(n\) è il numero lasciato in bianco.

La lingua come catena di scommesse

Un modello di linguaggio (language model) è un sistema che assegna una probabilità a una frase, o, che è lo stesso, scommette su quale parola verrà dopo, date quelle già lette. Sembra un esercizio astratto, ma è dappertutto: è la barra dei suggerimenti della tastiera del telefono, è il correttore che preferisce «buona serata» a «buona serrata», ed è ciò che permette a un riconoscitore vocale di scegliere la trascrizione che «suona» più italiana.

Elementare

Facciamo il gioco del completamento: «Il gatto nero salta sul…». Tu una risposta ce l’hai già: «muro», forse «tetto», di sicuro non «marmellata». Come fai? Hai letto e ascoltato milioni di frasi, e sai cosa viene di solito dopo cosa.

Un modello n-gram fa la stessa cosa, ma con un quaderno. Immagina di leggere tonnellate di testo con la matita in mano: ogni volta che incontri la parola «gatto», vai alla pagina intestata «gatto» e annoti la parola che la segue. A fine lettura, la pagina è la scommessa bell’e pronta: se dopo «gatto» hai visto 3 parole in tutto (2 volte «nero», 1 volta «bianco»), allora scommetti «nero» con fiducia 2 su 3 e «bianco» con fiducia 1 su 3.

C’è un patto nascosto, però. A rigore, per scommettere bene dovresti tener conto di tutta la frase letta fin lì; ma quasi nessuna frase intera compare due volte, nemmeno in una biblioteca, e non avresti mai conteggi. Il patto (lo stesso di Markov con le sue vocali) è fingere che conti solo l’ultima parola (modello a coppie, il bigramma) o le ultime due (a terne, il trigramma). È una semplificazione dichiarata, e funziona molto meglio di quanto meriti.

Superiore

Un modello di linguaggio stima la probabilità congiunta di una sequenza di parole \(w_1, \dots, w_N\). La regola della catena la scompone, senza alcuna approssimazione, in un prodotto di probabilità condizionate:

\[ P(w_1, \dots, w_N) = \prod_{t=1}^{N} P(w_t \mid w_1, \dots, w_{t-1}), \]

dove \(w_t\) è la parola in posizione \(t\) e ogni fattore è la scommessa sulla parola successiva dato il prefisso. Il problema è la stima: i prefissi lunghi sono quasi tutti unici e i loro conteggi valgono zero o uno. L’assunzione di Markov tronca la storia alle ultime \(n-1\) parole:

\[ P(w_t \mid w_1, \dots, w_{t-1}) \;\approx\; P(w_t \mid w_{t-n+1}, \dots, w_{t-1}). \]

Con \(n=2\) si ha il bigramma, \(P(w_t \mid w_{t-1})\); con \(n=3\) il trigramma. La stima è quella di massima verosimiglianza (MLE), già incontrata nel capitolo sui richiami di matematica: semplici frequenze relative,

\[ P(w_t \mid w_{t-1}) = \frac{C(w_{t-1}\, w_t)}{C(w_{t-1})}, \]

dove \(C(\cdot)\) conta le occorrenze nel corpus di addestramento: quante volte la coppia \(w_{t-1} w_t\) appare, diviso quante volte appare \(w_{t-1}\). Si dimostra che queste frazioni massimizzano la verosimiglianza del corpus. Due accorgimenti pratici: si incorniciano le frasi con simboli di inizio e fine, <s> e </s>, così anche la prima parola e la chiusura sono scommesse come le altre; e i prodotti di molte probabilità piccole si calcolano come somme di logaritmi, per evitare l’underflow (lo stesso trucco di Naive Bayes).

Tre frasi e un quaderno di conteggi

Basta un corpus giocattolo per vedere tutta la macchina in funzione, dove corpus è il mucchio di testo su cui si conta. Il nostro sarà di tre frasi:

1. «il gatto nero salta sul muro»

2. «il gatto bianco dorme sul divano»

3. «il cane guarda il gatto nero»

Contiamo le coppie di parole adiacenti. Prima però mettiamo a ogni frase due segnali, uno di inizio e uno di fine, che si scrivono <s> e </s> e servono a due cose precise. Il segnale di inizio dà una «parola precedente» anche alla primissima parola della frase, che altrimenti non ne avrebbe nessuna e non si potrebbe scommetterci sopra. Quello di fine trasforma il punto fermo in una scommessa come le altre: il modello, arrivato a «muro», deve poter decidere se la frase finisce lì o continua, e senza un simbolo per «finisce lì» non saprebbe come dirlo.

I conti che seguono si scrivono in una notazione da decifrare una volta per tutte, perché ricorre in tutto il libro: \(P(\text{gatto} \mid \text{il})\) si legge «la probabilità di gatto, sapendo che prima c’era il». La barretta verticale vuol dire «dato che», e separa la cosa su cui si scommette (a sinistra) da quello che si sa già (a destra). Tutto qui: è una frazione con un nome, e la frazione è proprio la pagina del quaderno, «quante volte questa parola ha seguito quell’altra, diviso quante volte quell’altra è comparsa».

• ogni frase comincia con «il»: \(P(\text{il} \mid \langle s \rangle) = 3/3 = 1\);

• «il» compare 4 volte, seguito 3 volte da «gatto» e 1 da «cane»: \(P(\text{gatto} \mid \text{il}) = 3/4 = 0{,}75\) e \(P(\text{cane} \mid \text{il}) = 0{,}25\);

• «gatto» compare 3 volte, seguito 2 volte da «nero» e 1 da «bianco»: \(P(\text{nero} \mid \text{gatto}) = 2/3\);

• «nero» compare 2 volte: una seguita da «salta», una a fine frase: \(P(\text{salta} \mid \text{nero}) = 0{,}5\);

• «sul» compare 2 volte, seguito una volta da «muro» e una da «divano»: \(P(\text{muro} \mid \text{sul}) = 0{,}5\).

La probabilità della frase intera è il prodotto delle scommesse lungo la catena. Prodotto e non somma, per la stessa ragione per cui la probabilità di fare sei due volte di fila è un sesto di un sesto: perché la frase esca tutta quanta devono andare in porto tutte le scommesse, una dopo l’altra, e ciascuna si gioca su quello che è già uscito.

\[\begin{split} \begin{aligned} P(\text{il gatto nero salta sul muro}) &= 1 \cdot 0{,}75 \cdot \tfrac{2}{3} \cdot 0{,}5 \cdot 1 \cdot 0{,}5 \cdot 1 \\ &= 0{,}125, \end{aligned} \end{split}\]

dove i sette fattori sono, nell’ordine: «il» a inizio frase, «gatto» dopo «il», «nero» dopo «gatto», «salta» dopo «nero», «sul» dopo «salta» (unica continuazione vista: probabilità 1), «muro» dopo «sul», e la chiusura di frase dopo «muro».

Un ottavo, detto così, sembra poco. Il metro giusto è un altro: quante frasi diverse potrebbe produrre questo modello? Infinite, perché in qualche punto la strada si biforca, e da «guarda» si torna a «il», così che il giro «il cane guarda il» si può ripetere quante volte si vuole. Un ottavo di tutta quella probabilità concentrato su una frase sola è moltissimo: se il modello si mettesse a inventare frasi, una volta su otto tirerebbe fuori esattamente questa. E non è perché la conosce a memoria. Le biforcazioni la trattano come tutte le altre, tanto che «il gatto bianco dorme sul muro», che nel corpus non c’è, prende lo stesso ottavo; e «il gatto nero», che si ferma prima, prende addirittura un quarto. A decidere sono le biforcazioni, non quello che il modello ha visto scritto.

Gli zeri, o la maledizione delle coppie mai viste

Ora proviamo con «il cane nero salta sul divano». Frase italiana ineccepibile, eppure il modello la boccia senza appello: la coppia «cane nero» non compare mai nel corpus, quindi \(P(\text{nero} \mid \text{cane}) = 0\), e uno zero nel prodotto azzera tutto. Il modello confonde «mai visto» con «impossibile».

È la regola, e non un difetto del nostro corpus giocattolo, e i conti si fanno in fretta. Jurafsky e Martin [JM26] prendono l’opera omnia di Shakespeare: circa 884.000 parole in tutto, ma parole diverse solo 29.000, perché le stesse tornano di continuo. Le coppie possibili sono allora 29.000 per 29.000, cioè poco più di 800 milioni. Le coppie che Shakespeare ha davvero scritto, contate nelle edizioni precedenti dello stesso manuale, sono circa 300.000: vuol dire che il 99,96 per cento delle coppie possibili non compare mai, nemmeno una volta, in tutto Shakespeare.

E Shakespeare è un corpus generoso. Qualunque testo nuovo conterrà coppie legittime che il modello non ha mai visto: il quaderno è quasi tutto bianco, e questa è la condizione normale del linguaggio, non l’eccezione (in gergo la si chiama sparsità). I rimedi si chiamano smoothing, lisciamento: togliere un po’ di probabilità alle coppie viste per regalarne un po’ a quelle mai viste.

Elementare

La pagina del quaderno intestata a «cane» ha una riga sola. Dopo «cane» è venuto «guarda», una volta. Le altre undici righe sono bianche, e una riga bianca vale zero.

Il rimedio più semplice l’abbiamo già incontrato nel filtro antispam, la «regola del +1» di Laplace, che passa sul quaderno e segna un trattino su ogni riga, anche sulle bianche. Le righe sono dodici, le undici parole del corpus più il segnale di fine frase. Per «cane nero», sopra, al posto dello zero va il trattino appena regalato: 1. Sotto vanno le volte in cui «cane» è comparso (una sola) più i 12 trattini appena distribuiti, cioè \(1 + 12 = 13\). «Nero dopo cane» passa da 0 a \(1/13\), circa 0,08. Piccola, ma viva.

Il regalo lo pagano i ricchi. La pagina di «il» dava «gatto» a \(3/4 = 0{,}75\); adesso sopra c’è \(3 + 1\) e sotto ci sono le 4 comparse di «il» più i 12 trattini, cioè \((3+1)/(4+12) = 4/16 = 0{,}25\). La fiducia di quella pagina è un piatto solo, e ora si divide fra dodici righe, dieci delle quali sono rimaste sempre bianche. Con un vocabolario vero, decine di migliaia di righe per pagina, il +1 porta quasi tutto il piatto ai fantasmi. Un trattino più magro, mezzo o un decimo, ne fa scivolare meno; ma lo fa scivolare sempre in parti uguali su ogni riga bianca.

Il quaderno però non è uno. Accanto a quello delle coppie ce n’è un altro, più povero e più pieno, che segna soltanto quanto è comune ogni parola, senza guardare che cosa la precedeva. Quando la riga della coppia è bianca si chiude il primo e si apre il secondo, dove la domanda è più facile: quanto è comune «nero». Anche questa risposta va pagata, perché il piatto deve restare intero. Invece di regalare un trattino a chiunque, si trattiene un poco da ogni coppia vista, e quel mucchietto è tutto ciò che si spartisce fra le righe mancanti.

Meglio ancora, non aspettare la riga bianca. Si tengono aperti tutti e due i quaderni a ogni parola e si fa la media dei due giudizi. Il primo è preciso quando la riga c’è e muto quando manca; il secondo risponde sempre, e risponde generico. Alla media si dà più peso al primo quando ha qualcosa da dire, e con le terne di parole i quaderni da tenere aperti diventano tre. Quanto peso non lo si decide a occhio. Si mettono da parte alcune frasi, senza segnarle nel quaderno, e si tiene il dosaggio che ne indovina meglio il seguito.

Superiore

Lo smoothing add-1 di Laplace (identico a quello visto per Naive Bayes) somma 1 a ogni conteggio:

\[ P_{+1}(w_t \mid w_{t-1}) = \frac{C(w_{t-1}\, w_t) + 1}{C(w_{t-1}) + |V|}, \]

dove \(|V|\) è la dimensione del vocabolario, che compare al denominatore perché il +1 va garantito a tutte le \(|V|\) continuazioni possibili. Sul corpus giocattolo \(|V| = 12\), cioè le undici parole diverse più </s>, che è una continuazione come le altre; <s> non c’è, perché non si predice mai: \(P_{+1}(\text{nero} \mid \text{cane}) = (0+1)/(1+12) \approx 0{,}077\), ma \(P_{+1}(\text{gatto} \mid \text{il}) = (3+1)/(4+12) = 0{,}25\), contro lo \(0{,}75\) della stima MLE. Add-1 sposta troppa massa verso l’inosservato: tanto che al posto suo si prova la variante add-\(k\), che regala \(k \ll 1\) invece di \(1\) e mette \(k|V|\) al denominatore. Sposta meno massa, ma il regalo resta spalmato in parti uguali su ogni continuazione mai vista, e per un modello di linguaggio non funziona bene lo stesso. Le alternative serie sono due, spesso combinate:

• interpolazione: mescolare sempre gli ordini,

  \[ \hat{P}(w_t \mid w_{t-1}) = \lambda_1\, P(w_t) + \lambda_2\, P(w_t \mid w_{t-1}), \qquad \lambda_1 + \lambda_2 = 1, \]

  dove i pesi \(\lambda_i\) non si fissano a mano ma si ottimizzano su un insieme di validazione (e con i trigrammi si aggiunge un terzo termine). È l’interpolazione lineare di Jelinek e Mercer, e in una versione più fine i pesi dipendono dal contesto, \(\lambda_i(w_{t-1})\): più peso alla coppia proprio là dove la coppia è stata vista spesso;

• backoff: usare l’ordine alto quando il suo conteggio è positivo e ripiegare sull’ordine inferiore altrimenti. Nella forma classica è il backoff di Katz (1987), e i fattori in gioco sono due, con due mestieri distinti: lo sconto di Good e Turing, che ri-stima verso il basso i conteggi piccoli, e un peso di ripiego che rimette la probabilità totale a

  1. La variante a sconto costante, quella che serve a Kneser–Ney, si chiama invece sconto assoluto: si toglie sempre la stessa quantità, qualunque sia il conteggio di partenza.

Il confronto sistematico tra queste famiglie è lo studio empirico di Chen e Goodman [CG99], per anni la bussola di chi costruiva modelli n-gram.

C’è però una trappola sottile nel ripiegare sulla parola singola, e la si racconta con un esempio diventato canonico. In un corpus americano la parola Francisco è frequente (si parla spesso di San Francisco) ma compare praticamente solo dopo San. Se il bigramma non sa che pesci pigliare e tu ripieghi sulla frequenza pura, finirai per scommettere Francisco in posti dove non può stare: «I can’t see without my reading ___» completato con Francisco invece che con glasses. L’italiano ha gli stessi fantasmi: «soppiatto» non è una parola rara, ma vive quasi soltanto nella coppia fissa «di soppiatto». La frequenza di una parola non dice quanto è versatile.

Elementare

Due conoscenti. Il primo compare in mille foto, ma sempre alla stessa festa: inseparabile dal padrone di casa, mai visto altrove. Il secondo compare in cento foto, ma di cento feste diverse. Chi è più probabile incontrare a una festa nuova? Il secondo, ovviamente: il primo è frequente, ma non va da nessuna parte senza il suo amico.

Da qui il rimedio proposto nel 1995 da Reinhard Kneser e Hermann Ney, che è tutto in una riga: quando devi ripiegare sulla parola singola, non chiederti «quante volte l’ho vista?» ma «dopo quante parole diverse l’ho vista?». «Francisco» e «soppiatto» hanno conteggi alti e una compagnia sola: come riempitivi di buchi nuovi valgono poco. Una parola vista dopo cento parole diverse, invece, è una buona scommessa quasi ovunque.

Il mucchietto messo da parte ha adesso una misura e una destinazione. A ogni coppia vista si toglie sempre la stessa quantità, tre quarti di unità: una coppia vista dieci volte scende a 9,25, una vista una volta sola scende a 0,25. Chi ne aveva molti quasi non se ne accorge, chi ne aveva uno solo ne perde tre quarti, ed è giusto, perché una coppia vista una volta sola poteva essere un caso. Poi si spartisce in proporzione alle feste girate, così che chi era frequente ma sempre allo stesso posto non ne prenda quasi niente. Il piatto resta intero, cambia soltanto come lo si divide.

Superiore

Lo smoothing di Kneser–Ney [KN95] sostituisce, nel termine di ripiego, la frequenza unigramma con la probabilità di continuazione:

\[ P_{\text{cont}}(w) = \frac{\bigl|\{\, w' : C(w'\, w) > 0 \,\}\bigr|} {\bigl|\{\, (u, v) : C(u\, v) > 0 \,\}\bigr|}, \]

dove il numeratore conta i contesti distinti in cui \(w\) è comparsa (quante parole diverse l’hanno preceduta almeno una volta) e il denominatore è il numero di bigrammi distinti del corpus, che normalizza. Per «Francisco» il numeratore vale 1, o poco più, per quanto alta sia la sua frequenza. Il lavoro del 1995 lo mette in un modello di ripiego, ed è quello che dice il suo titolo, Improved Backing-off for M-gram Language Modeling. La forma interpolata, quella che si usa oggi, è di Chen e Goodman [CG99], che ne danno una derivazione diversa e misurano che batte sistematicamente quella di ripiego; sul modello bigramma è

\[ P_{KN}(w_t \mid w_{t-1}) = \frac{\max\bigl(C(w_{t-1}\, w_t) - d,\; 0\bigr)}{C(w_{t-1})} + \lambda(w_{t-1})\, P_{\text{cont}}(w_t), \]

dove \(d\) è uno sconto assoluto (tipicamente intorno a \(0{,}75\)) sottratto a ogni conteggio positivo, e \(\lambda(w_{t-1})\) è il coefficiente che raccoglie esattamente la massa scontata e la ridistribuisce secondo \(P_{\text{cont}}\), così che le probabilità sommino a 1. La variante «modificata» di Chen e Goodman (tre sconti diversi a seconda che il conteggio valga 1, 2 o di più) è la vincitrice sistematica del loro studio, con le parole degli autori: batte «consistentemente» tutti gli altri algoritmi provati. Da lì in poi è la linea di base con cui ogni modello n-gram si confronta, ed è l’unico che KenLM, il costruttore più usato, sappia fare.

La pagella della scommettitrice: la perplessità

Come si misura se un modello di linguaggio scommette bene? Con la perplessità, e l’immagine da tenere è quella del dado: la perplessità dice con quante facce è il dado su cui il modello sta tirando a ogni scommessa. Perplessità 2, e il modello esita fra due parole soltanto; perplessità 100, e ne ha davanti cento tutte ugualmente plausibili. Più il numero è basso, meglio scommette. Nel capitolo sui richiami di matematica l’avevamo definita nella sezione sulla teoria dell’informazione, promettendo di riprenderla numeri alla mano: eccoci.

Elementare

Il conto si fa in tre mosse, e sulla nostra frase si può seguire tutto a mano.

Prima mossa: moltiplicare le scommesse. Sono quelle appena calcolate, \(1 \times 0{,}75 \times \frac{2}{3} \times 0{,}5 \times 1 \times 0{,}5 \times 1 = 0{,}125\), cioè un ottavo. Sono sette fattori, uno per ogni scommessa: le sei parole della frase più la chiusura, che è una scommessa anche lei (il modello deve decidere che la frase finisce lì). Il segnale di inizio, invece, fra le scommesse non ci va: la scommessa sulla prima parola c’è ed è il primo dei sette fattori, ma il segnale che le fa da «prima» non lo indovina nessuno, c’è e basta. Contarlo sarebbe come mettere in pagella un esame che passano tutti, e il voto migliorerebbe senza che nessuno abbia studiato di più.

Seconda mossa: capovolgere. Uno diviso un ottavo fa 8. Capovolgere serve a rimettere le cose nel verso in cui le vogliamo leggere: più la frase era probabile, più il numero di partenza era grande, e più questo viene piccolo. Otto è dunque quanto il modello ha «esitato» sull’intera frase. Ma dipende da quanto la frase è lunga: una frase doppia esita di più anche se il modello è identico, e così non si possono confrontare due frasi diverse.

Terza mossa: riportare alla singola scommessa. Le scommesse erano sette, e il conto totale è stato un prodotto di sette fattori: cerchiamo allora il numero che, moltiplicato per sé stesso fino a fare sette fattori, dà 8. È la radice settima di 8, parente stretta della radice quadrata (che è lo stesso gioco con due fattori invece di sette), e vale circa 1,35: infatti \(1{,}35\) elevato a \(7\) fa poco più di \(8\), e chiunque può verificarlo con la calcolatrice del telefono. Ecco la perplessità: un dado da 1,35 facce, cioè quasi nessun dubbio.

Superiore

Su una sequenza di \(N\) token la perplessità è

\[ \mathrm{PP} = P(w_1, \dots, w_N)^{-1/N}, \]

cioè l’inverso della probabilità del testo, riportato «per token» dalla media geometrica: è la stessa quantità \(2^H\) della teoria dell’informazione, con \(H\) la cross-entropia media per token misurata in bit, cioè con il logaritmo in base due, che è la base del math.log2 con cui il programma del bigramma fa il conto. E «cross-entropia» è il nome di un limite, il tasso di cross-entropia: quello che si misura su un testo finito è la log-verosimiglianza media per token cambiata di segno, che a quel limite tende soltanto se il processo che genera il testo è stazionario ed ergodico e il testo è abbastanza lungo. Su una frase di sette token è un nome generoso.

Un avvertimento sul conto di \(N\), perché è il punto esatto in cui si sbaglia. Con le frasi incorniciate fra <s> e </s>, anche </s> è una scommessa e va contato fra gli \(N\); <s> invece no, perché non lo si predice mai: è il contesto da cui parte la prima scommessa. Su «il gatto nero salta sul muro» gli \(N\) sono quindi sette, non sei, ed è la convenzione di Jurafsky e Martin [JM26] oltre che quella del programma del bigramma. Contare anche <s> sbaglierebbe nel verso che meno ci si aspetta. Incatenando le frasi, dopo </s> viene <s> con probabilità quasi 1, quindi si aggiungerebbe un fattore che lascia il prodotto dov’è e un token che porta \(N\) a otto. La radice si fa di grado più alto e la perplessità cala, cioè migliora, e sulla frase di prima si passerebbe da \(8^{1/7} \approx 1{,}35\) a \(8^{1/8} \approx 1{,}30\) a parità di scommesse.

Fig. 14.13 La perplessità nasce parola per parola: si moltiplicano le scommesse e si riporta il risultato a una sola, con la radice. La chiusura di frase è una scommessa come le altre, e infatti ha il suo riquadro. Nessuna parola, da sola, decide il punteggio.

Un limite però ce l’ha, e la Fig. 14.13 lo lascia vedere su un’altra frase, «Il gatto dorme sul divano», con le probabilità di un modello qualunque. Le scommesse entrano tutte con lo stesso peso, un sesto a testa, e a fare la differenza è solo quanto ciascuna sorprende: quella su «il», che vale 0,60, pesa il sette per cento del punteggio, quella su «divano», che vale 0,12, il ventinove. Ma in un testo vero le parole ovvie sono la stragrande maggioranza e quelle su cui si gioca la qualità sono una manciata, così la media annega le seconde nelle prime: un modello può cavarsela benissimo nel punteggio complessivo inciampando esattamente dove contava.

Lo stesso conto, scritto in una riga. Il bigramma a conteggi grezzi, senza nessun aggiustamento, dava alla frase «il gatto nero salta sul muro» probabilità \(0{,}125\) in 7 scommesse (sei parole più la chiusura di frase):

\[ \mathrm{PP} = 0{,}125^{-1/7} = 8^{1/7} \approx 1{,}35. \]

L’esponente sono le due mosse di prima scritte in una volta: il segno meno capovolge (\(0{,}125\) diventa 8) e l’un settimo è la radice settima.

Un dado da 1,35 facce: quasi nessun dubbio. Troppo bello per essere onesto, e intanto stiamo barando su una cosa: abbiamo valutato il modello sulla frase con cui l’abbiamo addestrato, che è la prima del corpus. La perplessità va sempre misurata su un testo di test, mai visto in addestramento; e lì, senza smoothing, basta un bigramma nuovo per mandarla a infinito.

Rifacciamo dunque il confronto come si deve, con il modello lisciato alla Laplace e su tre frasi che il modello non ha mai letto. La prima, «il gatto nero salta sul divano», è nuova ma tutta fatta di coppie già viste, e la chiameremo la frase senza sorprese. La seconda, «il cane nero salta sul divano», è quella stessa con dentro una coppia mai vista. La terza è la prima riscritta all’incontrario, «divano sul salta nero gatto il», ed è la frase rovesciata. Il programma del bigramma dà 5,5 alla frase senza sorprese, 7,0 a quella con la coppia mai vista, 14,2 a quella rovesciata.

Conviene guardare da dove viene quel 5,5, perché la lettura più naturale è sbagliata. Non è il prezzo di aver smesso di barare: sulla frase senza sorprese il bigramma a conteggi grezzi dà di nuovo 1,35, la stessa identica cifra della frase di addestramento, perché su un corpus di tre frasi «muro» e «divano» sono gemelli statistici. Il salto da 1,35 a 5,5 è tutto del lisciamento, che toglie probabilità alle coppie viste per regalarla a quelle mai viste, e su un vocabolario di dodici parole quel regalo è enorme. La misura onesta è il 5,5. L’1,35 di prima era ottimista per due ragioni, il testo di prova e i conteggi grezzi; qui pesa solo la seconda, perché il corpus è così piccolo che una frase nuova e una vista sono la stessa cosa, ma su un corpus vero la prima pesa quanto e più.

Restano i due confronti fra le tre frasi, e ciascuno dice una cosa sua. Dalla frase senza sorprese a quella con la coppia mai vista: quell’unica coppia fa salire la perplessità di poco più di un quarto, da 5,5 a 7,0. Dalla frase senza sorprese a quella rovesciata: le stesse identiche sei parole, in ordine diverso, la fanno più che raddoppiare, da 5,5 a 14,2, cioè due volte e mezzo abbondanti.

È qui che l’ordine delle parole, che il sacchetto della sezione precedente buttava via, si prende la rivincita: il modello non guarda niente più che le coppie di parole vicine, e tanto basta a distinguere una frase italiana da un mucchio di parole italiane.

Per le grandezze reali, nell’esperimento classico riportato da Jurafsky e Martin [JM26], tre modelli addestrati su 38 milioni di parole del Wall Street Journal e messi alla prova su un milione e mezzo di parole tenute da parte, con lo stesso vocabolario chiuso di ventimila parole per tutti e tre (senza quella condizione due perplessità non si confrontano), la perplessità scende da circa 960 con l’unigramma (il modello che scommette guardando solo quanto una parola è comune, senza nemmeno l’ultima parola letta: è il gradino sotto il bigramma) a 170 col bigramma e a circa 110 col trigramma. I modelli neurali che incontreremo faranno molto meglio, ma sulla stessa pagella.

La passeggiata del bigramma

Un modello che assegna probabilità sa anche generare. Si parte dal segnale di inizio frase e si guarda la pagina del quaderno intestata a lui: dice che dopo l’inizio è sempre venuto «il». Si scrive «il», si va alla sua pagina, e lì si trova che tre volte su quattro è seguito da «gatto» e una volta su quattro da «cane». Adesso si sorteggia, ma non con un dado onesto: con un sorteggio truccato secondo quei conteggi, in cui «gatto» ha tre biglietti su quattro e «cane» uno. Immaginate un sacchetto con dentro quattro foglietti, tre con scritto «gatto» e uno con scritto «cane»: si pesca a occhi chiusi. Poi si riparte dalla parola pescata e si pesca ancora, fino al segnale di fine. È esattamente il gioco dei libri sfogliati a caso di Shannon, automatizzato.

Sul nostro corpus di tre frasi la passeggiata produce cose come «il cane guarda il cane guarda il gatto nero» (Fig. 14.14): ogni passo è impeccabile (tutte coppie viste nel corpus) ma la frase gira in tondo. Su corpora veri l’effetto è identico, solo più elegante: come nelle approssimazioni di Shannon, il testo suona giusto da vicino ed è sconnesso da lontano.

Fig. 14.14 Una passeggiata, passo per passo. Sopra cresce la frase; sotto si apre ogni volta la pagina del quaderno intestata all’ultima parola scritta, con i foglietti che ci sono dentro e quello pescato. I due archetti segnano le volte in cui da «guarda» si torna a «il», che è il modo in cui il testo gira in tondo: nessuna delle scommesse è sbagliata, e il giro si chiude lo stesso.

Elementare

La nostra scommettitrice ha una memoria da pesce rosso: quando sceglie la parola nuova, ricorda solo l’ultima scritta (o le ultime due). È come attraversare una città chiedendo indicazioni a un passante diverso a ogni incrocio, senza mai dire da dove sei partito: ogni singolo consiglio è ragionevole, il percorso complessivo non porta da nessuna parte.

Allungare la memoria sembrerebbe facile: invece di coppie, terne; invece di terne, quaterne… Ma il quaderno esplode: per ogni parola in più da ricordare, le pagine si moltiplicano per tutto il vocabolario, e quasi tutte resterebbero bianche (combinazioni mai viste nemmeno in una biblioteca). E c’è un difetto più sottile: per il quaderno «gatto» e «micio» sono estranei totali. Aver letto mille volte «il gatto dorme» non lo aiuta di un grammo a scommettere su «il micio dorme». Servirebbe un modello che capisca che parole simili meritano scommesse simili. Quel modo di scrivere le parole il libro l’ha già montato, ed è quello che colloca «gatto» e «micio» vicini invece di trattarli come due numeri qualunque; le reti che scommettono sono la mossa che resta da fare.

Superiore

I limiti del modello n-gram sono strutturali, non di taratura:

• Crescita esponenziale dello spazio dei contesti. Gli n-gram possibili sono \(|V|^{\,n}\) (i contesti sono \(|V|^{\,n-1}\), ciascuno con \(|V|\) continuazioni): con un vocabolario di 50.000 parole, i bigrammi possibili sono \(2{,}5 \times 10^9\) e i trigrammi \(1{,}25 \times 10^{14}\). In memoria finiscono solo quelli visti, che sono pochissimi, ed è proprio questo il punto: oltre \(n = 4\) o \(5\) il guadagno si assottiglia e a decidere diventa la sparsità.

• Nessuna generalizzazione tra parole simili. Gli n-gram vivono nello spazio dei simboli discreti: \(C(\text{il gatto dorme})\) non trasferisce nulla a \(P(\text{dorme} \mid \text{il micio})\), perché «gatto» e «micio» sono ID distinti senza geometria. Gli embedding della sezione su come rappresentare il testo risolvono esattamente questo, collocando le parole in \(\mathbb{R}^d\) dove la similarità è misurabile.

La sintesi delle due cure è il modello di linguaggio neurale proposto da Yoshua Bengio e colleghi nel 2003 (embedding più rete feed-forward su una finestra fissa) e soprattutto le RNN della prossima sezione, il cui stato nascosto riassume in un vettore di dimensione fissa tutto il prefisso, non le ultime \(n-1\) parole. La scommessa resta identica, \(P(w_t \mid w_{<t})\), addestrata con la stessa cross-entropia e valutata con la stessa perplessità: cambia solo quanta memoria porta con sé lo scommettitore. Portata all’estremo (con i Transformer) questa identica scommessa diventerà GPT [BMR+20].

Un bigramma in quaranta righe di Python

Tutto ciò che serve è contare. Il codice che segue costruisce il bigramma sul corpus di tre frasi e non usa niente che non sia già dentro Python.

Il programma fa quattro cose, nell’ordine. La prima è il quaderno: scorre le tre frasi coppia per coppia e tiene il conto di quante volte ogni parola ne segue un’altra. La seconda sono le due frazioni, quella grezza e quella con il regalo di Laplace, che sono le stesse di qualche pagina fa. La terza è la passeggiata: parte dal segnale di inizio e pesca dal sacchetto dei foglietti finché non trova il segnale di fine. La quarta è la pagella: moltiplica le scommesse di una frase, capovolge, prende la radice, cioè le tre mosse della perplessità (con i logaritmi al posto delle moltiplicazioni, che è lo stesso conto scritto in modo che il computer non perda cifre per strada).

import math
import random
from collections import Counter, defaultdict

corpus = [
    "il gatto nero salta sul muro",
    "il gatto bianco dorme sul divano",
    "il cane guarda il gatto nero",
]

INIZIO, FINE = "<s>", "</s>"

# 1. Conteggi: conta[w1][w2] = quante volte w2 segue w1
conta = defaultdict(Counter)
for frase in corpus:
    parole = [INIZIO] + frase.split() + [FINE]
    for w1, w2 in zip(parole, parole[1:]):
        conta[w1][w2] += 1

vocabolario = {w for frase in corpus for w in frase.split()} | {FINE}
V = len(vocabolario)                      # 12: 11 parole + </s>

# 2. Probabilita': massima verosimiglianza e Laplace
def p_mle(w1, w2):
    tot = sum(conta[w1].values())
    return conta[w1][w2] / tot if tot else 0.0

def p_laplace(w1, w2):
    return (conta[w1][w2] + 1) / (sum(conta[w1].values()) + V)

print(p_mle("il", "gatto"))       # 0.75
print(p_mle("cane", "nero"))      # 0.0 -> lo zero che azzera tutto
print(p_laplace("cane", "nero"))  # 0.0769... -> piccola ma viva

# 3. Generazione: una passeggiata di scommesse da <s> a </s>
def genera(seme):
    rng = random.Random(seme)
    parola, frase = INIZIO, []
    while len(frase) < 20:
        seguiti = conta[parola]
        parola = rng.choices(list(seguiti), weights=seguiti.values())[0]
        if parola == FINE:
            break
        frase.append(parola)
    return " ".join(frase)

for seme in range(3):
    print(genera(seme))
# il cane guarda il gatto nero
# il cane guarda il gatto nero
# il cane guarda il cane guarda il gatto nero

# 4. Perplessita' di una frase secondo il modello lisciato
def perplessita(frase):
    parole = [INIZIO] + frase.split() + [FINE]
    log2p = sum(math.log2(p_laplace(w1, w2))
                for w1, w2 in zip(parole, parole[1:]))
    return 2 ** (-log2p / (len(parole) - 1))

# nessuna delle tre e' nel corpus di addestramento: si valuta su testo nuovo
print(perplessita("il gatto nero salta sul divano"))  # ~5.5  senza sorprese
print(perplessita("il cane nero salta sul divano"))   # ~7.0  coppia mai vista
print(perplessita("divano sul salta nero gatto il"))  # ~14.2 la rovesciata

La generazione con il seme 2 inciampa nell’anello «il cane guarda il cane guarda…»: a ogni passo il bigramma vede solo l’ultima parola, e da «guarda» si torna legittimamente a «il». E le tre perplessità raccontano la storia giusta, tutte e tre su frasi che il modello non ha mai letto: bassa per la frase senza sorprese, un quarto abbondante più alta per quella con la coppia mai vista, e due volte e mezzo tanto per la rovesciata, che ha esattamente le stesse parole della prima. Con la matita al posto di Python, sono i conti che Markov fece nel 1913.

Gli n-gram non sono morti

Sarebbe facile chiudere con «poi arrivarono le reti neurali e gli n-gram finirono in soffitta». Non è andata così, e l’onestà storica impone di dirlo. Contare è imbattibilmente economico. Addestrare una rete neurale vuol dire ripassare sugli stessi dati decine di volte, aggiustando ogni volta milioni di numeri con quel segnale di ritorno che si chiama gradiente, e per farlo in tempi umani serve una scheda grafica, una GPU. Costruire un n-gram vuol dire leggere il corpus una volta sola e riempire un quaderno; usarlo vuol dire aprire il quaderno alla pagina giusta. Nessuna scheda grafica, nessun gradiente, nessuna attesa. Nel 2006 Google distribuì i conteggi fino ai 5-grammi estratti da circa mille miliardi di parole di web: modelli giganteschi costruiti, in fondo, con la matita di Markov. Per anni la barra dei suggerimenti delle tastiere dei telefoni è stata proprio questo (un n-gram con smoothing, piccolo e veloce abbastanza da girare sul dispositivo), oggi affiancato da reti compatte che girano sullo stesso dispositivo. E nel riconoscimento vocale, come vedremo nel capitolo sullo Speech Recognition, un modello di linguaggio si fonde ancora col modello acustico per scegliere fra trascrizioni identiche all’orecchio («l’ago» o «lago») e per anni quel correttore silenzioso è stato un n-gram alla Kneser–Ney. Quando serve una probabilità subito, su hardware qualunque, contare resta un’ottima idea.

Ma il soffitto degli n-gram è quello che abbiamo toccato con mano: memoria corta per costruzione, e nessuna nozione del fatto che «gatto» e «micio» si somiglino. La prossima sezione riparte esattamente da qui: la stessa scommessa sulla parola successiva, affidata però a una rete che porta con sé, parola dopo parola, un riassunto dell’intera frase.

Elementare

Da ricordare

• Un modello di linguaggio scommette su quale parola viene dopo, e la probabilità di una frase intera è il prodotto di tutte quelle scommesse in fila. L’idea nasce con Markov, che nel 1913 conta a matita le lettere dell’Onegin, e con le «approssimazioni» di Shannon del 1948, costruite sfogliando libri a caso.

• Il patto degli n-gram: fingere che conti solo l’ultima parola letta (le coppie, il bigramma) o le ultime due (le terne, il trigramma), perché una frase intera non si ripete quasi mai e di lei non si potrebbe contare niente. Le scommesse stanno in un quaderno, una pagina per parola, con sopra le parole che l’hanno seguita e quante volte.

• Una coppia mai vista vale zero, e uno zero azzera l’intera frase: il modello confonde «mai visto» con «impossibile». Il rimedio più semplice è la regola del \(+1\) (un conteggio regalato a tutti), ma con un vocabolario vero quel regalo si mangia quasi tutta la probabilità, che finisce alle coppie mai viste. Meglio mescolare il giudizio della coppia con quello della parola singola, o ripiegare sulla seconda quando la prima manca; e meglio ancora, con Kneser–Ney, chiedersi non quante volte una parola è comparsa ma in quanti posti diversi («Francisco» è frequentissimo ma non va da nessuna parte senza «San»).

• La perplessità è la pagella: il numero di facce del dado con cui il modello esita a ogni scommessa, e più è basso meglio scommette. Va misurata su testo mai letto in addestramento, altrimenti si sta barando.

• Un n-gram sa anche generare, tirando il suo dado truccato una parola alla volta: il risultato suona giusto da vicino e non porta da nessuna parte da lontano, perché la memoria è da pesce rosso. Allungarla riempie il quaderno di pagine bianche, e comunque per il quaderno «gatto» e «micio» restano due estranei: sono le due ragioni che portano alle reti della prossima sezione.

• Gli n-gram non sono morti: le tastiere che suggeriscono la parola, la spalla del riconoscimento vocale, un metro di paragone velocissimo che gira su qualunque computer, senza GPU.

Superiore

Da ricordare

• Un modello di linguaggio assegna una probabilità a una frase scomponendola, con la regola della catena, in scommesse sulla parola successiva; l’idea nasce con i conteggi a mano di Markov sull’Onegin (1913) e con le «approssimazioni» di Shannon (1948).

• L’assunzione di Markov tronca la storia alle ultime \(n-1\) parole: bigrammi, trigrammi. La stima MLE è un rapporto di conteggi: \(C(w_{t-1} w_t) / C(w_{t-1})\).

• I conteggi zero confondono «mai visto» con «impossibile»: servono gli smoothing. Il +1 di Laplace è semplice ma sposta troppa massa; l’interpolazione mescola sempre gli ordini, il backoff commuta fra l’uno e l’altro; Kneser–Ney sostituisce la frequenza con i contesti distinti («Francisco» è frequente ma vive solo dopo «San»), nasce come modello di ripiego e si usa nella forma interpolata di Chen e Goodman, che è la linea di base rimasta fino all’era neurale.

• La perplessità (il \(2^H\) della teoria dell’informazione) è la pagella: va misurata su testo di test, mai su quello di addestramento.

• Un n-gram genera testo campionando scommessa dopo scommessa: giusto da vicino, sconnesso da lontano. I limiti sono strutturali: contesti \(|V|^{\,n-1}\) e nessuna generalizzazione tra parole simili; le ragioni che portano alle RNN della prossima sezione.

• Gli n-gram non sono morti: tastiere predittive, fusione col modello acustico del riconoscimento vocale, baseline velocissime senza GPU.