Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank

La proprietà di Markov, la matrice di transizione e l’evoluzione della distribuzione in un modello del tempo, la distribuzione stazionaria e il teorema ergodico, l’analisi delle vocali di Markov applicata al Máj di Mácha, il PageRank e la generazione di testo.

13 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 38 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Nel 1913 il matematico russo Andrej Markov sedeva davanti all’Evgenij Onegin di Puškin e faceva una cosa che uno studioso di letteratura considererebbe una barbarie: contava quante volte una vocale è seguita da un’altra vocale. Voleva dimostrare che la legge dei grandi numeri vale anche per eventi che dipendono l’uno dall’altro — e nel farlo inventò un modello che oggi calcola l’ordine delle pagine nei motori di ricerca, prevede il tempo, genera testo e sta alla base di un’intera famiglia di algoritmi di intelligenza artificiale. Con questa parte comincia il modulo sui modelli probabilistici.

Si collega alle parti Probabilità condizionata e teorema di Bayes e Algebra lineare per l’apprendimento automatico.

1. Un processo senza memoria

Definizione — catena di Markov

Una successione di variabili casuali X₀, X₁, X₂, … a valori in un insieme finito di stati S è una catena di Markov se per ogni t e per tutti gli stati vale la proprietà di Markov

P(X_t+1 = j | X_t = i, X_t−1, …, X₀) = P(X_t+1 = j | X_t = i).

Se questa probabilità non dipende da t, la catena è omogenea.

Che cosa porta la proprietà di Markov si vede dalla probabilità di un’intera traiettoria. In generale si scompone con la regola della catena in un prodotto di probabilità condizionate, ciascuna delle quali dipende da tutto il passato. La proprietà di Markov cancella da ogni condizione tutto tranne l’ultimo stato:

P(X₀ = x₀, …, X_T = x_T) = π₀(x₀) · ∏_t=1^T P(x_t | x_t−1)

P(X₀ = x₀, …)

probabilità che la catena percorra esattamente questa successione di stati

π₀(x₀)

distribuzione iniziale — da dove parte la catena la matrice non lo dice; questo dato deve arrivare dall’esterno

∏_t=1^T

prodotto sui passi — i passi si susseguono e ognuno deve «riuscire», per questo si moltiplicano

P(x_t | x_t−1)

probabilità di transizione di un passo, cioè l’elemento della matrice di transizione nella riga x_t−1 e nella colonna x_t — grazie alla proprietà di Markov dipende solo dallo stato precedente, non da tutta la storia; senza di essa qui ci sarebbe P(x_t | x₀, …, x_t−1)

2. La matrice di transizione

Definizione — matrice di transizione

Una catena omogenea con n stati è determinata dalla matrice di transizione P = (p_ij), dove p_ij = P(X_t+1 = j | X_t = i). La matrice è stocastica: p_ij ≥ 0 e ogni riga ha somma 1.

Un modello giocattolo del tempo con tre stati: dopo un giorno sereno, con probabilità 0,6 è di nuovo sereno, con 0,3 nuvoloso e con 0,1 piove; dopo uno nuvoloso 0,3 / 0,4 / 0,3; dopo uno piovoso 0,2 / 0,4 / 0,4. Come grafo:

La stessa informazione come matrice — la riga è il tempo di oggi, la colonna quello di domani:

Esempio — probabilità di una traiettoria

Oggi è sereno (π₀ = (1; 0; 0)). Qual è la probabilità che i prossimi tre giorni siano sereno, nuvoloso, pioggia? Secondo la formula della traiettoria

P = 1 · p_{sereno→sereno} · p_{sereno→nuvoloso} · p_{nuvoloso→pioggia} = 1 · 0,6 · 0,3 · 0,3 = 0,054.

Cioè il 5,4 %. La somma su tutte le 3³ = 27 possibili terne di giorni è 1 — proprio perché ogni riga della matrice ha somma 1.

3. Come evolve la distribuzione

Teorema — distribuzione dopo n passi

