T-61.281 Luonnollisen kielen tilastollinen käsittely
Vastaukset 6, ti 2.3.2004, 8:30-10:00 Markov-ketjut ja kätketyt Markov-mallit, Versio 1.0

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

Kuva: Säätila Markov-ketjuna
\begin{figure}\centering\epsfig{file=Turku-Markov.eps,width=0.4\linewidth}\end{figure}

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ä
$\displaystyle P(\mathbf S ~\vert~ q_0=S_2)$ $\displaystyle =$ $\displaystyle 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)$  
  $\displaystyle =$ $\displaystyle 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)$  
    $\displaystyle \cdot P(q_3=S_1 ~\vert~ q_0=S_2, q_1=S_3, q_2=S_2)$  
    $\displaystyle \cdot P(q_4=S_1 ~\vert~ q_0=S_2, q_1=S_3, q_2=S_2, q_3=S_1)$  
    $\displaystyle \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:

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

Tämä vastaa taulukoituja kertoimia $ a_{ij}$:
$\displaystyle P(\mathbf S ~\vert~ q_0=S_2)$ $\displaystyle =$ $\displaystyle a_{23} \cdot a_{32} \cdot a_{21} \cdot
a_{11} \cdot a_{11}$  
  $\displaystyle =$ $\displaystyle 0.1 \cdot 0.3 \cdot 0.4 \cdot 0.8 \cdot 0.8$  
  $\displaystyle =$ $\displaystyle 0.0077$  

c)
Oletusarvo sille, kuinka kauan tilassa pysytään on
$\displaystyle E(x)$ $\displaystyle =$ $\displaystyle \int x P(x) dx$  
  $\displaystyle =$ $\displaystyle \sum_{n=1}^\infty n a_{ii}^n (1-a_{ii})$  
  $\displaystyle =$ $\displaystyle (1-a_{ii}) \frac{a_{ii}}{(1-a_{ii})^2}$  
  $\displaystyle =$ $\displaystyle \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) \}$.
    $\displaystyle P (q_3=S_i ~\vert~ q_0=S_1, x_1, x_2, x_3, \lambda )$  
  $\displaystyle =$ $\displaystyle \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)}$  
  $\displaystyle =$ $\displaystyle \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ällön nimittäjässä ja osoittajassa on samankaltainen termi. Kevennetään hieman merkintöjä ja esitetään sama asia funktion $ \alpha_t(i)$ avulla:


$\displaystyle P (q_3=S_i ~\vert~ q_0=S_1, x_1, x_2, x_3, \lambda )$ $\displaystyle =$ $\displaystyle \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ä

$\textstyle \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*}}$ $\textstyle \parbox{.3\linewidth}{
\epsfig{file=forward1.eps,clip=,}
\par
\textit{Eteenpäin-algoritmin hilan alustus}
}$

Ensimmäinen päivä

$\textstyle \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*}}$ $\textstyle \parbox{.3\linewidth}{
\epsfig{file=forward2.eps,clip=,}
\par
\textit{Hila ensimmäisen päivän jälkeen}
}$ Toinen päivä

$\textstyle \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*}}$ $\textstyle \parbox{.3\linewidth}{
\epsfig{file=forward3.eps,clip=,}
\textit{\mbox{Hila} toisen päivän jälkeen}
}$

Kolmas päivä

$\textstyle \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*}}$ $\textstyle \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:

$\displaystyle P (q_3=S_1 ~\vert~ q_0=S_1, x_1, x_2, x_3, \lambda )$ $\displaystyle =$ $\displaystyle \frac{\alpha_3(1)}{\sum_{i=j}^3 \alpha_3(j)}$  
  $\displaystyle =$ $\displaystyle \frac{1.2144 \cdot 10^{-2}}{1.2144\cdot 10^{-2} + 1.4149\cdot 10^{-3}
+ 9.4387\cdot 10^{-4} }$  
  $\displaystyle =$ $\displaystyle 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ä

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

Viterbi: Ensimmäinen päivä

$\textstyle \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*}}$ $\textstyle \parbox{.3\linewidth}{
\epsfig{file=viterbi2.eps,clip=,}
\par
\textit{Viterbi-haku ensimmäisen päivän jälkeen}
}$Viterbi: Toinen päivä

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

$\textstyle \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*}}$ $\textstyle \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ä

$\textstyle \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*}}$

$\textstyle \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*}}$ $\textstyle \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.



vsiivola@cis.hut.fi