Appendice Q — Catene di Markov

Il processo di Markov di primo ordine è un concetto fondamentale in molti campi, tra cui l’intelligenza artificiale, la statistica e la teoria delle probabilità. Questo modello probabilistico rappresenta un equilibrio tra la semplicità delle variabili casuali indipendenti e la complessità delle interazioni tra variabili. Per chiarire il concetto, consideriamo una sequenza temporale di eventi rappresentata da variabili casuali \(X_0, X_1, ..., X_n, ...\). In molti fenomeni reali, queste variabili non sono né completamente indipendenti né totalmente interdipendenti. Una catena di Markov rappresenta un compromesso tra questi due estremi.

In questo contesto, ci concentreremo su catene di Markov con stati discreti e tempo discreto. Ciò significa che le variabili \(X_n\) possono assumere valori in un insieme finito, tipicamente indicato come \(\{1, 2, ..., M\}\), e che gli eventi si verificano in momenti distinti e numerabili. La proprietà fondamentale di una catena di Markov può essere espressa matematicamente con la seguente equazione:

\[ P(X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, ..., X_0 = i_0) = P(X_{n+1} = j | X_n = i). \]

Questa equazione indica che il futuro (rappresentato da \(X_{n+1}\)) dipende solo dal presente (\(X_n\)) e non dal passato (\(X_{n-1}, ..., X_0\)). La proprietà di Markov può essere vista come un primo allentamento dell’assunzione di indipendenza: le variabili casuali sono dipendenti in un modo specifico che risulta matematicamente conveniente.

Quantità importanti associate a una catena di Markov sono le probabilità condizionate, chiamate probabilità di transizione:

\[ P(X_{n+1} = j \mid X_n = i). \]

La probabilità \(P(X_{n+1} = j \mid X_n = i)\), nota come probabilità di transizione, rappresenta la probabilità di passare dallo stato \(i\) allo stato \(j\) in un singolo passo.

Per descrivere completamente una catena di Markov, si utilizza una matrice \(Q\), chiamata matrice di transizione. Questa è una matrice \(M \times M\) in cui ogni elemento \(q_{ij}\) rappresenta la probabilità di transizione dallo stato \(i\) allo stato \(j\). Un’importante caratteristica della matrice di transizione è che la somma degli elementi di ogni riga deve essere pari a 1, poiché partendo da uno stato qualsiasi, il sistema deve necessariamente transitare in uno degli stati possibili.

Per chiarire ulteriormente il concetto, consideriamo un modello di previsione del tempo a Firenze con tre possibili condizioni meteorologiche: soleggiato, piovoso e nebbioso. Di seguito è riportata una matrice di transizione che rappresenta le probabilità di passaggio da un tipo di tempo all’altro:

Tempo Oggi Soleggiato Piovoso Nebbioso
Soleggiato 0.8 0.15 0.05
Piovoso 0.2 0.6 0.2
Nebbioso 0.2 0.3 0.5

Vediamo come calcolare alcune probabilità:

Il modello di Markov di base assume che le probabilità di transizione rimangano costanti nel tempo, una proprietà nota come omogeneità temporale. Questo significa che, per esempio, la probabilità di passare dallo stato “soleggiato” allo stato “piovoso” è la stessa in qualsiasi periodo dell’anno.

In sintesi, l’utilità del modello di Markov risiede nella sua capacità di semplificare notevolmente i calcoli probabilistici. Invece di considerare l’intera storia passata del sistema, è sufficiente conoscere solo lo stato attuale per fare previsioni sul futuro. Questa caratteristica, nota come “assenza di memoria”, rende il modello estremamente utile in molte applicazioni pratiche, dalla modellazione di fenomeni naturali alla progettazione di algoritmi di apprendimento automatico. Il processo di Markov di primo ordine offre uno strumento potente per analizzare e prevedere il comportamento di sistemi complessi nel tempo, bilanciando la necessità di catturare le dipendenze temporali con la semplicità computazionale. La sua versatilità e applicabilità in diversi campi lo rendono un concetto chiave per comprendere e modellare molti fenomeni del mondo reale.

Q.1 Classificazione degli Stati

Consideriamo ora la terminologia usata per descrivere le varie caratteristiche di una catena di Markov.

Q.1.1 Catene di Markov Irriducibili

