隐马尔可夫模型（HMM，Hidden Markov model）是关于时序的概率模型，描述由隐藏马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。
隐马尔可夫模型属于动态贝叶斯网，可用于标注问题的模型学习，属于生成模型，在语音识别、自然语言处理，生物信息等领域有着广泛应用。

1. 基本概念

1.1 标注问题

标注（Tagging）问题是分类问题的推广，又是更复杂的结构预测（structure prediction）问题的简单形式。

• 输入：观测序列
• 输出：标记序列或状态序列
• 目的：学习一个模型，使其能够对观测序列给出标记序列作为预测

标注问题针对训练集$D$D，$D=\{(\boldsymbol x^{(1)},\boldsymbol y^{(1)}), (\boldsymbol x^{(2)}, \boldsymbol y^{(2)}),...,(\boldsymbol x^{(m)},\boldsymbol y^{(m)})\}$D={(x(1),y(1)),(x(2),y(2)),...,(x(m),y(m))}输入观测序列：$\boldsymbol x^{(i)} = (x_1^{(i)}, x_2^{(i)}, ...,x_n^{(i)})^{T}，i={1,2,...,m}$x(i)=(x1(i)​,x2(i)​,...,xn(i)​)T，i=1,2,...,m输出标记序列：$\boldsymbol y^{(i)} = (y_1^{(i)}, y_2^{(i)}, ...,y_n^{(i)})^{T}，i={1,2,...,m}$y(i)=(y1(i)​,y2(i)​,...,yn(i)​)T，i=1,2,...,m$n$n是序列的长度，$m$m为样本个数，$n<<m$n<<m。

学习一个模型（条件概率分布）：$P(Y_1, Y_2, ...,Y_n \mid X_1, X_2, ...,X_n)$P(Y1​,Y2​,...,Yn​∣X1​,X2​,...,Xn​)
使得对于一个新的观测序列：$\boldsymbol x^{(m+1)}=(x_1^{(m+1)}, x_2^{(m+1)}, ...,x_n^{(m+1)})^{T}$x(m+1)=(x1(m+1)​,x2(m+1)​,...,xn(m+1)​)T
找到使条件概率$P((y_1^{(m+1)}, y_2^{(m+1)}, ...,y_n^{(m+1)})^{T} \mid x_1^{(m+1)}, x_2^{(m+1)}, ...,x_n^{(m+1)})^{T}$P((y1(m+1)​,y2(m+1)​,...,yn(m+1)​)T∣x1(m+1)​,x2(m+1)​,...,xn(m+1)​)T最大的标记序列$\boldsymbol y^{(m+1)}=(y_1^{(m+1)}, y_2^{(m+1)}, ...,y_n^{(m+1)})^{T}$y(m+1)=(y1(m+1)​,y2(m+1)​,...,yn(m+1)​)T

1.2 马尔可夫链

随机过程$x(t)$x(t)，在$t$t时刻的状态$i_t$it​，仅与$t-1$t−1时刻的状态$i_{t-1}$it−1​有关，即$P(i_t \mid i_{t-1},...,i_{1})=P(i_t \mid i_{t-1}),t=1,2,...T$P(it​∣it−1​,...,i1​)=P(it​∣it−1​),t=1,2,...T，该过程称为马尔可夫过程（Markov Process），又称马尔可夫链（Markov Chain）。

上图为一个马尔可夫链，可以看出$P(i_{t+1}=M_3 \mid i_t=M_2)=0.6,\;\;P(i_{t+1}=M_4 \mid i_t=M_2)=0.4$P(it+1​=M3​∣it​=M2​)=0.6,P(it+1​=M4​∣it​=M2​)=0.4

1.3 隐马尔可夫模型

隐藏的马尔可夫链随机生成的状态的序列，称为状态序列（state sequence）；
每个状态生成一个观测，由此产生的观测的随机序列，称为观测序列（observation sequence）；
序列的每个位置为一个时刻。

