隐马尔科夫模型(HMM)原理详解

　　隐马尔可夫模型（Hidden Markov Model，HMM）是可用于标注问题的统计学习模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。HMM在语音识别、自然语言处理、生物信息、模式识别等领域都有着广泛的应用。

一、 HMM模型的定义

    HMM模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列称为状态序列(state sequence)；每个状态生成一个观测，再由此产生的观测的随机序列，称为观测序列(observation sequence。序列的每一个位置可以看作是一个时刻。

    HMM模型由初始概率分布、状态转移概率分布、观测概率分布确定。设$Q$是所有可能的状态的集合，$V$是所有可能的观测的集合，即：

$Q=\left\{q_{1}, q_{2}, \cdots, q_{N}\right\}, \quad V=\left\{v_{1}, v_{2}, \cdots, v_{M}\right\}$

　　其中，$N$是可能的状态数，$M$是可能的观测数。记$I$是长度为$T$的状态序列，$O$是对应的观测序列，即：

$I=\left(i_{1}, i_{2}, \cdots, i_{T}\right), \quad O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)$

　　记$A$为状态转移概率矩阵：

$A=\left[a_{i j}\right]_{N \times N}$

　　其中，$a_{i j}=P\left(i_{t+1}=q_{j} | i_{t}=q_{i}\right), \quad i=1,2, \cdots, N ; j=1,2, \cdots, N$，即在时刻$t$处于状态​$q_{i}$的条件下在时刻$t+1$转移到状态​$q_{j}$的概率。

    记$B$观测概率矩阵：

$B=\left[b_{j}(k)\right]_{N \times \mu}$

　　其中，$b_{j}(k)=P\left(o_{t}=v_{k} | i_{t}=q_{j}\right), \quad k=1,2, \cdots, M ; j=1,2, \cdots, N$,$N$是在时刻$t$处于状态$q_{j}$的条件下生成观测$v_{k}$的概率。

    记$\pi $为初始状态概率向量：

$\pi=\left(\pi_{i}\right)$

　　其中，$\pi_{i}=P\left(i_{1}=q_{i}\right), \quad i=1,2, \cdots, N$，表示时刻$t=1$处于状态$q_{i}$的概率。

    因此，HMM模型$\lambda$可以用三元符号表示，即：

$\lambda=(A, B, \pi)$

　　$A, B, \pi$称为HMM模型的三要素。

 　　举例说明

　　假设有4个盒子，每个盒子都有红白两种颜色的球，球的数量如下:

　　盒子 1 2 3 4 　　红球数 5 3 6 8 　　白球数 5 7 4 2

　　按下面的方法抽取球:
　　开始时，从4个盒子中等概率地抽取一个，再从盒子中随机抽一个球，记录颜色后放回。然后从当前盒子转移到下一个盒子，如果当前为盒子1，下一个盒子一定是2；如果当前为盒子2或3，以概率0.4和0.6转移到左边或右边的盒子；如果当前为盒子4，各以0.5概率停留在盒子4或转移到盒子3。转移后，再从盒子中随机抽一个球，记录颜色后放回。
　　现在假设我们要连续地抽5次。抽取结果如下:

$O$=( 红 , 红 , 白 , 白 , 红 )

　　这个例子中有两个随机序列:
　　盒子序列（状态序列）和球颜色序列（观测序列）。前者是隐藏的，后者是可观测的。
　　则状态集合$Q$和观测集合$V$为:

$Q$=(盒子1,盒子2,盒子3,盒子4), 　　$V$=(红,白)

　　状态序列和观测序列长度T=5。
　　开始时，从4个盒子中等概率地抽取一个，则初始概率分布$\pi $为:

$\pi=(0.25,0.25,0.25,0.25)^{\mathrm{T}}$　　

　　状态转移概率分布$A$为（由盒子转移规则得出）:

　　观测概率分布$B$为（由每个盒子红白球比例计算得出）:

二、两个基本假设和三个基本问题

　　隐马尔可夫模型做了两个基本假设:

• 齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻t无关，即:
  $P\left(i_{t} | i_{t-1}, o_{t-1}, \cdots, i_{1}, o_{1}\right)=P\left(i_{t} | i_{t-1}\right), \quad t=1,2, \cdots, T$
  
• 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他的观测和状态无关，即:
  $P\left(o_{t} | i_{T}, o_{T}, i_{T-1}, o_{T-1}, \cdots, i_{t+1}, o_{t+1}, i_{t-1}, i_{t-1}, \cdots, i_{1}, o_{1}\right)=P\left(o_{t} | i_{t}\right)$

　　隐马尔可夫模型有3个基本问题: 

　　1、概率计算问题　　给定模型λ和观测序列$O$，计算在模型$\lambda $下观测序列$O$出现的慨率$P(O\mid \lambda)$。

　　2、学习问题　　已知观测序列$O$，估计模型$\lambda $的参数，使得在该模型下观测序列概率$P(O\mid \lambda)$最大。即用极大似然估计的方法估计参数。

　　3、预测问题，也称为解码问题　　已知模型λ和观测序列$O$，求对给定观测序列条件概率$P(I\mid O)$最大的状态序列。即给定观测序列，求最有可能的对应的状态序列。

 三、概率计算问题：概率计算方法 

     概率计算即给定模型$\lambda=(A, B, \pi)$和观测序列$O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)$，计算在模型$\lambda $下，观测序列$o$出现的概率$P(O | \lambda)$。

　　3.1 直接计算法

     直接计算法是通过列举所有可能的长度为$T$的状态序列$I=\left(i_{1}, i_{2}, \cdots, i_{T}\right)$，求各个状态序列I II和观测序列$O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)$的联合概率$P(O, I | \lambda)$，然后对所有可能的状态序列求和，得到$P(O | \lambda)$。

    状态序列$I=\left(i_{1}, i_{2}, \cdots, i_{T}\right)$的概率为：

$P(I | \lambda)=\pi_{i_{1}} a_{i_{1} i_{2}} a_{i_{2} i_{3}} \cdots a_{i_{T-1} i_{T}}$

　　对固定的状态序列$I=\left(i_{1}, i_{2}, \cdots, i_{T}\right)$，观测序列$O=\left(o_{1}, o_{2}, \cdots, o_{T}\right)$的概率为$P(O | I, \lambda)$：

$P(O | I, \lambda)=b_{i_{1}}\left(o_{1}\right) b_{i_{2}}\left(o_{2}\right) \cdots b_{i_{T}}\left(o_{T}\right)$

　　$O$和$I$同时出现的l联合概率为：

　　对所有可能的状态序列$I$求和，得到观测序列$O$的概率$P(O | \lambda)$，即：

　　但是，通过这种计算方式的计算量非常大，其复杂度为$O\left(T N^{r}\right)$，因此是不可行的。在真实情况下，一般采用更有效的算法，即前向-后向算法。