Un Modello linguistico o Language Model, costruito a partire da un corpus di training in una determinata lingua, permette di associare una probabilità ad una determinata sequenza di parole.
Le applicazioni sono molteplici e spaziano dal confronto sulla verosimiglianza di frasi, al calcolo della probabilità della parola successiva in una frase, all'autocompletamento, alla correzione di parole fuori contesto in una frase, all'individuazione dell'output più probabile nella speech recognition,  al supporto predittivo alla comunicazione aumentata e accessibile.

Attraverso un approccio "tradizionale" statistico-probabilistico basato sugli N-Grammi, sequenze di N parole nel corpus, esaminiamo come è possibile costruire un modello di linguaggio in modo relativamente semplice.

Probabilità di Unigrammi e N-Grammi

La probabilità degli Unigrammi all'interno del corpus, ovvero delle singole parole, è banalmente $\displaystyle P(w)=\frac{C(w)}{m}$  ovvero il rapporto tra il numero di occorrenze della parola nel corpus e la dimensione del corpus.

Dato invece un generico N-Gramma  $w_1^n=w_1w_2\cdots w_n$  definiamo la probabilità dell'N-Gramma come probabilità condizionata $\displaystyle P(w_n|w_1\cdots w_{n-1}) =P(w_n|w_1^{n-1}) =\frac{C(w_1^n)}{\sum C(w_1^{n-1} w)}$  ,  rapporto tra le occorrenze dell'N-Gramma e quelle di tutti gli N-Grammi nel Corpus le cui n-1 prime parole sono $w_1^{n-1}$.

Con determinati accorgimenti sulla conclusione della frase che vedremo a seguire, è possibile semplificare l'espressione come $\displaystyle P(w_n|w_1\cdots w_{n-1}) =P(w_n|w_1^{n-1}) =\frac{C(w_1^n)}{C(w_1^{n-1})}$ , rapporto tra le occorrenze dell'N-Gramma e quelle dell' (N-1)-Gramma composto dalle prime N-1 parole 

Probabilità di una frase

Data una frase $w_1w_2\dots w_n$  possiamo calcolare la probabilità $P(w_1w_2\dots w_n)$  della sequenza utilizzando la semplice relazione relativa alla probabilità condizionata per cui $P(A \cap B)=P(A)P(B|A)$  . Avremo pertanto che la probabilità di una frase è riconducibile al prodotto delle probabilità di N-Grammi secondo la relazione:

$\displaystyle P(w_1^n)=P(w_1^{n-1})P(w_n|w_1^{n-1}) \\ =P(w_1^{n-2})P(w_{n-1}|w_1^{n-2})P(w_n|w_1^{n-1}) \\ = P(w_1)P(w_2|w_1)P(w_3|w_1^2)\cdots P(w_n|w_1^{n-1}) \\ =P(w_1)\prod_{i=2}^n P(w_i|w_1^{i-1})$

Ciò è intuitivamente verificabile con un esempio, ipotizzando ad esempio di voler calcolare la probabilità della frase "oggi vado al mare" avremo $P(\text{oggi vado al mare}) = P(\text{oggi})P(\text{vado}|\text{oggi})P(\text{al}|\text{oggi vado})P(\text{mare}|\text{oggi vado al})$

Approssimazione di Markov

La probabilità di una frase come calcolata sopra si scontra con un primo limite obiettivo, ovvero che è calcolabile e non nulla solo se nel corpus sono presenti tutti gli N-Grammi coinvolti nel calcolo. Ciò implicherebbe un corpus enorme dove compaiono tutte le possibili frasi da valutare, ipotesi assolutamente irrealistica e che non consentirebbe al nostro modello di generalizzare.

Si formula quindi l'assunzione che la probabilità di un generico N-Gramma di un qualunque ordine m>n sia ragionevolmente approssimabile come quella del N-Gramma di ordine n   $P(w_k|w_{k-m+1}^{k-1}) \approx P(w_k|w_{k-n+1}^{k-1})$  , ovvero che la probabilità di una parola sia condizionata solo dalle n parole precedenti.
Assumiamo ad esempio n=2 e che quindi il nostro modello sia basato su digrammi, avremo quindi che la probabilità della frase sopra vista diventa: $P(\text{oggi vado al mare}) = P(\text{oggi})P(\text{vado}|\text{oggi})P(\text{al}|\text{vado})P(\text{mare}|\text{al})$
Come vediamo il modello è già in grado di effettuare una prima generalizzazione,  risultando sufficiente la sola presenza nel Corpus dei digrammi coinvolti.  

