HMM隐马尔可夫模型概述

隐马尔可夫模型

隐马尔可夫模型（hidden Markov model， HMM）适用于标注问题的统计学习模型，描述又隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。

引子

考虑一个这样的场景,我们是一个瓜农,在我们的瓜地里种着很多的瓜.
而瓜地有很多条行行~,我们称呼一条行行为一个膜.
然后呢,种瓜的时候,我会从这个瓜田中的随机一个膜开始种瓜.
再然后呢,我会从我的兜兜里摸出一枚瓜子儿,这粒瓜子儿呢,我先不说它是什么瓜的瓜子儿,因为是从我兜兜里摸出来的嘛,我兜兜里有甜瓜,西瓜,打瓜,哈密瓜,我可不知道会是哪一种呢.
~~别跟我说拿眼睛辨别一下,不看不看我就是不看 QAQ~~
好啦,第一枚瓜子儿就这样投进了对应的区域,然后啊,我再依靠某种概率,走到瓜田的另外一个膜种瓜的地方,开始下一次投子儿...
我们的HMM研究的,就是这样一个问题.看起来挺简单的哈,那我们再来规范化一下.

HMM的基本概念

定义：HMM是一个关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再有各个状态生成一个观测而产生观测随机序列的过程。
状态序列：隐马尔可夫链随机生成的状态序列。
观测序列：每个状态生成一个观测，由此而产生的观测的随机序列。
Q是所有可能的状态的合集

$Q=\{q_1,q_2,q_3,...,q_N\}$
V是所有可能的观测的合集

$V=\{v_1,v_2,v_3,...,v_M\}$
I是长度为T的状态序列

$I=(i_1,i_2,i_3,...,i_T)$
O是状态序列对应的观测序列

$O=(o_1,o_2,o_3,...,o_T)$
A是状态转移概率矩阵

$A=[a_{ij}]_{M \cdot N}$

显然可以知道
$a_{ij}=P(i_{t+1}=q_j|i_t=q_i), i=1,2,3,...N, j=1,2,3,...,N;$
指的是在t时刻状态为 $q_i$ ,并在t+1时刻由状态 $q_i$ 转变为状态 $q_j$ 的概率。

B是观测概率矩阵

$B=[b_j(k)]_{N \cdot M}$

显然也可以知道
$b_j(k)=P(o_t=v_k|i_t=q_j), k=1,2,3,...N,j=1,2,3,...,N;$
指的是在t时刻状态为 $q_j$ ,并生成观测 $v_k$ 的概率。

$\pi$ 是初始状态概率向量

同理
$\pi _i=P(i_1=q_i), i=1,2,3,...,N$
指的是时刻t=1处于状态 $q_t$ 的概率

隐马尔科夫模型由初始概率分布，状态转移概率分布，观测概率分布确定。

即 HMM可由 $\lambda =(A, B, \pi)$ 表示.

我们可知状态转移概率矩阵A与初始状态概率向量 $\pi$ 确定了隐马尔科夫链,生成不可观测的状态序列.观测概率矩阵B确定了如何从状态生成观测,与状态序列综合确定了如何产生观测序列.
让我们再来明确应用HMM时的两个假设:
- 齐次马尔科夫假设: 隐马尔科夫链在任意时刻t的状态只依赖于其前一刻的状态,与其他时刻的状态以及观测无关,也就是说与时刻t同样无关
$P(i_t|i_{t-1},o_{t-1},...,i_1,o_1)=P(i_t|i_{t-1}), t=1,2,...,T$
- 独立观测性假设: 假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态,与其他观测及状态无关
$P(o_t|i_T,o_T,i_{T-1},o_{T-1},...,i_1,o_1)=P(o_t|i_t)$

回到引子

再次回到我们种瓜的问题哈,有了上面的规范化术语储备,来让我们把它和我们的瓜田问题对应起来.
假设有一位我的迷妹,把我每次种瓜的瞬间都拿相机记录了下来 ~~醒一醒不存在的~~.
那么在她的底片上,就会有我按时间序列呈顺序分布的拍照剪影,我们称其为状态片段.
那么一整条胶卷也就形成了一个状态序列.
假设我在膜与膜之间切换的时候是遵循着一个特定的规律,譬如我从i膜切换到j膜的时候概率是 $a_{ij}$ ,那么我在膜与膜之间切换的概率自然就形成了一个概率矩阵,我们称其为状态转移矩阵.
再假设,冰雪聪明的迷妹能够发现我埋下去的是哪一种瓜的种子,那么这里将来也就会长出什么瓜嘛,而迷妹也发现了我摸出各个瓜子的几率其实是和膜相关的.
(这肯定啦,有的膜靠渠道近,那么水量足,我大概率就摸出来缺水的瓜,有的膜靠着土坡坡,那我大概率就摸出不怎么需要阳光的瓜嘛,这一切都是命运石之门的安排.)
~~(口胡,你明明都没有看摸出来的是什么瓜子儿的说.)~~
倘若我当前所在的行是j行,想知道我摸出瓜子儿k的概率,那么这个概率也就被描述成为 $b_j(k)$ .

