生成模型，描述由隐藏的马尔科夫链随机生成观测序列的过程。

隐马尔科夫模型

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

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

其中$N$是可能的状态数，$M$是可能的观测数。

$I$是长度为$T$的状态序列，$O$是对应的观测序列。

$$
I=\{i_1, i_2, \dots, i_T\},O=\{o_1, o_2, \dots, o_T\}
$$

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

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

其中，$a_{ij}=P(i_{t+1}=q_j | i_t = q_i),i=1,2,\dots,N;j=1,2,\dots,M$是在时刻$t$处于状态$q_i$的条件下在时刻$t+1$转移到状态$q_j$的概率。

$B$是观测概率矩阵：

$$
B=[b_j(k)]_{N\times M}
$$

其中，$n_j(k)=P(o_t=v_k | i_t=q_j),k=1,2,\dots,M;j=1,2,\dots,N$是在时刻$t$处于状态$q_j$的条件下生成观测$v_t$的概率。

$\pi$是初始状态观测的向量：

$$
\pi=(\pi_i)
$$

其中，$\pi_i=P(i_1=q_i),i=1,2,\dots,N$是时刻$t=1$处于状态$q_i$的概率。

隐马尔科夫模型由初始状态概率向量$\pi$、状态转移概率矩阵$A$和观测概率矩阵$B$决定。$\pi$和$A$决定状态序列，$B$决定观测序列。因此，HMM $\lambda$可以由三元组表示：

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

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

$A,\pi$决定了隐藏的马尔科夫链，生成不可观测的状态序列。$B$决定了如何从状态生成观测，与状态序列综合决定了如何产生观测序列。

从定义可知，HMM作了两个基本的假设：

（1）齐次马尔科夫假设，即假设隐藏的马尔科夫链在任意时刻$t$的状态只依赖于其前一时刻的状态，而与其他时刻的状态无关，也与时刻$t$无关。

$$
P(i_t | i_{t-1}, o_{t-1}, i_{t-2}, o_{t-2}, \dots, i_1, o_1) = P(i_t | i_{t-1}), t=1,2,\dots,T
$$

（2）观测独立性假设，即假设任意时刻的观测只依赖于该时刻的状态，而与其他观测及状态无关。

$$
P(o_t | i_T, o_T, i_{T-1}, o_{T-1}, \dots, i_{t+1}, o_{t+1}, i_t, o_t, i_{t-1}, o_{t-1}, \dots, i_1, o_1) = P(o_t | i_t)
$$

HMM过程

一个长度为$T$的观测序列$O=(o_1,o_2,\dots,o_T)$的生成过程描述如下：

输入：隐马尔科夫模型$\lambda = (A, B, \pi)$，观测序列长度$T$。

输出：观测序列

（1）按照初始状态分布$\pi$产生状态$i_1$

（2）令$t=1$

（3）按照状态$i_t$的观测概率分布$b_{i_t}(k)$产生$o_t$

（4）按照状态$i_t$的状态转移概率分布$\{a_{i_t}, i_{t+1}\}$生成状态$i_{t+1}, i_{t+!}=1,2,\dots,N$

（5）令$t=t+1$，如果$t \lt T$，跳到(3)，否则终止。

HMM的三个基本问题

（1）概率计算问题

给定$\lambda = (A,B,\pi)$和观测序列$O=(o_1,o_2,\dots,o_T)$，计算在模型$\lambda$下观测序列$O$出现的概率$P(O|\lambda)$。

（2）学习概率

已知$O$，估计$\lambda$的参数，使$P(O|\lambda)$最大。

（3）预测问题（解码问题）

已知$\lambda$和$O$，求对$P(O|\lambda)$最大的状态序列$I=(i_1,i_2,\dots,i_T)$。

计算观测序列概率的方法

直接计算法

列举所有可能的长度为$T$的状态序列$I=(i_1,i_2,\dots,i_T)$，求各个状态序列$I$与观测序列$O=(o_1,o_2,\dots,o_T)$的联合概率$P(O,I|\lambda)$，然后对所有可能的状态序列求和，得到$P(O|\lambda)$。

状态序列$I=(i_1,i_2,\dots,i_T)$的概率是：

$$
P(O,I|\lambda) = b_{i_1}(o_1) b_{i_2}(o_2) \dots b_{i_T} (o_T)
$$

$O$和$I$同时出现的概率是：

$$
P(O,I | \lambda) = P(O | I, \lambda) P(I|\lambda)=\pi _{i_1}b_{i_1}(o_1) a_{i_1 i_2} b_{i_2}(o_2) a_{i_2 i_3} \dots a_{i_{T-1} i_{T}}b_{i_T}(o_T)
$$