Se π_t è il vettore riga della distribuzione di X_t, allora π_t+1 = π_t P, e quindi π_t = π₀ P^t. L’elemento (i, j) della matrice Pⁿ è la probabilità di passare da i a j in n passi.

π_t+1(j) = ∑_i π_t(i) · p_ij

π_t+1(j)

probabilità che domani lo stato sia j — una componente del nuovo vettore riga

∑_i

somma su tutti gli stati di oggi — in j si può arrivare da qualunque stato e questi percorsi si escludono a vicenda, quindi le loro probabilità si sommano (legge della probabilità totale)

π_t(i)

quanto è probabile che oggi siamo in i — il peso del percorso che passa per i

p_ij

probabilità di transizione da i a j — per la proprietà di Markov basta conoscere lo stato di oggi

Esempio — la distribuzione per dopodomani

Domani (dopo un oggi sereno) è π₁ = (0,6; 0,3; 0,1). Per dopodomani, componente per componente — colonna della matrice moltiplicata per il vettore π₁:

• sereno: 0,6 · 0,6 + 0,3 · 0,3 + 0,1 · 0,2 = 0,36 + 0,09 + 0,02 = 0,47,
• nuvoloso: 0,6 · 0,3 + 0,3 · 0,4 + 0,1 · 0,4 = 0,18 + 0,12 + 0,04 = 0,34,
• pioggia: 0,6 · 0,1 + 0,3 · 0,3 + 0,1 · 0,4 = 0,06 + 0,09 + 0,04 = 0,19.

La somma è di nuovo 1. Fra tre giorni, con lo stesso procedimento, si ottiene (0,422; 0,353; 0,225).

Una cosa interessante: dopo circa una settimana non importa se oggi c’è il sole o piove. Le due distribuzioni si incontrano sugli stessi valori e poi non cambiano più. La catena ha «dimenticato» da dove era partita.

Teorema — quanto in fretta la catena dimentica

Se la matrice P con n stati ha n autovalori distinti 1 = λ₁, λ₂, …, λ_n e |λ_k| < 1 per k ≥ 2, allora ogni distribuzione iniziale si scompone negli autovettori sinistri e

π_t = π + a₂λ₂^tu₂ + … + a_nλ_n^tu_n,

dove π è la distribuzione stazionaria. Lo scarto da π diminuisce quindi come |λ₂|^t, dove λ₂ è il secondo autovalore più grande in valore assoluto.

π_t ≈ π + a₂u₂ · λ₂^t

π_t

distribuzione dopo t giorni

π

distribuzione stazionaria — appartiene all’autovalore 1, che elevando a potenza non cambia; per questo è l’unica parte che sopravvive

a₂u₂

scarto iniziale nella direzione del secondo autovettore — solo qui si vede da dove è partita la catena (sole o pioggia); nella componente sereno è positivo per una partenza serena e negativo per una piovosa

λ₂^t

ogni giorno lo scarto si moltiplica per λ₂ — la velocità con cui la catena dimentica; i termini restanti con |λ| più piccolo spariscono ancora più in fretta, per questo possiamo trascurarli

Esempio — gli autovalori della matrice del tempo

La somma degli autovalori è la traccia della matrice, 0,6 + 0,4 + 0,4 = 1,4, e il loro prodotto è il determinante, che risulta 0,01. Un autovalore è 1 (le righe hanno somma 1), quindi gli altri due soddisfano λ₂ + λ₃ = 0,4 e λ₂λ₃ = 0,01. Sono le radici di λ² − 0,4λ + 0,01 = 0:

λ_2,3 = 0,2 ± √0,03 = (2 ± √3)/10, cioè λ₂ ≈ 0,373 e λ₃ ≈ 0,027.

