Kezdjük a szűréssel. Megmutatjuk, hogy ez menet közben egyszerűen, online módon elvégezhető: a t-edik időpillanatig tartó szűrés eredményét ismerve, a t + 1-edik időpillanatra az eredmény könnyen kiszámítható az új e_t+1 bizonyítékból. Azaz

P(Xt+1|e1:t+1) = f(et+1, P(Xt|e1:t))

valamely f függvénnyel. Ezt a folyamatot gyakran nevezik rekurzív becslésnek (recursive estimation). Tekinthetjük a számítást úgy, mint ami valójában két részből áll: elsőként a jelenlegi állapot eloszlását terjesztjük előre t-ről t + 1-re; azután fogjuk frissíteni, felhasználva az új e_t+1 bizonyítékot. Ez a kétlépéses folyamat elég egyszerűen alakul:

P(Xt+1|e1:t+1) = P(Xt+1|e1:t, et+1) (felosztva a bizonyítékot)

= α P(et+1|Xt+1, e1:t) P(Xt+1|e1:t) (a Bayes-szabályt használva)

= α P(et+1|Xt+1) P(Xt+1|e1:t) (a bizonyíték Markov-tulajdonsága miatt)

Itt és végig a fejezetben, az α egy normalizációs konstans, ami a valószínűségek 1-re összegzését biztosítja. A második tényező P(X_t+1|e_1:t) reprezentálja a következő állapot egylépéses előrejelzését, és az első tényező ezt frissíti az új bizonyítékkal. Vegyük észre, hogy P(e_t+1|X_t+1) közvetlenül kinyerhető az érzékelő modellből. Most a jelenlegi X_t állapotot feltételnek véve a következő állapot egylépéses előrejelzéséhez jutunk:

(kihasználva a Markov-tulajdonságot)(15.3)

Az összegzésen belül az első tényező egyszerűen az állapotátmenet-modell és a második a jelenlegi állapot eloszlása. Így megvan a kívánt rekurzív képlet. A szűrt P(X_t|e_1:t) becslésre úgy gondolhatunk, mint egy f_1:t „üzenetre”, amit előre terjesztünk végig a sorozaton, minden átmenetnél az új megfigyeléssel módosítva és frissítve. A folyamat

f1:t+1 = α Előre(f1:t, et+1)

ahol az ELŐRE a (15.3) egyenlet által leírt frissítést hajtja végre.

Mutassuk be a szűrési folyamatot két lépésen keresztül az alap esernyős példában (lásd 15.2. ábra). Feltesszük, hogy a biztonsági őrünknek van valamilyen a priori hite, hogy a 0. napon esett-e, éppen azelőtt, hogy a megfigyelések sorozata elkezdődik. Tegyük fel, hogy ez P(R₀) = 〈0,5, 0,5 〉. Most a két megfigyelést a következőképpen dolgozzuk fel:

és a t = 1-beli bizonyítékkal való frissítés azt adja, hogy

P(R1|u1) = αP(u1|R1) P(R1) = α〈0,9, 0,2〉〈0,5, 0,5〉

= α〈0,45, 0,1〉 ≈ 〈0,818, 0,182〉

a t = 2-beli bizonyítékkal való frissítés pedig azt adja, hogy

P(R2|u1, u2) = αP(u2|R2) P(R2|u1) = α〈0,9, 0,2〉 〈0,627, 0,373〉

= α〈0,565, 0,075〉 ≈ 〈0,883, 0,117〉

Érzésünk szerint az eső valószínűsége azért növekedett az 1. napról a 2. napra, mert az eső folytatódik. A 15.2. (a) feladat ennek a tendenciának a további vizsgálatát kéri.

Az előrejelzés feladatát tekinthetjük egyszerűen szűrésnek új bizonyíték hozzáadása nélkül. Valójában a szűrési folyamat már magában foglal egy egylépéses előrejelzést és könnyen származtatható a következő rekurzív számítás a t + k + 1 állapot előrejelzésére a t + k előrejelzéséből:

Természetesen ez a számítás csak az állapotátmenet-modellt tartalmazza és nem az érzékelő modellt.

Érdekes meggondolni, hogy mi történik, ahogy egyre távolabbra próbálunk előre jelezni a jövőben. A 15.2. (b) feladat megmutatja, hogy az eső előrejelzett eloszlása a 〈0,5, 0,5〉 fix ponthoz konvergál, ami után a továbbiakban állandó marad. Ez az állapotátmenet-modell által meghatározott Markov-folyamat stacionárius eloszlása (stationary distribution) (lásd még 14.5.2. szakasz - Következtetés Markov-lánc szimulációval rész). Rengeteg ismeret gyűlt fel az ilyen eloszlások tulajdonságairól és a keverési időről (mixing time) – ami nagyjából a fix pont eléréséig eltelt idő. Gyakorlati szempontból ez bukásra ítél minden olyan kísérletet, ami a keverési idő kis hányadánál nagyobb számú lépés múlva kísérli meg az aktuális állapot előrejelzését. Minél bizonytalanabb az állapotátmenet-modell, annál rövidebb a keverési idő, és a jövő annál homályosabb.

A szűrésen és az előrejelzésen túl, felhasználhatjuk az előrehaladó rekurziót egy bizonyítéksorozat P(e_1:t) valószínűségének a kiszámítására is. Ez egy hasznos mennyiség, ha különböző időbeli modelleket szeretnénk összehasonlítani, amelyek ugyanazt a bizonyítéksorozatot állíthatták elő; például a 15.6. alfejezetben különböző szavakat hasonlítunk össze, amelyek ugyanazt a hangsort állíthatták elő. Ehhez a rekurzióhoz felhasználjuk az ℓ_1:t = P(X_t, e_1:t) valószínűségi (likelihood) üzenetet. Egyszerű feladat azt megmutatni, hogy

ℓ1:t+1 = Előre(ℓ1:t, et+1)

Kiszámítva ℓ _1:t-t, az aktuális valószínűséget az X_t feletti összegzéssel kapjuk:

Ahogy korábban meghatároztuk, a simítás (smoothing) múltbeli állapotok feletti eloszlás kiszámításának a folyamata a jelenig tartó bizonyítékok ismeretében; azaz P(X_k|e_1:t) számítása valamely 0 ≤ k < t esetén (lásd 15.3. ábra). Ez legkényelmesebben két részletben végezhető el – a bizonyíték k-ig és a bizonyíték k + 1-től t-ig,

P(Xk|e1:t) = P(Xk|e1:k, ek+1:t)

= α P(Xk|e1:k) P(ek+1:t|Xk, e1:k) (a Bayes-szabályt használva)

= α P(Xk|e1:k) P(ek+1:t|Xk) (a feltételes függetlenséget használva)

= α f1:k bk+1:t (15.6)

ahol definiáltuk a b_k+1:t = P(e_k+1:t|X_k) „visszafelé” üzenetet, analóg módon az f_1:k előre üzenethez. Az f_1:k előre üzenetet előre szűréssel lehet kiszámolni 1-től k-ig, a (15.3) egyenlet alapján. A b_k+1:t visszafelé üzenetről pedig kiderül, hogy egy egyszerű rekurzív folyamattal kiszámítható, ami t-től visszafelé halad:

ahol az utolsó lépés az e_k+1 és az e_k+2:t feltételes függetlenségéből következik az x_k+1 melletti feltétellel. Az összegzésben a három tényezőből az első és a harmadik közvetlenül a modellből megkapható, a második pedig a „rekurzív hívás”. Az üzenetjelölést használva kapjuk, hogy

bk+1:t = Hátra(bk+2:t, ek+1:t)

ahol a HÁTRA a (15.7) egyenlet által leírt frissítést hajtja végre. Ahogy az előrefelé rekurziónál, az egyes frissítésekhez szükséges idő- és tárigény állandó, és így t-től független itt is.

