classificazione e segmentazione di testi: modelli generativi e condizionali a confronto
DESCRIPTION
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 - PowerPoint PPT PresentationTRANSCRIPT
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?
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.
itransizionNNstati 2
First Order Markov Model
Quando non basta un processo di Markov?
Matrice delle Matrice delle transizionitransizioni
Vettore delle Vettore delle probabilità inizialiprobabilità iniziali
E’ necessario estendere il modello per rappresentare processi in cui le osservazioni sono probabilisticamente legate ad un sottostante processo di Markov.
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).
Njiiqjqpa ttji ,1,|1
N
jji
ji
Nia
Njia
11,1
,1,0
L’insieme delle probabilità di emissione dei simboli, cioè distribuzione di probabilità in ogni stato.
la distribuzione iniziale di stato.
Niiqpi 1,1
MkNjjqvopkb tktj 1,1,|
M
kj
j
Njkb
MkNjkb
11,1
1,1,0
Definizione di HMM (2)
HMM: esempio
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.
),,( BA
Assunzioni… Assunzione di Markov
La scelta dello stato successivo dipende solo dallo stato corrente.
Assunzione di stazionarietà
Le probabilità di transizione sono indipendenti dal tempo in cui avviene la transizione.
Assunzione di independenza dell’output
L’osservazione corrente è statisticamente indipendente dalle precedenti
iqjqpa ttji |1
),|(,.....,,|
1,21
T
tttT qOpqqqOp
2111 ,),|(|2211
ttiqjqpiqjqp tttt
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 ForwardAlgoritmo Forward
= Pr( osservazione | stato nascosto è j ) x Pr(tutti I cammini verso j al tempo t) jt
Le probabilità parziali per l’osservazione finale tengono conto della probabilità di raggiungere questi stati tramite tutti i possibili path.
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)
INDUZIONE
(si assume ricorsivamente di conoscere il primo termine del prodotto)
TERMINAZIONE
(la somma di tutte le probabilità parziali dà la probabilità delle osservazioni, dato il modello)
Niobi ii 1),()( 11
NjTtobaij tjN
ijitt
111)()()( 11
1
N
iT iOP
1)()|(
ComplessitàIl calcolo coinvolge principalmente i termini:
NjjcalcolaTtperNjjcalcolatper
t
1,)(...21,)(1 1
)( jt
)( 2TNO
Ad ogni t ci sono solo N stati da considerare, quindi ogni calcolo coinvolge solo N valori precedenti, indipendentemente dalla lunghezza della sequenza.
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 ViterbiAlgoritmo 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.
Ognuno di questi path migliori parziali ha associato una probabilità, che è la probabilità del più probabile path verso quello stato.
È la massima probabilità di tutte le sequenze che terminano nello stato i al tempo t, ed il migliore percorso parziale è la sequenza a cui corrisponde questa probabilità.
),( ti
Algoritmo Viterbi (1) INIZIALIZZAZIONE (t=1)
INDUZIONE
Si tratta di cercare il path che termina in AX, BX o CX che ha la massima probabilità (sotto l’assunzione di Markov). )|.Pr()|Pr(
)1Pr(max)Pr( ,,
XttempoalobsiX
ttempoalittempoalX CBAi
Niobi ii 1),()( 11
)()((max)( 1 tijitjt obaji
In che stato dev’essersi trovato il sistema al tempo t-1 se è arrivato ottimamente nello
stato i al tempo t?
TERMINAZIONE (qual è lo stato più probabile al tempo t=T)
BACKTRAKING
Algoritmo Viterbi (2)
))((maxarg)( 1 jitj
t aji
))(max(arg ii Tt
)( 11 ttt ii
Considerazioni
L’algoritmo di Viterbi “guarda” l’intera sequenza prima di decidere il più probabile stato finale (backtraking).
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.
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
1tempoalistatonellovoltedinumeroattesafrequenzai
emessisimbolitotalenumeroksimbolodelemissionidinumerob jk
idaitransiziontotalenumerojiitransiziondinumeroaij
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,..).
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).
dovremmo enumerare tutte le possibili sequenze di osservazioni a meno di non fare ipotesi molto forti di indipendenza sulle osservazioni!!
S={S1 ,S2,..}
X={X1 ,X2,..}
)(),(maxarg*
xpsxps s
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 (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à Approccio ML
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.
idaitransiziontotalenumerojiitransiziondinumeroaij
emessisimbolitotalenumeroksimbolodelemissionidinumerob jk
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
Nell’identificare la migliore sequenza di stati per una data sequenza di osservazioni possiamo usare direttamente la probabilità condizionata.
modelli condizionali, che definiscono una probabilità condizionata della sequenza di label data una sequenza di osservazioni (o equivalente mente degli stati date le osservazioni).
Maximum Entropy Markov Model(1) Definiscono un unico insieme di cardinalità |S| di distribuzioni:
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.
),|'()|'( xSSPxsPs
Maximum Entropy Markov Model(2) Il modello della funzione di transizione/osservazione è log-lineare:
Le feature functions fanno uso di binary features che esprimono caratteristiche delle osservazioni dei dati di training.
)),'(exp(),(
1)|'( xsfxsZ
xsP kks
altrimenti
ssedxbsexsF bs
0
')(1),'(,
altrimenti
theneosservaziosexb
0
""1)(
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
0 1
2
3
4
5
Il problema
è
è
questo
quello
[a]
[b]
[a]
[a]
[c]
[d]
“Il problema è questo”
P(4|2,questo)=P(5|3,quello)=1
N.B: HMM non soffrono di questo problema.
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 random su cui è definita.
Lafferty definisce la probabilità di una sequenza di label y data una sequenza di osservazioni x come il prodotto normalizzato di funzioni potenziali del tipo:
)),(exp()(
1),|( xyfxZ
xyP jj
),(
),,(),(
,,1 ixiij
ikyytixys
xyf
Xi−2 Xi−1 Xi
Oi−2 Oi−1 Oi
f: wordi−1 = Grace & posi = NNP
f: posi−1 = NNP & posi = NNP & wordi = Road
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.
Una configurazione globale che ha maggiore probabilità soddisfa più vincoli di una configurazione con minore probabilità.
altrimenti
obsneosservaziosexb
0
""1)(
altrimenti
byayseixbixyyt
ii
iij0
),(),(
1
,,1
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 i.i.d, il prodotto
su tutte le sequenze di training, come funzione di è noto come likelihood:
Il training ML sceglie i valori dei parametri t.c il logaritmo del likelihood sia massimizzato.
)},{|}({ )()( kk xyp
)),(exp()(
1),|( xyfxZ
xyP jj
)},{( )()( kk yx
CRF
k
kjxYpXYp xYFEXYFE k )],([)],([)( )(
),|(),(~ )(
Si usa una tecnica iterativa.
k j
kkjjk xyF
xZ]),(
)(1[log)( )()()(
Il log-likelihood per un CRF è definito come:
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.
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
INFO: Labels: O autore titolo journal volume anno
INFO: O->O(O) O,OINFO: O->autore(autore) O,autoreINFO: O->titolo(titolo) O,titoloINFO: O->journal(journal) O,journalINFO: O->volume(volume) O,volumeINFO: O->anno(anno) O,annoState #0 "O"initialCost=0.0, finalCost=0.0#destinations=6-> O-> autore-> titolo-> journal-> volume-> anno
stato sorgentestato destinazionenome labelnome dei pesi
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ù probabileVengono combinati con il vettore delle feature.