T-61.5020 Luonnollisten kielten tilastollinen käsittely
Vastaukset 10, ke 4.4.2007, 12:15-14:00 -- Markov-ketjut ja kätketyt Markov-mallit
Versio 1.0

1.

a)

Kuvaan 1 on piirretty Turun säätila Markov-ketjuna.

Kuva 1: Säätila Markov-ketjuna

b)

Lasketaan tilasekvenssin $\mathbf S = (S_3, S_2, S_1, S_1, S_1)$ todennäköisyys kun tiedetään, että lähdetään tilasta $S_2$. Haluamme siis laskea todennäköisyyttä

$$P(\mathbf S ~\vert~ q_0=S_2) = P(q_1=S_3, q_2=S_2, q_3=S_1, q_4=S_1, q_5=S_1~\vert~ q_0=S_2)$$

$$= P(q_1=S_3 ~\vert~ q_0=S_2) \cdot P(q_2=S_2 ~\vert~ q_0=S_2, q_1=S_3)$$

$$\cdot P(q_3=S_1 ~\vert~ q_0=S_2, q_1=S_3, q_2=S_2)$$

$$\cdot P(q_4=S_1 ~\vert~ q_0=S_2, q_1=S_3, q_2=S_2, q_3=S_1)$$

$$\cdot P(q_5=S_1 ~\vert~ q_0=S_2, q_1=S_3, q_2=S_2, q_3=S_1, q_4=S_1)$$

Ensimmäisen rivin todennäköisyys on jaettu tässä käyttäen monta kertaa todennäköisyyslaskun kaavaa $P(A,B\vert C)=P(A\vert C)\cdot P(B\vert A, C)$.

Sovelletaan ylläolevaan kaavaan Markov-oletusta, että nykyinen tila riippuu vain edellisestä tilasta, muttei sitä aikaisemmista:

$$P(\mathbf S ~\vert~ q_0=S_2) = P(q_1=S_3 ~\vert~ q_0=S_2) \cdot P(q_2=S_2 ~\vert~ q_1=S_3)$$

$$\cdot P(q_3=S_1 ~\vert~ q_2=S_2) \cdot P(q_4=S_1 ~\vert~ q_3=S_1)$$

$$\cdot P(q_5=S_1 ~\vert~ q_4=S_1)$$

Tämä vastaa taulukoituja kertoimia $a_{ij}$:

$$P(\mathbf S ~\vert~ q_0=S_2) = a_{23} \cdot a_{32} \cdot a_{21} \cdot a_{11} \cdot a_{11}$$

$$= 0.1 \cdot 0.3 \cdot 0.4 \cdot 0.8 \cdot 0.8$$

$$= 0.0077$$

c)

Oletusarvo sille, kuinka kauan tilassa pysytään on

$$E(x) = \int x P(x) dx$$

$$= \sum_{n=1}^\infty n a_{ii}^n (1-a_{ii})$$

$$= (1-a_{ii}) \frac{a_{ii}}{(1-a_{ii})^2}$$

$$= \frac{a_{ii}}{1-a_{ii}}$$

Aurinkoisen päivän tapauksessa $a_{11}=0.8$ eli saadaan $\frac{0.8}{0.2} = 4$ päivää. Tämä siis oli oletusarvo sille, kuinka kauan tilassa pysytään, eli mehän olimme ensimmäisenä päivänä jo valmiiksi aurinkoisessa tilassa ja lopullinen vastaus on $4+1=5$ päivää.

2.

a) Tässä tehtävässä siis halutaa laskea tilan $S_i$ todennäköisyys kolmantena päivänä kun tiedetään, että lähtöpäivänä oli aurinkoista ja seuraavan kolmen päivän lämpötilat $\mathbf X = ( x_1, x_2, x_3) = (7^\circ C, 3^\circ C, -8^\circ C)$. Merkitään kaikkia malliin liittyviä parametrejä $\lambda=\{ \mathbf A , b_i(x) \}$.

$$P (q_3=S_i ~\vert~ q_0=S_1, x_1, x_2, x_3, \lambda )$$

