Catene di Markov in Python: tutorial per principianti

Una catena di Markov è un sistema matematico di solito definito come una collezione di variabili casuali che transita da uno stato all'altro secondo determinate regole probabilistiche. Questo insieme di transizioni soddisfa la proprietà di Markov, che afferma che la probabilità di passare a un particolare stato dipende esclusivamente dallo stato attuale e dal tempo trascorso, e non dalla sequenza di stati che l'ha preceduto. Questa caratteristica unica dei processi di Markov li rende senza memoria.

Vuoi affrontare altri argomenti di statistica con Python? Dai un'occhiata al corso Statistical Thinking in Python di DataCamp!

Passiamo alla transizione...

Perché le catene di Markov?

Le catene di Markov hanno un uso prolifico in matematica. Sono ampiamente impiegate in economia, teoria dei giochi, teoria della comunicazione, genetica e finanza. Emergono spesso in contesti statistici, in particolare nella statistica bayesiana, e in contesti di teoria dell'informazione. Nei problemi del mondo reale, vengono usate per ipotizzare soluzioni per studiare sistemi di cruise control nei veicoli, code o file di clienti in arrivo in un aeroporto, tassi di cambio delle valute, ecc. L'algoritmo noto come PageRank, proposto originariamente per il motore di ricerca Google, si basa su un processo di Markov. Subreddit Simulator di Reddit è un subreddit completamente automatizzato che genera post e commenti casuali usando catene di Markov: che figata!

Catena di Markov

Una catena di Markov è un processo casuale con la proprietà di Markov. Un processo casuale, o spesso chiamato stocastico, è un oggetto matematico definito come una collezione di variabili casuali. Una catena di Markov ha o uno spazio degli stati discreto (insieme dei possibili valori delle variabili casuali) o un insieme di indici discreto (che spesso rappresenta il tempo): dato ciò, esistono molte varianti di catena di Markov. Di solito il termine "catena di Markov" è riservato a un processo con un insieme di tempi discreto, ovvero una catena di Markov a tempo discreto (DTMC).

Catena di Markov a tempo discreto

Una catena di Markov a tempo discreto riguarda un sistema che a ogni passo si trova in un certo stato, con lo stato che cambia in modo casuale tra i passi. I passi sono spesso intesi come istanti nel tempo (ma potresti anche riferirti a distanze fisiche o a qualunque altra misura discreta). Una catena di Markov a tempo discreto è una sequenza di variabili casuali X₁, X₂, X₃, ... con la proprietà di Markov, tale che la probabilità di passare allo stato successivo dipende solo dallo stato presente e non dagli stati precedenti. In formula probabilistica:

Pr( X_n+1 = x | X₁ = x₁, X₂ = x₂, …, X_n = x_n) = Pr( X_n+1 = x | X_n = x_n)

Come vedi, la probabilità di X_n+1 dipende solo dalla probabilità di X_n che la precede. Questo significa che la conoscenza dello stato precedente è tutto ciò che serve per determinare la distribuzione di probabilità dello stato corrente, soddisfacendo la regola dell'indipendenza condizionale (o, detto in un altro modo: ti basta conoscere lo stato attuale per determinare il prossimo stato).

I valori possibili di X_i formano un insieme numerabile S chiamato spazio degli stati della catena. Lo spazio degli stati può essere qualsiasi cosa: lettere, numeri, punteggi di basket o condizioni meteo. Sebbene il parametro temporale sia di solito discreto, lo spazio degli stati di una catena di Markov a tempo discreto non ha restrizioni ampiamente concordate e rimanda piuttosto a un processo su uno spazio degli stati arbitrario. Tuttavia, molte applicazioni delle catene di Markov impiegano spazi degli stati finiti o numerabili infiniti, perché consentono un'analisi statistica più diretta.

Modello