Lo scarto della probabilità di sereno dal valore stazionario 0,393, partendo da un giorno sereno, è dopo 3, 4, 5 giorni 0,0286; 0,0107; 0,0040 — ogni giorno circa 0,373 volte quello precedente. Dopo una settimana è 0,0006, e partendo da un giorno di pioggia −0,0005: le due partenze differiscono solo alla quarta cifra decimale. Lo scarto si riduce a un centesimo in ln 0,01 / ln 0,373 ≈ 4,7 giorni.

4. La distribuzione stazionaria

Definizione — distribuzione stazionaria

Una distribuzione π è stazionaria se π P = π — cioè π è un autovettore sinistro della matrice P con autovalore 1.

Definizione — catena irriducibile e aperiodica

Indichiamo con p_ij⁽ⁿ⁾ l’elemento (i, j) della matrice Pⁿ, cioè la probabilità di passare da i a j in n passi.

• Una catena è irriducibile se per ogni coppia di stati i, j esiste n ≥ 1 con p_ij⁽ⁿ⁾ > 0.
• Il periodo dello stato i è d(i) = MCD{n ≥ 1 : p_ii⁽ⁿ⁾ > 0} — il massimo comune divisore delle lunghezze di tutti i percorsi che tornano in i. Se d(i) = 1 lo stato è aperiodico; in una catena irriducibile tutti gli stati hanno lo stesso periodo.

Il tempo è subito entrambe le cose: tutti gli elementi di P sono positivi (basta n = 1) e p_ii > 0, quindi il ritorno è possibile in 1 passo e il periodo è 1. Al contrario, una catena con due stati che li alterna regolarmente (p₁₂ = p₂₁ = 1) è irriducibile, ma ha periodo 2: π₀P^t con partenza (1; 0) salta all’infinito tra (1; 0) e (0; 1), anche se la distribuzione stazionaria (½; ½) esiste.

Teorema — teorema ergodico per catene finite

Se una catena finita è irriducibile (da ogni stato si può arrivare in ogni altro) e aperiodica, ha un’unica distribuzione stazionaria π e per ogni distribuzione iniziale π₀ P^t → π. Inoltre la frazione di tempo che la catena trascorre nello stato j tende con probabilità 1 a π_j e il tempo medio di ritorno in j è 1/π_j.

Per il nostro modello la distribuzione stazionaria risulta esattamente (24/61; 22/61; 15/61) ≈ (0,393; 0,361; 0,246): a lungo andare è sereno il 39 % dei giorni, nuvoloso il 36 % e piove nel 25 %. Dopo un giorno di pioggia aspettiamo la pioggia successiva in media 1/0,246 ≈ 4,07 giorni.

Esempio — la distribuzione stazionaria del tempo a mano

Cerchiamo π = (a; b; c) con πP = π. Colonna per colonna della matrice:

• a = 0,6a + 0,3b + 0,2c, cioè 4a = 3b + 2c,
• b = 0,3a + 0,4b + 0,4c,
• c = 0,1a + 0,3b + 0,4c, cioè 6c = a + 3b.

Le equazioni sono dipendenti (sommandole tutte e tre otteniamo a + b + c = a + b + c), quindi tralasciamo quella di mezzo. Dalla terza a = 6c − 3b, sostituendo nella prima 24c − 12b = 3b + 2c, cioè b = 22c/15 e a = 6c − 66c/15 = 24c/15. Il rapporto è a : b : c = 24 : 22 : 15 e la condizione a + b + c = 1 dà

π = (24/61; 22/61; 15/61) ≈ (0,393; 0,361; 0,246).

Il tempo medio di ritorno alla pioggia è 1/π_pioggia = 61/15 ≈ 4,07 giorni.

E la simulazione di un singolo percorso casuale mostra il teorema ergodico in azione:

La simulazione estrae ogni giorno separatamente dalla riga dello stato di oggi: un numero casuale u in [0, 1) si confronta con le somme progressive della riga. Dopo un giorno sereno u < 0,6 porta a sereno, 0,6 ≤ u < 0,9 a nuvoloso e il resto a pioggia:

