隐马尔可夫模型2021-08-20

隐马尔可夫模型

模型简介

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

HMM

模型定义

模型定义如下：

$Q$ $N$ $Q = \{q_1, q_2, ..., q_N \}$
$V$ $M$ $V = \{v_1, v_2, ..., v_N \}$
$I$ $I = \{i_1, i_2, ..., i_N \}$
$O$ $O = \{o_1, o_2, ..., o_N \}$
$A$ $A = \left [ a_{ij} \right ]_{N \times N}$ $a_{i j}=P\left(i_{t+1}=q_{j} \mid i_{t}=q_{i}\right), \quad i=1,2, \ldots, N ; j=1,2, \ldots, N$
$B$ $B = \left [ b_{jk} \right ]_{N \times M}$ $b_{j k}=P\left(o_{t}=v_{k} \mid i_{t}=q_{j}\right), \quad j=1,2, \ldots, N ; k=1,2, \ldots, M$
$\pi$ $\pi = \left(\pi_i,\pi_2, \cdots, \pi_N \right)$ $\pi_i = P(i_1 = q_i), i=1,2,\cdots,N$

$\pi$ $A$ $B$ $\pi$ $A$ $B$ 隐马尔可夫模型 $\lambda$ $\lambda = (A, B, \pi)$ 。

两个基本假设

齐次马尔可夫性假设
$t$ $t$ 无关：
$\begin{matrix} (1) & P (i_{t} ∣ i_{t - 1}, o_{t - 1}, \dots, i_{1}, o_{1}) = P (i_{t} ∣ i_{t - 1}) \end{matrix}$
观测独立性假设
假设任意时刻的观测只依赖于该时刻马尔可夫链的状态，与其它观测及状态无关：
$\begin{matrix} (2) & P (o_{t} ∣ i_{T}, o_{T}, i_{T - 1}, o_{T - 1}, \dots, i_{t}, i_{t - 1}, o_{t - 1}, \dots, i_{1}, o_{1}) = P (o_{t} ∣ i_{t}) \end{matrix}$

观测独立性假设

三个基本问题

概率计算问题
$\lambda = (A,B,\pi)$ $O = (o_1, o_2, \cdots , o_T)$ $\lambda$ $O$ 出现的概率 $P(O\mid \lambda)$ 。
学习问题
$O = (o_1, o_2, \cdots , o_T)$ $\lambda = (A,B,\pi)$ 参数 $P(O \mid \lambda)$ 最大。
预测问题
$\lambda = (A,B,\pi)$ $O = (o_1, o_2, \cdots , o_T)$ $I = (i_1,i_2,\cdots,i_T)$ $P(I \mid O,\lambda)$ 最大。

概率计算问题

直接计算

\begin{matrix} (3) & \begin{aligned} P (O ∣ λ) & = \sum_{I} P (O, I ∣ λ) \\ = \sum_{I} P (O ∣ I, λ) P (I ∣ λ) \end{aligned} \end{matrix}

$P(I \mid \lambda)$ $I = (i_1,i_2,\cdots,i_T)$ 的概率：

\begin{matrix} (4) & P (I ∣ λ) = π_{i_{1}} a_{i_{1} i_{2}} a_{i_{2} i_{3}} \dots a_{i_{T - 1} i_{T}} \end{matrix}

$P(O \mid I,\lambda)$ $\lambda$ $I = (i_1,i_2,\cdots,i_T)$ $O = (o_1, o_2, \cdots , o_T)$ 的概率：

\begin{matrix} (5) & P (O ∣ I, λ) = b_{i_{1} o_{1}} b_{i_{2} o_{2}} \dots b_{i_{T} o_{T}} \end{matrix}

因此：

\begin{matrix} (6) & \begin{aligned} P (O ∣ λ) & = \sum_{I} P (O, I ∣ λ) \\ = \sum_{I} P (O ∣ I, λ) P (I ∣ λ) \\ = \sum_{i_{1}, i_{2}, \dots, i_{T}} π_{i_{1}} b_{i_{1} o_{1}} a_{i_{1} i_{2}} b_{i_{2} o_{2}} \dots a_{i_{T - 1} i_{T}} b_{i_{T} o_{T}} \end{aligned} \end{matrix}

接下来，对该式进行算法复杂度分析：

$\large \sum_{i_{1}, i_{2}, \ldots, i_{T}}$ $N^T$ $O(N^T)$
$\large \pi_{i_{1}} b_{i_{1} o_{1}} a_{i_{1} i_{2}} b_{i_{2} o_{2}} \cdots a_{i_{T-1} i_{T}} b_{i_{T} o_{T}}$ $O(T)$
$O(TN^T)$ ，指数级复杂度，实际中不可行。

前向计算

$\lambda$ $t$ $(o_1,o_2,\cdots,o_t)$ $q_i$ 的概率为前向概率，记作：

\begin{matrix} (7) & α_{t} (i) = P (o_{1}, o_{2}, \dots, o_{t}, i_{t} = q_{i} ∣ λ) \end{matrix}

前向概率

对前向概率推导得：

