15.3. Rejtett Markov-modellek
Az előző fejezet időbeli valószínűségi következtetésre szolgáló algoritmusokat vezetett be egy általános keretben, ami független volt az állapotátmenet- és az érzékelő modellek speciális formájától. Ebben és a következő két alfejezetben, olyan konkrétabb modelleket és alkalmazásokat tárgyalunk meg, amelyek bemutatják az alapalgoritmusok erejét, és bizonyos esetekben további tökéletesítéseket tesznek lehetővé.
A rejtett Markov-modellekkel (RMM) (hidden Markov model, HMM) kezdjük. Egy RMM egy olyan időbeli valószínűségi modell, amelyben a folyamat állapotát egyetlen diszkrét valószínűségi változó írja le. [A modell karakterisztikus tulajdonsága tehát a rejtett állapot, azaz a (sztochasztikus) állapotfejlődés és annak passzív (sztochasztikus) megfigyelése. Az index időértelmezése helyett bármely szekvenciális értelmezés lehetséges, gyakori például az indexnek mint egy egydimenziós pozíciónak az értelmezése is – a ford.] A változó lehetséges értékei a világ lehetséges állapotai. Az előző fejezetben leírt esernyős példa ezért egy RMM, mivel csak egyetlen állapotváltozója van az Esőt. Az RMM keretei között további állapotváltozók csak úgy adhatók hozzá az időbeli modellhez, hogy az összes állapotváltozót egyetlen „megaváltozóba” kombináljuk, amelynek az értékei az egyes állapotváltozók értékeinek minden lehetséges kombinációja. Látni fogjuk, hogy az RMM-ek korlátozott struktúrája lehetővé teszi az összes alapalgoritmus egy nagyon egyszerű és elegáns mátrixos átfordítását.[158] A 15.6. alfejezet bemutatja az RMM-ek használatát a beszédfelismerésben.
Egyetlen, diszkrét Xt állapotváltozó esetén konkrét forma adható az állapotátmenet-modell, az érzékelő modell és az előre és hátra üzenetek reprezentációira. Jelöljük az Xt állapotváltozó értékeit 1, …, S egészekkel, ahol S a lehetséges állapotok száma. A P(Xt |Xt–1) állapotátmenet-modell ekkor egy T S × S mátrix, ahol
Tij = P(Xt = j|Xt–1 = i)
Azaz Tij az átmenet valószínűsége i-ből j-be. Például az esernyős világban az állapotátmenet-mátrix
Az érzékelő modellt szintén mátrixalakra hozzuk. Ebben az esetben mivel az Et bizonyítékváltozó értéke ismert, mondjuk et, így a modellnek csak azt a részét használjuk, ami az et megjelenésének valószínűségét meghatározza. Minden t időpontra konstruálunk egy Ot diagonális mátrixot, aminek az átlóbeli elemeit a P(et|Xt = i) értékek adják, a többi értéke pedig 0. Például az esernyős világban az 1. napon az U1 = igaz, így a 15.2. ábra szerint azt kapjuk, hogy
Most oszlopvektort használva az előre és hátra üzenetek reprezentálására, a számítások egyszerű mátrix-vektor műveletekké válnak. A (15.3) előrefelé egyenlet ekkor
f1:t + 1 = αOt + 1T ⊤f1:t (15.10)
és a (15.7) visszafelé egyenlet pedig
bk + 1:t = TOk + 1bk + 2:t (15.11)
Ezekből az egyenletekből látható, hogy az előre-hátra algoritmus (lásd 15.4. ábra) időkomplexitása egy t hosszúságú sorozatra történő alkalmazásnál O(S2t), mivel minden lépés egy S elemű vektor szorzását igényli egy S × S mátrixszal. A tárigény pedig O(St), mivel az előrefelé fázis t darab S méretű vektort tárol el.
Amellett hogy a mátrixos jelölés az RMM-ek esetében a szűrés és a simítás algoritmusaira egy elegáns leírásmódot kínál, ez javított algoritmusokra is jelez lehetőségeket. Az első az előre-hátra algoritmus egy egyszerű változata, ami simítás elvégzését teszi lehetővé állandó tárigény mellett, a sorozat hosszától függetlenül. Az ötlet az, hogy egy konkrét k időpillanatban a simítás mind az f1:k előre, mind a bk+1:t hátra üzenetek egyidejű jelenlétét igényli a (15.6) egyenlet szerint. Az előre-hátra algoritmus ezt úgy biztosítja, hogy az előrefelé fázisban tárolja az f-eket, hogy a hátrafelé fázisban elérhetők legyenek. Egy másik módszer szerint ez úgy érhető el, hogy egyetlen menetben mind f-et, mind b-t ugyanabban az irányban terjesztjük. Például az f „előre” üzenet terjeszthető hátrafelé, ha átrendezzük a (15.10) egyenletet, hogy a másik irányban működjön:
A módosított szűrési algoritmus úgy működik, hogy először lefut egy szabványos előre fázis, kiszámítva ft:t-t (elfelejtve az összes közbenső eredményt), majd lefut egy visszafelé fázis együtt b-re és f-re, kiszámítva a simított becslést minden időpontban. Mivel mindegyik üzenetnek csak egy példánya szükséges, a tárigény állandó (azaz független t-től, a sorozat hosszától). Az algoritmusra egyetlen jelentős megkötés vonatkozik: az állapotátmenet-mátrixnak invertálhatónak kell lennie, és az érzékelő modellben nem lehetnek nullák – azaz minden megfigyelésnek lehetségesnek kell lenni minden állapotban.
A második terület, ahol a mátrixjelölés javítást jelez, a menet közben történő (online) simítás állandó időkülönbözettel. Az a tény, hogy a simítás elvégezhető állandó tárigénnyel azt jelzi, hogy léteznie kell egy hatékony rekurzív algoritmusnak menet közbeni simításra – azaz olyan algoritmusnak amelynek az időkomplexitása független az időkülönbözet hosszától. Tegyük fel, hogy az időkülönbözet d; azaz a simítást t – d időpontban végezzük, ahol t a jelenlegi időpont. A (15.6) egyenlet szerint ki kell számolnunk a t – d időpontra az
α f1:t–d bt–d+1:t
értékét. Majd amikor az új megfigyelés beérkezik, a t – d + 1 időpontra kell kiszámítanunk az
α f1:t–d+1 bt–d+2:t+1
értéket. Hogyan tehető ez meg inkrementálisan? Először is, az f1:t–d+1 kiszámítható az f1:t–d-ből a szabványos szűrés műveletét használva a (15.3) egyenlet szerint.
A visszafelé üzenet inkrementális kiszámítása trükkösebb, mivel nincs egyszerű kapcsolat a régi bt–d+1:t visszafelé üzenet és az új bt–d+2:t+1 visszafelé üzenet között. Ehelyett, a régi bt–d+1:t visszafelé üzenet és a sorozat kezdő bt+1:t visszafelé üzenete közötti kapcsolatot fogjuk megvizsgálni. Ennek eléréséhez alkalmazzuk a (15.11) egyenletet d alkalommal, és azt kapjuk, hogy
ahol a Bt–d+1:t mátrix a T és az O mátrixok sorozatának a szorzata. A B-t felfoghatjuk egy „transzformációs operátornak”, ami egy későbbi visszafelé üzenetet egy korábbiba alakít. Egy hasonló egyenlet áll fenn az új visszafelé üzenetekre a következő megfigyelés beérkezése után:
Ha a (15.12) és a (15.13) egyenletben megvizsgáljuk a szorzatokat, láthatjuk, hogy egyszerű kapcsolat van közöttük: a második szorzathoz el kell „osztani” az első szorzatot TOt–d+1-gyel, és megszorozni az új utolsó elemmel TOt+1-gyel. Mátrixjelöléssel ekkor a régi és az új B mátrixok között egy egyszerű kapcsolat van:
Ez az egyenlet a B mátrix egy inkrementális frissítését adja, amely viszont (a (15.3) egyenlet által) lehetővé teszi az új bt–d+2:t+1 visszafelé üzenet kiszámítását. A teljes algoritmus, ami az f és B tárolását és frissítését igényli, a 15.6. ábrán látható.
15.6. ábra - Egy állandó d lépésnyi időkülönbözettel simító algoritmus, folyamatos működésű (online) algoritmusként megvalósítva: egy új időpontbeli megfigyelésre kiadja az új simított becslést
[158] A vektor- és mátrixművelekben járatlan olvasó számára hasznos lehet az A) függeléket átnézni, mielőtt a fejezetben továbbhaladna.
