Diszkriminatív modellezés és strukturált modellalkotás

Diszkriminatív modellezés és strukturált modellalkotás

Modellalkotási szemléletek ●

●

Strukturált modellalkotás (pl. osztálycímkék szekvenciája, Bayes-hálók) vs. egyszerű modellek (pl. bináris/n-osztályos osztályozás) Generatív (együttes) (feltételes) modellek ●

vs.

diszkriminatív

Célváltozó és jellemzők közötti összefüggés eltérő kezelése

Generatív (NB)

Diszkriminatív (ME)

HMM címkéző ●

Állapotautomata + Markov-feltevés

●

P( X ,Y )= ∏ P( X∣Y ) P(Y )=∏ P (x i∣ y i ) P ( y i∣ y i−1 )

●

●

Ismerünk kell az egyes rejtett állapotok közötti átmenetvalószínűségeket (A) Valamint az egyes állapotokban tapasztalható emissziós/észlelési feltételes valószínűségeket (B) A)

B)

HMM-ekkel kapcsolatos kérdések ●

Megfigyeléssorozat valószínűsége ●

●

Megfigyeléssorozatot generáló legvalószínűbb rejtett állapotsorozat meghatározása ●

●

Forward algoritmus

Viterbi algoritmus

Tanítás: paraméterek kalibrálása ●

Expectation Maximization algoritmussal: maximum likelihood becslés hiányos megfigyelések esetén –

Forward-backward algoritmus (Baum-Welch algoritmus)

Forward és Viterbi algoritmusok ●

Rekurzív összefüggés ●

●

●

v t ( j)=max i v t −1 (i) a i , j b j (o t )

A teljes megfigyeléssorozat első t elemét legvalószínűbben generáló, j-re végződő rejtett állapotsorozat és az első t megfigyelés együttes valószínűsége Forward algoritmus teljesen hasonló, csak maximum helyett összegzünk

Egy t hosszú mondat(töredék) hányféle szófajsorozattal írható le, ha minden szó C szófaji kódba tartozhat?

Viterbi algoritmus din. programozással

●

Észrevétel: korábban számolt (t-edik megfigyelést megelőző) értékek újrahasznosíthatók

Az EM problémaköre és az EM filozófia ●

●

Egyszerű példa: binomiális eloszlás ●

F,F,F,I,F,I,I,F,I,I

●

F,F,F,I,F,I,I,F,I,?

p(F)=? p(F)=?

Mi tehető a hiányos megfigyelésekkel? ●

Tegyünk úgy, mintha meg sem történt volna?

●

Helyettesítsünk egy eloszlással (és iteráljunk)?

●

Tegyünk úgy, mintha a gyakrabban (ténylegesen is) megfigyelt megfigyeléstípusba tartozna?

EM valamivel formálisabban ● ●

Adottak megfigyeléseink

ML: Keressük a véletlen változóink feltételezett eloszlásának azon Θ paramétereit, ami a megfigyelés valószínűségét maximalizálja (IID) ●

● ●

●

x={x 1, x 2, x 3, ... , x n }

Likelihood: L(θ ; x)= p( x 1, x 2,. .. , x n∣θ)

Ha x adatunk teljes, könnyű dolgunk van Ellenben ha vannak rejtett z változóink is, akkor a hiányos log-likelihood-ot kell maximalizáljuk l(θ; x)=log ∑ p( x , z∣θ) z

Miért működik az EM? ●

Jensen-egyenlőtlenség ●

∑ αi=1 és konvex f függvényre – –

●

f ( ∑ αi x i )≤∑ αi f ( x i )

Miért igaz, hogy a számtani átlag ≥ a mértaninál? Miért igaz, hogy n elemű értékkészlettel rendelkező diszkrét változó maximális entrópiája log(n)?

Segédfüggvény a hiányos log-likelihoodhoz ●

l (θ ; x)=log p(x∣θ)=log ∑ z

● ●

p (x , z∣θ) p(x , z∣θ)=log ∑ q (z∣x) q( z∣x) z

p (x , z∣θ) l (θ ; x)≥∑ q( z∣x)log =L ( p(z∣x),θ) q( z∣x) z

A segédfüggvényünk egy alsó korlátot biztosít a teljes log-likelihoodra

