隐马尔科夫模型

1. 历史背景

2. 问题引入

假设有一个由多个可观测的样本组合的序列 $\mathbf{x}=(x_1,x_2,\dots,x_T)$，我们称之为观测序列。观测序列中的 $t$ 可以指时间、染色体或 DNA 上位点的索引或单词在句子中的位置，对于每个 $t\in1,2,\dots,T$，我们希望得到一个对应的感兴趣的隐藏状态变量 $z_t\in \mathcal{Z}$，其中 $\mathcal{Z}$ 是有限的集合，由 $z_t$ 组成的序列称为状态序列 $\mathbf{z}$。例如在词性标注中，观测序列就是文档中的 $t$ 个单词，状态序列就是每个单词对应的词性标签。

试想一下，如果用之前的机器学习方法可以怎么做？

可以用贝叶斯估计，最大似然条件概率 $\displaystyle\arg\max \frac{p(X=\mathbf{x}|Z=\mathbf{z})p(Z=\mathbf{z})}{p(X=\mathbf{x})}$，显然单词间的组合太多了，需要的样本量之多几乎不可能做到，只能利用朴素贝叶斯的思想，假定 $(x_i,z_i)$ 与 $(x_j,z_j)$ 相互独立，这样我们就可以对每一个单词给出一个最大后验概率 $\displaystyle\hat{z}_t=\arg\max p(X_t={x_t}|Z_t={z_t})p(Z_t={z_t})$。但这显然是不合理的，最终只能给出每个单词的所属词性最大概率的一个，但实际上每个单词与前后文相关，而在朴素贝叶斯中却无法体现出来。

为了考虑时序的概率情况，隐马尔科夫模型被提了出来。隐马尔科夫是在马尔科夫链的基础上提出来的，它们之间的不同之处就在于，马尔科夫链中的状态都是可观测的，而隐马尔科夫模型中存在不可观测的状态，但它们之间的根本原理都是无后效性，即未来状态只与当前的状态有关，即

$$P(Z_{t+1}=z_{t+1}|Z_t=z_t,\cdots,Z_0=z_0)=P(Z_{t+1}=z_{t+1}|Z_t=z_{t})$$

隐马尔科夫模型中存在一个隐藏的马尔科夫链，也就是状态序列 $Z=(Z_0,Z_1,\dots,Z_T)$，状态集合为 $\mathcal{Z}$，对于任意两个状态 $i,j\in\mathcal{Z}$ 都可以给出一个转移概率

$$a_{ij}=P(Z_{t+1}=j|Z_{t}=i)\qquad i,j=1,2,\dots,N$$

因此最终可以得到一个状态转移概率矩阵

$$A=\begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1N}\\ a_{21}&a_{22}&\cdots&a_{2N}\\ \vdots \\ a_{N1}&a_{N2}&\cdots&a_{NN}\\ \end{bmatrix}$$

同时存在另一个随机变量序列 $X=(X_0,X_2,\dots,X_T)$ 称为观测序列，它的取值来自于观测空间 $\mathcal{X}$，我们假设观测具有独立性，即任意时刻的观测只依赖于该时刻的马尔科夫链的状态，而与其他时刻观测及状态无关。因此，在给定时刻 $t$ 状态 $b_j$ 的情况下，都可以得到对应观测值 $k$ 的概率

$$b_{j}(k)=P(X_t=k|Z_t=j)\qquad k=1,2,\dots,M;j=1,2,\dots,N$$

进一步地可以得到一个观测概率矩阵

$$B=\begin{bmatrix} b_{11}&b_{12}&\cdots&b_{1M}\\ b_{21}&b_{22}&\cdots&b_{2M}\\ \vdots \\ b_{N1}&b_{N2}&\cdots&b_{NM}\\ \end{bmatrix}$$

最后还需要确定初始状态概率 $\pi=(\pi_1,\pi_2,\dots,\pi_N)$，其中

$$\pi_i=P(Z_1=i)\qquad i=1,2,\dots,N$$