$$= \frac{P (q_3=S_i, x_1, x_2, x_3 ~\vert~ q_0=S_1, \lambda)} {P (x_1, x_2, x_3 ~\vert~ q_0=S_1, \lambda)}$$

$$= \frac{P (q_3=S_i, x_1, x_2, x_3 ~\vert~ q_0=S_1, \lambda)} {\sum_{j=1}^3 P (q_3=S_j,x_1, x_2, x_3 ~\vert~ q_0=S_1, \lambda)}$$

Ylläolevan yhtälön pyörittämiseen käytettiin ensiksi todennäköisyyslaskun kaavaa $P(A\vert B,C)=\frac{P(A,B\vert C)}{P(B\vert C)}$. Sitten huomattiin että $P(A)=\sum_B P(A,B)$. Edellisen yhtälön nimittäjässä ja osoittajassa on samankaltainen termi. Kevennetään hieman merkintöjä ja esitetään sama asia funktion $\alpha_t(i)$ avulla:

$$P (q_3=S_i ~\vert~ q_0=S_1, x_1, x_2, x_3, \lambda ) = \frac{\alpha_3(i)}{\sum_{j=1}^3 \alpha_3(j)}$$

Tarkastellaanpa, miten tämä eteenpäin-todennäköisyys $\alpha_t(i)$ oikein voidaan laskea.

Lähtöpäivä

$\parbox{.65\linewidth}{ Tiedetään, että lähtöpäivänä oli aurinkoista... ...ray*} \alpha_0(1)&=&1\\ \alpha_0(2)&=&0\\ \alpha_0(3)&=&0 \end{eqnarray*}}$ $\parbox{.3\linewidth}{ \epsfig{file=forward1.eps,clip=,} \par \textit{Eteenpäin-algoritmin hilan alustus} }$

Ensimmäinen päivä

$\parbox{.65\linewidth}{ Edellisenä päivänä oli aurinkoista ja tänään... ...)&=&a_{13} \cdot b_3(x\ge5^\circ C) = 0.05\cdot 0.3 = 0.015\\ \end{eqnarray*}}$ $\parbox{.3\linewidth}{ \epsfig{file=forward2.eps,clip=,} \par \textit{Hila ensimmäisen päivän jälkeen} }$ Toinen päivä

$\parbox{.65\linewidth}{ Nyt emme tiedä, minkälainen sää edellisenä p... ...! 0.4 \! \cdot \! 0.015)\cdot 0.4 \\ &=& 6.000\cdot 10^{-4} \end{eqnarray*}}$ $\parbox{.3\linewidth}{ \epsfig{file=forward3.eps,clip=,} \textit{\mbox{Hila} toisen päivän jälkeen} }$

Kolmas päivä

$\parbox{.65\linewidth}{ Jatketaan jo tutulla tavalla eteenpäin. $x_3... ...dot 6.000\cdot 10^{-4} )\cdot 0.3 \\ &=& 9.4387\cdot 10^{-4} \end{eqnarray*}}$ $\parbox{.3\linewidth}{ \epsfig{file=forward4.eps,clip=} \par \textit{Hila viimeisenä päivänä} }$

Nyt olemme saaneet lasketuksi tehtävän ratkaisuun tarvittavat suureet. Sijoitetaan luvut kaavaan:

$$P (q_3=S_1 ~\vert~ q_0=S_1, x_1, x_2, x_3, \lambda ) = \frac{\alpha_3(1)}{\sum_{i=j}^3 \alpha_3(j)}$$

$$= \frac{1.2144 \cdot 10^{-2}}{1.2144\cdot 10^{-2} + 1.4149\cdot 10^{-3} + 9.4387\cdot 10^{-4} }$$

$$= 0.8874$$

Palatessa on siis 89 % todennäköisyydellä aurinkoista. Samalla tavalla voidaan laskea pilvisen sään todennäköisyys 10 % ja sateisen sään todennäköisyys 1 %.