Una catena di Markov è rappresentata usando un automa probabilistico (sembra complicato, ma non lo è!). I cambiamenti di stato del sistema si chiamano transizioni. Le probabilità associate ai vari cambiamenti di stato si chiamano probabilità di transizione. Un automa probabilistico include la probabilità di una data transizione nella funzione di transizione, trasformandola in una matrice di transizione.

Puoi pensarla come una sequenza di grafi orientati, in cui gli archi del grafo n sono etichettati con le probabilità di passare da uno stato al tempo n agli altri stati al tempo n+1, Pr(X_n+1 = x | X_n = x_n). Puoi leggerlo come: probabilità di andare allo stato X_n+1 dato il valore dello stato X_n. La stessa informazione è rappresentata dalla matrice di transizione dal tempo n al tempo n+1. Ogni stato nello spazio degli stati è incluso una volta come riga e di nuovo come colonna, e ogni cella della matrice indica la probabilità di passare dallo stato della sua riga allo stato della sua colonna.

Se la catena di Markov ha N stati possibili, la matrice sarà una matrice N x N, tale che l'elemento (I, J) è la probabilità di passare dallo stato I allo stato J. Inoltre, la matrice di transizione deve essere stocastica, cioè le voci di ogni riga devono sommare esattamente a 1. Perché? Perché ogni riga rappresenta una propria distribuzione di probabilità.

Dunque, il modello è caratterizzato da uno spazio degli stati, da una matrice di transizione che descrive le probabilità delle particolari transizioni, e da uno stato iniziale sullo spazio degli stati, dato dalla distribuzione iniziale.

Un sacco di parole, eh?

Vediamo un semplice esempio per comprendere i concetti:

Quando Cj è triste, cosa che non capita spesso: o va a correre, o si ingozza di gelato, oppure fa un pisolino.

Dai dati storici, se ha passato una giornata triste dormendo. Il giorno dopo è probabile al 60% che vada a correre, al 20% che resti a letto il giorno dopo e al 20% che si abbuffi di gelato.

Quando è triste e va a correre, c'è il 60% di probabilità che vada a correre anche il giorno dopo, il 30% che si ingozzi di gelato e solo il 10% che passi il giorno successivo dormendo.

Infine, quando si concede il gelato in una giornata triste, c'è appena il 10% di probabilità che continui a mangiare gelato anche il giorno dopo, il 70% che vada a correre e il 20% che passi il giorno successivo dormendo.

La catena di Markov rappresentata nel diagramma degli stati ha 3 possibili stati: dormire, correre, gelato. Quindi la matrice di transizione sarà 3 x 3. Nota che le frecce che escono da uno stato sommano sempre esattamente a 1, allo stesso modo le voci di ogni riga nella matrice di transizione devono sommare esattamente a 1, rappresentando una distribuzione di probabilità. Nella matrice di transizione, le celle fanno lo stesso lavoro delle frecce nel diagramma degli stati.

Ora che hai visto l'esempio, dovresti avere un'idea dei diversi concetti legati a una catena di Markov. Ma come e dove puoi usare questa teoria nella vita reale?

Con l'esempio che hai visto, ora puoi rispondere a domande come: "Partendo dallo stato: dormire, qual è la probabilità che Cj starà correndo (stato: correre) alla fine di una durata triste di 2 giorni?"

Rispondiamoci: per passare dallo stato: dormire allo stato: correre, Cj deve o rimanere nello stato: dormire alla prima mossa (o giorno), poi passare allo stato: correre alla mossa successiva (seconda) (0,2 $\cdot$ 0,6); oppure passare allo stato: correre il primo giorno e poi restarci il secondo (0,6 $\cdot$ 0,6); oppure potrebbe passare allo stato: gelato alla prima mossa e poi allo stato: correre alla seconda (0,2 $\cdot$ 0,7). Quindi la probabilità: ((0,2 $\cdot$ 0,6) + (0,6 $\cdot$ 0,6) + (0,2 $\cdot$ 0,7)) = 0,62. Possiamo dunque dire che c'è il 62% di probabilità che Cj passi allo stato: correre dopo due giorni di tristezza, se è partita dallo stato: dormire.