stav = sereno
for den in 1 … N:
    u = numero casuale in [0, 1)
    j = 0
    while u ≥ P[stav][j]:          # sottrai le probabilità finché u non «cade» nella casella
        u = u − P[stav][j]
        j = j + 1
    stav = j
    počet[stav] += 1
podíly = počet / N                 # per il teorema ergodico → π

La distribuzione stazionaria stessa si può calcolare senza estrazioni, moltiplicando ripetutamente per la matrice:

import numpy as np

P = np.array([[0.6, 0.3, 0.1],
              [0.3, 0.4, 0.3],
              [0.2, 0.4, 0.4]])

pi = np.ones(3) / 3
for _ in range(100):          # metodo delle potenze: π ← π P
    pi = pi @ P
print(pi.round(3))            # [0.393 0.361 0.246]

5. Markov, Onegin e Máj

Markov passò in rassegna le prime 20 000 lettere dell’Evgenij Onegin e segnò ciascuna come vocale o consonante. Le vocali erano il 43,2 %. Se le lettere si susseguissero in modo indipendente, una vocale seguirebbe una vocale anch’essa nel 43,2 % dei casi. Markov però ne contò solo il 12,8 %, mentre dopo una consonante il 66,3 %. Le lettere dipendono l’una dall’altra — eppure la frazione di vocali in un testo lungo converge in modo affidabile. Questa era la sua dimostrazione che la legge dei grandi numeri non ha bisogno dell’indipendenza.

Ripetiamolo sulla prima strofa di Máj (Maggio), il poema di Karel Hynek Mácha («Byl pozdní večer – první máj…»). Ha 311 lettere, le vocali sono il 37,6 %. La stima della matrice di transizione dai conteggi delle coppie:

Nella strofa ci sono solo 6 coppie di vocali consecutive — il ceco ama alternarle con le consonanti ancora più del russo. E la distribuzione stazionaria di questa catena risulta del 37,7 % di vocali: la catena stimata dal testo si «stabilizza» praticamente sulla frazione che nel testo c’è davvero (la differenza la fanno solo la prima e l’ultima lettera).

p̂_ij = n_ij / ∑_k n_ik

p̂_ij

stima della probabilità di transizione — il cappuccio dice che si tratta di un numero calcolato dai dati, non del valore vero

n_ij

quante volte nel testo i è stato seguito direttamente da j — si contano le coppie di lettere vicine, perché una catena di Markov guarda indietro di un solo passo

∑_k n_ik

quante volte i è stato seguito da qualunque cosa — dividendo, la riga somma a 1, come richiede una matrice stocastica

Esempio — conteggi delle coppie nella prima strofa

311 lettere danno 310 coppie di lettere vicine. Vocale–vocale 6, vocale–consonante 111, consonante–vocale 111, consonante–consonante 82. Da qui

p̂_voc→voc = 6/117 = 0,051, p̂_voc→con = 111/117 = 0,949, p̂_con→voc = 111/193 = 0,575, p̂_con→con = 82/193 = 0,425.

Una catena con due stati ha una distribuzione stazionaria data da una formula semplice:

π_voc = p_con→voc / (p_voc→con + p_con→voc)

π_voc

frazione di vocali a lungo andare

p_con→voc

flusso verso le vocali — più spesso si passa da una consonante a una vocale, più vocali ci sono

p_voc→con

flusso dalle vocali — più in fretta si lascia una vocale, meno vocali ci sono

Esempio — Máj e Onegin secondo la formula

Máj: π_voc = 0,575 / (0,949 + 0,575) = 0,377. Più precisamente: le transizioni vocale→consonante e consonante→vocale sono tante quante (111), quindi π_voc = (111/193) / (111/117 + 111/193) = 117/310. La frazione effettiva di vocali è 117/311 — differisce solo nel denominatore, perché l’ultima lettera della strofa («r») non inizia nessuna coppia.

