隐马尔可夫模型（HMM）及其三个基本问题

隐马尔可夫模型的定义^[1]

隐马尔可夫模型（Hidden Markov Model，HMM）是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为状态序列；每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列，序列的每一个位置又可以看作是一个时刻。其形式定义如下：

$Q$是所有可能的状态的集合，$V$是所有可能的观测的集合：

$$Q=\{q_1,q_2,...,q_N\},V=\{v_1,v_2,...,v_M\}$$

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

$$I=(i_1,i_2,...,i_T),O=(o_1,o_2,...,o_T)$$

$A$是状态转移概率矩阵：

$$A=[a_{ij}]_{N\times N}$$

其中，$a_{ij}=P(i_{t+1}=q_j\vert i_t=q_i),\quad i=1,2,…,N;j=1,2,…,N$，表示在时刻$t$处于状态$q_i$的条件下在时刻$t+1$转移到状态$q_j$的概率。
$B$是观测概率矩阵：

$$B=[b_{jk}]_{N\times M}$$

其中，$b_{jk}=P(o_t=v_k\vert i_t=q_j),\quad j=1,2,…N;k=1,2,…,M$，表示在时刻$t$处于状态$q_j$的条件下生成观测$v_k$的概率。
$\pi$是初始状态概率向量：

$$\pi=(\pi_1,\pi_2,...,\pi_N)$$

其中，$\pi_i=P(i_1=q_i),\quad i=1,2,…,N$，表示时刻$t=1$时处于状态$q_i$的概率。
隐马尔可夫模型由初始状态概率向量$\pi$、状态转移概率矩阵$A$和观测概率矩阵$B$决定。$\pi$和$A$决定状态序列，$B$决定观测序列。因此，隐马尔可夫模型$\lambda$可以用三元符号表示，即：

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

$A,B,\pi$称为隐马尔可夫模型的三要素。
从定义可知，隐马尔可夫模型作了两个基本假设：

1. 齐次马尔可夫性假设，即假设隐藏的马尔可夫链在任意时刻$t$的状态只依赖于其前一时刻的状态，与其他时刻的状态及观测无关，也与时刻$t$无关： $$P(i_t\vert i_{t-1},o_{t-1},...,i_1,o_1)=P(i_t\vert i_{t-1})$$
2. 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态，与其他观测及状态无关： $$P(o_t\vert i_T,o_T,i_{T-1},o_{T-1},...,i_t,i_{t-1},o_{t-1},...,i_1,o_1)=P(o_t\vert i_t)$$

隐马尔可夫模型的三个基本问题

1. 概率计算问题：给定模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,…,o_T)$，计算在模型$\lambda$下观测序列$O$出现的概率$P(O\vert \lambda)$；
2. 学习问题：已知观测序列$O=(o_1,o_2,…,o_T)$，估计模型$\lambda=(A,B,\pi)$参数，使得在该模型下观测序列概率$P(O\vert \lambda)$最大，即用极大似然估计的方法估计参数；
3. 预测问题：也称为解码问题，已知模型$\lambda=(A,B,\pi)$和观测序列$O=(o_1,o_2,…,o_T)$，求对给定观测序列条件概率$P(I\vert O)$最大的状态序列$I=(i_1,i_2,…,i_T)$，即给定观测序列，求最有可能的对应状态序列。

概率计算问题

直接计算法

对于求$P(O\vert \lambda)$最直接的方法就是按照概率公式直接计算，即：

$$\begin{aligned} P(O\vert\lambda)&=\sum_{I}P(O,I\vert\lambda) \\ &=\sum_{I}P(O\vert I,\lambda)P(I\vert\lambda) \end{aligned}$$

其中，$P(I\vert \lambda)$表示给定模型参数时，产生状态序列$I=(i_1,i_2,…,i_T)$的概率：

$$P(I\vert \lambda)=\pi_{i_1}a_{i_1i_2}a_{i_2i_3}\cdots a_{i_{T-1}i_T}$$