15.3. ábra - A simítás egy múltbeli k időpontban az állapot a posteriori P(X_k|e_1:t) eloszlását számítja ki egy teljes, 1-től t-ig terjedő megfigyelés sorozat ismeretében

Most láthatjuk, hogy a (15.6) egyenlet mindkét tényezője kiszámítható időbeli rekurzióval, az egyik előrefelé fut 1-től k-ig, és a szűrés (15.3) egyenletét használja, a másik visszafelé fut t-től k+1-ig, és a (15.7) egyenletet használja. Figyeljünk arra, hogy a viszszafelé fázist b_t+1:t = P(e_t+1:t|X_t) = 1-gyel inicializáljuk, ahol 1 egy egyesekből álló vektor. (Mivel e_t+1:t egy üres sorozat, a megfigyelésének valószínűsége 1.)

Alkalmazzuk most ezt az algoritmust az esernyős példára, kiszámítva az eső valószínűségének simított becslését t = 1-nél, az első és második nap megfigyeléseinek ismeretében. A (15.6) egyenlet szerint ezt az adja meg, hogy

P(R1|u1, u2) = α P(R1|u1) P(u2|R1) (15.8)

A korábban leírt előrefelé szűrési folyamatból már tudjuk, hogy az első tényező 〈0,818, 0,182〉. A második tényezőt a (15.7) egyenletbeli visszafelé rekurziót alkalmazva számíthatjuk ki:

Ezt visszahelyettesítve a (15.8) egyenletbe azt kapjuk, hogy a simított becslés az esőre az 1. napon

P(R1|u1, u2) = α 〈0,818, 0,182〉 × 〈0,69, 0,41〉 ≈ 〈0,883, 0,117〉

Így ebben az esetben a simított becslés nagyobb, mint a szűrt becslés (0,818). Ennek oka az, hogy az esernyő a 2. napon valószínűbbé teszi, hogy esett a 2. napon, és mivel az eső tartósan szokott esni, ez még valószínűbbé teszi, hogy esett az 1. napon.

Mind az előrefelé, mind a visszafelé haladó rekurzió lépésenként állandó időt igényel; így a simítás időkomplexitása e_1:t bizonyíték esetén O(t). Ez egy konkrét k időlépésbeli simítás komplexitása. Ha a teljes szekvenciát szeretnénk simítani, nyilvánvaló módszer, hogy egyszerűen az egész simítási folyamatot lefuttatjuk minden egyes simítandó időpillanatra. Ez O(t²) időkomplexitást eredményez. Jobb megközelítés a dinamikai programozás nagyon egyszerű alkalmazásával O(t)-re csökkenti a komplexitást. A megoldás kulcsa megjelent az esernyős példa előző elemzésében, ahol az előrefelé szűrés folyamatának eredményeit újra fel tudtuk használni. A lineáris idejű algoritmus kulcsa így az előrefelé szűrés eredményeinek a tárolása az egész sorozatnál. Aztán a visszafelé rekurziót futtatjuk t-től 1-ig, kiszámítva a szűrt becslést minden k lépésnél a kiszámolt b_k+1:t visszafelé üzenetből és a tárolt f_1:k előrefelé üzenetből. Az algoritmus, amit találóan előre-hátra algoritmusnak (forward-backward algorithm) neveznek, a 15.4. ábrán látható.

15.4. ábra - Az előre-hátra algoritmus, ami állapotok egy sorozatának az a posteriori valószínűségeit számítja ki adott megfigyelési sorozat ismeretében. Az ELŐRE és a HÁTRA műveleteket rendre a (15.3) és (15.7) egyenletek definiálják.

