24-HMM-隐马尔科夫模型
文章目录1.背景1. 1 频率派1.2 贝叶斯派1.3 概率图模型1.背景HMM就是隐马尔科夫模型，全称 Hidden-Markov-Model .这个模型在以前的NLP问题占据非常重要的地位，可以作自然语言处理，语音识别等功能。在讲具体模型之前，我们应讲讲整个学科的背景。HMM隐马尔科夫模型从根本上来说是一种概率图模型。1. 1 频率派一开始我们知道，机器学习大致可以分为两派，频率派和贝叶斯派，
1.背景
HMM就是隐马尔科夫模型，全称 Hidden-Markov-Model .这个模型在以前的NLP问题占据非常重要的地位，可以作自然语言处理，语音识别等功能。在讲具体模型之前，我们应讲讲整个学科的背景。HMM隐马尔科夫模型从根本上来说是一种概率图模型。
1. 1 频率派
一开始我们知道，机器学习大致可以分为两派，频率派和贝叶斯派，频率派逐渐发展成为一门叫统计机器学习的学科。它的核心问题是优化问题。比如李航老师的统计学习方法这本书中大部分算法都是属于优化层面的算法模型。
- 定义模型 Model :比如： f ( w ) = w T x + b f(w)=w^Tx+b f(w)=wTx+b
- 策略：strategy：损失函数
- 算法：梯度下降GD,随机梯度下降SGD，牛顿法，拟牛顿法
1.2 贝叶斯派
贝叶斯派逐渐发展成为一门叫概率图模型的学科。它的核心是推断inference问题，主要是求后验概率P(Z|X)。以及求关于后验概率的期望和方法，从而引出了积分问题，为了求积分，我们用数值积分的方式求解，常见的方法有MCMC方法，MCMC方法的提出让贝叶斯派有了实际的意义，不仅仅体现在理论上。
1.3 概率图模型
概率图模型根据是否有向分为两类，有向模型是贝叶斯网络Byaesion-Network,无向模型是马尔科夫随机场或马尔科夫网络。对于概率图模型加上时间序列就叫做动态模型。动态模型中的样本之间不是独立同分布的(
X
i
之
间
不
是
i
i
d
的
X_i之间不是iid的
Xi之间不是iid的)
- 比如高斯混合模型中加上时间序列后就组成了动态模型系统。动态模型可以看作是横向的时间+纵向的混合模型；动态模型如果系统状态Z是离散的，我们称为HMM隐马尔科夫模型；如果Z是连续的线性关系，我们称为卡曼滤波模型，如果Z是连续的非线性关心，我们称为粒子滤波模型；
1.4 HMM模型
1.4.1 HMM 一个模型参数
隐马尔科夫模型如图所示，它的模型参数如下：
λ
=
[
π
,
A
,
B
]
(1)
\lambda=[\pi,A,B]\tag 1
λ=[π,A,B](1)
- π \pi π:初始的概率分布 init-prob-dist
- 状态转移矩阵 A = [ a i j ] , a i j = P ( i t + 1 = q j ∣ i t = q i ) A=[a_{ij}],a_{ij}=P(i_{t+1}=q_j|i_t=q_i) A=[aij],aij=P(it+1=qj∣it=qi)
- 发射矩阵 B = [ b j ( k ) ] = P ( o t = v k ∣ i t = q j ) B=[b_j(k)]=P(o_t=v_k|i_t=q_j) B=[bj(k)]=P(ot=vk∣it=qj)
- 观测变量用O表示： { o 1 , o 2 , . . . , o t , . . . } \{o_1,o_2,...,o_t,...\} {o1,o2,...,ot,...};观测变量值的集合用V表示： V = { v 1 , v 2 , . . . , v m } V=\{v_1,v_2,...,v_m\} V={v1,v2,...,vm}
- 状态变量用I表示： { i 1 , i 2 , . . . , i t , . . . . } \{i_1,i_2,...,i_t,....\} {i1,i2,...,it,....};随机变量[状态变量的取值]的集合用Q表示： Q = { q 1 , q 2 , . . . , q N } Q=\{q_1,q_2,...,q_N\} Q={q1,q2,...,qN}
- 状态转移矩阵 A = [ a i j ] , a i j = P ( i t + 1 = q j ∣ i t = q i ) A=[a_{ij}],a_{ij}=P(i_{t+1}=q_j|i_t=q_i) A=[aij],aij=P(it+1=qj∣it=qi)
- 发射矩阵
B
=
[
b
j
(
k
)
]
=
P
(
o
t
=
v
k
∣
i
t
=
q
j
)
B=[b_j(k)]=P(o_t=v_k|i_t=q_j)
B=[bj(k)]=P(ot=vk∣it=qj)
1.4.2 HMM 两个假设
- 齐次马尔科夫假设[无后效性]
P ( i t + 1 ∣ i t , i t + 1 , . . . , i 1 , o t , o t − 1 , . . . , o 1 ) = P ( i t + 1 ∣ i t ) (2) P(i_{t+1}|i_t,i_{t+1},...,i_1,o_t,o_{t-1},...,o_1)=P(i_{t+1}|i_t)\tag 2 P(it+1∣it,it+1,...,i1,ot,ot−1,...,o1)=P(it+1∣it)(2)
注：在给定当前时刻的时候，未来只依赖于现在，与过去无关。即英雄不问出处，未来只取决于现在 - 观测独立性假设
P ( o t ∣ i t , i t − 1 . . . , o t − 1 , . . . , o 1 ) = P ( o t ∣ i t ) (3) P(o_t|i_t,i_{t-1}...,o_{t-1},...,o_1)=P(o_t|i_t)\tag 3 P(ot∣it,it−1...,ot−1,...,o1)=P(ot∣it)(3)
1.4.3 HMM 三个问题
- Evaluation 问题
已 知 参 数 λ ， 求 解 P ( O ∣ λ ) 的 概 率 值 . 常 用 的 算 法 ： f o r w a r d − b a c k w a r d − a l g o r i t h m 已知参数\lambda，求解P(O|\lambda)的概率值.常用的算法：forward-backward-algorithm 已知参数λ，求解P(O∣λ)的概率值.常用的算法：forward−backward−algorithm - Learning 问题
求参数，参数估计问题，求解参数 λ \lambda λ,常用的算法：EM算法或Baum-Welch算法。
λ = arg max λ P ( O ∣ λ ) (4) \lambda=\mathop{\arg\max}\limits_{\lambda}P(O|\lambda)\tag 4 λ=λargmaxP(O∣λ)(4) - Decoding 问题
我们要找到一个序列i使得P(I|O)取得最大
I = arg max i P ( I ∣ O ) (5) I=\mathop{\arg\max}\limits_{i}P(I|O)\tag {5} I=iargmaxP(I∣O)(5)
预测：
P ( i t + 1 ∣ o 1 , o 2 , . . . , o t ) (6) P(i_{t+1}|o_1,o_2,...,o_t)\tag {6} P(it+1∣o1,o2,...,ot)(6)
滤波：
P ( i t ∣ o 1 , o 2 , . . . , o t ) (7) P(i_{t}|o_1,o_2,...,o_t)\tag {7} P(it∣o1,o2,...,ot)(7)
2.前向算法
前向算法主要是解决evaluation问题，主要是为了求解在参数
λ
\lambda
λ已知的情况下，
P
(
O
∣
λ
)
P(O|\lambda)
P(O∣λ)问题；
为了求解在已知参数
λ
\lambda
λ的情况下的观测变量O的概率问题，我们需要将状态变量I引入其中，即：
P
(
O
∣
λ
)
=
∑
I
P
(
I
,
O
∣
λ
)
=
∑
I
P
(
O
∣
I
,
λ
)
⋅
P
(
I
∣
λ
)
(8)
P(O|\lambda)=\sum_{I}P(I,O|\lambda)=\sum_{I}P(O|I,\lambda)·P(I|\lambda)\tag {8}
P(O∣λ)=I∑P(I,O∣λ)=I∑P(O∣I,λ)⋅P(I∣λ)(8)
-
P
(
I
∣
λ
)
P(I|\lambda)
P(I∣λ)
P ( I ∣ λ ) = P ( i 1 , i 2 , . . . i T ∣ λ ) = P ( i T ∣ i 1 , i 2 , . . . i T − 1 , λ ) ⋅ P ( i 1 , i 2 , . . . i T − 1 ∣ λ ) (9) P(I|\lambda)=P(i_1,i_2,...i_T|\lambda)=P(i_T|i_1,i_2,...i_{T-1},\lambda)·P(i_1,i_2,...i_{T-1}|\lambda)\tag {9} P(I∣λ)=P(i1,i2,...iT∣λ)=P(iT∣i1,i2,...iT−1,λ)⋅P(i1,i2,...iT−1∣λ)(9) - 由齐次马尔科夫假设可得：
P
(
i
T
∣
i
1
,
i
2
,
.
.
.
i
T
−
1
,
λ
)
=
P
(
i
T
∣
i
T
−
1
)
=
a
i
t
−
1
,
i
t
;
由
递
归
式
可
得
：
P(i_T|i_1,i_2,...i_{T-1},\lambda)=P(i_T|i_{T-1})=a_{i_{t-1},i_t};由递归式可得：
P(iT∣i1,i2,...iT−1,λ)=P(iT∣iT−1)=ait−1,it;由递归式可得：
P ( I ∣ λ ) = a i t − 1 , i t ⋅ a i t − 2 , i t − 1 ⋅ . . . . ⋅ a i 3 , i 2 ⋅ π 1 = π 1 ⋅ ∏ t = 2 T a i t − 1 i t (10) P(I|\lambda)=a_{i_{t-1},i_t}·a_{i_{t-2},i_{t-1}}·....·a_{i_3,i_2}·\pi_1=\pi_1·\prod_{t=2}^{T}a_{i_{t-1}i_{t}}\tag {10} P(I∣λ)=ait−1,it⋅ait−2,it−1⋅....⋅ai3,i2⋅π1=π1⋅t=2∏Tait−1it(10) -
P
(
O
∣
I
,
λ
)
P(O|I,\lambda)
P(O∣I,λ)
P ( O ∣ I , λ ) = ∏ t = 1 T b i t ( o t ) (11) P(O|I,\lambda)=\prod_{t=1}^{T}b_{i_t}(o_t)\tag {11} P(O∣I,λ)=t=1∏Tbit(ot)(11)
故可得：
P ( O ∣ λ ) = ∑ I π 1 ⋅ ∏ t = 2 T a i t − 1 i t ⋅ ∏ t = 1 T b i t ( o t ) = ∑ i 1 ∑ i 2 . . . ∑ i T π 1 ⋅ ∏ t = 2 T a i t − 1 i t ⋅ ∏ t = 1 T b i t ( o t ) (12) P(O|\lambda)=\sum_{I}\pi_1·\prod_{t=2}^{T}a_{i_{t-1}i_{t}}·\prod_{t=1}^{T}b_{i_t}(o_t)=\sum_{i_1}\sum_{i_2}...\sum_{i_T}\pi_1·\prod_{t=2}^{T}a_{i_{t-1}i_{t}}·\prod_{t=1}^{T}b_{i_t}(o_t)\tag {12} P(O∣λ)=I∑π1⋅t=2∏Tait−1it⋅t=1∏Tbit(ot)=i1∑i2∑...iT∑π1⋅t=2∏Tait−1it⋅t=1∏Tbit(ot)(12)
由上述公式可以看出，实在是太复杂了，想吐，复杂度 O ( N T ) O(N^T) O(NT)，为了解决上述问题，我们提出前向算法forward-algorithm
为了更好的表示前向算法，我们用
α
t
(
i
)
\alpha_t(i)
αt(i)这个符号记作相关概率：
α
t
(
i
)
=
P
(
o
1
,
o
2
,
.
.
.
,
o
t
,
i
t
=
q
i
∣
λ
)
(13)
\alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda)\tag {13}
αt(i)=P(o1,o2,...,ot,it=qi∣λ)(13)
由此可得：
α
T
(
i
)
=
P
(
o
1
,
o
2
,
.
.
.
,
o
T
,
i
t
=
q
i
∣
λ
)
=
P
(
O
,
i
t
=
q
i
∣
λ
)
(14)
\alpha_T(i)=P(o_1,o_2,...,o_T,i_t=q_i|\lambda)=P(O,i_t=q_i|\lambda)\tag {14}
αT(i)=P(o1,o2,...,oT,it=qi∣λ)=P(O,it=qi∣λ)(14)
所以目标概率
P
(
O
∣
λ
)
P(O|\lambda)
P(O∣λ)
P
(
O
∣
λ
)
=
∑
i
=
1
N
P
(
O
,
i
t
=
q
i
∣
λ
)
=
∑
i
=
1
N
α
T
(
i
)
(15)
P(O|\lambda)=\sum_{i=1}^N P(O,i_t=q_i|\lambda)=\sum_{i=1}^N \alpha_T(i)\tag {15}
P(O∣λ)=i=1∑NP(O,it=qi∣λ)=i=1∑NαT(i)(15)
我们希望的是找到
α
t
(
i
)
和
α
t
+
1
(
j
)
\alpha_t(i)和\alpha_{t+1}(j)
αt(i)和αt+1(j)的递推关系：
α
t
+
1
(
j
)
=
P
(
o
1
,
o
2
,
.
.
.
,
o
t
,
o
t
+
1
,
i
t
+
1
=
q
j
∣
λ
)
(16)
\alpha_{t+1}(j)=P(o_1,o_2,...,o_t,o_{t+1},i_{t+1}=q_{j}|\lambda)\tag {16}
αt+1(j)=P(o1,o2,...,ot,ot+1,it+1=qj∣λ)(16)
我们把
i
t
=
q
i
i_t=q_i
it=qi概率加入上式后并用求和来抵消：
α
t
+
1
(
j
)
=
∑
i
=
1
N
P
(
o
1
,
o
2
,
.
.
.
,
o
t
,
o
t
+
1
,
i
t
=
q
i
,
i
t
+
1
=
q
j
∣
λ
)
(17)
\alpha_{t+1}(j)=\sum_{i=1}^NP(o_1,o_2,...,o_t,o_{t+1},i_t=q_i,i_{t+1}=q_{j}|\lambda)\tag {17}
αt+1(j)=i=1∑NP(o1,o2,...,ot,ot+1,it=qi,it+1=qj∣λ)(17)
联合概率分解成条件概率积
α
t
+
1
(
j
)
=
∑
i
=
1
N
P
(
o
t
+
1
∣
o
1
,
o
2
,
.
.
.
,
o
t
,
i
t
=
q
i
,
i
t
+
1
=
q
j
,
λ
)
⋅
P
(
o
1
,
o
2
,
.
.
.
,
o
t
,
i
t
=
q
i
,
i
t
+
1
=
q
j
,
λ
)
(18)
\alpha_{t+1}(j)=\sum_{i=1}^NP(o_{t+1}|o_1,o_2,...,o_t,i_t=q_i,i_{t+1}=q_{j},\lambda)·P(o_1,o_2,...,o_t,i_t=q_i,i_{t+1}=q_{j},\lambda)\tag {18}
αt+1(j)=i=1∑NP(ot+1∣o1,o2,...,ot,it=qi,it+1=qj,λ)⋅P(o1,o2,...,ot,it=qi,it+1=qj,λ)(18)
- 由观测独立性假设可得： P ( o t + 1 ∣ o 1 , o 2 , . . . , o t , i t = q i , i t + 1 = q j , λ ) = P ( o t + 1 ∣ i t + 1 = q j ) = b j ( o t + 1 ) P(o_{t+1}|o_1,o_2,...,o_t,i_t=q_i,i_{t+1}=q_{j},\lambda)=P(o_{t+1}|i_{t+1}=q_j)=b_j(o_{t+1}) P(ot+1∣o1,o2,...,ot,it=qi,it+1=qj,λ)=P(ot+1∣it+1=qj)=bj(ot+1)
- 将 P ( o 1 , o 2 , . . . , o t , i t = q i , i t + 1 = q j , λ ) = P ( i t + 1 = q j ∣ o 1 , o 2 , . . . , o t , i t = q i , λ ) ⋅ P ( o 1 , o 2 , . . . , o t , i t = q i ∣ λ ) P(o_1,o_2,...,o_t,i_t=q_i,i_{t+1}=q_{j},\lambda)=P(i_{t+1}=q_{j}|o_1,o_2,...,o_t,i_t=q_i,\lambda)·P(o_1,o_2,...,o_t,i_t=q_i|\lambda) P(o1,o2,...,ot,it=qi,it+1=qj,λ)=P(it+1=qj∣o1,o2,...,ot,it=qi,λ)⋅P(o1,o2,...,ot,it=qi∣λ)
- 由于齐次马尔科夫假设可得: P ( i t + 1 = q j ∣ o 1 , o 2 , . . . , o t , i t = q i , λ ) = P ( i t + 1 = q j ∣ i t = q i , λ ) = a i j P(i_{t+1}=q_{j}|o_1,o_2,...,o_t,i_t=q_i,\lambda)=P(i_{t+1}=q_j|i_t=q_i,\lambda)=a_{ij} P(it+1=qj∣o1,o2,...,ot,it=qi,λ)=P(it+1=qj∣it=qi,λ)=aij
- 由定义可得：
α
t
(
i
)
=
P
(
o
1
,
o
2
,
.
.
.
,
o
t
,
i
t
=
q
i
∣
λ
)
\alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda)
αt(i)=P(o1,o2,...,ot,it=qi∣λ)
α t + 1 ( j ) = ∑ i = 1 N b j ( o t + 1 ) ⋅ a i j ⋅ α t ( i ) (19) \alpha_{t+1}(j)=\sum_{i=1}^Nb_j(o_{t+1})·a_{ij}·\alpha_t(i)\tag {19} αt+1(j)=i=1∑Nbj(ot+1)⋅aij⋅αt(i)(19)
3.后向算法
3.1 求出 P ( O ∣ λ ) 与 β 1 ( i ) 关 系 P(O|\lambda)与\beta_1(i)关系 P(O∣λ)与β1(i)关系
我们记：
β
t
(
i
)
\beta_t(i)
βt(i)如下：
β
t
(
i
)
=
P
(
o
t
+
1
,
o
t
+
2
,
.
.
.
,
o
T
∣
i
t
=
q
i
,
λ
)
(20)
\beta_t(i)=P(o_{t+1},o_{t+2},...,o_T|i_t=q_i,\lambda)\tag{20}
βt(i)=P(ot+1,ot+2,...,oT∣it=qi,λ)(20)
我们是从后往前去推导的即：
β
T
(
i
)
−
>
β
T
−
1
(
i
)
−
>
β
T
−
2
(
i
)
.
.
.
−
>
β
1
(
i
)
(21)
\beta_{T}(i)->\beta_{T-1}(i)->\beta_{T-2}(i)...->\beta_1(i)\tag{21}
βT(i)−>βT−1(i)−>βT−2(i)...−>β1(i)(21)
举例：
β
1
(
i
)
=
P
(
o
2
,
o
3
,
.
.
.
,
o
T
∣
i
t
=
q
i
,
λ
)
(22)
\beta_1(i)=P(o_{2},o_{3},...,o_T|i_t=q_i,\lambda)\tag{22}
β1(i)=P(o2,o3,...,oT∣it=qi,λ)(22)
我们的目标是要求
P
(
O
∣
λ
)
P(O|\lambda)
P(O∣λ)的概率。
P
(
O
∣
λ
)
=
P
(
o
1
,
o
2
,
.
.
.
,
o
T
∣
λ
)
=
∑
i
=
1
N
P
(
o
1
,
o
2
,
.
.
.
,
o
T
,
i
1
=
q
i
∣
λ
)
P(O|\lambda)=P(o_1,o_2,...,o_T|\lambda)=\sum_{i=1}^{N}P(o_1,o_2,...,o_T,i_1=q_i|\lambda)
P(O∣λ)=P(o1,o2,...,oT∣λ)=i=1∑NP(o1,o2,...,oT,i1=qi∣λ)
=
∑
i
=
1
N
P
(
o
1
,
o
2
,
.
.
.
,
o
T
∣
i
1
=
q
i
,
λ
)
⋅
P
(
i
1
=
q
i
∣
λ
)
=\sum_{i=1}^{N}P(o_1,o_2,...,o_T|i_1=q_i,\lambda)·P(i_1=q_i|\lambda)
=i=1∑NP(o1,o2,...,oT∣i1=qi,λ)⋅P(i1=qi∣λ)
-
P
(
i
1
=
q
i
∣
λ
)
=
π
i
;
注
：
初
始
概
率
分
布
π
=
{
π
1
,
π
2
,
.
.
.
,
π
N
}
P(i_1=q_i|\lambda)=\pi_i;注：初始概率分布 \pi=\{\pi_1,\pi_2,...,\pi_N\}
P(i1=qi∣λ)=πi;注：初始概率分布π={π1,π2,...,πN}
= ∑ i = 1 N P ( o 1 , o 2 , . . . , o T ∣ i 1 = q i , λ ) ⋅ π i =\sum_{i=1}^{N}P(o_1,o_2,...,o_T|i_1=q_i,\lambda)·\pi_i =i=1∑NP(o1,o2,...,oT∣i1=qi,λ)⋅πi - 将
o
1
o_1
o1提取出来可得：
= ∑ i = 1 N P ( o 1 ∣ o 2 , . . . , o T , i 1 = q i , λ ) ⋅ P ( o 2 , . . , o T ∣ i 1 = q i ) ⋅ π i =\sum_{i=1}^{N}P(o_1|o_2,...,o_T,i_1=q_i,\lambda)·P(o_2,..,o_T|i_1=q_i)·\pi_i =i=1∑NP(o1∣o2,...,oT,i1=qi,λ)⋅P(o2,..,oT∣i1=qi)⋅πi - 由观测独立性假设可得： P ( o 1 ∣ o 2 , . . . , o T , i 1 = q i , λ ) = P ( o 1 ∣ i 1 = q i ) P(o_1|o_2,...,o_T,i_1=q_i,\lambda)=P(o_1|i_1=q_i) P(o1∣o2,...,oT,i1=qi,λ)=P(o1∣i1=qi)
- 由定义可得：
P
(
o
2
,
.
.
,
o
T
∣
i
1
=
q
i
)
=
β
1
(
i
)
P(o_2,..,o_T|i_1=q_i)=\beta_1(i)
P(o2,..,oT∣i1=qi)=β1(i)
= ∑ i = 1 N P ( o 1 ∣ i 1 = q i ) ⋅ β 1 ( i ) ⋅ π i =\sum_{i=1}^{N}P(o_1|i_1=q_i)·\beta_1(i)·\pi_i =i=1∑NP(o1∣i1=qi)⋅β1(i)⋅πi -
由
定
义
可
得
：
b
i
(
o
1
)
=
P
(
o
1
∣
i
1
=
q
i
)
由定义可得：b_i(o_1)=P(o_1|i_1=q_i)
由定义可得：bi(o1)=P(o1∣i1=qi)
P ( O ∣ λ ) = ∑ i = 1 N b i ( o 1 ) ⋅ β 1 ( i ) ⋅ π i (23) P(O|\lambda)=\sum_{i=1}^{N}b_i(o_1)·\beta_1(i)·\pi_i\tag{23} P(O∣λ)=i=1∑Nbi(o1)⋅β1(i)⋅πi(23)
3.2 求出 β t ( i ) 递 推 关 系 \beta_t(i)递推关系 βt(i)递推关系
β t ( i ) = P ( o t + 1 , . . o T ∣ i t = q i ) (24) \beta_t(i)=P(o_{t+1},..o_T|i_t=q_i)\tag{24} βt(i)=P(ot+1,..oT∣it=qi)(24)
- 引入变量
i
t
+
1
=
q
j
i_{t+1}=q_j
it+1=qj，并求和抵消
= ∑ j = 1 N P ( o t + 1 , . . o T , i t + 1 = q j ∣ i t = q i ) =\sum_{j=1}^{N} P(o_{t+1},..o_T,i_{t+1}=q_j|i_t=q_i) =j=1∑NP(ot+1,..oT,it+1=qj∣it=qi) - 联合概率拆分：
= ∑ j = 1 N P ( o t + 1 , . . o T , ∣ i t + 1 = q j , i t = q i ) ⋅ P ( i t + 1 = q j ∣ i t = q i ) =\sum_{j=1}^{N} P(o_{t+1},..o_T,|i_{t+1}=q_j,i_t=q_i)·P(i_{t+1}=q_j|i_t=q_i) =j=1∑NP(ot+1,..oT,∣it+1=qj,it=qi)⋅P(it+1=qj∣it=qi) - 由图模型中head to tail 结构可得： P ( o t + 1 , . . o T , ∣ i t + 1 = q j , i t = q i ) = P ( o t + 1 , . . o T ∣ i t + 1 = q j ) P(o_{t+1},..o_T,|i_{t+1}=q_j,i_t=q_i)=P(o_{t+1},..o_T|i_{t+1}=q_j) P(ot+1,..oT,∣it+1=qj,it=qi)=P(ot+1,..oT∣it+1=qj)
-
P
(
i
t
+
1
=
q
j
∣
i
t
=
q
i
)
=
a
i
j
P(i_{t+1}=q_j|i_t=q_i)=a_{ij}
P(it+1=qj∣it=qi)=aij
= ∑ j = 1 N P ( o t + 1 , . . o T ∣ i t + 1 = q j ) ⋅ a i j =\sum_{j=1}^{N} P(o_{t+1},..o_T|i_{t+1}=q_j)·a_{ij} =j=1∑NP(ot+1,..oT∣it+1=qj)⋅aij -
将
o
t
+
1
提
出
来
将o_{t+1}提出来
将ot+1提出来
= ∑ j = 1 N P ( o t + 1 ∣ o t + 2 . . o T , i t + 1 = q j ) ⋅ P ( o t + 2 . . o T ∣ i t + 1 = q j ) ⋅ a i j =\sum_{j=1}^{N} P(o_{t+1}|o_{t+2}..o_T,i_{t+1}=q_j)·P(o_{t+2}..o_T|i_{t+1}=q_j)·a_{ij} =j=1∑NP(ot+1∣ot+2..oT,it+1=qj)⋅P(ot+2..oT∣it+1=qj)⋅aij - 由定义可得： P ( o t + 2 . . o T ∣ i t + 1 = q j ) = β t + 1 ( j ) P(o_{t+2}..o_T|i_{t+1}=q_j)=\beta_{t+1}(j) P(ot+2..oT∣it+1=qj)=βt+1(j)
- 由观测独立性假设可得：
P
(
o
t
+
1
∣
o
t
+
2
.
.
o
T
,
i
t
+
1
=
q
j
)
=
P
(
o
t
+
1
∣
i
t
+
1
=
q
j
)
=
b
j
(
o
t
+
1
)
P(o_{t+1}|o_{t+2}..o_T,i_{t+1}=q_j)=P(o_{t+1}|i_{t+1}=q_j)=b_j(o_{t+1})
P(ot+1∣ot+2..oT,it+1=qj)=P(ot+1∣it+1=qj)=bj(ot+1)
β t ( i ) = ∑ j = 1 N b j ( o t + 1 ) ⋅ a i j ⋅ β t + 1 ( j ) (25) \beta_t(i)=\sum_{j=1}^{N} b_j(o_{t+1})·a_{ij}·\beta_{t+1}(j)\tag{25} βt(i)=j=1∑Nbj(ot+1)⋅aij⋅βt+1(j)(25)
这样我们就能够通过上述公式由初始值 β T ( i ) \beta_T(i) βT(i)递推求出 β 1 ( i ) \beta_1(i) β1(i)，又由于 P ( O ∣ λ ) = ∑ i = 1 N b i ( o 1 ) ⋅ β 1 ( i ) ⋅ π i P(O|\lambda)=\sum_{i=1}^{N}b_i(o_1)·\beta_1(i)·\pi_i P(O∣λ)=∑i=1Nbi(o1)⋅β1(i)⋅πi所以我们可以求得 P ( O ∣ λ ) P(O|\lambda) P(O∣λ).
4.Baum-Welch算法[EM算法]
关于HMM模型中三大问题的第二个问题是Learning问题，主要是求得模型的参数，前面我们已经得到了，如下公式：
λ
M
L
E
=
arg
max
λ
P
(
O
∣
λ
)
(26)
\lambda_{MLE}=\mathop{\arg\max}\limits_{\lambda}P(O|\lambda)\tag{26}
λMLE=λargmaxP(O∣λ)(26)
P
(
O
∣
λ
)
=
∑
I
π
(
a
i
1
)
⋅
∏
t
=
2
T
a
i
t
−
1
i
t
⋅
∏
t
=
1
T
b
i
t
(
o
t
)
=
∑
i
1
∑
i
2
.
.
.
∑
i
T
π
(
a
i
1
)
⋅
∏
t
=
2
T
a
i
t
−
1
i
t
⋅
∏
t
=
1
T
b
i
t
(
o
t
)
(27)
P(O|\lambda)=\sum_{I}\pi(a_{i1})·\prod_{t=2}^{T}a_{i_{t-1}i_{t}}·\prod_{t=1}^{T}b_{i_t}(o_t)=\sum_{i_1}\sum_{i_2}...\sum_{i_T}\pi(a_{i1})·\prod_{t=2}^{T}a_{i_{t-1}i_{t}}·\prod_{t=1}^{T}b_{i_t}(o_t)\tag {27}
P(O∣λ)=I∑π(ai1)⋅t=2∏Tait−1it⋅t=1∏Tbit(ot)=i1∑i2∑...iT∑π(ai1)⋅t=2∏Tait−1it⋅t=1∏Tbit(ot)(27)
-
以上公式复杂度为 O ( N T ) O(N^T) O(NT)，根本无法求解，我们用前向或后向算法时，发现算法复杂度变为了 O ( T ⋅ N 2 ) O(T·N^2) O(T⋅N2)，规模下降很多。
为解决上述问题，我们想到了含隐变量模型的参数估计方法-EM算法。我们这里直接给出EM算法公式：
θ ( t + 1 ) = arg max θ ∫ z log P ( x , z ∣ θ ) ⋅ P ( z ∣ x , θ ( t ) ) d z (28) \theta^{(t+1)}=\mathop{\arg\max}\limits_{\theta}\int_{z}\log P(x,z|\theta)·P(z|x,\theta^{(t)})dz\tag{28} θ(t+1)=θargmax∫zlogP(x,z∣θ)⋅P(z∣x,θ(t))dz(28) -
我们将EM算法代入到HMM模型中进行分析类比；
-
X : 观 测 变 量 − > O 来 代 替 X:观测变量->O来代替 X:观测变量−>O来代替
-
Z ： 隐 变 量 − > I 来 代 替 Z：隐变量->I来代替 Z：隐变量−>I来代替
-
θ : 模 型 参 数 − > λ 来 代 替 \theta:模型参数->\lambda来代替 θ:模型参数−>λ来代替
λ ( t + 1 ) = arg max λ ∑ I log P ( O , I ∣ λ ) ⋅ P ( I ∣ O , λ ( t ) ) d I (29) \lambda^{(t+1)}=\mathop{\arg\max}\limits_{\lambda}\sum_{I}\log P(O,I|\lambda)·P(I|O,\lambda^{(t)})dI\tag{29} λ(t+1)=λargmaxI∑logP(O,I∣λ)⋅P(I∣O,λ(t))dI(29) -
由联合概率展开可得： P ( I ∣ O , λ ( t ) ) = P ( I , O ∣ λ ( t ) ) P ( O ∣ λ ( t ) ) P(I|O,\lambda^{(t)})=\frac{P(I,O|\lambda^{(t)})}{P(O|\lambda^{(t)})} P(I∣O,λ(t))=P(O∣λ(t))P(I,O∣λ(t))
-
由于 P ( O ∣ λ ( t ) ) 中 的 λ ( t ) 是 常 数 ， 所 以 分 母 此 项 与 I 无 关 ， 所 以 上 述 公 式 可 简 化 为 如 下 ： P(O|\lambda^{(t)})中的\lambda^{(t)}是常数，所以分母此项与I无关，所以上述公式可简化为如下： P(O∣λ(t))中的λ(t)是常数，所以分母此项与I无关，所以上述公式可简化为如下：
λ ( t + 1 ) = arg max λ ∑ I log P ( O , I ∣ λ ) ⋅ P ( O , I ∣ λ ( t ) ) (30) \lambda^{(t+1)}=\mathop{\arg\max}\limits_{\lambda}\sum_{I}\log P(O,I|\lambda)·P(O,I|\lambda^{(t)})\tag{30} λ(t+1)=λargmaxI∑logP(O,I∣λ)⋅P(O,I∣λ(t))(30) -
定义模型参数： λ ( t ) = ( π ( t ) , A ( t ) , B ( t ) ) \lambda^{(t)}=(\pi^{(t)},A^{(t)},B^{(t)}) λ(t)=(π(t),A(t),B(t))，为方便后续计算，我们引入函数定义 Q ( λ , λ ( t ) ) Q(\lambda,\lambda^{(t)}) Q(λ,λ(t))：
Q ( λ , λ ( t ) ) = ∑ I log P ( O , I ∣ λ ) ⋅ P ( O , I ∣ λ ( t ) ) (31) Q(\lambda,\lambda^{(t)})=\sum_{I}\log P(O,I|\lambda)·P(O,I|\lambda^{(t)})\tag{31} Q(λ,λ(t))=I∑logP(O,I∣λ)⋅P(O,I∣λ(t))(31) -
我们之前计算过关于 P ( O , I ∣ λ ) = ∑ I P ( O , I ∣ λ ) = ∑ I π ( a i 1 ) ⋅ ∏ t = 2 T a i t − 1 i t ⋅ ∏ t = 1 T b i t ( o t ) P(O,I|\lambda)=\sum_{I}P(O,I|\lambda)=\sum_{I}\pi(a_{i1})·\prod_{t=2}^{T}a_{i_{t-1}i_{t}}·\prod_{t=1}^{T}b_{i_t}(o_t) P(O,I∣λ)=∑IP(O,I∣λ)=∑Iπ(ai1)⋅∏t=2Tait−1it⋅∏t=1Tbit(ot);
-
故： P ( O , I ∣ λ ) = π 1 ⋅ ∏ t = 2 T a i t − 1 i t ⋅ ∏ t = 1 T b i t ( o t ) P(O,I|\lambda)=\pi_1·\prod_{t=2}^{T}a_{i_{t-1}i_{t}}·\prod_{t=1}^{T}b_{i_t}(o_t) P(O,I∣λ)=π1⋅∏t=2Tait−1it⋅∏t=1Tbit(ot),代入 Q ( λ , λ ( t ) ) Q(\lambda,\lambda^{(t)}) Q(λ,λ(t))可得：
Q ( λ , λ ( t ) ) = ∑ I { [ log π 1 + ∑ t = 2 T log a i t − 1 i t + ∑ t = 1 T log b i t ( o t ) ] ⋅ P ( O , I ∣ λ ( t ) ) } (32) Q(\lambda,\lambda^{(t)})=\sum_{I}\{[\log\pi_1+\sum_{t=2}^T \log a_{i_{t-1}i_{t} }+\sum_{t=1}^T\log b_{i_t}(o_t) ]·P(O,I|\lambda^{(t)})\}\tag{32} Q(λ,λ(t))=I∑{[logπ1+t=2∑Tlogait−1it+t=1∑Tlogbit(ot)]⋅P(O,I∣λ(t))}(32)
我们这里先只求 π ( t + 1 ) \pi^{(t+1)} π(t+1)，将其他无关项删除可得：
π ( t + 1 ) = arg max π Q ( λ , λ ( t ) ) (33) \pi^{(t+1)}=\mathop{\arg\max}\limits_{\pi}Q(\lambda,\lambda^{(t)})\tag{33} π(t+1)=πargmaxQ(λ,λ(t))(33)
π ( t + 1 ) = arg max π ∑ I [ log π 1 ⋅ P ( O , I ∣ λ ( t ) ) ] (34) \pi^{(t+1)}=\mathop{\arg\max}\limits_{\pi}\sum_I[\log \pi_1·P(O,I|\lambda^{(t)})]\tag{34} π(t+1)=πargmaxI∑[logπ1⋅P(O,I∣λ(t))](34)
π ( t + 1 ) = arg max π ∑ i 1 ∑ i 2 . . . ∑ i T [ log π 1 ⋅ P ( O , I 1 I 2 . . I T ∣ λ ( t ) ) ] (35) \pi^{(t+1)}=\mathop{\arg\max}\limits_{\pi}\sum_{i_1}\sum_{i_2}...\sum_{i_T}[\log \pi_1·P(O,I_1I_2..I_T|\lambda^{(t)})]\tag{35} π(t+1)=πargmaxi1∑i2∑...iT∑[logπ1⋅P(O,I1I2..IT∣λ(t))](35) -
将其他项 I 2 . . I T I_2..I_T I2..IT消除：
π ( t + 1 ) = arg max π ∑ i 1 [ log π 1 ⋅ P ( O , I 1 ∣ λ ( t ) ) ] (36) \pi^{(t+1)}=\mathop{\arg\max}\limits_{\pi}\sum_{i_1}[\log \pi_1·P(O,I_1|\lambda^{(t)})]\tag{36} π(t+1)=πargmaxi1∑[logπ1⋅P(O,I1∣λ(t))](36) -
I 1 是 状 态 序 列 中 第 一 个 状 态 ， 每 个 状 态 里 面 有 { q 1 , q 2 , . . , q N } I_1是状态序列中第一个状态，每个状态里面有\{q_1,q_2,..,q_N\} I1是状态序列中第一个状态，每个状态里面有{q1,q2,..,qN}组合，所以上式可变为：
π ( t + 1 ) = arg max π ∑ i = 1 N [ log π 1 ⋅ P ( O , i 1 = q i ∣ λ ( t ) ) ] (37) \pi^{(t+1)}=\mathop{\arg\max}\limits_{\pi}\sum_{i=1}^{N}[\log \pi_1·P(O,i_1=q_i|\lambda^{(t)})]\tag{37} π(t+1)=πargmaxi=1∑N[logπ1⋅P(O,i1=qi∣λ(t))](37)
同 时 满 足 ： ∑ i = 1 N π i = 1 (38) 同时满足：\sum_{i=1}^N \pi_i=1\tag{38} 同时满足：i=1∑Nπi=1(38) -
由拉格朗日乘子法可得如下：
L ( π , η ) = log π 1 ⋅ P ( O , i 1 = q i ∣ λ ( t ) ) + η ( 1 − ∑ i = 1 N π i ) (39) L(\pi,\eta)=\log \pi_1·P(O,i_1=q_i|\lambda^{(t)})+\eta(1-\sum_{i=1}^N\pi_i)\tag{39} L(π,η)=logπ1⋅P(O,i1=qi∣λ(t))+η(1−i=1∑Nπi)(39) -
对 L ( π , η ) 求 关 于 π i 求 偏 导 ： L(\pi,\eta)求关于\pi_i求偏导： L(π,η)求关于πi求偏导：
1 π i ⋅ P ( O , i 1 = q i ∣ λ ( t ) ) − η = 0 (40) \frac{1}{\pi_i}·P(O,i_1=q_i|\lambda^{(t)})-\eta=0\tag{40} πi1⋅P(O,i1=qi∣λ(t))−η=0(40)
η π i = P ( O , i 1 = q i ∣ λ ( t ) ) (41) \eta\pi_i=P(O,i_1=q_i|\lambda^{(t)})\tag{41} ηπi=P(O,i1=qi∣λ(t))(41) -
将上式关于i=1,2,…,N求和; ∑ i = 1 N π i = 1 \sum_{i=1}^N \pi_i=1 ∑i=1Nπi=1
η ∑ i = 1 N π i = ∑ i = 1 N P ( O , i 1 = q i ∣ λ ( t ) ) (42) \eta\sum_{i=1}^N\pi_i=\sum_{i=1}^NP(O,i_1=q_i|\lambda^{(t)})\tag{42} ηi=1∑Nπi=i=1∑NP(O,i1=qi∣λ(t))(42) -
代入可得：
π i ( t + 1 ) = P ( O , i 1 = q i ∣ λ ( t ) ) P ( O ∣ λ ( t + 1 ) ) (43) \pi_i^{(t+1)}=\frac{P(O,i_1=q_i|\lambda^{(t)})}{P(O|\lambda^{(t+1)})}\tag{43} πi(t+1)=P(O∣λ(t+1))P(O,i1=qi∣λ(t))(43)
π ( t + 1 ) = { π 1 ( t + 1 ) , π 2 ( t + 1 ) , . . . , π N ( t + 1 ) } (44) \pi^{(t+1)}=\{\pi_1^{(t+1)},\pi_2^{(t+1)},...,\pi_N^{(t+1)}\}\tag{44} π(t+1)={π1(t+1),π2(t+1),...,πN(t+1)}(44)
同理可以求得 A ( t + 1 ) , B ( t + 1 ) A^{(t+1)},B^{(t+1)} A(t+1),B(t+1)
λ ( t + 1 ) = ( π ( t + 1 ) , A ( t + 1 ) , B ( t + 1 ) ) (45) \lambda^{(t+1)}=(\pi^{(t+1)},A^{(t+1)},B^{(t+1)})\tag{45} λ(t+1)=(π(t+1),A(t+1),B(t+1))(45)
5. 维特比算法-Viterbi
HMM三个问题中的第三个问题Decoding 问题，主要是求在给定观测量的情况下，求隐变量序列问题。即
- Decoding 问题
I ^ = arg max I P ( I ∣ O , λ ) (46) \hat{I}=\mathop{\arg\max}\limits_{I} P(I|O,\lambda)\tag{46} I^=IargmaxP(I∣O,λ)(46)
在 给 定 T 个 观 测 变 量 O 的 情 况 下 ， 我 们 要 找 到 最 有 可 能 的 隐 状 态 序 列 I 在给定 T 个观测变量 O 的情况下，我们要找到最有可能的隐状态序列 I 在给定T个观测变量O的情况下，我们要找到最有可能的隐状态序列I - 预测问题：
P = P ( o T + 1 ∣ o 1 , o 2 , . . . , o T ) (47) P=P(o_{T+1}|o_1,o_2,...,o_T)\tag{47} P=P(oT+1∣o1,o2,...,oT)(47)
P = P ( i T + 1 ∣ o 1 , o 2 , . . . , o T ) (48) P=P(i_{T+1}|o_1,o_2,...,o_T)\tag{48} P=P(iT+1∣o1,o2,...,oT)(48)
所以预测问题应该是对未来时刻的预测，而不是对既定发生的事实的解析。所以第三个问题应该是解码问题，而不是预测问题。
因为每一个隐状态 I I I都有N个状态，即: I i = { q 1 , q 2 , . . . , q N } I_i=\{q_1,q_2,...,q_N\} Ii={q1,q2,...,qN},解码是为了求解最有可能的序列组合
这里相当于是一个动态规划问题，这里的动态规划问题实际上就是最大概率问题，每一个箭头可以按照相应的概率赋予一定的权重，这样就变成了求距离问题。理论是一样的，将每个时刻的N个状态中选择一个状态后最后组合成一个序列，找出概率最大的一个序列。
我们定义符号 δ t ( i ) \delta_t(i) δt(i)，其公式如下：
δ t ( i ) = max i 1 , . . . , i t − 1 P ( o 1 , o 2 , . . . , o t , i 1 , i 2 , . . . , i t − 1 , i t = q i ) (49) \delta_t(i)=\mathop{\max}\limits_{i_1,...,i_{t-1}} P(o_1,o_2,...,o_t,i_1,i_2,...,i_{t-1},i_t=q_i)\tag{49} δt(i)=i1,...,it−1maxP(o1,o2,...,ot,i1,i2,...,it−1,it=qi)(49) - 在 第 t 时 刻 时 是 第 q i 状 态 时 ， 前 面 t − 1 时 刻 随 便 走 ， 只 要 可 以 到 达 q i 这 个 状 态 就 行 了 。 而 从 中 选 取 概 率 最 大 的 序 列 在第 t 时刻时是第q_i状态时，前面t-1时刻随便走，只要可以到达q_i这个状态就行了。而从中选取概率最大的序列 在第t时刻时是第qi状态时，前面t−1时刻随便走，只要可以到达qi这个状态就行了。而从中选取概率最大的序列，我们的想法是在已知 t 时刻时，我们求关于 t+1 时刻的状态；
-
δ
t
+
1
(
j
)
\delta_{t+1}(j)
δt+1(j)状态如图所示：
δ t + 1 ( i ) = max i 1 , . . . , i t P ( o 1 , o 2 , . . . , o t , o t + 1 , i 1 , i 2 , . . . , i t − 1 , i t + 1 = q j ) (50) \delta_{t+1}(i)=\mathop{\max}\limits_{i_1,...,i_{t}} P(o_1,o_2,...,o_t,o_{t+1},i_1,i_2,...,i_{t-1},i_{t+1}=q_j)\tag{50} δt+1(i)=i1,...,itmaxP(o1,o2,...,ot,ot+1,i1,i2,...,it−1,it+1=qj)(50) - 递推式：
δ t + 1 ( i ) = max 1 ≤ i ≤ N δ t ( i ) a i j b j ( o t + 1 ) (51) \delta_{t+1}(i)=\mathop{\max}\limits_{1\leq i \leq N}\delta_{t}(i)a_{ij}b_j(o_{t+1}) \tag{51} δt+1(i)=1≤i≤Nmaxδt(i)aijbj(ot+1)(51)
viterbi算法最后求得的是一个概率值，而不是一个路径序列，为了求序列，需要引入如下变量：
ϕ t + 1 ( j ) = arg max 1 ≤ i ≤ N δ t ( i ) ⋅ a i j (52) \phi_{t+1}(j)=\mathop{\arg\max}\limits_{1 \leq i \leq N}\delta_t(i)·a_{ij} \tag{52} ϕt+1(j)=1≤i≤Nargmaxδt(i)⋅aij(52) - 这个函数用来干嘛的呢？他是来记录每一次迭代过程中经过的状态的 index。这样我们最终得到的
{ φ 1 , φ 2 , ⋅ ⋅ ⋅ , φ T } \{φ_1, φ_2, · · · , φ_T \} {φ1,φ2,⋅⋅⋅,φT}，就可以得到整个路径了.
6.小结
隐马尔科夫模型属于动态模型的一种，属于模型加时间序列，不仅仅跟时间相关。我们知道高斯混合模型GMM中的隐变量Z是离散型的，可以得到
Z
=
{
Z
1
,
Z
2
,
.
.
.
,
Z
N
}
Z=\{Z_1,Z_2,...,Z_N\}
Z={Z1,Z2,...,ZN},X是观测变量，从Z到X满足高斯分布即[发射概率：
Z
→
X
∼
N
(
μ
,
δ
)
Z\rightarrow X \sim N(\mu,\delta)
Z→X∼N(μ,δ)]，HMM可以看作是高斯混合模型GMM加上时间序列。
H
M
M
=
G
M
M
+
T
i
m
e
(53)
HMM=GMM+Time \tag{53}
HMM=GMM+Time(53)
- HMM中 i 1 , i 2 , . . . i N 都 是 离 散 的 i_1,i_2,...i_N都是离散的 i1,i2,...iN都是离散的
- 发射概率 P ( o j ∣ i j ) P(o_j|i_j) P(oj∣ij)可以是离散也可以是连续
- 观测变量O可以是离散也可以是连续
6.1 learning 问题
动态模型往往也可以称作状态空间模型，就是要解决learning 问题，即通过观测变量X来学习出模型的参数，
6.2 Inference 问题
另外一个是推断Inference问题，即P(Z|X)H后验分布，推断问题分很多，具体如下
- Decoding解码问题(在给定观测量X的情况下，求出隐变量Z的最大可能性概率)：
P ( Z 1 , Z 2 , . . . , Z t ∣ X 1 , X 2 , . . . , X t ) (54) P(Z_1,Z_2,...,Z_t|X_1,X_2,...,X_t) \tag{54} P(Z1,Z2,...,Zt∣X1,X2,...,Xt)(54) - Prob of evidence
P ( Z t ∣ X 1 , X 2 , . . , X t ) (55) P(Z_t|X_1,X_2,..,X_t)\tag{55} P(Zt∣X1,X2,..,Xt)(55) - filtering 滤波问题-在线学习online-learning
P ( Z t ∣ X 1 , X 2 , . . . , X t ) (56) P(Z_t|X_1,X_2,...,X_t)\tag{56} P(Zt∣X1,X2,...,Xt)(56) - smoothing平滑问题-离线学习offline-learning
P ( Z t ∣ X 1 , X 2 , . . . , X T ) (57) P(Z_t|X_1,X_2,...,X_T)\tag{57} P(Zt∣X1,X2,...,XT)(57) - prediction预测问题：如在给定"我爱我的祖X"时，就能预测X为国
P ( Z t + 1 , Z t ∣ X 1 , X 2 , . . . , X t ) (57) P(Z_{t+1},Z_{t}|X_1,X_2,...,X_t)\tag{57} P(Zt+1,Zt∣X1,X2,...,Xt)(57)
P ( X t + 1 , X t + 2 ∣ X 1 , X 2 , . . . , X t ) (58) P(X_{t+1},X_{t+2}|X_1,X_2,...,X_t)\tag{58} P(Xt+1,Xt+2∣X1,X2,...,Xt)(58)
7.小结-算法
如下图为HMM模型所涉及到的推断问题背后的算法。
Z
=
arg
max
Z
P
(
Z
∣
X
)
Z=\mathop{\arg\max}\limits_{Z}P(Z|X)
Z=ZargmaxP(Z∣X)
7.1 filtering 滤波问题
- filtering 滤波问题-在线学习online-learning
P ( Z t ∣ X 1 , X 2 , . . . , X t ) (59) P(Z_t|X_1,X_2,...,X_t)\tag{59} P(Zt∣X1,X2,...,Xt)(59) - 条件概率转联合概率
P ( Z t ∣ X 1 : t ) = P ( Z t , X 1 : t ) P ( X 1 : t ) (60) P(Z_t|X_{1:t})=\frac{P(Z_t,X_{1:t})}{P(X_{1:t})}\tag{60} P(Zt∣X1:t)=P(X1:t)P(Zt,X1:t)(60) - 定义如下变量：
α t = P ( X 1 , X 2 , . . . , X t , Z t ) (61) \alpha_t=P(X_1,X_2,...,X_t,Z_t)\tag{61} αt=P(X1,X2,...,Xt,Zt)(61)
β t = P ( X t + 1 , X t + 2 , . . . , X T ∣ Z t ) (62) \beta _t=P(X_{t+1},X_{t+2},...,X_T|Z_t)\tag{62} βt=P(Xt+1,Xt+2,...,XT∣Zt)(62)
那么我们可以得到如下：
P ( Z t ∣ X 1 : t ) = α t ∑ Z t P ( X 1 : t , Z t ) ∝ α t (63) P(Z_t|X_{1:t})=\frac{\alpha_t}{\sum_{Z_t}P(X_{1:t},Z_t)}\propto \alpha_t\tag{63} P(Zt∣X1:t)=∑ZtP(X1:t,Zt)αt∝αt(63) - P ( X 1 : t ) = ∑ Z t P ( X 1 : t , Z t ) P(X_{1:t})=\sum_{Z_t}P(X_{1:t},Z_t) P(X1:t)=∑ZtP(X1:t,Zt),此项与Z变量无关，故在求概率时忽略。
- 所以filtering 滤波问题就可以用前向算法求解(Forward-algorithm)
7.2 Smoothing平滑问题
由于已知smoothing问题是求
P
(
Z
t
∣
X
1
,
X
2
,
.
.
.
,
X
T
)
P(Z_t|X_1,X_2,...,X_T)
P(Zt∣X1,X2,...,XT)，故我们可以转换成如下：
P
(
Z
t
∣
X
1
,
X
2
,
.
.
.
,
X
T
)
=
P
(
X
1
,
X
2
,
.
.
.
,
X
T
,
Z
t
)
P
(
X
1
,
X
2
,
.
.
.
,
X
T
)
(64)
P(Z_t|X_1,X_2,...,X_T)=\frac{P(X_1,X_2,...,X_T,Z_t)}{P(X_1,X_2,...,X_T)}\tag{64}
P(Zt∣X1,X2,...,XT)=P(X1,X2,...,XT)P(X1,X2,...,XT,Zt)(64)
-
P
(
X
1
,
X
2
,
.
.
.
,
X
T
,
Z
t
)
简
化
为
：
P
(
X
1
:
T
,
Z
t
)
P(X_1,X_2,...,X_T,Z_t)简化为：P(X_{1:T},Z_t)
P(X1,X2,...,XT,Zt)简化为：P(X1:T,Zt)
P ( Z t ∣ X 1 , X 2 , . . . , X T ) = P ( X 1 : T , Z t ) P ( X 1 : T ) = P ( X 1 : T , Z t ) ∑ Z t P ( X 1 : T , Z t ) (65) P(Z_t|X_1,X_2,...,X_T)=\frac{P(X_{1:T},Z_t)}{P(X_{1:T})}=\frac{P(X_{1:T},Z_t)}{\sum _{Z_t}P(X_{1:T},Z_t)}\tag{65} P(Zt∣X1,X2,...,XT)=P(X1:T)P(X1:T,Zt)=∑ZtP(X1:T,Zt)P(X1:T,Zt)(65) - 化简
P
(
X
1
:
T
,
Z
t
)
P(X_{1:T},Z_t)
P(X1:T,Zt)
P ( X 1 : T , Z t ) = P ( X 1 : t , X t + 1 : T , Z t ) = P ( X t + 1 : T ∣ X 1 : t , Z t ) ⋅ P ( X 1 : t , Z t ) (66) P(X_{1:T},Z_t)=P(X_{1:t},X_{t+1:T},Z_t)=P(X_{t+1:T}|X_{1:t},Z_t)·P(X_{1:t},Z_t)\tag{66} P(X1:T,Zt)=P(X1:t,Xt+1:T,Zt)=P(Xt+1:T∣X1:t,Zt)⋅P(X1:t,Zt)(66)
由定义可得如下： P ( X 1 : t , Z t ) = α t P(X_{1:t},Z_t)=\alpha_t P(X1:t,Zt)=αt
为了方便用概率图tail-to-tail来描述上述问题，我们定义如下符号： - C = X t + 1 : T C=X_{t+1:T} C=Xt+1:T
- B = Z t B=Z_t B=Zt
-
A
=
X
1
:
t
A=X_{1:t}
A=X1:t
故 可 得 ： P ( X t + 1 : T ∣ X 1 : t , Z t ) = P ( C ∣ A , B ) (67) 故可得：P(X_{t+1:T}|X_{1:t},Z_t)=P(C|A,B)\tag{67} 故可得：P(Xt+1:T∣X1:t,Zt)=P(C∣A,B)(67)
由图形可得：
上述可以看作概率图中的tail-to-tail模型
P
由tail-to-tail可得，在给定变量B时，变量A独立于变量C;即：A⊥C|B
则：
P ( C ∣ A , B ) = P ( C ∣ B ) (68) P(C|A,B)=P(C|B)\tag{68} P(C∣A,B)=P(C∣B)(68)
故可得如下：
P ( X t + 1 : T ∣ X 1 : t , Z t ) = P ( X t + 1 : T ∣ Z t ) = β t (69) P(X_{t+1:T}|X_{1:t},Z_t)=P(X_{t+1:T}|Z_t)=\beta_t\tag{69} P(Xt+1:T∣X1:t,Zt)=P(Xt+1:T∣Zt)=βt(69)
综上所述：
P ( Z t ∣ X 1 , X 2 , . . . , X T ) = α t ⋅ β t (70) P(Z_t|X_1,X_2,...,X_T)=\alpha_t·\beta_t\tag{70} P(Zt∣X1,X2,...,XT)=αt⋅βt(70)
所以Smoothing平滑问题可以看作是前向后向算法[forward-backward algorithm]
7.3 Prediction-预测问题
7.3.1预测问题<1>
我们知道预测问题就是要求
P
(
Z
t
+
1
,
Z
t
∣
X
1
,
X
2
,
.
.
.
,
X
t
)
P(Z_{t+1},Z_{t}|X_1,X_2,...,X_t)
P(Zt+1,Zt∣X1,X2,...,Xt),我们可以进行拆分得到如下公式
P
(
Z
t
+
1
∣
X
1
:
t
)
=
∑
Z
t
P
(
Z
t
+
1
,
Z
t
∣
X
1
:
t
)
=
∑
Z
t
P
(
Z
t
+
1
∣
Z
t
,
X
1
:
t
)
⋅
P
(
Z
t
∣
X
1
:
t
)
(71)
P(Z_{t+1}|X_{1:t})=\sum_{Z_t}P(Z_{t+1},Z_t|X_{1:t})=\sum_{Z_t}P(Z_{t+1}|Z_t,X_{1:t})·P(Z_t|X_{1:t})\tag{71}
P(Zt+1∣X1:t)=Zt∑P(Zt+1,Zt∣X1:t)=Zt∑P(Zt+1∣Zt,X1:t)⋅P(Zt∣X1:t)(71)
- 由齐次马可夫假设可得： P ( Z t + 1 ∣ Z t , X 1 : t ) = P ( Z t + 1 ∣ Z t ) = P(Z_{t+1}|Z_t,X_{1:t})=P(Z_{t+1}|Z_t)= P(Zt+1∣Zt,X1:t)=P(Zt+1∣Zt)=
- P ( Z t ∣ X 1 : t ) P(Z_t|X_{1:t}) P(Zt∣X1:t)就是我们前面求得filtering问题；
故 p r e d i c t i o n 问 题 就 是 用 的 前 向 算 法 f o r w a r d − a l g o r i t h m 故prediction问题就是用的前向算法forward-algorithm 故prediction问题就是用的前向算法forward−algorithm
7.3.2预测问题<2>
预测问题第二类是求概率值：
P
(
X
t
+
1
∣
X
1
:
t
)
P(X_{t+1}|X_{1:t})
P(Xt+1∣X1:t),为了方便计算，我们需要的是引入变量
Z
t
+
1
Z_{t+1}
Zt+1,即：
P
(
X
t
+
1
∣
X
1
:
t
)
=
∑
Z
t
+
1
P
(
X
t
+
1
,
Z
t
+
1
∣
X
1
:
t
)
=
∑
Z
t
+
1
P
(
X
t
+
1
∣
Z
t
+
1
,
X
1
:
t
)
⋅
P
(
Z
t
+
1
∣
X
1
:
t
)
(72)
P(X_{t+1}|X_{1:t})=\sum_{Z_{t+1}}P(X_{t+1},Z_{t+1}|X_{1:t})=\sum_{Z_{t+1}}P(X_{t+1}|Z_{t+1},X_{1:t})·P(Z_{t+1}|X_{1:t})\tag{72}
P(Xt+1∣X1:t)=Zt+1∑P(Xt+1,Zt+1∣X1:t)=Zt+1∑P(Xt+1∣Zt+1,X1:t)⋅P(Zt+1∣X1:t)(72)
- 由观测独立假设可得： P ( X t + 1 ∣ Z t + 1 , X 1 : t ) = P ( X t + 1 ∣ Z t + 1 ) − > 已 知 P(X_{t+1}|Z_{t+1},X_{1:t})=P(X_{t+1}|Z_{t+1})->已知 P(Xt+1∣Zt+1,X1:t)=P(Xt+1∣Zt+1)−>已知
- P ( Z t + 1 ∣ X 1 : t ) ： 表 示 就 是 预 测 问 题 < 1 > P(Z_{t+1}|X_{1:t})：表示就是预测问题<1> P(Zt+1∣X1:t)：表示就是预测问题<1>
CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！
更多推荐
0
0- 0
已为社区贡献5条内容
所有评论(0)