$P(O\vert I,\lambda)$表示给定模型参数且状态序列为$I=(i_1,i_2,…,i_T)$时，产生观测序列$O=(o_1,o_2,…,o_T)$的概率：

$$P(O\vert I,\lambda)=b_{i_1o_1}b_{i_2o_2}...b_{i_To_T}$$

所以

$$\begin{aligned} P(O\vert\lambda)&=\sum_{I}P(O\vert I,\lambda)P(I\vert\lambda) \\ &=\sum_{i_1,i_2,...,i_T}\pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}\cdots a_{i_{T-1}i_T}b_{i_To_T} \end{aligned}$$

其中，$\sum_{i_1,i_2,…,i_T}$共有$N^T$种可能，计算$\pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}\cdots a_{i_{T-1}i_T}b_{i_To_T}$的时间复杂度为$O(T)$，所以上式整体的时间复杂度为$O(TN^T)$，显然这种算法是不可行的。

前向算法

首先定义前向概率：给定隐马尔可夫模型$\lambda$，定义到时刻$t$部分观测序列为$o_1,o_2,…,o_t$且状态为$q_i$的概率为前向概率，记作：

$$\alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i\vert \lambda)$$

根据前向概率的定义可推得：

$$P(O\vert \lambda)=\sum_{i=1}^{N}P(o_1,o_2,...,o_T,i_T=q_i\vert \lambda)=\sum_{i=1}^{N}\alpha_T(i)$$

于是求解$P(O\vert \lambda)$的问题被转化为了求解前向概率$\alpha_T(i)$的问题。由前向概率的定义可知：

$$\begin{aligned} \alpha_1(i)&=\pi_ib_{io_1} \\ \alpha_2(i)&=[\sum_{j=1}^{N}\alpha_1(j)a_{ji}]\times b_{io_2} \\ \alpha_3(i)&=[\sum_{j=1}^{N}\alpha_2(j)a_{ji}]\times b_{io_3} \\ \end{aligned}$$

依次此类推可得如下递推公式：

$$\alpha_{t+1}(i)=[\sum_{j=1}^{N}\alpha_t(j)a_{ji}]\times b_{io_{t+1}}$$

因此可以递推求得：

$$\alpha_{T}(i)=[\sum_{j=1}^{N}\alpha_{T-1}(j)a_{ji}]\times b_{io_{T}}$$

后向算法

同前向算法一样，首先定义后向概率：给定隐马尔可夫模型$\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\vert i_t=q_i,\lambda)$$

由后向概率的定义可知：

$$\begin{aligned} \beta_T(i)&=1 \\ \beta_{T-1}(i)&=\sum_{j=1}^{N}a_{ij}b_{jo_T}\beta_T(j) \\ \beta_{T-2}(i)&=\sum_{j=1}^{N}a_{ij}b_{jo_{T-1}}\beta_{T-1}(j) \\ \end{aligned}$$

依次类推可得递推公式：

$$\beta_t(i)=\sum_{j=1}^{N}a_{ij}b_{jo_{t+1}}\beta_{t+1}(j)$$

根据递推公式可求得$\beta_1(i)$，又

$$P(O\vert \lambda)=\sum_{i=1}^{N}\pi_ib_{io_1}\beta_1(i)$$

所以也可求得$P(O\vert \lambda)$。

综上可以看出前向算法和后向算法都是先计算局部概率，然后递推到全局，每一时刻的概率计算都会用上前一时刻计算出的结果，整体的时间复杂度大约为$O(TN^2)$，明显小于直接计算法的$O(TN^T)$。

利用前向概率和后向概率，可以得到关于单个状态和两个状态概率的一些计算公式：