Speriamo che questo ti abbia dato un'idea delle varie domande a cui puoi rispondere usando una rete di Markov.

Con questo chiaro in mente, diventa anche più facile comprendere alcune proprietà importanti delle catene di Markov:

• Riducibilità: una catena di Markov si dice irriducibile se è possibile raggiungere qualsiasi stato da qualsiasi stato. In altre parole, una catena di Markov è irriducibile se esiste una catena di passi tra due stati qualunque che abbia probabilità positiva.
• Periodicità: uno stato in una catena di Markov è periodico se la catena può tornare a quello stato solo a multipli di un intero maggiore di 1. Quindi, iniziando nello stato "i", la catena può tornare a "i" solo a multipli del periodo "k", e k è il più grande di tali interi. Lo stato "i" è aperiodico se k = 1 e periodico se k > 1.
• Transienza e ricorrenza: uno stato "i" si dice transiente se, dato che partiamo nello stato "i", esiste una probabilità non nulla di non tornarvi mai più. Lo stato i è ricorrente (o persistente) se non è transiente. Uno stato ricorrente è detto positivamente ricorrente se ci si attende che ritorni entro un numero finito di passi e nullo ricorrente altrimenti.
• Ergodicità: uno stato "i" si dice ergodico se è aperiodico e positivamente ricorrente. Se tutti gli stati in una catena di Markov irriducibile sono ergodici, allora la catena si dice ergodica.
• Stato assorbente: uno stato i si chiama assorbente se è impossibile lasciarlo. Quindi, lo stato "i" è assorbente se p_ii = 1 e p_ij = 0 per i ≠ j. Se ogni stato può raggiungere uno stato assorbente, allora la catena di Markov è una catena di Markov assorbente.

Consiglio: se vuoi anche una spiegazione visiva delle catene di Markov, assicurati di visitare questa pagina.

Catene di Markov in Python

Proviamo a codificare l'esempio sopra in Python. E anche se nella vita reale probabilmente useresti una libreria che implementa le catene di Markov in modo molto più efficiente, il codice dovrebbe aiutarti a iniziare...

Importiamo prima alcune librerie che userai.

import numpy as np
import random as rm

Definiamo ora gli stati e le loro probabilità: la matrice di transizione. Ricorda, la matrice sarà 3 X 3 poiché hai tre stati. Inoltre, dovrai definire i percorsi di transizione; puoi farlo anche usando matrici.

# The statespace
states = ["Sleep","Icecream","Run"]

# Possible sequences of events
transitionName = [["SS","SR","SI"],["RS","RR","RI"],["IS","IR","II"]]

# Probabilities matrix (transition matrix)
transitionMatrix = [[0.2,0.6,0.2],[0.1,0.6,0.3],[0.2,0.7,0.1]]

Oh, assicurati sempre che le probabilità sommino a 1. E non fa male lasciare messaggi d'errore, almeno quando si programma!

if sum(transitionMatrix[0])+sum(transitionMatrix[1])+sum(transitionMatrix[1]) != 3:
    print("Somewhere, something went wrong. Transition matrix, perhaps?")
else: print("All is gonna be okay, you should move on!! ;)")

All is gonna be okay, you should move on!! ;)

Ora scriviamo il codice vero e proprio. Userai numpy.random.choice per generare un campione casuale dall'insieme di transizioni possibili. Sebbene la maggior parte dei suoi argomenti sia autoesplicativa, forse p non lo è. È un argomento opzionale che ti permette di inserire la distribuzione di probabilità per l'insieme di campionamento, che in questo caso è la matrice di transizione.

