Szekvenciatanulás

A szekvenciatanulás (sequence labeling, stuctured prediction) problémája abban tér el a klasszikus osztályozási feladattól, hogy itt nem egyetlen szeparált egyed címkéjének előrejelzésére építünk statisztikai modellt, hanem egyidőben egyedek egy sorozatára. Természetesen ebben az esetben nem élhetünk az egyedek közötti függetlenség feltevésével sem.

Az információkinyerés problémáját gyakran fogalmazzák meg szekvenciatanulásként. Tekintsük példaként a tulajdonnév-felismerést. Ekkor a cél szavak egy sorozatának (általában egy mondatnak) felcímkézése tulajdonnév kategóriákkal. A kimenet is tehát címkék szekvenciája lesz:

SólyomPER  LászlóPER  MagyarországLOC  köztársaságiNON  elnökeNON  azNON  MTV-nekORG  elmondtaNON   . . .

Alább bemutatjuk a három legismertebb szekvencia alapú gépi tanulási modellt.

Rejtett Markov-modell

A legkorábbi szekvencia alapú tanuló algoritmus a rejtett Markov-modell (hidden Markov model, Hmm, Manning & Schütze, 1999). A modell alaptevései, hogy a rendszer állapotai generálják a megfigyeléseket (pl. szavak) és hogy egy elsőrendű Markov-modellben a rendszer állapota a t időpontban (yt  ) csak a megelőző állapottól függ, azaz

P(y∣y   ,y   ,...,y )= P(y ∣y   )
   t t- 1 t-2     1      t t-1

valamint a t időpontbeli megfigyelés (x
 t  ) csak az aktuális y
 t  állapottól függ. A modell az állapotsorozat és megfigyeléssorozat együttes valószínűségét becsli, célja a legvalószínűbb állapotsorozat megtalálása az adott megfigyeléssorozathoz (a gyakorlatban általában a rendszer állapotait egyértelműen megfeleltetik a cél címkéknek). A rejtett Markov-modell három típusú valószínűséget használ:

Ezek felhasználásával a becsülendő együttes eloszlás:

P(x,y)= P(y )P(x ∣y ) T P(x∣y  )P(x ∣y )
           1    1 1 Y2    t t-1    t t

Ezeket az eloszlásokat egy tanító halmazból a Baum–Welsh-eljárás (egy Expectation-Maximization módszer) segítségével becsülhetjük. Ezen becslések ismeretében és adott szekvencia esetén a legvalószínűbb utat (állapotszekvenciát) a Viterbi algoritmussal találhatjuk meg. Ez az algoritmus dinamikus programozáson alapul, lényegében a t -ik legvalószínűbb állapotot az alapján választjuk meg, hogy a (t- 1)  .ik állapotokba milyen eséllyel kerülhet a rendszer. A Baum–Welsh- és Viterbi-algoritmusok részletesebb leírása megtalálható például Manning & Schütze, 1999 és Rabiner, 1990 munkákban.

A rejtett Markov-modellekkel kapcsolatban két problémát kell tisztán látnunk:

Maximum entrópia Markov-modell

A maximum entrópia Markov-modell (maximum entropy Markov model, Memm, McCallum et al, 2000) nem tételez fel függetlenséget az egyes — megfigyeléseket leíró — jellemzők között. Alapja egy osztályozó eljárás a maximum entrópia (más néven logisztikus regresszió) módszer ami a osztálycímkék eloszlását, mint függvényt közelíti. Alapfeltevése, hogy a feltételes valószínűség logaritmusa lineáris modellel leírható:

         1       K
P(y∣x) = ----exp{ X λy,jxj},
        Z(x)    j=1

ahol K darab xj  jellemző van, azok súlya a λy,j  paraméterek, valamint Z(x)  egy normalizációs faktor:

              K
Z(x)= X  exp{X  λy,jxj}
       y     j=1

A maximum entrópia Markov-modell nem használ külön átmeneti és emissziós valószínűségeket, hanem egyetlen feltételes valószínűségbe vonja ezeket össze: mekkora az egyes címkék valószínűsége a megelőző címke és a megfigyelt jellemzővektor függvényében. Ezt az eloszlást becsli az exponenciális modell segítségével:

                 1         K
P(yt∣yt-1,x) = ---------exp{X  λjfj(x,yt,yt-1)},
             Z(yt-1,x)     j=1

ahol fj  egy jelölési egyszerűsítés az f(yt,yt-1)  és f (yt,xt)  jellemzőfüggvények megadására. A tanulás itt tehát az egyes jellemzők súlyának (λy,j  ) a megtanulása. A becsült P(yt∣yt-1,x)  felhasználásával azután a Viterbi-algoritmushoz hasonló módon kiszámíthatjuk a legvalószínűbb címkesorozatot.

A Memm tanítása csak némileg komplexebb, mint a Hmm-é, viszont empirikusan bizonyított, hogy a legtöbb probléma esetén — a jellemzők közötti összefüggések kiaknázásának köszönhetően — sokkal hatékonyabb.