1. 给定模型参数$\lambda$和观测$O$，在时刻$t$处于状态$q_i$的概率，记 $$\gamma_t(i)=P(i_t=q_i\vert O,\lambda)$$ 可以通过前向概率和后向概率进行计算，推导如下： $$\gamma_t(i)=P(i_t=q_i\vert O,\lambda)=\cfrac{P(i_t=q_i,O\vert \lambda)}{P(O\vert\lambda)}$$ 又由前向概率和后向概率的定义可知： $$\alpha_t(i)\beta_t(i)=P(i_t=q_i,O\vert\lambda)$$ 所以 $$\gamma_t(i)=\cfrac{P(i_t=q_i,O\vert \lambda)}{P(O\vert\lambda)}=\cfrac{P(i_t=q_i,O\vert \lambda)}{\sum_{j=1}^NP(i_t=q_j,O\vert \lambda)}=\cfrac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N\alpha_t(j)\beta_t(j)} \tag{A.1}$$
2. 给定模型参数$\lambda$和观测$O$，在时刻$t$处于状态$q_i$且在时刻$t+1$处于状态$q_j$的概率，记 $$\xi_t(i,j)=P(i_t=q_i,i_{t+1}=q_j\vert O,\lambda)$$ 可以通过前向后向概率进行计算，推导如下： $$\xi_t(i,j)=\cfrac{P(i_t=q_i,i_{t+1}=q_j,O\vert\lambda)}{P(O\vert\lambda)}=\cfrac{P(i_t=q_i,i_{t+1}=q_j,O\vert\lambda)}{\sum_{i=1}^N\sum_{j=1}^NP(i_t=q_i,i_{t+1}=q_j,O\vert\lambda)}$$ 而 $$P(i_t=q_i,i_{t+1}=q_j,O\vert\lambda)=\alpha_t(i)a_{ij}b_{jo_{t+1}}\beta_{t+1}(j)$$ 所以 $$\xi_t(i,j)=\cfrac{\alpha_t(i)a_{ij}b_{jo_{t+1}}\beta_{t+1}(j)}{\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_{jo_{t+1}}\beta_{t+1}(j)}\tag{A.2}$$

学习问题

监督学习方法

假设已给出训练数据包含$S$个长度相同的观测序列和对应的状态序列$\{(O_1,I_1),(O_2,I_2),…,(O_S,I_S)\}$，那么可以利用极大似然估计法来估计隐马尔可夫模型的参数，具体方法如下：

• 转移概率$a_{ij}$的估计： $$a_{ij}=\cfrac{A_{ij}}{\sum_{j=1}^NA_{ij}}$$ 其中，$A_{ij}$为样本中时刻$t$处于状态$q_i$而到时刻$t+1$转移到状态$q_j$的频数；
• 观测概率$b_{jk}$的估计： $$b_{jk}=\cfrac{B_{jk}}{\sum_{k=1}^MB_{jk}}$$ 其中，$B_{jk}$为样本中状态为$q_j$，其对应观测为$v_k$的频数；
• 初始状态概率$\pi_i$的估计为$S$个样本中初始状态为$q_i$的频率。

显然此训练数据中的状态序列数据通常是需要人工标注出来的，因此代价较高，所以非监督学习的方法更为实用，例如Baum-Welch算法。

Baum-Welch算法

如果只有观测序列数据$O=(o_1,o_2,…,o_T)$，而没有状态序列数据$I=(i_1,i_2,…,i_T)$，那么隐马尔可夫模型就是一个含有隐变量的概率模型：

$$P(O|\lambda)=\sum_I P(O\vert I,\lambda)P(I\vert \lambda)$$

如果要对它进行参数估计，则可以采用EM算法来实现，具体步骤如下：

1.确定完全数据的对数似然函数

此时观测数据为$O=(o_1,o_2,…,o_T)$，未观测数据为$I=(i_1,i_2,…,i_T)$，则完全数据为$(O,I)=(o_1,o_2,…,o_T,i_1,i_2,…,i_T)$，完全数据的对数似然函数为：

$$\ln P(O,I\vert \lambda)$$

