Classificazione e segmentazione
di testi: modelli generativi e
condizionali a confronto
Sommario



Makov Model
Hidden Markov Model
 Evaluation Problem
 Decoding Problem
 Learning Problem
Classificazione e Segmentazione di testi con HMM




DATAMOLD
Limiti dei Modelli Generativi
Modelli Condizionali
Conditional Random Field

MALLET
Markov Model


Qualsiasi ambito in cui occorre una sequenza di eventi può
produrre pattern interessanti …
Come modellare il processo che potrebbe averli generati?
Nstati  N 2transizioni


Un processo di Markov è un processo che si sposta da
uno stato all’altro in base ai precedenti n stati.
Non equivale ad un processo deterministico, dato che la
scelta è fatta in modo probabilistico.
First Order Markov Model
Matrice delle
transizioni
Vettore delle
probabilità iniziali
Quando non basta un processo di Markov?
E’ necessario estendere il modello per rappresentare processi in cui le
osservazioni sono probabilisticamente legate ad un sottostante processo di
Markov.
Hidden Markov Model
b11 b12
b13 b14
b 21
a12
a21
q1
q2
a13
a31
a23
a32
q3
b 31
b32
b 22
b 33
b 34
b 23
b 24
Definizione di HMM (1)

N, stati del modello.

M, numero di simboli distinti osservati.
Corrispondono all’output fisico del sistema.

L’insieme delle probabilità di transizione (distribuzione).
ai j  pqt 1  j | qt  i ,
1  i, j  N
ai j  0,

N
  ai j  1,
1 i  N
 j 1


1  i, j  N
Definizione di HMM (2)

L’insieme delle probabilità di emissione dei simboli, cioè distribuzione di
probabilità in ogni stato.
b j k   pot  vk | qt  j,
1  j  N ,1  k  M
b j k   0,
 M
  b j k   1,
1 j  N
k 1


la distribuzione iniziale di stato.
 i  pq1  i ,
1 i  N
1  j  N ,1  k  M
HMM: esempio
  ( A, B, )
Gli stati nascosti sono modellati come un processo di Markov del primo ordine.
Gli archi tra gli stati nascosti e quelli osservabili rappresentano la probabilità di
generare (ed osservare) un particolare stato visibile essendo in un certo stato
nascosto.
Assunzioni…

Assunzione di Markov
ai j  pqt 1  j | qt  i

La scelta dello stato successivo dipende solo dallo stato corrente.

Assunzione di stazionarietà

p qt
1
1
 j | qt  i
1
  p(qt
2
1
 j | qt  i ),
2
t1 , t 2
Le probabilità di transizione sono indipendenti dal tempo in cui avviene la transizione.

Assunzione di independenza dell’output

p O | q1 , q2 ,.....,qT , 

T
   p(Ot | qt ,  )
t 1
L’osservazione corrente è statisticamente indipendente dalle precedenti
Evaluation Problem

Dato un HMM completamente definito, con probabilità di transizione ed
emissione note, si vuole determinare la probabilità che una certa sequenza di
stati sia generata dal modello.

Algoritmo Forward
Le probabilità parziali per l’osservazione finale tengono conto della probabilità di raggiungere
questi stati tramite tutti i possibili path.
 t  j  = Pr( osservazione | stato nascosto è j ) x Pr(tutti I cammini verso j al tempo t)
La somma di queste probabilità parziali è la somma di tutti i possibili paths attraverso il reticolo,
quindi è la probabilità di osservare la sequenza dato il modello.
Algoritmo Forward

INIZIALIZZAZIONE (t=1)
1 (i )   i bi (o1 ),

1 i  N
INDUZIONE
N
i 1


 t 1 ( j )     t (i )ai j b j (ot 1 )
1 t  T 1
1 j  N
(si assume ricorsivamente di conoscere il primo termine del prodotto)

TERMINAZIONE
N
P (O |  )    T (i )
i 1
(la somma di tutte le probabilità parziali dà la probabilità delle osservazioni,
dato il modello)
Complessità
Il calcolo coinvolge principalmente i termini:
per
per
 t ( j)
1 ( j ) , 1  j  N
t  2...T calcola  t ( j ) , 1  j  N
t 1
calcola
Ad ogni t ci sono solo N stati da considerare, quindi ogni calcolo
coinvolge solo N valori precedenti, indipendentemente dalla
lunghezza della sequenza.
O( N 2T )
Decoding Problem