Più in generale l'approssimazione di Markov per N-Grammi di grado N ci consente di modifcare la probabilità della frase vista sopra come prodotto di N-Grammi al più di grado N:

$\displaystyle P(w_1^n)=P(w_1)\prod_{i=2}^n P(w_i|w_{\max\{1;i-N+1\}}^{i-1})$

Completamento del contesto: inizio e conclusione delle frasi

L'esempio sopra ci mostra che, a prescindere dalla scelta di n, vengono utilizzati nel calcolo anche n-1 N-Grammi di grado inferiore ad n all'inizio della frase.
Questo non è desiderabile per almeno due motivi: oltre al fatto che vengono utilizzati N-Grammi eterogenei con un diverso grado di sensibilità al contesto, andiamo a perdere un'informazione di contesto molto rilevante che è quella relativa all'inizio della frase.
La probabilità dell'unigramma $P(oggi)$ difatti è relativa alla mera frequenza relativa dell'unigramma nel corpus, senza nessuna informazione riguardo alla posizione nella frase.
A questo fine si prependono n-1 token speciali di delimitazione <d>  per rappresentare correttamente il contesto di inizio.
Nel caso esaminato, dove si utilizzano Digrammi, andremo ad inserire un solo <d> in avvio e avremo quindi:
$P(\text{<d>oggi vado al mare}) = P(\text{oggi|<d>})P(\text{vado}|\text{oggi})P(\text{al}|\text{vado})P(\text{mare}|\text{al})$

Utilizzando invece Trigrammi, si inseriranno due <d> in avvio di frase e avremo:
$P(\text{<d><d>oggi vado al mare}) = P(\text{oggi|<d> <d>})P(\text{vado}|\text{<d> oggi})P(\text{al}|\text{oggi vado})P(\text{mare}|\text{vado al})$

Anche alla fine della frase abbiamo una esigenza analoga di corretta rappresentazione del contesto di chiusura, inserendo un solo delimitatore <d> e un corrispondente N-Gramma a valorizzare la probabilità che le ultime N-1 parole rilevino realmente la fine della frase.  
Come accennato sopra, questo accorgimento ci permetterà di utilizzare in modo coerente la relazione $P(w_n|w_1^{n-1}) =\frac{C(w_1^n)}{C(w_1^{n-1})}$ che altrimenti potrebbe risultare inesatta per gli N-Grammi in chiusura di frase.

Riprendendo l'esempio con l'utilizzo di Digrammi avremo:
$P(\text{<d>oggi vado al mare<d>}) = P(\text{oggi|<d>})P(\text{vado}|\text{oggi})P(\text{al}|\text{vado})P(\text{mare}|\text{al})P(\text{<d>}|\text{mare})$

Mentre utilizzando Trigrammi:
$P(\text{<d><d>oggi vado al mare<d>}) = P(\text{oggi|<d> <d>})P(\text{vado}|\text{<d> oggi})P(\text{al}|\text{oggi vado})P(\text{mare}|\text{vado al})P(\text{<d>}|\text{mare})$

Con l'inserimento dei delimitatori tra le n parole possiamo quindi definire in modo più compatto la probabilità della frase: 

$\displaystyle P(w_1^n)= \prod_{i=N}^n P(w_i|w_{i-N+1}^{i-1})$

Costruzione delle Matrici delle occorrenze e delle probabilità

Definiti i criteri per il modello linguistico, si procede quidi al calcolo della probabilità degli N-Grammi organizzando i dati del Corpus di training in Matrici.
Il primo passo è la realizzazione di una matrice delle occorrenze degli N-Grammi, dove le righe riportano gli (N-1)-Grammi ai quali sono condizionate la parole w indicate nelle colonne.
Consideriamo ad esempio il seguente corpus di 3 frasi sul quale costruire un modello con Digrammi:
Oggi vado al mare
Al mare oggi piove
Se piove vado al parco