其中，$P(O,I\vert \lambda)=\pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}\cdots a_{i_{T-1}i_T}b_{i_To_T}$，所以可以进一步推得：

$$\begin{aligned} \ln P(O,I\vert \lambda)&=\ln (\pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}\cdots a_{i_{T-1}i_T}b_{i_To_T}) \\ &=\ln \pi_{i_1} + \sum_{t=1}^{T-1}\ln a_{i_t i_{t+1}} + \sum_{t=1}^{T}\ln b_{i_t o_t} \\ \end{aligned}$$

2.EM算法E步：求$Q$函数$Q(\lambda,\bar{\lambda})$

$$Q(\lambda,\bar{\lambda})=\sum_I P(I\vert O,\bar{\lambda})\ln P(O,I\vert \lambda)$$

其中，$\bar{\lambda}$是隐马尔可夫模型参数的当前估计值，$\lambda$是要极大化的隐马尔可夫模型参数。为了便于后续计算，$Q$函数还可以作如下恒等变形：

$$\begin{aligned} Q(\lambda,\bar{\lambda})&=\sum_I P(I\vert O,\bar{\lambda})\ln P(O,I\vert \lambda) \\ &=\sum_I \cfrac{P(I\vert O,\bar{\lambda})P(O\vert\bar{\lambda})}{P(O\vert\bar{\lambda})}\ln P(O,I\vert \lambda) \\ &=\sum_I \cfrac{P(O,I\vert\bar{\lambda})}{P(O\vert\bar{\lambda})}\ln P(O,I\vert \lambda) \end{aligned}$$

由于接下来仅极大化$\lambda$，所以$P(O\vert\bar{\lambda})$可以看做常数项进行略去，所以$Q$函数可以进一步化简为：

$$\begin{aligned} Q(\lambda,\bar{\lambda})&=\sum_I P(O,I\vert\bar{\lambda})\ln P(O,I\vert \lambda) \\ &=\sum_I P(O,I\vert\bar{\lambda})\left(\ln \pi_{i_1} + \sum_{t=1}^{T-1}\ln a_{i_t i_{t+1}} + \sum_{t=1}^{T}\ln b_{i_t o_t}\right) \\ &=\sum_I P(O,I\vert\bar{\lambda})\ln \pi_{i_1} + \sum_I P(O,I\vert\bar{\lambda})\left(\sum_{t=1}^{T-1}\ln a_{i_t i_{t+1}}\right)+ \sum_I P(O,I\vert\bar{\lambda})\left(\sum_{t=1}^{T}\ln b_{i_t o_t}\right) \end{aligned}$$

3.EM算法M步：极大化$Q$函数

由于要极大化的参数在上式中单独地出现在3个项中，所以只需对各项分别极大化。