Elvi algoritmus ●

●

E-lépés: Θ(t)-t fixnek tekintve maximalizáljuk L-t p(z|x,Θ)-ban p( x , z∣θ) L ( p( z∣x ,θ),θ)=∑ p( z∣x ,θ)log =log p (x∣θ)=l (θ ; x ) p( z∣x ,θ) z M-lépés: p(z|x)-et fixnek tekintve maximalizáljuk L-t Θ-ban

L ( p( z∣x), θ)=∑ p(z∣x)log p( x , z∣θ)−∑ p(z∣x)log p( z∣x) z

Maximalizálandó “teljes” likelihood ●

●

z

Θ-tól független

EM-algoritmus: inicializáljuk Θ-t, majd ismételjük az E,-és Mlépéseket p(F) becslésén túl hol használható még az EM? ●

Bayes hálók valószínűségeinek meghatározására, keverékeloszlásoknál (GMM), HMM tanításánál

Példa - Bayes háló valószínűségei Kezdeti tippjeink (Θ) P(H)=0,4 P(A|H)=0,55 P(A|¬H)=0,61 P(B|H)=0,43 P(B|¬H)=0,52

A B H # 0 0 ? 6 0 1 ? 1 1 0 ? 1 1 1 ? 4 A B 1. E

2. E ... 5. E

... 10. E

1. M

2. M

... 5. M

...

10. M

0 0 0,48 0,52

0,79

0,971

P(H)

0,42

0,42

0,46

0,52

0 1 0,39 0,39

0,31

0,183

P(A|H)

0,35

0,31

0,09

0,03

1 0 0,42 0,39

0,31

0,183

P(A|¬H) 0,46

0,50

0,69

0,83

1 1 0,33 0,28

0,05

0,01

P(B|H)

0,34

0,30

0,09

0,03

P(B|¬H) 0,47

0,50

0,69

0,83

P(H| D, Θ) = P(H|A=a, B=b, Θ)

Példa - Bayes háló valószínűségei Kezdeti tippjeink (Θ) P(H)=0,4 P(A|H)=0,55 P(A|¬H)=0,61 P(B|H)=0,43 P(B|¬H)=0,52

A B H # 0 0 ? 6 0 1 ? 1 1 0 ? 1 1 1 ? 4 A B 1. E

2. E ... 5. E

... 10. E

1. M

2. M

... 5. M

...

10. M

0 0 0,48 0,52

0,79

0,971

P(H)

0,42

0,42

0,46

0,52

0 1 0,39 0,39

0,31

0,183

P(A|H)

0,35

0,31

0,09

0,03

1 0 0,42 0,39

0,31

0,183

P(A|¬H) 0,46

0,50

0,69

0,83

1 1 0,33 0,28

0,05

0,01

P(B|H)

0,34

0,30

0,09

0,03

P(B|¬H) 0,47

0,50

0,69

0,83

P(H| D, Θ) = P(H|A=a, B=b, Θ)

L(Θ(0);x)=(0,4*0,45*0,57+0,6*0,54*0,43)6*(0,4*0,45*0,43+0,6*0,39*0,52)*(...)*(...)4=3,89*10-8 L(Θ(10);x)=(0,52*0,972+0,48*0,172)*(0,52*0,97*0,03+0,48*0,17*0,83)2*(...)4=1,34*10-6 l(Θ(0);x)=6*log(0,4*0,45*0,57+0,6*0,54*0,43)+log(...)+(...)+4*(...)=-7,409 l(Θ(10);x)=6*log(...)+2*log(...)+4*log(...)=-5,872

Vissza a HMM-ekhez (és tanításukhoz) ●

Backward számítások (t-edik időponttól számítva a megfigyelések hátralévő részének valószínűsége) βt (i)=

●

●

∑

j∈állapotok

βt +1 ( j)a i , j b j (ot +1 ) (a forward számítások mintájára)

Aij legyen az i-ből j állapotba történő átmenetek várható értékének és az i állapotból (bárhova tartó) továbbmenetel várható értékének hányadosa ξt legyen a t időpontban i állapotból j-be való átmenet valószínűsége adott megfigyelés és modell mellett P (q t =i ,q t +1= j ,O∣M ) ξt (i , j)=P(q t =i , q t +1= j∣O , M )= P (O∣M ) P( A , B∣C ) összefüggés miatt P( A∣B ,C )= P ( B∣C )