\begin{matrix} (8) & \begin{aligned} α_{t} (i) & = P (o_{1}, o_{2}, \dots, o_{t}, i_{t} = q_{i} ∣ λ) \\ = P (i_{t} = q_{i}, o_{1}^{t}) \\ = \sum_{j = 1}^{N} P (i_{t - 1} = q_{j}, i_{t} = q_{i}, o_{1}^{t - 1}, o_{t}) \\ = \sum_{j = 1}^{N} P (i_{t} = q_{i}, o_{t} ∣ i_{t - 1} = q_{j}, o_{1}^{t - 1}) \cdot P (i_{t - 1} = q_{j}, o_{1}^{t - 1}) \\ = \sum_{j = 1}^{N} P (i_{t} = q_{i}, o_{t} ∣ i_{t - 1} = q_{j}) \cdot α_{t - 1} (j) \\ = \sum_{j = 1}^{N} P (o_{t} ∣ i_{t} = q_{i}, i_{t - 1} = q_{j}) \cdot P (i_{t} = q_{i} ∣ i_{t - 1} = q_{j}) \cdot α_{t - 1} (j) \\ = \sum_{j = 1}^{N} P (o_{t} ∣ i_{t} = q_{i}) \cdot P (i_{t} = q_{i} ∣ i_{t - 1} = q_{j}) \cdot α_{t - 1} (j) \\ = \sum_{j = 1}^{N} b_{i o_{t}} \cdot a_{j i} \cdot α_{t - 1} (j) \\ = \sum_{j = 1}^{N} [a_{j i} \cdot α_{t - 1} (j)] \cdot b_{i o_{t}} \\ 其 中 ， & i = (1, 2, \dots, N), t = (2, 3, \dots, T) \end{aligned} \end{matrix}

$\text{公式说明：因所有概率均在参数}\lambda \text{下计算，故从第二步开始，省略条件中的}\lambda$

因此，

\begin{matrix} (9) & α_{T} (i) = [\sum_{j = 1}^{N} α_{T - 1} (j) a_{j i}] \times b_{i o_{T}} \end{matrix}

基于前向概率，可得观测序列的概率为：

\begin{matrix} (10) & P (O ∣ λ) = P (o_{1}, o_{2}, \dots, o_{T} ∣ λ) = \sum_{i = 1}^{N} P (o_{1}, o_{2}, \dots, o_{T}, i_{T} = q_{i} ∣ λ) = \sum_{i = 1}^{N} α_{T} (i) \end{matrix}

根据上述推导，可得通过前向算法计算观测概率的算法如下：