1. 上述$Q$函数中的第1项可以写成： $$\begin{aligned} \sum_I P(O,I\vert\bar{\lambda})\ln \pi_{i_1} &=\sum_{i=1}^N \left\{\ln\pi_{i}\cdot\left(\sum_{i_2,i_3,...,i_T} P(O,i_1=q_i,i_2,i_3,...,i_T\vert\bar{\lambda})\right)\right\} \\ &=\sum_{i=1}^N \left\{\ln\pi_{i}\cdot P(O,i_1=q_i\vert\bar{\lambda})\right\} \\ &=\sum_{i=1}^N\ln\pi_{i}P(O,i_1=q_i\vert\bar{\lambda}) \end{aligned}$$ 由于$\pi_i$需要满足约束$\sum_{i=1}^N\pi_i=1$，利用拉格朗日乘子法，写出拉格朗日函数： $$\sum_{i=1}^N\ln\pi_{i}P(O,i_1=q_i\vert\bar{\lambda})+\eta\left(\sum_{i=1}^N\pi_i-1\right)$$ 对其关于$\pi_i$求偏导并令结果为0： $$\cfrac{\partial}{\partial\pi_i}\left[\sum_{i=1}^N\ln\pi_{i}P(O,i_1=q_i\vert\bar{\lambda})+\eta\left(\sum_{i=1}^N\pi_i-1\right)\right]=0$$ 得 $$P(O,i_1=q_i\vert\bar{\lambda})+\eta\pi_i=0\tag{B.1}$$ 对上式关于$i$求和可得： $$\begin{aligned} \sum_{i=1}^N\left[P(O,i_1=q_i\vert\bar{\lambda})+\eta\pi_i\right]&=0 \\ \sum_{i=1}^NP(O,i_1=q_i\vert\bar{\lambda})+\sum_{i=1}^N\eta\pi_i&=0 \\ P(O\vert\bar{\lambda})+\eta\cdot 1&=0 \\ \end{aligned}$$ 解得 $$\eta=-P(O\vert\bar{\lambda})$$ 将其代回式（B.1）可得： $$P(O,i_1=q_i\vert\bar{\lambda})-P(O\vert\bar{\lambda})\cdot\pi_i=0$$ $$\pi_i = \cfrac{P(O,i_1=q_i\vert\bar{\lambda})}{P(O\vert\bar{\lambda})}$$ $$\pi_i=\gamma_1(i)$$ 其中，$\gamma_1(i)$由式（A.1）给出。
2. 上述$Q$函数中的第2项可以写成： $$\begin{aligned} \sum_I P(O,I\vert\bar{\lambda})\left(\sum_{t=1}^{T-1}\ln a_{i_t i_{t+1}}\right)&=\sum_{t=1}^{T-1}\left\{\sum_{i=1}^N\sum_{j=1}^N\left[\ln a_{ij}\cdot\left(\sum_{i_1,...,i_{t-1},i_{t+2},...,i_T}P(O,i_1,...,i_t=q_i,i_{t+1}=q_j,...,i_T\vert\bar{\lambda})\right)\right]\right\} \\ &=\sum_{t=1}^{T-1}\left\{\sum_{i=1}^N\sum_{j=1}^N\left[\ln a_{ij}\cdot P(O,i_t=q_i,i_{t+1}=q_j\vert\bar{\lambda})\right]\right\} \\ &=\sum_{t=1}^{T-1}\sum_{i=1}^N\sum_{j=1}^N\ln a_{ij}P(O,i_t=q_i,i_{t+1}=q_j\vert\bar{\lambda}) \end{aligned}$$ 由于$a_{ij}$满足约束$\sum_{j=1}^Na_{ij}=1$，同样利用拉格朗日乘子法，写出拉格朗日函数： $$\sum_{t=1}^{T-1}\sum_{i=1}^N\sum_{j=1}^N\ln a_{ij}P(O,i_t=q_i,i_{t+1}=q_j\vert\bar{\lambda})+\eta\left(\sum_{j=1}^Na_{ij}-1\right)$$ 对其关于$a_{ij}$求偏导并令结果为0： $$\cfrac{\partial}{\partial a_{ij}}\left[\sum_{t=1}^{T-1}\sum_{i=1}^N\sum_{j=1}^N\ln a_{ij}P(O,i_t=q_i,i_{t+1}=q_j\vert\bar{\lambda})+\eta\left(\sum_{j=1}^Na_{ij}-1\right)\right]=0$$ 得 $$\sum_{t=1}^{T-1}P(O,i_t=q_i,i_{t+1}=q_j\vert\bar{\lambda})+\eta a_{ij}=0\tag{B.2}$$ 对上式关于$j$求和可得： $$\begin{aligned} \sum_{j=1}^N\sum_{t=1}^{T-1}P(O,i_t=q_i,i_{t+1}=q_j\vert\bar{\lambda})+\sum_{j=1}^N\eta a_{ij}&=0 \\ \sum_{t=1}^{T-1}P(O,i_t=q_i\vert\bar{\lambda})+\eta\cdot 1&=0 \\ \end{aligned}$$ 解得： $$\eta=-\sum_{t=1}^{T-1}P(O,i_t=q_i\vert\bar{\lambda})$$ 将其代回式（B.2）可得： $$\sum_{t=1}^{T-1}P(O,i_t=q_i,i_{t+1}=q_j\vert\bar{\lambda})-\sum_{t=1}^{T-1}P(O,i_t=q_i\vert\bar{\lambda}) \cdot a_{ij}=0$$ $$a_{ij}=\cfrac{\sum_{t=1}^{T-1}P(O,i_t=q_i,i_{t+1}=q_j\vert\bar{\lambda})}{\sum_{t=1}^{T-1}P(O,i_t=q_i\vert\bar{\lambda})}$$ 分子分母同时除以$P(O|\bar{\lambda})$，所以 $$a_{ij}=\cfrac{\cfrac{\sum_{t=1}^{T-1}P(O,i_t=q_i,i_{t+1}=q_j\vert\bar{\lambda})}{P(O|\bar{\lambda})}}{\cfrac{\sum_{t=1}^{T-1}P(O,i_t=q_i\vert\bar{\lambda})}{P(O|\bar{\lambda})}}=\cfrac{\sum_{t=1}^{T-1}P(i_t=q_i,i_{t+1}=q_j\vert O,\bar{\lambda})}{\sum_{t=1}^{T-1}P(i_t=q_i\vert O,\bar{\lambda})}=\cfrac{\sum_{t=1}^{T-1}\xi_t(i,j)}{\sum_{t=1}^{T-1}\gamma_t(i)}$$ 其中，$\xi_t(i,j)$由式（A.2）给出，$\gamma_t(i)$由式（A.1）给出。
3. 上述$Q$函数中的第3项可以写成： $$\begin{aligned} \sum_I P(O,I\vert\bar{\lambda})\left(\sum_{t=1}^{T}\ln b_{i_t o_t}\right)&=\sum_{t=1}^{T}\left\{\sum_{j=1}^N\left[\ln b_{jo_t}\cdot\left(\sum_{i_1,...,i_{t-1},i_{t+1},...,i_T}P(O,i_1,...,i_t=q_j,...,i_T\vert\bar{\lambda})\right)\right]\right\} \\ &=\sum_{t=1}^{T}\left\{\sum_{j=1}^N\left[\ln b_{jo_t}\cdot P(O,i_t=q_j\vert\bar{\lambda})\right]\right\} \\ &=\sum_{t=1}^{T}\sum_{j=1}^N\ln b_{jo_t}P(O,i_t=q_j\vert\bar{\lambda}) \\ \end{aligned}$$ 由于$b_{jk}$满足约束$\sum_{k=1}^M b_{jk}=1$，同样利用拉格朗日乘子法，写出拉格朗日函数： $$\sum_{t=1}^{T}\sum_{j=1}^N\ln b_{jo_t}P(O,i_t=q_j\vert\bar{\lambda})+\eta\left(\sum_{k=1}^M b_{jk}-1\right)$$ 对其关于$b_{jk}$求偏导并令结果为0： $$\cfrac{\partial}{\partial b_{jk}}\left[\sum_{t=1}^{T}\sum_{j=1}^N\ln b_{jo_t}P(O,i_t=q_j\vert\bar{\lambda})+\eta\left(\sum_{k=1}^M b_{jk}-1\right)\right]=0$$ 得 $$\sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})\mathbb{I}(o_t=v_k)+\eta b_{jk}=0 \tag{B.3}$$ 其中，$\mathbb{I}(o_t=v_k)$为指示函数。对上式关于$k$求和可得： $$\begin{aligned} \sum_{k=1}^M\sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})\mathbb{I}(o_t=v_k)+\sum_{k=1}^M\eta b_{jk}&=0 \\ \sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})+\eta\cdot 1&=0 \end{aligned}$$ 解得： $$\eta=-\sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})$$ 将其代回式（B.3）可得： $$\sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})\mathbb{I}(o_t=v_k)-\sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})\cdot b_{jk}=0$$ $$b_{jk}=\cfrac{\sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})\mathbb{I}(o_t=v_k)}{\sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})}$$ 分子分母同时除以$P(O|\bar{\lambda})$，所以 $$b_{jk}=\cfrac{\cfrac{\sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})\mathbb{I}(o_t=v_k)}{P(O|\bar{\lambda})}}{\cfrac{\sum_{t=1}^{T}P(O,i_t=q_j\vert\bar{\lambda})}{P(O|\bar{\lambda})}}=\cfrac{\sum_{t=1}^{T}P(i_t=q_j\vert O,\bar{\lambda})\mathbb{I}(o_t=v_k)}{\sum_{t=1}^{T}P(i_t=q_j\vert O,\bar{\lambda})}=\cfrac{\sum_{t=1,o_t=v_k}^T\gamma_t(j)}{\sum_{t=1}^{T}\gamma_t(j)}$$ 其中，$\gamma_t(j)$由式（A.1）给出。

