隐马尔可夫模型HMM模型笔记1--前向后向算法

隐马尔可夫模型HMM模型细节和推导1.概述隐马尔可夫模型(Hidden Markov Model,HMM) 是传统的机器学习模型，在自然语言处理和模式识别中，运用广泛。虽然有RNN和LSTM的提出，作为机器学习的传统模型，还是有必要深入了解。HMM模型中，包含两种序列，分别为状态序列和观测序列。其中状态序列我们不可见，而观测序列可见，并且观测序列以概率的形式，由状态序列生成。比如语音识...

Longlongaaago

779人浏览 · 2020-03-28 10:34:47

Longlongaaago · 2020-03-28 10:34:47 发布

隐马尔可夫模型HMM模型笔记1--前向后向算法

1.概述

隐马尔可夫模型(Hidden Markov Model,HMM) 是传统的机器学习模型，在自然语言处理和模式识别中，运用广泛。虽然有RNN和LSTM的提出，作为机器学习的传统模型，还是有必要深入了解。

HMM模型中，包含两种序列，分别为状态序列和观测序列。其中状态序列我们不可见，而观测序列可见，并且观测序列以概率的形式，由状态序列生成。比如语音识别中，我们听到的声音，和其背后的文字的关系。计算机能听到语音，但是它看不到语音所表达的文字，所以需要用机器学习模型让其自行“脑补”。还有词义标注等等，应用很多。

直观的理解上就是，HMM实际上包含三个参数， $\large \lambda =(A,B,\Pi )$ ，分别表示 $\large A$ （转移概率矩阵）， $\large B$ （观测状态生成的概率矩阵）以及 $\large \Pi$ （初始状态矩阵）。假设我们已经得到了这个参数 $\large \lambda =(A,B,\Pi )$ ，那我们就可以用这个模型随机地生成一段序列。当然这个不是最主要的，最主要的是要解决三个基本问题：

1.评估观察序列概率，即我们假设有了模型 $\large \lambda =(A,B,\Pi )$ ，当得到一条新的观测序列，那么这条观测序列出现的概率是多少？

2.模型参数学习问题，即我们得到了一些可以学习的观测序列，那么如何去估计模型 $\large \lambda =(A,B,\Pi )$ 的参数？

3.预测问题，也称为解码问题或者推断问题，即当我们假设有了模型 $\large \lambda =(A,B,\Pi )$ ，如何通过得到的观测序列，去推断其状态序列？

2.定义

引用这一篇的模型定义（https://www.cnblogs.com/pinard/p/6945257.html）：

假设 $\large Q$ 是所有可能的隐藏状态的集合， $\large V$ 是所有可能的观测状态的集合，即：

$\large Q=\left \{ q_{1},q_{2},\cdots q_{N-1},q_{N}\right \}$ , $\large V=\left \{ v_{1},v_{2},\cdots v_{M-1},v_{M}\right \}$ （1）

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

对于一个长度为 $\large T$ 的序列， $\large I$ 是对应的状态序列, $\large O$ 是对应的观察序列，即：

$\large I=\left \{ i_{1},i_{2},\cdots ,i_{t},\cdots,i_{T-1},i_{T}\right \}$ , $\large O=\left \{ o_{1},o_{2},\cdots ,o_{t},\cdots o_{T-1},o_{T}\right \}$ （2）

其中，任意一个隐藏状态 $\large i_{t}\in Q$ ,任意一个观察状态 $\large o_{t}\in V$

HMM模型做了两个很重要的假设如下：

1.齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态。

如果在时刻 $\large t$ 的隐藏状态是 $\large i_{t}=q_{i}$ ,在时刻 $\large t+1$ 的隐藏状态是 $\large i_{t+1}=q_{j}$ , 则从时刻 $\large t$ 到时刻 $\large t+1$ 的HMM状态转移概率 $\large a_{ij}$ 可以表示为：

$\large a_{ij}=P(i_{t+1}=q_{j}|i_{t}=q_{i} )$ （3）

这样转移概率 $\large a_{ij}$ 就组成了上述的马尔科夫链的状态转移矩阵 $\large A$ ：

$\large A=\left [ a_{ij} \right ]_{N\times N}$ （4）

2. 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态。如果在时刻 $\large t$ 的隐藏状态是 $\large i_{t}=q_{j}$ 而对应的观察状态为 $\large o_{t}=v_{k}$ , 则该时刻观察状态 $\large v_{k}$ 在隐藏状态 $\large q_{j}$ 下生成的概率为 $\large b_{j}(k)$ ,满足：

$\large B=\left [b_{j}(k) \right ]_{N\times M}$ （5）

3.初始状态概率。即在初始状态， $\large t=1$ 的隐藏状态的概率分布 $\large \Pi$ ：