观测序列的生成过程

我们可以将一个长度为T的观测序列O=(o_1,o_1,...,o_T)的生成过程描述如下:
- 输入HMM: $\lambda =(A, B, \pi)$ 和序列长度 T
  - 按照初始状态分布 $\pi$ 产生状态 $i_1$
  - 令t=1
  - 按照状态 $i_t$ 的观测概率分布 $b_{i_1}(k)$ 生成o_t (1)
  - 按照状态 $i_t$ 的状态转移概率分布 ${a_{i_ti_{t+1}}}$ 生成状态 $i_{t+1}$ ,且 $i_{t+1}$ =1,2,...,N
  - 令t=t+1,如果t < T,移步(1),否则,则终止.
  - 输出观测序列 $O=(o_1,o_2,...,o_T).$

HMM的三个基本问题

概率计算问题 给定模型 $\lambda = (A, B, \pi)$ 和观测序列 $O=(o_1,o_2,...,o_t)$ ,在模型 $\lambda$ 下计算序列O出现的概率P(O| $\lambda$ )
学习问题 已知观测序列 $O=(o_1,o_2,...,o_T)$ ,估计模型 $\lambda = (A, B, \pi)$ ,使得在该模型下观测序列概率P(O| $\lambda$ )最大,即用最大似然估计的方法估计参数.
预测问题/解码问题 已知模型 $\lambda =(A, B, \pi)$ 和观测序列 $O=(o_1, o_2, o_3,...,o_T)$ ,求给定观测序列条件概率 $P(I|O)$ 最大的状态序列.

概率计算算法

直接计算法
- 给定模型 $\lambda = (A, B, \pi)$ 的情况下,当我们需要知道 $P(O|\lambda)$ 的时候,可以先求得状态序列 $I$ 出现的概率:
  $P(I|\lambda) = \pi _{i_1}a_{i_1 i_2}a_{i_2 i_3}...a_{i_T-1 i_T}$
- 倘若再次基础上附加上观测序列的生成概率的话,那就是:
  $P(I,O|\lambda) = P(I|\lambda) \cdot b_{i_1}(o_1) \cdot b_{i_2}(o_2) \cdot ... \cdot b_{i_t}(o_t)$
- 这时候只要我们再把所有的序列 $I$ 的概率加在一起,就可以得到我们期待的 $P(O|\lambda)$ 了.
  $P(O|\lambda) = \sum _I P(O,I|\lambda)$
- 推导起来是不是轻松加愉快呢,但我们通常不采取这种方法是有原因的呀,下面来让我们看一下这种方法计算的复杂度.
  1.计算 $P(I,O|\lambda)$ 的时候我们只需要计算等同于长度 $T$ 的次数,也就是 $T$ 次.
  2.但是在我们在下一步将不同的 $I$ 累加起来的时候,就会发现, $I$ 可由N种元素 $(i_1, i_2,...,i_N)$ 无限制混搭形成.即有 $N^T$ 种组合方式,两者相乘我们就有 $O(TN^T)$ 的复杂度,怪不得我们不用这种方法呢.ww
