标签：规则   iter   子序列   --   条件   其他   简单   https   马尔科夫   

【ML-13-1】隐马尔科夫模型HMM

【ML-13-2】隐马尔科夫模型ＨＭＭ--前向后向算法

【ML-13-3】隐马尔科夫模型ＨＭＭ--Baum-Welch（鲍姆-韦尔奇）

【ML-13-4】隐马尔科夫模型ＨＭＭ--预测问题Viterbi（维特比）算法 

目录

1. 基础--HMM常用概率的计算
2. HMM最可能隐藏状态序列近似算法
3. Viterbi（维特比）算法
4. Viterbi（维特比）算法举例

HMM模型最后一个问题的求解：求给定观测序列条件下，最可能出现的对应的隐藏状态序列。即给定模型λ=(A,B,π)和观测序列Q={q1,q2,...,qT}，求给定观测序列条件概率P(I|Q，λ)最大的隐含状态序列 I。在阅读本篇前，建议先阅读这个系列的第一篇以熟悉HMM模型。

HMM模型的解码问题最常用的算法是维特比Viterbi（维特比）算法，当然也有其他的算法可以求解这个问题。同时维特比算法是一个通用的求序列最短路径的动态规划算法，也可以用于很多其他问题，比如文本挖掘的分词原理中单独用维特比算法来做分词。

　　本文关注于用维特比算法来解码HMM的的最可能隐藏状态序列。

一、基础--HMM常用概率的计算

　利用前向概率和后向概率，我们可以计算出HMM中单个状态和两个状态的概率公式。

1.1 单个状态的概率

求给定模型λ和观测序列Q的情况下，在时刻t处于状态si的概率，记做：

单个状态概率的意义主要是用于判断在每个时刻最可能存在的状态，从而可以得到一个状态序列作为最终的预测结果。

利用前向概率和后向概率的定义可知：

由上面两个表达式可知：

1.2 两个状态的联合概率

求给定模型λ和观测序列Q的情况下，在时刻t处于状态si并时刻t+1处于状态sj概率，记做：

1.3 上述两种求和可以得到：

二、HMM最可能隐藏状态序列近似算法　　

在HMM模型的解码问题中，给定模型λ=(A,B,Π)和观测序列，求给定观测序列Q条件下，最可能出现的对应的状态序列I={i1,i2,...iT},即P(I|Q)要最大化。直接在每个时刻t时候最优可能的状态作为最终的预测状态，使用下列公式计算概率值：

只要求得满足使得上式概率最大的值，可以通过前向和后向求得。

近似算法很简单，但是却不能保证预测的状态序列是整体是最可能的状态序列，因为预测的状态序列中某些相邻的隐藏状态可能存在转移概率为0的情况。

　 而维特比算法可以将HMM的状态序列作为一个整体来考虑，避免近似算法的问题，下面我们来看看维特比算法进行HMM解码的方法。

三、Viterbi（维特比）算法

Viterbi算法实际是用动态规划的思路求解HMM预测问题，求出概率最大的"路径"，每条"路径"对应一个状态序列：

时刻t隐藏状态为i所有可能的状态转移路径i1,i2,...it中的概率最大值。记为δt(i):

由δt(i)的定义可以得到δ的递推表达式：

计算时刻T最大的δT(i),即为最可能隐藏状态序列出现的概率。

使得上式最大后，最终得到最有可能的隐藏状态序列I∗={i∗1,i∗2,...i∗T}

四、Viterbi（维特比）算法举例

4.1 例题

假设有三个盒子，编号为1,2,3；每个盒子都装有黑白两种颜色的小球，球的比例如下：

按照下列规则的方式进行有放回的抽取小球，得到球颜色的观测序列：

1. 按照π的概率选择一个盒子，从盒子中随机抽取出一个小球，记录颜色后，放回盒子中；
2. 按照某种条件概率选择新的盒子，重复该操作；
3. 最终得到观测序列："白黑白白黑

• 状态集合：S={盒子1，盒子2，盒子3}
• 观测集合：O={白，黑}
• 状态序列和观测序列的长度T=5
• 初始概率分布π
• 状态转移概率矩阵A
• 观测概率矩阵B

在给定参数π、A、B的时候，得到观测序列为"白黑白白黑"，求出最优的隐藏状态序列。

4.2 计算过程

最终盒子序列为: (2, 3, 2, 2, 3)

附件一：手写练习

【ML-13-4】隐马尔科夫模型ＨＭＭ--预测问题Viterbi（维特比）算法

标签：规则   iter   子序列   --   条件   其他   简单   https   马尔科夫   

原文地址：https://www.cnblogs.com/yifanrensheng/p/12684738.html