$\text { 算法 } \mathbf{1. 0} \text { (观测序列概率的前向算法） }$

$\text { 输入：隐马尔可夫模型 } \lambda, 观测序列O$

$\text { 输出：观测序列概率 } P(O \mid \lambda)$

$\text{ 初值：} \alpha_1(i) = P(o_1, i_1=q_i \mid \lambda) = P(o_1 \mid i_1=q_i,\lambda) \cdot P(i_1 = q_i \mid \lambda) = \pi_i \cdot b_{io_1}, i=1,2,\cdots , N$
$\text { 递推：} \large \alpha_t(i)=\sum_{j=1}^{N} \left [a_{j i} \cdot \alpha_{t-1}(j) \right ] \cdot b_{io_t}, i=1,2,\cdots , N, t=2,3,\cdots,T$
$\text{ 终止：} \large P(O \mid \lambda)=\sum_{i=1}^{N} \alpha_{T}(i)$

时间复杂度分析：

$\sum_{i=1}^{N} \sum_{j=1}^{N}$ $O(N^2)$
$O(T)$
$O(TN^2)$ ，相比直接计算，有很大提升。

后向计算

$\lambda$ $t$ $q_i$ $t+1$ $T$ $(o_{t+1}, o_{t+2},\cdots,o_T)$ 的概率为后向概率，记作：

\begin{matrix} (11) & β_{t} (i) = P (o_{t + 1}, o_{t + 2}, \dots, o_{T} ∣ i_{t} = q_{i}, λ) \end{matrix}

后向概率

对后向概率推导得：

\begin{matrix} (12) & \begin{aligned} β_{t} (i) & = P (o_{t + 1}, o_{t + 2}, \dots, o_{T} ∣ i_{t} = q_{i}, λ) \\ = \sum_{j = 1}^{N} P (o_{t + 1}, o_{t + 2}, \dots, o_{T}, i_{t + 1} = q_{j} ∣ i_{t} = q_{i}, λ) \\ = \sum_{j = 1}^{N} P (o_{t + 2}^{T}, o_{t + 1}, i_{t + 1} = q_{j} ∣ i_{t} = q_{i}, λ) \\ = \sum_{j = 1}^{N} P (o_{t + 2}^{T} ∣ i_{t} = q_{i}, λ, o_{t + 1}, i_{t + 1} = q_{j}) \cdot P (o_{t + 1}, i_{t + 1} = q_{j} ∣ i_{t} = q_{i}, λ) \\ = \sum_{j = 1}^{N} P (o_{t + 2}^{T} ∣ λ, i_{t + 1} = q_{j}) \cdot P (o_{t + 1} ∣ i_{t + 1} = q_{j}, i_{t} = q_{i}, λ) \cdot P (i_{t + 1} = q_{j} ∣ i_{t} = q_{i}, λ) \\ = \sum_{j = 1}^{N} β_{t + 1} (j) \cdot b_{j o_{t + 1}} \cdot a_{i j} \\ 其 中 ， & i = (1, 2, \dots, N), t = (1, 2, \dots, T - 1) \end{aligned} \end{matrix}

$\beta_{T}(i)=P\left(\varnothing \mid i_{T}=q_{i}, \lambda\right)=1$ 。

基于后向概率，可得观测序列的概率为：

\begin{matrix} (13) & P (O ∣ λ) = P (o_{1}, o_{2}, \dots, o_{T} ∣ λ) = \sum_{i = 1}^{N} P (o_{1}, i_{1} = q_{i} ∣ λ) P (o_{2}, o_{3}, \dots, o_{T} ∣ i_{1} = q_{i}, λ) = \sum_{i = 1}^{N} π_{i} b_{i o_{1}} β_{1} (i) \end{matrix}

根据上述推导，可得通过后向算法计算观测概率的算法如下：

$\text { 算法 } \mathbf{1. 1} \text { (观测序列概率的后向算法） }$

$\text { 输入：隐马尔可夫模型 } \lambda, 观测序列O$

$\text { 输出：观测序列概率 } P(O \mid \lambda)$

$\text{ 初值：} \beta_T(i) = 1, i=1,2,\cdots , N$
$\text { 递推：} \large \beta_t(i)=\sum_{j=1}^{N} \beta_{t+1}(j) \cdot b_{jo_{t+1}} \cdot a_{ij} 其中， i = (1,2,\cdots,N) , t = (T-1,T-2,\cdots,1)$
$\text{ 终止：} \large P(O \mid \lambda)=\sum_{i=1}^{N} \pi_{i} b_{i o_{1}} \beta_{1}(i)$

若干公式

$\times$ 后向概率
$\begin{matrix} (14) & \begin{aligned} α_{t} (i) β_{t} (i) & = P (o_{1}, o_{2}, \dots, o_{t}, i_{t} = q_{i} ∣ λ) P (o_{t + 1}, o_{t + 2}, \dots, o_{T} ∣ i_{t} = q_{i}, λ) \\ = P (o_{1}^{t}, i_{t} = q_{i} ∣ λ) \cdot P (o_{t + 1}^{T} ∣ i_{t} = q_{i}, λ) \\ = P (o_{1}^{t} ∣ i_{t} = q_{i}, λ) \cdot P (i_{t} = q_{i} ∣ λ) \cdot P (o_{t + 1}^{T} ∣ i_{t} = q_{i}, λ) \\ = P (o_{1}^{T} ∣ i_{t} = q_{i}, λ) \cdot P (i_{t} = q_{i} ∣ λ) \\ = P (i_{t} = q_{i}, O ∣ λ) \end{aligned} \end{matrix}$
$\lambda$ $O$ $t$ $q_i$ 的概率
$\begin{matrix} (15) & \begin{aligned} γ_{t} (i) & = P (i_{t} = q_{i} ∣ O, λ) \\ = \frac{P (i_{t} = q_{i}, O ∣ λ)}{P (O ∣ λ)} \\ = \frac{P (i_{t} = q_{i}, O ∣ λ)}{\sum_{j = 1}^{N} P (i_{t} = q_{j}, O ∣ λ)} \\ = \frac{α_{t} (i) β_{t} (i)}{\sum_{j = 1}^{N} α_{t} (j) β_{t} (j)} \end{aligned} \end{matrix}$
$\lambda$ $O$ $t$ $q_i$ $t+1$ $q_j$ 的概率

\begin{matrix} (16) & \begin{aligned} ξ_{t} (i, j) & = P (i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ O, λ) \\ = \frac{P (i_{t} = q_{i}, i_{t + 1} = q_{j}, O ∣ λ)}{P (O ∣ λ)} \\ = \frac{P (i_{t} = q_{i}, i_{t + 1} = q_{j}, O ∣ λ)}{\sum_{i = 1}^{N} \sum_{j = 1}^{N} P (i_{t} = q_{i}, i_{t + 1} = q_{j}, O ∣ λ)} \end{aligned} \end{matrix}

又因为：

\begin{matrix} (17) & \begin{aligned} P (i_{t} = q_{i}, i_{t + 1} = q_{j}, O ∣ λ) & = P (i_{t} = q_{i}, i_{t + 1} = q_{j}, o_{1}, o_{2}, \dots, o_{T} ∣ λ) \\ = P (i_{t} = q_{i}, i_{t + 1} = q_{j}, o_{1}^{t}, o_{t + 1}^{N} ∣ λ) \\ = P (i_{t} = q_{i}, o_{1}^{t} ∣ λ) P (i_{t + 1} = q_{j}, o_{t + 1}^{N} ∣ λ, i_{t} = q_{i}, o_{1}^{t}) \\ = P (i_{t} = q_{i}, o_{1}^{t} ∣ λ) P (i_{t + 1} = q_{j}, o_{t + 1}^{N} ∣ λ, i_{t} = q_{i}) \\ = P (i_{t} = q_{i}, o_{1}^{t} ∣ λ) P (i_{t + 1} = q_{j}, o_{t + 1}, o_{t + 2}^{N} ∣ λ, i_{t} = q_{i}) \\ = P (i_{t} = q_{i}, o_{1}^{t} ∣ λ) P (o_{t + 2}^{N} ∣ i_{t + 1} = q_{j}, o_{t + 1}, λ, i_{t} = q_{i}) P (i_{t + 1} = q_{j}, o_{t + 1} ∣ λ, i_{t} = q_{i}) \\ = P (i_{t} = q_{i}, o_{1}^{t} ∣ λ) P (i_{t + 1} = q_{j}, o_{t + 1} ∣ λ, i_{t} = q_{i}) P (o_{t + 2}^{N} ∣ i_{t + 1} = q_{j}, λ) \\ = α_{t} (i) a_{i j} b_{j o_{t + 1}} β_{t + 1} (j) \end{aligned} \end{matrix}

所以：

\begin{matrix} (18) & ξ_{t} (i, j) = \frac{α_{t} (i) a_{i j} b_{j o_{t + 1}} β_{t + 1} (j)}{\sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{t} (i) a_{i j} b_{j o_{t + 1}} β_{t + 1} (j)} \end{matrix}

学习问题

状态已知，观测已知

$S$ $\{ (O_1,I_1), (O_2,I_2) \cdots (O_S,I_S)\}$ ，那么可以利用极大似然估计法来估计隐马尔可夫模型的参数，具体方法如下：

$a_{i j}$ 的估计
$\begin{equation} \Large a_{i j}=\frac{A_{i j}}{\sum_{j=1}^{N} A_{i j}} \end{equation}$
$A_{i j}$ $t$ $q_i$ $t+1$ $q_j$ 的的频数。
$b_{j k}$ 的估计
$\begin{equation} \Large b_{j k}=\frac{B_{j k}}{\sum_{k=1}^{M} B_{j k}} \end{equation}$
$B_{j k}$ $q_j$ $v_k$ 的的频数。
$\pi_i$ 的估计
$q_i$ 的频率。

状态未知，观测已知

问题定义

$O = (o_1, o_2, \cdots, o_T)$ $I = (i_1, i_2, \cdots, i_T)$ ，那么隐马尔可夫模型就是一个含有隐变量的概率模型：

\begin{matrix} (19) & P (O ∣ λ) = \sum_{I} P (O ∣ I, λ) P (I ∣ λ) \end{matrix}

可使用EM算法对该问题进行参数求解，该算法亦称为Baum-Welch算法。

完全数据的对数似然

需要确定完全数据的对数似然函数。 $O = (o_1, o_2, \cdots, o_T)$ $I = (i_1, i_2, \cdots, i_T)$ $(O,I) = (o_1,i_1,o_2,i_2,\cdots,o_T,i_T)$ ，完全数据的对数似然函数为：

\begin{matrix} (20) & \ln P (O, I ∣ λ) \end{matrix}

$\large P(O, I \mid \lambda)=\pi_{i_{1}} b_{i_{1} o_{1}} a_{i_{1} i_{2}} b_{i_{2} o_{2}} \cdots a_{i_{T-1} i_{T}} b_{i_{T} o_{T}}$ ，所以可进一步得到：

\begin{matrix} (21) & \begin{aligned} \ln P (O, I ∣ λ) & = \ln (π_{i_{1}} b_{i_{1} o_{1}} a_{i_{1} i_{2}} b_{i_{2} O_{2}} \dots a_{i_{T - 1} i_{T}} b_{i_{T} o_{T}}) \\ = \ln π_{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} \end{matrix}

$Q$ 函数

$Q$ 函数如下：

\begin{matrix} (22) & Q (λ, \bar{λ}) = \sum_{I} P (I ∣ O, \bar{λ}) \ln P (O, I ∣ λ) \end{matrix} 其中， \bar{λ} 是隐马尔可夫模型参数的当前估计值， λ 是 要 极 大 化 的 隐 马 尔 可 夫 模 型 参 数 。

$Q$ 函数做如下恒等变形：

\begin{matrix} (23) & \begin{aligned} Q (λ, \bar{λ}) & = \sum_{I} P (I ∣ O, \bar{λ}) \ln P (O, I ∣ λ) \\ = \sum_{I} \frac{P (O, I ∣ \bar{λ})}{P (O ∣ \bar{λ})} \ln P (O, I ∣ λ) \end{aligned} \end{matrix}

$\lambda$ $P(O \mid \bar{\lambda})$ $Q$ 函数可以进一步简化为：

\begin{matrix} (24) & \begin{aligned} Q (λ, \bar{λ}) & = \sum_{I} P (O, I ∣ \bar{λ}) \ln P (O, I ∣ λ) \\ = \sum_{I} P (O, I ∣ \bar{λ}) (\ln π_{i_{1}} + \sum_{t = 1}^{T - 1} \ln a_{i_{t} i_{t + 1}} + \sum_{t = 1}^{T} \ln b_{i_{t} o_{t}}) \\ = \sum_{I} P (O, I ∣ \bar{λ}) \ln π_{i_{1}} + \sum_{I} P (O, I ∣ \bar{λ}) (\sum_{t = 1}^{T - 1} \ln a_{i_{t} i_{t + 1}}) + \sum_{I} P (O, I ∣ \bar{λ}) (\sum_{t = 1}^{T} \ln b_{i_{t} o_{t}}) \end{aligned} \end{matrix}

$Q$ 函数

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

$\pi_i$
$Q$ 函数中的第1项可以写成：
$\begin{matrix} (25) & \begin{aligned} \sum_{I} P (O, I ∣ \bar{λ}) \ln π_{i_{1}} & = \sum_{i_{1}, i_{2}, \dots, i_{T}} P (O, i_{1}, i_{2}, \dots, i_{T} ∣ \bar{λ}) \ln π_{i_{1}} \\ = \sum_{i = 1}^{N} (\sum_{i_{2}, i_{3}, \dots, i_{T}} P (O, i_{1} = q_{i}, i_{2}, i_{3}, \dots, i_{T} ∣ \bar{λ}) \ln π_{i}) \\ = \sum_{i = 1}^{N} {\ln π_{i} \cdot (\sum_{i_{2}, i_{3}, \dots, i_{T}} P (O, i_{1} = q_{i}, i_{2}, i_{3}, \dots, i_{T} ∣ \bar{λ}))} \\ = \sum_{i = 1}^{N} \ln π_{i} P (O, i_{1} = q_{i} ∣ \bar{λ}) \end{aligned} \end{matrix}$
$\pi$ $\sum_{i=1}^{N} \pi_i = 1$ ，利用拉格朗日乘子法，写出拉格朗日函数：
$\begin{matrix} (26) & \sum_{i = 1}^{N} \ln π_{i} P (O, i_{1} = q_{i} ∣ \bar{λ}) + η (\sum_{i = 1}^{N} π_{i} - 1) \end{matrix}$
$\pi$ 求偏导并令结果为0：
$\begin{matrix} (27) & \begin{matrix} \frac{\partial}{\partial π_{i}} [\sum_{i = 1}^{N} \ln π_{i} P (O, i_{1} = q_{i} ∣ \bar{λ}) + η (\sum_{i = 1}^{N} π_{i} - 1)] = 0 \\ \frac{1}{π_{i}} \cdot P (O, i_{1} = q_{i} ∣ \bar{λ}) + η = 0 \\ P (O, i_{1} = q_{i} ∣ \bar{λ}) + η π_{i} = 0 \end{matrix} \end{matrix}$
$\sum_{i=1}^{N} \pi_i = 1$ $i$ 求和可得：
$\begin{matrix} (28) & \begin{matrix} \sum_{i = 1}^{N} [P (O, i_{1} = q_{i} ∣ \bar{λ}) + η π_{i}] = 0 \\ \sum_{i = 1}^{N} P (O, i_{1} = q_{i} ∣ \bar{λ}) + \sum_{i = 1}^{N} η π_{i} = 0 \\ P (O ∣ \bar{λ}) + η \cdot 1 = 0 \\ η = - P (O ∣ \bar{λ}) \end{matrix} \end{matrix}$
$P\left(O, i_{1}=q_{i} \mid \bar{\lambda}\right)+\eta \pi_{i}=0$ 可得：
$\begin{matrix} (29) & \begin{matrix} P (O, i_{1} = q_{i} ∣ \bar{λ}) - P (O ∣ \bar{λ}) \cdot π_{i} = 0 \end{matrix} \end{matrix}$ $\begin{matrix} (30) & \begin{aligned} π_{i} & = \frac{P (O, i_{1} = q_{i} ∣ \bar{λ})}{P (O ∣ \bar{λ})} \\ = P (i_{1} = q_{i} ∣ O, \bar{λ}) \\ = γ_{1} (i) \\ = \frac{α_{1} (i) β_{1} (i)}{\sum_{j = 1}^{N} α_{1} (j) β_{1} (j)} \end{aligned} \end{matrix}$
$\text{其中，} \large \gamma_{1}(i)=\frac{\alpha_{1}(i) \beta_{1}(i)}{\sum_{j=1}^{N} \alpha_{1}(j) \beta_{1}(j)} \text{表示给定模型参数} \bar{\lambda} \text{和观测} O \text{，在时刻} t \text{处于状态} q_i \text{的概率。}$
$a_{i j}$
$Q$ 函数中的第2项可以写成：
$\begin{matrix} (31) & \begin{aligned} \sum_{I} P (O, I ∣ \bar{λ}) (\sum_{t = 1}^{T - 1} \ln a_{i_{i}, i_{t + 1}}) & = \sum_{t = 1}^{T - 1} (\sum_{i_{i}, i_{2}, \dots, i_{T}} P (O, i_{1}, i_{2}, \dots, i_{T} ∣ \bar{λ}) \ln a_{i_{i} i_{+ 1}}) \\ = \sum_{t = 1}^{T - 1} {\sum_{i = 1}^{N} \sum_{j = 1}^{N} (\sum_{i_{1}, i_{2}, \dots, i_{t - 1}, i_{t + 2}, \dots, i_{T}} P (O, i_{1}, i_{2}, \dots, i_{t} = q_{i}, i_{t + 1} = q_{j}, \dots, i_{T} ∣ \bar{λ}) \ln a_{i j})} \\ = \sum_{t = 1}^{T - 1} {\sum_{i = 1}^{N} \sum_{j = 1}^{N} [\ln a_{i j} \cdot (\sum_{i_{1}, i_{2}, \dots, i_{t - 1}, i_{t + 2}, \dots, i_{T}} P (O, i_{1}, i_{2}, \dots, i_{t} = q_{i}, i_{t + 1} = q_{j}, \dots, i_{T} ∣ \bar{λ}))]} \\ = \sum_{t = 1}^{T - 1} \sum_{i = 1}^{N} \sum_{j = 1}^{N} \ln a_{i j} P (O, i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ \bar{λ}) \end{aligned} \end{matrix}$
$a_{i j}$ $\sum_{j=1}^{N} a_{i j} = 1$ 的约束条件，同样需要利用拉格朗日乘子法，写出拉格朗日函数：
$\begin{matrix} (32) & \sum_{t = 1}^{T - 1} \sum_{i = 1}^{N} \sum_{j = 1}^{N} \ln a_{i j} P (O, i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ \bar{λ}) + η (\sum_{j = 1}^{N} a_{i j} - 1) \end{matrix}$
$a_{i j}$ 求偏导并令结果为0：
$\begin{matrix} (33) & \begin{matrix} \frac{\partial}{\partial a_{i j}} [\sum_{t = 1}^{T - 1} \sum_{i = 1}^{N} \sum_{j = 1}^{N} \ln a_{i j} P (O, i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ \bar{λ}) + η (\sum_{j = 1}^{N} a_{i j} - 1)] = 0 \\ \frac{1}{a_{i j}} \cdot \sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ \bar{λ}) + η = 0 \\ \sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ \bar{λ}) + η a_{i j} = 0 \end{matrix} \end{matrix}$
$\sum_{j=1}^{N} a_{i j} = 1$ ，对上式两边求和可得：
$\begin{matrix} (34) & \begin{matrix} \sum_{j = 1}^{N} \sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ \bar{λ}) + \sum_{j = 1}^{N} η a_{i j} = 0 \\ \sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i} ∣ \bar{λ}) + η \cdot 1 = 0 \\ η = - \sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i} ∣ \bar{λ}) \end{matrix} \end{matrix}$
$\sum_{t=1}^{T-1} P\left(O, i_{t}=q_{i}, i_{t+1}=q_{j} \mid \bar{\lambda}\right)+\eta a_{i j}=0$ 可得：
$\begin{matrix} (35) & \begin{matrix} \sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ \bar{λ}) - \sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i} ∣ \bar{λ}) \cdot a_{i j} = 0 \\ a_{i j} = \frac{\sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i}, i_{t + 1} = q_{j} \bar{λ})}{\sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i} ∣ \bar{λ})} \end{matrix} \end{matrix}$
$P(O \mid \bar{\lambda})$ 得：
$\begin{matrix} (36) & a_{i j} = \frac{\frac{\sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ \bar{λ})}{P (O ∣ λ)}}{\frac{\sum_{t = 1}^{T - 1} P (O, i_{t} = q_{i} ∣ \bar{λ})}{P (O ∣ λ)}} = \frac{\sum_{t = 1}^{T - 1} P (i_{t} = q_{i}, i_{t + 1} = q_{j} ∣ O, \bar{λ})}{\sum_{t = 1}^{T - 1} P (i_{t} = q_{i} ∣ O, \bar{λ})} = \frac{\sum_{t = 1}^{T - 1} ξ_{t} (i, j)}{\sum_{t = 1}^{T - 1} γ_{t} (i)} \end{matrix}$
$其中, \xi_{t}(i, j) =\frac{P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O \mid \lambda\right)}{\sum_{i=1}^{N} \sum_{j=1}^{N} P\left(i_{t}=q_{i}, i_{t+1}=q_{j}, O \mid \lambda\right)} 表示给定 \bar{\lambda} 和 O，在时刻 t 处于状态 q_i 且在时刻 t+1 处于 q_j 的概率。\\ \gamma_{t}(i) = \frac{\alpha_{t}(i) \beta_{t}(i) }{\sum_{j=1}^{N} \alpha_{t}(j) \beta_{t}(j) } 表示给定\bar{\lambda}和O，在时刻t处于状态q_i的概率。$
$b_{j k}$