A figyelmes olvasó észrevehette, hogy a 15.3. ábrán látható Bayes-hálóstruktúra egy polifa (polytree) a 14. fejezet szóhasználatában. Ez azt jelenti, hogy a csoportosító algoritmus egy nyilvánvaló alkalmazása szintén lineáris idejű algoritmust eredményez, ami a teljes sorozatra kiszámítja a simított becslést. Mára már világossá vált, hogy az előre-hátra algoritmus valójában a csoportosító eljárásokban használt polifa terjesztési algoritmusnak egy speciális esete (bár a kettőt egymástól függetlenül fejlesztették ki).

Az előre-hátra algoritmus alkotja a gerincét azon számítási módszereknek, amelyeket számos zajos megfigyelések sorozatával foglalkozó alkalmazásban használnak, a beszédfelismeréstől a repülőgépek radarkövetéséig. Ahogy leírtuk, két gyakorlati hátránya van. Az első, hogy a tárigénye túl nagy lehet azoknál az alkalmazásoknál, ahol az állapottér nagy, és a sorozatok hosszúak, mivel O(|f|t) méretű tárat használ, ahol |f| az előrefelé üzenet reprezentációjának a mérete. A tárigény O(|f|log t)-re csökkenthető az időkomplexitásnak egy log t tényezővel történő egyidejű megnövelése árán, ahogy a 15.3. feladat mutatja. Bizonyos esetekben (lásd 15.3. alfejezet) egy állandó tárigényű algoritmus használható időbüntetés nélkül.

Az alapalgoritmus második hátránya, hogy a folyamatos (online) működéshez módosítást igényel. Ekkor ugyanis a korábbi időpontokhoz simított becsléseket kell kiszámítanunk, amint folyamatosan új megfigyelések érkeznek a sorozat végéhez. A leggyakoribb követelmény az állandó időkülönbségű simítás (fixed-lag smoothing), ami a P(X_t–d|e_1:t) simított becslés kiszámítását jelenti egy rögzített d-re. Azaz a simítást a jelenlegi t időpillanat előtt d lépéssel lévő időpontra végezzük el; t növekedését a simításnak is követnie kell. Nyilvánvaló, hogy lefuttathatjuk az előre-hátra algoritmust a d lépéses „ablakban”, amint egy új bizonyíték adódik, de ez nem tűnik hatékonynak. A 15.3. alfejezetben látni fogjuk, hogy az állandó időkülönbségű simításnál egy frissítés bizonyos esetekben állandó idő alatt megtehető, függetlenül a d időkülönbségtől.

Tegyük fel, hogy a biztonsági őr esernyősorozata a munkája első öt napjában az [igaz, igaz, hamis, igaz, igaz]. Mi a legvalószínűbb időjárás-sorozat, ami ezt megmagyarázza? Az esernyő hiánya a 3. napon azt jelenti, hogy nem esett, vagy azt, hogy az igazgató elfelejtette elhozni? Ha a 3. napon nem esett, talán a 4. napon sem esik (mivel az időjárás nem változik gyorsan), de ekkor az igazgató puszta óvatosságból hozta az esernyőt. Összességében 2⁵ lehetséges időjárás-sorozatot választhatunk. Létezik-e módszer a legvalószínűbb sorozat megkeresésére, az összes felsorolása nélkül?

Az egyik megközelítés, amit kipróbálhatunk a következő lineáris idejű algoritmus: használjuk a simító algoritmust, hogy megtaláljuk az időjárás a posteriori eloszlását minden időpillanatban; majd állítsuk elő a sorozatot minden egyes lépésnél az a posteriori szerinti legvalószínűbb időjárást felhasználva. Egy ilyen megközelítést kötelező gyanakvással kell fogadnia az olvasónak, mivel a szűrés által kiszámított a posteriori eloszlások az egyes időpontok feletti eloszlások, ezzel szemben a legvalószínűbb sorozat megtalálásához az összes időpont feletti együttes valószínűségeket kell figyelembe venni. Az eredmények valójában nagyon különbözők lehetnek (lásd 15.4. feladat).