$\large \Pi=\left [ \pi(i) \right ]_{N}$ ,且 $\large \pi(i)=P(i_{1}=q_{i})$ （6）

由此，组成了上述的HMM模型的参数， $\large \lambda =(A,B,\Pi )$ ，其中 $\large A$ 为状态转移概率矩阵， $\large B$ 为观测状态概率矩阵， $\large \Pi$ 为初始状态概率矩阵。

2.评估观测序列概率

2.1.暴力求解

假设我们已知HMM的模型参数， $\large \lambda =(A,B,\Pi )$ ，那么如何求解对应观测序列的概率呢？即求解 $\large P(O|\lambda )$ 的概率。

那么我们首先可能想到的办法就是，我们可以利用状态序列和观测序列的联合概率，进行求解，即把边缘概率转换成联合概率的求和。

$\large P(O|\lambda ) = \sum_{I} P(O,I|\lambda )=\sum_{I} P(I|\lambda )\cdot P(O|I,\lambda )$ （7）

其中：

$\large P(I|\lambda )=$ $\large P( i_{1},i_{2},\cdots ,i_{t},\cdots,i_{T-1},i_{T}|\lambda )$ $\large =P( i_{1}|\lambda )\cdot P( i_{2}| i_{1},\lambda )\cdot P( i_{3} | i_{2}, i_{1},\lambda )\cdot \cdot \cdot P( i_{T}|i_{1},i_{2},\cdots ,i_{t},\cdots,i_{T-1},\lambda )$

$\large =P( i_{1}|\lambda )\cdot P( i_{2}| i_{1},\lambda )\cdot P( i_{3} | i_{2}, \lambda )\cdot \cdot \cdot P( i_{T}|i_{T-1},\lambda )$ (齐次马尔科夫链假设)

$\large =\pi _{i_{1}}\cdot a_{i_{1}i_{2}}\cdot a_{i_{2}i_{3}}\cdot \cdot \cdot a_{i_{T-1}i_{T}}$ （8）

对应的，给定某个确定的状态序列 $\large I=\left \{ i_{1}=q_{*},i_{2}=q_{*},\cdots ,i_{t}=q_{*},\cdots,i_{T-1}=q_{*},i_{T}=q_{*}\right \}$ （假设这个序列的各个状态都是知道的用 $\large q_{*}$ 来表示，后续的序列表示，都会进行省略，即认为 $\large i_{t}$ 是有值的，是属于某个状态状态 $\large q_{*}$ 的， $\large o_{t}$ 是有值的，是属于某个观测 $\large v_{*}$ 的）那么，对应的观察序列 $\large O=\left \{ o_{1},o_{2},\cdots ,o_{t},\cdots o_{T-1},o_{T}\right \}$ 的出现概率是：

$\large P(O|I,\lambda )=P(o_{1},o_{2},\cdots ,o_{t},\cdots o_{T-1},o_{T}|I,\lambda)$

$\large =P(o_{1}|I,\lambda)\cdot P(o_{2}|I,\lambda)\cdot \cdot \cdot P(o_{T-1}|I,\lambda)\cdot P(o_{T}|I,\lambda)$ (各个观测值直接条件独立)

$\large =P(o_{1}|i_{1},\lambda)\cdot P(o_{2}|i_{2},\lambda)\cdot \cdot \cdot P(o_{T-1}|i_{T-1},\lambda)\cdot P(o_{T}|i_{T},\lambda)$ ( 观测独立性假设)

$\large =b_{i_{1}}(o_{1})\cdot b_{i_{2}}(o_{2})\cdot \cdot \cdot b_{i_{T-1}}(o_{T-1})\cdot b_{i_{T}}(o_{T})$ （9）

回到（7）式，就可以看到，这样是对所有的状态序列进行遍历，来求解对应观测序列的概率，这样的一个问题在于，每个状态都包含N种可供选择的状态数，所以所有的状态就有 $\large N^{T}$ 种组合，而且每次计算都要计算 $\large O(T)$ 所以复杂度为 $\large O(TN^{T})$ ，那这种指数级增长的复杂度肯定是不可取的。所以引出下面的前向后向算法。

2.2.前向算法

还是上面的问题，我们要求解 $\large P(O|\lambda )$ 的概率，可以转换成如下形式：

$\large P(O|\lambda )= \sum_{i_{T}} \large P(o_{1:T},i_{T}|\lambda )$ （10）

注***写法上进行了省略， $\large P(O|\lambda )= \sum_{i_{T}} \large P(o_{1:T},i_{T}|\lambda )$ 等同于 $\large P(O|\lambda )= \sum_{j=1}^{N} \large P(o_{1:T},i_{T}=q_{j}|\lambda )$ ，为了书写简便， $\large i_{T}$ 这个变量表示包含某个状态，即 $\large i_{T}=q_{j}$ ，观测 $\large o_{T}$ 同理，没有把每个变量的状态值写出来，下同。

