HMM笔记

最近发现健忘比较严重,现象就是上课老师讲的全都能听懂,下课回顾一下立刻全都忘光了。所以现在开始每次下课把笔记整理好传上来防止以后彻底忘掉!

我打算在这篇博文中用自己的理解浅谈一下HMM。为了大家能够轻松地看,我也尽量轻松地写。所以文中肯定会出现不少纰漏,请大家海涵,也求大家指教。

本文参考文献为中科院计算所宗成庆老师NLP的课件,其中有不少图均除此其中
(宗老师的课件做的特别好,推荐大家上网找一找!)

所谓HMM即Hidden Markov Model,隐马尔可夫模型。相信大家在很多领域都听到过这个模型,因为它的功能实在太强大了,按照导师的话说:

只要跟时间序列扯上点儿关系的东西,很多都能试试用隐马尔可夫模型。

按照自动化所的师兄说:

其实不一定是时间序列,我觉得只要排列有顺序,按此顺序的组合有一定的统计模式 就可以用马尔科夫模型

可见HMM的作用有多大!闲话少叙,下面进入正题。

马尔可夫模型与一阶马尔可夫链

  • 现在有个系统,其包含了N个状态:\(S_1, S_2, ..., S_N\)
  • 随着时间的推移,系统会从一个状态转向另一个状态。
  • 系统在时间\(t\)时的状态记为\(q_t\)
  • 系统在\(t\)时刻处于状态\(S_j~~~(1\lt j\lt N)\)的概率是:

$$ P(q_t=S_j|q_{t-1}=S_i, q_{t-2}=S_k, ...) $$

上面这些话就是在讲:首先有个系统,它当前的状态与之前的各种状态序列有关,而这个状态序列出现的概率值就是指“当系统经过一系列状态后到达状态\(S_j\)”这件事发生的概率。

举个例子来说,假设现在的系统是天气预报系统。“昨天、今天、明天”等是时间序列,“下雨、阴天、晴天”等是状态。对于这个随机过程来说,“明天是个大晴天”的概率是跟之前的天气状态相关的。可以看出“之前的天气状态”是一个模糊的无穷的概念,也就是说明天是个大晴天这件事是受到昨天、前天、甚至是一万年前的某一天的影响的!(冥冥之中有一种宿命论的节奏)。

如果说我们要用上面这个模型来研究天气,明天天气跟今天还算相关(今天多云明天就可能下雨),跟昨天也算有点儿关系(有可能连续两三天多云就很有可能下雨),但是如果说“今天天气跟一百万年前的一天有着密切关系”,你一定觉得我在开玩笑。没错!如果按照上面这个系统,一百万年前的一天的天气跟现在“肯定”是有关系的,但是这个关系微乎其微,对于一个数学理论在工程上的应用,我们可以做一些忽略和近似,使得数学理论能够产生应用价值,这时候就该提到“马尔可夫”了。

既然上面的模型在应用领域有着一些难以企及的高度,我们不妨对上面这个模型做一些“限制”:

  • 系统在t时间的状态只与t-1时刻的状态有关,即:(马尔可夫假设) $$P(q_t=S_j|q_{t-1}=S_i,q_{t-2}=S_k) = P(q_t=S_j|q_{t-1}=S_i)$$
  • 考虑上述随机过程,是独立于时间t的,即:(不动性假设) $$P(q_t=S_j|q_{t-1}=S_i)=a_{ij}$$

对于满足上面限制1的系统称为“离散的一阶马尔科夫链”,对于满足上面两条限制的随机过程称为马尔可夫模型(Markov Model)。

上面这两条限制究竟做了些什么?首先第一条明确了“当前状态的选择只与前一个时间的状态有关”,也就是说“明天的天气只与今天有关”。这一句话就把上面无穷无尽的随机过程简化成了一个非常简单的模型。而这句话明确了“一阶马尔可夫链”的定义。有一阶就说明有二阶三阶等等。没错所谓一阶就是当前状态只与前一个状态有关,二阶就是与前面两个状态有关!(其实说到这里很多了解过NLP的人就明白了,这不就是Language Model嘛!)