Lineáris idejű algoritmus azonban létezik a legvalószínűbb sorozat megtalálására, de kicsit több gondolkozást igényel. Ugyanazon a Markov-tulajdonságon alapul, mint ami hatékony algoritmusokat eredményezett a szűrésre és a simításra. A problémáról való gondolkodás legkönnyebb módja, hogy ha minden sorozatot egy útvonalnak tekintünk egy gráfban, aminek a csomópontjai az egyes időpillanatokban a lehetséges állapotok. Egy ilyen gráf látható az esernyős problémára a 15.5. (a) ábrán. Most gondoljuk meg a gráfon keresztül vezető legvalószínűbb út megkeresésének a problémáját, ahol egy út valószínűsége (a likelihood érték) az útvonal menti átmenetek valószínűségeinek és az egyes állapotokban adott megfigyelések valószínűségeinek a szorzata. Koncentráljunk most azokra az útvonalakra, amelyek elérik az Eső₅ = igaz állapotot. A Markov-tulajdonság miatt fennáll, hogy az Eső₅ = igaz állapotba vezető legvalószínűbb útvonal tartalmazza azt a legvalószínűbb útvonalat, amely valamelyik 4. időpontbeli állapotba vezet, és amit egy átmenet követ az Eső₅ = igaz-ba; a 4. időpontbeli állapot pedig, ami része lesz az Eső₅ = igaz-ba vezető útnak, az az állapot, amelyik maximalizálja ennek az útvonalnak a valószínűségét.

A (15.9) egyenlet megegyezik a szűrés (15.3) egyenletével, azzal a kivétellel, hogy

ami az x_t állapotba vezető legvalószínűbb út valószínűségeit adja meg; és

Így a legvalószínűbb állapotsorozat kiszámítása hasonló a szűréshez: előrefelé végigfut a sorozaton, minden időpontban kiszámítva az m üzeneteket a (15.9) egyenlet szerint. A számítás menetét a 15.5. (b) ábra mutatja. Végül ez kiadja az összes végső állapothoz vezető legvalószínűbb útvonal valószínűségét. Így már könnyen kiválasztható a teljes hosszúságú legvalószínűbb sorozat (a vastagon szedettel kiemelt végső állapottól). Az aktuális sorozat azonosításához – szemben azzal, amikor csak a valószínűségét számítjuk ki – az algoritmusnak minden állapotból mutatókat kell nyilvántartania a legjobb hozzá vezető állapothoz (vastagon szedettel látható); a sorozat a mutatóknak a legjobb végső állapottól való visszafelé követésével határozható meg.

15.5. ábra - (a) Az Eső_t lehetséges állapotsorozatait tekinthetjük egy átvezető útnak egy gráfon, aminek csomópontjai a lehetséges állapotok az egyes időpontokban. (Az állapotokat négyzetes csomópont jelzi, hogy félreérthetetlenül megkülönböztessük őket egy Bayes-háló csomópontjaitól.) (b) A Viterbi-algoritmus működése az [igaz, igaz, hamis, igaz, igaz] megfigyelési sorozatra. Minden t időpontra feltüntettük az m_1:t üzenet értékeit, ami minden egyes t időpontbeli állapothoz megadja a legjobb, benne végződő sorozat valószínűségét. Minden egyes állapothoz egy vastag nyíl is vezet, ami a legjobb elődjét jelzi, a megelőző sorozat valószínűségének és az átmenet valószínűségének a szorzata szerint. A vastag nyilak visszafelé követése az m_1:5-beni legvalószínűbb állapotból pedig megadja a legvalószínűbb sorozatot.

Az előzőleg leírt algoritmust Viterbi-algoritmusnak nevezik a megalkotója után. Hasonlóan a szűrési algoritmushoz, ennek a komplexitása is lineáris t-ben, a sorozat hosszában. Azonban eltérően a szűréstől, a tárigénye szintén lineáris t-ben. Ez azért van így, mert a Viterbi-algoritmusban mutatókkal kell nyilvántartani az egyes állapotokhoz vezető legjobb sorozatot.