$\large P(o_{1:T},i_{T}|\lambda )= \sum_{i_{T-1}} P(o_{1:T},i_{T-1},i_{T}|\lambda )$

$\large = \sum_{i_{T-1}} P(o_{1:T-1},o_{T},i_{T-1},i_{T}|\lambda )= \sum_{i_{T-1}} P(o_{1:T-1},i_{T-1}|\lambda )\cdot P(o_{T},i_{T}|o_{1:T-1},i_{T-1},\lambda )$

$\large = \sum_{i_{T-1}} P(o_{1:T-1},i_{T-1}|\lambda ) \cdot P(i_{T}|o_{1:T-1},i_{T-1},\lambda ) \cdot P(o_{T}|i_{T},o_{1:T-1},i_{T-1},\lambda )$

$\large = \sum_{i_{T-1}} P(o_{1:T-1},i_{T-1}|\lambda ) \cdot P(i_{T}|i_{T-1},\lambda ) \cdot P(o_{T}|i_{T},\lambda )$ （第2项是齐次马尔科夫链假设，第3项是观测独立性）（11）

其中 $\large o_{1:T}$ 表示，从第1个到第 $\large T$ 个所有的观测序列，那中间的 $\large t$ 时刻也是同理，我们把（11） $\large T$ 改成 $\large t$ ，以此类推，我们就能得到

$\large P(o_{1:t},i_{t}|\lambda )= \sum_{i_{t-1}} P(o_{1:t},i_{t-1},i_{t}|\lambda )$

$\large = \sum_{i_{t-1}} P(o_{1:t-1},i_{t-1}|\lambda ) \cdot P(i_{t}|i_{t-1},\lambda ) \cdot P(o_{t}|i_{t},\lambda )$ （12）

能够发现 $\large P(i_{t}|i_{t-1},\lambda )$ 就是对应的状态转移概率， $\large P(o_{t}|i_{t},\lambda )$ 表示为状态到观测的生成概率。所以这就可以利用动态规划去求解。在这里定义 $\large P(o_{1:t},i_{t}|\lambda )$ 表示为 $\large \alpha _{t}(i_{t})$ ，即表示为在 $\large t$ 时刻，对应的状态为 $\large i_{t}$ 的前向概率（ $\large i_{t}$ 有特定的状态，没有写出来，实际上 $\large i_{t}=q_{j},j\in [1,N]$ ），在所以就又如下计算公式：

$\large P(o_{1:t},i_{t} |\lambda )=\sum _{i_{t-1}}\alpha _{t-1}(i_{t-1})\cdot a_{i_{t}i_{t-1}}\cdot b_{i_{t}}(o_{t})$ （13）

这样，我们就能利用动态规划去一步一步地生成每一步的概率，我们可以利用公式（13）从 $\large P(o_{1},i_{1}|\lambda )$ 从后向前生成。

$\large P(o_{1},i_{1}|\lambda )=P(i_{1}|\lambda )\cdot P(o_{1}|i_{1},\lambda )=\pi(i_{1})\cdot b_{i_{1}}(o_{1})$ （14）

从递推公式可以看出，前向算法的复杂度为 $\large O(TN^{2})$

至此，前向算法就讲解完毕了。

2.3.后向算法

还是上面的问题，我们要求解 $\large P(O|\lambda )$ 的概率，可以转换成如下形式：

$\large P(O|\lambda )= \sum_{i_{1}} \large P(o_{1:T},i_{1}|\lambda )$ (15)

$\large P(o_{1:T}|\lambda )= \sum_{i_{1}} \large P(o_{1:T},i_{1}|\lambda )=\sum_{i_{1}} \large P(o_{1},o_{2:T},i_{1}|\lambda )$

$\large =\sum_{i_{1}} \large P(i_{1}|\lambda )\cdot P(o_{2:T}|i_{1},\lambda )\cdot P(o_{1}|i_{1},o_{2:T},\lambda )$

$\large =\sum_{i_{1}} \large P(i_{1}|\lambda )\cdot P(o_{2:T}|i_{1},\lambda )\cdot P(o_{1}|i_{1},\lambda )$ 第3项是观测独立性 (16)

通过上述推导，我们可以知道，如果利用第一个状态的和序列的联合概率，也能求出对应的序列的概率，那么后续怎么继续计算呢？我们继续把公式（16）的 $\large P(o_{2:T}|i_{1},\lambda )$ 拿出来，进行一般化：

$\large P(o_{t+1:T}|i_{t},\lambda )= \sum_{i_{t+1}} P(o_{t+1:T},i_{t+1}|i_{t},\lambda )$