通过初始状态概率向量 $\pi$、状态转移概率矩阵 $A$，观测概率矩阵 $B$ 就可以确定隐马尔科夫模型，它们也称为隐马尔科夫模型的三要素

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

可以发现，隐马尔科夫是基于无后效性和观测独立性假设提出来的。观测独立性假设，即任意时刻的观测结果只与该时刻的马尔科夫链的状态有关，与其他状态及观测无关

$$P(X_t|X_T,Z_{T},\dots,X_1,Z_{1})=P(X_t|Z_t)$$

有了三要素，给定序列长度 $T$ 就可以生成一个对应的观测序列，而概率矩阵的拟合根据数据是否标记可采用不同的学习算法。最终想要隐马尔科夫模型进行预测需要解决一下三个问题

1. 学习问题。已知观测序列 $\mathbf{x}=(x_1,x_2,\dots,x_T)$，估计模型 $\lambda=(A,B,\pi)$ 参数，使得在该模型下的观测序列概率 $P(\mathbf{x}|\lambda)$ 最大，也就是用最大似然估计的方法来估计模型参数。
2. 先验概率问题。给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $\mathbf{x}=(x_1,x_2,\dots,x_T)$，计算在模型 $\lambda$ 下观测序列 $\mathbf{x}$ 出现的概率 $P(\mathbf{x}|\lambda)$，也就是先验概率。
3. 预测问题。已知模型 $\lambda=(A,B,\pi)$ 和观测序列 $\mathbf{x}=(x_1,x_2,\dots,x_T)$，求在给定观测序列下条件概率 $P(\mathbf{z}|\mathbf{x})$ 最大的状态序列 $\mathbf{z}=(z_1,z_2,\dots,z_T)$。

3. 先验概率计算算法

给定模型 $\lambda=(A,B,\pi)$ 和观测序列 $\mathbf{x}=(x_1,x_2,\dots,x_T)$，计算观测序列 $\mathbf{x}$ 出现的概率 $P(\mathbf{x}|\lambda)$，也就是先验概率。

通过概率公式可以直接计算，通过列举所有长度为 $T$ 可能的状态序列 $\mathbf{z}=(z_1,z_2,\dots,z_T)$，求每个状态序列 $\mathbf{z}$ 与观测序列 $\mathbf{x}$ 的联合概率 $P(\mathbf{x}, \mathbf{z}|\lambda)$，然后对所有可能的状态序列求和，就可以得到先验概率 $P(\mathbf{x}|\lambda)$。

状态序列 $\mathbf{z}=(z_1,z_2,\dots,z_T)$ 的概率

$$P(\mathbf{z}|\lambda)=\pi(z_1)\prod_{t=2}^T A(z_t|z_{t-1})$$

给定状态序列，观测序列的条件概率为

$$p(\mathbf{x}|\mathbf{z},\lambda)=\prod_{t=1}^T B(x_t|z_{t})$$

因此状态序列 $\mathbf{z}$ 和观测序列 $\mathbf{x}$ 联合概率为

$$P(\mathbf{x},\mathbf{z}|\lambda)=P(\mathbf{x}|\mathbf{z},\lambda)P(\mathbf{z}|\lambda)$$

然后对所有可能的状态序列 $\mathbf{z}$ 求和，得到观测序列 $\mathbf{x}$ 的概率为

$$\begin{aligned} P(\mathbf{x}|\lambda)&=\sum_{\mathbf{z}}P(\mathbf{x}|\mathbf{z},\lambda)P(\mathbf{z}|\lambda)\\ &=\sum_{\mathbf{z}}\pi(z_1)\prod_{t=2}^TA(z_{t}|z_{t-1})\prod_{t=1}^TB(x_t|z_t) \end{aligned}$$

状态序列 $\mathbf{z}$ 的可能情况有 $N^T$ 种，因此时间复杂度为 $O(TN^T)$，通过动态规划的思想可以将算法进行优化。

3.1 前向算法

从上可以知道观测序列的概率

