NO.22.tip： 隐马尔可夫链

背景

隐马尔可夫链简介

定义 1 [隐马尔可夫链 (HMM)]: 一个双离散随机过程 (double discrete stochastic process) $\{C_t\},\{X_t\}$ 被称作隐马尔可夫链，若它满足以下两个条件： $$\{\begin{array}{ll}(1)P(C_t=c_t\mid C_1^{t-1}=c_1^{t-1})=P(C_t=c_t\mid C_{t-1}=c_{t-1})& \text{(HMM 性质 1)}\\ (2)P(X_t=x_t\mid C_1^t=c_1^t,X_1^{t-1}=x_1^{t-1})=P(X_t=x_t\mid C_t=c_t)& \text{(HMM 性质 2)}\end{array}$$

使用简便记号，隐马尔可夫链的定义也可简写为

$$\{\begin{array}{l}p(c_t\mid c_1^{t-1})=p(c_t\mid c_{t-1})\\ p(x_t\mid c_1^t,x_1^{t-1})=p(x_t\mid c_t)\end{array}$$

在隐马尔可夫链的定义中，$\{C_t\}$ 被称作状态过程 (state process)，它是不可观察的（隐藏的），HMM 性质 1 说明其是一个马尔可夫链；$\{X_t\}$ 被称为观测值过程 (observation process)，HMM 性质 2 说明它仅与当前状态有关，而与之前的状态和观测值均无关。

在此基础上，我们还可以定义加强版（改进版）的隐马尔可夫链，如下所示。

定义 2 [加强版的隐马尔可夫链 (Revised HMM)]: $$(1)p(c_t\mid x_1^{t-1},c_1^{t-1})=p(c_t\mid c_{t-1})\text{(加强版的 HMM 性质 1)}$$ $$(2)p(x_t\mid x_1,\dots ,x_{t-1},x_{t+1},\dots ,x_T,c_1,\dots ,c_t)=p(x_t\mid c_t)\text{(加强版的 HMM 性质 2)}$$

加强版的 HMM 性质 1 说明，给定第 $t-1$ 个状态变量，第 $t$ 个状态变量与其他所有变量均不相关；加强版的 HMM 性质 2 说明，给定第 $t$ 个状态变量，第 $t$ 个观测值与其他所有变量均不相关。

在后续部分中，我们将不再详细区分 HMM 性质与加强版的 HMM 性质。总的来说，在隐马尔可夫链框架下，一共两个随机过程，$\{C_t\}$ 与 $\{X_t\}$；$\{C_t\}$ 是马尔可夫链，给定 $C_{t-1}$，$C_t$ 与其他所有变量（过去的观测值和过去的状态）均无关，$\{X_t\}$ 是观测值过程，给定 $C_t$，$X_t$ 与其他所有变量（之前和之后的观测值、过去的状态）均无关。

三个基本问题

应用隐马尔可夫链面临三个基本问题：

• 当参数给定时，求出观测值序列发生的概率，即 $$P(X_1^T=x_1^T\mid \theta )$$ 通常对于这个问题我们使用向前/向后算法 (Forward/Backward Approach)

• 找出一个隐藏的状态序列 $c_1,c_2,\dots ,c_T$，其能最好的解释观测值序列 $x_1,x_2,\dots ,x_T$
  这个问题也称为解码 (decoding)，通常使用维特比算法 (Viterbi Algorithm)

• 找出能使观测值序列发生概率最大的参数，即 $$\hat{\theta }=\arg \underset{\theta }{\max }P(X_1^T=x_1^T)$$ 此问题即参数估计，也称为学习 (study) 或者训练 (train)，是三个基本问题中最复杂的，通常使用期望最大化算法 (Expectation Maximization Method or called Baum–Welch Method)。

源与流

隐马尔可夫链的若干基本性质

我们首先定义一个符号

$$p_i(x)=P(X_t=x\mid C_t=i)$$

可见 $p_i(x)$ 是给定 $C_t$ 在 $t$ 时刻位于状态 $i$ 时，$X_t$ 的条件概率。它也被称为状态相关分布 (state-dependent distribution)，或者发射分布 (emission distribution)。形象地理解，可以把观测值 $X_t$ 当作状态 $C_t$ “发射”的“信号”(signal)。

在此基础上，定义

$$P(x)={\left[\begin{array}{cccc}{p}_1(x)& & & \\ & p_2(x)& & \\ & & \ddots & \\ & & & p_m(x)\end{array}\right]}_{m\times m}$$

$P(x)$ 被称为对角发射矩阵 (diagonal emission matrix)，它的第 $i$ 个对角线元素即是 $p_i(x)$。

定理 1 [单变量分布 (univariate distribution)]: $$P(X_t=x)=\sum _{i=1}^m{u}_i(t)\cdot p_i(x)$$ 写成矩阵形式为 $$P(X_t=x)=u(t)\cdot P(x)\cdot 1^{\mathrm{T}}$$

证明：

$$P(X_t=x)=\sum _{i=1}^{m}P(X_t=x\mid C_t=i)\cdot P(C_t=i)\text{（基于定理 1.1，全概率公式）}$$

$$=\sum _{i=1}^m{u}_i(t)\cdot p_i(x)$$

上式也可以用矩阵运算写成

$$P(X_t=x)=[u_1(t),u_2(t),\dots ,u_m(t){]}_{1\times m}\cdot {\left[\begin{array}{cccc}{p}_1(x)& & & \\ & p_2(x)& & \\ & & \ddots & \\ & & & p_m(x)\end{array}\right]}_{m\times m}\cdot {\left[\begin{array}{c}1\\ 1\\ ⋮\\ 1\end{array}\right]}_{m\times 1}$$

$$=u(t)\cdot P(x)\cdot 1^{\mathrm{T}}$$

此外，我们知道，$u(t)=u(1)\cdot A^{t-1}$，因此，上述定理的矩阵形式也可写为

$$P(X_t=x)=u(1)\cdot A^{t-1}\cdot P(x)\cdot 1^{\mathrm{T}}=\pi \cdot A^{t-1}\cdot P(x)\cdot 1^{\mathrm{T}}$$

若马尔可夫链是稳态的，$u(t)\equiv \delta$，则上式又可简化为

$$P(X_t=x)=\delta \cdot P(x)\cdot 1^{\mathrm{T}}$$

定理 2: $$p(x_t,x_{t+k},c_t,c_{t+k})=p(c_t)\cdot p_{c_t}(x_t)\cdot a_{c_t,c_{t+k}}(k)\cdot p_{c_{t+k}}(x_{t+k})$$

证明：

$$\begin{array}{rlrl}& p(x_t,x_{t+k},c_t,c_{t+k})& & \\ & =p(x_t,x_{t+k}\mid c_t,c_{t+k})\cdot p(c_t,c_{t+k})& & \text{（取条件于 }{c}_t,c_{t+k}\text{）}\\ & =p(x_t\mid c_t,c_{t+k})\cdot p(x_{t+k}\mid x_t,c_t,c_{t+k})\cdot p(c_{t+k}\mid c_t)\cdot p(c_t)& & \text{（基于引理 1 及取条件于 }{c}_t\text{）}\\ & =p(x_t\mid c_t)\cdot p(x_{t+k}\mid c_{t+k})\cdot p(c_t)\cdot a_{c_t,c_{t+k}}(k)& & \text{（基于 HMM 性质 2）}\\ & =p(c_t)\cdot p_{c_t}(x_t)\cdot a_{c_t,c_{t+k}}(k)\cdot p_{c_{t+k}}(x_{t+k})& & \end{array}$$

证毕

定理 2 可以直观地理解如下：隐马尔可夫链在时刻 $t$ 和 $t+k$，状态变量取值为 $c_t$ 和 $c_{t+k}$，观测变量取值为 $x_t$ 和 $x_{t+k}$ 的概率，等于在 $t$ 时刻，状态变量取值于 $c_t$ 的概率，乘以“发射信号”$x_t$ 的概率，乘以状态变量 $k$ 步转移到 $c_{t+k}$ 的概率（此时时刻为 $t+k$），再乘以“发射信号”$x_{t+k}$ 的概率。

定理 3 [双变量分布 (Bivariate Distribution)]: $$P(X_t=v,X_{t+k}=w)=\sum _{i=1}^m\sum _{j=1}^m{u}_i(t)\cdot p_i(v)\cdot a_{ij}(k)\cdot p_j(w)$$ 矩阵形式可写为 $$P(X_t=v,X_{t+k}=w)=u(t)\cdot P(v)\cdot A^k\cdot P(w)\cdot 1^{\mathrm{T}}$$

证明：

$$\begin{array}{rl}& P(X_t=v,X_{t+k}=w)\\ & =P\left(X_t=v,X_{t+k}=w,\bigcup _i(C_t=i),\bigcup _j(C_{t+k}=j)\right)\\ & =\sum _{i=1}^m\sum _{j=1}^{m}P(X_t=v,X_{t+k}=w,C_t=i,C_{t+k}=j)\\ & =\sum _{i=1}^m\sum _{j=1}^{m}P(C_t=i)\cdot p_i(v)\cdot a_{ij}(k)\cdot p_j(w)\\ & =\sum _{i=1}^m\sum _{j=1}^m{u}_i(t)\cdot p_i(v)\cdot a_{ij}(k)\cdot p_j(w)\text{（基于定理 2）}\end{array}$$

上式也可用矩阵运算写为

$$\begin{array}{rl}& P(X_t=v,X_{t+k}=w)\\ & =[u_1(t),\dots ,u_m(t){]}_{1\times m}\cdot {\left[\begin{array}{cccc}{p}_1(v)& & & \\ & p_2(v)& & \\ & & \ddots & \\ & & & p_m(v)\end{array}\right]}_{m\times m}\\ & \cdot {\left[\begin{array}{ccc}{a}_{11}(k)& \cdots & a_{1m}(k)\\ ⋮& \ddots & ⋮\\ a_{m1}(k)& \cdots & a_{mm}(k)\end{array}\right]}_{m\times m}\cdot {\left[\begin{array}{cccc}{p}_1(w)& & & \\ & p_2(w)& & \\ & & \ddots & \\ & & & p_m(w)\end{array}\right]}_{m\times m}\\ & \cdot {\left[\begin{array}{c}1\\ 1\\ ⋮\\ 1\end{array}\right]}_{m\times 1}\end{array}$$

$$=u(t)\cdot P(v)\cdot A(k)\cdot P(w)\cdot 1^{\mathrm{T}}$$

$$=u(t)\cdot P(v)\cdot A^k\cdot P(w)\cdot 1^{\mathrm{T}}\text{（基于定理2}A(k)=A^k\text{）}$$

证毕

若马尔可夫链是稳态的，则 $u(t)\equiv \delta$，上式又可简化为

$$P(X_t=v,X_{t+k}=w)=\delta \cdot P(v)\cdot A^k\cdot P(w)\cdot 1^{\mathrm{T}}$$

定理 4: $$P(X_1^T=x_1^T,C_1^T=c_1^T)={\pi }_{c_1}\cdot \prod _{t=1}^{T-1}{a}_{c_t,c_{t+1}}\cdot \prod _{t=1}^T{p}_{c_t}(x_t)={\pi }_{c_1}\cdot \prod _{t=2}^T{a}_{c_{t-1},c_t}\cdot \prod _{t=1}^T{p}_{c_t}(x_t)$$

证明：

$$P(X_1^T=x_1^T,C_1^T=c_1^T)=p(x_1^T,c_1^T)=p(x_1^T\mid c_1^T)\cdot p(c_1^T)\text{（取条件于 }{c}_1^T\text{）}$$

• 首先我们求 $p(c_1^T)$

$$\begin{array}{rlrl}p(c_1^T)& =p(c_2^T\mid c_1)\cdot p(c_1)& & \\ & ={\pi }_{c_1}\cdot p(c_2\mid c_1)\cdot p(c_3^T\mid c_1,c_2)& & \text{（取条件于 }{c}_1\text{）}\\ & ={\pi }_{c_1}\cdot a_{c_1,c_2}\cdot p(c_3^T\mid c_2)& & \text{（基于引理 1）}\\ & ={\pi }_{c_1}\cdot a_{c_1,c_2}\cdot p(c_3\mid c_2)\cdot p(c_4^T\mid c_2,c_3)& & \text{（基于 HMM 性质 1）}\\ & ⋮& & \text{（基于引理 1）}\\ & ={\pi }_{c_1}\cdot a_{c_1,c_2}\cdot a_{c_2,c_3}\cdots a_{c_{T-1},c_T}& & \text{（重复上述过程）}\\ & ={\pi }_{c_1}\cdot \prod _{t=1}^{T-1}{a}_{c_t,c_{t+1}}& & \\ & ={\pi }_{c_1}\cdot \prod _{t=2}^T{a}_{c_{t-1},c_t}& & \end{array}$$

• 接下来我们求 $p(x_1^T\mid c_1^T)$

$$\begin{array}{rlrl}p(x_1^T\mid c_1^T)& =p(x_1\mid c_1^T)\cdot p(x_2^T\mid c_1^T,x_1)& & \text{（基于引理 1）}\\ & =p(x_1\mid c_1)\cdot p(x_2^T\mid c_2^T)& & \text{（基于 HMM 性质 2）}\\ & =p_{c_1}(x_1)\cdot p(x_2\mid c_2^T)\cdot p(x_3^T\mid c_2^T,x_2)& & \text{（基于引理 1）}\\ & =p_{c_1}(x_1)\cdot p(x_2\mid c_2)\cdot p(x_3^T\mid c_3^T)& & \text{（基于 HMM 性质 2）}\\ & =p_{c_1}(x_1)\cdot p_{c_2}(x_2)\cdot p(x_3\mid c_3^T)\cdot p(x_4^T\mid c_3^T,x_3)& & \text{（基于引理 1）}\\ & ⋮& & \text{（重复上述过程）}\\ & =p_{c_1}(x_1)\cdot p_{c_2}(x_2)\cdots p_{c_T}(x_T)& & \\ & =\prod _{t=1}^T{p}_{c_t}(x_t)& & \end{array}$$

结合上述两步的结果，可得

$$P(X_1^T=x_1^T,C_1^T=c_1^T)={\pi }_{c_1}\cdot \prod _{t=1}^{T-1}{a}_{c_t,c_{t+1}}\cdot \prod _{t=1}^T{p}_{c_t}(x_t)={\pi }_{c_1}\cdot \prod _{t=2}^T{a}_{c_{t-1},c_t}\cdot \prod _{t=1}^T{p}_{c_t}(x_t)$$

证毕

定理 4 可以直观地理解如下：出现状态序列 $c_1,c_2,\dots ,c_T$ 和观测值序列 $x_1,x_2,\dots ,x_T$ 的概率，等于初始时刻状态位于 $c_1$ 的概率（右边第 1 项），乘以状态从 $c_1$ 转移到 $c_2$ 的概率，再乘以状态从 $c_2$ 转移到 $c_3$ 的概率，以此类推，直到乘以状态从 $c_{T-1}$ 转移到 $c_T$ 的概率（右边第 2 项），最后还要乘以在每个状态 $c_t$ 下“发射信号”$x_t$ 的概率（右边第 3 项）。

从定理 4 出发，我们也可以导出观测值序列 $x_1,x_2,\dots ,x_T$ 出现的概率。

定理 5: $$P(X_1^T=x_1^T)=\sum _{c_1,c_2,\dots ,c_T=1}^{m}P(X_1^T=x_1^T,C_1^T=c_1^T)$$

证明：

$$\begin{array}{rlrl}P(X_1^T=x_1^T)& =P\left(X_1^T=x_1^T,\bigcup _{c_1=1}^m(C_1=c_1)\right)& & \\ & =\sum _{c_1=1}^{m}P(X_1^T=x_1^T,C_1=c_1)& & \\ & =\sum _{c_1=1}^{m}P\left(X_1^T=x_1^T,C_1=c_1,\bigcup _{c_2}(C_2=c_2)\right)& & \\ & =\sum _{c_1=1}^m\sum _{c_2=1}^{m}P(X_1^T=x_1^T,C_1=c_1,C_2=c_2)& & \\ & ⋮& & \\ & =\sum _{c_1=1}^m\sum _{c_2=1}^m\cdots \sum _{c_T=1}^{m}P(X_1^T=x_1^T,C_1=c_1,C_2=c_2,\dots ,C_T=c_T)& & \text{（重复上述步骤）}\\ & =\sum _{c_1,c_2,\dots ,c_T=1}^{m}P(X_1^T=x_1^T,C_1^T=c_1^T)& & \end{array}$$

证毕

隐马尔可夫链的似然函数

隐马尔可夫链的似然函数是个很重要的概念，在参数估计、条件分布、预测等问题中有着非常重要的应用。此外，后面介绍的前向（后向）概率等许多参量也可以用似然函数来表示。幸运的是，不但正常情况下隐马尔可夫链的似然函数有明晰的解析表达式，在个别数据缺失的情况下，依然可以得到似然函数的解析表达式。

正常情况下隐马尔可夫链的似然函数

定理 6 [无缺失数据时 HMM 的似然函数]: 若隐马尔可夫链共有 $T$ 个观测值，$x_1,x_2,\dots ,x_T$，则其似然函数可表示为 $$L=\pi P(x_1)AP(x_2)\cdots AP(x_T)\cdot 1^{\mathrm{T}}=\pi P(x_1)\cdot \prod _{s=2}^{T}AP(x_s)\cdot 1^{\mathrm{T}}$$

证明：

$$\begin{array}{rlrl}L& =P(X_1^T=x_1^T)& & \\ & =\sum _{c_1,\dots ,c_T=1}^{m}P(X_1^T=x_1^T,C_1^T=c_1^T)& & \text{（基于定理 5）}\\ & =\sum _{c_1,\dots ,c_T=1}^m{\pi }_{c_1}\cdot \prod _{t=2}^T{a}_{c_{t-1},c_t}\cdot \prod _{t=1}^T{p}_{c_t}(x_t)& & \text{（基于定理 4）}\\ & =\sum _{c_1,\dots ,c_T=1}^m{\pi }_{c_1}\cdot a_{c_1,c_2}\cdot a_{c_2,c_3}\cdots a_{c_{T-1},c_T}& & \\ & \cdot p_{c_1}(x_1)\cdot p_{c_2}(x_2)\cdot p_{c_3}(x_3)\cdots p_{c_T}(x_T)& & \\ & =\pi P(x_1)AP(x_2)AP(x_3)\cdots AP(x_T)\cdot 1^{\mathrm{T}}& & \\ & =\pi P(x_1)\cdot \prod _{s=2}^{T}AP(x_s)\cdot 1^{\mathrm{T}}& & \end{array}$$

从矩阵运算的观点来看，LHS（似然函数）是一个实数，RHS 是 $(1\times m)\cdot (m\times m)\cdots (m\times m)\cdot (m\times 1)$ 的矩阵乘法，其结果 $(1\times 1)$ 也是一个实数。 证毕

特别地，如果马尔可夫链（隐马尔可夫链的状态过程）是稳态的，则有 $\pi =\delta =\delta \cdot A$，因此上式可简化为

$$L=\delta \cdot AP(x_1)\cdot \prod _{s=2}^{T}AP(x_s)\cdot 1^{\mathrm{T}}=\delta \cdot \prod _{s=1}^{T}AP(x_s)\cdot 1^{\mathrm{T}}$$

数据缺失情况下隐马尔可夫链的似然函数

在个别数据缺失的情况下，隐马尔可夫链的似然函数也有类似的表达式。

定理 7 [有缺失数据时 HMM 的似然函数]: 若观察值 $x_3,x_5,x_6$ 缺失，则似然函数可表示为 $$L^{-(3,5,6)}=\pi P(x_1)\cdot AP(x_2)\cdot A^{2}P(x_4)\cdot A^{3}P(x_7)\cdots AP(x_T)\cdot 1^{\mathrm{T}}$$ 其中 $L^{-(3,5,6)}$ 代表 $x_3,x_5,x_6$ 缺失时的似然函数。

证明：

$$\begin{array}{rl}& L^{-(3,5,6)}\\ & =P(X_1=x_1,X_2=x_2,X_4=x_4,X_7=x_7,X_8^T=x_8^T)\\ & =\sum _{\text{除 }{c}_3,c_5,c_6\text{ 之外的所有 }{c}_t}{\pi }_{c_1}\cdot a_{c_1,c_2}\cdot a_{c_2,c_4}(2)\cdot a_{c_4,c_7}(3)\cdot a_{c_7,c_8}\cdots a_{c_{T-1},c_T}\\ & \cdot p_{c_1}(x_1)\cdot p_{c_2}(x_2)\cdot p_{c_4}(x_4)\cdot p_{c_7}(x_7)\cdot p_{c_8}(x_8)\cdots p_{c_T}(x_T)\\ & =\sum _{\text{除 }{c}_3,c_5,c_6\text{ 之外的所有 }{c}_t}{\pi }_{c_1}\cdot p_{c_1}(x_1)\cdot a_{c_1,c_2}\cdot p_{c_2}(x_2)\cdot a_{c_2,c_4}(2)\cdot p_{c_4}(x_4)\\ & \cdot a_{c_4,c_7}(3)\cdot p_{c_7}(x_7)\cdot a_{c_7,c_8}\cdot p_{c_8}(x_8)\cdots a_{c_{T-1},c_T}\cdot p_{c_T}(x_T)\\ & =\pi P(x_1)\cdot AP(x_2)\cdot A(2)P(x_4)\cdot A(3)P(x_7)\cdot AP(x_8)\cdots AP(x_T)\cdot 1^{\mathrm{T}}\\ & =\pi P(x_1)\cdot AP(x_2)\cdot A^{2}P(x_4)\cdot A^{3}P(x_7)\cdot AP(x_8)\cdots AP(x_T)\cdot 1^{\mathrm{T}}\\ & \text{（基于定理2}A(k)=A^k\text{）}\end{array}$$

证毕

评注： 对于缺失数据的似然函数，有一个简便的记忆方法。若 $x_t$ 缺失，则对应的对角发射矩阵（diagonal emission matrix），$P(x_t)$，就被替换为单位阵 $I$；等价的，对于所有的 $i=1,2,\dots ,m$，$p_i(x_t)\equiv 1$。

例： $x_3$ 缺失
则 $P(x_3)\to I$，似然函数的变化为

$$\cdots P(x_2)AP(x_3)AP(x_4)\cdots \to \cdots P(x_2)\cdot A\cdot I\cdot AP(x_4)\cdots =\cdots P(x_2)A^{2}P(x_4)\cdots$$

例： $x_5,x_6$ 缺失
则 $P(x_5)\to I,P(x_6)\to I$，似然函数变化为

$$\cdots P(x_4)AP(x_5)AP(x_6)AP(x_7)\cdots \to \cdots P(x_4)\cdot A\cdot I\cdot A\cdot I\cdot A\cdot P(x_7)=\cdots P(x_4)A^{3}P(x_7)$$

数据缺失情况下的隐马尔可夫链似然函数在后文提到的分布预测等问题中有很多应用。

两类隐马尔可夫链 我们将介绍两类常见的隐马尔可夫链，泊松-隐马尔可夫链 (Poisson-HMM) 和正态-隐马尔可夫链 (Normal-HMM)。它们都是从“发射信号”这个角度来划分的。若发射概率是泊松分布的，则称这种 HMM 为泊松-隐马尔可夫链，正态-隐马尔可夫链与此同理。类似地，也可定义二项-隐马尔可夫链 (Binomial-HMM) 或者伽马-隐马尔可夫链 (Gamma-HMM) 等。

定义 3 [泊松-隐马尔可夫链 (Poisson-HMM)]: 若隐马尔可夫链共有 $m$ 个状态，$T$ 个观测值，即 $i=1,2,\dots ,m,t=1,2,\dots ,T$，在每个状态 $i$ 下，发射概率（emission probability）是泊松分布的并且强度为 ${\lambda }_i$，即 $$p_i(x_t)=P(X_t=x_t\mid C_t=i)=\frac{e^{-{\lambda }_i}\cdot {\lambda }_i^{x_t}}{x_t!}$$ 则称此 HMM 为泊松-隐马尔可夫链。

在泊松-隐马尔可夫链框架下，参数为 $\theta =[\pi ,A,\lambda ]$，其中

$$\{\begin{array}{ll}\pi =[{\pi }_1,{\pi }_2,\dots ,{\pi }_m{]}_{1\times m}& \text{（初始分布向量）}\\ A={\left[\begin{array}{ccc}{a}_{11}& \cdots & a_{1m}\\ ⋮& \ddots & ⋮\\ a_{m1}& \cdots & a_{mm}\end{array}\right]}_{m\times m}& \text{（转移概率矩阵）}\\ \lambda =[{\lambda }_1,{\lambda }_2,\dots ,{\lambda }_m{]}_{1\times m}& \text{（发射参数向量）}\end{array}$$

与泊松-隐马尔可夫链类似，我们也可以定义正态-隐马尔可夫链，区别仅在于在每个状态 $i$ 下，发射概率为正态分布而非泊松分布。

定义 4 [正态-隐马尔可夫链 (Normal-HMM)]: 若隐马尔可夫链共有 $m$ 个状态，$T$ 个观测值，即 $i=1,2,\dots ,m,t=1,2,\dots ,T$，在每个状态 $i$ 下，发射概率是正态分布的并且参数为 ${\mu }_i$ 和 ${\sigma }_i$，即 $$p_i(x_t)=P(X_t=x_t\mid C_t=i)=\frac{1}{\sqrt{2\pi }{\sigma }_i}{e}^{-(x_t-{\mu }_i{)}^2/(2{\sigma }_i^2)}$$ 则称此 HMM 为正态-隐马尔可夫链。

在正态-隐马尔可夫链框架下，参数为 $\theta =[\pi ,A,\mu ,\sigma ]$，其中

$$\{\begin{array}{ll}\pi =[{\pi }_1,{\pi }_2,\dots ,{\pi }_m{]}_{1\times m}& \text{（初始分布向量）}\\ A={\left[\begin{array}{ccc}{a}_{11}& \cdots & a_{1m}\\ ⋮& \ddots & ⋮\\ a_{m1}& \cdots & a_{mm}\end{array}\right]}_{m\times m}& \text{（转移概率矩阵）}\\ \mu =[{\mu }_1,{\mu }_2,\dots ,{\mu }_m{]}_{1\times m}& \text{（发射参数向量）}\\ \sigma =[{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_m{]}_{1\times m}& \text{（发射参数向量）}\end{array}$$

向前/向后算法

我们曾提到过，隐马尔可夫链的核心是三个基本问题，其中第一个问题就是计算观测值出现的概率，$P(X_1^T=x_1^T\mid \theta )$。回答这个问题需使用向前/向后算法，而这个算法的核心是前向/后向概率。此外，前向/后向概率也是其他重要算法如后面提到的期望最大化算法的基础。

前向概率与向前算法

定义 5 [前向概率 (Forward Probability)]: $${\alpha }_i(t)=P(X_1^t=x_1^t,C_t=i)(t=1,2,\dots ,T;i=1,2,\dots ,m)$$ 可见前向概率是一个联合概率，它是出现观测值 $x_1,x_2,\dots ,x_t$ 且状态在 $t$ 时刻位于 $i$ 的概率。

仿照前面行向量 $u(t),\pi$ 的定义，我们也可以定义前向概率的向量表示 (vector representation)，

$$\alpha (t)=[{\alpha }_1(t),{\alpha }_2(t),\dots ,{\alpha }_m(t){]}_{1\times m}$$

对于前向概率的向量表示，我们有如下的定理

定理 8: $$\alpha (t)=\pi P(x_1)AP(x_2)\cdots AP(x_t)=\pi P(x_1)\cdot \prod _{s=2}^{t}AP(x_s)$$

直观地看，上式的左边是一个 $1\times m$ 的行向量，右边是 $(1\times m)\cdot (m\times m)\cdots (m\times m)$ 的矩阵乘法，结果也是一个 $1\times m$ 的行向量。

定理 9 [前向概率的初值条件 (Initial Condition of Forward Probability)]: $${\alpha }_i(1)={\pi }_i\cdot p_i(x_1)(i=1,2,\dots ,m)$$ 矩阵（向量）形式为 $$\alpha (1)=\pi P(x_1)$$

证明：

$$\begin{array}{rlrl}{\alpha }_i(1)& =P(X_1=x_1,C_1=i)& & \\ & =P(X_1=x_1\mid C_1=i)\cdot P(C_1=i)& & \text{（取条件于 }{C}_1\text{）}\\ & ={\pi }_i\cdot p_i(x_1)& & \end{array}$$

矩阵形式下，可写为

$$[{\alpha }_1(1),{\alpha }_2(1),\dots ,{\alpha }_m(1){]}_{1\times m}=[{\pi }_1,{\pi }_2,\dots ,{\pi }_m{]}_{1\times m}\cdot {\left[\begin{array}{cccc}{p}_1(x_1)& & & \\ & p_2(x_1)& & \\ & & \ddots & \\ & & & p_m(x_1)\end{array}\right]}_{m\times m}$$

也即

$$\alpha (1)=\pi P(x_1)$$

证毕

定理 10 [前向概率的递归公式 (Recursion of Forward Probability)]: $${\alpha }_j(t+1)=\left(\sum _{i=1}^m{\alpha }_i(t)\cdot a_{ij}\right)\cdot p_j(x_{t+1})(t=1,2,\dots ,T-1;j=1,2,\dots ,m)$$ 矩阵形式为 $$\alpha (t+1)=\alpha (t)\cdot A\cdot P(x_{t+1})(t=1,2,\dots ,T-1)$$

证明：

(1) 实数形式 (scalar form)

$$\begin{array}{rlrl}{\alpha }_j(t+1)& =P(X_1^{t+1}=x_1^{t+1},C_{t+1}=j)& & \\ & =P\left(X_1^{t+1}=x_1^{t+1},C_{t+1}=j,\bigcup _i(C_t=i)\right)& & \\ & =\sum _{i}P(X_1^{t+1}=x_1^{t+1},C_t=i,C_{t+1}=j)& & \\ & =\sum _{i}P(X_{t+1}=x_{t+1},C_{t+1}=j\mid X_1^t=x_1^t,C_t=i)\cdot \stackrel{{\alpha }_i(t)}{\overbrace{P(X_1^t=x_1^t,C_t=i)}}& & \\ & \text{（取条件于 }{X}_1^t,C_t\text{）}& & \\ & =\sum _{i}P(X_{t+1}=x_{t+1},C_{t+1}=j\mid C_t=i)\cdot {\alpha }_i(t)& & \text{（基于 HMM 性质 1、2）}\\ & =\sum _i{\alpha }_i(t)\cdot P(C_{t+1}=j\mid C_t=i)\cdot P(X_{t+1}=x_{t+1}\mid C_t=i,C_{t+1}=j)& & \\ & \text{（基于引理 1）}& & \\ & =\sum _i{\alpha }_i(t)\cdot a_{ij}\cdot P(X_{t+1}=x_{t+1}\mid C_{t+1}=j)& & \text{（基于 HMM 性质 2）}\\ & =\left(\sum _i{\alpha }_i(t)\cdot a_{ij}\right)\cdot p_j(x_{t+1})& & \end{array}$$

(2) 矩阵形式 (matrix form)

$$\alpha (t+1)=\pi P(x_1)\cdot \prod _{s=2}^{t+1}AP(x_s)\text{（基于定理 8）}$$

$$=\pi P(x_1)\cdot \prod _{s=2}^{t}AP(x_s)\cdot AP(x_{t+1})$$