但是只有上面这一条还不足以称为马尔可夫模型,还需要有第二条:状态的选择与时间无关。说白了就是“今天阴天从而明天下雨”的概率等于2015年1月1日阴天从而1月2日下雨的概率,也等于公元前123年2月29日阴天从而2月30日下雨的概率。概率值都是\(a_{阴天,下雨}\),与这两个状态的发生时间无关。

除此之外,作为马尔科夫模型的“\(a_{ij}\)”还应该满足一些条件:

$$a_{ij}\geq 0$$ $$\sum_{j=1}^Na_{ij}=1$$

看到上面这个公式大家其实就明白了,原来这个\(a\)就是个概率啊!没错,这个\(a_{ij}\)叫做“状态转移概率”,为什么叫这个名字我们下面就会提到。

如果这时给定一个状态序列\(S_1,...,S_T\),我们是可以求得这个序列在系统的所有序列中出现的可能,也就是概率:\(P(S_i,...S_T) \)。

根据条件概率的链式法则,我们可以展开这个概率值的计算表达式:

$$P(S_i,\dots ,S_T) = P(S_1)\times P(S_2|S_1)\times P(S_3|S_1,S_2)\times \dots \times P(S_T|S_1,S_2,...,S_{T-1})$$

上面这个公式可以用来“无损”地求得状态序列的概率,但是想求出它的每一个因式项仍然是非常困难的。回想一下上面介绍到马尔科夫模型时所提到的方法:即每一个状态只与其前一个状态相关,这样这个公式就能进一步“有损”地化简成这样:

$$P(S_i,\dots ,S_T) = P(S_1)\times P(S_2|S_1)\times P(S_3|S_2)\times \dots \times P(S_T|S_{T-1})$$

这样公式是不是就简单多了!还记得上面提到过的那个状态转移概率吗?就是\(P(q_t=S_j|q_{t-1}=S_i)=a_{ij}\)。显然我们可以用它替换掉这个公式中的很多部分。而除此之外,我们还设\(P(q_1=S_i) = \pi_i\),则上面的公式最终能够化简成为:

$$P(S_i,\dots ,S_T) = \pi_{S_1}\times \prod_{t=1}^{T-1}a_{S_tS_{t+1}}$$

我们管\(\pi_i\)叫做“初始概率”,也就是说当第一个状态等于\(i\)时的概率。

马尔可夫链也可以表示成一个状态图(转移弧上有概率的非确定的有限状态自动机),比如下面这张图

上面这张状态图就描述了一个有限状态自动机,同时也是一个马尔可夫模型。“start”表明了起始状态只能是状态“t”,也就是说\(\pi_i=1~~(iff. i=t)\)。而当\(i\)等于其他时\(\pi_i=0\)。(脑补一下其实\(\pi\)就是一个向量,这个脑补对以后的算法实现有帮助)

既然有了马尔科夫模型了,那我们可以做个小练习来感受一下:

  • 假设现在有序列1(t, i, p),这个序列产生的概率:

$$ P(t,i,p)=P(S_1=t)\times P(S_2=i|S_1=t)\times P(S_3=p|S_2=i)\\
=\pi_t\times a_{t,i}\times a_{i,p}=1.0\times 0.3\times 0.6 = 0.18 $$

  • 又假设有序列2(t, h, e),这个序列产生的概率:

$$ P(t,h,e)=P(S_1=t)\times P(S_2=h|S_1=t)\times P(S_3=e|S_2=h)\\
=\pi_t\times a_{t,h}\times a_{h,e}=1.0\times 0.4\times 1.0 = 0.4 $$