$$P(\mathbf{x}|\lambda)=\sum_{\mathbf{z}}\pi(z_1)\prod_{t=2}^TA(z_{t}|z_{t-1})\prod_{t=1}^TB(x_t|z_t)$$

对于不同的状态序列都需要重新计算一遍该公式，但依照动态规划的思想，中间计算结果可以保存下来从而减少计算量，假设 $T=3$ 的情况下

$$\begin{aligned} P(\mathbf{x}|\lambda)&=\sum_{z_1,z_2,z_3}\pi(z_1)\prod_{t=2}^3A(z_{t}|z_{t-1})\prod_{t=1}^3B(x_t|z_t)\\ &=\sum_{z_3}\underbrace{B(x_3|z_3)\sum_{z_2}A(z_{3}|z_{2})\underbrace{B(x_2|z_2)\sum_{z_1}A(z_{2}|z_{1})\underbrace{\pi(z_1)B(x_1|z_1)}_{\alpha_1(z_1)}}_{\alpha_2(z_2)}}_{\alpha_3(z _3)} \end{aligned}$$

我们可以发现

$$\alpha_2(z_2)=B(x_2|z_2)\sum_{z_1}A(z_{2}|z_{1})\alpha_1(z_1)$$ $$\alpha_3(z_3)=B(x_3|z_3)\sum_{z_2}A(z_{3}|z_{2})\alpha_2(z_2)$$

以上 $\alpha_t(z_t)$ 就是每次重复计算的过程结果，如果保存下来的话就可以减少计算量，通过推导可以得到递推公式

$$\alpha_{t+1}(i)=b_i(x_{t+1})\sum_{j=1}^Na_{ij}\alpha_t(i)\qquad i=1,2,\dots,N$$

$\alpha$ 实际上就是时刻 $t$ 给定部分观测序列 $x_1,x_2,\dots,x_t$ 且状态为 $i$ 的概率，称为前向概率

$$\alpha_t(z_t=i)=P(x_1,x_2,\dots,x_t,z_t=i|\lambda)$$

如果状态空间的数量为 $4$，那么原本需要计算 $444$ 次，而上述算法只需要 $44+44$ 次，时间复杂度由 $O(TN^T)$ 降到了 $O(TN^2)$

有了递推公式之后，动态规划算法还需要初始化状态和终止条件，前向算法如下

1. 初始化状态 $\alpha_1(i)=\pi(i)b_i(x_1)$。
2. 对于每一时刻 $t=1,2,\dots,T-1$ 计算 $$\alpha_{t+1}(i)=b_i(x_{t+1})\sum_{j=1}^Na_{ij}\alpha_t(i)\qquad i=1,2,\dots,N$$
3. 最终计算结束状态 $$P(\mathbf{x}|\lambda)=\sum_{i=1}^N\alpha_{T}(i)$$

3.2 后向算法

前向算法是从初始状态向结束状态进行计算，后向算法则是从结束状态向前得到递推公式，同样在假设 $T=3$ 的情况下

$$\begin{aligned} P(\mathbf{x}|\lambda)&=\sum_{z_1,z_2,z_3}\pi(z_1)\prod_{t=2}^3A(z_{t}|z_{t-1})\prod_{t=1}^3B(x_t|z_t)\\ &=\underbrace{\sum_{z_1}\pi(z_1)B(x_1|z_1)\underbrace{\sum_{z_2}A(z_{2}|z_{1})B(x_2|z_2)\underbrace{\sum_{z_3}A(z_{3}|z_{2})B(x_3|z_3)}_{\beta_2(z_2)}}_{\beta_1(z_1)}}_{\beta_0} \end{aligned}$$

对于 $t=2$ 时，根据观测独立性假设有 $P(x_3|z_3) = P(x_3|z_3,z_2)$，因此

$$\begin{aligned} \beta_2(z_2)&=\sum_{z_3}A(z_{3}|z_{2})B(x_3|z_3) \\ &=\sum_{z_3}P(z_{3}|z_{2})P(x_3|z_3)\\ &=\sum_{z_3}P(z_{3}|z_{2})P(x_3|z_3,z_2) \\ &=P(x_3|z_2) \end{aligned}$$