Una catena di Markov è detta irriducibile se, per qualsiasi coppia di stati \(i\) e \(j\), esiste una probabilità positiva di passare dallo stato \(i\) allo stato \(j\) in un numero finito di passi. In altre parole, una catena irriducibile non ha stati isolati: ogni stato è raggiungibile da qualsiasi altro stato.

Q.1.2 Stati Ricorrenti

Uno stato \(i\) di una catena di Markov si dice ricorrente se, partendo da \(i\), la probabilità di ritornarvi è uguale a 1. Questo implica che una volta raggiunto lo stato \(i\), è garantito che la catena tornerà in \(i\) prima o poi. Gli stati ricorrenti possono essere ulteriormente classificati come:

  • Positivamente ricorrenti: uno stato è positivamente ricorrente se il tempo medio atteso per ritornare in quello stato, partendo da esso, è finito.
  • Nullamente ricorrenti: uno stato è nullamente ricorrente se il tempo medio atteso per ritornare in quello stato è infinito.
  • Ricorrenti di Harris: sono stati ricorrenti che vengono visitati infinite volte quando il tempo tende all’infinito, garantendo una certa frequenza di visita.

Q.1.3 Aperiodicità

Uno stato \(i\) si dice aperiodico se il massimo comun divisore dei tempi di ritorno in \(i\) è 1. In altre parole, uno stato è aperiodico se non esiste un ciclo deterministico che vincola i tempi in cui la catena può ritornare in quello stato. Una catena di Markov è aperiodica se tutti i suoi stati sono aperiodici. L’aperiodicità evita che la catena rimanga bloccata in una sequenza ciclica fissa, permettendo un comportamento più variegato nel tempo.

Q.1.4 Stazionarietà

Nella teoria delle catene di Markov, una distribuzione stazionaria \(\pi\) è una distribuzione di probabilità sugli stati tale che, se la catena parte con questa distribuzione iniziale, la distribuzione delle probabilità rimane invariata nel tempo. Matematicamente, se \(\pi\) è la distribuzione stazionaria, allora \(\pi P = \pi\), dove \(P\) è la matrice di transizione della catena di Markov. La stazionarietà è fondamentale per analizzare il comportamento a lungo termine della catena, poiché una volta raggiunta, la distribuzione di probabilità sugli stati rimane costante.

Q.1.5 Ergodicità

Una catena di Markov si dice ergodica se è irriducibile e aperiodica, e tutti i suoi stati sono positivamente ricorrenti. Questo implica che la catena, nel lungo termine, visita tutti gli stati secondo una distribuzione di probabilità che diventa stabile (stazionaria) e non dipende dallo stato iniziale. La proprietà di ergodicità è cruciale in quanto garantisce che le medie temporali di una funzione sugli stati della catena convergono alle medie rispetto alla distribuzione stazionaria.

Q.1.6 Convergenza

La convergenza di una catena di Markov si riferisce al processo mediante il quale la distribuzione di probabilità degli stati si avvicina alla distribuzione stazionaria \(\pi\) man mano che il numero di passi \(n\) tende all’infinito. In altre parole, indipendentemente dalla distribuzione iniziale degli stati, la distribuzione della catena dopo un lungo periodo di tempo sarà vicina a \(\pi\). Questo concetto è strettamente legato alla stazionarietà, poiché la convergenza descrive il percorso verso l’equilibrio, mentre la stazionarietà rappresenta lo stato di equilibrio raggiunto.

Q.2 Estensioni del modello di Markov

Oltre al modello di base, esistono diverse estensioni del processo di Markov che aumentano la sua capacità di rappresentare situazioni più complesse.

Q.2.1 Modello di Markov misto

Un’estensione comune del modello di Markov è il modello di Markov misto (Mixture Markov model, MMM), che considera la possibilità che una popolazione sia composta da sottogruppi distinti (cluster) con proprie probabilità di transizione. Ad esempio, possiamo immaginare di dividere una popolazione studentesca in due gruppi: quelli con alte prestazioni e quelli con basse prestazioni. Ogni gruppo ha una propria matrice di transizione che descrive la probabilità di rimanere o cambiare stato. Questo approccio permette di identificare sottogruppi latenti all’interno della popolazione e può essere utilizzato per raggruppare dati sequenziali in base a modelli di comportamento simili.

Q.2.2 Modello di Markov nascosto