A Memm problémája az, hogy a tanítás folyamán megelőző címkeként az etalon (gold standard) címkéket használja, a predikciós fázisban azonban az előző címke nem biztos, hogy helyes, így ez a „jellemző” igen zajossá válhat. Ez a probláma a gyökere az irodalomban label bias problémaként (Lafferty et al, 2001) emlegetett jelenségnek.

Feltételes valószínűségi mezők

A Hmm és a Memm is lokális eloszlásbecsléseket hajtanak végre, majd a Viterbi-algoritmus segítségével kiválasztják a legvalószínűbb utat. Ezzel szemben a label bias problémára megoldást kínáló feltételes valószínűségi mező (conditional random fields, Crf, Lafferty et al, 2001) valóban az egész struktúra előrejelzését végzi el. A Crf nem P(yt∣xt)  jellegű lokális valószínűségeket becsül, hanem az egész szekvencia feltételes valószínűségét:

         1          K
P(y∣x) = ----exp {X X  λjfj(x,yt,yt-1)}
        Z(x)     t j=1

Figyeljük meg, hogy a normalizációs faktor itt már csak a megfigyelés függvénye, így nem jelentkezhet a label bias probléma. A rendszer tanítása (λ
  j  becslése) általában a logaritmikus feltételes valószínűség maximalizálásával történik:

              N
max ℓ(λ) = max X p(y(i)∣x(i)),
 λ            i=1

ahol a tanító halmaz N darab  (i)
x  megfigyelés-szekvenciából és  (i)
y  állapotszekvenciából áll. Mivel a ℓ(λ)  függvény g(x) = log(Pi exp xi))  alakú így szigorúan konkáv is. A Crf optimalizálást általában valamilyen kvázi-Newton-módszerrel (például BFGS (Byrd et al, 1995)) szokták elvégezni.

A Crf egyetlen nagy hátránya a tanítás időigénye, ami égyzetesen függ a osztálycímkék számától és lineárisan a tanító példák számától valamint az átlagos szekvenciahossztól. Azokra a problémákra ahol ez az idő elfogadható nagyságrendű napjaink legsikeresebb rendszerei Crf-et használnak.

A fent bemutatott Crf modell (linear-chain Crf) a legegyszerűbb feltételes valószínűségi mezőn alapul ahol yt  csak yt-1  és yt+1  -től függ. Elméletileg a modell tetszőleges valószínűségi mező felett értelmezhető. Ekkor lehetővé válik például távoli egyedek közötti (pl. mondatokon átívelő) összefüggések leírása is. Ezeknek az általános Crf-eknek (Sutton & McCallum, 2007) az effektív tanítása még nyitott kutatási kérdés, gyakorlati problémák megoldására (egy-két speciális esettől eltekintve) nem alkalmazhatóak.

A három modell összehasonlítása

Összefoglalásként tekintsük át a három bemutatott modellt azok gráfos ábrázolásán keresztül (1. ábra).


PIC
1. ábra. A Hmm-, a Memm- és a lánc-Crf-modellek gráfos reprezentációja (balról jobbra). Az üres pont azt jelöli, hogy a változót nem a modell generálja (Forrás: Lafferty et al, 2001.)


A Hmm alapfeltevése, hogy a megfigyeléseket az állapotok generálják. Legnagyobb hátránya, hogy a megfigyeléseket leíró jellemzőket egymástól függetlennek tételezi fel. A Memm nem igényli a P (x)  kiszámítását, így a jellemzők közötti összefüggések modellezését kikerüli. A modellben az egyes címkék eloszlását egy exponenciális modellel írhatjuk le, ahol tulajdonképpen a jellemzők sokdimenziós terében egy függvény-approximációt hajtunk végre a tanítás folyamán.

A Memm már adottnak tekinti a megfigyeléssorozatot ellentétben a Hmm-el) és célja az optimális állapotszekvencia megtalálása (középső ábra) azonban magával hozza a label bias problémáját. Ennek kiküszöbölésére a Crf modell a lokális valószínűség-becslések helyett az egész állapotszekvencia feltételes valószínűségében optimalizál. Ez megteremti a kapcsolatot a t időpontbeli címke és a későbbi (t < ) megfigyelések közt is (nem irányított a modell).

Forrás:

R. H. Byrd, P. Lu, J. Nocedal, and C. Y. Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computing, 16(6):1190–1208, 1995.

J. Lafferty, A. McCallum, and F. Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. of ICML-01, 18th Int. Conf. on Machine Learning, pages 282–289, Williamstown, USA, 2001.

Ch. D. Manning and H. Schütze. Foundations of Statistical Natural Language Processing. The MIT Press, Cambridge, 1999.

A. McCallum, D. Freitag, and F. C. N. Pereira. Maximum entropy Markov models for information extraction and segmentation. In Proc. of ICML-00, 17th Int. Conf. on Machine Learning, pages 591–598, Stanford, USA, 2000.

L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. In A. Waibel and K.-F. Lee, editors, Readings in Speech Recognition, pages 267–296. Kaufmann, San Mateo, CA, 1990.

Ch. Sutton and A. McCallum. An introduction to conditional random fields for relational learning. In L. Getoor and B. Taskar, editors, Introduction to Statistical Relational Learning. MIT Press, 2007. To appear.