并且

$$\begin{aligned} \beta_1(z_1)&=\sum_{z_2}A(z_{2}|z_{1})B(x_2|z_2)\beta_2(z_2) \\ &=\sum_{z_2}P(z_{2}|z_{1})P(x_2|z_2)P(x_3|z_2)\\ &=P(x_2,x_3|z_1) \end{aligned}$$

通过归纳可以推导出递推公式

$$\beta_{t}(i)=\sum_{j=1}^Na_{ij}b_j(x_{t+1})\beta_{t+1}(j)\qquad i=1,2,\dots,N$$

$\beta_t$ 即为在时刻 $t$ 状态为 $i$ 的条件下，从 $t+1$ 到 $T$ 的部分观测序列的概率，称为后向概率

$$\beta_{t}(i)=P(x_{t+1},x_{t+2},\dots,x_{T}|z_t=i,\lambda)$$

后向算法同样需要确定初始化状态和终止条件

1. 初始化状态 $\beta_T(i)=1$。
2. 对于每一时刻 $t=1,2,\dots,T-1$ 计算 $$\beta_{t}(i)=\sum_{j=1}^Na_{ij}b_j(x_{t+1})\beta_{t+1}(j)\qquad i=1,2,\dots,N$$
3. 最终计算结束状态 $$P(\mathbf{x}|\lambda)=\sum_{i=1}^N\pi(i)b_i(x_{1})\beta_{1}(i)$$

3.3 概率计算

有了前向概率和后向概率，可以直接计算一些概率值。

由前向概率和后向概率的定义可以知道

$$\alpha_{t}(i)\beta_{t}(i) = P(z_t=i,\mathbf{x}|\lambda)$$

因此，在某一时刻 $t$，观测序列的概率 $P(\mathbf{x}|\lambda)$ 可以由该时刻的前向和后向概率计算

$$P(\mathbf{x}|\lambda) = \sum_{i=1}^N\alpha_{t}(i)\beta_{t}(i)=\sum_{i=1}^N\sum_{j=1}^N\alpha_{t}(i)a_{ij}b_j(x_{t+1})\beta_{t+1}(j)$$

给定观测序列 $\mathbf{x}$ 和模型参数 $\lambda$，在时刻 $t$ 状态为 $i$ 的条件概率为

$$\gamma_t(i)=P(z_t=i|\mathbf{x},\lambda)=\frac{P(z_t=i,\mathbf{x}|\lambda)}{P(\mathbf{x}|\lambda)}$$

因此，由前向和后向概率可得

$$\gamma_t(i)=\frac{P(z_t=i,\mathbf{x}|\lambda)}{P(\mathbf{x}|\lambda)}=\frac{\alpha_{t}(i)\beta_{t}(i)}{\displaystyle \sum_{i=1}^N\alpha_{t}(i)\beta_{t}(i)}$$

给定观测序列 $\mathbf{x}$ 和模型参数 $\lambda$，在时刻 $t$ 状态为 $i$ 且时刻 $t+1$ 的状态为 $j$ 的条件概率为

$$\xi_t(i,j)=P(z_t=i,z_{t+1}=j|\mathbf{x},\lambda)$$

通过前向后向概率计算

$$\begin{aligned} \xi_t(i,j)&=\frac{P(z_t=i,z_{t+1}=j,\mathbf{x}|\lambda)}{P(\mathbf{x}|\lambda)}\\ &= \frac{\alpha_{t}(i)a_{ij}b_j(x_{t+1})\beta_{t+1}(j)}{\displaystyle\sum_{i=1}^N\sum_{j=1}^N\alpha_{t}(i)a_{ij}b_j(x_{t+1})\beta_{t+1}(j)} \end{aligned}$$

给定观测序列 $\mathbf{x}$ ，状态 $i$ 出现的期望值

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

给定观测序列 $\mathbf{x}$ ，由状态 $i$ 转移的期望值

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

给定观测序列 $\mathbf{x}$ ，由状态 $i$ 转移的期望值

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

