Table of Contents
Hidden Markov Model (隐马尔科夫模型)
Back to TOC
两种问题特征：
- 基于序列的，比如时间序列，或者状态序列
- 两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列
定义
Back to TOC
假设 N N N是可能的隐藏状态数， M M M是可能的观测状态数，定义
Q = { q 1 , q 2 , … , q N } , V = { v 1 , v 2 , … , v M } \mathcal{Q}=\{q_1,q_2,\dots,q_N\},\mathcal{V}=\{v_1,v_2,\dots,v_M\} Q={
q1,q2,…,qN},V={
v1,v2,…,vM}
分别为所有可能的隐藏状态和所有可能的观测状态的集合
同时，对于一个长度为 T T T的序列 I I I，和对应的观测序列 O O O
I = { s 1 , s 2 , … , s T } , O = { o 1 , o 2 , … , o T } \mathcal{I}=\{s_1,s_2,\dots,s_T\},\mathcal{O}=\{o_1,o_2,\dots,o_T\} I={
s1,s2,…,sT},O={
o1,o2,…,oT}
HMM做了两个很重要的假设：
- 齐次马尔科夫链假设。任意时刻隐藏状态只依赖于它前一个隐藏状态
定义状态转移概率 A i j A_{ij} Aij为从当前时刻 t t t的状态 s i s_i si转移到下一时刻 t + 1 t+1 t+1的状态 s j s_j sj的概率，即
A i j = P ( s t + 1 = q j ∣ s t = q i ) A_{ij}=P(s_{t+1}=q_j|s_t=q_i) Aij=P(st+1=qj∣st=qi)
从而定义状态转移矩阵 A ∈ R N × N A\in \mathbb{R}^{N\times N} A∈RN×N
- 观测独立性假设即任意时刻的观测状态只仅仅依赖于当前时刻的隐藏状态。定义生成概率 B i j B_{ij} Bij为由隐藏状态 s i s_i si生成观测状态 q j q_j qj的概率，即
B i j = P ( o t = v i ∣ s t = q j ) B_{ij}=P(o_t=v_i|s_t=q_j) Bij=P(ot=vi∣st=qj)
从而定义生成概率矩阵(发射矩阵) B ∈ R N × M B\in \mathbb{R}^{N\times M} B∈RN×M
最后，定义在 t t t时刻的隐藏状态分布 Π t = [ π t ( k ) ] \Pi_t=[\pi_t (k)] Πt=[πt(k)]，其中 π t ( k ) = P ( s t = q k ) \pi_t (k)=P(s_t=q_k) πt(k)=P(st=qk)
因此一个HMM模型主要由三个参数表示：
λ = ( A , B , Π ) \lambda=(A,B,\Pi) λ=(A,B,Π)
基本问题
Back to TOC
-
- 评估观察序列概率。给定模型 λ \lambda λ和观测序列 O \mathcal{O} O，计算在模型 λ \lambda λ下该观测序列 O \mathcal{O} O出现的概率 P ( O ∣ λ ) P(\mathcal{O}|\lambda) P(O∣λ)。求解方法：前向后向算法
-
- 预测问题。给定观测序列 O = { o 1 , o 2 , … , o T } \mathcal{O}=\{o_1,o_2,\dots,o_T\} O={
o1,o2,…,oT}和模型参数 λ = （ A , B , Π ) \lambda=（A,B,\Pi) λ=（A,B,Π)，求解最有可能出现的隐藏状态序列。求解方法：Viterbi算法
-
- 模型参数学习问题。给定观测序列 O = { o 1 , o 2 , … , o T } \mathcal{O}=\{o_1,o_2,\dots,o_T\} O={
o1,o2,…,oT}，求解模型参数 λ = （ A , B , Π ) \lambda=（A,B,\Pi) λ=（A,B,Π)使得 P ( O ∣ λ ) P(\mathcal{O}|\lambda) P(O∣λ)最大。求解方法：Baum-Walch算法(EM算法)
前向算法
Back to TOC
算法流程
输入：观测序列 O = { o 1 , o 2 , … , o T } \mathcal{O}=\{o_1,o_2,\dots,o_T\} O={
o1,o2,…,oT}，模型参数 λ = （ A , B , Π ) \lambda=（A,B,\Pi) λ=（A,B,Π)
输出：观测序列 P ( O ∣ λ ) P(O|\lambda) P(O∣λ)
步骤：
- 计算时刻1各个隐藏状态 s i s_i si的前向概率
α 1 ( i ) = π ( i ) B i , o 1 , i = 1 , 2 , … , N \alpha_1(i)=\pi(i)B_{i,o_1},i=1,2,\dots,N α1(i)=π(i)Bi,o1,i=1,2,…,N
- 递推 2 , 3 , … , T 2,3,\dots,T 2,3,…,T时刻的前向概率
α t + 1 ( i ) = [ ∑ j = 1 N α t ( j ) A j i ] B i , o t + 1 , i = 1 , 2 , … , N \alpha_{t+1}(i)=[\sum_{j=1}^{N}\alpha_{t}(j)A_{ji}]B_{i,o_{t+1}},i=1,2,\dots,N αt+1(i)=[j=1∑Nαt(j)Aji]Bi,ot+1,i=1,2,…,N
- 最终结果
P ( O ∣ λ ) = ∑ i N α T ( i ) P(\mathcal{O}|\lambda)=\sum_i^N\alpha_T(i) P(O∣λ)=i∑NαT(i)
实现代码
def HMMfwd(pi, a, b, obs):
'''
pi:初始概率分布
a:状态转移矩阵
b:发射矩阵
obs:观测序列
'''
nStates = np.shape(b)[0]
T = np.shape(obs)[0]
alpha = np.zeros((nStates,T))
'''alpha[i,t]表示上述公式的 alpha_t(i)'''
alpha[:,0] = pi*b[:,obs[0]]
for t in range(1,T):
for s in range(nStates):
alpha[s,t] = b[s,obs[t]] * np.sum(alpha[:,t-1] * a[:,s])
return alpha
最后计算 P ( O ∣ λ ) P(\mathcal{O}|\lambda) P(O∣λ)
np.sum(alpha[:,-1])
后向算法
Back to TOC
算法流程
输入：观测序列 O = { o 1 , o 2 , … , o T } \mathcal{O}=\{o_1,o_2,\dots,o_T\} O={
o1,o2,…,oT}，模型参数 λ = （ A , B , Π ) \lambda=（A,B,\Pi) λ=