前向算法

定义前向概率：给定HMM $\lambda$，定义到时刻$t$部分观测序列为$o_1,o_2,\dots,o_t$且状态为$q_i$的概率为前向概率，记作：

$$
\alpha_t(i)=P(o_1,o_2,\dots,o_t,i_t=q_i | \lambda)
$$

观测序列概率的前向算法：

输入：HMM $\lambda$，观测序列$O$。

输出：观测序列概率$P(O|\lambda)$.

（1）初值

$$
\alpha_1(i) = \pi_i b_i (o_1), i=1,2,\dots, N
$$

（2）递推

对于$t=1,2,\dots,T-1$，

$$
\alpha_{t+1}(i)= \left[ \sum\limits_{j=1}^N \alpha_t(j) a_{ij} \right] b_i(o_{t+1})
$$

（3）终止

$$
P(O|\lambda) = \sum\limits_{i=1}^N \alpha_T(i)
$$

利用了动态规划的思想去计算$P(O|\lambda)$。

后向算法

后向概率：给定HMM $\lambda$，定义在时刻$t$状态为$q_i$的条件下，从$t+1$到$T$的部分观测序列为$o_{t+1},o_{t+2},\dots,o_T$的概率为后向概率，记作：

$$
\beta_t(i) = P(o_{t+1}, o_{t+2}, \dots, o_T | i_t = q_i, \lambda)
$$

可以用递推的方法求得后向概率$\beta_t(i)$及观测序列概率$P(O|\lambda)$.

输入：HMM $\lambda$，观测序列$O$。

输出：观测序列概率$P(O|\lambda)$.

（1）$\beta_T(i) = 1, i=1,2,\dots,N$

（2）对$t=T-1,T-2,\dots,1,$

$$
\beta_t(i)=\sum\limits_{j=1}^N a_{ij} b_j (o_{t+1}) \beta_{t+1} (j), i=1,2,\dots,N
$$

（3）$P(O | \lambda) = \sum\limits_{i=1}^N \pi_i b_i (o_1) \beta_1(i)$

利用前向概率和后向概率的定义，观测序列概率$P(O|\lambda)$可以写成

$$
P(O|\lambda) = \sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_t (i) \alpha_{ij} b_j (o_{t+1}) \beta_{t+1} (j), t=1,2,\dots,T-1
$$

给定前向概率和后向概率，可以得到关于单个状态和两个状态概率的计算公式。

1 给定模型$\lambda$和观测序列$O$，在时刻$t$处于状态$q_i$的概率，记

$$
\gamma_t(i) = P(i_t = q_i | O, \lambda)
$$

而$\gamma_t(i) = P(i_t = q_i | O, \lambda) = \frac {P(i_t = q_i, O|\lambda)} {P(O|\lambda)}$，$\alpha_t(i) \beta_t(i) = P(i_t = q_i, O | \lambda)$

于是

$$
\gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{P(O|\lambda)} = \frac {\alpha_t(i) \beta_t(i)} {\sum\limits_{j=1}^N \alpha_t(j) \beta_t(j)}
$$

2 给定模型$\lambda$和观测$O$，在时刻$t$处于状态$q_i$且在时刻$t+1$处于状态$q_j$的概率，记为

$$
\begin{split}
\xi_t (i,j)
= & \frac {P(i_t = q_i, i_{t+1} = q_j, O | \lambda)} {P(O|\lambda)} \\
= & \frac {P(i_t = q_i, i_{t+1} = q_j, O | \lambda)} {\sum\limits_{i=1}^N \sum\limits_{j=1}^N P(i_t = q_i, i_{t+1} = q_j, O | \lambda)}
\end{split}
$$

而$P(i_t = q_i, i_{t+1} = q_j, O | \lambda) = \alpha_t (i) \alpha_{ij} b_j (o_{t+1}) \beta_{t+1} (j)$

于是

$$
\xi_t(i,j) = \frac {\alpha_t (i) \alpha_{ij} b_j (o_{t+1}) \beta_{t+1} (j)} {\sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_t (i) \alpha_{ij} b_j (o_{t+1}) \beta_{t+1} (j)}
$$

3 （1）在观测$O$下，状态$i$出现的期望值：

$$
\sum\limits_{t=1}^T \gamma_t(i)
$$

（2）在观测$O$下，状态$i$转移的期望值：

$$
\sum\limits_{t=1}^{T-1} \gamma_t(i)
$$

（3）在观测$O$下，由状态$i$转移到状态$j$的期望值：

$$
\sum\limits_{t=1}^{T-1} \xi_t (i,j)
$$