Onegin: dai numeri di Markov (vocale dopo vocale 12,8 %, quindi vocale→consonante 87,2 %; vocale dopo consonante 66,3 %) risulta π_voc = 0,663 / (0,872 + 0,663) = 0,432 — esattamente il 43,2 % di vocali che Markov contò direttamente.

6. PageRank: il navigatore casuale

Nel 1998 Sergey Brin e Larry Page, i fondatori di Google, proposero un modo per ordinare le pagine web per importanza. Immaginarono un navigatore che clicca a caso sui link e si chiesero: su quali pagine passerà più tempo?

Definizione — PageRank

Sia i una pagina con k_i link uscenti. Il navigatore casuale con probabilità d (di solito 0,85) clicca su uno dei link scelto uniformemente a caso, altrimenti salta su una qualsiasi delle N pagine:

p_ij = (1 − d)/N + d/k_i se i ha un link verso j, altrimenti (1 − d)/N.

Il PageRank è la distribuzione stazionaria di questa catena. I salti garantiscono che la catena sia irriducibile e aperiodica.

In cima c’è C (0,374), a cui punta quasi ogni pagina. Più interessante è A: ha un solo link in entrata, eppure è seconda (0,342) — perché quel link viene da C e C non punta da nessun’altra parte. B, a cui punta solo A, riceve metà del peso di A (0,171). Le pagine D, E e F, che si collegano soprattutto fra loro, restano intorno a 0,04. Il vero PageRank calcolava la stessa cosa per miliardi di pagine, con il metodo delle potenze.

L’equazione π = πP scritta per una sola pagina dà la nota forma del PageRank:

PR(j) = (1 − d)/N + d ∑_i→j PR(i) / k_i

PR(j)

PageRank della pagina j — la frazione di tempo che il navigatore vi trascorre; la somma su tutte le pagine è 1

(1 − d)/N

contributo dei salti casuali — lo riceve ogni pagina in egual misura, anche quella a cui non punta nulla; grazie a esso la catena è irriducibile e aperiodica

d

probabilità che il navigatore clicchi su un link invece di saltare altrove — 0,85 nell’articolo originale di Brin e Page

∑_i→j

somma solo sulle pagine che puntano a j — un link è un «voto» per la pagina di destinazione

PR(i) / k_i

il voto della pagina i pesa quanto è importante i stessa, e si divide fra tutti i suoi k_i link — una pagina con mille link dà a ciascuno solo poco

Esempio — verifica di A, B e C

Per N = 6 e d = 0,85 è (1 − d)/N = 0,025. In A arriva solo il link da C, che ha un unico link (k_C = 1); in B solo quello da A, che ne ha due:

• PR(A) = 0,025 + 0,85 · 0,37351 / 1 = 0,34248,
• PR(B) = 0,025 + 0,85 · 0,34248 / 2 ≈ 0,1706,
• PR(C) = 0,025 + 0,85 · (PR(A)/2 + PR(B)/1 + PR(D)/2 + PR(E)/3 + PR(F)/1) = 0,025 + 0,85 · 0,41001 = 0,37351.

I valori del metodo delle potenze soddisfano l’equazione — così si riconosce che l’iterazione è arrivata alla fine.

PR = [1/N] * N                              # parti in modo uniforme
repeat:
    nové = [(1 − d)/N] * N                  # salti casuali
    for i in stránky:
        if i non ha link:                   # vicolo cieco: salta ovunque
            nové[j] += d · PR[i]/N  per tutti i j
        else:
            for j in odkazy[i]:
                nové[j] += d · PR[i]/k_i
    PR = nové
until PR quasi non cambia

7. Catene, testo e modelli linguistici

Una catena i cui stati sono lettere si può far generare. Dalle coppie di lettere della prima strofa di Máj stimiamo che cosa segue ciascuna lettera, e poi estraiamo a sorte. Ecco come appaiono 90 caratteri:

lal kou lasvavzvný dnkyl plásnětičaskol dnou ta javu snáscezepráro pl h jin trů bo kylalav

