Modelli markoviani nascosti e grammatiche stocastiche context free

1.Modelli state space
......
... ...
Processo nascosto
Osservazioni
Xt-1 Xt Xt+1
Yt-1 Yt Yt+1
Figura 1.1: Rappresentazione grafica di un modello state space
nascosto (Hidden Markov Model, HMM). I modelli HMM sono trattati in dettaglio
nel Capitolo 2.
Per descrivere un modello state space bisogna precisare la struttura probabili-
stica dei due processi coinvolti; a tal fine e` necessario definire le seguenti quantita`,
specificate a meno di un parametro incognito λ.
• La distribuzione di probabilita` iniziale del processo markoviano nascosto: defi-
nita come la distribuzione della variabile casuale X1 con densita` pi(·) rispetto
alla misura µ sullo spazio di probabilita` (X,F) in cui e` definito il processo:
X1 ∼ pi(x)dµ(x).
• Le distribuzioni di probabilita` di transizione del processo markoviano nascosto:
per t = 2, . . . , T la distribuzione di Xt|Xt−1 = xt−1 con densita` at(xt−1, ·)
rispetto alla misura µ:
Xt|Xt−1 = xt−1 ∼ at(xt−1, x)dµ(x).
• La distribuzione di probabilita` condizionata delle osservazioni : definita come
la distribuzione di Yt|Xt = xt, per t = 1, . . . , T , con densita` bt(xt, ·) rispetto
alla misura η sullo spazio di probabilita` (Y,G) in cui e` definito il processo delle
osservazioni:
Yt|Xt = xt ∼ bt(xt, y)dη(y).
Al fine di preservare la generalita` del modello nessuna ipotesi e` stata introdotta
relativamente agli spazi di probabilita` e alle variabili casuali dei due processi. Nel
caso in cui gli spazi (X,F) e (Y,G) siano continui, le misure µ e η sono misure di
Lebesgue, mentre nel caso discreto sono misure di conteggio.
Molteplici sono gli obiettivi che si vogliono raggiungere tramite lo studio dei mo-
delli state space; alcuni riguardano il processo nascosto, altri il processo osservabile,
altri ancora coinvolgono i parametri incogniti. Prima di presentare da un punto di
vista piu` teorico le principali problematiche legate a questi tre aspetti, si portano
alcuni esempi che mettono in evidenza la versatilita` di tali modelli.
2
1.Modelli state space
Esempio 1.1 (Ingegneria). Un esempio di applicazione dei modelli state space in
ambito ingegneristico e` rappresentato dal riconoscimento di segnali acustici (Levin-
son et al., 1983; Rabiner e Juang, 1993). Il segnale ricevuto e` suddiviso in brevi
intervalli temporali, ciascuno dei quali e` assegnato a una categoria scelta all’inter-
no di un insieme finito. Tali categorie rappresentano i possibili stati del processo
osservabile (Yt)t≥1. La variabile di stato Xt e` invece il segnale realmente trasmesso
nel t-simo intervallo di tempo. Il principale problema a cui si e` interessati e` quello
di ricostruire il piu` accuratamente possibile la sequenza di segnali che puo` avere
generato le osservazioni che si hanno a disposizione.
Esempio 1.2 (Biologia). In Biologia e` possibile utilizzare i modelli markoviani na-
scosti per il problema dell’individuazione delle isole cg in una sequenza di DNA
(Durbin et al., 1998). Un frammento di DNA e` una successione di basi azotate,
rappresentate da lettere appartenenti all’alfabeto {a,c,g,t}, le quali hanno tra di
loro una dipendenza di tipo markoviano. In alcune sequenze di DNA, definite isole
cg, la coppia di basi cg appare con maggiore frequenza; l’obiettivo dell’applicazione
e` determinare, data una sequenza di basi, la presenza di una isola cg. Lo spazio
degli stati per il processo nascosto e` {a, c, g, t} × {0, 1}, dove 1 e 0 indicano rispet-
tivamente la presenza o l’assenza di una isola cg. Le osservazioni invece sono date
dalla sola lettera, senza l’indicatore booleano. L’obiettivo e` quello di identificare le
isole cg presenti nel frammento di DNA basandosi semplicemente sulla sequenza di
osservazioni.
Esempio 1.3 (Geofisica). I modelli markoviani nascosti sono stati utilizzati per
modellare le precipitazioni piovose in diverse aree di interesse (Zucchini e Guttorp,
1991). Gli stati della catena markoviana nascosta indicano le differenti condizioni
climatiche (sereno, piovoso, nuvoloso,. . . ) mentre i dati osservati sono le quantita`
di precipitazioni giornaliere. Le probabilita` di transizione fra gli stati del processo
nascosto sono calcolate a partire da alcune variabili di tipo meteorologico. I risultati
ottenuti dallo studio di tale modello hanno stabilito che, con riferimento al caso
preso in esame, le quantita` di pioggia cadute nelle varie aree sono indipendenti una
volta fissate le condizioni climatiche.
1.2 Problemi relativi al processo nascosto
In questo paragrafo si introducono i principali problemi relativi allo studio del
processo nascosto nei modelli state space e le ricorsioni atte a risolverli.
Sono necessarie alcune precisazioni sulla notazione utilizzata. Dati due istanti
temporali r e t, con r < t, si indica con xtr la successione xr, xr+1, . . . , xt−1, xt degli
stati del processo nascosto; analogamente si avra` ytr = (yr, yr+1, . . . , yt−1, yt). La
densita` condizionale di due vettori aleatori qualsiasi W e Z e` indicata con p(w|z),
mentre per la densita` condizionale di Xt dati Y s1 = ys1 si usa la notazione ft|s(xt|ys1).
Quest’ultima densita` condizionale riveste un ruolo decisivo nello studio dei mo-
delli state space. In particolare si parla di densita` di filtraggio se s = t, densita` di
3
1.Modelli state space
predizione se s < t e densita` di smoothing se s > t. Per il calcolo di tali densita` si
presentano nei paragrafi seguenti alcune ricorsioni di base che mostrano come esse
interagiscano strettamente fra loro.
1.2.1 Problema di predizione
Le densita` di predizione danno una misura della probabilita` dello stato in cui si
trovera` il processo nascosto in futuro, basandosi sulle osservazioni disponibili fino
all’istante presente. Le densita` di predizione a un passo considerano due istanti
temporali consecutivi e possono essere calcolate a partire dalle densita` di filtraggio
secondo la seguente ricorsione:
ft+1|t(xt+1|y
t
1) =
∫
at+1(x, xt+1)ft|t(x|y
t
1)dµ(x) con t = 1, . . . , T − 1. (1.2.1)
Tale formula si ricava condizionando ft+1|t rispetto ai possibili valori di Xt e
sfruttando l’indipendenza di Xt+1 e Y t1 condizionatamente a Xt.
Nel caso di processi continui la misura µ e` la misura di Lebesgue e l’integrale e`
l’integrale secondo Lebesgue calcolato sullo spazio X, che solitamente corrisponde a
un opportuno integrale secondo Riemann. Se invece si considera uno spazio discreto
la misura µ e` la misura conteggio e l’integrale diventa una sommatoria su tutti gli
elementi di X. Tali considerazioni valgono per tutte le formule presentate in seguito.
In modo analogo si possono calcolare le densita` di predizione a k passi, le qua-
li “guardano” a un futuro piu` lontano. La ricorsione in questo caso si ha per
t = 1, . . . , T − 1 con k ∈ {1, . . . , T − t − 1} ed e` una generalizzazione della formula
(1.2.1):
ft+k|t(xt+k|y
t
1) =
∫
at+k(x, xt+k)ft+k−1|t(x|y
t
1)dµ(x).
Si puo` calcolare anche la densita` di predizione per le osservazioni, nel caso in
cui si vogliano studiare le probabilita` dei futuri stati del processo osservabile. Tale
densita` e` indicata con p(yt+1|yt1) e si calcola ricorsivamente sfruttando le densita`
di predizione del processo degli stati, le quali richiamano a loro volta le densita` di
filtraggio. Condizionando la densita` di predizione per le osservazioni ai possibili
valori di Xt+1 e osservando che Yt+1 e (Y1, . . . , Yt) sono indipendenti dato Xt+1 si
ottiene la seguente formula:
p(yt+1|yt1) =
∫
bt+1(x, yt+1)ft+1|t(x|y
t
1)dµ(x). (1.2.2)
1.2.2 Problema di filtraggio
Il problema del filtraggio consiste nel calcolare la probabilita` relativa a uno stato
nascosto avendo a disposizione tutte le osservazioni associate ai vari stati fino allo
stato attuale; si vogliono cioe` determinare per ogni istante t le densita` di filtraggio.
La ricorsione che permette di calcolare tali densita` coinvolge le densita` di predizione
4
1.Modelli state space
per le osservazioni e le densita` di predizione secondo la seguente formula, ottenuta
sfruttando la formula di Bayes per le distribuzioni condizionate:
ft|t(xt|y
t
1) =
bt(xt, yt)ft|t−1(xt|y
t−1
1 )
p(yt|y
t−1
1 )
con t = 1, . . . , T − 1.
Sostituendo ft|t−1 con la corrispondente espressione calcolata in (1.2.1) si puo` espli-
citare la ricorsione sulle densita` di filtraggio e osservare che le uniche quantita` coin-
volte nel calcolo di ft|t sono la densita` di predizione per le osservazioni e la densita`
di filtraggio all’istante precedente:
ft|t(xt|y
t
1) =
bt(xt, yt)
∫
at(x, xt)ft−1|t−1(x|y
t−1
1 )dµ(x)
p(yt|y
t−1
1 )
. (1.2.3)
1.2.3 Problema di smoothing
La densita` di smoothing descrive l’incertezza associata a un dato stato del processo
latente condizionatamente ai dati disponibili sulle osservazioni passate, presenti e
future. Data una serie completa di osservazioni (y1, . . . , yT ) si vogliono determinare
le probabilita` associate ai singoli stati nascosti che possono averla generata. Ci sono
tre tipologie di problemi legati allo smoothing: lo smoothing su intervallo fisso, dove
si e` interessati a determinare ft|T (xt|yT1 ) per ogni t = 1, . . . , T ; lo smoothing con
ritardo, in cui si vuole calcolare ft|t+R(xt|y
t+R
1 ) con R > 0 fissato; lo smoothing di
punto fisso, in cui si cerca ft|P (xt|yP1 ) per un determinato istante temporale t al
crescere di P > t. Briers et al. (2004) hanno dimostrato che e` possibile utilizzare un
unico schema per risolvere tutti tre i problemi, basato sullo smoothing su intervallo
fisso.
Si puo` notare che, condizionatamente a Y T1 , (XT , XT−1, . . . , X1) e` una catena di
Markov non omogenea all’indietro con densita` iniziale pari a fT |T (xT |yT1 ) e densita`
di transizione pari a
p(xt|xt+1, yT1 ) = p(xt|xt+1, yt1) =
at+1(xt, xt+1)ft|t(xt|yt1)
ft+1|t(xt+1|yt1)
. (1.2.4)
Per dimostrare la dipendenza markoviana condizionatamente a Y T1 basta osservare
che Xt e (XTt+2, Y Tt+2) sono indipendenti data Xt+1 e quindi vale
p(xt|xTt+1, y
T
1 ) = p(xt|xt+1, yt1).
La formula per la densita` di transizione segue direttamente dall’applicazione della
formula di Bayes.
E` possibile ora ricavare una ricorsione per la densita` di smoothing. Tramite una
ricorsione in avanti si calcolano le densita` di filtraggio e le densita` di predizione, le
5
1.Modelli state space
quali sono utilizzate per calcolare la densita` di smoothing nella seguente ricorsione
all’indietro per t = T − 1, . . . , 1:
ft|T (xt|y
T
1 ) = ft|t(xt|yt1)
∫
at+1(xt, x)
ft+1|t(x|yt1
ft+1|T (x|y
T
1 )dµ(x). (1.2.5)
Si osservi che per t = T il problema di smoothing si riconduce a un problema di
filtraggio.
Per ridurre la complessita` di tale ricorsione si puo` utilizzare una procedura di
smoothing che al posto delle densita` di predizione utilizzi le densita` di predizione
per le osservazioni, le quali sono piu` facili da calcolare. Si introduce la seguente
quantita`:
rt|T (xt, y
T
1 ) :=
p(yTt+1|xt)
p(yT
t+1|y
t
1)
con rT |T ≡ 1.
Applicando la formula di Bayes alla distribuzione condizionata rispetto a Y t1 e os-
servando che Y t1 e Y
T
t+1 sono indipendenti dato Xt, si dimostra che la densita` di
smoothing soddisfa la relazione
ft|T (xt|y
T
1 ) = ft|t(xt|yt1)rt|T (xt, yT1 ). (1.2.6)
L’idea e` quella di combinare i risultati di una ricorsione in avanti per il calcolo delle
densita` di filtraggio con quelli di una ricorsione all’indietro per il calcolo di rt|T .
In particolare rt|T si trova a partire dalle densita` di predizione per le osservazioni
secondo la seguente ricorsione per t = T − 1, . . . , 1:
rt|T (xt, y
T
1 ) =
∫
bt+1(x, yt+1)at+1(xt, x)rt+1|T (x, yT1 )dµ(x)
p(yt+1|yt1)
.
Tale formula si dimostra condizionando p(yTt+1|xt) rispetto a Xt+1 e sfruttando prima
l’indipendenza di Y Tt+1 e Xt dato Xt+1, poi quella di Yt+1 e Y Tt+2 dato Xt+1.
Utilizzando la markovianita` del processo nascosto e le densita` di smoothing e` pos-
sibile calcolare anche la distribuzione condizionale del vettore latente (Xs, Xs+1, . . . , Xt)
dato (Y1, . . . , Yt) per s = 1, . . . , t− 1 con t ≤ T :
p(xts|y
t
1) = ft|T (xt|yT1 )
t−1∏
i=s
p(xi|xi+1, yT1 ).
1.2.4 Problema di decoding
Le densita` introdotte finora non permettono di risolvere il problema di decoding,
cioe` non consentono di determinare la sequenza di stati nascosti che con maggiore
probabilita` ha generato le osservazioni che si hanno a disposizione. Per ottenere tale
risultato Viterbi (1967) ideo` una tecnica di programmazione dinamica che sfrutta
ricorsioni in avanti e all’indietro. Nel caso in cui lo spazio degli stati sia finito, tale
tecnica prende il nome di algoritmo di Viterbi. Nel Capitolo 2 si tratta in modo piu`
approfondito il problema di decoding e si descrive nel dettaglio tale algoritmo.
6