学习算法

监督学习

设已给出的数据包含了$S$个长度相同的观测序列和对应的状态序列$\{ (O_1, I_1), (O_2, I_2), \dots, (O_S, I_S) \}$，则可以使用极大似然估计来估计HMM的参数。

（1）转移概率$a_{ij}$的估计

设样本中时刻$t$处于状态$i$，时刻$t+1$处于状态$j$的样本为$A_{ij}$，则状态转移概率$a_{ij}$的估计是

$$
\hat{a_{ij}} = \frac {A_{ij}} {\sum\limits_{j=1}^N A_{ij}}, i=1,2,\dots,N;j=1,2,\dots,N
$$

（2）观测概率$b_j(k)$的估计

设样本中状态为$j$且观测为$k$的频数是$B_{jk}$，那么状态为$j$观测为$k$的概率$b_j(k)$的估计为

$$
\hat{b_j(k)} = \frac {B_{jk}} {\sum\limits_{k=1}^M B_{jk}},j=1,2,\dots,N;k=1,2,\dots,M
$$

（3）初始状态概率$\pi_i$的估计

$\pi_i$的估计$\hat{\pi_i}$为初始状态$q_i$的频率。

非监督学习

设训练数据包含$S$个长度为$T$的观测序列$\{O_1,O_2,\dots,O_S \}$，目标是学习HMM的参数$\lambda=(A,B,\pi)$。如果将状态序列视为不可观测的隐数据$I$，那么HMM就是一个含有隐变量的概率模型

$$
P(O | \lambda) = \sum _I P(O|I,\lambda) P( I | \lambda )
$$

这样参数的学习就可以通过EM算法实现。

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

所有观测数据写成$O=(o_1,o_2,\dots,o_T)$，所有隐数据写成$I=(i_1,i_2,\dots,i_T)$，完全数据是$(O,I) = (o_1,o_2,\dots,o_T,i_1,i_2,\dots,i_T)$，完全数据的对数似然函数是$\log P(O,I|\lambda)$。

（2）E步：求Q函数 $Q(\lambda, \overline\lambda)$

$$
Q(\lambda, \overline\lambda) = \sum_I \log P(O,I|\lambda) P(O,I|\overline\lambda)
$$

其中。$\overline\lambda$是HMM参数的当前估计值，$\lambda$是要极大化的值。

$$
P(O,I|\lambda) = \pi_{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)
$$

于是Q函数可以写成：

$$
\begin{split}
Q(\lambda, \overline\lambda)
= & \sum_I \log \pi_{i_1}P(O,I|\overline\lambda) \\
& + \sum_I \left( \sum\limits_{t=1}^{T-1} \log a_{i_t} i_{t+1} \right)P(O,I|\overline\lambda) \\
& + \sum_I \left( \sum\limits_{t=1}^T b_{i_t} (o_t) \right)P(O,I|\overline\lambda)
\end{split} \tag{1}
$$

（3） M步：极大化Q函数，求$\lambda$

只需对$(1)$式的3项分别求极大化即可。

公式$(1)$的第1项可以写成：

$$
\sum_I \log \pi_{i_1}P(O,I|\overline\lambda) = \sum\limits_{i=1}^N \log \pi_i P(O,i_1=i | \overline\lambda)
$$

存在约束条件

$$
\sum\limits_{i=1}^N \pi_i = 1
$$

利用拉格朗日乘子法，写出拉格朗日函数：

$$
\sum\limits_{i=1}^N \log \pi_i P(O,i_1=i | \overline\lambda) + \gamma \left( \sum\limits_{i=1}^N \pi_i - 1 \right) \tag{2}
$$

求$(2)$式对$\pi_i$的偏导令等于0，得

$$
P(O,i_1=i | \overline\lambda) + \gamma\pi_i = 0, i=1,2,\dots,N \tag{3}
$$

i从1到N，N个公式$(3)$相加，得到

$$
P(O|\overline\lambda) + \gamma = 0
$$

于是

$$
\gamma = -P(O|\overline\lambda)
$$

代回原式，得到

$$
\pi_i = \frac {P(O,i_1=i | \overline\lambda)} {P(O|\overline\lambda)}
$$

公式$(1)$的第2项可以写成：

$$
\sum_I \left( \sum\limits_{t=1}^{T-1} \log a_{i_t i_{t+1}} \right)P(O,I | \overline\lambda) = \sum\limits_{i=1}^N \sum\limits_{j=1}^N \sum\limits_{t=1}^{T-1} \log a_{ij} P(O, i_t = i, i_{t+1} = j | \overline\lambda)
$$

