HMM轻松理解1

1.HMM解码问题 —最笨解法

如图&＃xff0c;已知了HMM的参数 θ (π, A, B) 和观测序列 X(x1,x2,x3,…xn)&＃xff0c;寻找最佳的状态序列 Z(z1,z2,z3,…,zn)

其中&＃xff1a;π 是初始状态概率向量&＃xff0c; A 是状态转移矩阵&＃xff0c; B 是观测概率矩阵
最笨的解法 &＃xff1a;求使 likelyhood 最大的状态序列
假设每个隐状态可取 {a, b, c}, 那么状态序列的组合就有 3^n 次方种&＃xff0c;假设其中 3 种 (只考虑 n&＃61;5 时)为&＃xff1a;
Z1 &＃61; (a, b, b, c, a)
Z2 &＃61; (b, c, a, b, c)
Z3 &＃61; (a, a, c, b ,b)
那么计算 Zi的 likelyhood 为P(Zi)&＃xff1a;&＃xff08;概率值包括两部分&＃xff0c;一部分是转移概率&＃xff0c;一部分是观测概率&＃xff09;
P(Z1) &＃61; p(a) * p(b|a) * p(b | b) * p(c|b ) * p(a |c) * p( x1 | a) * p(x2|b) * p(x3 | b) *p(x4|c) *p(x5| a)
P(Z1) &＃61; p(b) * p(c|b) * p(a | c) * p(b|a ) * p(c |b) * p( x1 | b) * p(x2| c) * p(x3 | a) *p(x4| b) *p(x5| c)
P(Z1) &＃61; p(a) * p(a|a) * p(c | a) * p(b|c ) * p(b |b) * p( x1 | a) * p(x2| a) * p(x3 | c) *p(x4| b) *p(x5 | b)
由于 θ (π, A, B)都是已知的&＃xff0c;所以上式中所有概率都可以计算出来&＃xff1b;
我们只需要选择使 P(Zi) 最大的 Zi 就行了&＃xff0c;但这是指数级复杂度&＃xff0c;不可能求解出来&＃xff0c;所以使用威特比算法

2.HMM的解码问题 —维特比算法

2.1 维特比算法条件

维特比算法只适用于链式结构&＃xff0c;即当前的隐藏状态只依赖与上一时刻的隐藏状态&＃xff0c;而不能依赖于 上两个隐藏状态或下一个隐藏状态等…
维特比算法开始前都会画一个图

图中&＃xff1a;Zi 是隐藏状态&＃xff0c;m 是状态的所有可能取值 类似于上文提到的{ a, b , c …}

2.2 维特比算法

定义&＃xff1a;δ_k(i) 是到 第 K 时刻&＃xff0c;状态为 i 的最佳路径的score&＃xff0c;score值就是 likelyhood值&＃xff0c;只不过会取 log &＃xff0c;将乘法变成加法&＃xff0c; 避免计算机溢出。
我们现在要求&＃xff1a; δ_k&＃43;1(i) &＃61; &＃xff1f;
如图所示&＃xff1a;假设 绿色的点 为δ_k&＃43;1(j)&＃xff0c;那么它有可能来自 δ_k(1)&＃xff0c; δ_k(2)&＃xff0c;δ_k(3)&＃xff0c;…δ_k(m)

所以

如何计算上面的式子呢&＃xff1f;
可以创建一个 M x N 列的表格&＃xff0c;M表示可能的状态取值&＃xff0c;N代表每一个时刻&＃xff1b;
然后一列一列的去填充这个表格&＃xff0c;表格中的第一列根据 π, B 的值来填充&＃xff0c;其他列的计算就要用到 π, A, B了。比如第一列第一个的值为&＃xff1a;

填充完表格之后&＃xff0c;找出最后一列最大值score对应的影藏状态&＃xff0c;然后从后往前推出其他隐藏状态&＃xff0c;因为我们在填充每一列时会记录当前值是由之前哪一条路径得来的。

3. HMM的 F/B算法

3.1 定义

