Esercizio - Filtraggio in un HMM - il bambino e il pannolino (slide del corso)

Formulazione

Stato nascosto $X_t\in\{\text{pulito},\text{sporco}\}$, evidenza $e_t$ = parola detta al cambio $t$ (Ragionamento probabilistico nel tempo - catene di Markov, HMM, filtraggio e smoothingPer ragionare sul tempo il mondo è una sequenza di istanti: stato nascosto $X_t$ ed evidenza osservata $E_t$. Ipotesi di Markov del primo ordine $P(X_t\mid X_{0:t-1})=P(X_t\mid X_{t-1})$ (modello di transizione) e ipotesi del sensore $P(E_t\mid X_{0:t},E_{1:t-1})=P(E_t\mid X_t)$ (modello del sensore): congiunta $P(X_0)\prod_t P(X_t\mid X_{t-1})P(E_t\mid X_t)$. Un HMM ha uno stato discreto a $S$ valori: transizione = matrice $\mathbf T$ ($T_{ij}=P(X_t=j\mid X_{t-1}=i)$), sensore = matrici diagonali $\mathbf O_t$. Compiti: filtraggio $P(X_t\mid e_{1:t})$, predizione $P(X_{t+k}\mid e_{1:t})$, smoothing $P(X_{t-k}\mid e_{1:t})$, spiegazione più probabile $\arg\max P(x_{1:t}\mid e_{1:t})$. Filtraggio ricorsivo: $\mathbf f_t=\alpha,\mathbf O_t\mathbf T^\top\mathbf f_{t-1}$ (predizione, poi aggiornamento). Mondo dell'ombrello: $\mathbf f_1=\langle0{,}818;\ 0{,}182\rangle$, $\mathbf f_2=\langle0{,}883;\ 0{,}117\rangle$. Senza normalizzare, $\mathbf s_t=\mathbf O_t\mathbf T^\top\mathbf s_{t-1}$ dà la verosimiglianza $P(e_{1:t})$.Ragionamento probabilistico nel tempo - catene di Markov, HMM, filtraggio e smoothing →). Prior $\mathbf P(X_0)=\langle0{,}5;\ 0{,}5\rangle$. Transizione ($\mathbf T$, riga = stato di partenza, colonne pulito/sporco) ed emissione ($\mathbf O^{e}$ diagonale): $$\mathbf T=\begin{pmatrix}0{,}5&0{,}5\\0{,}8&0{,}2\end{pmatrix},\quad \mathbf O^{\text{mama}}=\mathbf O^{\text{papa}}=\begin{pmatrix}0{,}4&0\\0&0{,}1\end{pmatrix},\quad \mathbf O^{\text{poo-poo}}=\mathbf O^{\text{pee-pee}}=\begin{pmatrix}0{,}1&0\\0&0{,}4\end{pmatrix}.$$

Si vuole $P(e_1,e_2,e_3,e_4)=\sum_{x_4}P(e_1,\dots,e_4,x_4)$ (la probabilità della sequenza è la somma, sullo stato finale, della probabilità congiunta con quello stato).

Soluzione

Ricorsione. Sia $\mathbf s_t=\mathbf P(e_{1:t},X_t)$. Per le due ipotesi di Markov: $$\mathbf s_t=\mathbf P(e_t\mid X_t)\sum_{x_{t-1}}\mathbf P(X_t\mid x_{t-1})\,s_{t-1}(x_{t-1})\quad\Longleftrightarrow\quad\mathbf s_t=\mathbf O_t\,\mathbf T^\top\,\mathbf s_{t-1},\qquad\mathbf s_0=\mathbf P(X_0).$$ È il filtraggio senza la normalizzazione $\alpha$: così la somma finale conserva $P(e_{1:t})$.

Passo 1, "mama". $\mathbf T^\top\mathbf s_0=\begin{pmatrix}0{,}5&0{,}8\\0{,}5&0{,}2\end{pmatrix}\begin{pmatrix}0{,}5\\0{,}5\end{pmatrix}=\begin{pmatrix}0{,}65\\0{,}35\end{pmatrix}$ (probabilità di essere pulito/sporco al primo cambio: $0{,}5\cdot0{,}5+0{,}5\cdot0{,}8=0{,}65$). Moltiplicando per $\mathbf O^{\text{mama}}$: $\mathbf s_1=\langle0{,}4\cdot0{,}65;\ 0{,}1\cdot0{,}35\rangle=\langle0{,}260;\ 0{,}035\rangle$.

Passo 2, "mama". $\mathbf T^\top\mathbf s_1=\langle0{,}5\cdot0{,}26+0{,}8\cdot0{,}035;\ 0{,}5\cdot0{,}26+0{,}2\cdot0{,}035\rangle=\langle0{,}158;\ 0{,}137\rangle$, poi $\mathbf s_2=\langle0{,}4\cdot0{,}158;\ 0{,}1\cdot0{,}137\rangle=\langle0{,}0632;\ 0{,}0137\rangle$.

Passo 3, "pee-pee". $\mathbf T^\top\mathbf s_2=\langle0{,}5\cdot0{,}0632+0{,}8\cdot0{,}0137;\ 0{,}5\cdot0{,}0632+0{,}2\cdot0{,}0137\rangle=\langle0{,}04256;\ 0{,}03434\rangle$, poi $\mathbf s_3=\langle0{,}1\cdot0{,}04256;\ 0{,}4\cdot0{,}03434\rangle=\langle0{,}004256;\ 0{,}013736\rangle$.

Passo 4, "pee-pee". $\mathbf T^\top\mathbf s_3=\langle0{,}5\cdot0{,}004256+0{,}8\cdot0{,}013736;\ 0{,}5\cdot0{,}004256+0{,}2\cdot0{,}013736\rangle=\langle0{,}0131168;\ 0{,}0048752\rangle$, poi $\mathbf s_4=\langle0{,}1\cdot0{,}0131168;\ 0{,}4\cdot0{,}0048752\rangle=\langle0{,}00131168;\ 0{,}00195008\rangle$.

Somma. $$P(e_1,e_2,e_3,e_4)=0{,}00131168+0{,}00195008=0{,}00326176\approx0{,}0033.$$ Le slide arrotondano ogni vettore a tre decimali ($\mathbf s_1=\langle0{,}260;\,0{,}035\rangle$, $\mathbf s_2=\langle0{,}063;\,0{,}014\rangle$, $\mathbf s_3=\langle0{,}004;\,0{,}014\rangle$, $\mathbf s_4=\langle0{,}001;\,0{,}002\rangle$) e scrivono $0{,}001+0{,}002=0{,}003$: l'arrotondamento a ogni passo fa perdere circa l'$8\%$ del valore (le componenti di $\mathbf s_4$ hanno una sola cifra significativa). Il valore calcolato senza arrotondare è $0{,}00326$.

Controlli.

• Forza bruta: sommando il prodotto $P(x_0)\prod_tP(x_t\mid x_{t-1})P(e_t\mid x_t)$ su tutte le $2^5=32$ sequenze di stati $x_0,\dots,x_4$ si ottiene $0{,}00326176$.
• Prodotto dei fattori di normalizzazione del filtraggio: $0{,}295\cdot0{,}2607\cdot0{,}2340\cdot0{,}1813=0{,}00326$, perché $P(e_{1:4})=\prod_tP(e_t\mid e_{1:t-1})$.

Cosa si ricava ancora.

• Filtraggio dopo le quattro parole: $\mathbf f_4=\mathbf s_4/\sum\mathbf s_4=\langle0{,}402;\ 0{,}598\rangle$ (pulito $0{,}402$, sporco $0{,}598$: le ultime due parole, "pee-pee", sono più probabili con il pannolino sporco).
• Smoothing con forward-backward ($\mathbf b_{k+1:4}=\mathbf T\mathbf O_{k+1}\mathbf b_{k+2:4}$): $P(\text{pulito}_1\mid e_{1:4})=0{,}840$, $P(\text{pulito}_2\mid e_{1:4})=0{,}862$, $P(\text{pulito}_3\mid e_{1:4})=0{,}326$, $P(\text{pulito}_4\mid e_{1:4})=0{,}402$. Dopo la sola prima parola il pannolino è pulito con probabilità $0{,}881$; le due "pee-pee" finali, più probabili con il pannolino sporco, abbassano a $0{,}326$ la probabilità di pulito al terzo cambio.

Codice

import numpy as np

T = np.array([[0.5, 0.5],          # T[i, j] = P(X_t = j | X_{t-1} = i); stati: [pulito, sporco]
              [0.8, 0.2]])
O = {'mama': np.diag([0.4, 0.1]), 'papa': np.diag([0.4, 0.1]),      # P(parola | stato) sulla diagonale
     'poo-poo': np.diag([0.1, 0.4]), 'pee-pee': np.diag([0.1, 0.4])}
s = np.array([0.5, 0.5])           # P(X_0): pulito e sporco equiprobabili

for parola in ['mama', 'mama', 'pee-pee', 'pee-pee']:
    s = O[parola] @ T.T @ s        # s_t = O_t T^T s_{t-1}, SENZA normalizzare
    print(parola, s)
print("P(sequenza) =", s.sum())
print("filtraggio dopo 4 parole:", s / s.sum())

Output:

mama [0.26  0.035]
mama [0.0632 0.0137]
pee-pee [0.004256 0.013736]
pee-pee [0.00131168 0.00195008]
P(sequenza) = 0.00326176
filtraggio dopo 4 parole: [0.40213872 0.59786128]