$\begin{array}{r|r|r|r|} C(w_i|w_{i-1})& <d> & oggi & vado & al & mare & piove & se & parco \\ \hline <d> & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ \hline oggi & 0 &0 & 1 &0 &0 & 1 & 0 & 0\\ \hline vado & 0 & 0 &0 & 2 & 0 &0 &0 &0\\ \hline al & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 1\\ \hline mare & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline piove & 1 &0 & 1 &0 & 0 &0 & 0 & 0\\ \hline se & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ \hline parco & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array}$

$\begin{array}{r|r|r|r|} P(w_i|w_{i-1})& <d> & oggi & vado & al & mare & piove & se & parco \\ \hline <d> & 0 & 0,33 & 0 & 0,33 & 0 & 0 & 0,33 & 0 \\ \hline oggi & 0 &0 & 0,50 &0 &0 & 0,50 & 0 & 0\\ \hline vado & 0 & 0 &0 & 1 & 0 &0 &0 &0\\ \hline al & 0 & 0 & 0 & 0 & 0,67 & 0 & 0 & 0,33\\ \hline mare & 0,50 & 0,50 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline piove & 0,50 &0 & 0,50 &0 & 0 &0 & 0 & 0\\ \hline se & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ \hline parco & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array}$

Per calcolare la probabilità di una qualunque frase $w_1^n$ , inseriti gli opportuni delimitatori, effettueremo quindi una produttoria delle probabilità dei Digrammi $\displaystyle P(w_1^n)=\prod_{i=1}^{n-1} P(w_{i+1}|w_i)$  .  Nella pratica, con corpus estesi e probabilità che tendono rapidamente a zero, è opportuno per evitare problemi di underflow utilizzare la relazione in forma logaritmica    $\displaystyle \log P(w_1^n)=\sum_{i=1}^{n-1} \log P(w_{i+1}|w_i)$

Proviamo ad esempio a calcolare la probabilità di  <d>Oggi piove<d>  : $P(\text{<d>oggi piove<d>})=P(\text{oggi}|\text{<d>})P(\text{piove}|\text{oggi})P(\text{<d>}|\text{piove})=0,33\cdot 0,50\cdot 0,50=0,0825$

Generalizzazione del modello: dizionario e parole sconosciute

Un primo limite che si rileva immediatamente è quello relativo all'utilizzo di parole sconosciute. Il modello come impostato non appare applicabile a frasi con parole non presenti nel corpus.
Per gestire il caso di parole sconosciute viene costruito un dizionario a partire dal corpus, composto generalemente dalle parole con frequenza uguale o maggiore di un parametro $k$  o in accordo ad altro criterio, sostituendo poi nel corpus tutte le parole non presenti nel dizionario con il token <unk> a rappresentare una parola sconosciuta.
Riprendendo l'esempio sopra, con un dizionario costruito con k=2 , vediamo che le parole se e parco vengono sostituite da <unk> e la nostra matrice delle probabilità viene ricalcolata come:

$\begin{array}{r|r|r|r|} P(w_i|w_{i-1})& <d> & oggi & vado & al & mare & piove & <unk> \\ \hline <d> & 0 & 0,33 & 0 & 0,33 & 0 & 0 & 0,33 \\ \hline oggi & 0 &0 & 0,50 &0 &0 & 0,50 & 0 \\ \hline vado & 0 & 0 &0 & 1 & 0 &0 &0 \\ \hline al & 0 & 0 & 0 & 0 & 0,67 & 0 & 0,33\\ \hline mare & 0,50 & 0,50 & 0 & 0 & 0 & 0 & 0 \\ \hline piove & 0,50 &0 & 0,50 &0 & 0 &0 & 0 \\ \hline <unk> & 0,50 & 0 & 0 & 0 & 0 & 0,50 & 0 \\ \hline \end{array}$

