Modelli di Markov

Per introdurre il concetto di hidden Markov model, partiamo da quello più intuitivo di modello di Markov. Consideriamo il classico esempio della coffe machine. Supponiamo di avere nel nostro ufficio (a casa è improbabile) una macchina che ha l'ottima qualità di fare il caffè o il tè gratuitamente, ma ha la pessima caratteristica di non avere un selezionatore per le bevande, per cui noi non possiamo prelevare la nostra bevanda preferita a nostra discrezione. Quando cioè ci poniamo davanti alla macchinetta e premiamo l'unico pulsante presente a volte esce caffè altre tè. Noi potremmo imaginare che il subdolo meccanismo sottostante potrebbe essere generato dal fatto che la nostra macchina possiede due stati interni corrispondenti alle due bevande. I due stati poi si alternano con una probabilità decisa casualmente e che dipende soltanto dallo stato in cui si trova la nostra macchina in quel preciso istante. Questa restrizione ne fa un modello di Markov, in quanto lo stato sucessivo dipende soltanto dallo stato attuale. Possiamo allora porci le seguenti domande:

1. Qual'è la probabilità di una sequenza di eventi (caffè/tè) dato il modello? Se conosco quali sono le probabilità con cui la macchina salta da uno stato all'altro, qual'è la probabilità di una particolare sequenza di eventi caffè e tè?
2. model learning: se ottengo dalla macchina una serie o più serie di eventi caffè e teè, come posso stimare il modello che sta all'interno, cioè le probabilità di transizione tra gli stati?

Per quanto riguarda la prima domanda, possiamo considerare di avere visto che all'interno della macchina esite effettivamente un modello di Markov e che esso sia quello mostrato in Figura . Se allora abbiamo a disposizione la la sequenza di eventi s='CTCCT' (dove C=coffe,T=tea) possiamo calcolare la probabilità che tale sequenza sia essere generata dal modello della figura. Da cui abbiamo

$$\begin{eqnarray*} P(s\vert Modello)&=& a_{C,T}\cdot a_{T,C}\cdot a_{C,C}\cdot a_... ... P(T\vert C)\\ &=& 0.10\cdot 0.20\cdot 0.90\cdot 0.10 = 0.0018 \end{eqnarray*}$$

dove abbiamo indicato la probabilità di transizione da uno stato $s$ ad uno stato $t$ con $a_{s,t}=P(t\vert s)$. In modo del tutto analogo possiamo quindi verificare che la probabilità di generare la sequenza 'CTCTC' è invece $0.10\cdot0.20\cdot0.10\cdot0.20=0.0004$

Figura: Modello di Markov della coffe-machine

