HMM 博客汇总
全部（为了防止部分读者厌烦，故而单独发了三个问题的博客）概率计算问题学习问题解码问题词性标注
解码问题（Decoding）
解码问题就是求 argmaxIP(I∣O,λ)\underset{I}{argmax}\ P(I|O,\lambda)IargmaxP(I∣O,λ)
Viterbi算法
Viterbi算法事实上是一个动态规划的算法
这个图来自知乎
我们把概率当成距离
那么只要确定了唯一的终点，到这个终点的最大距离必然等于到前一个时间轴5个点的最大距离分别乘以这5个点到终点的距离
我们也可以用公式严格推导出这一性质
定义距离为
δt(i)=maxi1,i2,...,it−1P(o1,o2,...,ot,i1,i2,...,it−1,it=qi)\delta_t(i) = \underset{i_1,i_2,...,i_{t-1}}{max} P(o_1,o_2,...,o_t,i_1,i_2,...,i_{t-1},i_t=q_i) δt(i)=i1,i2,...,it−1maxP(o1,o2,...,ot,i1,i2,...,it−1,it=qi)
δi+1(i)=maxi1,i2,...,itP(o1,o2,...,ot,ot+1,i1,i2,...,it−1,it,it+1=qi)=maxi1,i2,...,itP(ot+1∣it+1=qi)⋅P(o1,o2,...,ot,i1,i2,...,it,it+1=qi)=bi(ot+1)⋅maxi1,i2,...,itP(o1,o2,...,ot,i1,i2,...,it,it+1=qi)=bi(ot+1)⋅maxjmaxi1,i2,...,it−1P(o1,o2,...,ot,i1,i2,...,it=qj,it+1=qi)=bi(ot+1)⋅maxjmaxi1,i2,...,it−1P(it+1=qi∣it=qj)⋅P(o1,o2,...,ot,i1,i2,...,it=qj)=bi(ot+1)⋅maxjmaxi1,i2,...,it−1αji⋅P(o1,o2,...,ot,i1,i2,...,it=qj)=bi(ot+1)⋅maxj(αji⋅maxi1,i2,...,it−1P(o1,o2,...,ot,i1,i2,...,it=qj))=bi(ot+1)⋅maxj(αji⋅δt(j))\begin{aligned} \delta_{i+1}(i) &= \underset{i_1,i_2,...,i_t}{max} P(o_1,o_2,...,o_t,o_{t+1},i_1,i_2,...,i_{t-1},i_t,i_{t+1}=q_i) \\ &= \underset{i_1,i_2,...,i_t}{max} P(o_{t+1}|i_{t+1}=q_i)\cdot P(o_1,o_2,...,o_t,i_1,i_2,...,i_t,i_{t+1}=q_i) \\ &=b_i(o_{t+1})\cdot \underset{i_1,i_2,...,i_t}{max} P(o_1,o_2,...,o_t,i_1,i_2,...,i_t,i_{t+1}=q_i) \\ &=b_i(o_{t+1})\cdot \underset{j}{max}\underset{i_1,i_2,...,i_{t-1}}{max}P(o_1,o_2,...,o_t,i_1,i_2,...,i_t=q_j,i_{t+1}=q_i) \\ &=b_i(o_{t+1})\cdot \underset{j}{max}\underset{i_1,i_2,...,i_{t-1}}{max}P(i_{t+1}=q_i|i_t=q_j)\cdot P(o_1,o_2,...,o_t,i_1,i_2,...,i_t=q_j) \\ &=b_i(o_{t+1})\cdot \underset{j}{max}\underset{i_1,i_2,...,i_{t-1}}{max}\alpha_{ji}\cdot P(o_1,o_2,...,o_t,i_1,i_2,...,i_t=q_j) \\ &=b_i(o_{t+1})\cdot \underset{j}{max}\left( \alpha_{ji}\cdot \underset{i_1,i_2,...,i_{t-1}}{max}P(o_1,o_2,...,o_t,i_1,i_2,...,i_t=q_j)\right) \\ &=b_i(o_{t+1})\cdot \underset{j}{max}\left( \alpha_{ji}\cdot \delta_t(j)\right) \\ \end{aligned} δi+1(i)=i1,i2,...,itmaxP(o1,o2,...,ot,ot+1,i1,i2,...,it−1,it,it+1=qi)=i1,i2,...,itmaxP(ot+1∣it+1=qi)⋅P(o1,o2,...,ot,i1,i2,...,it,it+1=qi)=bi(ot+1)⋅i1,i2,...,itmaxP(o1,o2,...,ot,i1,i2,...,it,it+1=qi)=bi(ot+1)⋅jmaxi1,i2,...,it−1maxP(o1,o2,...,ot,i1,i2,...,it=qj,it+1=qi)=bi(ot+1)⋅jmaxi1,i2,...,it−1maxP(it+1=qi∣it=qj)⋅P(o1,o2,...,ot,i1,i2,...,it=qj)=bi(ot+1)⋅jmaxi1,i2,...,it−1maxαji⋅P(o1,o2,...,ot,i1,i2,...,it=qj)=bi(ot+1)⋅jmax(αji⋅i1,i2,...,it−1maxP(o1,o2,...,ot,i1,i2,...,it=qj))=bi(ot+1)⋅jmax(αji⋅δt(j))
推导完毕
但是上面还没有给出路径
对于给定终点，我们要知道到达它的上一个点
即
ψt+1(i)=argmaxjδt(j)⋅aji\psi_{t+1}(i)=\underset{j}{\operatorname{argmax}} \delta_{t}(j)\cdot a_{ji} ψt+1(i)=jargmaxδt(j)⋅aji
算法过程
（1）初值
δ1(i)=P(o1,i1=qi)=P(o1∣i1=qi)⋅P(i1=qi)=bi(o1)πi\delta_1(i) = P(o_1,i_1=q_i) = P(o_1\mid i_1=q_i)\cdot P(i_1=q_i) = b_i(o_1)\pi_i δ1(i)=P(o1,i1=qi)=P(o1∣i1=qi)⋅P(i1=qi)=bi(o1)πi
（2）递推
δi+1(i)=bi(ot+1)⋅maxj(αji⋅δt(j))ψt+1(i)=argmaxj(δt(j)⋅aji)\begin{aligned} \delta_{i+1}(i) &= b_i(o_{t+1})\cdot \underset{j}{max}\left( \alpha_{ji}\cdot \delta_t(j)\right) \\ \psi_{t+1}(i) &= \underset{j}{\operatorname{argmax}}(\delta_{t}(j)\cdot a_{ji}) \end{aligned} δi+1(i)ψt+1(i)=bi(ot+1)⋅jmax(αji⋅δt(j))=jargmax(δt(j)⋅aji)
（3）终止
P∗=max1⩽i⩽NδT(i)iT∗=argmax1⩽i⩽N[δT(i)]\begin{array}{c} P^{*}=\underset{{1 \leqslant i \leqslant N}}{max} \delta_{T}(i) \\ i_{T}^{*}=\underset{{1 \leqslant i \leqslant N}}{argmax}\left[\delta_{T}(i)\right] \end{array} P∗=1⩽i⩽NmaxδT(i)iT∗=1⩽i⩽Nargmax[δT(i)]
（4）回溯（对 ttt 从T−1,T−2,...,1T-1,T-2,...,1T−1,T−2,...,1）
it∗=argmax1⩽i⩽N[δt(i)]i_t^* = \underset{{1 \leqslant i \leqslant N}}{argmax}\left[\delta_{t}(i)\right] it∗=1⩽i⩽Nargmax[δt(i)]
算法实现
import numpy as nppi= [0.25,0.25,0.25,0.25]A = [[0, 1, 0, 0 ],[0.4,0,0.6,0],[0,0.4,0,0.6],[0,0,0.5,0.5]]B = [[0.5,0.5],[0.3,0.7],[0.6,0.4],[0.8,0.2]]
定义模型
class Model:def __init__(self,pi,A,B) -> None:self.pi = np.array(pi)self.A = np.array(A)self.B = np.array(B)self.N = len(A)self.M = len(B[0])def decode(self,O):T = len(O)delta = np.zeros(shape=(T,self.N))fi = np.zeros(shape=(T,self.N),dtype=int)# 初始化delta[0] = self.B[:,O[0]]*self.pi# 前向计算for t in range(0,T-1):for i in range(self.N):p = self.A[:,i]*delta[t]delta[t+1][i] = self.B[i,O[t+1]]*p.max()fi[t+1][i] = p.argmax()#回溯I = []index = delta[T-1].argmax()I.append(index)for t in reversed(range(1,T)):index = fi[t,index]I.insert(0,index)return I
解码
model = Model(pi,A,B)I,O = generate(5)print(I)print(O)model.decode(O)