Proviamo ora a calcolare la probabilità di una frase con parole non presenti nel dizionario:
$P(\text{<d>Quando piove vado al museo<d>})=P(\text{<d><unk> piove vado al <unk><d>})= \\ = P(\text{<unk>}|\text{<d>})P(\text{piove}|\text{<unk>})P(\text{vado}|\text{piove})P(\text{al}|\text{vado})P(\text{<unk>}|\text{al})P(\text{<d>}|\text{<unk>})= \\ = 0,33\cdot 0,50\cdot 0,50\cdot 1 \cdot 0,33 \cdot 0,50 =0,0136125$

E' quindi possibile calcolare la probabilità della frase secondo pur in presenza di parole estranee al corpus.

Generalizzazione del modello: k-smoothing, backoff e interpolazione

Un altro limite che rileviamo dall'osservazione matrice di probabilità è relativo all'alto numero di valori pari a zero nella matrice - circostanza tanto più vera quanto meno esteso è il corpus e quanto più alto è il grado N degli N-Grammi utilizzato.
La presenza di un N-Gramma con probabilità zero nel modello, rende automaticamente a probabilità nulla ogni frase che lo contenga a prescindere dall'apporto di probabilità degli altri N-Grammi.
Nell'esempio sopra la frase Oggi piove al mare avrebbe probabilità zero in quanto $P(\text{al}|\text{piove})=0$ , nonostante non appaia come frase del tutto implausibile per il modello.

Questo non è un comportamento generalmente desiderabile e limita la generalizzazione del modello in presenza di N-Grammi non presenti nel Corpus, anche dopo l'adozione di un dizionario. 

Indichiamo tre approcci utilizzati per ovviare a questo problema:

K-smoothing

Questo approccio consiste in un ricalcolo della matrice di probabilità applicando uno smoothing di valore k , dipendente sia dalla numerosità/sparsità della tabella e dal grado di smoothing desiderato, secondo la formula
$\displaystyle P(w_n|w_1^{n-1}) =\frac{C(w_1^n)+k}{C(w_1^{n-1})+k|V|}$ , dove |V| è la dimensione del dizionario, pari al numero di colonne della matrice.

In questo caso, ipotizzando uno smoothing con k=0,1 la nostra matrice sarà ricalcolata a partire dalle occorrenze come:

