Cosa sono le catene di Markov, quando usarle, e come funzionano
Le catene di Markov sono un modo abbastanza comune, e relativamente semplice, per modellare statisticamente processi casuali. Sono state usate in molti domini diversi, che vanno dalla generazione di testo alla modellazione finanziaria. Un esempio popolare è r/SubredditSimulator, che utilizza le catene di Markov per automatizzare la creazione di contenuti per un intero subreddit. Nel complesso, le catene di Markov sono concettualmente abbastanza intuitive, e sono molto accessibili in quanto possono essere implementate senza l’uso di alcun concetto statistico o matematico avanzato. Sono un ottimo modo per iniziare ad imparare la modellazione probabilistica e le tecniche di data science.
Scenario
Per iniziare, le descriverò con un esempio molto comune:
Imagine that there were two possible states for weather: sunny or cloudy. You can always directly observe the current weather state, and it is guaranteed to always be one of the two aforementioned states.Now, you decide you want to be able to predict what the weather will be like tomorrow. Intuitively, you assume that there is an inherent transition in this process, in that the current weather has some bearing on what the next day's weather will be. So, being the dedicated person that you are, you collect weather data over several years, and calculate that the chance of a sunny day occurring after a cloudy day is 0.25. You also note that, by extension, the chance of a cloudy day occurring after a cloudy day must be 0.75, since there are only two possible states.You can now use this distribution to predict weather for days to come, based on what the current weather state is at the time.
Questo esempio illustra molti dei concetti chiave di una catena di Markov. Una catena di Markov consiste essenzialmente in un insieme di transizioni, che sono determinate da una certa distribuzione di probabilità, che soddisfano la proprietà di Markov.
Osserva come nell’esempio, la distribuzione di probabilità è ottenuta unicamente osservando le transizioni dal giorno corrente al successivo. Questo illustra la proprietà di Markov, la caratteristica unica dei processi di Markov che li rende senza memoria. Questo tipicamente li rende incapaci di produrre con successo sequenze in cui ci si aspetta che si verifichi una qualche tendenza sottostante. Per esempio, mentre una catena di Markov può essere in grado di imitare lo stile di scrittura di un autore basato sulla frequenza delle parole, non sarebbe in grado di produrre un testo che contiene un significato profondo o un significato tematico, poiché questi si sviluppano su sequenze di testo molto più lunghe. Mancano quindi della capacità di produrre contenuti dipendenti dal contesto poiché non possono prendere in considerazione l’intera catena di stati precedenti.
Il modello
Formalmente, una catena di Markov è un automa probabilistico. La distribuzione di probabilità delle transizioni di stato è tipicamente rappresentata come la matrice di transizione della catena di Markov. Se la catena di Markov ha N possibili stati, la matrice sarà una matrice N x N, tale che la voce (I, J) è la probabilità di transizione dallo stato I allo stato J. Inoltre, la matrice di transizione deve essere una matrice stocastica, una matrice le cui voci in ogni riga devono sommare esattamente 1. Questo ha completamente senso, poiché ogni riga rappresenta la propria distribuzione di probabilità.
Inoltre, una catena di Markov ha anche un vettore di stato iniziale, rappresentato come una matrice N x 1 (un vettore), che descrive la distribuzione di probabilità di iniziare in ciascuno degli N stati possibili. La voce I del vettore descrive la probabilità che la catena inizi allo stato I.
Queste due entità sono tipicamente tutto ciò che è necessario per rappresentare una catena di Markov.
Ora sappiamo come ottenere la probabilità di transizione da uno stato all’altro, ma come trovare la probabilità che quella transizione avvenga su più passi? Per formalizzare questo, ora vogliamo determinare la probabilità di passare dallo stato I allo stato J su M passi. Come si è scoperto, questo è in realtà molto semplice da scoprire. Data una matrice di transizione P, questo può essere determinato calcolando il valore della voce (I, J) della matrice ottenuta elevando P alla potenza di M. Per piccoli valori di M, questo può essere facilmente fatto a mano con ripetute moltiplicazioni. Tuttavia, per grandi valori di M, se avete familiarità con la semplice algebra lineare, un modo più efficiente per elevare una matrice ad una potenza è di diagonalizzare prima la matrice.
Conclusione
Ora che conoscete le basi delle catene di Markov, dovreste essere in grado di implementarle facilmente in un linguaggio di vostra scelta. Se la codifica non è il tuo forte, ci sono anche molte proprietà più avanzate delle catene di Markov e dei processi di Markov in cui immergersi. A mio parere, la progressione naturale lungo il percorso della teoria sarebbe verso i processi di Markov nascosti o MCMC. Le catene di Markov semplici sono gli elementi costitutivi di altre tecniche di modellazione più sofisticate, quindi con questa conoscenza, è possibile passare a varie tecniche all’interno di argomenti come la modellazione delle credenze e il campionamento.