一些基本概念
在正式讲解隐马尔可夫模型(Hidden Markov Model,HMM)之前,有几个概念需要搞清楚。
概率模型(Probabilistic Model)
所谓概率模型,顾名思义,就是将学习任务归结于计算变量的概率分布的模型。
概率模型非常重要。在生活中,我们经常会根据一些已经观察到的现象来推测和估计未知的东西——这种需求,恰恰是概率模型的推断(Inference)行为所做的事情。
推断(Inference)的本质是:利用可观测变量,来推测未知变量的条件分布。
我们下面要讲的隐马尔可夫模型(HMM)和条件随机场(CRF)都是概率模型,之前讲过的朴素贝叶斯和逻辑回归也是概率模型。
生成模型 VS 判别模型
概率模型又可以分为两类:生成模型(Generative Model)和判别模型(Discriminative Model)。
既然概率模型是通过可观测变量推断部分未知变量,那么我们将可观测变量的集合命名为 $O$,我们感兴趣的未知变量的集合命名为 $Y$。
生成模型学习出来的是 $O$ 与 $Y$ 的联合概率分布 $P(O,Y)$,而判别模型学习的是条件概率分布:$P(Y|O)$。
朴素贝叶斯模型是生成模型,而逻辑回归则是判别模型。
对于某一个给定的观察值 $O$,运用条件概率 $P(Y|O)$ 很容易求出它对于不同 $Y$ 的取值。
那么当遇到分类问题时,直接就可以运用判别模型——给定 $O$ 对于哪一个 $Y$ 值的条件概率最大——来判断该观测样本应该属于的类别。
生成模型直接用来给观测样本分类有点困难。当然也不是不可行,通过运用贝叶斯法则,可以将生成模型转化为判别模型,但是这样显然比较麻烦。
在分类问题上,判别模型一般更具优势。不过生成模型自有其专门的用途,下面我们要讲的 HMM,就是一种生成模型。
概率图模型(Probabilistic Graphical Model)
我们还需要明确一个很重要的概念:概率图模型。
概率图模型:是一种以图(Graph)为表示工具,来表达变量间相关关系的概率模型。
这里说得图就是“数据结构”课中讲过的图概念:一种由节点和连接节点的边组成的数据结构。
在概率图模型中,一般用节点来表示一个或者一组随机变量,而节点之间的边则表示两个(组)变量之间的概率相关关系。
边可以是有向(有方向)的,也可以是无向的。概率图模型大致可以分为:
- 有向图模型(贝叶斯网络):用有向无环图表示变量间的依赖关系;
- 无向图模型(马尔可夫网):用无向图表示变量间的相关关系。
HMM 就是贝叶斯网络的一种——虽然它的名字里有和“马尔可夫网”一样的“马尔可夫”。
对变量序列建模的贝叶斯网络又叫做动态贝叶斯网络。HMM 就是最简单的动态贝叶斯网络。
马尔可夫链,马尔可夫随机场和条件随机场
马尔可夫链(Markov Chain):一个随机过程模型,它表述了一系列可能的事件,在这个系列当中每一个事件的概率仅依赖于前一个事件。
上图就是一个非常简单的马尔可夫链。两个节点分别表示晴天和雨天,几条边表示节点之间的转移概率。
一个晴天之后,0.9的可能是又一个晴天,只有0.1的可能是一个雨天。而一个雨天之后,0.5的可能是晴天,也有0.5的可能是另外一个雨天。
假设这是某个地区的天气预报模型(这个地区只有晴天和雨天两种天气),则明天天气的概率,只和今天的天气状况有关,和前天以及更早没有关系。那么我们只要知道今天的天气,就可以推测明天是晴是雨的可能性了。
通俗的例子
有一个人每天中午12点会呈现出三个状态:吃
,玩
,睡
中的一个,这就是状态分布。
想要预测他n天后中午12点的状态是什么?
是在吃,还是在玩,还是在睡?
这些状态发生的概率分别都是多少?
先看个假设,他每个状态的转移都是有概率的,比如今天玩,明天是睡的概率,今天玩,明天也是玩的概率。
这个矩阵就是转移概率矩阵P,并且它是保持不变的,就是说第一天到第二天的转移概率矩阵跟第二天到第三天的转移概率矩阵是一样的。这个也就是时齐。
有了这个矩阵,再加上已知的第一天的状态分布,就可以计算出第N天的状态分布了。
S1 是4月1号中午12点的的状态分布矩阵 [0.6, 0.2, 0.2],里面的数字分别代表吃的概率,玩的概率,睡的概率。那么4月2号的状态分布矩阵 S2 = S1 * P (俩矩阵相乘)。
4月3号的状态分布矩阵 S3 = S2 * P (看见没,跟S1无关,只跟S2有关)。
4月4号的状态分布矩阵 S4 = S3 * P (看见没,跟S1,S2无关,只跟S3有关)。
...
4月n号的状态分布矩阵 Sn = Sn-1 * P (看见没,只跟它前面一个状态Sn-1有关)。
总结:马尔可夫链就是这样一个任性的过程,它将来的状态分布只取决于现在,跟过去无关!就把下面这幅图想象成是一个马尔可夫链吧。实际上就是一个随机变量随时间按照Markov性质进行变化的过程。
2号吃的概率 $P_吃$ = 0.6*0.2+0.2*0.1+0.2*0.4 = 0.22
2号玩的概率 $P_玩$ = 0.6*0.3+0.2*0.6+0.2*0.5 = 0.4
2号玩的概率 $P_睡$ = 0.6*0.5+0.2*0.3+0.2*0.1 = 0.38
$S_2$ = [0.22,0.4,0.38]
隐马尔可夫模型(Hidden Markov Model,HMM)
HMM 定义
HMM 是一个关于时序的概率模型,它的变量分为两组:
- 状态变量 ${s_1, s_2, …, s_T}$, 其中 $s_t \in \mathcal{S}$ 表示 $t$ 时刻的系统状态;
- 观测变量 ${o_1, o_2, …, o_T}$, 其中 $o_t \in \mathcal{O}$ 表示 $t$ 时刻的观测值。
状态变量和观测变量各自都是一个时间序列,每个状态/观测值都和一个时刻相对应(见下图,图中箭头表示依赖关系):
一般假定状态序列是隐藏的、不能被观测到的,因此状态变量是隐变量(Hidden Variable)——这就是 HMM 中 H(Hidden)的来源。
这个隐藏的、不可观测的状态序列是由一个马尔可夫链随机生成的——这是 HMM 中的第一个 M(Markov)的含义。
一条隐藏的马尔可夫链随机生成了一个不可观测的状态序列(State Sequence),然后每个状态又对应生成了一个观测结果,这些观测值按照时序排列后就成了观测序列(Observation Sequence)。这两个序列是一一对应的,每个对应的位置又对应着一个时刻。
一般而言,HMM 的状态变量取值是离散的,而观测变量的取值,则可以是离散的,也可以是连续的。
不过为了方便讨论,也因为在大多数应用中观测变量也是离散的,因此,我们下面仅讨论状态变量和观测变量都是离散的情况。
HMM 基本假设
HMM 的定义建立在两个假设之上:
假设1: 假设隐藏的马尔可夫链在任意时刻 $t$ 的状态只依赖于前一个时刻($t-1$ 时)的状态,与其他时刻的状态及观测无关,也与时刻 $t$ 无关。
用公式表达就是:
$P(s_t|s_{t-1}, o_{t-1}, …, s_1, o_1) = P(s_t|s_{t-1}), \ \ t = 1,2,…, T$
这一假设又叫做齐次马尔可夫假设。
假设2:假设任意时刻的观测只依赖于该时刻的马尔可夫链状态,与其他观测及状态无关。
用公式表达为:
$P(o_t|s_T, o_T, s_{T-1}, o_{T-1}, …, s_{t+1}, o_{t+1}, s_t, o_t, …, s_1, o_1) = P(o_t|s_t)$
这叫观测独立性假设。
确定 HMM 的两个空间和三组参数
基于上述两个假设,我们可知:所有变量(包括状态变量和观测变量)的联合分布为:
$P(s_1,o_1, …, s_T, o_T) = P(s_1)P(o_1|s_1)\prod_{t=2}^{T}P(s_t|s_{t-1})P(o_t|s_t)$.
设 HMM 的状态变量(离散型),总共有 $N$ 种取值,分别为:${S_1, S_2, …, S_N}$。
观测变量(也是离散型),总共有 M 种取值,分别为:${O_1, O_2, …, O_M}$。
那么,要确定一个 HMM,除了要指定其对应的状态空间 $\mathcal{S}$ 和观测空间 $\mathcal{O}$ 之外,还需要三组参数,分别是:
-
状态转移概率:模型在各个状态间转换的概率,通常记作矩阵 $A = \begin{bmatrix} a_{ij} \end{bmatrix}_{N\times N}$。
其中,$a_{ij} = P(s_{t+1} = S_j | s_t = S_i), 1 \leqslant i, j \leqslant N $ 表示在任意时刻 $t$,若状态为 $ S_i $,则下一时刻状态为 $S_j$ 的概率。
-
输出观测概率:模型根据当前状态获得各个观测值的概率,通常记作矩阵 $B = \begin{bmatrix} b_{ij} \end{bmatrix}_{N\times M}$。
其中,$b_{ij} = P(o_t = O_j | s_t = S_i), 1 \leqslant i \leqslant N, 1 \leqslant j \leqslant M $ 表示在任意时刻 $t$,若状态为 $S_i$,则观测值 $O_j$ 被获取的概率。
有些时候,$S_i$ 已知,但可能 $O_j$ 是未知的,这个时候,$b$ 就成了当时观测值的一个函数,因此也可以写作 $b_i(o) = P(o| s= S_i)$。
-
初始状态概率:模型在初始时刻各状态出现的概率,通常记作 $\pi = (\pi_1, \pi_2, ..., \pi_N)$,其中 $\pi_i = P(s_1 = S_i), 1 \leqslant i \leqslant N$ 表示模型的初始状态为 $S_i$ 的概率。
通常我们用 $\lambda = [A, B, \pi]$ 来指代这三组参数。
有了状态空间 $\mathcal{S}$ 和观测空间 $\mathcal{O}$,以及参数 $\lambda$,一个 HMM 就被确定了。
三个基本问题
其他模型都是直接把特征对应成一个结果,当然,这个结果的取值本身可以是连续的(回归模型)或者离散的(分类模型),不过整个过程里涉及到的也就是输入变量(特征)和预测结果两部分数据。
HMM 却是变量自己就分成两类:状态变量和观测变量,而且,模型的运行过程也是来来回回在这两类变量之间转圈圈,这到底有什么用呢?
三个基本问题
在实际运用中,HMM 有三个基本问题。
概率计算问题
问题名称:概率计算问题,又称评价(Evaluation)问题。
已知信息:
- 模型 $\lambda = [A, B, \pi]$
- 观测序列 $O=(o_1, o_2, …, o_T)$
求解目标:计算在给定模型 $\lambda$ 下,已知观测序列 $O$ 出现的概率:$P(O|\lambda)$。也就是说,给定观测序列,求它和评估模型之间的匹配度。
预测问题
问题名称:预测问题,又称解码(Decoding)问题。
已知信息:
- 模型 $\lambda = [A, B, \pi]$
- 观测序列 $O=(o_1, o_2, …, o_T)$
求解目标:计算在给定模型 $\lambda$ 下,使已知观测序列 $O$ 的条件概率 $P(O|S)$ 最大的状态序列 $S=(s_1, s_2, …, s_T)$。即给定观测序列,求最有可能与之对应的状态序列。
学习问题
问题名称:学习(Learning)问题又称训练(Training)问题。
已知信息:
- 观测序列 $O=(o_1, o_2, …, o_T)$
- 或许也会给定与之对应的状态序列: $S=(s_1, s_2, …, s_T)$
求解目标:估计模型 $\lambda = [A, B, \pi]$ 参数,使得该模型下观测序列概率 $P(O|\lambda)$ 最大。也就是训练模型,使其最好地描述观测数据。
前两个问题是模型已经存在之后如何使用模型的问题,而最后一个则是如何通过训练得到模型的问题。
举个栗子
死囚想请求赦免,皇帝给了一个条件,如果死囚能做到就会被赦免
皇帝摆出金银铜三个水果盒。
- 金水果盒里有
两个苹果
、一个蓝莓
,一个葡萄
和一个橙子
; - 银水果盒里有
苹果
、蓝莓
、葡萄
和橙子
各一个; - 铜水果盒里有
苹果
、葡萄
和橙子
各一个。
规则是这样:
- 把三个水果盒放在一个轮盘上,随机转动轮盘。
- 停下时,哪个盒子在皇帝眼前,皇帝就从这个水果盒里随机拿出一个水果,记录水果的种类后,把水果放回原盒中。
皇帝将重复上述动作3次,如果3次拿出来的正好依次是苹果,葡萄和橙子,死囚就被赦免。
那么请问:死囚被赦免的可能性到底有多大呢?
问题分析
按照操作,最终我们希望看到的是一个水果的观测序列,是:$O$ = (苹果,葡萄,橙子)。
其实,在整个事个中,除了最终的水果序列之外,还有另一个序列:水果盒的序列。
首先皇帝选了一系列的盒子,然后再从每个盒子里选了一个水果。
如此一来,水果盒正好对应状态,而水果则对应观测。水果盒序列就是状态序列,水果序列则是观测序列。
状态序列的不同状态之间是依据时序一对一跳转的,而某一个时刻的观测值也仅与当时的状态值有关。
这种情况下,我们完全可以应用 HMM 来估计 $O$ 出现的概率。
要确定一个 HMM,我们需要两个空间和 $\lambda$:
状态空间,也就是状态值的集合是:{金盒子,银盒子,铜盒子}。
观测空间,也就是观测值的集合是:{苹果,葡萄,橙子,蓝莓}。
$\lambda = (A, B, \pi)$
我们来看看 $A,B,和 \pi$ 分别是什么。
A 是状态转移矩阵,A 中元素用来反应不同状态之间的跳转概率。
我们现在设定的场景是“轮盘赌”,也就是说一个轮盘随机旋转。
如果每一次停留的位置都是随机的,那么任意一个状态到下面任意一个状态的概率都应该是0.33。
但是为了我们的例子更加清晰,我们假设:这个轮盘是不均衡的。
当前盒子为金时,下一次转到银盒子的概率是0.5,铜盒子为0.4,还是金盒子为0.1;当前为银盒子,则下一轮转到金盒子或者铜盒子的概率都是0.4,还是银盒子的概率为0.2;当前为铜盒子,下一个盒子为金银铜的概率分别为0.5,0.3,0.2。
那么我们用一个表格来反应概率跳转(每一行表示一个当前状态,每一列表示一个下一时刻的状态):
金 | 银 | 铜 | |
---|---|---|---|
金 | 0.1 | 0.5 | 0.4 |
银 | 0.4 | 0.2 | 0.4 |
铜 | 0.5 | 0.3 | 0.2 |
我们把金银铜改成数字,分别代表行号和列号:
1 | 2 | 3 | |
---|---|---|---|
1 | 0.1 | 0.5 | 0.4 |
2 | 0.4 | 0.2 | 0.4 |
3 | 0.5 | 0.3 | 0.2 |
这分明就是一个矩阵嘛,写出来就是:
$ \begin{bmatrix} 0.1 & 0.5 & 0.4 \\ 0.4 & 0.2 & 0.4 \\0.5 & 0.3 & 0.2 \\ \end{bmatrix}$
这就是状态转移矩阵:
$ A = \begin{bmatrix}0.1 & 0.5 & 0.4 \\ 0.4 & 0.2 & 0.4 \\ 0.5 & 0.3 & 0.2 \\ \end{bmatrix}$
再看各个盒子里面拿不同材质水果出来的概率:
苹果 | 葡萄 | 橙子 | 蓝莓 | |
---|---|---|---|---|
金 | 0.4 | 0.2 | 0.2 | 0.2 |
银 | 0.25 | 0.25 | 0.25 | 0.25 |
铜 | 0.33 | 0.33 | 0.33 | 0 |
这个表格对应观测矩阵:
$ B = \begin{bmatrix}0.4 & 0.2& 0.2& 0.2\\ 0.25& 0.25& 0.25& 0.25\\ 0.33& 0.33& 0.33& 0\\ \end{bmatrix}$
初始概率分布铜盒子略高,其他两个概率相等:$\pi=(0.3, 0.3, 0.4)^T$。
求解三个基本问题的现实意义
在开始时就有了两个空间和一个 $\lambda =(A,B,\pi)$, 我们就定义了一个 HMM。
那么运用这个 HMM 解决概率计算问题,就可以求出连续拿出三个水果依次是苹果、葡萄和橙子的可能性有多大。
反过来,通过解决预测问题,还可以得到最终观测序列为(苹果,葡萄,橙子)情况下,最有可能出现的状态序列(盒子序列)是什么。
如果假设在开始的时候,我们根本不知道 $\lambda$ 的取值,则可以通过不断地转动轮盘选盒子,拿水果,生成一个个状态序列和观测序列。然后用它们作为训练数据,来解决学习问题,从而得出 $\lambda$。
那么解决这些问题到底有什么意义啊?
学习问题还好说,毕竟可以求 $\lambda$,但是像解决概率计算问题和预测问题,反正都已经知道观测序列了,还去计算它出现的概率干什么呀?
单用这个例子来说,我们可以把上面的情形变得复杂一点——皇帝现在提出了两种方案:
【方案-1】如果转三次轮盘,拿出来的水果依次是苹果,葡萄和橙子,皇帝就赦免死囚;
【方案-2】如果转四次,连续4次都拿出苹果,则赦免死囚。
皇帝让死囚在两个方案之间选择,那么应如何选呢?
这时候就需要分别计算两个序列 $O_1$ = (苹果,葡萄,橙子), $O_2$ = (苹果,苹果,苹果,苹果)的出现概率,然后比大小,选择大的那个所对应的方案。
这三个基本问题到底怎么求解呢?
概率计算问题
继续上一篇的例子。现在模型已经给定,观测序列也已经知道了,我们要计算的是 $O$ = (苹果,葡萄,橙子) 的出现概率,我们要求的是 $P(O|\lambda)$。
直接计算
用直接计算法来求 $\lambda$ 情况下长度为 $T$ 的观测序列 $O$ 的概率:
$P(O|\lambda) = \sum_{S \in S_T} P(O,S|\lambda)$
意思是不同盒子序列状态下,出现$O$ = (苹果,葡萄,橙子)的概率总和。
其中 $S_T$ 表示所有长度为 $T$ 的状态序列的集合,$S$ 为其中一个状态序列。
比如:$S$状态序列有,金金金,金金铜,金金银,金银金,金银银,金银铜,金铜金...33种不同状态序列。
对所有长度为 $T$ 的状态序列 $S_t$ 和观测序列 $O$ 求以 $\lambda$ 为条件的联合概率,然后对所有可能的状态序列求和,就得到了 $P(O|\lambda)$ 的值。
因为 $P(O,S|\lambda) = P(O|S,\lambda)P(S|\lambda)$;
意思是,在“金,银,金”的状态序列下 给定的 $O$ = (苹果,葡萄,橙子)的概率
等于(在“金,银,金”的状态序列下,出现“苹果,葡萄,橙子”的概率) * (出现“金,银,金”的状态序列的概率)
又因为 $P(O|S,\lambda) = b_{11}b_{22}…b_{TT}$;
而 $P(S|\lambda) = \pi_{1}a_{12}a_{ 23}…a_{ (T-1)T}$,其中 $a_{ij}$ 为矩阵 $A$ 中的元素;
所以 $P(O|\lambda) = \sum_{s_1,s_2,…,s_T } \pi_{ 1} b_{11}a_{12} b_{22}a_{23}… a_{(T-1)T} b_{TT}$。
理论上讲,我们可以把所有状态序列都按照上述公式计算一遍,但它的时间复杂度是 $O(TN^T)$,计算量太大了,基本上不可行。
前向-后向算法
如果不是直接计算,还有什么办法可以算出一个观测序列出现的概率吗?
当然有,那就是前向-后向算法。
前向—后向算法是一种动态规划算法。它分两条路径来计算观测序列概率,一条从前向后(前向),另一条从后向前(后向)。这两条路径,都可以分别计算观测序列出现概率。
在实际应用中,选择其中之一来计算就可以。
所以,前向-后向算法其实也可以被看作两个算法:前向算法和后向算法,它们可以分别用来求解 $P(O|\lambda)$。
前向算法
设 $\alpha_t(i) = P(o_1, o_2, …, o_t, s_t = S_i| \lambda)$ 为前向概率。
它表示的是:给定 $\lambda$ 的情况下,到时刻 $t$ 时,已经出现的观测序列为 $o_1,o_2,…o_t$ 且此时状态值为 $S_i$ 的概率。
此处写法有点 Confusing,这里具体解释一下。
现在是 $t$ 时刻,到此刻为止,我们获得的观测序列是 $(o_1, o_2, …, o_t)$,这些 $o_1, o_2, …, o_t$ 的下标标志是时刻(而非观测空间的元素下标),具体某个 $o_i$ 的取值才是观测空间中的一项。因此观测序列中很可能出现 $o_i = o_j$ 的状况。
$S_i$ 为一个具体的状态值。当前 HMM 的状态空间一共有 $N$ 个状态值:$(S_1, S_2, …, S_N)$,$S_i$ 是其中的一项。
$s_t$ 在此处表示 $t$ 时刻的状态,它的具体取值是 $S_i$。
因此有:
(1)$\alpha_1(i)= \pi_{i}b_i (o_1),\ \ i = 1,2, …, N$;
(2)递推,对于 $t=1,2,…, T-1$,有 $\alpha_{t+1}(i) = [\sum_{j=1}^{N} \alpha_t(k) a_{ji}] b_i(o_{t+1}), \ \ i = 1,2, …, N$;
(3)最终 $P(O|\lambda) = \sum_{i=1}^{N}\alpha_T(i),\ \ i = 1, 2, …, N$。
如此一来,概率计算问题的计算复杂度就变成了 $O(N^2T)$。
后向算法
设 $\beta_t(i) = P(o_{t+1}, o_{t+2}, …, o_T|s_t =S_i, \lambda)$ 为后向概率。
它表示的是:给定 $\lambda$ 的情况下,到时刻 $t$ 时,状态为 $S_i$ 的条件下,从 $t+1$ 到 $T$ 时刻出现的观察序列为 $o_{t+1}, o_{t+2}, …, o_T$ 的概率。
(1)$\beta_T(i) = 1, \ \ i=1,2,…, N$——到了最终时刻,无论状态是什么,我们都规定当时的后向概率为$1$;
(2)对 $t = T-1, T-2, …, 1$,有 $\beta_t(i) = \sum_{j=1}^{N} a_{ij}b_j (o_{t+1})\beta_{t+1}(j), \ \ i=1,2,…, N$;
(3)$P(O|\lambda) = \sum_{i=1 }^{N} \pi_i b_i(o_1) \beta_1(i), \ \ i=1,2,…, N$。
结合前向后向算法,定义 $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, …, T-1$
预测算法
直接求解
预测算法是在 $\lambda$ 既定,观测序列已知的情况下,找出最有可能产生如此观测序列的状态序列的算法。
比如,上面的例子中,真的出现了 $O$= (苹果,葡萄,橙子),那么,最有可能导致 $O$ 出现的 $S$ 是什么?
比较直接的算法是:在每个时刻 $t$,选择在该时刻最有可能出现的状态 $s_t^* $,从而得到一个状态序列 $S^* =(s_1^* , s_2^* ,…, s_T^* )$,直接就把它作为预测结果。
给定 $\lambda$ 和观测序列 $O$ 的情况下,$t$ 时刻处于状态 $S_i$ 的概率为:
$\gamma_t(i) = P(s_t=S_i |O,\lambda)$
因为 $ \gamma_t(i) = P(s_t = S_i| O, \lambda) = \frac{P(s_t=S_i, O|\lambda)}{P(O|\lambda)}$,通过前向概率 $\alpha_t(i)$ 和后向概率 $\beta_t(i)$ 定义可知:
$\alpha_t(i) \beta_t(i) = P(s_t =S_i, O | \lambda)$。
所以有:$\gamma_t(i) = \frac{\alpha_t(i)\beta_t(i)}{P(O|\lambda)} = \frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1 }^{N} \alpha_t(j)\beta_t(j)}$。
有了这个公式,我们完全可以求出 $t$ 时刻,状态空间中每一个状态值 $S_1, S_2, …, S_N$ 所对应的 $\gamma_t(i)$,然后选取其中概率最大的作为 $t$ 时刻的状态即可。
这种预测方法在每一个点上都求最优,然后再“拼”成整个序列。
它的优点是简单明了,缺点同样非常明显:不能保证状态序列对于观测序列的支持整体最优。
维特比算法
如何避免掉那些实际上不会发生的状态序列,从而求得整体上的“最有可能”呢?
有一个很有名的算法:维特比算法——用动态规划求解概率最大路径。
维特比算法是求解 HMM 预测问题的经典算法。
推荐:
小白给小白详解维特比算法(一)
小白给小白详解维特比算法(二)
学习算法
HMM 的学习算法根据训练数据的不同,可以分为有监督学习和无监督学习两种。
如果训练数据既包括观测序列,又包括对应的状态序列,且两者之间的对应关系已经明确标注了出来,那么就可以用有监督学习算法。
否则,如果只有观测序列而没有明确对应的状态序列,就需要用无监督学习算法训练。
有监督学习
训练数据是若干观测序列和对应的状态序列的样本对(Pair)。也就是说训练数据不仅包含观测序列,同时每个观测值对应的状态值是什么,也都是已知的。
那么,最简单的,我们可以用频数来估计概率。
我们经过统计训练数据中所有的状态值和观测值,可以得到状态空间 $(S_1, S_2, …, S_N)$ 和观测空间 $(O_1, O_2, …, O_M)$。
假设样本中时刻 $t$ 处于状态为 $S_i$,到了 $t+1$ 时刻,状态属于 $S_j$ 的频数为 $A_{ij}$,那么状态转移概率 $a_{ij}$ 的估计是:
$\hat{a_{ij}} = \frac{A_{ij}}{\sum_{j=1}^{N}(A_{ij})},\ \ i=1,2,…, N; \ \ j=1,2,…,N$
假设样本状态为 $S_j$,观测为 $O_k$ 的频数为 $B_{jk}$,观测概率 $b_{jk}$ 的估计是:
$\hat{b_{jk}} = \frac{B_{jk}}{\sum_{k=1}^{M}(B_{jk})}, \ \ j=1,2,…,N; \ \ k= 1,2,…, M$
初始状态概率 $\pi_i$ 的估计 $\hat{\pi_i}$ 为所有样本中初始状态为 $S_i$ 的频率。
这样,通过简单的统计估计,就得到了$\lambda = (\hat{A}, \hat{B}, \hat{\pi})$。
无监督学习
当训练数据仅有观测序列(设观测序列为 $O$),而没有与其对应的状态序列时,状态序列 $S$ 实则处于隐藏状态。
这种情况下,我们是不可能直接用频数来估计概率的。
有专门的 Baum-Welch
算法,针对这种情况求 $\lambda=(A, B, \pi) $。
Baum-Welch
算法利用了前向-后向算法,同时还是 EM 算法的一个特例。简单点形容,大致是一个嵌套了 EM 算法的前向-后向算法。
HMM 实例
用代码实现前述死囚轮盘赌问题:
from __future__ import division
import numpy as np
from hmmlearn import hmm
def calculateLikelyHood(model, X):
score = model.score(np.atleast_2d(X).T)
print "\n\n[CalculateLikelyHood]: "
print "\nobservations:"
for observation in list(map(lambda x: observations[x], X)):
print " ", observation
print "\nlikelyhood:", np.exp(score)
def optimizeStates(model, X):
Y = model.decode(np.atleast_2d(X).T)
print"\n\n[OptimizeStates]:"
print "\nobservations:"
for observation in list(map(lambda x: observations[x], X)):
print " ", observation
print "\nstates:"
for state in list(map(lambda x: states[x], Y[1])):
print " ", state
states = ["Gold", "Silver", "Bronze"]
n_states = len(states)
observations = ["Apple", "Grape", "Orange", "Blueberry"]
n_observations = len(observations)
start_probability = np.array([0.3, 0.3, 0.4])
transition_probability = np.array([
[0.1, 0.5, 0.4],
[0.4, 0.2, 0.4],
[0.5, 0.3, 0.2]
])
emission_probability = np.array([
[0.4, 0.2, 0.2, 0.2],
[0.25, 0.25, 0.25, 0.25],
[0.33, 0.33, 0.33, 0]
])
model = hmm.MultinomialHMM(n_components=3)
# 直接指定pi: startProbability, A: transmationProbability 和B: emissionProbability
model.startprob_ = start_probability
model.transmat_ = transition_probability
model.emissionprob_ = emission_probability
X1 = [0,1,2]
calculateLikelyHood(model, X1)
optimizeStates(model, X1)
X2 = [0,0,0]
calculateLikelyHood(model, X2)
optimizeStates(model, X2)
如果出现错误提示:ModuleNotFoundError: No module named 'hmmlearn'
可以尝试手动安装hmmlearn解决pip install -U --user hmmlearn
,参考
输出结果:
[CalculateLikelyHood]:
observations:
Apple
Grape
Orange
likelyhood: 0.021792431999999997
[OptimizeStates]:
observations:
Apple
Grape
Orange
states:
Gold
Silver
Bronze
[CalculateLikelyHood]:
observations:
Apple
Apple
Apple
likelyhood: 0.03437683199999999
[OptimizeStates]:
observations:
Apple
Apple
Apple
states:
Bronze
Gold
Bronze