Várható értékek származtatása ●

P(qt =i , qt +1= j , O∣M )=α t (i)aij b j (ot +1)βt +1 ( j) N

●

P(O∣M )=αT ( N )=βT (1)=∑ α t ( j)βt ( j)

α a b (o t +1 )βt+ 1 ( j) ● ξ (i , j)= t ij j t αT ( N ) ●

j=1

γt(j) legyen a t időpontban j állapotban tartózkodás P (q t = j , O∣M ) α t ( j)βt ( j) valószínűsége γt ( j)=P (qt = j∣O , M )= P (O∣M ) = α ( N ) T

Forward-Backward algoritmus egészben

Problémák a HMM-el ●

Jellemzők feltételes függetlenségének a feltételezése ●

●

Együttes (joint) modellszemlélet ●

●

pl. az, hogy nagy kezdőbetűs-e egy szó nem független attól, hogy mi a megelőző szó A paraméterek a megfigyeléssorozat egészének valószínűségét maximalizálják (a megfigyelések során tapasztalt rejtett állapotokkal együtt)

Nekünk a legvalószínűbb állapotsorozat kellene adott megfigyeléssorozat mellett ●

Feltételes (conditional) modellezés: log-lineáris vagy maximum entrópia módszerek (Maximum Entrópia Markov Modellek - MEMM)

Evidenciák túlsúlyozása Európa Monaco Monaco

Tanító halmaz Monaco Monaco

Monaco

NB modell Osztály H

K

M

Monaco Hong Kong

P(A) = P(E) = P(M|A) = P(M|E) = P(H|A) = P(K|A) = P(H|E) = PK|E) =

Hong Kong Monaco

Ázsia Monaco

P(A,H,K,M) = P(E,H,K,M) = P(A|H,K,M) = P(E|H,K,M) =

Hong Kong

Hong Kong

Evidenciák túlsúlyozása Európa Monaco Monaco

Tanító halmaz Monaco Monaco

Monaco

NB modell Osztály H

K

M

Monaco Hong Kong

P(A) = P(E) = ½ P(M|A) = ¼ P(M|E) = ¾ P(H|A) = P(K|A) = 3/8 P(H|E) = PK|E) = 1/8

Hong Kong Monaco

Ázsia Monaco

Hong Kong

Hong Kong

P(A,H,K,M) = ½*9/64*¼ P(E,H,K,M) = ½*1/64*¾ P(A|H,K,M) = 9/(9+3)=¾ P(E|H,K,M) = 3/(9+3)=¼

Maximum Entrópia elv ●

Tanítópéldák (az egyszerűség kedvéért bináris) jellemzők által adottak, pl.