4. 学习算法

隐马尔科夫模型参数的学习可分为监督学习与无监督学习。

4.1 监督学习

在监督学习中，观测序列相当于特征值，状态序列相当于标注结果，假设给出数据集

$$D=\{(\mathbf x_1,\mathbf z_1),(\mathbf x_2,\mathbf z_2),...,(\mathbf x_S,\mathbf z_S)\}$$

其中，观测序列 $\mathbf x_i$ 与状态序列 $\mathbf z_i$ 长度均为 $T$，因此可以通过最大似然估计来确定隐马尔科夫模型的参数。

假设样本中时刻 $t$ 处于状态 $i$ 时刻 $t+1$ 转移到状态 $j$ 的频数为 $c_{ij}$，状态空间的总数为 $N$，那么状态转移概率 $a_{ij}$ 的估计为

$$\hat a_{ij}=\frac{c_{ij}}{\displaystyle \sum_{j=1}^{N}c_{ij}}\qquad i,j=1,2,\dots,N$$

设样本状态 $j$ 并观测为 $k$ 的频数是 $d_{ij}$，观测空间的总数为 $M$，那么状态为 $j$ 时观测为 $k$ 的概率估计为

$$\hat{b}_{j}(k)=\frac{d_{ij}}{\displaystyle \sum_{j=1}^{N}d_{ij}}\qquad k=1,2,\dots,M;j=1,2,\dots,N$$

初始状态概率 $\pi_i$ 的估计 $\hat{\pi}_i$ 为 $S$ 个样本中初始状态为 $i$ 的频率。

4.2 无监督学习

如果给定训练数据只包含 $S$ 个长度为 $T$ 的观测序列，而缺少状态序列，那么状态序列可以视为不可观测的隐藏变量，隐马尔科夫模型实际上就是一个存在隐藏变量的概率模型

$$P(\mathbf{x}|\lambda)=\sum_{\mathbf{z}}P(\mathbf{x}|\mathbf{z},\lambda)P(\mathbf{z}|\lambda)$$

我们可以使用 EM 算法求解上述概率模型，同时应用在 HMM 中的 EM 算法也称为 Baum-Welch 算法。由之前已经推导出，第 $k+1$ 次迭代只需要最大化下式即可。

$$\arg\max_{\lambda} \sum_{\mathbf{z}}{P}(\mathbf{z}|\mathbf{X}, \lambda_k)\ln{P}(\mathbf{X}, \mathbf{z}|\lambda)$$

由隐马尔科夫三要素可以得到完全数据的似然函数为

$$P(\mathbf{x},\mathbf{z}|\lambda)=\pi(z_1)\prod_{t=2}^TA(z_{t}|z_{t-1})\prod_{t=1}^TB(x_t|z_t)$$

相应的对数似然函数为

$$\ln P(\mathbf{x},\mathbf{z}|\lambda)=\ln{\pi(z_1)}+\sum_{t=2}^T\ln A(z_{t}|z_{t-1})+\sum_{t=1}^T\ln B(x_t|z_t)$$

E 步，得到在 $\lambda_k$ 下的上述对数似然函数的期望

$$\begin{aligned} E_{\mathbf{z|\mathbf{X},\lambda}}\{\ln\mathcal{P}(\mathbf{X}, \mathbf{z}|\theta)\} &= \sum_{\mathbf{z}}{P}(\mathbf{z}|\mathbf{X}, \lambda_k)\ln{P}(\mathbf{X}, \mathbf{z}|\lambda) \\ &= \sum_{\mathbf{z}}{P}(\mathbf{z}|\mathbf{X}, \lambda_k)\ln{\pi(z_1)}+\sum_{\mathbf{z}}\sum_{t=2}^T{P}(\mathbf{z}|\mathbf{X}, \lambda_k)\ln A(z_{t}|z_{t-1})\\ &+\sum_{\mathbf{z}}\sum_{t=1}^T{P}(\mathbf{z}|\mathbf{X}, \lambda_k)\ln B(x_t|z_t) \end{aligned}$$