• 状态集合：$Q=\{q_1,q_2,...,q_N\}$Q={q1​,q2​,...,qN​}，$N$N是可能的状态数。
• 观测集合：$V=\{v_1,v_2,...,v_M\}$V={v1​,v2​,...,vM​}，$M$M是可能的观测数。
• 状态序列：$I=(i_1,i_2,...,i_T)$I=(i1​,i2​,...,iT​)，$T$T是状态序列的长度。
• 观测序列：$O=(o_1,o_2,...,o_T)$O=(o1​,o2​,...,oT​)。
  

（1）定义

隐马尔可夫模型$\lambda$λ由状态转移概率分布矩阵$A$A、观测概率矩阵$B$B及初始概率分布向量$\pi$π确定，可表示为$\lambda=(A,B,\pi)$λ=(A,B,π)。$\pi$π和$A$A决定状态序列，$B$B决定观测序列。

• 状态转移概率矩阵$A=[a_{ij}]_{N \times N}$A=[aij​]N×N​，其中$a_{ij}=P(i_{t+1}=q_j \mid i_t=q_i)，i=1,2,...,N;j=1,2,...,N$aij​=P(it+1​=qj​∣it​=qi​)，i=1,2,...,N;j=1,2,...,N是$t$t时刻$q_i$qi​状态下转移到$t+1$t+1时刻$q_j$qj​状态的概率。

• 观测概率矩阵$B=[b_{jk}]_{N \times M}$B=[bjk​]N×M​，其中$b_{jk}=P(o_t=v_k \mid i_t=q_j)，k=1,2,...,M;j=1,2,...,N$bjk​=P(ot​=vk​∣it​=qj​)，k=1,2,...,M;j=1,2,...,N是$t$t时刻$q_j$qj​状态下生成观测$v_k$vk​的概率。

• 初始状态概率向量$\pi = (\pi_i)$π=(πi​)，其中$\pi_i=P(i_1=q_i),i=1,2,...,N$πi​=P(i1​=qi​),i=1,2,...,N是$t=1$t=1时刻处于状态$q_i$qi​的概率。

根据定义，观测序列$O=(o_1,o_2,...,o_T)$O=(o1​,o2​,...,oT​)的生成过如下：

• Step1: 按照初始状态分布$\pi$π产生状态$i_1$i1​
• Step2: 令$t=1$t=1
• Step3: 按照状态$i_t$it​的观测概率分布$b_{i_t}(k)$bit​​(k)生成$o_t$ot​
• Step4: 按照状态$i_t$it​的转移概率分布$\{a_{i_t,i_{t+1}}\}${ait​,it+1​​}产生状态$i_{t+1}$it+1​
• Step5: 令$t=t+1$t=t+1，若$t<T$t<T，转至Step3；否则，终止

（2）两个基本假设

由定义可知，隐马尔可夫模型有两个基本假设：

• 齐次马尔可夫性假设：隐藏马尔可夫链任意$t$t时刻的状态$i_t$it​只依赖于$t-1$t−1时刻的状态$i_{t-1}$it−1​，与其他时刻的状态及观测无关，也与时刻$t$t无关，即

$P(i_t \mid i_{t-1},o_{t-1},...,i_{1},o_{1})=P(i_t \mid i_{t-1}),t=1,2,...T$P(it​∣it−1​,ot−1​,...,i1​,o1​)=P(it​∣it−1​),t=1,2,...T

• 观测独立性假设：任意$t$t时刻的观测$o_t$ot​只依赖于该时刻的马尔可夫链的状态$o_t$ot​，与其他观测即状态无关，即

$P(o_t \mid i_{T},o_{T},i_{T-1},o_{T-1}...,i_{t+1},o_{t+1},i_{t},i_{t-1},o_{t-1},...,i_{1},o_{1})=P(o_t \mid i_{t}),t=1,2,...T$P(ot​∣iT​,oT​,iT−1​,oT−1​...,it+1​,ot+1​,it​,it−1​,ot−1​,...,i1​,o1​)=P(ot​∣it​),t=1,2,...T

1.4 E.g.

按如下步骤，产生颜色序列：

