维特比算法(Viterbi Algorithm)

╰+攻爆jí腚メ 2022-07-20 12:12 150阅读 0赞

寻找最可能的隐藏状态序列 (Finding most probable sequence of hidden states)

对于一个特殊的隐马尔科夫模型(HMM)及一个相应的观察序列，我们常常希望能找到生成此序列最可能的隐藏状态序列。

**假设连续观察3天的海藻湿度为(Dry,Damp,Soggy),求这三天最可能的天气情况。**天气只有三类(Sunny,Cloudy,Rainy)，而且海藻湿度和天气有一定的关系。

已知：

1. 隐藏的状态：Sunny,Cloudy, Rainy;海藻湿度有四类\{Dry,Dryish, Damp,Soggy \}

2. 观察状态序列：\{Dry, Damp, Soggy \};

3. 初始状态序列：Sunny(0.63),Cloudy(0.17),Rainy(0.20);

4. 状态转移矩阵：

<table style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px"> 
 <tbody> 
 <tr> 
 <td> </td> 
 <td> Sunny </td> 
 <td> Cloudy </td> 
 <td> Rainy </td> 
 </tr> 
 <tr> 
 <td> Sunny </td> 
 <td> 0.5 </td> 
 <td> 0.375 </td> 
 <td> 0.125 </td> 
 </tr> 
 <tr> 
 <td> Cloudy </td> 
 <td> 0.25 </td> 
 <td> 0.125 </td> 
 <td> 0.625 </td> 
 </tr> 
 <tr> 
 <td> Rainy </td> 
 <td> 0.25 </td> 
 <td> 0.375 </td> 
 <td> 0.375 </td> 
 </tr> 
 </tbody> 
</table>

Cloudy(昨天)->Sunny(今天)的概率是0.25;

Sunny(昨天)->Rainy(今天)的概率是0.125.

5. 混淆矩阵（海藻湿度与天气的相关性）：

<table style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:26px"> 
 <tbody> 
 <tr> 
 <td> </td> 
 <td> Dry </td> 
 <td> Dryish </td> 
 <td> Damp </td> 
 <td> Soggy </td> 
 </tr> 
 <tr> 
 <td> Sunny </td> 
 <td> 0.6 </td> 
 <td> 0.2 </td> 
 <td> 0.15 </td> 
 <td> 0.05 </td> 
 </tr> 
 <tr> 
 <td> Cloudy </td> 
 <td> 0.25 </td> 
 <td> 0.25 </td> 
 <td> 0.25 </td> 
 <td> 0.25 </td> 
 </tr> 
 <tr> 
 <td> Rainy </td> 
 <td> 0.05 </td> 
 <td> 0.10 </td> 
 <td> 0.35 </td> 
 <td> 0.50 </td> 
 </tr> 
 </tbody> 
</table>

由HMM可知，Day2的天气仅取决于Day1；Day3的天气又只取决于Day2的天气。

**Day1由于是初始状态**，我们分别求

P(Day1-Sunny)=0.63\*0.6;  
  
P(Day1-Cloudy)=0.17\*0.25;  
  
P(Day1-Rain)=0.20\*0.05;  
  
Choose max\{ P(Day1-Sunny) , P(Day1-Cloudy),P(Day1-Rainy)\}, 得到P(Day1-Sunny)最大，得出第1天Sunny的概率最大。

**Day2的天气又取决于Day1的天气状况，同时也受Day2观察的海藻情况影响**。

P(Day2-Sunny)= max\{ P(Day1-Sunny)\*0.5, P(Day1-Cloudy)\*0.25,  P(Day1-Rainy)\*0.25\} \***0.15**;

P(Day2-Cloudy)= max\{ P(Day1-Sunny)\*0.375,  P(Day1-Cloudy)\*0.125, P(Day1-Rainy)\*0.625\} \***0.25**;

P(Day2-Rainy)= max\{ P(Day1-Sunny)\*0.125,  P(Day1-Cloudy)\*0.625 , P(Day1-Rainy)\*0.375\} \***0.35**;

Choosemax\{ P(Day2-Sunny) , P(Day2-Cloudy), P(Day2-Rainy)\},得到P(Day2-Rainy)最大，得出第2天Rainy的概率最大。

故\{Sunny,Rainy\}是前两天最大可能的天气序列。

**Day3的天气又取决于Day2的天气状况，同时也受Day3观察的海藻情况影响**。

P(Day3-Sunny)= max\{ P(Day2-Sunny)\*0.5, P(Day2-Cloudy)\*0.25,  P(Day2-Rainy)\*0.25\} \***0.05**;

P(Day3-Cloudy)= max\{ P(Day2-Sunny)\*0.375,  P(Day2-Cloudy)\*0.125, P(Day2-Rainy)\*0.625\} \***0.25**;

P(Day3-Rainy)= max\{ P(Day2-Sunny)\*0.125,  P(Day2-Cloudy)\*0.625, P(Day2-Rainy)\*0.375\} \***0. 05**;

Choosemax\{ P(Day3-Sunny) , P(Day3-Cloudy), P(Day3-Rainy)\},得到 P(Day3-Rainy)最大，得出第3天Rainy的概率最大。

**故\{Sunny,Rainy,Rainy\}是这三天最可能的天气序列。**