python专题深度学习神经网络 python算法进阶

HMM

2021-04-27 本文已影响0人三方斜阳

1. 什么样的问题需要HMM模型

使用HMM模型时的问题一般有这两个特征：

１）问题是基于序列的，比如时间序列，或者状态序列。

２）问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。

2. 马尔科夫模型的两个假设

1）独立输出假设：每个时刻的输出只与当前状态有关

2）马尔科夫假设：输出与前一个时刻和当前时刻有关

3. HMM定义：

Q：所有可能的隐藏状态集合

$Q=(q_{1} ,q_{2} ,...,q_{N} )$

V: 所有可能的观测状态的集合

$V= ( v_{1} ,v_{2} ,...,v_{M} )$

N是可能的隐藏状态数，M是所有的可能的观察状态数,对于从盒子中取出小球来说，N是盒子的个数，M是小球的颜色种类数目

A ：状态转移矩阵：实际上每个状态指的是每个时刻，也就是从哪个盒子，因为每个时刻对应取一个盒子

$A=[a_{ij} ]N*N$

$a_{ij}=P(q_{t+1}=j| q_{t}=i)$

B：观测状态矩阵：B是输出符号的概率分布， $b_{j}(K)$ 表示在状态 j 时输出状态为 $v_{K}$ 的概率

$b_{j}(K)=P(v_{K}|j)$

$\Pi$ ：初始时刻状态分布：表示时刻 1 选择某个状态的概率，比如初始时刻从第一个盒子拿球的概率 p1，从第二个盒子拿球的概率 p2，从第三个盒子拿球的概率 p3;

$\pi (i)=P(q_{1}=i )$

一个HMM模型，由初始隐藏状态分布 $\Pi$ ，状态转移矩阵 $A$ ，观测状态矩阵 $B$ 决定

三个概率矩阵：

1. 状态转移概率矩阵

2. 发射概率矩阵(观测状态矩阵)

3. 初始状态分布

两个序列：

1. 观察序列

2. 状态序列

3. 马尔可夫模型在应用过程中有 3 个基本问题

1. 概率计算问题。给定模型 λ=(A,B,π) 和观测序列 O={o1,o2,⋯,oT}，计算在模型 λ 下观测序列 O 出现的概率 P(O|λ)。

2. 学习问题。已知观测序列 O={o1,o2,⋯,oT}，估计模型 λ=(A,B,π) 参数，使得在该模型下观测序列概率 P(X|λ) 最大。即用极大似然估计的方法估计参数。

3. 预测问题，也称为解码（decoding）问题。已知模型 λ=(A,B,π) 和观测序列 O={o1,o2,⋯,oT}，求对给定观测序列条件概率 P(I|O) 最大的状态序列 I={i1,i2,⋯,iT}。即给定观测序列，求最有可能的对应的状态序列。这个问题的求解需要用到基于动态规划的维特比算法。

4. 盒子与球的实例

假设有3个盒子，每个盒子里都有红色和白色两种球，这三个盒子里球的数量分别是：

所以观测状态矩阵 B：

N*M 3*2

开始的时候，从第一个盒子抽球的概率是0.2，从第二个盒子抽球的概率是0.4，从第三个盒子抽球的概率是0.4。以这个概率抽一次球后，将球放回。然后从当前盒子转移到下一个盒子进行抽球。

所以初始状态分布： $\Pi =(0.2,0.4,0.4)T$

规则是：如果当前抽球的盒子是第一个盒子，则以0.5的概率仍然留在第一个盒子继续抽球，以0.2的概率去第二个盒子抽球，以0.3的概率去第三个盒子抽球。如果当前抽球的盒子是第二个盒子，则以0.5的概率仍然留在第二个盒子继续抽球，以0.3的概率去第一个盒子抽球，以0.2的概率去第三个盒子抽球。如果当前抽球的盒子是第三个盒子，则以0.5的概率仍然留在第三个盒子继续抽球，以0.2的概率去第一个盒子抽球，以0.3的概率去第二个盒子抽球。如此下去，直到重复三次，得到一个球的颜色的观测序列: O={红，白，红}

所以状态转移矩阵A：

N*N

那么现在的问题就是已知观测序列为：O={红，白，红} 求得到这个观测序列的概率值

5. 前向算法：

当然第一反应可以暴力求解，但是时间复杂度太高，所以有前向后向算法,

前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。

在前向算法中，通过定义“前向概率”来定义动态规划的这个局部状态。

前向概率 $\alpha _{t}(i)$ ：

给定模型 $\lambda$ ，时刻 $t$ ，处在状态 $i$ (哪个盒子)，且部分观察序列为 $o_{1} ,o_{2} ....o_{t}$ 的概率

定义时刻 $t$ 时候隐藏状态 $q_{i}$ ,观测序列为 $o_{1} ,o_{2} ....o_{t}$ ，的概率

若 $\alpha _{t}(i)$ 已知， $(1\leq i\leq N)$ )

$\alpha _{t+1}(i) =[\sum_{i=1}^N \alpha _{t}(i)\alpha _{ij} ]b_{j} O_{t+1}$ (迭代计算)

6. 维特比算法

$\delta _{t}(i)=maxP(q_{1}q_{2}...q_{t-1}q_{t} =i,o_{1},o_{2}...o_{t} |\lambda )$

$\delta _{t}(i)$ 的含义是，给定模型 $\lambda$ ，在时刻 $t$ 处于状态 $i$ ，观察到 $O_{1} ,O_{2} ,...,O_{t}$ 的最佳状态转换序列为 $q_{1} ,q_{2} ,...,q_{t}$ 的概率

$\delta _{1}(i) =\pi _{i} b_{i} (o_{1} ),1\leq i\leq N$

若 $\delta _{t}(i)$ 已知，如何计算： $\delta _{t+1}(i)$ ？

1）计算实例：

代码实现：

参考：

隐马尔可夫模型HMM - 知乎 (zhihu.com)

李航《统计机器学习》

上一篇下一篇

猜你喜欢

热点阅读