# A function that implements the Markov model to forecast the state/mood.
def activity_forecast(days):
    # Choose the starting state
    activityToday = "Sleep"
    print("Start state: " + activityToday)
    # Shall store the sequence of states taken. So, this only has the starting state for now.
    activityList = [activityToday]
    i = 0
    # To calculate the probability of the activityList
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1  
    print("Possible states: " + str(activityList))
    print("End state after "+ str(days) + " days: " + activityToday)
    print("Probability of the possible sequence of states: " + str(prob))

# Function that forecasts the possible state for the next 2 days
activity_forecast(2)

Start state: Sleep
Possible states: ['Sleep', 'Sleep', 'Run']
End state after 2 days: Run
Probability of the possible sequence of states: 0.12

Ottieni un insieme casuale di transizioni possibili insieme alla probabilità che si verifichi, partendo dallo stato: Sleep. Estendi ulteriormente il programma per iterarlo magari qualche centinaio di volte con lo stesso stato iniziale: potrai così vedere la probabilità attesa di terminare in uno stato particolare insieme alla sua probabilità. Riscriviamo la funzione activity_forecast e aggiungiamo un nuovo set di cicli per farlo...

def activity_forecast(days):
    # Choose the starting state
    activityToday = "Sleep"
    activityList = [activityToday]
    i = 0
    prob = 1
    while i != days:
        if activityToday == "Sleep":
            change = np.random.choice(transitionName[0],replace=True,p=transitionMatrix[0])
            if change == "SS":
                prob = prob * 0.2
                activityList.append("Sleep")
                pass
            elif change == "SR":
                prob = prob * 0.6
                activityToday = "Run"
                activityList.append("Run")
            else:
                prob = prob * 0.2
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Run":
            change = np.random.choice(transitionName[1],replace=True,p=transitionMatrix[1])
            if change == "RR":
                prob = prob * 0.5
                activityList.append("Run")
                pass
            elif change == "RS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.3
                activityToday = "Icecream"
                activityList.append("Icecream")
        elif activityToday == "Icecream":
            change = np.random.choice(transitionName[2],replace=True,p=transitionMatrix[2])
            if change == "II":
                prob = prob * 0.1
                activityList.append("Icecream")
                pass
            elif change == "IS":
                prob = prob * 0.2
                activityToday = "Sleep"
                activityList.append("Sleep")
            else:
                prob = prob * 0.7
                activityToday = "Run"
                activityList.append("Run")
        i += 1    
    return activityList

# To save every activityList
list_activity = []
count = 0

# `Range` starts from the first count up until but excluding the last count
for iterations in range(1,10000):
        list_activity.append(activity_forecast(2))

# Check out all the `activityList` we collected    
#print(list_activity)

# Iterate through the list to get a count of all activities ending in state:'Run'
for smaller_list in list_activity:
    if(smaller_list[2] == "Run"):
        count += 1

# Calculate the probability of starting from state:'Sleep' and ending at state:'Run'
percentage = (count/10000) * 100
print("The probability of starting at state:'Sleep' and ending at state:'Run'= " + str(percentage) + "%")

The probability of starting at state:'Sleep' and ending at state:'Run'= 62.419999999999995%

Come ci siamo avvicinati al 62% desiderato?

Nota Questa è in realtà la "legge dei grandi numeri", un principio di probabilità che afferma che le frequenze di eventi con la stessa probabilità di occorrenza si uniformano, ma solo se ci sono abbastanza prove o istanze. In altre parole, al crescere del numero di esperimenti, il rapporto effettivo degli esiti convergerà verso un rapporto teorico o atteso degli esiti.

Markov State of Mind

Questo conclude il tutorial sulle catene di Markov. Sei stato introdotto alle catene di Markov e ad alcune delle loro proprietà. Le catene di Markov semplici sono uno degli argomenti fondamentali richiesti per iniziare con la data science in Python. Se vuoi altre risorse per iniziare con la statistica in Python, assicurati di consultare questa pagina.

Ti interessa esplorare altri casi di studio pratici con la statistica in Python? Dai un'occhiata ai corsi di DataCamp Case Studies in Statistical Thinking o Network Analysis in Python.