• Step1：从4个盒子中等概率选取1个盒子，然后随机抽出1个球，记录颜色并放回
• Step2：按照如下规则选择盒子，从选定的盒子中抽出1个球，记录颜色并放回
  • 如果当前盒子是A：直接选择盒子B
  • 如果当前盒子是B或C：以0.4概率转移到左边盒子，0.6的概率转移到右边盒子
  • 如果当前盒子是D：以0.5的概率停留在盒子D，0.5的概率转移到盒子C

即按照如下马尔可夫链选择盒子：

如此重复$T$T次，得到颜色的观测序列。

该例子为一个隐马尔可夫模型，有两个随机序列：

• 状态序列：盒子的序列（隐藏的），长度为$T$T
• 观测序列：颜色的观测序列（可观测的），长度为$T$T
• 状态集合：$Q=\{A,B,C,D\}$Q={A,B,C,D}，状态数$N=4$N=4
• 观测集合：$V=\{红，白\}$V={红，白}，观测数$M=2$M=2
• 初始概率分布：$\pi = (0.25,0.25,0.25,0.25)$π=(0.25,0.25,0.25,0.25)
• 状态转移概率分布：$A = \begin{bmatrix} 0 && 1 && 0 &&0 \\ 0.4 && 0 && 0.6 &&0 \\ 0 && 0.4 && 0 &&0.6\\ 0 && 0 && 0.5 &&0.5\\ \end{bmatrix}$A=⎣⎢⎢⎡​00.400​​100.40​​00.600.5​​000.60.5​⎦⎥⎥⎤​
• 观测概率分布：$b = \begin{bmatrix} 0.5 && 0.5 \\ 0.3 && 0.7 \\ 0.6 && 0.4 \\ 0.8 && 0.2 \\ \end{bmatrix}$b=⎣⎢⎢⎡​0.50.30.60.8​​0.50.70.40.2​⎦⎥⎥⎤​
  其中，$b_{21}=P(o_t=v_1 \mid i_t=q_2)=P(o_t=红 \mid i_t= B)=0.3,j=2,k=1$b21​=P(ot​=v1​∣it​=q2​)=P(ot​=红∣it​=B)=0.3,j=2,k=1

表示$t$t时刻，B盒状态下生成观测为红球的概率为0.3。

2. 三个基本问题

2.1 概率计算问题

已知模型$\lambda=(A,B,\pi)$λ=(A,B,π)和观测序列$O=(o_1,o_2,...,o_T)$O=(o1​,o2​,...,oT​)，计算在模型$\lambda$λ下观测序列$O$O出现的概率$P(O \mid \lambda)$P(O∣λ)。采用前向（forward）与后向（backward）算法。

2.2 学习问题

已知观测序列$O=(o_1,o_2,...,o_T)$O=(o1​,o2​,...,oT​)，估计模型参数$(A,B,\pi)$(A,B,π)，即使得该模型下观测序列产生的概率$P(O \mid \lambda)$P(O∣λ)最大，可使用极大似然估计法估计参数。

如果将观测序列看做观测数据$O$O，而状态序列看做不可观测的隐数据$I$I，则隐马尔可夫模型可看做是一个含有隐变量的概率模型

$P(O \mid \lambda) = \sum_I P(O \mid I,\lambda)P(I \mid \lambda)$P(O∣λ)=I∑​P(O∣I,λ)P(I∣λ)可使用EM算法（Baum-Welch算法）实现隐马尔可夫模型的训练。

2.3 预测问题

已知模型$\lambda=(A,B,\pi)$λ=(A,B,π)和观测序列$O=(o_1,o_2,...,o_T)$O=(o1​,o2​,...,oT​)，计算使得条件概率$P(I \mid O)$P(I∣O)最大的状态序列$I=(i_1,i_2,...,i_T)$I=(i1​,i2​,...,iT​)，即给定观测序列，求对应的最可能的状态序列，又称解码问题。

维比特算法应用动态规划搞笑求解最优路径，即概率最大的状态路径。