F/B 算法&＃xff1a; Forward and Backward 算法
F &＃xff1a; Forward 算法
B &＃xff1a;Backward算法
F/B&＃xff1a; 目标是计算 P (Zk | X) &＃xff0c;即给定状态序列 X, 求 k 时刻处于隐藏状态Zk 的概率
F &＃xff1a;目标是计算联合概率 P( Zk, X1:k) &＃xff0c;即求 k 时刻处于隐藏状态Zk&＃xff0c;且 k 时刻之前的观测值为 X1,X2,X3,…,Xk
B&＃xff1a;目标是计算条件概率 p( Xk&＃43;1:n | Zk)&＃xff0c;即求 在k 时刻处于隐藏状态Zk 的条件下&＃xff0c;在k 时刻之后观测值为 Xk&＃43;1, Xk&＃43;2, Xk&＃43;3, …Xk&＃43;n 的概率
X1:k 表示 X1, X2, X3, …,Xk
Xk&＃43;1:n 表示 Xk&＃43;1, Xk&＃43;2, Xk&＃43;3,…, Xk&＃43;n

3.2 公式推导

引入&＃xff1a;马尔科夫假设

1. 齐次马尔科夫性假设&＃xff1a;即假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态&＃xff0c;与其他时刻的状态及观测无关&＃xff0c;也与时刻t无关&＃xff1b;
2. 观测独立性假设&＃xff1a;即假设任意时刻的观测只依赖于该时刻的隐藏状态&＃xff0c;与其他观测和隐藏状态无关

公式推导

上式只是计算了 P(Zk, X),若要计算 P(Zk | X) 还必须 进行归一化&＃xff0c;即

F/B 的作用&＃xff1a;

1. 估计模型参数

2. 判断两个图&＃xff08;或观测&＃xff09;之间是否发生突变&＃xff0c;一种方法计算两种图的相似度&＃xff0c;如果小于某个设定的阈值&＃xff0c;则认为这两张图发生了突变&＃xff0c;可用于风险控制。另一种方法是看隐状态&＃xff0c;假如隐状态可能取值 {0,1}, 正常的状态序列为 0 -->0 --> 0 --> …, 如果发生突变则会变为 0 --> 0—> 0 —> 1 —>0 ----> 0 …

4. Forward 算法

目的&＃xff1a;计算 P(Zk, X1:k) 概率
方法&＃xff1a;动态规划
idea&＃xff1a;构建一个概率&＃xff0c;使它包含 P(Zk, X1:k) 的子问题 P(Zk-1, X1:k-1) &＃xff0c;类似于下图

观测左右两边变量不一样&＃xff0c;左边没有Zk-1&＃xff0c;为了引入这个变量&＃xff0c;我们需要做边缘化处理&＃xff0c;也就是变成联合概率

我们要时刻记住这是一个动态规划的算法&＃xff0c;那么我们是要保留 P(Zk-1, X1:k-1) 这一项的&＃xff0c;所以在此基础上拆解联合概率分布
推导过程如下&＃xff1a;用到了马尔科夫的两个假设

动态规划必须有第一项才能迭代下去

5. backward算法

目标&＃xff1a; 计算条件概率 P( Xk&＃43;1:n | Zk)
方法&＃xff1a;动态规划
idea&＃xff1a;由于是后项&＃xff0c;子问题是 P( Xk&＃43;2:n | Zk&＃43;1&＃xff09;

观测左右两边变量不一样&＃xff0c;左边条件是Zk&＃xff0c;而右边是Zk&＃43;1&＃xff0c;为了引入这个变量&＃xff0c;我们需要做边缘化处理&＃xff0c;也就是变成联合概率

算法复杂度

因为Zk&＃43;1 有 m 个可能的取值&＃xff0c;∑ 相当于要循环 m 次&＃xff0c;而 &＃xff08;Zk&＃xff09;也有 m 种可能取值&＃xff1b;k 是某一时刻&＃xff0c;而要计算完整个序列&＃xff0c;长度是为 n 的&＃xff0c;所以复杂度为

前向算法与后向算法复杂度一样

通过F/B可以得到了 P(Zk | X)

如何基于 P(Zk | X ) 去估计HMM的参数 θ (π, A, B)&＃xff0c;请听下回分解- -