Un’altra estensione utile è il modello di Markov nascosto (Hidden Markov model, HMM), utilizzato quando lo stato di interesse non può essere osservato direttamente o quando vi è un errore di misurazione nelle osservazioni. In un HMM, la catena di Markov opera a livello di stati nascosti, che generano o emettono stati osservati con diverse probabilità. Ad esempio, consideriamo l’abilità di uno studente come uno stato nascosto e il suo successo scolastico come uno stato osservato. Non possiamo misurare direttamente la vera abilità dello studente, ma possiamo stimarla dai punteggi dei test, che rappresentano le emissioni del loro stato di abilità. Questi modelli, noti come modelli di Markov nascosti misti (Mixture hidden Markov models, MHMM), combinano l’idea di cluster tempo-costanti con stati nascosti variabili nel tempo, permettendo di modellare popolazioni complesse con sottogruppi che si comportano in modo diverso nel tempo.

Q.2.3 Sommario

Una catena di Markov è una sequenza di variabili aleatorie \(X_0, X_1, X_2, \ldots\) che soddisfa la cosiddetta proprietà di Markov. Questa proprietà stabilisce che, dato lo stato attuale della catena, il futuro è indipendente dal passato. Formalmente, questa proprietà si esprime come:

\[ P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \ldots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i) = q_{ij}, \]

dove \(q_{ij}\) rappresenta la probabilità di passare dallo stato \(i\) allo stato \(j\) in un singolo passo. Queste probabilità di transizione sono organizzate in una matrice di transizione \(Q = (q_{ij})\), in cui ogni riga corrisponde a una distribuzione di probabilità condizionata sui possibili stati futuri dato l’attuale stato della catena.

La distribuzione di probabilità degli stati della catena dopo \(n\) passi può essere calcolata moltiplicando la matrice di transizione \(Q\) elevata alla potenza \(n\) per il vettore di probabilità iniziale \(s\), che descrive la distribuzione di probabilità degli stati al tempo \(0\). In simboli, questo è rappresentato da \(sQ^n\), che fornisce la distribuzione di probabilità marginale degli stati dopo \(n\) passi.

Gli stati di una catena di Markov possono essere classificati come ricorrenti o transitori. Uno stato è ricorrente se la catena torna a questo stato ripetutamente nel tempo; è transitorio se la catena potrebbe lasciare questo stato per non ritornarvi mai più. Gli stati possono anche avere un periodo associato, definito come il massimo comun divisore dei numeri di passi necessari per ritornare allo stato stesso. Una catena di Markov è detta irriducibile se è possibile raggiungere qualsiasi stato da qualsiasi altro stato in un numero finito di passi, ed è aperiodica se ogni stato ha periodo 1.

Una distribuzione stazionaria di una catena di Markov è una distribuzione di probabilità che rimane invariata nel tempo. Se la catena inizia con questa distribuzione, continuerà a mantenerla in ogni passo successivo. Questa condizione si esprime matematicamente come \(sQ = s\), dove \(s\) è il vettore di probabilità stazionaria e \(Q\) è la matrice di transizione. Per una catena di Markov finita che è irriducibile e aperiodica, esiste una distribuzione stazionaria unica verso la quale la catena converge indipendentemente dalla distribuzione iniziale.

Un concetto importante nelle catene di Markov è quello di reversibilità. Una catena di Markov è detta reversibile se esiste una distribuzione di probabilità \(s\) tale che, per ogni coppia di stati \(i\) e \(j\), la condizione di reversibilità \(s_i q_{ij} = s_j q_{ji}\) sia soddisfatta. Questa condizione garantisce che \(s\) sia una distribuzione stazionaria per la catena. Le catene di Markov reversibili sono particolarmente utili in applicazioni pratiche come gli algoritmi di simulazione Monte Carlo, ad esempio l’algoritmo di Metropolis-Hastings, poiché permettono di progettare catene che convergono rapidamente alla distribuzione di probabilità desiderata.

Q.2.4 Letteratura