$\large P(o_{t+1:T},i_{t+1}|i_{t},\lambda)=P(o_{t+1},o_{t+2:T},i_{t+1}|i_{t},\lambda)$

$\large =P(i_{t+1}|i_{t},\lambda)\cdot P(o_{t+1},o_{t+2:T}|i_{t},i_{t+1},\lambda)$

$\large =P(i_{t+1}|i_{t},\lambda)\cdot P(o_{t+2:T}|i_{t},i_{t+1},\lambda)\cdot P(o_{t+1}|o_{t+2:T},i_{t},i_{t+1},\lambda)$

$\large =P(i_{t+1}|i_{t},\lambda)\cdot P(o_{t+2:T}|i_{t+1},\lambda)\cdot P(o_{t+1}|i_{t+1},\lambda)$ （D-Separation）（第2项是齐次马尔科夫链假设，第3项是观测独立性）（17）

那么通过这个推导，我们就能看到 $\large P(o_{t+1:T}|i_{t},\lambda )$ 和 $\large P(o_{t+2:T}|i_{t+1},\lambda)$ 之间的递推关系， $\large P(i_{t+1}|i_{t},\lambda)$ 正好是状态转移矩阵， $\large P(o_{t+1}|i_{t+1},\lambda)$ 正好是状态到观测的转移矩阵。在这里令 $\large P(o_{t+1:T}|i_{t},\lambda )$ 表示为 $\large \beta _{t}(i_{t})$ ,即表示为，在 $\large t$ 时刻，状态为 $\large i_{t}$ 的后向概率，（ $\large i_{t}$ 有特定的状态，没有写出来，实际上 $\large i_{t}=q_{j},j\in [1,N]$ ）。所以有如下递推公式：

$\large \beta _{t}(i_{t})= \sum_{i_{t+1}} \beta _{t+1}(i_{t+1})\cdot a_{i_{t+1}i_{t}}\cdot b_{i_{t+1}}(o_{t+1})$ （18）

同样的，我们从后往前推，所以要知道由于 $\large T$ 时刻的时候，整个序列都已经确定了，所以 $\large \beta _{T}(i_{t})$ 的概率设为1。

$\large \beta _{T}(i_{t}=q_{j})=1,j\in [1,N]$

这样就能从 $\large T-1,T-2,\cdot \cdot \cdot ,t,\cdot \cdot \cdot,2,1$ 陆续推导，对应的复杂度也为 $\large O(TN^{2})$ 。

至此，后向算法也讲解完毕。

2.4.前向/后向算法（Forward/Backward）

观测序列的概率可以用前向后向算法进行估计，但是前向后向算法的最终目的是什么？

在后续，需要参数学习的时候，我们需要求解 $\large P(i_{t}|O,\lambda )$ 的概率，即需要求解在给定序列 $\large O$ 的情况下，在 $\large t$ 时刻，对应的状态 $\large i_{t}$ 的概率（ $\large i_{t}$ 有特定的状态，没有写出来，实际上 $\large i_{t}=q_{j},j\in [1,N]$ ，为了方便书写）

$\large P(i_{t}|O,\lambda )=\frac{P(i_{t},O,\lambda)}{P(O,\lambda)}\propto P(i_{t},O,\lambda)$ （19）

$\large \propto$ 表示正比于，也就是 $\large P(i_{t}|O,\lambda )$ 和 $\large P(i_{t},O,\lambda)$ 有着正比关系，所以我们可以通过计算后者，来间接计算前者，然后继续将其拆分：

$\large P(i_{t},O,\lambda)=P(o_{t+1:T}|i_{t},o_{1:t},\lambda) \cdot P(i_{t},o_{1:t},\lambda)$ （20）

可以看到，上面已经出现了前向后向算法的雏形:

1. $\large P(o_{t+1:T}|i_{t},o_{1:t},\lambda)$ 中还多了一个 $\large o_{1:t}$ 的条件，通过D-Seperation（分隔定理）或者齐次马尔科夫链假设，可以发现实际上条件 $\large o_{1:t}$ 和 $\large o_{t+1:T}$ 之间是相互独立的。

2. $\large P(i_{t},o_{1:t},\lambda)$ 就是前面讨论的前向算法,所以可以再次简化成下式：

$\large P(i_{t},O,\lambda)=P(o_{t+1:T}|i_{t},\lambda) \cdot P(i_{t},o_{1:t},\lambda)$ （21）

能看到就是后向概率和前向概率的乘积

通过这样的方式，就可以回头计算 $\large P(i_{t}|O,\lambda )$ 的概率了，假设我们要求 $\large P(i_{t}=q_{1}|O,\lambda )$ 即，给定序列 $\large O$ 和参数 $\large \lambda$ 的条件下，第t个时刻，状态值为 $\large q_{1}$ 的概率为：