隐马尔可夫模型（一）

  2019-10-25 

Hidden Markov Model

隐马尔可夫模型，HMM，属于生成模型

HMM存在两个随机过程，且两个过程是相互联系的，具体来说就是第一个随机过程为状态序列随机过程，这和一般的马尔可夫链一致（具有马尔可夫性，当前状态只与前一个状态有关，与其它状态、观测无论未来还是过去都无关），第二个随机过程为观测序列的随机过程，它的当前值（观测值）由每一时刻的状态序列随机过程下的当前状态生成，且观测序列当前值只与状态序列随机过程的当前状态有关，与随机过程中其它观测和状态无论未来还是过去无关。即：

HMM观测序列每生成一个新的状态就生成一次新观测

符号表记

HMM中符号较多

$\lambda=(A,B,\pi)$表记一个HMM，$A$：状态转移概率矩阵，$B$：观测概率矩阵，$\pi$：初始状态概率向量(比如$\pi=[0.2,0,4,0,4]$即表示在$t=1$时状态为$q_1,q_2,q_3$的初始概率分别为$0.2,0,4,0,4$

$i_t$：一个状态，$I=(i_1,i_2,\cdots,i_T)$：状态序列，经过指定状态序列$i_1,i_2,\cdots,i_T$后到达指定最终状态$i_T$的概率

$o_k$：一个观测，$O=(o_1,o_2,\cdots,o_T)$：观测序列，对指定状态序列过程中产生的每一时刻状态进行观测（产生一个观测），这些观测构成指定序列的概率

$N$：可能的状态数，$Q=\{q_1.q_2.\cdots,q_N\}$：可能的状态集合

$M$：可能的观测数，$V=\{v_1,v_2,\cdots,v_M\}$：可能的观测集合

注意$i∈(i_1,\cdots,i_t)$但$q∈(q_1,\cdots,q_N),v∈(v_1,\cdots,v_M)$

$a_{ij}=P(i_{t+1}|i_t)$：$t$时刻下状态$i_t$到$t+1$时刻下状态$i_{t+1}$的转移概率

$b_{i_t}(o_t)$：$t$时刻下，由状态$i_t$产生的观测$o_t$的概率，具体的，$b_{q_{i_t}}(o_t)$即状态$i_t$取值为$q_{i_t}$时候，观测为$o_t$的概率

注意 对于当前状态$\sigma_t$，状态转移矩阵$A$,回到上一状态$\sigma_{t-1}=A\sigma_t$，到达下一状态$\sigma_{t+1}=\sigma_tA$

概率计算算法—预测观测概率$\max\{P(O|\lambda)\}$

直接计算

$T$时间后到达某状态序列概率：$P(I|\lambda)=\pi a_{i_1i_2}a_{i_2i_3},\cdots,a_{i_{T-1}i_T}$

在$I$状态序列下，$T$时间后输出某观测序列$O=(o_1,o_2,\cdots,o_T)$的概率：$P(O|I,\lambda)=b_{i_1}(o_1)b_{i_2}(o_2)\cdots b_{i_T}(o_T)$

$\therefore$$T$时间后到达某状态序列$I$后输出某观测序列的概率为联合分布：

（加括号仅为表明每个观测的状态对位关系）

$\therefore$ 为了求得$T$时间后观测得指定观测序列$O=(o_1,o_2,\cdots,o_T)$的概率，需要边缘化联合概率公式中的$I$，$I=(i_1,i_2,\cdots,i_N),i_1,i_2,\cdots,i_t=1,2,\cdots,N$

$\therefore P(O|\lambda)=\sum_{i_1,i_2,\cdots,i_T}P(O,I|\lambda)=\sum_{i_1,i_2,\cdots,i_T}((\pi_{i_1} b_{i_1}(o_1)) (a_{i_1i_2}b_{i_2}(o_2)) \cdots(a_{i_{T-1}i_T}b_{i_T}(o_T))$

注意表示法$\sum_{i_1,i_2,\cdots,i_T},其中i_1,i_2,\cdots,i_t=1,2,\cdots,N$(每个状态$i_t$下都有$N$种取值)，意思是对所有可能的$I$序列取值组合，计算右边式子之后，再对所有式子结果求和

关系为$\lambda\to I\to O$，所以求$O$的时候可以看成一个全链接路径图或FC DNN

观察这个式子，对于$,i_1=1,2,\cdots,N$：

$t=1: P_1(O|\lambda)=\sum_{i_1}\pi_{i_1} b_{i_1}(o_1)=\pi_{q_1}b_{q_1}(o_1)+\pi_{q_2}b_{q_2}(o_1)+\cdots+\pi_{q_N}b_{q_N}(o_1)$

$t=2: P_2(O|\lambda)=\sum_{i_1,i_2}((\pi_{i_1} b_{i_1}(o_1))a_{i_1i_2}b_{i_2}(o_2)$

$=((\pi_{q_1}b_{q_1}(o_1))a_{q_1q_1}b_{q_1}(o_2)+((\pi_{q_1}b_{q_1}(o_1))a_{q_1q_2}b_{q_2}(o_2)+\cdots+((\pi_{q_1}b_{q_1}(o_1))a_{q_1q_N}b_{q_N}(o_2)+$​

$((\pi_{q_2}b_{q_2}(o_1))a_{q_2q_1}b_{q_1}(o_2)+((\pi_{q_2}b_{q_2}(o_1))a_{q_2q_2}b_{q_2}(o_2)+\cdots+((\pi_{q_2}b_{q_2}(o_1))a_{q_2q_N}b_{q_N}(o_2)+$

$\cdots+$

$((\pi_{q_N}b_{q_N}(o_1))a_{q_Nq_1}b_{q_1}(o_2)+((\pi_{q_N}b_{q_N}(o_1))a_{q_Nq_2}b_{q_2}(o_2)+\cdots+((\pi_{q_N}b_{q_N}(o_1))a_{q_Nq_N}b_{q_N}(o_2)$

$\cdots$

$t=T:\cdots$

这样算下去就很麻烦了，路径非常多，计算量非常大

结论：8行

前向算法

观测到式子中存在大量重复子式，如$t=2$时，重复了在$t=1$中的子式$\pi_{q_1}b_{q_1}(o_1),\pi_{q_2}b_{q_2}(o_1),\cdots,\pi_{q_N}b_{q_N}(o_1)$各$N$次，于是想到可以用BP一样的解决办法，即

核心思想：可以观察到计算图如同一张全连接的深度神经网络，状态空间维度$N$即为每层隐藏神经元个数，时间序列运行时间$T$即为网络深度，于是我们只要保存每一个结点的计算结果，就可以大幅减少计算量

于是可以写出算法：

定义到时刻$t$部分观测序列为$o_1,o_2,\cdots,o_t$且状态为$q_i$的概率为前向概率：

$\alpha_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i|\lambda)$

初始值：$\alpha_1(i)=\pi_ib_i(o_1),i=1,2,\cdots,N$

递推式：$\alpha_{t+1}(i)=[\sum^N_{j=1}\alpha_t(j)\alpha_{ji}]b_i(o_{t+1}),i=1,2,\cdots,N$

终止：$P(O|\lambda)=\sum^N_{i=1}\alpha_T(i)$

很像DNN的前向传递

前向算法最小结构就是当前时刻所有状态$i_t$转移到下一时刻的某状态$i_{t+1}$，有$N$个这一时刻的状态$i_t$，1个下一时刻的某状态$i_{t+1}$和1个对下一时刻状态的观测$b_i(o_{t+1})$（观测是先验）

注意一个理解：整个概率的计算是在时间$t$过程的前向转播中不断迭代产生的，每一个结点的计算都包含了全路径状态的转移概率和某一时刻的先验观测概率，所以完整的先验需要运行整个过程。当在$t=T$，最后一层结点计算完的时候，那么再对全状态路径求和才能求得先验$O=(o_1,o_2,\cdots,o_T)$下的概率。若对所有可能存在的观测序列$O$计算那必然$P(O|\lambda)=1$。

后向算法

同理

定义在时刻$t$状态为$q_i$的条件下，从$t+1$到$T$的部分观测序列$o_{t+1},o_{t+2},\cdots,o_T$的概率为后向概率：

$\beta_t(i)=P(o_{t+1},o_{t+2},\cdots,o_T|i_t=q_i,\lambda)$

初始值：$\beta_T(i)=1,i=1,2,\cdots,N$

递推式：$\beta_{t}(i)=\sum^N_{j=1}a_{ij}b_j(o_{t+1})\beta_{t+1}(j),i=1,2,\cdots,N$

终止：$P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)$

很像DNN的反向传递…

后向算法最小结构就是下一时刻的所有状态$i_{t+1}$回退到当前时刻某状态$i_{t}$，有1个这一时刻的某状态$i_t$，有$N$个下一时刻的状态$i_{t+1}$，和$N$个对下一时刻状态的观测$b_j(o_{t+1})$（观测是先验）

同理，整个概率的计算是在时间$t$过程的后向转播中不断迭代产生的，这个先验需要运行整个过程，只不过这个过程是反着运行的。

其它应用

利用前向概率与后向概率的定义，可以将观测序列概率统一可写成：

$P(O|\lambda)=\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j),t=1,2,\cdots,T-1$

式中$\alpha_t(i)$即为$i$状态下$t$时刻以前的概率，$\beta_{t+1}(j)$即为$i$状态下$t+1$时刻以后的概率，这个式子等于枚举出了网络中所有的路径

  1. 给定模型$\lambda$和观测$O$，求在时刻$t$处于状态$q_i$的概率$\gamma_t(i)$

    记$\gamma_t(i)=P(i_t=q_i|O,\lambda)=\frac{P(i_t=q_i,O|\lambda)}{P(O|\lambda)}$

    由前向概率和后向概率定义可得

    $\alpha_t(i)\beta_t(i)=P(o_1,o_2,\cdots,o_t,i_t=q_i|\lambda)*P(o_{t+1},o_{t+2},\cdots,o_T|i_t=q_i,\lambda)=P(i_t=q_i,O|\lambda)$

    $\therefore \gamma_t(i)=P(i_t=q_i|O,\lambda)=\frac{P(i_t=q_i,O|\lambda)}{P(O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{P(O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum^N_{j=1}\alpha_t(j)\beta_t(j)}$

    对各个时刻求和，于是可以求出在观测$O$下状态$i$出现的期望值$=\sum_{t=1}^T \gamma_t(i)$

    同理，在观测$O$下由状态$i$转移的期望值$=\sum_{t=1}^{T-1} \gamma_t(i)$

  2. 给定模型$\lambda$和观测$O$，在时刻$t$处于状态$q_i$且在时刻$t+1$处于状态$q_j$的概率$\epsilon_t(i,j)$

    $\epsilon_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,\lambda)=\frac{P(i_t=q_i,i_{t+1}=q_j,O|\lambda)}{P(O|\lambda)}=\frac{P(i_t=q_i,i_{t+1}=q_j,O|\lambda)}{\sum^N_{i=1}\sum^N_{j=1}P(i_t=q_i,i_{t+1}=q_j,O|\lambda)}$

    由于$P(i_t=q_i,i_{t+1}=q_j,O|\lambda)=\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)$

    $\therefore \epsilon_t(i,j)=P(i_t=q_i,i_{t+1}=q_j|O,\lambda)=\frac{P(i_t=q_i,i_{t+1}=q_j,O|\lambda)}{P(O|\lambda)}=\frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{\sum^N_{i=1}\sum^N_{j=1}\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}$

    在观测$O$下由状态$i$转移到状态$j$的期望值$=\sum_{t=1}^{T-1} \epsilon_t(i,j)$

赏

且听风吟