前向算法
- 先来抛个小定义
前向概率: 给定HMM为 $\lambda = (A,B,\pi)$ ,已知截止到 $t$ 时刻的观测序列 ${o_1, o_2, o_3,...,o_t}$ ,又知道 $t$ 时刻的状态 $q_t$ ,记作:
$\alpha _t(i) = P(o_1,o_2,...,o_t,i_t = q_t|\lambda)$
- 给定HMM $\lambda$ 与观测序列 $O$
  1.初值
  $\alpha _1(i) = \pi _ib_1(o_1), i = 1, 2,...,N$
  2.递推
  $\alpha _{t+1}(i_{t+1}) = \sum _{i_t=1}^N \alpha_t(i_t) \cdot a_{i_t i_{t+1}} \cdot b_{i_{t+1}}(o_{t+1}), i = 1, 2,..., T-1$
  - 这里显然是遵循了齐次马尔可夫定理的,我们在计算概率的时候是仅仅只用到了前一项.
  - 可能会有一点儿难理解,那就再稍微解释一下. 这条递推公式的含义是, 后一项 $\alpha _{t+1}(i+1)$ 的前向概率是前一项 $\alpha _t(i) (i \in Q)$ 的所有情况与对应的状态转移概率 $a _{i_t i_{t+1}}$ 的乘积的加和,在 $a _{i_t i_{t+1}}$ 中 $i_t$ 是变化的,而 $i_{t+1}$ 则是一开始就给定的 $\alpha _{t+1}(i_{t+1})$ 的 $i_{t+1}$ ,之后再乘以对应的观测概率 $b_{i_{t+1}}(o_{t+1})$ 就可以啦.
  - 顺带一提的是,这里我们不强调各个项的顺序,因为累加可以类比于一种离散的积分,既然是积分,那么与被积分项无关的部分可以提到括号最外面,所以同理我们这里就不强调顺序啦.
  3.终止
  $P(O|\lambda) = \sum _{i=1}^N \alpha _T(i)$
  
  至此,我们就完美利用前向算法求出了我们需要的观测序列概率 $P(O|\lambda)$ 啦.
- 举个前向算法的栗子叭
  
  假设种瓜的杨同学目前只给三个膜种瓜,只带了西瓜籽儿和甜瓜籽儿这两种瓜籽儿.
  状态转移矩阵:
  $A = \left\{ \begin{matrix} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 & 0.5 \end{matrix} \right\}$
  观测矩阵:
  $B = \left\{ \begin{matrix} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{matrix} \right\}$
  初始状态向量:
  $\pi = (0.2, 0.4, 0.4)^T$
  设 $T=3$ , $O$ =(西瓜, 甜瓜, 西瓜),试用前向算法计算 $P(O|\lambda)$
- 解:
  - 计算初值
    $\alpha _1(i) = \pi _ib_1(o_1), i = 1, 2,...,N$
    $\alpha _1 = 0.2 \cdot 0.5 = 0.1$
    $\alpha _2 = 0.4 \cdot 0.4 = 0.16$
    $\alpha _3 = 0.4 \cdot 0.7 = 0.28$
  - 递推
    $\alpha _{t+1}(i_{t+1}) = \sum _{i_t=1}^N \alpha_t(i_t) \cdot a_{i_t i_{t+1}} \cdot b_{i_{t+1}}(o_{t+1}), t = 1, 2,..., T-1$
    $\alpha _2(1) = (0.1 \cdot 0.5 + 0.16 \cdot 0.3 + 0.28 \cdot 0.2) \cdot 0.5 = 0.077$
    $\alpha _2(2) = (0.1 \cdot 0.2 + 0.16 \cdot 0.5 + 0.28 \cdot 0.3) \cdot 0.6 = 0.1104$
    $\alpha _2(3) = (0.1 \cdot 0.3 + 0.16 \cdot 0.2 + 0.28 \cdot 0.5) \cdot 0.3 = 0.0606$
    $\alpha _3(1) = 0.04187$
    $\alpha _3(2) = 0.035512$
    $\alpha _3(3) = 0.052836$
  - 终止
    $P(O|\lambda) = \sum _{i=1}^N \alpha _T(i)$
    T = 3,带入上一步的值,可得:
    $P(O|\lambda) = \alpha _3(1) + \alpha _3(2) + \alpha _3(3) = 0.130218$
后向算法
- 再来抛个小定义
后向概率: 给定HMM为 $\lambda = (A,B,\pi)$ .定义在时刻 $t$ 状态为 $q_i$ 的情况下,从 $t+1$ 到 $T$ 的部分观测序列为 $o_{t+1},o_{t+2},...,o_T$ 的概率为后向概率.
$\beta _t(i) = P(o_{t+1},o_{t+2},...,o_T|i_t = q_t,\lambda)$
- 前面我们才讲过前向概率,可能到这里会有一点儿点儿晕,不慌,我们来看一个示意图:

前后向概率区分.jpg

在前后向概率的定义中涉及的元素均如图所示,可以轻易加以区分.

同时我们需要明确,前向概率的推进方向是由左及右,后向概率的推进方向是由右及左.

给定HMM $\lambda$ 与观测序列 $O$
1.初值
$\beta _T(i) = 1, i = 1, 2, ..., N$
2.递推
$\beta _t(i_t)=\sum _{i_{t+1}=1}^N a_{i_t i_{t+1}}b_{i_{t+1}}(o_{t+1}) \beta _{t+1}(i_{t+1})$