b) Halusimme vielä arvata, mikä oli todennäköisin sääsekvenssi poissa ollessamme. Tämän voimme hoitaa Viterbi-algoritmilla, joka on hyvin samankaltainen eteenpäin-algoritmin kanssa. Nyt vain joka tilassa lasketaan todennäköisyys parhaan reitin kautta sen sijaan että summattaisiin kaikkien reittejen yli. Viterbi: Lähtöpäivä

$\parbox{.65\linewidth}{ Alustetaan hila samalla tavalla kuin eteenpä... ...ray*} \delta_0(1)&=&1\\ \delta_0(2)&=&0\\ \delta_0(3)&=&0 \end{eqnarray*}}$ $\parbox{.3\linewidth}{ \epsfig{file=viterbi1.eps,clip=,} \par \textit{Viterbi-algoritmin hilan alustus} }$

Viterbi: Ensimmäinen päivä

$\parbox{.65\linewidth}{ Paras polku kuhunkin tilaan tulee aurinkoise... ...0.015\\ \psi_1(1)&=&1\\ \psi_1(2)&=&1\\ \psi_1(3)&=&1\\ \end{eqnarray*}}$ $\parbox{.3\linewidth}{ \epsfig{file=viterbi2.eps,clip=,} \par \textit{Viterbi-haku ensimmäisen päivän jälkeen} }$Viterbi: Toinen päivä

$\parbox{.65\linewidth}{ Valitaan tilaan tulevasta reitistä todennäkö... ...j1} b_1(-5^\circ C \!\le\! x \!\le\! 5^\circ C)) \\ &=& 1 \\ \end{eqnarray*}}$

$\parbox{.65\linewidth}{ \begin{eqnarray*} \delta_2(2)&=& \max_j ~ (... ...a_{j3} b_2(-5^\circ C \!\le\! x \!\le\! 5^\circ C)) \\ &=& 3 \end{eqnarray*}}$ $\parbox{.3\linewidth}{ \epsfig{file=viterbi3.eps,clip=,} \textit{\mbox{Hila} toisen päivän jälkeen} }$Laskettaessa $\psi_2(3)$ huomataan, että kahdesta paikkaa (tilat 1 ja 3) päästään yhtä todennäköisesti tilaan 3. Tässä tapauksessa paras paluureitti ratkaistiin arpomalla näiden kahden välillä ja tulokseksi saatiin 3.

Viterbi: Kolmas päivä

$\parbox{.65\linewidth}{ Valitaan tilaan tulevasta reitistä todennäkö... ...ax}_j ( \delta_2(j)\cdot a_{j1} b_1(x \le 5^\circ C)) = 2 \\ \end{eqnarray*}}$

$\parbox{.65\linewidth}{ \begin{eqnarray*} \delta_3(2)&=& \max_j ~ (... ...j ( \delta_1(j)\cdot a_{j3} b_2(x \!\le\! -5^\circ C)) = 2 \\ \end{eqnarray*}}$ $\parbox{.3\linewidth}{ \epsfig{file=viterbi4.eps,clip=,} \par \textit{Viterbi-haun hila viimeisenä päivänä} }$Valmiista hilasta voidaan hakea todennäköisin tilasekvenssi: aloitetaan kaikkein todennäköisimmästä lopputilasta ja seurataan nuolia alkuun päin. Nyt siis näyttäisi siltä, että aurinkoisen lähtöpäivän jälkeen Turussa on ollut aurinkoista, pilvistä ja taasen aurinkoista.

Yhteenveto: Mitä eroa eteenpäin-algoritmilla ja Viterbi-haulla

Eteenpäin-algoritmi hakee oikean todennäköisyyden kullekin tilasekvenssille. Sen avulla ei kuitenkaan pysty hakemaan parasta polkua hilasta.

Viterbi-haulla tilatodennäköisyydet ovat vain approksimaatioita. Tätä algorimia kuitenkin käytetään paljon juuri sen takia, että sillä pysytytään löytämään paras polku.

Laskennallisesti algoritmit ovat yhtä raskaita, eteenpäin-algoritmin summaus on vain Viterbi-haussa vaihtunut maksimoinniksi.