序列1和序列2有着不同的产生概率,序列2“出现”的概率要大于序列1。举个不恰当的例子。加入状态t是阴天,状态h是小雨,状态e是中雨,状态i是晴天,状态p是大雨。对应到序列1就是连续三天(阴天,晴天,大雨),而序列2就是连续三天(阴天,小雨,中雨)。显然序列2出现的可能性更要大一些吧!

说了这么多,都是马尔可夫模型。那么“隐”马尔可夫模型究竟是啥呢?

隐马尔可夫模型

在上面的讲述中,我们发现:如果知道了状态和他们之间的转移概率,我们就得到了一个马尔可夫模型。用这个模型我们可以干很多事:例如根据前几天的天气状态,预测一下明天的天气状态。

但是有些时候,我们并不是那么容易就能知道“状态”发生的序列。这就好比不抬头看天就去预报天气。但是他能够从一些“侧面”的角度来揣测状态序列。这些侧面的角度我们将其称为“观察”。

所谓“观察”,其实就是在未知(但存在)的状态下,我们观测到的数据。例如虽然不能抬头看天,因而不知道天上有没有乌云、会不会下雨,但是我们发现“燕子低飞”。显然“燕子低飞”这个观察,跟“下雨”这个状态之间是有一定联系的。

这个时候,状态是隐藏的,称为隐变量。但是状态到观察之间是存在着关系的。例如当所有的观察包括{燕子低飞,地面湿润,地表龟裂},而状态集合依然是{晴天,阴天,下雨}。这个时候我们只能通过观察序列,来推测状态序列。而状态与观察的关系是用概率的形式定义的。例如当状态时“阴天”时,“燕子低飞”的概率显然要大于“地表龟裂”。

再比如说,我们用经典的“袋子与球”作为例子:

我们有三种颜色的球:红、绿、蓝。同时还有好几种混有不同数量的袋子:袋子1={红,红,红,绿},袋子2={红,绿,绿,蓝},袋子3={绿,绿,蓝,蓝},袋子4={绿,蓝,蓝,蓝} ... 等等。

现在的游戏规则是从袋子中摸球。而在每个袋子摸完之后,记录下球的颜色并且把球放回去。然后按照不同的概率跳转到另一个袋子或者依然在这个袋子中去摸下一个球。这时候我们能够摸出来一个不同颜色球的序列。

那么问题来了,如果我们只能看到摸出来球的序列,但是并不知道他们分别是从哪个袋子中摸出来的。对于每个袋子,我们知道其能摸出求的颜色的概率:(即混淆矩阵B中的元素)

$$B_{袋子1}(红)=\frac{3}{4},~~B_{袋子1}(绿)=\frac{1}{4},~~B_{袋子1}(蓝)=\frac{0}{4}$$

也知道从第\(i\)个袋子摸完球后,下一个球从第\(j\)个袋子中的概率\(a_{ij}\)(即状态转移矩阵中的一个元素)。

这时候,我们就可以使用隐马尔可夫模型对这个随机过程进行建模,并且分析其内在的几个问题:

  • 在给定了模型\(\mu =(A,B,\pi)\)和观察序列\(O=O_1,O_2,\dots ,O_T\)的情况下,怎样快速计算概率\(P(O|\mu)\)?(已知模型参数、计算某一给定可观察序列的概率)
  • 在给定了模型\(\mu =(A,B,\pi)\)和观察序列\(O=O_1,O_2,\dots ,O_T\)的情况下,如何选在在一定意义下“最优”的状态序列\(Q=q_1q_2\dots q_T\),使得该序列“最好地解释”观察序列?(根据可观察状态的序列、找到一个最可能的隐藏状态序列)
  • 给定一个观察序列\(O=O_1,O_2,\dots ,O_T\),如何根据最大似然估计来求模型的参数值?即如何调节模型的\(\mu =(A,B,\pi)\),使得\(P(O|\mu)\)最大?(根据观察到的序列,来确定一个最有可能使得该序列出现的HMM)

