Il POS tagging con il modello HMM (Hidden Markov Model)

Il POS tagging con il modello HMM (Hidden Markov Model)

Immagina di avere una scatola piena di etichette colorate. Ogni colore rappresenta una parte diversa del discorso: per esempio, il blu per i nomi, il rosso per i verbi e il verde per gli aggettivi. Ora, immagina di avere una fila di parole, come se fossero dei trenini di legno senza colore. Il tuo compito è attaccare la giusta etichetta colorata su ciascun treno – cioè, su ogni parola – a seconda di quale parte del discorso appartiene.

Questa attività di etichettare le parole con le parti del discorso si chiama “POS tagging” (Part-Of-Speech Tagging), che significa “assegnazione delle parti del discorso”. Ogni parola in una frase ha un ruolo e il POS tagging è come un grande gioco dove dobbiamo indovinare il ruolo giusto per ogni parola.

Adesso, come facciamo a indovinare? Qui entra in gioco qualcosa chiamato un “Modello Nascosto di Markov” (Hidden Markov Model – HMM). il modello HMM non guarda direttamente il ruolo di una parola (perché è nascosto), ma guarda le “piste” che lascia – come le parole vicine e come queste si collegano in generale. Quindi, il modello usa queste informazioni per fare una buona ipotesi su quale etichetta colorata dovrebbe andare su ciascuna parola.

Gli HMM sono molto efficienti in questo compito perché hanno delle regole basate sulla statistica che dicono cose come: “Se la parola prima è ‘the’ (un articolo), allora la prossima parola è molto probabilmente un nome (colore blu)”, oppure “dopo un nome di solito viene un verbo (colore rosso)”. Così, usano queste regole per fare le loro migliori ipotesi.

Approfondimento

Le parti del discorso (Part of speech POS) forniscono informazioni essenziali sulle strutture delle frasi e sul significato. Sapere, per esempio, se una parola è un verbo ci dice molto riguardo alle parole vicine (i verbi richiedono nomi come soggetti e oggetti, aggettivi, nomi formati da verbi e strutture sintattiche di verbi composti).

Ogni parola ha il suo ruolo in una frase, ma senza comprendere questo ruolo, il significato può essere mal interpretato. il POS Tagging aiuta a distinguere tra parole che hanno più funzioni grammaticali (omografi) a seconda del contesto. Ad esempio, la parola “piano” può essere un sostantivo (“il piano della casa”) o un avverbio (“parla piano”). Sapendo quale parte del discorso la parola rappresenta in una data frase, un sistema NLP può comprendere meglio il significato della frase.

Inoltre, il POS Tagging è cruciale per il parsing sintattico, cioè l’analisi della struttura grammaticale di una frase, che consente ai sistemi di identificare relazioni tra le parole e di comprendere frasi anche complesse. Facilita anche il riconoscimento delle entità, che è il processo di identificazione di nomi di persone, organizzazioni, luoghi e altre entità specifiche. Questo è utile per estrarre informazioni da grandi volumi di testo e per costruire risposte informative in chatbot e assistenti virtuali.

Nel vasto universo del NLP, il POS Tagging è il primo passo per decriptare il codice complesso del nostro linguaggio.

Il POS Tagging consiste nell’assegnare etichette a ogni parola in un testo, che indicano la sua funzione grammaticale, come sostantivo, verbo, aggettivo, ecc.

Uno strumento che viene spesso impiegato in questa operazione è il modello Hidden Markov Model (HMM)

L’etichettatura con un Modello di Markov Nascosto (Hidden Markov Model, HMM) per l’analisi delle parti del discorso (Part-of-Speech Tagging, POS Tagging) è una tecnica classica nell’elaborazione del linguaggio naturale (NLP).

Gli HMM considerano le parole come frutto di uno specifico stato (parte del discorso) ed esaminano la probabilità che una parola derivi da un certo stato, tenendo conto della sequenza di stati. Gli stati sono le etichette POS, e le osservazioni sono le parole del testo.

Si tratta di un modello statistico che assume che il sistema da modellare sia un processo di Markov con parametri ignoti (nascosti). In un processo di Markov, si presume che il futuro sia indipendente dal passato, data la conoscenza dello stato presente. Gli HMM sono caratterizzati da:

  1. Stati nascosti: In POS Tagging, questi stati nascosti corrispondono alle parti del discorso (sostantivo, pronome, verbo, avverbio, etc.).
  2. Probabilità di transizione: La probabilità di transizione da uno stato (parte del discorso) al successivo (la probabilità che ad un verbo segua per esempio un sostantivo).
  3. Osservazioni: Le parole effettive nel testo (il, gatto, mangia, etc.).
  4. Probabilità di osservazione o di emissione: La probabilità che una data parola sia generata da una particolare parte del discorso (per esempio sapendo di avere a che fare con un sostantivo, la probabilità che si tratti della parola “gatto”)
  5. Probabilità iniziali: La probabilità iniziale di ciascuna parte del discorso all’inizio di una frase.

In simboli:

Gli HMM, quindi, modellano l’etichettatura POS come un problema di inferenza, dove si cerca la sequenza più probabile di etichette (stati nascosti) che potrebbe aver generato la sequenza osservata di parole. Questo è tipicamente risolto utilizzando l’algoritmo di Viterbi, un algoritmo dinamico che effettua tale inferenza in modo efficiente.

Le probabilità di transizione e di emissione vengono rappresentate mediante delle matrici

L’etichettatura con un Modello di Markov Nascosto (HMM) implica la costruzione di un modello probabilistico che tiene conto delle transizioni tra stati (che rappresentano le parti del discorso) e le osservazioni (che sono le parole stesse). Ecco un esempio semplificato per mostrarti come funziona l’etichettatura HMM.

Esempio

Immagina di avere una semplice frase: “The cat sleeps.”

Il nostro HMM potrebbe avere un set limitato di stati che rappresentano le parti del discorso, ad esempio:

N (nome)
V (verbo)
A (articolo)

Ogni stato ha probabilità di transizione associate che indicano quanto è probabile passare da uno stato all’altro. Per esempio:

A segue A: 0.1
A segue N: 0.8
A segue V: 0.1
N segue A: 0.1
N segue N: 0.1
N segue V: 0.8
V segue A: 0.4
V segue N: 0.1
V segue V: 0.5

Inoltre, avremmo probabilità di emissione che descrivono quanto è probabile che uno stato specifico produca una certa parola. Ad esempio:

P(“the”|A): 0.9
P(“cat”|N): 0.7
P(“sleeps”|V): 0.6

Le probabilità di inizio ci dicono quale stato è più probabile all’inizio di una frase:

π(A) = 0.6
π(N) = 0.2
π(V) = 0.2

Quando cerchiamo di etichettare la frase “The cat sleeps”, l’HMM calcolerà la sequenza di stati (parti del discorso) più probabile per questa sequenza di parole. Utilizza le probabilità di inizio, le probabilità di transizione e le probabilità di emissione per fare previsioni sulla sequenza di etichette:

Inizia con “The”, che è molto probabilmente un ARTICOLO (A) dato che P(“the”|A) è alto.
Dato che siamo in A, il successivo stato più probabile è N (per “cat”), perché A -> N ha una probabilità di transizione alta (0.8).

Infine, dato che siamo in N e abbiamo “sleeps” come prossima parola, passeremmo a V con una probabilità di transizione alta (N -> V è 0.8) e una ragionevole probabilità di emissione (P(“sleeps”|V) = 0.6).

Quindi, l’etichettatura finale per la frase secondo l’HMM potrebbe essere:

“The” – A
“cat” – N
“sleeps” – V

L’algoritmo di Viterbi

L’algoritmo di Viterbi è tipicamente utilizzato in un HMM per calcolare il percorso più probabile attraverso questi stati, determinando l’etichettatura più probabile per l’intera frase.

Le probabilità di emissione, nel contesto degli HMM, sono fondamentali perché collegano gli stati nascosti (nel caso dell’etichettatura delle parti del discorso, sarebbero le parti del discorso come sostantivi, verbi, aggettivi, ecc.) alle osservazioni effettive (le parole nella frase). Queste probabilità misurano quanto è probabile vedere un’osservazione specifica (una parola) quando si è in un particolare stato (parte del discorso).

Nel processo di etichettatura con un HMM, ogni volta che si passa a un nuovo stato, le probabilità di emissione vengono utilizzate per valutare quale parola è la più probabile per quel particolare stato. Ad esempio, se lo stato attuale è un sostantivo (N), la probabilità di emissione determinerà quanto è probabile che la parola “gatto” sia osservata se siamo in quello stato.

In pratica, se stai cercando di decodificare la sequenza di stati più probabile data una sequenza di parole, userai sia le probabilità di transizione (per passare da uno stato all’altro) sia le probabilità di emissione (per scegliere le parole che corrispondono a quegli stati). L’algoritmo di Viterbi, utilizzato negli HMM per il processo di decodifica, calcola il percorso più probabile combinando queste due serie di probabilità.

Quindi, le probabilità di emissione sono cruciali per collegare i dati osservati (le parole che leggiamo o ascoltiamo) con il modello probabilistico sottostante (gli stati nascosti che rappresentano le parti del discorso) in un HMM.

Nell’ambito di un Modello di Markov Nascosto (HMM), le probabilità di transizione e le probabilità di emissione vengono combinate per calcolare la probabilità complessiva di una particolare sequenza di etichette date le parole osservate. Il processo che combina queste probabilità per decodificare la sequenza più probabile di stati (o etichette) è noto come decodifica, e l’algoritmo di Viterbi è spesso utilizzato per questo scopo.

Ecco come funziona il processo di combinazione:

Si parte con la probabilità iniziale di uno stato, detto anche probabilità di partenza (πi per lo stato i).

Per ogni passaggio da uno stato all’altro, si utilizza la probabilità di transizione aij che indica la probabilità di passare dallo stato i allo stato j.

Per ogni parola osservata, si consulta la probabilità di emissione (bi(ot)) che rappresenta la probabilità che lo stato i generi l’osservazione ot (nel caso delle parole, ot sarebbe la parola specifica osservata al tempo t).