Dato un HMM e un set di osservazioni, si vuole determinare la più probabile
sequenza di stati nascosti per le osservazioni, cioè che potrebbe aver generato
quelle osservazioni.
Applicazioni: segmentation, NLP task.
Algoritmo di Viterbi
Si definisce la probabilità parziale, cioè la probabilità di raggiungere un particolare
stato intermedio nel reticolo. Rappresenta la probabilità del più probabile path verso
uno stato al tempo t.
massima
di tutte
sequenze
che
terminanoche
nello
stato
i al tempo
 (Ognuno
i, t ) Èdi laquesti
path probabilità
migliori parziali
ha le
associato
una
probabilità,
è la
probabilità
delt,
ed il migliore
percorso
più probabile
path verso
quello parziale
stato. è la sequenza a cui corrisponde questa probabilità.
Algoritmo Viterbi (1)

INIZIALIZZAZIONE (t=1)
1 (i )   i bi (o1 ),

1 i  N
INDUZIONE
 t (i )  max j ( t 1( j )a jibi (ot )
X dialcercare
tempo
 max
i oalCX tempo
 1)  probabilità
i  A,in
B ,AX,
C Pr(
SiPr(
tratta
il patht )che
termina
BX
che ha latmassima
(sotto l’assunzione di Markov).
Pr( X | i )  Pr(obs. al tempo t | X )
Algoritmo Viterbi (2)

In che stato dev’essersi trovato il sistema al tempo t-1 se è arrivato ottimamente nello
stato i al tempo t?
t (i)  arg max ( t 1 ( j )a ji )
j

TERMINAZIONE (qual è lo stato più probabile al tempo t=T)
it  arg max(  T (i ))

BACKTRAKING
it  t 1 (it 1 )
Considerazioni
Ipotesi di invarianza temporale delle probabilità→ riduzione della
complessità del problema (evitando la necessità di esaminare tutti i
possibili percorsi nel reticolo).
La Σ presente nell’algoritmo forward è rimpiazzata dall’operatore di
max perché si cerca il più probabile cammino per la posizione
corrente, non la probabilità totale.
L’algoritmo di Viterbi “guarda” l’intera sequenza prima di decidere il
più probabile stato finale (backtraking).
Gode della proprietà di fornire la migliore interpretazione rispetto
all’intero contesto delle ossservazioni.
LEARNING PROBLEM

Conoscendo solo il “guscio” di un HMM ( il numero di stati visibili e
nascosti, ma non le probabilità di transizione ed emissione), e date
delle osservazioni di training, si vogliono determinare i parametri del
modello.

Generare un HMM da una sequenza di osservazioni (training set).

La quantità da massimizzare durante il processo di learning, dipende dal
tipo di applicazione. Ci sono diversi criteri di ottimizzazione per il learning,
ad esempio Maximum Likelihood (ML).
LEARNING PROBLEM


Inizialmente, l’algoritmo indovina i valori dei parametri, e man mano li
ridefinisce cercando di ridurre gli errori.
Il nome deriva dal fatto che, per ogni stato in un reticolo di esecuzione,
calcola la probabilità `forward' di arrivare a questo stato (data la corrente
approssimazione del modello) e la probabilità `backward' di generare lo stato
finale del modello, rispetto alla approssimazione corrente.
LEARNING PROBLEM
 i  frequenza attesa  numero
di volte nello stato i al tempo 1
b jk 
a ij 
numero di emissioni del simbolo k
numero totale simboli emessi
numero di transizion i i  j
numero totale transizion i da i
Iterativamente, si usa la stima  per migliorare la probabilità di
osservare la sequenza rispetto al nuovo modello calcolato.
Il risultato finale è la stima di massima verosimiglianza del HMM.
Labelling con HMM

HMM si possono usare per classificazione e segmentazione di testi: (identificare la più
probabile sequenza di label per le parole in una frase,..).
S={S1 ,S2,..}
X={X1 ,X2,..}

Scegiere la sequenza che massimizza la probabilità condizionata di una sequenza di
label data la sequenza di osservazioni p(y|x).

Poiché definiscono una distribuzione di probabilità congiunta sugli stati e le
osservazioni, la più appropriata sequenza di label per ogni sequenza di osservazioni è
ottenuta trovando gli stati che massimizzano p(s|x).
s*  arg max s

p( x, s)
p ( x)
dovremmo enumerare tutte le possibili sequenze di osservazioni a meno di non fare
ipotesi molto forti di indipendenza sulle osservazioni!!
Segmentazione di testi: DATAMOLD

HMM :per la segmentazione automatica di testo in record
strutturati (indirizzi postali, records bibliografici, elenco
telefonico..).

Sistemi rule-based: problema della estrazione di field a causa
della grande varianza nella struttura dei record.

DATAMOLDO: tool che usa la tecnica statistica degli HMM.
DATAMOLD (1)
DATAMOLD (2)
Training:

Scegliere la struttura del HMM (nodi, dizionario,..)

Struttura naive: uno stato per ogni elemento.
Ignora le relazioni sequenziali nello stesso elemento!!

Struttura innestata: esterna + interna.

Apprendere le probabilità
k
numerodidiemissioni
transiziondel
i i simbolo
j

Approccio ML abijjk numero
numero
totale
simbolii emessi
numero
totale
transizion
da i
Testing: data una sequenza, associare ad ogni simbolo un elemento.
 Algoritmo di Viterbi (modificato) :per incorporare informazioni di
dipendenza, rispetto al data base di relazioni semantiche.
Considerazioni


HMM e modelli generativi non sono i più appropriati per labelling.
Definendo una distribuzione di probabilità congiunta su osservazioni e
labels dovrebbero enumerare tutte le possibili sequenze a meno di
ipotesi di indipendenza sulle osservazioni.

ESIGENZE: inferenza trattabile & non ipotesi restrittive di indipendenza.

SOLUZIONE
modelli condizionali, che definiscono una
probabilità condizionata della sequenza di label data una sequenza di
osservazioni (o equivalente mente degli stati date le osservazioni).

Nell’identificare la migliore sequenza di stati per una data sequenza di
osservazioni possiamo usare direttamente la probabilità condizionata.
Maximum Entropy Markov Model(1)

Definiscono un unico insieme di cardinalità |S| di distribuzioni:
Ps ( s'| x)  P( S '| S , x)


E’ una funzione specifica per un dato stato, quindi la scelta di St+1
dipende da St.
La sequenza di osservazioni è condizionata piuttosto che generata.
Trattare le osservazioni come eventi condizionati significa che le
probabilità di ogni transizione possono dipendere da feature non
indipendenti e interagenti della sequenza di osservazioni.
Maximum Entropy Markov Model(2)

Il modello della funzione di transizione/osservazione è log-lineare:
1
Ps ( s'| x) 
exp( k f k ( s' , x))
Z ( s, x )

Le feature functions fanno uso di binary features che esprimono
caratteristiche delle osservazioni dei dati di training.
s  s'
1 se b( x) ed
1 se osservazio ne "the"


F s,b  ( s' , x)  
b( x )  
0
0
altrimenti
altrimenti


Lebel bias problem

MEMM usano un insieme di distribuzioni di probabilità definite per
ogni stato, apprese separatamente. Ogni distribuzione definisce la
probabilità condizionata del prossimo stato dato quello corrente ed il
successivo elemento osservato.
Necessità di un fattore di normalizzazione per ogni stato.
Le osservazioni influenzano la scelta del prossimo stato ma non la
probabilità con cui verrà scelto.

Per le transizioni con un solo arco uscente, l’osservazione potrebbe
del tutto essere ignorata.
Label Bias Problem: esempio
“Il problema è questo”
questo
[a]
2
4
[a]
[c]
è
0
1
Il problema
[b]
è
3
P(4|2,questo)=P(5|3,quello)=1

quello
[a]
N.B: HMM non soffrono di questo problema.
5
[d]
Conditional Random Field


Sono un modello condizionale che consente di rilassare l’ipotesi di
indipendenza (hmm) ed evitare il label bias problem (memm).
Specificano una singola distribuzione di probabilità sull’intera sequenza di
label, data la sequenza di osservazioni, piuttosto che definire una
distribuzione per stato.
 per applicazioni in cui la sequenza di label può dipendere da feature (delle


osservazioni) interagenti.
La natura esponenziale della distribuzione consente alle feature di diversi stati
di essere controbilanciate, cioè alcuni stati possono essere più importanti di
altri.
Grafo non orientato globalmente condizionato su X.
CRF:funzioni potenziali



E’ possibile fattorizzare la disrtribuzione congiunta su Y (corrispondenti agli
stati S) in un prodotto normalizzato di funzioni potenziali strettamente positive
a valori reali, ognuna operante su un sottoinsieme delle variabili random
corrispondenti ai vertici del grafo, i quali formano una cricca massimale.
Non ha una diretta interpretazione probabilistica, ma rappresenta vincoli sulla
configurazione
delle variabili
Xi−2
Xi−1
Xi random su cui è definita.
f: wordi−1 = Grace & posi = NNP
posi−1 = NNP
posi y= data
NNP &
word
Lafferty definisce la probabilità di unaf: sequenza
di &label
una
sequenza
i = Road
diO
osservazioni
prodotto normalizzato di funzioni potenziali del tipo:
O x come ilO
i−2
i−1
i
1
P ( y | x,  ) 
exp(  j f j ( y, x))
Z ( x)
 s k ( y i , x, i )
f ( y, x)  
t j ( yi 1 , yi, x, i )
CRF:funzioni potenziali

Per definire le feature fanction costruiamo delle feature real-valued delle
osservazioni per esprimere caratteristche sulla distribuzione empirica dei
dati di training che possiamo usare per modellare la distribuzione.
1 se osservazio ne "obs"

b( x )  
0
altrimenti

b( x, i ) se

t j ( yi 1, yi, x, i )  
 0


yi 1  a
yi  b
altrimenti
Una configurazione globale che ha maggiore probabilità soddisfa più vincoli
di una configurazione con minore probabilità.
CRF

L’informazione dei dati di training è incapsulata nell’insieme di feature
function.

Per stimare la distribuzione potenziale di un set di dati di training si sfrutta il
principio di massima entropia.
L’entropia di una distribuzione è la misura dell’incertezza.

Assumendo l’insieme di TD {( x

P ( y | x,  ) 
(k )
, y (k ) )}i.i.d, il prodotto
1
exp(  j f j ( y, x))
Z ( x)
su tutte le sequenze di training, come funzione di

è noto come likelihood:
p({ y (k ) } | {x (k ) },  )

Il training ML sceglie i valori dei parametri t.c il logaritmo del likelihood sia
massimizzato.
CRF
Il
log-likelihood per un CRF è definito come:
( )   [log
k
1
Z ( x (k ) )
   j F j ( y ( k ) , x ( k ) )]
j
( )
 E ~p (Y , X ) [ F (Y , X )]   E p (Y | x , ) [ F j (Y , x( k ) )]

k
(k )
Uguagliando
a zero si ottiene il vincolo del modello di massima entropia:
Il valore atteso di ogni feature rispetto al modello è uguale al valore atteso sulla
distribuzione empirica dei dati di training.
Si
usa una tecnica iterativa.
Considerazioni

Rispetto agli HMM il modello definito dai CRF è più espressivo,
consentendo arbitrarie ipotesi di indipendenza sulle osservazioni.

Condivide le proprietà di convessità generali dei modelli di massima
entropia.
MALLET



Libreria di classi Java che offre supporto alle applicazioni di NLP,
classificazione, clustering, estrazione di informazione, etc..
Abbiamo utilizzato l’implementazione fornita sui CRF, sfruttando il modello per
la segmentazione di records bibliografici.
FASE INIZIALE



ETICHETTE: autore, titolo, journal, volume, anno.
FEATURE: CAPITALIZED, LONGCAPITALIZED, MIXEDCAPS,
LONGMIXEDCAPS, ALLCAPS, ALLDIGIT, FOURDIGIT, NUMERIC,
ALFANUMERIC.
INPUT: dati etichettati con le appropriate label e feature
TRAINING & TEST (1)

TRAINING

INPUT (file) → SimpleTagger:
crea un SimpleTaggerSentence2FeatureVectorSequence:
estrae DataAlphabet e LabelAlfabet, crea FeatureVectorSequence e
LabelSequence → costruisce una InstanceList sui dati di training e
su questa invoca train: apprende i pesi (costi) per i nodi applicando
l’algoritmo forwardbackward: crea la struttura del lattice → restituisce
un CRF.

OUTPUT: crf (file)
TRAINING & TEST (2)

TEST

INPUT (file): esempi di test, con feature → SimpleTagger →
crea InstanceList sui dati di testing→ test → apply( crf, dati di
test): applica viterbiPath(dati di test): restituisce la sequenza di
output.

OUTPUT: risultato
Mallet:INFO
stato
stato
nome
sorgente
destinazione
label
nome
dei pesi
 INFO: Labels: O autore titolo journal volume anno
INFO: O->O(O) O,O
INFO: O->autore(autore) O,autore
INFO: O->titolo(titolo) O,titolo
INFO: O->journal(journal) O,journal
INFO: O->volume(volume) O,volume
INFO: O->anno(anno) O,anno
State #0 "O"
initialCost=0.0, finalCost=0.0
#destinations=6
-> O
-> autore
-> titolo
-> journal
-> volume
-> anno
Mallet:INFO
STATE NAME="O" (6 outgoing transitions)
initialCost = 0.0
finalCost = 0.0
-> O WEIGHTS NAME="O,O"
O -> O: <DEFAULT_FEATURE> = 0.0
-> autore WEIGHTS NAME="O,autore"
O -> autore: <DEFAULT_FEATURE> = 0.0
-> titolo WEIGHTS NAME="O,titolo"
O -> titolo: <DEFAULT_FEATURE> = 0.0
-> journal WEIGHTS NAME="O,journal"
O -> journal: <DEFAULT_FEATURE> = 0.0
-> volume WEIGHTS NAME="O,volume"
O -> volume: <DEFAULT_FEATURE> = 0.0
-> anno WEIGHTS NAME="O,anno"
O -> anno: <DEFAULT_FEATURE> = 0.0
I pesi, weight set, sono
inizializzati con un valore di
default e per tutte le feature
sono costruiti a partire dai
predicati di input.
Assumono valori da -Inf a
Inf. Valori più alti rendono il
path più probabile
Vengono combinati con il
vettore delle feature.