---

前言

隐马尔可夫模型是结构最简单的动态贝叶斯网，这是一种著名的有向图模型，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用。

---

一、基本概念

1、两组变量和三组参数

两组变量

• 状态变量$y_i$：隐藏的马尔可夫随机链生成的状态序列，不可观测
• 观测变量$x_i$：每个状态生成一个观测，由此产生观测的随机序列

两个基本假设：

• 观测独立性假设：
    图中的箭头表示了变量间的依赖关系。在任一时刻，观测变量的取值仅依赖于状态变量，即$x_t$由$y_t$确定，与其他状态变量及观测变量的取值无关。‘
• 齐次马尔可夫假设：
    同时，t时刻的状态$y_t$仅依赖于$t-1$时刻的状态$y_{t-1}$，与其余$n-2$个状态无关，这就是马尔科夫链，即：系统下一时刻的状态仅由当前状态确定，不依赖于以往的任何状态，基于这种依赖关系所有变量的联合概率分布为：
  

三组参数

• 状态转移概率：模型在各个状态间转换的概率，通常记为$A=[a_{ij}{]}_{N\times N}$，其中
  $$a_{ij}=P(y_{t+1}=s_j|y_t=s_i),1\le i,j\le N,$$
• 输出观测概率：模型根据当前状态获得各个观测值的概率，通常记为矩阵$B=[b_{ij}{]}_{N\times M}$
  $$b_{ij}=P(x_t=o_j|y_t=s_i),1\le i\le N,1\le j\le M$$
• 初始状态概率：模型在初始时刻各状态出现的概率，通常记为$\pi =({\pi }_1,{\pi }_2,...,{\pi }_n)$
  $${\pi }_i=P(y_1=s_i),1\le i\le N$$

通过指定状态空间$\mathcal{Y}$、观测空间$\mathcal{X}$和上述三个参数，就能确定一个隐马尔可夫模型，通过用其参数$\lambda =[A,B,pi]$来指代。给定隐马尔可夫模型$\lambda$，它按如下过程产生观测序列 { x 1 , x 2 , . . . , x n } \{x_1,x_2,...,x_n\} {x1​,x2​,...,xn​}：
（1）设置$t=1$，并根据初始状态概率$\pi$选择初始状态$y_1$;
（2）根据状态$y_t$和输出观测概率$B$选择观测变量取值$x_t$；
（3）根据状态$y_t$和状态转移矩阵$A$转移模型状态，即确定$y_{t+1}$；
（4）若$t<n$，设置 $t=t+1$，并转到第（2）步，否则停止。
其中 y t ∈ { s 1 , s 2 , . . . , s n } y_t\in \{s_1,s_2,...,s_n\} yt​∈{s1​,s2​,...,sn​}和 x t ∈ { o 1 , o 2 , . . . , o m } x_t\in \{o_1,o_2,...,o_m\} xt​∈{o1​,o2​,...,om​}分别为第 $t$时刻的状态和观测值。

2、三个基本问题

• 概率学习问题
  

• 预测问题（解码问题）
  

• 学习问题
  

二、概率计算问题

1、直接计算法（暴力穷举）

列举所有可能的长度为T的状态序列 y = { y 1 , y 2 , . . . , y T } y=\{y_1,y_2,...,y_T \} y={y1​,y2​,...,yT​}，求各个状态序列$x$与观测序列 x = { x 1 , x 2 , . . . , x T } x= \{x_1,x_2,...,x_T \} x={x1​,x2​,...,xT​}的联合概率$P(x,y|\lambda )$，然后对所有可能的状态序列求和，从而得到最终的概率$P(x|\lambda )$；

缺点：计算量非常庞大，$O(T{N}^T)$阶，不可行

2、前向算法

首先，定义前向概率：

前向概率：给定隐马科夫模型$\lambda$，定义到时刻$t$为止的观测序列为$o_1,o_2,......,o_t$且状态为$q_i$的概率为前向概率，记作
$${\alpha }_t(i)=P(o_1,o_2,......,o_t,i_t=q_i|\lambda )$$
可以递推地求得前向概率${\alpha }_t(i)$及观测序列概率$P(0|\lambda )$

• 输入：隐马尔科夫模型$\lambda$,观测序列$O$
• 输出：观测序列概率$P(O|\lambda )$
• 前向算法：

理解：

计算：每一次计算直接引用上一时刻的计算结果，避免重复计算，计算量是$O(N^{2}T)$阶。

3、后向算法

首先，定义后向概率：

后向概率：给定隐马科夫模型$\lambda$，定义在时刻$t$状态为$q_i$的条件下，从 $t+1$到$T$的部分观测序列为$o_{t+1},o_{t+2},......,o_T$的概率为后向概率，记作
$${\beta }_t(i)=P(o_{t+1},o_{t+2},......,o_T|i_t=q_i,\lambda )$$
可以递推地求得后向概率${\beta }_t(i)$及观测序列概率$P(0|\lambda )$

• 输入：隐马尔科夫模型$\lambda$,观测序列$O$
• 输出：观测序列概率$P(O|\lambda )$
• 后向算法：

理解：

三、预测问题

1、近似算法

2、维特比算法

  用动态规划求概率最大路径（最优路径），这时一条路径对应着一个状态序列。

理解

• 输入：隐马尔科夫模型$\lambda$,观测序列$O$
• 输出：最优路径$I^{\ast }=(i_1^{\ast },i_1^{\ast },...i_T^{\ast })$.
• 维特比算法：
  
  例子：

四、学习问题

1、监督学习算法

2、非监督学习算法

---

reference

[1]周志华-《机器学习》
[2]李航-《统计学习方法》
[3]02 隐马尔可夫模型 - HMM的三个问题 - 概率计算问题
[4]隐马尔科夫模型（HMM）一前向与后向算法