WMR 13 - Hidden Markov Models I

• Date: [2020-04-06 lun 14:52]

• Course Site: Web Mining e Retrieval (a.a. 2019/20)

• Lecturer: Roberto Basili.

• Slides: ()

• Table of Contents:

In questa lezione vediamo come poter trattare fenomeni sequenziali linguistici (ma non solo) attraverso un approccio Bayesiano tramite l'utilizzo di modelli markoviani noti cone il nome di Hidden Markov Models. Questi modelli vengono utilizzati per prendere decisioni in un contesto in cui abbiamo una sequenza di eventi certi di cui però non conosciamo le cause, ovvero non conosciamo gli stati interni che hanno generato quella sequenza.

In questa serie di lezioni rispetto agli hidden markov models affronteremo i seguenti argomenti:

• Prima introduciamo il concetto di modello statistico per un linguaggio.

• Poi introduciamo gli hidden markov models.

• Infine impararemo un modo per apprendere un hidden markov model dai dati (Baun-Welch method), per poi generalizzarlo ad altri task.

Come abbiamo visto nelle precedenti lezioni le strutture linguistiche sintattiche veicolano delle informazioni cruciali per il machine learning. Il modello più utilizzato per rappresentare queste strutture sintattiche sono le grammatiche formali.

S   -> NP V
S   -> NP
NP  -> PN
NP  -> N
NP  -> Adj N
N   -> "imposta"
V   -> "imposta"
Adj -> "pesane"
PN  -> "Pesante"

Utilizzando le grammatiche formali possiamo infatti lavorare con delle rappresentazioni alboree della sintassi della frase. Queste strutture vengono chiamate parse trees.

Notiamo che alcuni parse più sono più "rari" di altri, nel senso che raramente incontriamo strutture del genere nell'utilizzo comune della lingua. Nell'esempio precedente il parse tree a sinistra è molto strano, in quanto "Pesante" viene interpretato come il nome proprio di una persona, e "imposta" come un verbo diretto.

Per cercare di modellare questa differenza tra parse tree "rari" e parse tree "comuni" possiamo introdurre delle probabilità alle varie regole di una grammatica formale, ottenendo così facendo delle grammatiche formali probabilistiche. La probabilità associata ad una regola rappresenta la probabilità di utilizzare quella particolare regola di trasformazione durante la generazione della frase.

S   -> NP V          0.7
S   -> NP            0.3
NP  -> PN            0.1
NP  -> N             0.6
NP  -> Adj N         0.3
N   -> "imposta"     0.6
V   -> "imposta"     0.4
Adj -> "pesane"      0.8
PN  -> "Pesante"     0.2

L'introduzione della probabilità ci permette di associare ad ogni parse tree un valore di probabilità, ottenuto moltiplicando i valori di probabilità associati alla presenza di ogni regola (arco) che compone l'albero.

Rispetto all'esempio di prima troviamo le seguenti probabilità per i due parse trees:

\[\begin{split} P(((\text{Pesante})_{\text{Pn}} (\text{imposta})_{\text{V}})_{\text{S}}) &= 0.7 \cdot 0.1 \cdot 0.2 \cdot 0.4 = 0.0084 \\ \\ P(((\text{Pesante})_{\text{Adj}} (\text{imposta})_{\text{N}})_{\text{S}}) &= 0.3 \cdot 0.3 \cdot 0.8 \cdot 0.6 = 0.0432 \\ \end{split}\]

Introducendo le probabilità abbiamo i seguenti vantaggi:

1. Muovendoci verso gli alberi più probabili siamo quindi in grado di affrontare eventuali problematiche di ambiguità.

2. Potendo assegnare dei valori di probabilità anche ad alberi incompleti, o mal strutturati, siamo in grado di avere una maggiore tolleranza agli errori.

3. Passando dalla probabilità vado da un modello discreto in cui tutte le regole hanno la stessa importanza, ad un modello quantitativo che ci permette di utilizzare gli strumenti offerti dalla teoria della probabilità.

In questo momento pensiamo al linguaggio non come ad un teoria, ma come all'emergenza di eventi a cui possiamo assegnare delle probabilità (language in use).

Supponiamo adesso di avere una sequenza di simboli che seguono una successione temporale rigida, ovvero totalmente ordinata rispetto al crescere del tempo, e che rappresentano dei segnali emessi da una certa sorgente.

Per modellare questo fenomeno possiamo utilizzare un language model, che assume che ogni emissione (simbolo) è una variabile aleatoria \(X\) tale che