M 步，最大化上述期望，可以分别最大化等式中的每一项。

a. 更新初始状态概率 $\pi$

$$\begin{aligned} F_1(\pi;\lambda_k) &= \sum_{\mathbf{z}}{P}(\mathbf{z}|\mathbf{X}, \lambda_k)\ln{\pi(z_1)} \\ &= \sum_{z_1}{P}(z_1|\mathbf{X}, \lambda_k)\ln{\pi(z_1)} \end{aligned}$$

对上式进行优化，$\pi$ 是唯一变量，同时满足约束条件 $\displaystyle\sum_{z_1=i}^N\pi(z_1)=1$，利用拉格朗日乘子法，得到拉格朗日函数

$$\sum_{z_1}{P}(z_1|\mathbf{X}, \lambda_k)\ln{\pi(z_1)}+\theta\left(\displaystyle\sum_{z_1=i}^N\pi(z_1)-1\right)$$

对其求偏导数并令结果为 0

$$\frac{\partial}{\partial\pi(z_1)}\left[\sum_{z_1}{P}(z_1|\mathbf{X}, \lambda_k)\ln{\pi(z_1)}+\theta\left(\displaystyle\sum_{z_1}\pi(z_1)-1\right)\right]$$

可得

$${P}(z_1|\mathbf{X}, \lambda_k)+\theta\pi(z_1)=0\qquad z_1=i=1,2,\dots,N$$

对上式进行合并

$$\sum_{z_1}{P}(z_1|\mathbf{X}, \lambda_k)+\theta\sum_{z_1}\pi(z_1)=0$$

条件概率之和为 1，最终可得

$$\theta=-1$$

因此求得

$$\pi(z_1)={P}(z_1|\mathbf{X}, \lambda_k)$$

由前面已经得到

$${P}(z_t=i|\mathbf{X}, \lambda_k)=\gamma_t(i)=\frac{\alpha_{t}(i)\beta_{t}(i)}{\displaystyle \sum_{i=1}^N\alpha_{t}(i)\beta_{t}(i)}$$

因此解的

$$\pi(z_1=i)=\gamma_1(i)$$

b. 更新状态转移概率 $A$

$$\begin{aligned} F_2(A;\lambda_k) &= \sum_{\mathbf{z}}\sum_{t=2}^T{P}(\mathbf{z}|\mathbf{X}, \lambda_k)\ln A(z_{t}|z_{t-1}) \\ &= \sum_{t=2}^T\sum_{i,j}{P}(z_{t-1}=i,z_t=j|\mathbf{X}, \lambda_k)\ln{A(z_{t}=j|z_{t-1}=i)} \end{aligned}$$

前面已经求得

$$\xi_t(i,j)=P(z_t=i,z_{t+1}=j|\mathbf{x},\lambda)$$

因此

$$F_2(A;\lambda_k)=\sum_{i,j}\sum_{t=2}^{T}\xi_{t-1}(i,j)\ln{a_{ij}}$$

如同计算初始状态概率，需要满足约束条件 $\displaystyle \sum_j a_{ij}=1$，通过拉格朗日乘子法得到拉格朗日函数

$$\sum_{i,j}\sum_{t=2}^{T}\xi_{t-1}(i,j)\ln{a_{ij}}+\theta\left(\displaystyle\sum_{j=1}^Na_{ij}-1\right)$$

偏导数

$$\sum_{t=2}^{T}\xi_{t-1}(i,j)+\theta a_{ij}=0 \qquad i,j=1,2,\dots,N$$

根据 $j$ 的所有取值合并上述公式

$$\sum_j\sum_{t=2}^{T}\xi_{t-1}(i,j)+\theta=0 \qquad i=1,2,\dots,N$$

根据条件概率

