HMM是一种结构简单的贝叶斯网络，主要用于时序数据建模，在语音识别，自然语言处理等领域有广泛应用。

一、HMM概述

1、HMM模型的网络结构

上图为HMM模型的结构，其中$[z_1,z_2,....,z_n]$是不可观测的状态序列；$[x_1,x_2,...,x_n]$为观测序列。$z_i$表示第$i$时刻的状态变量，取值为$[s_1,s_2,...,s_N]$；。$x_i$表示第$i$时刻的观测值，取值为$[o_1,o_2,...,o_M]$

2、HMM模型的三组参数
$$\lambda =[A,B,\pi ]$$

• $A=[a_{i,j}{]}_{N\ast N}$为状态转移矩阵。从前一个状态转移到后一个状态的概率。
  $$a_{i,j}=\mathrm{Pr}(z_{t+1}=s_j|z_t=s_i),1\le i,j\le N$$

• $B=[b_{i,j}{]}_{N\ast M}$为观测概率分布矩阵，在当前状态下取某个观测值的概率
  $$b_{i,j}=\mathrm{Pr}(x_t=o_j|z_t=s_i),1\le i\le N,1\le j\le M$$

• $\pi =[{\pi }_1,....,{\pi }_N]$为初始概率矩阵, 表示初始时刻各状态出现概率。
  $$\pi =\mathrm{Pr}(z_1=s_i),1\le i\le N$$

     注意：
     1、状态序列是离散的，观测序列可以是离散的，也可以是连续的。
     2、t观测值只与t时刻状态相关，t+1时刻状态值只与t时刻状态值相关
  

例子：HMM分词

假设我们相对如下这行话进行分词：

【欢迎来到我的博客】

上面有8个字，即8个时刻。
假设我们是这样分的：找到“终止字”，然后根据终止字来分词。即：对于这行字，“迎、到、我、的、客”是终止字，于是最终这么分词：欢迎/来到/我/的/博客。那么我们对每个字只需判断它是否为终止字，这就是所谓的隐变量。有$[s_1,s_2]$=[‘是终止字’,‘不是终止字’]

下面用上面的知识对这个例子建立HMM的$\lambda =[A,B,\pi ]$

• A 状态转移矩阵的确定：
  $$A=[a_{i,j}{]}_{2\ast 2},$$
  其中，$a_{i,j}=\mathrm{Pr}(z_{t+1}=s_j|z_t=s_i),1\le i,j\le 2.$

• B观测矩阵的确定：
  如果我们的目标文字使用Unicode编码，那么上面的任何一个字都是0~65535中的一个数，于是我们的观测就会是$[o_1,o_2,...,o_M],M=65536$，于是观测矩阵就是个2*M的矩阵，如下：
  $$B=[b_{i,j}{]}_{2\ast 65536}$$
  其中，$b_{i,j}=\mathrm{Pr}(x_t=o_j|z_t=s_i),1\le i\le N,1\le j\le M$

• $\pi$初始概率矩阵的确定
  $$\pi =[{\pi }_1，{\pi }_2]$$
  其中，${\pi }_i=P(z_1=s_i)，i=1,2$

       HMM怎么生成观测序列【欢迎来到我的博客】?
     假设有了 z1=“非终止字”这个状态，然后根据这个状态从65535个字中选出x1=“欢”这个字，然后根据状态转移矩阵，下一次转移到了Z2 =“终止字”，然后根据Z2从65535个字中选出了x2=“迎”这个字，这样，最终生成了这句话。
  

3、HMM模型关注的三个问题

• 1）概率计算问题：给定参数$\lambda$和观测序列$x=[x_1,x_2,...,x_n]$，计算$\mathrm{Pr}(x|\lambda )$。
  使用前向后向算法（动态规划）
• 2）学习问题：已知观测序列$x=[x_1,x_2,...,x_n]$，求解参数$\lambda$，使得$\mathrm{Pr}(x|\lambda )$最大，即求解$\underset{\lambda }{\mathrm{argmax}}\mathrm{Pr}(x|\lambda )$。
  采用Baum-Welch算法（EM）
• 3)预测问题：已知$\lambda$和观测序列$x=[x_1,x_2,...,x_n]$，求隐藏的状态序列的概率。即求$\mathrm{Pr}(z|x,\lambda )$，例已知参数和观测值，求每个字是不是终止字，这样就可以分词了啊。
  采用Viterbi算法（动态规划）

二、HMM关注的问题求解

1、概率计算问题

• 首先给出直接求解的方法，它的缺点是时间复杂度极高。
  (注意：下面的$x_i$代表的都是一个已知的具体的观测值，$[x_1,x_2,x_3]$=[红白红])
  

• 给出前向后向算法，时间复杂度极大地减小。
  下图给出了前向概率和后向概率的表示，${\alpha }_t(i)$为给定$\lambda$的条件下,计算时刻t观测值为i且观测值为$[y_1,y_2,...,y_t]$的前向概率。
  
  
  下面给出一道例题来直观理解前向算法的迭代过程
  

• 前向后向算法的关系
  $$\mathrm{Pr}(z_t=s_i,x|\lambda )={\alpha }_t(i){\beta }_t(i)$$

• 初步给出了预测问题的近似解。
  已知$\lambda$和观测序列$x=[x_1,x_2,...,x_n]$，求t时刻隐藏的状态序列的概率。即求${\gamma }_t(i)=\mathrm{Pr}(z_t=s_i|x,\lambda )$，它求的是单个状态的概率。
  $${\gamma }_t(i)=\frac{{\alpha }_t(i){\beta }_t(i)}{{\sum }_{i=1}^N{\alpha }_t(i){\beta }_t(i)}$$
  有了上式，我们可以根据观测序列和$\lambda$，求得每个字是否为"停止字"的概率，假设是的概率大于否的概率，则判定这个字是停止字，从而进行分词处理。

两个状态的联合概率分布${\xi }_t(i,j)=\mathrm{Pr}(z_t=s_i,z_{t+1}=s_j|x,\lambda )$

2、学习问题

• 给出观测序列和状态序列（监督学习）
  以HMM分词为例，你已经拿到了语料库，即有每个字的（B,M,E,S）四种状态。训练得到参数，在测试语料上分词。此时利用大数定律来学习参数$\lambda$
  
• 只给了观测序列（无监督学习）
  采用Baum-Welch算法（可以看成EM算法的推广）
  推导就是EM算法的E步（求Q）和M步（求参数），这里不做赘述。下图就是最终得到的算法。
  

3、预测问题
Viterbi算法
对比前向算法，发现只是把$\Sigma$换为$\max$

直观例题理解

当球为红白红时，三次从哪个盒子摸出的概率最大。

参考文章：参考文章