存在约束条件：$\sum\limits_{j=1}^N a_{ij} = 1$

利用拉格朗日乘子法可得：

$$
a_{ij} = \frac {\sum\limits_{t=1}^{T-1} P(O, i_t = i, i_{t+1} = j | \overline\lambda)} {\sum\limits_{t=1}^{T-1} P(O, i_t = i | \overline\lambda)}
$$

公式$(1)$的第3项可以写成：

$$
\sum_I \left( \sum\limits_{t=1}^T \log b_{i_t}(o_t) \right) P(O, I | \overline\lambda) = \sum\limits_{j=1}^N \sum\limits_{t=1}^T \log b_{i_t}(o_t) P(O, i_t = j | \overline\lambda)
$$

约束条件$\sum\limits_{k=1}^M b_j(k) = 1$

注意到只有在$o_t = v_k$时$b_j(o_t)$对$b_j(k)$的偏导数才不为0，以$I(o_t = v_k)$表示。

由拉格朗日乘子法得：

$$
b_j(k) = \frac {\sum\limits_{t=1}^T P(O, i_t = j | \overline\lambda) I(o_t = v_k)} {\sum\limits_{t=1}^T P(O, i_t = j | \overline\lambda)}
$$

将以上三个结果分别用$\gamma_t(i), \xi_t(i,j)$表示，则有

$$
a_{ij} = \frac{\sum\limits_{t=1}^{T-1} \xi_t (i,j) } { \sum\limits_{t=1}^{T-1} \gamma_t(i) }
$$

$$
b_j(k) = \frac {\sum\limits_{t=0,o_t=v_k}^{T} \gamma_t(j) } {\sum\limits_{t=1}^T \gamma_t(j)}
$$

$$
\pi_i = \gamma_i(i)
$$

以上即为Baum-Welch算法，它是EM算法在HMM中的具体实现。

预测算法

近似算法

在每个时刻$t$选择在该时刻最有可能出现的状态$i_t^{*}$，从而得到一个状态序列$I^{*} = (i_1^{*}, i_2^{*}, \dots, i_T^{*})$，作为预测结果。

给定HMM参数$\lambda$和观测序列$O$，在时刻$t$处于状态$q_i$的概率$\gamma_t(i)$是：

$$
\gamma_t(i) = \frac {\alpha_t(i) \beta_t(i)} {P(O|\lambda)} = \frac {\alpha_t(i) \beta_t(i)} {\sum\limits_{j=1}^N \alpha_t(j) \beta_t(j)}
$$

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

$$
i_t^{*} = \arg \max\limits_{1 \le i \le N} \left[ \gamma_t(i) \right],i=1,2,\dots,T
$$

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

这种方法计算见到，但是不能保证预测的状态序列整体上是最有可能的状态序列。

维特比算法

用动态规划的思想去求解HMM预测问题。

输入：模型$\lambda = (A,B,\pi)$和观测$O=(o_1,o_2,\dots,o_T)$。

输出：最优路径$I^{*} = (i_1^{*}, i_2^{*}, \dots, i_T^{*})$

1 初始化

$$
\delta_1(i) = \pi_i b_i (o_1),i=1,2,\dots,N
$$

$$
\psi_1(i) = 0,i=1,2,\dots,N
$$

2 递推

对$t=2,3,\dots,T$

$$
\delta_t(i) = \max\limits_{1 \le j \le N} [\delta_{t-1} a_{ji}] b_i (o_t), i=1,2,\dots,N
$$

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

3 终止

$$
P^{*} = \max \limits_{1 \le i \le N} \delta_T(i)
$$

$$
i^{*} = \arg \max \limits_{1 \le j \le N} [\delta_T(i)]
$$

$\delta$为在时刻$t$状态为$i$的所有单个路径$(i_1,i_2,\dots,i_t)$中概率的最大值.

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

于是：

$$
\begin{split}
\delta_{t+1}(i)
= & \max \limits_{i_1,i_2,\dots,i_{t-1}} P(i_{t+1}=i,i_{t},\dots,i_1,o_{t+1},o_{t},\dots,o_1) \\
= & \max\limits_{1\le j\le N} [\delta_t(j)a_{ji}] b_i(o_{t+1})
\end{split}
$$

$\psi$为在时刻$t$状态为$i$的所有单个路径$(i_1,i_2,\dots,i_t)$中概率最大的路径的第$t-1$个结点.

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

4 最优路径回溯

对$t=T-1,T-2,\dots,1$，

$$
i^{*} = \psi_{t+1}(i_{t+1} ^ {*})
$$

于是最优路径$I^{*} = (i_1^{*}, i_2^{*}, \dots, i_T^{*})$