{

f i ( x , y )= 1 , ha x=Monaco∧ y=Európa 0, különben ●

Keressük azt a modellt, ami azon túl, hogy konzisztens a tanító példákkal, maximális feltételes entrópiájú is (a lehető legkevesebb feltételezéssel szeretnénk élni) ● ●

p∗( y∣x)=argmax p( y∣x)∈P H ( y∣x) H ( y∣x)=−

∑

( x , y)∈ X ×Y

p(x , y)log p( y∣x)

Maximum Entrópia elv szemléletesen ●

A modellünk entrópiája legyen maximális, de mindeközben tegyen eleget előzetes elvárásoknak 1. p(fej)+p(iras)=1 (tényleges eloszlást akarunk) 2. p(fej) = 0,3

MaxEnt szemlélet ●

●

●

Lehetséges állapotok = {NN, NNP, NNS, NNPS, VBZ, VBD} szófajok, melyeket rendre 3, 5, 11, 13, 3 ill. 1 alkalmakkal láttunk Ha csak az entrópai maximalizálása a célunk, a modellünk p(NN)=p(NNP)=...p(VBD)=1/6 lenne Jellemzők bevezetése (melyek empirikus megfigyeléseinek számával a modellünk által becsült várható megfigyelések száma meg kell egyezzen) ●

f1: főnév-e, f2: többesszámú főnév-e NN f1 f2

NNP NNS

NNPS VBZ

VBD


●

●


f1: főnév-e, f2: többesszámú főnév-e NN f1 f2

NNP NNS

8/36 8/36 8/36

NNPS VBZ

VBD

8/36

2/36

2/36


●

●


f1: főnév-e, f2: többesszámú főnév-e NN

NNP NNS

NNPS VBZ

VBD

f1

8/36 8/36 8/36

8/36

2/36

2/36

f2

4/36 4/36 12/36

12/36

2/36

2/36

Modell formuláció ●

Elávrásaink p*-gal szemben ● ●

●

Legyen eloszlás, vagyis

∑ p( y∣x)=1 y ∈Y

Konzisztencia: minden egyes jellemzőre a tanítópéldákon tapasztalt “tüzelésük” empirikus száma egyezzen meg a bekövetkezésük modell által előrejelzett várható értékével E (f i )= Ẽ (f i )∀ i

Korlátozott optimalizálási feladat Lagrange-fgv.-e m

̃ i ))+λ m+1 ( ∑ p( y∣x)−1) L( p , λ)=H ( y∣x)+ ∑ λ i ( E(f i )− E(f i=1

y∈Y

Jellemzők várható értékei ●

Jellemző empirikus v.é.-e T tanítóhalmaz esetén Ẽ (f i )=

∑

( x , y )∈X ×Y

1 p̃ (x , y) f i (x , y)= f i ( x , y) ∑ ∣T∣ (x , y)∈T


Jellemző empirikus v.é.-e T tanítóhalmaz esetén

∑

Ẽ (f i )=

( x , y )∈X ×Y


Jellemző modell által predikált v.é.-e 1 E (f )= ∑ p( x , y) f ( x , y)≈ ∑ p̃ ( x) p( y∣x)f (x , y)= ∑ ∑ p ( y∣x) f (x , y) ∣T∣ ●

i

i

(x , y)∈X × Y

●

i

( x , y )∈ X ×Y

x ∈T y∈Y

i

Az együttes eloszlást az összes lehetséges jellemző-osztálycímke kombinációra nehéz lenne számítani, ezért közelítjük azt


Jellemző empirikus v.é.-e T tanítóhalmaz esetén

∑

Ẽ (f i )=

( x , y )∈X ×Y


Jellemző modell által predikált v.é.-e 1 E (f )= ∑ p( x , y) f ( x , y)≈ ∑ p̃ ( x) p( y∣x)f (x , y)= ∑ ∑ p ( y∣x) f (x , y) ∣T∣ ●

i

i

i

(x , y)∈X × Y

●

( x , y )∈ X ×Y

x ∈T y∈Y

i

Az együttes eloszlást az összes lehetséges jellemző-osztálycímke kombinációra nehéz lenne számítani, ezért közelítjük azt –

Hasonló trükkel számoljuk a feltételes entrópiát is

H ( y∣x)≈−

∑

( x , y)∈X × Y

p̃ ( x) p( y∣x)log p( y∣x)

MaxEnt modell levezetés ●

Maximalizáljuk a Lagrange-függvényt m

∂ L( p , λ)=− p̃ ( x)[1+log p( y∣x)]+ ∑ λ i p̃ (x) f i (x , y)+λ m+1 ∂ p( y∣x) i=1



∂ L( p , λ)=− p̃ ( x)[1+log p( y∣x)]+ ∑ λ i p̃ (x) f i (x , y)+λ m+1 ∂ p( y∣x) i=1 ●

Ahonnan

m

λ m+1 log p( y∣x)=∑ λ i f i ( x , y)+ −1 p̃ ( x) i=1 m λ m+1 p( y∣x)=exp( ∑ λ i f i (x , y))exp( −1) p̃ ( x) i=1




Ahonnan

●

Kihasználva, hogy p(y|x) eloszlás

m

λ m+1 log p( y∣x)=∑ λ i f i ( x , y)+ −1 p̃ ( x) i=1 m λ m+1 p( y∣x)=exp( ∑ λ i f i (x , y))exp( −1) p̃ ( x) i=1 m

λ m+1 ∑ p( y∣x)= ∑ exp(∑ λi f i ( x , y ))exp( p̃ (x) −1)=1 y ∈Y y∈Y i=1 λ m+1 1 exp( −1)= m p̃ (x) ∑ exp(∑ λi f i (x , y)) y∈Y

i=1




Ahonnan

●

Kihasználva, hogy p(y|x) eloszlás

m

λ m+1 log p( y∣x)=∑ λ i f i ( x , y)+ −1 p̃ ( x) i=1 m λ m+1 p( y∣x)=exp( ∑ λ i f i (x , y))exp( −1) p̃ ( x) i=1 m

λ m+1 ∑ p( y∣x)= ∑ exp(∑ λi f i ( x , y ))exp( p̃ (x) −1)=1 y ∈Y y∈Y i=1 λ m+1 1 1 exp( −1)= = m Z p̃ (x) ∑ exp(∑ λi f i (x , y)) y∈Y

i=1

A MaxEnt modell tehát m

●

Formája:

exp( ∑ λ i f i (x , y)) p( y∣x)= m

●

Z

Ahol Z= ∑ exp( ∑ λ i f i (x , y)) az ún. particionáló fgv. y ∈Y

●

i=1

Regularizáció ●

●

i=1

A célfüggvény módosítása oly módon, hogy az a modellünk komplexitását is figyelembe vegye (MDL) Az egyszerűbb modelleket preferáljuk (Occam borotvája) –

Pl. diszkontáljuk a célfüggvény értékét a modellhez tartozó súlyvektor L1 vagy L2 norma szerint hosszával

Súlyok meghatározása és használata A súlyok meghatározása optimalizálási feladatként kezelhető

● ●

Newton-módszer, magasabb rendű módszerek (L-BFGS), ...

●

f1(x, y) ≡ [y = LOCATION ∧ w-1 = “in” ∧ isCapitalized(w)]

●

f2(x, y) ≡ [y = LOCATION ∧ hasAccentedLatinChar(w)]

●

f3(x, y) ≡ [y = DRUG ∧ ends(w, “c”)]

●

λ=[1,8; -0,6; 0,3]

●

P(LOCATION|in Québec) = e1,8–0,6/(e1,8–0,6 + e0,3 + e0) = 0,586

●

P(DRUG|in Québec) = e0,3/(e1,8–0,6 + e0,3 + e0) = 0,238

●

P(PERSON|in Québec) = e0 /(e1,8–0,6 + e0,3 + e0)= 0,176

MEMM és CRF ●

MEMM: maximum entrópia markov modell ● ●

●

Maximum Entrópia elv érvényesíte szekvenciajelölésben Diszkriminatív megközelítés, ami nem él a generatív HMM-eknél használt feltételezéssel a jellemzők osztálycímkéken kondicionált feltételes függetlenségére vonatkozóan Label bias probléma: – –

●

A rejtett állapotok közötti átmenetautomata nem teljes Előnyt élveznek azok az állapotok, melyekből kevés másik állapot érhető el

A MEMM “lépésről lépésre” osztályoz, a CRF pedig a teljes tokensorozathoz tartozó valószínűséget próbálja modellezni egyszerre ●

Nehezebb feladat, megoldások

de

még

mindig

ismertek

rá

hatékony

Számítógépes nyelvészeti jellemzők Data BUSINESS: Stocks hit a yearly low …

Label: BUSINESS Features {…, stocks, hit, a, yearly, low, …}

Szövegkategorizáció - bag of words

Data … to restructure bank:MONEY debt.

Label: MONEY Features

Data DT

JJ

NN …

The previous fall … Label: NN Features

{…, w-1=restructure, w+1=debt, …}

{w=fall, t-1=JJ w-1 =previous}

Jelentésegyértelműsítés

Szófaji kódolás

- kontextus

- felszíni jegyek - kontextus

Gráfikus modellek ●

Valószínűségi gráfikus modellel tetszőleges komplexitású eloszlást definiálhatunk ● ●

A gráf csúcsai véletlen változókat jeleznek Az élek az egyes változók közötti közvetlen függőséget reprezentálják

Szekvenciamodellek gráfos ábrázolása ●

HMM

●

MEMM

●

CRF

Alkalmazási lehetőségek ●

Szöveg,-és beszédfeldolgozás

●

Képfeldolgozás

●

Orvosi diagnosztika

Diszkriminatív modellezés és strukturált modellalkotás

Recommend Documents