Vediamo ora che non esistono più probabilità nulle nella matrice (sebbene alcuni casi specifici dovrebbero essere trattati separatamente, come l'ipotesi di un Digramma (<d>|<d>) da porre a zero, in quanto corrispondente ad una frase vuota), ed il modello è in grado di generalizzare su qualunque frase con qualunque parola.

Backoff

L'approccio di backoff prevede, nel caso la probabilità in tabella del N-Gramma $P(w^n_{n-N+1})$ sia nulla, di utilizzare la probabilità del corrispondente (N-1)-Gramma moltiplicato per un coefficiente di riduzione d  , ovvero $d \cdot P(w^n_{n-(N-1)+1})$  .   Generalmente si utilizza un coefficiente $d \approx 0,40$.
Il criterio viene applicato ricorsivamente sino a quando non abbiamo una probabilità non nulla.

Ipotizziamo di avere un modello su Trigrammi e di voler calcolare la probabilità di una frase nella quale occorre  $P(\text{libro}|\text{leggo un})$ con valore in matrice pari a zero:  al suo posto calcoleremo    $d \cdot P(\text{libro}|\text{un})$  , e se anche tale valore fosse nullo, si utilizzerà $d^2 \cdot P(\text{libro})$.

Ovviamente questo approccio prevede di calcolare non solo la matrice delle probabilità degli N-Grammi di ordine N, ma anche quelle di ordine inferiore.

Interpolazione

Simile all'approccio precedente, prevede di prendere comunque in considerazione tutte le probabilità degli N-Grammi di ordine inferiore, da ponderare con opportuni coefficienti decrescenti. Avremo quindi $\displaystyle \hat P(w^n_{n-N+1})=\sum_{i=1}^N \lambda_i P(w^n_{n-N+i})$  , dove $\displaystyle \sum_{i=1}^N \lambda_i =1$.

Nel caso del punto precedente avremo che $\hat P(\text{libro}|\text{leggo un})=\lambda_1 P(\text{libro}|\text{leggo un})+\lambda_2 P(\text{libro}|\text{un})+\lambda_3 P(\text{libro})$

Valutazione del modello e Perplessità

Una volta costruito il modello sul corpus di training e definiti criteri e correttivi per il calcolo della probabilità di una frase, possiamo ottenere una misura della "bontà" del modello, sia in termini della capacità di generalizzare correttamente, sia in termini di aderenza al contesto linguistico/tematico al quale dovrà essere applicato,  valutando le sue performance in termini di capacità di predizione rispetto ad un corpus di test, composto da frasi che il modello non ha utilizzato in fase di training.

La misura generalmente utilizzatà è la Perplessità definita come $\displaystyle PP(W)=\sqrt[m]{\prod_{i=1}^m \frac{1}{P(W_i)}}$  dove W è il corpus di test suddiviso in m N-Grammi indicati con $W_i$  

La perplessità varia a partire da un minimo teorico di 1, ad indicare un modello in grado di predirre esattamente il corpus di test, crescendo man mano che si incontrano N-Grammi con probabilità inferiore ad 1.

Valori tipici della perplessità per modelli di linguaggio addestrati su corpus dimensionalmente rilevanti oscillano nell'ordine tra 100 e 1000, con valori inferiori per modelli ad N-Grammi di ordine superiore, in grado di cogliere in modo più articolato relazioni tra parole più distanti.

 

 

Uno dei task più classici dell'NLP è il Part of Speech Tagging, ovvero l'analisi grammaticale di un testo con attribuzione ad ogni parola della relativa caratteristica lessicale (Nome, Verbo, Aggettivo, Pronome, etc...). 
Tale caratteristica lessicale dipende, oltre che dalla parola, dalla sua collocazione nel contesto della frase: un rilevante numero di parole può assumere una caratteristica diversa a seconda dell'utilizzo; ad esempio "la" può essere articolo, pronome, o nome.

L'approccio con il modello di Markov a stati nascosti è una soluzione classica che permette di ottenere risultati di accuratezza apprezzabili senza utilizzare word embedding.

Modello di Markov a Stati Nascosti (Hidden Markov Model)

Nel modello di Markov a Stati Nascosti andiamo a rappresentare attraverso un grafo orientato ai cui rami sono associate delle probabilità, poi tradotto poi in 2 matrici, la conoscenza desunta da un corpus di training testuale al quale sono già state associate le caratteristiche lessicali.

Stati

Gli Stati nel nostro problema corrispondono alle caratteristiche lessicali - nell'esempio a seguire per semplicità consideriamo solo "Nome", "Verbo", "Articolo".
Parliamo di stati nascosti perchè, quando analizziamo una frase, non conosciamo a priori la sequenza dei corrispondenti Stati - che anzi, è nostro obiettivo determinare nella configurazione più probabile per la frase in esame - ma stiamo osservando gli "Eventi", ovvero le parole della frase che costituiscono l'emissione degli stati corrispondenti.
Nel modello aggiungiamo anche uno stato $\pi$  che corrisponde al delimitatore della frase, quindi rappresentando sia l'inizio che la fine - è pertanto l'unico stato noto a priori.

Transizioni e Matrice di Transizione

Alle possibili Transizioni tra i vari stati vengono associate le probabilità calcolate sul corpus di training:  partendo da un qualsiasi stato $S_i$ la parola successiva quindi sarà riconducibile ad un determinato stato $S_j$con una certa probabilità $\displaystyle P(S_j | S_i) = \frac{C(S_i, S_j) + \varepsilon }{C(S_i) +\varepsilon \cdot N}$ , dove  $C(S_i, S_j)$ è il conteggio nel corpus delle occorrenze della sequenza $S_i$ $S_j$ ,    $C(S_i)$ è il conteggio nel corpus delle occorrenze di $S_i$ ,  una piccola costante di smoothing $\varepsilon$ evita che vi siano transizioni a probabilità nulla ed $N$  è il numero degli stati; 
Tutte le probabilità $P(S_j | S_i)$ saranno collocate in una matrice ${\bf A}_{(N \times N)}$  detta Matrice di transizione.

Emissioni, Dizionario e Matrice di Emissione

Alle possibili Emissioni dei vari stati, nel nostro caso le parole che possono essere manifestazione di un particolare Stato, vengono associale le rispettive probabilità calcolate sul corpus di training:  per un determinato stato $S_i$  e per ogni parola $w_j$nel dizionario ricavato dal corpus, avremo che $\displaystyle P(w_j | S_i) = \frac{C(S_i, w_j) + \varepsilon }{C(S_i) +\varepsilon \cdot |V|}$, dove  $C(S_i, w_j)$ è il conteggio nel corpus delle occorrenze della parola $w_j$ quando compare con stato $S_i$ ,    $C(S_i)$ è il conteggio nel corpus delle occorrenze di $S_i$ ,  una piccola costante di smoothing $\varepsilon$ evita che vi siano emissioni a probabilità nulla e $|V|$  è il numero di parole nel nostro dizionario.

Il dizionario $V$ , specie per corpus rilevanti, è costruito utilizzando non tutte le parole del corpus, ma solo quelle che presentano un frequenza maggiore di un certo valore $k$ (tipicamente 1 o 2) , e aggiungendovi una parola speciale $unk$  a rappresentare una generica corrispondenza non presente nel vocabolario (eventualmente possono essere aggiunte delle parole specializzate $unk\_nom$ , $unk\_ver$ , etc. dove siano implementate regole o un'analisi euristica del suffisso per determinare la possibile appartenenza di una parola sconosciuta a uno specifico Stato).
In fase di training e applicazione del modello, quando viene incontrata una parola non presente nel dizionario viene considerata come $unk$  (oppure, applicando alla parola le opportune analisi euristiche per la possibile associazione a uno Dtato, verrà considerata come  $unk\_Stato$ ).

Ciò permetterà di addestrare e utilizzare il modello con buoni risultati anche per parole non presenti nel set di training.
 
Tutte le probabilità $P(S_j | S_i)$ saranno collocate in una matrice ${\bf B}_{(N \times |V|)}$  detta Matrice di emissione.

Esempio di calcolo delle matrici di transizione ed emissione

Ipotizziamo uno scenario semplificato con un corpus di training composto da sole 3 frasi e con i 3 stati N (nome), V(verbo), A(articolo):

$\underset{A}{\text{il}} \ \underset{N}{\text{gatto}} \ \underset{V}{\text{cerca}} \ \underset{A}{\text{la}} \ \underset{N}{\text{mamma}} \\ \underset{N}{\text{Mario}} \ \underset{V}{\text{suona}} \ \underset{A}{\text{un}} \ \underset{N}{\text{la}} \\ \underset{A}{\text{la}} \ \underset{N}{\text{mamma}} \ \underset{V}{\text{guarda}} \ \underset{A}{\text{il}} \ \underset{N}{\text{gatto}} \\$   

e procediamo al conteggio delle transizioni e degli stati

$\begin{array} {r|r|r|r|r|r} \color{red}{C(S_i,S_j)} & \pi & A & N & V & \color{red}{C(S_i)}\\ \hline \pi & 0 & 2 & 1 & 0 & \color{red}{3}\\ \hline A & 0 & 0 & 5 & 0 & \color{red}{5}\\ \hline N & 3 & 0 & 0 & 3 & \color{red}{6}\\ \hline V & 0 & 3 & 0 & 0 & \color{red}{3}\\ \hline \end{array}$     

e al conteggio delle emissioni, ipotizzando di adottare un dizionario con tutte le parole del corpus.

$\begin{array} {r|c|c|c|c|c|c|c|c|c|c|c|} \color{red}{C(S_i,w_j)} & \text{il} & \text{gatto} & \text{cerca} & \text{la} & \text{mamma} & \text{Mario} & \text{suona} & \text{un} & \text{guarda} & -unk- & -del- \\ \hline \pi & 0 & 0 & 0 & 0 & 0 &0 &0 &0&0&0 &4 \\ \hline A & 2 & 0 & 0 & 2 & 0 &0 &0 &1&0&0 &0\\ \hline N & 0 &2 &0&1&2&1&0&0&0&0&0 \\ \hline V & 0 & 0 & 1 & 0&0&0&1&0&1&0&0 \\ \hline \end{array}$

Procediamo ora al calcolo della matrice di transizione A, utilizzando un coefficiente di smoothing $\varepsilon=0,01$  (che non applichiamo alla transizione $P(\pi|\pi)$ considerata di fatto impossibile, corrispondendo ad una frase nulla)

$\begin{array} {r|r|r|r|r|} \color{red}{P(S_j|S_i)} & \pi & A & N & V \\ \hline \pi & 0 & 0,663 & 0,333 & 0,003 \\ \hline A & 0,002 & 0,002 & 0,994 & 0,002 \\ \hline N & 0,498 & 0,002 & 0,002 & 0,498 \\ \hline V & 0,003 & 0,990 & 0,003 & 0,003 \\ \hline \end{array}$

e al calcolo della matrice di emissione B, utilizzando un coefficiente di smoothing $\varepsilon=0,01$   (per lo stato $\pi$ le emissioni sono sempre certe e verso il delimitatore $-del-$, senza necessità di considerare nello smoothing la ripettiva riga e la rispettiva colonna)

$\begin{array} {r|c|c|c|c|c|c|c|c|c|c|c|} \color{red}{P(w_j|S_i)} & \text{il} & \text{gatto} & \text{cerca} & \text{la} & \text{mamma} & \text{Mario} & \text{suona} & \text{un} & \text{guarda} & -unk- & -del- \\ \hline \pi & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &0&1 \\ \hline A & 0,394 & 0,002 & 0,002 & 0,394 & 0,002 &0,002 &0,002 &0,198&0,002&0,002&0 \\ \hline N & 0,002 &0,330 &0,002&0,166&0,330&0,166&0,002&0,002&0,002&0,002&0 \\ \hline V & 0,003 & 0,003 & 0,326 & 0,003&0,003&0,003&0,326&0,003&0,326&0,003&0 \\ \hline \end{array}$

Rileviamo facilmente che il prodotto delle matrici $\bf AB$ conterrà le probabilità $P(w^{(t+1)}_j|S^{(t)}_i)$ che la parola successiva allo stato $S^{(t)}_i$ sia $w^{(t+1)}_j$

Algoritmo di Viterbi

Data una frase arbitraria da analizzare, dobbiamo trovare la sequenza di stati da associare ad ogni parola, tale da massimizzare la probabilità risultante della frase, calcolata sulla base delle matrici di transizione ed emissione.

Ci viene in aiuto in ciò l'algoritmo di Viterbi , che con un approccio di programmazione dinamica, permette di analizzare i percorsi tra stati sul grafo a partire dallo stato iniziale attraversando gli stati successivi individuando il miglior percorso in relazione alle emissioni date (le $k$ parole della frase $\bf w$).

L'algoritmo prevede la costruzione iterativa per colonne di due matrici  ${\bf C}_{(N \times k)}$  , contenente le probabilità dei migliori percorsi attraversati, e ${\bf D}_{(N \times k)}$ con la traccia degli stati attraversati.

La prima colonna della matrice ${\bf C}_{(N \times k)}$ viene inizializzata ponendo $c_{i,1}=a_{1,i} \cdot b_{i,indice(w_1)}$  , ovvero le probabilità di emettere la prima parola $w_1$ attraverso la transizione dallo stato iniziale verso un primo stato $S_i$.

La prima colonna della La prima colonna della matrice ${\bf D}_{(N \times k)}$ viene inizializzata ponendo $d_{i,1}=0$  in quanto non abbiamo ancora parti precedenti del percorso da tracciare.

Le successive  colonne della matrice ${\bf C}_{(N \times k)}$ vengono iterativamente calcolate come $c_{i,j}=\underset{k}{\max} c_{k,j-1} \cdot a_{k,i}\cdot b_{i,indice(w_j)}$   , scegliendo in pratica di raggiungere lo stato $S_i$ dallo stato precedente $S_k$ che massimizza la probabilità del percorso parziale.
Di conseguenza nella matrice ${\bf D}_{(N \times k)}$ andremo ad inserire proprio tale $k$ calcolato come $d_{i,j}=\underset{k}{\arg \max} \ c_{k,j-1} \cdot a_{k,i}\cdot b_{i,indice(w_j)}$

Una volta calcolate le due matrici, avremo che il massimo valore presente nella colonna $k$  della matrice $\bf C$  rappresenta la probabilità della sequenza di stati più probabile.  In particolare il suo indice  $s_k=\underset{i}{\arg \max} \ c_{i,k}$  ci indicherà lo stato della sequenza più probabile associato all'ultima parola $w_k$ .

Per trovare gli Stati associati alle parole precedenti, itereremo nella matrice $\bf D$ popolata con gli indici delgli stati di provenienza dei vari percorsi, ponendo $s_{j-1}=d_{s_{j},j}$   ,  ottenendo infine l'intera sequenza desiderata degli stati   $S_{s_1}S_{s_2}\cdots S_{s_k}$

Esempio di analisi di una frase con algoritmo di Viterbi

Supponiamo, a partire dalle matrici di transizione ed emissione già calcolate, di voler analizzare la frase  Il gatto mangia un topo

Rileviamo subito che abbiamo 2 parole sconosciute per il nostro dizionario che quindi sostituiremo con -unk- al fine dell'analisi.

Inizializziamo le matrici secondo le formule indicate, partendo dallo stato di inizio frase:

$\begin{array} {r|c|c|c|c|c|} \color{red}{\bf C} & \text{un} & \text{gatto} & \text{mangia} & \text{il} & \text{topo} \\ \hline A & 1,313 \cdot 10^{-1} & & & & \\ \hline N & 6,660 \cdot 10^{-4} & & & & \\ \hline V & 9,000 \cdot 10^{-6}& & & & \\ \hline \end{array}$   $\begin{array} {r|c|c|c|c|c|} \color{red}{\bf D} & \text{un} & \text{gatto} & \text{mangia} & \text{il} & \text{topo} \\ \hline A & 0 & & & & \\ \hline N & 0 & & & & \\ \hline V & 0 & & & & \\ \hline \end{array}$
 

e proseguiamo iterativamente a riempire le successive colonne secondo le formule sopra indicate:

$\begin{array} {r|c|c|c|c|c|} \color{red}{\bf C} & \text{un} & \text{gatto} & \text{mangia} & \text{il} & \text{topo} \\ \hline A & 1,313 \cdot 10^{-1} & 5,251 \cdot 10^{-7} & 1,722 \cdot 10^{-7} & 1,261 \cdot 10^{-5} & 5,044 \cdot 10^{-11} \\ \hline N & 6,660 \cdot 10^{-4} & 4,306 \cdot 10^{-2} & 1,722 \cdot 10^{-7} & 3,860 \cdot 10^{-10} & \color{red}{2,507 \cdot 10^{-8}} \\ \hline V & 9,000 \cdot 10^{-6} & 9,950 \cdot 10^{-7} & 6,433 \cdot 10^{-5} & 5,790 \cdot 10^{-10} & 7,566 \cdot 10^{-11} \\ \hline \end{array}$       $\begin{array} {r|c|c|c|c|c|} \color{red}{\bf D} & \text{un} & \text{gatto} & \text{mangia} & \text{il} & \text{topo} \\ \hline A & 0 & 1 & 2& 3& 1\\ \hline N & 0 & 1 & 2& 3& \color{red}{1}\\ \hline V & 0 & 2 & 2&3 &1 \\ \hline \end{array}$  

e ripercorrendo a ritroso, colonna per colonna, gli indici degli stati nella tabella D a partire dall'indice indicato in rosso, otteniamo 

$s_5=2 \rightarrow S_{\text{topo}}=N \\ s_4=1 \rightarrow S_{\text{il}}=A \\ s_3=3 \rightarrow S_{\text{mangia}}=V \\ s_2=2 \rightarrow S_{\text{gatto}}=N \\ s_1=1 \rightarrow S_{\text{un}}=A \\$

che costituisce la sequenza di stati attribuiti alle frase con massima la probabilità secondo il modello di Markov presentato - ed è effettivamente la corretta analisi grammaticale della frase, nonostante presenza di due parole estranee al dizionario.