$Q$ 函数中的第3项可以写成：

\begin{matrix} (37) & \begin{aligned} \sum_{I} P (O, I ∣ \bar{λ}) (\sum_{t = 1}^{T} \ln b_{i_{1} o_{t}}) & = \sum_{t = 1}^{T} (\sum_{i_{1}, i_{2}, \dots, i_{T}} P (O, i_{1}, i_{2}, \dots, i_{T} ∣ \bar{λ}) \ln b_{i_{i} o t}) \\ = \sum_{t = 1}^{T} {\sum_{j = 1}^{N} (\sum_{i_{1}, i_{2}, \dots, i_{t - 1}, i_{t + 1}, \dots, i_{T}} P (O, i_{1}, i_{2}, \dots, i_{t} = q_{j}, \dots, i_{T} ∣ \bar{λ}) \ln b_{j o t})} \\ = \sum_{t = 1}^{T} {\sum_{j = 1}^{N} [\ln b_{j o_{t}} \cdot (\sum_{i_{1}, i_{2}, \dots, i_{t - 1}, i_{t + 1}, \dots, i_{T}} P (O, i_{1}, i_{2}, \dots, i_{t} = q_{j}, \dots, i_{T} ∣ \bar{λ}))]} \\ = \sum_{t = 1}^{T} \sum_{j = 1}^{N} \ln b_{j o_{t}} P (O, i_{t} = q_{j} ∣ \bar{λ}) \end{aligned} \end{matrix}