预测问题

近似算法

近似算法思想：在每个时刻$t$选择在该时刻最有可能出现的状态$i_t^*$，从而得到一个状态序列$I^*=(i_1^*,i_2^*,…,i_T^*)$，将它作为预测的结果。具体算法如下：

给定隐马尔可夫模型$\lambda$和观测序列$O$，在时刻$t$处于状态$q_i$的概率$\gamma_t(i)$是

$$\gamma_t(i)=\cfrac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^N\alpha_t(j)\beta_t(j)}$$

在每一时刻$t$最有可能的状态$i_t^*$是

$$i_t^*=\arg\max\limits_{1\leq i \leq N}[\gamma_t(i)],\quad t=1,2,...,T$$

从而得到状态序列$I^*=(i_1^*,i_2^*,…,i_T^*)$。

近似算法的优点是计算简单，其缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的序列可能有实际不发生的部分，也即可能存在状态转移概率$a_{i^*j^*}=0$的相邻状态$i^*$和$j^*$出现。尽管如此，近似算法仍然是有用的。

维特比算法

维特比（Viterbi）算法实际是用动态规划解隐马尔可夫模型预测问题，即用动态规划求概率最大路径，这时一条路径对应着一个状态序列。具体算法如下：

定义在时刻$t$状态为$q_i$的所有单个路径$(i_1,i_2,…,i_t)$中概率最大值为