Per ogni passo temporale t nella sequenza di osservazioni, si calcola per ogni possibile stato la probabilità che lo stato sia attivo al tempo t e che generi l’osservazione corrispondente. Questo si ottiene moltiplicando la probabilità di transizione per la probabilità di emissione e per la probabilità del migliore stato precedente che porta a questo stato. Formalmente, se si vuole calcolare questa probabilità per lo stato jj al tempo tt, la formula è:

Pt(j)=max⁡i(Pt−1(i)⋅aij⋅bj(ot))

dove max⁡i indica che si prende il massimo su tutti i possibili stati precedenti i.

Questo processo viene ripetuto per ogni parola nella sequenza.

Alla fine della frase, il percorso più probabile può essere tracciato indietro dallo stato finale al primo stato, utilizzando informazioni di backtracking che vengono conservate durante l’esecuzione dell’algoritmo di Viterbi.

In sostanza, le probabilità di transizione ci dicono come ci si sposta tra i tag, mentre le probabilità di emissione ci dicono come i tag si correlano alle parole effettive. Questi due insiemi di probabilità lavorano insieme per permetterci di decodificare le sequenze di parole in sequenze di etichette delle parti del discorso in modo che ogni parola riceva il tag più probabile dato il contesto fornito dalle parole circostanti.

Esempio semplice

Immaginiamo di avere una frase molto semplice come “She eats” e vogliamo trovare la sequenza più probabile delle parti del discorso (POS tagging) usando un HMM. Le uniche parti del discorso che considereremo saranno “Pronome” (PR) e “Verbo” (VB).

Dobbiamo definire le seguenti probabilità:

Probabilità iniziali di stato (π):
PR: 0.7
VB: 0.3

Probabilità di transizione (a):
PR -> PR: 0.1
PR -> VB: 0.9
VB -> PR: 0.4
VB -> VB: 0.6

Probabilità di osservazione/emissione (b):
“She” come PR: 0.9
“She” come VB: 0.1 (improbabile, ma non impossibile a causa di errori di battitura o giochi di parole)
“eats” come PR: 0.1
“eats” come VB: 0.9

Ora utilizziamo l’algoritmo di Viterbi:

Il valore Viterbi più alto per la parola “eats” è 0.5082 per il tag VB, che proviene da PR. Quindi, il percorso più probabile fino ad ora è PR seguito da VB.

Partendo dalla fine, scegliamo il tag con la probabilità più alta all’ultimo passo, che è VB per “eats”. Seguiamo i puntatori indietro per trovare da quale stato siamo arrivati a VB, che è PR per “She”.

La sequenza più probabile di tag è quindi “PR VB” per la frase “She eats”.

Esempio con più di due parole

immaginiamo di avere la seguente frase: “The cat sits on the mat” e vogliamo trovare la sequenza di parti del discorso (POS) più probabile per questa frase. Per questo esempio, considereremo tre tag possibili: Aggettivo (ADJ), Nome (N), e Verbo (V). Ecco le probabilità che assegniamo:

Probabilità iniziali di stato (π):

ADJ: 0.4
N: 0.4
V: 0.2

Probabilità di transizione (a):

ADJ -> ADJ: 0.1

ADJ -> N: 0.8,

ADJ -> V: 0.1

N -> ADJ: 0.2

N -> N: 0.3

N -> V: 0.5

V -> ADJ: 0.5

V -> N: 0.4

V -> V: 0.1

Per semplificare, diciamo che ogni parola ha la seguente probabilità di emissione (b) di essere osservata per ogni tag (normalmente, si avrebbe una probabilità specifica per ogni parola per ogni tag):

“The” come ADJ: 0.6,

“The” come N: 0.2,

“The” come V: 0.2

“cat/sits/mat” come ADJ: 0.2,

“cat/sits/mat” come N: 0.7,

“cat/sits/mat” come V: 0.1

“on” come ADJ: 0.3,

“on” come N: 0.3,

“on” come V: 0.4

Creiamo una griglia con le parole in colonna e i tag in riga, e compiliamo con le probabilità calcolate in base all’algoritmo di Viterbi. Assumendo di aver già fatto i calcoli, potremmo avere una griglia che assomiglia a qualcosa del genere:

I numeri all’interno della griglia rappresentano le probabilità calcolate a ogni passo per ogni stato. Queste probabilità si basano sull’esempio ipotetico e semplice delle probabilità fornite sopra e non riflettono i calcoli esatti dell’algoritmo di Viterbi.

L’algoritmo di Viterbi, nel corso dell’analisi di una frase, esegue questi calcoli a ogni passo temporale (ogni parola della frase) e per ogni stato (tag). Questo esempio è solo una rappresentazione molto semplificata di come si possa disporre una griglia di Viterbi. In un caso reale, ogni cella della griglia conterrà il massimo valore calcolato per il passo precedente, moltiplicato per la probabilità di transizione e la probabilità di emissione, e si tiene traccia del percorso che ha portato a quel valore massimo. Alla fine, il backtracking attraverso i massimi valori di ogni colonna dalla fine all’inizio fornisce il percorso più probabile attraverso gli stati.