$b_{j k}$ $\sum_{k=1}^{M} b_{j k} = 1$ ，同样利用拉格朗日乘子法，写出拉格朗日函数：

\begin{matrix} (38) & \sum_{t = 1}^{T} \sum_{j = 1}^{N} \ln b_{j o_{t}} P (O, i_{t} = q_{j} ∣ \bar{λ}) + η (\sum_{k = 1}^{M} b_{j k} - 1) \end{matrix}

$b_{j k}$ 求偏导并令结果为0：

\begin{matrix} (39) & \begin{aligned} \frac{\partial}{\partial b_{j k}} [\sum_{t = 1}^{T} \sum_{j = 1}^{N} \ln b_{j o_{t}} P (O, i_{t} = q_{j} ∣ \bar{λ}) + η (\sum_{k = 1}^{M} b_{j k} - 1)] = 0 \\ \frac{1}{b_{j k}} \cdot \sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ}) I (o_{t} = v_{k}) + η = 0 (其中, I (o_{t} = v_{k}) 为指示函数) \\ \sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ}) I (o_{t} = v_{k}) + η b_{j k} = 0 \end{aligned} \end{matrix}

$\sum_{k=1}^{M} b_{j k} = 1$ $k$ 求和可得：

\begin{matrix} (40) & \begin{aligned} \sum_{k = 1}^{M} \sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ}) I (o_{t} = v_{k}) + \sum_{k = 1}^{M} η b_{j k} = 0 \\ \sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ}) + η \cdot 1 = 0 \\ η = - \sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ}) \end{aligned} \end{matrix}