这三个问题就是隐马尔可夫模型经典的三个问题。第一个是在进行“评估”(Evaluation)。例如我们有几个不同的HMM和观察序列,想要知道哪一个HMM最可能产生这个观察序列。第二个问题是“解码”(Decoding)。就是说给定观察序列,找到一个最有可能的隐藏的状态序列。语音识别就可以用它来进行:语音的特征输入就是观察序列,语音所代表的词汇序列就是隐藏状态序列。用语音特征去“解码”状态序列,就是语音识别的过程。第三个问题是学习(Learning),就是在给定大量的已有数据,来推算出一个HMM,使其能够最佳匹配(极大似然的思想)这些数据。

对于第一个问题,使用前向算法(Forward algorithm)解决;对于第二个问题,使用Viterbi算法(Viterbi algorithm)解决;对于第三个问题使用前向后向算法(forward-backward algorithm)解决

接下来我就针对上面的每个问题进行详细的阐述。并且尽可能地去剖析其中的算法。

评估(Evaluation)

所谓评估,就是要进行这样一件事:给定模型\(\mu =(A,B,\pi)\)和观察序列\(O=O_1,O_2,\dots ,O_T\)的情况下,计算\(P(O|\mu)\)。但是问题来了:一个观察序列可能由多个状态序列而来,那这个观察序列的概率定义究竟是啥呢?没错,就是“在每个可能的状态序列下求得的概率”之和:

对于给定的状态序列\(Q=q_1q_2\dots q_T\): $$ P(O|\mu)=\sum_QP(O,Q|\mu)=\sum_QP(Q|\mu)P(O|Q,\mu)
$$

其中 $$ P(Q|\mu)=\pi_{q_1}a_{q_1q_2}a_{q_2q_3}\dots a_{q_{T-1}q_T}\\
P(O|Q,\mu)=b_{q_1}(O_1)\cdot b_{q_2}(O_2)\dots b_{q_T}(O_T)
$$

这里的求和符号的范围是Q,这该怎么算?没错,穷举!

对于上面抓球的例子来说,假设只有四个袋子(状态集合),三种不同颜色的球(观察集合)。现在我们观察到了这样的序列:{红,红,绿}。那么这个观察序列的概率: $$ P(红,红,绿|\mu)=P(红,红,绿|袋_1,袋_1,袋_1,)\\
+P(红,红,绿|袋_1,袋_1,袋_2,)\\ +P(红,红,绿|袋_1,袋_1,袋_3,)\\ +P(红,红,绿|袋_1,袋_2,袋_1,)\\ +P(红,红,绿|袋_1,袋_2,袋_2,)\\ +\dots \dots $$

公式太长写不完,画个图来表达:

还记得我们曾经用图来表示马尔可夫模型嘛?这个图只不过多加了一个观察序列,原理依然是类似的。有了这幅图,大家会发现,我们想要求观察序列的概率值,无非就是把上面从左到右(时间递增)的路径全都穷举一遍。每一条路径都能得到“在三个状态组成的路径下,产生观察值的概率”。然后把这些值叠加起来,就是\(P(O|\mu)=\sum_QP(O,Q|\mu)\)的真谛。

但显然,这样算的代价显然太大了。所以我们现在要考虑一些方法来优化它。我们再重新考量一下上图的每个过程:

首先考虑一下中间状态的情况。我们可以把中间状态作为所有到达这个状态的全部路径求和。例如在\(t=2\)时,袋子是2号的概率一定是由其左边的路径所确定的。

我们将这个概率(在t时刻处于状态\(i\)局部概率)定义为\(\alpha_t(i)\)

看到这里肯定有人会发现,这种结构可以使用动态规划的方法去解决!没错,前向算法就是一种最简单的动态规划的算法结构。我们重新梳理一下动态规划的依赖情况。

现在用的这个blog系统的的草稿预览不支持MathJax公式,所以我不得不先发表后编辑了。所以看到这句话说明这篇文章还没写完。。。并且我的拖延症又犯了。。

Friskit

继续阅读此作者的更多文章