$$\begin{aligned} \sum_j\sum_{t=2}^{T}\xi_{t-1}(i,j)&=\sum_j\sum_{t=2}^{T}P(z_{t-1}=i,z_{t}=j|\mathbf{x},\lambda)\\ &=\sum_{t=2}^{T}\sum_jP(z_{t-1}=i,z_{t}=j|\mathbf{x},\lambda)\\ &=\sum_{t=2}^{T}P(z_{t-1}=i|\mathbf{x},\lambda)\\ &=\sum_{t=2}^{T}\gamma_{t-1}(i)\\ \end{aligned}$$

因此

$$\theta=-\sum_{t=2}^{T}\gamma_{t-1}(i)$$

最终解得

$$a_{ij}=\frac{\displaystyle\sum_{t=2}^{T}\xi_{t-1}(i,j)}{\displaystyle\sum_{t=2}^{T}\gamma_{t-1}(i)}$$

c. 更新观测概率 $B$

$$\begin{aligned} F_3(B;\lambda_k) &= \sum_{\mathbf{z}}\sum_{t=1}^T{P}(\mathbf{z}|\mathbf{X}, \lambda_k)\ln B(x_t|z_t) \\ &= \sum_{t=1}^T\sum_{z_t}{P}(z_t|\mathbf{X}, \lambda_k)\ln{B(x_t|z_t)}\\ &= \sum_{t=1}^T\sum_{j}\gamma_{t}(j)\ln{b_j(x_t))}\\ \end{aligned}$$

同样具有约束条件 $\displaystyle \sum_{k=1}^Mb_j(k)=1$，因此拉格朗日函数

$$\sum_{t=1}^T\sum_{j}\gamma_{t}(j)\ln{b_j(x_t)}+\theta\left(\sum_{k=1}^Mb_j(k)-1\right)$$

偏导数

$$\sum_{t=1}^{T}\gamma_{t}(j)I(x_t=k)+\theta b_j(k)=0 \qquad k=1,2,\dots,M;j=1,2,\dots,N$$

合并 $k$ 个方程，解得 $\displaystyle\theta=-\sum_{t=1}^{T}\gamma_{t}(j)$，因此

$$b_j(k)=\frac{\displaystyle \sum_{t=1}^{T}\gamma_{t}(j)I(x_t=k)}{\displaystyle \sum_{t=1}^{T}\gamma_{t}(j)}$$

注意这里是对 $k$ 求和的结果为 $1$，同时 $b_j(k)$ 相当于固定变量，而 $b_j(x_t)$ 只有在 $x_t=k$ 的情况下才是同一个值，才具有偏导数。

总结

5. 预测算法

已知 $\mathbf{x},\lambda$，求得状态概率 $P(\mathbf{z}|\mathbf{x},\lambda)$ 即为预测问题。

隐马尔科夫模型预测分为近似算法和维特比算法，近似算法相当于路径规划中每走一步只选最短的路线，也就是贪婪算法，而维特比算法则相当于动态规划算法。

5.1 近似算法

由前已知

$$\gamma_t(i)=P(z_t=i|\mathbf{x},\lambda)=\frac{\alpha_{t}(i)\beta_{t}(i)}{\displaystyle \sum_{i=1}^N\alpha_{t}(i)\beta_{t}(i)}$$

因此，在给定 $\mathbf{x},\lambda$ 的情况下，想要得到隐藏的状态序列，可以在每一时刻 $t$ 选择最大的条件概率 $P(z_t=i|\mathbf{x},\lambda)$ 对应的隐藏状态 $\hat{z}_t$，由于分母都一样，因此只需要考虑分子即可，即

$$\hat{z}_t=\arg\max_{i}(\alpha_{t}(i)\beta_{t}(i))$$

由此得到状态序列

$${\mathbf{\hat z}}=(\hat{z}_1,\hat{z}_2,\cdots,\hat{z}_t)$$

5.2 维特比算法

近似算法相当于单步最优，要想得到全局最优的结果，则需要根据联合分布函数得到联合概率最大对应的状态，即

$${\mathbf{\hat z}}=\arg\max_{\mathbf{z}} P(\mathbf{z},\mathbf{x}|\lambda)$$

我们分步求取当前的联合概率，假设

$$\mathbf{z}_t = (z_1,z_2,\dots,z_t)$$