$公式说明：\sum_{k=1}^{M} \sum_{t=1}^{T} P\left(O, i_{t}=q_{j} \mid \bar{\lambda}\right) \mathbb{I}\left(o_{t}=v_{k}\right) = \sum_{t=1}^{T} P\left(O, i_{t}=q_{j} \mid \bar{\lambda}\right)的原因：每一时刻的o_t必然属于且仅属于v_k(k=1,\cdots,M)中的一个。\\ 将v_k遍历一遍，所有时刻的o_t必然且仅能满足一次o_t=v_k。$

$\sum_{t=1}^{T} P\left(O, i_{t}=q_{j} \mid \bar{\lambda}\right) \mathbb{I}\left(o_{t}=v_{k}\right)+\eta b_{j k}=0$ 可得：

\begin{matrix} (41) & \begin{matrix} \sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ}) I (o_{t} = v_{k}) - \sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ}) \cdot b_{j k} = 0 \\ b_{j k} = \frac{\sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ}) I (o_{t} = v_{k})}{\sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ})} \end{matrix} \end{matrix}

$P(O \mid \bar{\lambda})$ ：

\begin{matrix} (42) & \begin{aligned} b_{j k} & = \frac{\frac{\sum_{t = 1}^{T} P (O, i_{t} = q_{j} ∣ \bar{λ}) I (o_{t} = v_{k})}{P (O ∣ \bar{λ})}}{\frac{\sum_{t = 1}^{T} P (O, i_{t} = q_{j} \bar{λ})}{P (O ∣ \bar{λ})}} \\ = \frac{\sum_{t = 1}^{T} P (i_{t} = q_{j} ∣ O, \bar{λ}) I (o_{t} = v_{k})}{\sum_{t = 1}^{T} P (i_{t} = q_{j} ∣ O, \bar{λ})} \\ = \frac{\sum_{t = 1, o_{t} = v_{k}}^{T} γ_{t} (j)}{\sum_{t = 1}^{T} γ_{t} (j)} \end{aligned} \end{matrix}

