概率计算问题

已知模型λ和观测序列O，求对给定观测序列条件概率P（I|O）最大的状态序列。即给定观测序列，求最有可能的对应的状态序列。

解决算法

近似算法

近似算法的核心思想是在每个时刻t选择在该时刻最有可能出现的状态 i_t*，从而得到一个近似状态序列。

具体算法流程如下：
给定隐马尔可夫模型λ和观测序列O，在时刻t处于状态qi的概率为：（详见向前向后算法）

在每一时刻t最有可能的状态 i_t* 是:

从而得到状态序列 I*：

这种算法的优点是算法简单易理解。
缺点是预测的序列可能有实际不发生的部分，即有可能出现转移概率为0的相邻状态，没法保证整体上的状态序列是最有可能的。该算法每次都是求解局部最优（贪心原则），不能保证全局最优。

Viterbi算法（维特比算法）

维特比算法通过动态规划求概率最大的路径（最优路径），这时每一条路径即对应着一个状态序列。
最优路径的特性：如果最优路径在时刻t通过结点i_t，那么最优路径中从结点i_t到最终结点i_T的部分路径是所有可能从i_t到i_T路径中最优的（同时从i₁到i_t的路径也是最优的）。

维特比算法从时刻t=1开始，递推地计算在时刻t状态为i的各条部分路径的最大概率，直到得到时刻t=T状态为i的各条路径的最大概率，我们用一个变量来记录到达最优路径的上一个结点的状态。

所以我们首先确定t=T时刻的状态值，然后根据到达该状态的上一个结点状态来递推到 i_T-1* ,…,i₁*

首先定义两个变量δ和ψ，定义在时刻t状态为i的所有单个路径(i₁,i₂,…,i_t)中概率最大值为:

由定义可得δ的递推公式：

定义在时刻t状态为i的所有单个路径(i₁,i₂,…,i_t-1,i)中概率最大的路径的第t−1个结点为:

具体流程如下：

1. 计算初值:

2. 递推计算t=2,3,···,T：

3. 在t=T时，终止递归：

4. 最终路径回溯，对t=T-l,T-2,…,1，求得最优路径I*=(i₁* ,i₂* ,…,i_T*)

其中值得注意的是，ψ₁(i)=0是无用的，在前向递推到时刻T获得最大概率的同时也获得了最优的最终状态i_T*，回溯的过程只需要从T-1开始，不需要任何计算，因为 ψ中保存了到达当前最优路径状态的上一状态。

具体递归形式

给定状态数量N，观测数量M

1. 对于观测值o₁：状态a从1取到N，共N项
   P(观测1，状态a)=P(观测1->状态a) * P(状态a初始概率)
   =发射矩阵中状态a观测为o₁的概率 * 初始概率矩阵中初始状态为a的概率

2. 对于观测值o₂：状态b从1取到N，共N项
   P(观测2，状态b)=max{ P(观测1，状态a) * P(状态a->状态b)，…共N项 } * P(观测2->状态b)
   =max{上一步N个P(观测1，状态a) * 转移矩阵中每一个状态a对应转移到状态b的概率} * 发射矩阵中状态b观测为观测2的概率

…

3. 对于观测值o_s：状态m从1取到N，共N项
   P(观测s，状态t)=max{ P(观测s-1，状态m) * P(状态m->状态t)，共N项}*P(观测s->状态t)
   =max{上一步N个P(观测s-1，状态m) * 转移矩阵中每一个状态m对应转移到状态t的概率} * 发射矩阵中状态t观测为观测s的概率

4. 设s已经是最后一个观测值，从所有概率值中选出最大的那个P（观测s，状态t），则状态t就是我们的观测s的最优状态。在每一步时记录了取得的max值时的P（观测s-1，状态m）的状态m，通过回溯从最后一个观测值开始得到每一个观测值的最优状态。最后得到一个和观测序列对应的完整的状态序列。

具体应用

问题描述

假设已知模型 λ ：
状态集合 S：健康，发烧；
可观测集合 O：正常、冷、头晕；
初始概率的状态矩阵 π：

转移矩阵 A：

观测状态转移概率矩阵（发射矩阵）B

已知：观测序列 O ：正常，冷，头晕

问：在该模型 λ 下，求这个人这三天最有可能的状态序列？

问题分析

1. 第一天：对第一个状态：正常
   P(第一天正常，第一天健康)=P₁(S₁)=π₁ * b₁(o₁)=0.6 * 0.5=0.3
   P(第一天正常，第一天发烧)=P₁(S₂)=π₁ * b₂(o₁)=0.4 * 0.1=0.04
   记录每个概率P取的状态，P(第一天正常，第一天健康)取的是健康；P(第一天正常，第一天发烧)取的是发烧。

2. 第二天：对第二个状态：冷
   P(第二天冷,第二天健康)=P₂(S₁)=max{ P₁(S₁) * a₁₁，P₁(S₂) * a₂₁} * b₁(o₂)
   =max{0.3 * 0.7,0.04 * 0.4} * 0.4=0.084
   P(第二天冷,第二天发烧)=P₂(S₂)=max{ P₁(S₁)) * a₁₂，P₁(S₂) * a₂₂} * b₁(o₂)
   =max{0.3 * 0.3,0.04 * 0.6} * 0.3=0.027
   记录每个P中max取的上一次的概率，P(第二天冷，第二天健康)取的是P(第一天正常，第一天健康)；P(第二天冷,第二天发烧)取的是P(第一天正常，第一天健康)。

3. 第三天：对第二个状态：头晕
   P(第三天头晕，第三天健康)=P₃(S₁)=max{P₂(S₁) * a₁₁，P₂(S₂) * a₂₁} * b₁(o₃)
   =max{0.0840.7,0.0270.4}*0.1=0.00588
   P(第三天头晕，第三天发烧)=P₃(S₁)=max{P₂(S₁) * a₁₂，P₂(S₂) * a₂₂} * b₁(o₃)
   =max{0.084 * 0.3,0.027 * 0.6} * 0.6=0.01512
   记录每个P中max取的上一次的概率，P(第三天头晕，第三天健康)取的是P(第二天冷，第二天健康)；P(第三天头晕，第三天发烧)取的是P(第二天冷，第二天健康)。

4. 回溯:
   最后一个状态最大概率是P（第三天头晕，第三天发烧）= 0.01512，记录对应状态是发烧。max中取的是P（第二天冷，第二天健康）。即倒数第二个观测取的状态是健康。P（第二天冷，第二天健康）max中取的是P（第一天正常，第一天健康），所以第一个观测取的状态是健康。
   所以最终的最优状态序列为:健康、健康、发烧。

参考文献

• https://blog.csdn.net/zgcr654321/article/details/92639420
• https://zhuanlan.zhihu.com/p/95986693
• https://www.cnblogs.com/jiangxinyang/p/9279711.html