在最终预测的时候模型参数 $\lambda$ 确定，因此可以省略。联合概率为

$$\begin{aligned} P(\mathbf{z}_t,\mathbf{x}_t)&=P(\mathbf{z}_t,\mathbf{x}_t|\mathbf{z}_{t-1},\mathbf{x}_{t-1})P(\mathbf{z}_{t-1},\mathbf{x}_{t-1})\\ &=P(z_t,x_t|\mathbf{z}_{t-1},\mathbf{x}_{t-1})P(\mathbf{z}_{t-1},\mathbf{x}_{t-1})\\ &=P(x_t|z_t,\mathbf{z}_{t-1},\mathbf{x}_{t-1})P(z_t|\mathbf{z}_{t-1},\mathbf{x}_{t-1})P(\mathbf{z}_{t-1},\mathbf{x}_{t-1})\\ &=P(x_t|z_t)P(z_t|z_{t-1})P(\mathbf{z}_{t-1},\mathbf{x}_{t-1})\\ &=B(x_t|z_t)A(z_t|z_{t-1})P(\mathbf{z}_{t-1},\mathbf{x}_{t-1})\\ \end{aligned}$$

定义

$$d_t(i)=\max_{\mathbf{z}_{t-1}}P(\mathbf{z}_{t-1},z_t=i,\mathbf{x}_{t})$$

对于 $t=2,\dots,T$ 且 $i=1,\dots,N$，$d_t(i)$ 存在以下递归关系

$$\begin{aligned} d_t(i)&=\max_{\mathbf{z}_{t-1}}P(\mathbf{z}_{t-1},z_t=i,\mathbf{x}_{t})\\ &=\max_{\mathbf{z}_{t-1}}B(x_t|z_t=i)A(z_t=i|z_{t-1})P(\mathbf{z}_{t-1},\mathbf{x}_{t-1})\\ &=B(x_t|z_t=i)\max_{z_{t-1}}A(z_t=i|z_{t-1})\max_{\mathbf{z}_{t-2}}P(\mathbf{z}_{t-2},z_{t-1}=j,\mathbf{x}_{t-1})\\ &=B(x_t|z_t=i)\max_{z_{t-1}}A(z_t=i|z_{t-1})d_{t-1}(z_{t-1}=j)\\ \end{aligned}$$

再确定初始化和结束条件，最后完善维特比算法

维特比算法

1. 初始化，对于 $i=1,2,\dots,N$，计算 $d_1(i)=\pi(i)b_i(x_1)$
2. 对于 $t=2,3,\dots,T$，计算 $$d_t(i)=b_i(x_t)\max_{j}d_{t-1}(j)a_{ji}\qquad i=1,2,\dots,N$$ $$f_t(i)=\arg\max_jd_{t-1}(j)a_{ji}\qquad i=1,2,\dots,N$$
3. 最终得到 $\displaystyle z_T^*=\arg\max_jd_T(j)$
4. 回溯，对于 $t=T-1,\dots,1$ $$z_{t}^*=f_{t+1}(z_{t+1}^*)$$
5. 返回 $\mathbf z^=(z^_1, z^_2, \dots, z^_T)$

当 $T$ 很大时，计算概率时的舍入误差可能会成为问题，为避免问题，可以使用对数计算

$$d_t(i)=\max_{\mathbf{z}_{t-1}}\log P(\mathbf{z}_{t-1},z_t=i,\mathbf{x}_{t})$$

递推公式则为

$$d_t(i)=\log b_i(x_t)+ \max_{j}\left\{d_{t-1}(j)+\log a_{ji}\right\}\qquad i=1,2,\dots,N$$

参考

1. Hidden Markov model - Wikipedia
2. 隐马尔科夫模型（HMM）一基本模型与三个基本问题 - zhihu
3. Lecture notes: Hidden Markov Models
4. Lecture 9: Hidden Markov Model
5. History and Theoretical Basicsof Hidden Markov Models
6. Hidden Markov Models

---

Machine Learning

2022-04-22