• Assume come valori i simboli presenti in un alfabeto \(A\).

• Per descrivere l'incertezza del particolare segnale emesso si utilizza la probabilità

  \[P(X = w_i) \;\;\;,\; w_i \in A\]

  e quindi l'evento \((X_i = w_j)\) significa che all'i-esimo passo, ovvero all'i-esimo simbolo emesso, abbiamo incontrato la parola \(w_j\).

Dato che tutti i simboli emessi devono appartenere all'alfabeto \(A\), troviamo che

\[\sum_j P(X_i = w_j) = 1\]

Data una sequenza di variabili aleatorie \(X_1, X_2, \ldots, X_T\) ciascuna delle quali assume valori in un insieme numerabili \(W = \{p_1, p_2, \ldots, p_N\}\) detto anche state space, per avere una catena di Markov la sequenza di v.a. deve rispettare le seguenti due proprietà:

• Limited horizon property: Si basa sul tagliare la dipendenza dell'osservazione futura dalla storia delle osservazioni passate.

  \[P(X_{t+1} = p_k | X_1, ..., X_t) = P(X_{t+1} = p_k | X_t)\]

• Time invariant: Al variare del tempo \(t\) le probabilità di passare da uno stato ad un altro non cambia

  \[P(X_{t+1} = p_k | X_t = p_l) = P(X_2 = p_k | X_1 = p_l) \;\;\;\; \forall t > 1\]

Un modello di Markov può essere rappresentato analiticamente da una matrice di transizione \(A\), che contiene le varie probabilità di cambiamento tra stati. La matrice di transizione è definita come segue,

\[a_{i,j} = P(X_{t+1} = p_j \;\;|\;\; X_t = p_i)\]

notando poi che

• \(\forall i, j \;\; a_{i,j} \geq 0\)

• \(\forall i \;\; \sum_j a_{i, j} = 1\)

Graficamente possiamo rappresentare un modello di Markov con un grafo in cui i nodi sono i possibili stati in cui la catena si può trovare, e gli archi rappresentano le transizioni da stato in stato, e sono etichettati con le relative probabilità.

Consideriamo il problema del Part-Of-Speech tagging, che consiste, data una sequenza di morfemi \(w_1, \ldots, w_n\) con delle descrizioni sintattiche ambigue (part-of-speech tags), di assegnare la sequenza degli n POS tags \(t_{j_1}, \ldots, t_{j_n}\) che caratterizzano tutte le parole \(w_i\).

Ad esempio, "Secretariat is expected to race tomorrow". Possiamo assegnare a questa frase le seguenti sequence di POS tags

NNP VBZ VBN TO VB NR
NNP VBZ VBN TO NN NR

Per capire quale sequenza tra le due date è la più promettente possiamo utilizzare un modello markoviano rappresentato dal seguente grafo

notiamo che i nodi del grafo, che rappresentano gli stati della catena, sono le part of speech.

Data una sequenza di morfemi \(w_1, \ldots, w_n\) vogliamo trovare i POS tags che massimizzano la probabilità

\[P(w_1, \ldots, w_n, t_1, \ldots, t_n)\]

ovvero tali che

\[(t_1, \ldots, t_n) =\underset{\text{pos}_1, \ldots, \text{pos}_n}{\text{argmax}} P(w_1, \ldots, w_n, \text{pos}_1, \ldots, \text{pos}_n)\]

Dato poi che siamo interessati solamente all'argmax, possiamo utilizzare il fatto che

\[P(w_1, \ldots, w_n, \text{pos}_1, \ldots, \text{pos}_n) = P(\text{pos}_1, \ldots, \text{pos}_n | w_1, \ldots, w_n) \cdot P(w_1, \ldots, w_n)\]

e dal fatto che \(P(w_1, \ldots, w_n)\) è costante al variare dei pos tags, per considerare solamente i tags che massimizzano la seguente probabilità

\[(t_1, \ldots, t_n) =\underset{\text{pos}_1, \ldots, \text{pos}_n}{\text{argmax}} P(\text{pos}_1, \ldots, \text{pos}_n | w_1, \ldots, w_n)\]

Utilizzando poi la legge di Bayes troviamo

\[(t_1, \ldots, t_n) =\underset{\text{pos}_1, \ldots, \text{pos}_n}{\text{argmax}} P(w_1, \ldots, w_n | \text{pos}_1, \ldots, \text{pos}_n) \cdot P(\text{pos}_1, \ldots, \text{pos}_n)\]