[TOC]
- 隐马尔可夫模型的基本概念
- 隐马尔可夫模型的定义
- 观测序列的生成过程
- 隐马尔可夫模型的三个基本问题
- 概率计算方法
- 直接计算法
- 前向算法
- 后向算法
- 一些概率与期望值的计算
- 学习算法
- 监督学习方法
- Baum-Welch算法
- Baum-Welch模型参数估计公式
- 预测算法
- 近似算法
- 维特比算法
-
我记得在第六章有一个经典的文献介绍最大熵的原理的，例子是语言翻译。这章有个类似的文献就是书中给出的前两个参考文献1， 书中的符号体系和书中的参考文献1的保持一致。
-
动态贝叶斯网络的最简单实现隐马尔可夫模型。HMM可以看成是一种推广的混合模型。
-
序列化建模，打破了数据独立同分布的假设。
-
有些关系需要理清
- 另外一个图
graph TD
subgraph 贝叶斯网络
A1((A))-->B1((B))
A1-->C1((C))
B1-->D1((D))
C1-->D1
end
subgraph 马尔可夫网络
A2((A))---B2((B))
A2---C2((C))
B2---D2((D))
C2---D2
end
另外，注意一点，在李老师这本书上介绍的HMM，涉及到举例子的，给的都是观测概率矩阵是离散的情况，对应了Multinominal HMM。但这个观测概率矩阵是可以为连续的分布的，比如高斯模型，对应了Gaussian HMM，高斯无处不在。具体可以参考hmmlearn库2
- HMM有两个基本假设和三个基本问题， 两个基本假设。$I$是隐变量。
有些基本的概念， 引用吴军在数学之美3之中的描述。
19世纪, 概率论的发展从对(相对静态的)随机变量的研究发展到对随机变量的时间序列$s_1,s_2, s_3, \dots,s_t,\dots$,即随机过程(动态的)的研究
数学之美,吴军
随机过程有两个维度的不确定性. 马尔可夫为了简化问题, 提出了一种简化的假设, 即随机过程中各个状态$s_t$的概率分布, 只与它的前一个状态$s_{t-1}$有关, 即$P(s_t|s_1, s_2, s_3, \dots,s_{t-1})=P(s_t|s_{t-1})$
这个假设后来被称为马尔可夫假设,而符合这个假设的随机过程则称为马尔可夫过程, 也称为马尔可夫链.
数学之美, 吴军
时间和状态取值都是离散的马尔可夫过程也称为马尔可夫链.
隐含的是状态
隐含马尔可夫模型由初始概率分布(向量$\pi$), 状态转移概率分布(矩阵$A$)以及观测概率分布(矩阵$B$)确定.
隐马尔可夫模型$\lambda$ 可以用三元符号表示, 即 $$ \lambda = (A, B, \pi) $$
其中$A,B,\pi$称为模型三要素.
具体实现的过程中, 如果观测的概率分布是定的, 那么$B$就是确定的了. 在hhmlearn2中, 实现了三种概率分布的HMM模型: MultinominalHMM, GaussianHMM, GMMHMM. 还可以定义不同的emission probabilities4, 生成不同的HMM模型.
-
齐次马尔科夫假设(状态) $$ P(i_t|i_{t-1},o_{t-1},\dots,i_1,o_1) = P(i_t|i_{t-1}), t=1,2,\dots,T $$ 注意书里这部分的描述
假设隐藏的马尔可夫链在任意时刻$t$的状态
$\rightarrow i_t$ 只依赖于其前一时刻的状态$\rightarrow i_{t-1}$
与其他时刻的状态
$\rightarrow i_{t-1, \dots, i_1}$ 及观测无关
$\rightarrow o_{t-1},\dots,o_1$ 也与时刻$t$无关
$\rightarrow t=1,2,\dots,T$ 如此烦绕的一句话, 用一个公式就表示了, 数学是如此美妙.
-
观测独立性假设(观测) $$ P(o_t|i_T,o_T,i_{T-1},o_{T-1},\dots,i_{t+1},o_{t+1},i_t,i_{t-1},o_{t-1},\dots,i_1,o_1)=P(o_t|i_t) $$ 书里这部分描述如下
假设任意时刻$t$的观测
$\rightarrow o_t$ 只依赖于该时刻的马尔可夫链的状态
$\rightarrow i_t$ 与其他观测
$\rightarrow o_T,o_{T-1},\dots,o_{t+1},o_{t-1},\dots,o_1$ 及状态无关
$\rightarrow i_T,i_{T-1},\dots,i_{t+1},i_{t-1},\dots,i_1$ 李老师这个书真的是无废话
-
概率计算问题 输入: 模型$\lambda=(A,B,\pi)$, 观测序列$O=(o_1,o_2,\dots,o_T)$ 输出:
$P(O|\lambda)$ -
学习问题 输入: 观测序列
$O=(o_1,o_2,\dots,o_T)$ 输出: 输出$\lambda=(A,B,\pi)$ -
预测问题, 也称为解码问题(Decoding) 输入: 模型$\lambda=(A,B,\pi)$, 观测序列$O=(o_1,o_2,\dots,o_T)$ 输出: 状态序列
$I=(i_1,i_2,\dots,i_T)$ 因为状态序列是隐藏的, 不可观测的, 所以叫解码.
There are three fundamental problems for HMMs:
- Given the model parameters and observed data, estimate the optimal sequence of hidden states.
- Given the model parameters and observed data, calculate the likelihood of the data.
- Given just the observed data, estimate the model parameters.
The first and the second problem can be solved by the dynamic programming algorithms known as the Viterbi algorithm and the Forward-Backward algorithm, respectively. The last one can be solved by an iterative Expectation-Maximization (EM) algorithm, known as the Baum-Welch algorithm.
---hhmlearn
输入：$\lambda=(A,B,\pi)$ ,观测序列长度$T$
输出：观测序列$O=(o_1,o_2,\dots,o_T)$
- 按照初始状态分布$\pi$产生$i_1$
$t=1$ - 按照状态$i_t$的观测概率分布$b_{i_t}(k)$生成$o_t$
- 按照状态$i_t$的状态转移概率分布${a_{i_t, {i_{t+1}}}}$产生状态$i_{t+1}$,$\color{red}i_{t+1}=1,2,\dots,N$
$t=t+1$ 如果$t<T$转到3,否则，终止
上面是书中的描述，和本章大参考文献5的描述是一样的， 但这里面有点容易混淆。
书中定义了$I=(i_1,i_2,\dots,i_T), Q={q_1,q_2,\dots,q_T}$根据定义，
Rabiner定义的$a_{ij}$是这样的 $$ A={a_{ij}},a_{ij}=Pr(q_j at t+1|q_i at t) $$ 这里理解就好， 有时候用角标$i$代表对应的state， 有时候用$q_i$代表对应的state。
给定马尔可夫模型$\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) $$ 给定马尔可夫模型$\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) $$
$\color{red} 关于\alpha 和\beta 这两个公式, 仔细看下, 细心理解.$ 前向概率从前往后递推， 后向概率从后向前递推。
输入:
$\lambda , O$ 输出:$P(O|\lambda)$
初值 $$ \alpha_1(i)=\pi_ib_i(o_1), i=1,2,\dots,N $$ 观测值$o_1$,
$i$ 的含义是对应状态$q_i$这里$\alpha$ 是$N$维向量, 和状态集合$Q$的大小$N$有关系.
$\alpha$ 是个联合概率.递推 $$ \color{red}\alpha_{t+1}(i) = \left[\sum\limits_{j=1}^N\alpha_t(j)a_{ji}\right]b_i(o_{t+1})\color{black}, \ i=1,2,\dots,N, \ t = 1,2,\dots,T-1 $$ 转移矩阵$A$维度$N\times N$, 观测矩阵$B$维度$N\times M$, 具体的观测值$o$可以表示成one-hot形式, 维度$M\times1$, 所以$\alpha$的维度是$\alpha = \alpha ABo=1\times N\times N\times N \times N\times M \times M\times N=1\times N$
终止 $$ P(O|\lambda)=\sum\limits_{i=1}^N\alpha_T(i)=\color{red}\sum\limits_{i=1}^N\alpha_T(i)\beta_T(i) $$ 注意, 这里$O\rightarrow (o_1, o_2, o_3,\dots, o_t)$,
$\alpha_i$ 见前面前向概率的定义$P(o_1,o_2,\dots,o_t,i_t=q_i|\lambda)$, 所以, 对$i$求和能把联合概率中的$I$消掉.这个书里面解释的部分有说.
书中有说前向算法的关键是其局部计算前向概率, 然后利用路径结构将前向概率"递推"到全局.
减少计算量的原因在于每一次计算直接引用前一时刻的计算结果, 避免重复计算.
前向算法计算$P(O|\lambda)$的复杂度是$O(N^2T)$阶的, 直接计算的复杂度是$O(TN^T)$阶, 所以$T=2$时候并没什么改善.
红色部分为后补充了$\beta_T(i)$项，这项为1,此处注意和后面的后向概率对比。
输入:
$\lambda , O$ 输出:$P(O|\lambda)$
终值 $$ \beta_T(i)=1, i=1,2,\dots,N $$ 在$t=T$时刻, 观测序列已经确定.
递推 $$ \color{red}\beta_t(i)=\sum\limits_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j)\color{black}, i=1,2,\dots,N, t=T-1, T-2,\dots,1 $$ 从后往前推
$\beta = ABo\beta = N \times N \times N \times M \times M \times N \times N \times 1 = N \times 1$
$$ P(O|\lambda)=\sum\limits_{i=1}^N\pi_ib_i(o_1)\beta_1(i)=\color{red}\sum\limits_{i=1}\alpha_1(i)\beta_1(i) $$
- 这里需要注意下, 按照后向算法,
$\beta$ 在递推过程中会越来越小, 如果层数较多, 怕是$P(O|\lambda)$会消失 - 另外一个要注意的点$\color{red}o_{t+1}\beta_{t+1}$
- 注意，红色部分为后补充，结合前面的前向概率最后的红色部分一起理解。
求解的都是观测序列概率 观测序列概率$P(O|\lambda)$统一写成 $$ P(O|\lambda)=\sum_{i=1}^N\sum_{j=1}^N\alpha_t(i)a_{ij}b_j(o_{t+1}\beta_{t+1}(j)),\ t=1,2,\dots,T-1 $$
$P(O|\lambda) = \alpha ABo\beta$
其实前向和后向不是为了求整个序列$O$的概率, 是为了求中间的某个点$t$, 前向后向主要是有这个关系: $$ \alpha_t(i)\beta_t(i)=P(i_t=q_i,O|\lambda) $$ 当$t=1$或者$t=T-1$的时候, 单独用后向和前向就可以求得$P(O|\lambda)$, 分别利用前向和后向算法均可以求解$P(O|\lambda)$, 结果一致.
利用上述关系可以得到下面一些概率和期望, 这些概率和期望的表达式在后面估计模型参数的时候有应用.
概率与期望
- 输入模型$\lambda$与观测$O$, 输出在时刻$t$处于状态$q_i$的概率$\gamma_t(i)$
- 输入模型$\lambda$与观测$O$, 输出在时刻$t$处于状态$q_i$且在时刻$t+1$处于状态$q_j$的概率$\xi_t(i,j)$
- 在观测$O$下状态$i$出现的期望值
- 在观测$O$下状态$i$转移的期望值
- 在观测$O$下状态$i$转移到状态$j$的期望值
效果好，费钱，如果有钱能拿到标注数据，不用犹豫，去干吧。
马尔可夫模型实际上是一个含有隐变量的概率模型
$$
P(O|\lambda)=\sum\limits_IP(O|I,\lambda)P(I|\lambda)
$$
关于EM算法可以参考第九章, 对隐变量求期望,
输入: 观测数据$O=(o_1, o_2, \dots, o_T)$
输出: 隐马尔可夫模型参数
初始化 对$n=0$, 选取$a_{ij}^{(0)}, b_j(k)^{(0)}, \pi_i^{(0)}$, 得到模型参数$\lambda^{(0)}=(A^{(0)}, B^{(0)},\pi^{(0)})$
递推 对$n=1,2,\dots,$ $$ a_{ij}^{(n+1)}=\frac{\sum\limits_{t=1}^{T-1}\xi_t(i,j)}{\sum\limits_{t=1}^{T-1}\gamma_t(i)} $$
$$ b_j(k)^{(n+1)}=\frac{\sum\limits_{t=1,o_t=v_k}^{T}\gamma_t(j)}{\sum\limits_{t=1}^T\gamma_t(j)} $$
$$ \pi_i^{(n+1)}=\gamma_1(i) $$
终止 得到模型参数$\lambda^{(n+1)}=(A^{(n+1)}, B^{(n+1)},\pi^{(n+1)})$
单独说一下这个问题, 公式里面求和有个$o_t=v_k$, 什么意思?
窃以为这里可以表示成$b_{jk}$, 书中对应部分的表达在$P_{172}的10.3$, 也说明了$b_j(k)$的具体定义.
注意这里$b_j(k)$并不要求是离散的，可以定义为一个连续的函数， 所以书中这样的表达更通用一些，关于这点在本章大参考文献5中有部分内容讨论，见Special cases of the B parameters。
这里涉及到实际实现的时候, 可以考虑把观测序列$O$转换成one-hot的形式,
补充一下，
克罗内克函数是一个二元函数， 自变量一般是两个整数， 如果两者相等， 输出是1, 否则为0.
其实和指示函数差不多， 只不过条件只限制在了相等。 $$ \sigma_{ij}= \begin{cases} 1 (i = j)\ 0 (i\ne j) \end{cases} \ b_j(k)=\frac{\sum\limits_{t=1,o_t=v_k}^{T}\gamma_t(j)}{\sum\limits_{t=1}^T\gamma_t(j)}=\frac{\sum\limits_{t=1}^{T}\sigma_{o_t,v_k}\gamma_t(j)}{\sum\limits_{t=1}^T\gamma_t(j)} $$
Baum-Welch算法是EM算法在隐马尔可夫模型学习中的具体实现, 由Baum和Welch提出.
看到书上这里都知道是EM算法, 具体实现$\color{red}哪里是E,哪里是M?$
书中在前向后向算法介绍之后, 单独有一个小节介绍了"一些概率与期望值的计算", 这部分内容在后面的Baum
-Welch算法中会用到, 代码实现的时候才理解, 这小节对应的是E步概率和期望, 后面算法里面的是M步的内容, 说明如何用这些概率和期望去更新HMM模型的参数.
重新梳理一下整个10.2节的内容，这部分内容描述**概率计算方法 **， 实际上在E步操作的时候都要用到，需要用到前向后向算法根据模型参数$A,B,\pi$来更新$\alpha$和$\beta$，然后利用这两个值来更新一些概率和期望，再通过模型参数的递推公式来更新模型参数。
这里可能还有点疑问，EM算法的描述里面，E步计算的是Q函数，但是前面的描述似乎并没有显示Q函数和这些工作之间的关系。另外，M步具体操作是参数更新的递推公式，怎么就是最大化了呢? 书中$P_{182}$的推导也许能解释这个问题。
看到这里, 感觉书上真的是一句废话都没有...
这部分的理解，要再结合第九章的内容反复一下，应该会有新的体会。
注意E步计算Q函数 $$ Q(\lambda,\bar{\lambda})=\sum_I\log P(O,I|\lambda)P(O,I|\bar\lambda) $$ 对比一下算法9.1，$P(O,I|\bar\lambda)=P(I|O,\bar\lambda)P(O|\bar\lambda)$，所以书中在这个地方有个注释，略去了对于$\lambda$而言的常数因子$1/P(O|\bar\lambda)$
每个时刻最有可能的状态$i_t^$是 $$ i_t^=\arg \max\limits_{1\leqslant i\leqslant N}\left[\gamma_t(i)\right], t=1,2,\dots,T $$ 得到序列$I^=(i_1^,i_2^,\dots,i_T^)$
这个算法, 在输出每个状态的时候, 只考虑了当前的状态.
输入: 模型$\lambda=(A, B, \pi)$和观测$O=(o_1, o_2,\dots,o_T)$
输出: 最优路径$I^=(i_1^, i_2^,\dots,i_T^)$
- 初始化
$\delta_1(i)=\pi_ib_i(o_1), i=1,2,\dots,N$ $\psi_1(i)=0, i=1,2,\dots,N$ - 递推
$t=2,3,\dots,T$ $\delta_t(i)=\max\limits_{1\leqslant j \leqslant N}\left[\delta_{t-1}(j)a_{ji}\right]b_i(o_t), i=1,2,\dots,N$ $\psi_t(j)=\arg\max\limits_{1\leqslant j \leqslant N}\left[\delta_{t-1}(j)a_{ji}\right], i=1,2,\dots,N$ - 终止 $P^=\max\limits_{1\leqslant i\leqslant N}\delta_T(i)$ $i_T^=\arg\max\limits_{1\leqslant i \leqslant N}\left[ \delta_T(i)\right]$
- 最优路径回溯
$t=T-1, T-2, \dots,1$ $i_t^=\psi_{t+1}(i_{i+1}^)$
书上配了个图, 这个图可视化了$\delta$
这个例子主要说明怎么从数据中拿到状态集合, 观测集合, 序列长度以及模型三要素.
分清楚哪些是已知, 哪些是推导得到.
书中描述也很清楚
这是一个隐马尔可夫模型的例子, 根据所给条件, 可以明确状态集合, 观测集合, 序列长度以及模型三要素.
恩, 例子干的就是这个事, 而这个小节叫做 隐马尔可夫模型的定义.
这个例子就是递推的~~~矩阵乘法~~~
因为是递推的, 所以没办法用矩阵乘法实现.
这里针对这个例子说下自己的看法, 这个例子稍微有点特殊$T$和$N$都是3, 这种情况对展开分析算法不是很合适, 如果$T=4$有些问题可能会更容易分析.
求最优状态序列
这个例子相对简单了, 在验证的过程中, 要核对$\delta$的结果.
上面两个例子真的比较特殊,状态转移矩阵还是对称矩阵.
状态转移矩阵$A$肯定是个方阵，但是这个例子里面状态数和序列长度一样， 稍微有点不方便。
前面在处理例10.2的时候, 还觉得这个例子不合适. 翻看后面习题的过程中发现, 有些点是在习题中有所展开.
模型参数和例子10.2是一样的, 只是改变了观测序列长度.
状态转移矩阵非对称, 观测序列长度更长, 求解的过程需要使用前向后向一起求解.
针对这个问题$i_4=q_3$给定了条件$t=4, i=3$, 那么公式10.22有下面的形式 $$ P(O|\lambda)=\sum\limits_{j=1}^N\alpha_4(3)a_{3j}b_j(o_5)\beta_5(j) $$ 这个习题应该是要思考观测序列概率的形式吧, 应该是一个维度是$N\times N \times T$的一个三维矩阵.
求例子10.1 的隐状态序列
这个在自己推导的过程中, 不自觉的注意到了.
推荐按照书中的例子, 推导$\alpha, \beta, \delta
一个用到了求和, 另外一个用到了求最大值.
采样应用
隐马尔可夫模型的一个强大的性质是他对与时间轴上的局部的变形具有某种程度的不变性.
有几个问题要弄清:
- 怎么评价分词效果的好坏?
- 模型参数训练的过程, 迭代应该在什么时候停止?