Una sciocchezza — ma una sciocchezza che «suona ceca»: alterna vocali e consonanti, ha parole brevi e sillabe come «lás» o «kol». Claude Shannon fece lo stesso esperimento con l’inglese nel 1948 e mostrò che con un contesto più lungo (terne di lettere, coppie di parole) il testo sembra via via più naturale.

Esempio — la riga «l» del modello a bigrammi

Convertiamo il testo della strofa in minuscole e sostituiamo la punteggiatura con uno spazio. La lettera «l» vi è seguita 31 volte da un altro carattere: 13 volte da uno spazio, 7 volte da «a», 6 volte da «á», 2 volte da «o» e una volta ciascuna da «i», «h», «u». Secondo la formula di stima è quindi

P(spazio | l) = 13/31 ≈ 0,42, P(a | l) = 7/31 ≈ 0,23, P(á | l) = 6/31 ≈ 0,19, P(o | l) = 2/31 ≈ 0,06 e gli altri 1/31 ≈ 0,03.

La generazione fa poi la stessa cosa della simulazione del tempo: dalla riga del carattere corrente estrae il carattere successivo. Dopo «l» la parola è il più delle volte alla fine — «byl», «lhal», «kol», «bol».

Definizione — modello a n-grammi

Un modello a n-grammi prevede il simbolo successivo in base agli n − 1 precedenti: P(w_t | w_t−n+1, …, w_t−1). È una catena di Markov il cui stato sono gli ultimi n − 1 simboli.

Esempio — quanti stati ha un modello a n-grammi

Con un vocabolario di V simboli, un modello a n-grammi ha |V|ⁿ⁻¹ stati e in ogni riga |V| probabilità. La strofa di Máj usa 32 caratteri diversi (lettere e spazio):

• bigrammi (n = 2): 32 stati, matrice 32 × 32 = 1 024 numeri — più dei caratteri della strofa, quindi la maggior parte risulta zero;
• trigrammi: 32² = 1 024 stati e oltre 32 mila numeri — la maggior parte delle coppie di lettere nella strofa non compare affatto e le loro righe restano vuote;
• un modello linguistico con un vocabolario di 50 000 token e una finestra di 1 000 token: 50 000^1 000 ≈ 10^4 699 stati.

Per questo un contesto più lungo richiede o dati enormi, o un modello che non prende le probabilità da una tabella, ma le stima con una funzione — una rete neurale.

8. Dove portano le catene di Markov

• Modelli di Markov nascosti — e se lo stato non lo vediamo e ne vediamo solo le manifestazioni? Se ne occupa la prossima parte.
• Processi decisionali di Markov aggiungono azioni e ricompense: su di essi si basa l’apprendimento per rinforzo.
• I metodi Monte Carlo basati su catene di Markov (MCMC) costruiscono una catena la cui distribuzione stazionaria è quella da cui vogliamo campionare — tipicamente la distribuzione a posteriori nella statistica bayesiana. Il criterio di Metropolis della parte sulla ricottura simulata è proprio una catena di questo tipo.

9. Riepilogo

• Una catena di Markov non ha memoria: lo stato successivo dipende solo da quello attuale. La descrive una matrice di transizione stocastica P.
• La distribuzione evolve moltiplicando per la matrice, π_t = π₀ P^t.
• Una catena irriducibile e aperiodica si stabilizza su un’unica distribuzione stazionaria π = π P, indipendentemente dall’inizio; per il tempo (0,393; 0,361; 0,246).
• Markov mostrò la dipendenza delle lettere sull’Onegin; in Máj una vocale segue una vocale solo nel 5 % dei casi.
• Il PageRank è la distribuzione stazionaria del navigatore casuale; i modelli a n-grammi e anche gli odierni modelli linguistici sono catene di Markov con uno stato grande.

Vuoi metterci le mani? Fai costruire a un agente IA un modello a bigrammi di parole da tutto Máj o dalle tue e-mail e fagli generare frasi — e poi prova con i trigrammi.

La vedi diversamente? Scrivi a support@coden-app.com.