I metodi markoviani sono stati ampiamente utilizzati in vari ambiti della psicologia e dell’educazione. Una delle applicazioni più comuni di questi metodi è il clustering dei dati sequenziali (Törmänen et al. (2022); Törmänen et al. (2023); Fincham et al. (2018)). Ad esempio, i modelli nascosti di Markov (HMM) sono stati utilizzati per raggruppare le sequenze di dati tracciati da sistemi di gestione dell’apprendimento (LMS) degli studenti, al fine di identificare i loro schemi di attività, ovvero le tattiche e strategie di apprendimento (Fincham et al. (2018)). Un uso molto diffuso dei modelli di Markov di primo ordine è quello di mappare le transizioni degli studenti tra diverse attività di apprendimento. Per esempio, Matcha et al. (2020) ha utilizzato modelli di Markov di primo ordine per studiare i processi di transizione degli studenti tra diverse strategie di apprendimento. Altri usi includono lo studio delle transizioni tra diverse strategie di scrittura accademica (Peeters et al. (2020)), tra eventi di apprendimento autoregolato (Lim et al. (2023)), o all’interno di contesti di apprendimento collaborativo (Saqr & López-Pernas (2023)). Esempi più specifici nell’ambito psicologico comprendono lo studio delle influenze reciproche tra stati affettivi (Cipresso et al. (2023)) e l’analisi degli effetti psicologici che dipendono dal tempo nelle sequenze di decision-making (Gunawan et al. (2022)).

Q.2.5 Stima dei Parametri del Modello

I parametri di un modello di Markov, come le probabilità iniziali degli stati e le probabilità di transizione tra stati, possono essere stimati a partire dai dati utilizzando diversi metodi statistici. In questo corso, ci concentreremo sulla stima bayesiana utilizzando il software Stan, che offre una grande flessibilità nella definizione dei modelli e permette di ottenere stime precise.

Per chiarire meglio, consideriamo l’esempio di un processo di Markov di primo ordine implementato in Stan. Immaginiamo di voler modellare un sistema meteorologico, come abbiamo discusso in precedenza. In questo contesto, potremmo voler stimare le probabilità iniziali di condizioni meteorologiche specifiche e le probabilità di transizione che descrivono come il tempo potrebbe cambiare da un giorno all’altro.

data {
  int<lower=1> N;           // Numero di osservazioni
  int<lower=1> K;           // Numero di stati possibili (3 per Soleggiato, Piovoso, Nebbioso)
  int<lower=1, upper=K> y[N]; // Sequenza di osservazioni (stati)
}

parameters {
  simplex[K] P[K]; // Matrice di transizione delle probabilità
}

model {
  for (n in 2:N) {
    y[n] ~ categorical(P[y[n-1]]);
  }
}

In questo modello, usiamo la distribuzione categorical() per modellare le transizioni tra i tre stati meteorologici possibili.

Consideriamo ora una situazione ancora più semplice, come quella discussa nel Capitolo 104. In questo secondo caso, abbiamo una sequenza di prove con solo due stati: prova prova corretta (0) e prova sbagliata (1). Il nostro interesse è la prestazione post-errore. Questo scenario si presta naturalmente all’uso della distribuzione bernoulli().

data {
  int<lower=1> N;           // Numero di prove
  int<lower=0, upper=1> y[N]; // Sequenza di risultati (0 = corretto, 1 = errore)
}

parameters {
  real<lower=0, upper=1> p_error_given_correct;
  real<lower=0, upper=1> p_error_given_error;
}

model {
  for (n in 2:N) {
    if (y[n - 1] == 1) {
      y[n] ~ bernoulli(p_error_given_error);
    } else {
      y[n] ~ bernoulli(p_error_given_correct);
    }
  }
}

In questo modello:

  • p_error_given_correct rappresenta la probabilità di errore dopo una prova corretta.
  • p_error_given_error rappresenta la probabilità di errore dopo un errore precedente.

Mentre nel modello Meteo avevamo tre stati (Soleggiato, Piovoso, Nebbioso), nel caso del modello Post-Errore abbiamo solo due stati (Corretto, Errore). Ciò porta ad una differenza tra le funzioni di verosimiglianza che vengono utilizzate:

  • Modello Meteo: categorical();
  • Modello Post-Errore: bernoulli().

Di conseguenza, la parametrizzazione dei modelli cambia:

  • Modello Meteo: Matrice di transizione completa (simplex[K] P[K]);
  • Modello Post-Errore: Due probabilità di transizione (p_error_given_correct, p_error_given_error)

In conclusione, il processo di Markov di primo ordine è uno strumento potente per modellare sequenze di eventi con memoria limitata. L’implementazione in Stan permette di effettuare inferenze su questi modelli, sia in contesti con molteplici stati (come le previsioni meteo) sia in scenari binari (come l’analisi della prestazione post-errore).