$其中，\large \gamma_{t}(i) = \frac{\alpha_{t}(i) \beta_{t}(i) }{\sum_{j=1}^{N} \alpha_{t}(j) \beta_{t}(j) } 表示给定\bar{\lambda}和O，在时刻t处于状态q_i的概率。$

预测问题

贪心算法

$t$ $i_t^*$ $I^* = (i_1^*,i_2^*,\cdots,i_T^*)$ ，将它作为预测的结果。具体算法那如下：

$\text { 算法 } \mathbf{1. 2} \text { (贪心算法预测状态序列） }$

$\text { 输入：隐马尔可夫模型 } \lambda, 观测序列O$

$\text { 输出：状态序列 }I^* = (i_1^*,i_2^*,\cdots,i_T^*)$

$对时刻t=1,2,\cdots,T$
- $\text{计算在时刻}t \text{处于状态} q_i \text{的概率：} \gamma_{t}(i)=\frac{\alpha_{t}(i) \beta_{t}(i)}{\sum_{j=1}^{N} \alpha_{t}(j) \beta_{t}(j)}$
- $在时刻 t 最有可能的状态： i_{t}^{*}=\arg \max _{1 \leq i \leq N}\left[\gamma_{t}(i)\right], \quad t=1,2, \ldots, T$
$得到状态序列 I^* = (i_1^*,i_2^*,\cdots,i_T^*)$

维特比算法

维特比算法：使用动态规划求解概率最大路径，每一条路径对应一个状态序列。具体算法如下：

$\text { 算法 } \mathbf{1. 3} \text { (维特比算法预测状态序列） }$

$\text { 输入：隐马尔可夫模型 } \lambda, 观测序列O$

$\text { 输出：状态序列 }I^* = (i_1^*,i_2^*,\cdots,i_T^*)$

$定义在时刻 t 状态为 q_i 的所有单个路径中概率最大值为： \\ \quad \delta_{t}(i)=\max _{i_{1}, i_{2}, \ldots, i_{t-1}} P\left(o_{1}, \ldots, o_{t}, i_{1}, \ldots, i_{t-1}, i_{t}=q_{i}\right), \quad i=1,2, \ldots, N$
- $在t=1时刻，可知：\delta_1(i) = \pi_i b_{io_1}$
- $对时刻t=1,2,\cdots,T \\ \quad \delta_{t}(i)=\max _{1 \leq j \leq N}\left[\delta_{t-1}(j) a_{j i}\right] b_{i o_{t}}, i=1,2,\cdots,N$
$定义在时刻 t 状态为 q_i 的所有单个路径中，概率最大的路径中的第t-1个节点为：\\ \quad \psi_{t}(i)=\arg \max _{1 \leq j \leq N}\left[\delta_{t-1}(j) a_{j i}\right]$
- $在T时刻，可知：i_{T}^{*}=\arg \max _{1 \leq i \leq N}\left[\delta_{T}(i)\right]$
- $在时刻t=T-1,T-2,\cdots,1 \\ \quad i_{t}^{*}=\psi_{t+1}\left(i_{t+1}^{*}\right)$
$得到状态序列 I^* = (i_1^*,i_2^*,\cdots,i_T^*)$

例题：盒子和球模型

假设有3个盒子，每个盒子里面都装有红白两种颜色的球，盒子里的红白球数如下表所示：

$\begin{equation} \begin{array}{|c|c|c|c|} \hline \text { 盒子 } & 1 & 2 & 3 \\ \hline \text { 红球数 } & 5 & 4 & 7 \\ \hline \text { 白球数 } & 5 & 6 & 3 \\ \hline \end{array} \end{equation}$

按照如下规则抽球，从而产生一个球的颜色的观测序列：首先以0.2、0.4、0.4的概率从1、2、3号盒子中选取一个盒子，从这个盒子里随机抽出1个球，记录其颜色后放回，然后按以下概率选取下一个盒子：

$\begin{equation} \begin{array}{|c|c|c|c|} \hline \text { 盒子 } & 1 & 2 & 3 \\ \hline \text { 1 } & 0.5 & 0.2 & 0.3 \\ \hline \text { 2 } & 0.3 & 0.5 & 0.2 \\ \hline \text { 3 } & 0.2 & 0.3 & 0.5 \\ \hline \end{array} \end{equation}$

确定了转移的盒子后，再从盒子里随机抽出1个球，记录其颜色后放回。

重复3次，最终得到的观测序列为O={红，白，红}。

记选取的盒子序列状态序列 $I^* = (i_1^*,i_2^*,\cdots,i_T^*)$

$\LARGE 解:$

该问题为典型的隐马尔可夫模型，由题意可得知模型的参数为：

$\begin{equation} A=\left[\begin{array}{lll} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 & 0.5 \end{array}\right] \quad B=\left[\begin{array}{cc} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{array}\right] \quad \pi=(0.2,0.4,0.4)^{\mathrm{T}} \end{equation}$

$O = \{红，白，红 \}$

按照维特比算法我们可以进行如下计算：

$t=1$
$\begin{equation} \begin{array}{ll} \delta_{1}(1)=\pi_{1} b_{1 o_{1}}=0.2 \times 0.5=0.1, & \psi_{1}(1)=0 \\ \delta_{1}(2)=\pi_{2} b_{2 o_{1}}=0.4 \times 0.4=0.16, & \psi_{1}(2)=0 \\ \delta_{1}(3)=\pi_{3} b_{3 o_{1}}=0.4 \times 0.7=0.28, & \psi_{1}(3)=0 \end{array} \end{equation}$
$t=2$
$\begin{equation} \begin{aligned} &\delta_{2}(1)=\max _{1 \leq j \leq 3}\left[\delta_{1}(j) a_{j 1}\right] b_{1 o_{2}}=\max \left\{\begin{array}{c} 0.1 \times 0.5=0.05 \\ 0.16 \times 0.3=0.048 \\ 0.28 \times 0.2=0.056 \end{array}\right\} \times 0.5=0.028, \quad \psi_{2}(1)=\arg \max _{1 \leq j \leq 3}\left[\delta_{1}(j) a_{j 1}\right]=3 \\ &\delta_{2}(2)=\max _{1 \leq j \leq 3}\left[\delta_{1}(j) a_{j 2}\right] b_{2 o_{2}}=\max \left\{\begin{array}{c} 0.1 \times 0.2=0.02 \\ 0.16 \times 0.5=0.08 \\ 0.28 \times 0.3=0.084 \end{array}\right\} \times 0.6=0.0504, \quad \psi_{2}(2)=\arg \max _{1 \leq j \leq 3}\left[\delta_{1}(j) a_{j 2}\right]=3 \\ &\delta_{2}(3)=\max _{1 \leq j \leq 3}\left[\delta_{1}(j) a_{j 3}\right] b_{3 o_{2}}=\max \left\{\begin{array}{c} 0.1 \times 0.3=0.03 \\ 0.16 \times 0.2=0.032 \\ 0.28 \times 0.5=0.14 \end{array}\right\} \times 0.3=0.042, \quad \psi_{2}(3)=\arg \max _{1 \leq j \leq 3}\left[\delta_{1}(j) a_{j 3}\right]=3 \end{aligned} \end{equation}$
$t=3$
$\begin{equation} \begin{aligned} &\delta_{3}(1)=\max _{1 \leq j \leq 3}\left[\delta_{2}(j) a_{j 1}\right] b_{1 o_{3}}=\max \left\{\begin{array}{c} 0.028 \times 0.5=0.014 \\ 0.0504 \times 0.3=0.01512 \\ 0.042 \times 0.2=0.0084 \end{array}\right\} \times 0.5=0.00756, \quad \psi_{3}(1)=\arg \max _{1 \leq j \leq 3}\left[\delta_{2}(j) a_{j 1}\right]=2 \\ &\delta_{3}(2)=\max _{1 \leq j \leq 3}\left[\delta_{2}(j) a_{j 2}\right] b_{2 o_{3}}=\max \left\{\begin{array}{c} 0.028 \times 0.2=0.0056 \\ 0.0504 \times 0.5=0.0252 \\ 0.042 \times 0.3=0.0126 \end{array}\right\} \times 0.4=0.01008, \quad \psi_{3}(2)=\arg \max _{1 \leq j \leq 3}\left[\delta_{2}(j) a_{j 2}\right]=2 \\ &\delta_{3}(3)=\max _{1 \leq j \leq 3}\left[\delta_{2}(j) a_{j 3}\right] b_{3 o_{3}}=\max \left\{\begin{array}{c} 0.028 \times 0.3=0.0084 \\ 0.0504 \times 0.2=0.01008 \\ 0.042 \times 0.5=0.021 \end{array}\right\} \times 0.7=0.0147, \quad \psi_{3}(3)=\arg \max _{1 \leq j \leq 3}\left[\delta_{2}(j) a_{j 3}\right]=3 \end{aligned} \end{equation}$

所以，最优状态序列为：

$\begin{equation} \begin{aligned} &i_{3}^{*}=\arg \max _{i}\left[\delta_{3}(i)\right]=3 \\ &i_{2}^{*}=\psi_{3}\left(i_{3}^{*}\right)=\psi_{3}(3)=3 \\ &i_{1}^{*}=\psi_{2}\left(i_{2}^{*}\right)=\psi_{2}(3)=3 \end{aligned} \end{equation}$

参考文档

如何理解隐马尔科夫模型(HMM)后向算法初始值为1？ - 知乎 (zhihu.com)

隐马尔可夫模型

模型简介

模型定义

两个基本假设

三个基本问题

概率计算问题

直接计算

前向计算

后向计算

若干公式

学习问题

状态已知，观测已知

状态未知，观测已知

问题定义

完全数据的对数似然

E步：求QQ函数

M步：极大化QQ函数

预测问题

贪心算法

维特比算法

例题：盒子和球模型

参考文档

$Q$ 函数

$Q$ 函数