从中我们不难发现后向概率的递推和前向概率的递推有很大的相似性,这次固定的变成了 $a_{i_t i_{t+1}}$ 中的 $i_t$ ,由左侧的 $\beta _t(i_t)$ 给定,而 $i_{t+1}$ 则根据后一项的状态 $i_{t+1}$ 的不同而变化.

3.终止
$P(O|\lambda)=\sum _{i=1}^N \pi _i b_i(o_1) \beta_1(i)$

这里我们就成功利用后向算法计算出了我们想要的观测概率 $P(O| \lambda)$ 了.

最后再举个后向算法的栗子叭,就拿刚才那一题好了,我们再把题目搬过来~

假设种瓜的杨同学目前只给三个膜种瓜,只带了西瓜籽儿和甜瓜籽儿这两种瓜籽儿.
状态转移矩阵: $A = \left\{ \begin{matrix} 0.5 & 0.2 & 0.3 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 & 0.5 \end{matrix} \right\}$
观测矩阵:
$B = \left\{ \begin{matrix} 0.5 & 0.5 \\ 0.4 & 0.6 \\ 0.7 & 0.3 \end{matrix} \right\}$
初始状态向量:
$\pi = (0.2, 0.4, 0.4)^T$
设 $T=3$ , $O$ =(西瓜, 甜瓜, 西瓜),试用前向算法计算 $P(O|\lambda)$
解:
- 计算初值
  $\beta _t(i) = 1, i=1, 2, 3,...,N$
  $\beta _3 (1) = 1$
  $\beta _3 (2) = 1$
  $\beta _3 (3) = 1$
- 递推
  $\beta _t(i_t)=\sum _{i_{t+1}=1}^N a_{i_t i_{t+1}}b_{i_{t+1}}(o_{t+1}) \beta _{t+1}(i_{t+1})$
  $\beta _2(1) = (0.5 \cdot 0.5 \cdot1 +0.2 \cdot 0.4 \cdot 1 + 0.3 \cdot 0.7 \cdot 1) = 0.54$
  $\beta _2(2) = (0.3 \cdot 0.5 \cdot1 +0.5 \cdot 0.4 \cdot 1 + 0.2 \cdot 0.7 \cdot 1) = 0.49$
  $\beta _2(3) = (0.2 \cdot 0.5 \cdot1 +0.3 \cdot 0.4 \cdot 1 + 0.5 \cdot 0.7 \cdot 1) = 0.57$
  $\beta _1(1) = (0.5 \cdot 0.5 \cdot 0.54 +0.2 \cdot 0.6 \cdot 0.49 + 0.3 \cdot 0.3 \cdot 0.57) = 0.2451$
  $\beta _1(2) = (0.3 \cdot 0.5 \cdot 0.54 +0.5 \cdot 0.6 \cdot 0.49 + 0.2 \cdot 0.3 \cdot 0.57) = 0.2622$
  $\beta _1(3) = (0.2 \cdot 0.5 \cdot 0.54 +0.3 \cdot 0.6 \cdot 0.49 + 0.5 \cdot 0.3 \cdot 0.57) = 0.2277$
- 终止
  $P(O|\lambda)=\sum _{i=1}^N \pi _i b_i(o_1) \beta_1(i)$
  $P(O| \lambda) = 0.2 \cdot 0.5 \cdot 0.2451 + 0.4 \cdot 0.4 \cdot 0.2622 + 0.4 \cdot 0.7 \cdot0.2277 = 0.130218$
检验后我们可以发现结果与之前我们利用前项算法得出的结论是一致的.ww

最后编辑于：2019.08.17 19:44:17

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 196,165评论 5赞 462
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 82,503评论 2赞 373
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 143,295评论 0赞 325
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,589评论 1赞 267
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,439评论 5赞 358
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,342评论 1赞 273
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,749评论 3赞 387
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,397评论 0赞 255
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,700评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,740评论 2赞 313
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,523评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,364评论 3赞 314
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,755评论 3赞 300
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,024评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,297评论 1赞 251
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,721评论 2赞 342
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,918评论 2赞 336

HMM隐马尔可夫模型概述

隐马尔可夫模型

引子

HMM的基本概念

回到引子

观测序列的生成过程

HMM的三个基本问题

概率计算算法

直接计算法

前向算法

后向算法

推荐阅读更多精彩内容