$$\delta_t(i)=\max\limits_{i_1,i_2,..,i_{t-1}}P(o_1,...,o_t,i_1,...,i_{t-1},i_t=q_i),\quad i=1,2,...,N$$

由此定义可推得

$$\begin{aligned} \delta_1(i)&=\pi_ib_{io_1} \\ \delta_2(i)&=\max\limits_{1\leq j\leq N}[\delta_1(j)a_{ji}]b_{io_2} \\ \delta_3(i)&=\max\limits_{1\leq j\leq N}[\delta_2(j)a_{ji}]b_{io_3} \\ \end{aligned}$$

依次此类推可得如下递推公式：

$$\delta_{t}(i)=\max\limits_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}]b_{io_t}$$

同时再定义在时刻$t$状态为$q_i$的所有单个路径$(i_1,i_2,…,i_t)$中概率最大的路径的第$t-1$个结点为

$$\psi_t(i)=\arg\max\limits_{1\leq j\leq N}[\delta_{t-1}(j)a_{ji}]$$

因此，取$i_T^*=\arg\max\limits_{1\leq i\leq N}[\delta_T(i)]$，则$i_{T-1}^*=\psi_T(i_T^*),i_{T-2}^*=\psi_{T-1}(i_{T-1}^*),…,i_1^*=\psi_2(i_2^*)$，具体例子参见[1]第10章例10.3。

参考文献

[1] 李航.《统计学习方法》