Per quanto riguarda la seconda domanda, dobbiamo stimare da una o una serie di sequenze da noi (o da nostri amici) ottenute utilizzando la macchina, in modo da calcolare i parametri del modello. Il modo più utilizzato è quello della massima verosimiglianza o maximum likelihood (ML). In questo caso quello che vogliamo e` ottenere i parametri del nostro modello che massimizzano la probabilità di generare quella (quelle sequenze). Più formalmente cerchiamo l'insieme dei parametri $\theta_M$ del nostro modello (le probabilità di transizione) che massimizzano la $P(s\vert\theta)$

$$\begin{eqnarray*} P_{M}(s\vert\theta_M)=\max_{\theta}P(s\vert\theta) \end{eqnarray*}$$

Pur sembrando particolarmente strano questo approccio è esattamente quello più naturale e maggiormente utilizzato. Lo abbiamo spesso utilizzato inconsapevolmente. Per esempio quando facciamo l'ipotesi che i dati di un nostro esperimento $x_1,x_2,..x_n$ seguano una legge di distribuzione degli errori Gaussiana e indipendente, di fatto appichiamo poi la ML per derivare i nostri parametri valor medio $\mu$ e deviazione standard $\sigma$ della nostra serie di dati. Se infatti poniamo

$$p(x\vert\mu, \sigma)=\frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$$ (11.2)

abbiamo che per $n$ valutazioni che consideriamo essere indipendenti, della nostra variabile $x$ la likelihood è

$$\begin{eqnarray*} P(x_1,..x_n)=\prod_{i=1}^{n}p(x_i\vert\mu, \sigma) \end{eqnarray*}$$

Per la nostra ML sarà quella che ci fornirà il massimo valore della probabilità $P(x_1,..,x_n)$ per specifici valodi di $\mu$ e $\sigma$. Noi poi sappiamo dal calcolo che i valori di massimo (in realtà i punti critici) di una funzione li otteniamo eguagliando a 0 la derivata della funzione. Abbiamo perciò che i valori per cui la nostra likelihood è massima sono quelli per cui

$$\begin{eqnarray*} \frac{\partial P(x_1,..,x_n)}{\partial \mu} = 0 \\ \frac{\partial P(x_1,..,x_n)}{\partial \sigma} = 0 \end{eqnarray*}$$

Valutando tali equazioni per il nostro caso in esame otteniamo proprio

$$\begin{array}{c} \mu = (\sum_{i=1}^n x_i)/n \\ \sigma^2 = (\sum_{i=1}^n (x_i - \mu)^2)/n \end{array}$$ (11.3)

Per poter vedere come di fatto possiamo ottenere i paramatri massimizzando la probabilità prendiamo il caso esplicito del modello di Markov generico della nostra coffe-machine, come proposto in Figura . Esso possiede 2 parametri liberi che sono la probabilità di transire dallo stato coffe su se stesso $C$ e quella di transire dallo stato tea su se stesso $T$. Le altre due probabilità $P(S\vert T)$ e $P(T\vert S)$ si ottengono automaticamente ricordando la condizione di normalizzazione

$$\begin{eqnarray*} \sum_{k} P(k\vert s)= \sum_{k} a_{s,k} = 1 \quad \forall s \end{eqnarray*}$$

Fissati dunque i generici parametri $C$ e $T$, la probabilità di una data sequenza $s$ è quindi

$$\begin{eqnarray*} P(s\vert\theta)=(C)^{n_{CC}} (1-C)^{n_{AT}} (T)^{n_{TT}} (1-T)^{n_{TC}} \end{eqnarray*}$$

dove abbiamo che $n_{ij}$ è il numero di volte in cui troviamo nela nostra sequenza una la coppia di simboli $ij$ (nel nostro caso $i,j \in$ {tea, coffe}). Cercare quindi i valori $C$ e $T$ che massimizzano la probabilità equivale a cercare per quali $C$ e $T$ si annullano le derivate della probabilità (o per la monotonicità della funzione $\log{}$ come vedremo nell'esercizio ) rispetto a tali variabili

$$\begin{eqnarray*} \frac{\partial P(s\vert\theta)}{\partial C}=0 \quad oppure\qua... ...pure\quad \frac{\partial \log{P(s\vert\theta)}}{\partial C} = 0 \end{eqnarray*}$$

Nel primo caso abbiamo

$$\begin{eqnarray*} \frac{\partial \log{P(s)}}{\partial C} = 1/P(s)\cdot\{\frac{n_{CC}}{C}-\frac{n_{CT}}{1-C} \} \end{eqnarray*}$$

che eguagliando a zero diviene

$$\begin{eqnarray*} 1/P(s)\cdot\{\frac{n_{CC}(1-C)-n_{CT}C}{C(1-C)} \} =0 &\\ \Rightarrow C=n_{CC}/(n_{CC}+n_{CT}) & \end{eqnarray*}$$

Analogamente si vede che anche per $T$ si ottiene

$$\begin{eqnarray*} T=n_{TT}/(n_{TT}+n_{TC}) \end{eqnarray*}$$

È molto interessante vedere che l'approccio basato sulla ML, porta al concetto comune che per stimare la probabilità di transizione tra coffe e tea data una sequenza di eventi, la massima probabilità la ottengo contando il numero di volte che a coffe segue coffe ($n_{CC}$) e lo sottraggo per il numero di volte in cui da coffe passo ad un altro stato ( $(n_{TT}+n_{TC})$).

Per cui se andiamo alla macchina e generiamo la sequenza s='CCCTT', ed un nostro amico (coffe-addicted) genera bevendo tutto la sequenza t='TCCC TTTT CCC TTC', possiamo stimare le probabilità come

$$\begin{eqnarray*} C=n_{CC}/(n_{CC}+n_{CT})= 6/ (6+3) = 0.67 \Rightarrow 1-C=0.33... ...T=n_{TT}/(n_{TT}+n_{TC})= 5/ (5+3) = 0.625 \Rightarrow 1-T=0.375 \end{eqnarray*}$$

Figura: Modello di Markov generico della coffe-machine