区块链技术博客
www.b2bchain.cn

【概率图模型】S08E05 概率估计:隐马尔科夫模型观测序列描述求职学习资料

D0b2wT.gif

本文介绍了【概率图模型】S08E05 概率估计:隐马尔科夫模型观测序列描述求职学习资料,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

1.隐马尔科夫模型要研究什么

1.1.一个赌场的故事背景

在上一小节里,我们基本上把隐马尔科夫模型的运行机制和基本要素讲清楚了,那么他的关键研究要点是什么?或者说一般而言我们关注的研究问题聚焦在哪些方面呢?

我们不妨来看一个例子,这个例子可以更好的讲清楚我们为什么要研究这个模型,以及问题的关键点在哪。

这里我们举一个赌博的例子,大家应该都听说过用骰子猜大小的赌博游戏,掷出骰子,如果点数为$1,2,3$,则为小,如果点数为$4,5,6$,则为大。对于一个正常的骰子而言,掷出$1,2,3,4,5,6$的点数的概率都是相等的,即都为$frac{1}{6}$,因此大小的概率各半,可以说是听天由命了,这个结果对于赌客而言是公平的,纯凭运气。

但是如果掷骰子的人是一个老千呢?也就是说他手上的骰子是特制的,各个点数投掷出来的概率不再均等,那赌客的钱包可得遭殃了。

怎么讲?举个例子,老千手上有三个骰子,$1$号骰子是正常的,$2$号骰子和$3$号骰子都是特制的,他每次使用其中一个骰子进行投掷,并且不停的偷偷对这三个骰子进行切换使用,也就是说你不知道他使用的是哪个骰子,因此这对应的就是隐藏状态,而由骰子掷出的点数就是观测,这个很好理解。

那么由两个作弊的骰子掷出各个点数的概率,也就是输出概率如下图所示:
【概率图模型】S08E05 概率估计:隐马尔科夫模型观测序列描述

图1.作弊骰子的输出概率

同时,老千每次随机使用其中一个骰子,在三个骰子之间互相转换的过程符合马尔科夫性,因此这里还会包含有一个三个骰子之间相互切换的概率转移矩阵。

1.2.研究问题描述

基于上述背景,我们就来谈谈我们到底会去研究些什么。

第一个研究的内容是观测序列概率估计: 当我们知道老千切换三个骰子的转移概率矩阵以及各个骰子输出各个点数的概率的基础上,我们可以计算出任意一个观测序列出现的概率,比如老千连续掷出诡异的$8$个$6$,我们可以看看这种情况发生的概率有多大。

用隐马尔科夫模型的形式化语言概况就是:在给定隐马尔科夫模型三要素 $lambda=(A,B,pi)$ 的基础上,针对一个具体的观测序列$O=(o_1,o_2,…,o_T)$,求他出现的概率。

第二个研究的内容是隐含状态序列解码: 当我们知道老千切换三个骰子的转移概率以及各个骰子输出各个点数的概率时,我们可以通过已知的观测序列,也就是骰子的点数序列,来解码出老千所使用的骰子的序列,也就是隐状态序列。换句话说,就是可以推测出每一个掷出的点数背后,老千到底用的是哪一个骰子,可以判断他什么时候出千。

用隐马尔科夫模型的形式化语言概况就是:在给定隐马尔可夫模型三要素$lambda=(A,B,pi)$和观测序列$O=(o_1,o_2,…,o_T)$的基础上,求最有可能对应的隐藏状态序列$I=(i_1,i_2,…i_T)$。

那么具体该怎么做,我们接下来开始详细讲解,这一小节里我们首先介绍指定观测序列的概率估计问题:

即在已知隐马尔科夫模型$lambda=(A,B,pi)$的基础上,求指定观测序列$O=(o_1,o_2,…,o_T)$出现的概率,也就是我们上面一个例子中所说的,求扔出一串指定点数骰子的概率,那么用条件概率来表示我们的计算目标就是:求$P(O|lambda)$的概率。

2.一个直观的思路

首先来梳理一下这里面的思路,我们知道,对于同一个观测序列$O$而言,可以对应不同的隐含状态序列$I$,实际上所有的隐含状态序列$I$ 都能够以一定的概率生成这个观测序列$O$。

那么按这个思路,$P(O|lambda)$的求解过程就可以看作是通过对一系列不同$I$和指定对应$O$的联合概率进行求和,最终得到边缘概率的过程:$P(O|lambda)=sum_{I}P(O,I|lambda)$。

然后联合概率$P(O,I|lambda)$按照贝叶斯公式进行展开有:$P(O,I|lambda)=P(O|I,lambda)P(I|lambda)$,我们代入到原始公式中,就将目标式子转化成了:

$P(O|lambda)=sum_{I}P(O|I,lambda)P(I|lambda)$

这个概率怎么计算呢?对于任意一个隐含状态序列,我们设他的序列为:$I=(i_1,i_2,i_3,…,i_T)$,同时转移概率矩阵为$A$。那么首先利用马尔科夫链生成这个隐含状态:

$P(I|lambda)=pi_{i_1}a_{i_1i_2}a_{i_2i_3}a_{i_3i_4}…a_{i_{T-1}i_T}$

然后我们再接着求解概率$P(O|I,lambda)$,$P(O|I,lambda)$的本质就是利用这个已知的隐含状态序列$I=(i_1,i_2,i_3,…,i_T)$去生成指定的观测序列$O=(o_1,o_2,o_3,…,o_T)$,这里要运用一下输出概率矩阵$B$:

$P(O|I,lambda)=b_{i_1o_1}b_{i_2o_2}…b_{i_To_T}$

那么我们把他合并起来就有:

$P(O,I|lambda)=P(O|I,lambda)P(I|lambda)=pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}a_{i_2i_3}b_{i_3o_3}…a_{i_{T-1}i_T}b_{i_To_T}$

这里补充一句,大家从$P(O,I|lambda)$和$P(O|I,lambda)$的表达式的不同,就能体会到这两个概率式子的不同含义。

3.直接计算的问题

看上去$P(O,I|lambda)=P(O|I,lambda)P(I|lambda)$的计算并不难,就是$2T$次乘法运算,但是请你注意,他的外面还有一个求和的$sum$运算,恐怖的地方在这,相当于要对每一个可能出现的隐含状态序列都进行$2T$次乘法运算,所有的隐含状态序列有多少个?序列长度为$T$,隐含状态集中有$N$个状态,那么所有的隐含状态序列的个数就是 $N^T$,整个运算复杂度就是$O(TN^T)$,这恐怕是不能接受的。

4.更优的方法:前向概率算法

4.1.算法推导证明

这里我们一般采取的是基于递推的前向概率算法,这个算法有一定的推导过程,在这个过程中我们本质上就是不断的在条件概率、联合概率和边缘概率之间做着转换,这也是一个很好的复习的过程。

我们先定义一个变量:$alpha_t(i)=P(o_1,o_2,…,o_t,i_t=q_i|lambda)$

那么,我们来看看这个和我们的目标计算概率$P(O|lambda)$也就是$P(o_1,o_2,…,o_T|lambda)$有什么联系?还是那个思路:利用联合概率求解边缘概率:

$P(o_1,o_2,…,o_T|lambda)=sum_{i=1}^{N}P(o_1,o_2,…,o_T,i_T=q_i|lambda)$,看看同学们啊,$P(o_1,o_2,…,o_T,i_T=q_i|lambda)$这个是什么?这个不就是$alpha_T(i)$吗?

于是整个目标概率就变成了:$P(o_1,o_2,…,o_T|lambda)=sum_{i=1}^{N}alpha_T(i)$,问题就来了,如何求 $alpha_T(i)$?

这里我先抛出一个递推公式:$alpha_{t+1}(i)=[sum_{j=1}^{N}alpha_t(j)a_{ji}]b_{io_{t+1}}$。

这个公式是一个神器,他的物理意义很直观,$alpha_t(j)=P(o_1,o_2,…,o_t,i_t=q_j|lambda)$所表达的是在时刻$t$,一方面已经形成观测序列$(o_1,o_2,…,o_t)$ ,另一方面此时隐状态是$i_t=q_j$,很明显的是,当$j$取$1$到$N$任意一个值的时候,都可以通过转移概率在$t+1$时刻转移到$i_{t+1}=q_i$,因此合并所有$alpha_{t}(j)a_{ji}$之后,再在$i_{t+1}=q_i$的隐状态上输出$o_{t+1}$,就得到了$alpha_{t+1}(i)$。

这是从内涵意义层面进行的推导,如果我们下面来证明一下这个式子的成立,我们就能放心大胆的从$alpha_1(i)$一步一步的递推到$alpha_T(i)$。

那么怎么证明这个递推关系成立呢?按道理来说,其实大家都不喜欢看大篇幅的公式证明,但是这里确实是不可避免的,必须要真刀真枪的把问题说清楚,不过呢我来个庖丁解牛,一定要大家轻轻松松搞明白。

在推导之前,我还是要再强调一下:抓住两个关键点,所有的推导都是建立在其上的:

一个是联合概率到边缘概率的转换关系;
一个是条件概率到联合概率的转换关系,也就是贝叶斯公式;

让我们开始,首先拿出定义:$alpha_t(i)=P(o_1,o_2,o_3,…,o_t,i_t=q_i|lambda)$

然后看$a_{ji}$,这个再熟悉不过了,隐含状态从$t$时刻的状态$j$转移到$t+1$时刻的状态$i$的概率,写成条件概率就是:$a_{ji}=P(i_{t+1}=q_i|i_t=q_j,lambda)$。

好的,关键的地方来了,我们按照递推公式把他们写在一起:

$sum_{j=1}^{N}alpha_t(j)a_{ji}$
$=sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_i|lambda)P(i_{t+1}=q_i|i_t=q_j,lambda)$

下一步就是利用贝叶斯公式,将条件概率转换为联合概率,类似这样:$P(A,B)=P(A)P(B|A)$,那么,很显然:

$sum_{j=1}^{N}alpha_t(j)a_{ji}$
$=sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_j|lambda)P(i_{t+1}=q_i|i_t=q_j,lambda)$
$=sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_j,i_{t+1}=q_i|lambda)$

接下来怎么办,显然是一个联合概率到边缘概率的转换过程,说明白点就是经过$1$到$N$的求和之后,$i_t=q_j$这一块就被“边缘”了,就变成了:

$sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_j,i_{t+1}=q_i|lambda)$ $=P(o_1,o_2,o_3,…,o_t,i_{t+1}=q_i|lambda)$

还遥遥无期吗?说实话快了,最后一把,把$b_{io_{t+1}}$给结合上,$b_{io_{t+1}}$是观测输出概率,表示在时刻$i_{t+1}$,隐含状态为$q_i$时输出观测为$o_{t+1}$的概率,即:$b_{io_{t+1}}=P(o_{t+1}|i_{t+1}=q_i,lambda)$

最后我们把他加上,写成递推公式的完整形式:

$[sum_{j=1}^{N}alpha_t(j)a_{ji}]b_{io_{t+1}}=P(o_1,o_2,o_3,…,o_t,i_{t+1}=q_i|lambda)P(o_{t+1}|i_{t+1}=q_i,lambda)$,这又是一个条件概率到联合概率的转换过程:

$P(o_1,o_2,o_3,…,o_t,i_{t+1}=q_i|lambda)P(o_{t+1}|i_{t+1}=q_i,lambda)=P(o_1,o_2,o_3,…,o_{t+1},i_{t+1}=q_i|lambda)$

看看这是什么吧!$P(o_1,o_2,o_3,…,o_{t+1},i_{t+1}=q_i|lambda)$,不就是 $alpha_{t+1}(i)$吗?这样一来,$[sum_{j=1}^{N}alpha_t(j)a_{ji}]b_{io_{t+1}}=alpha_{t+1}(i)$就推导出来了。说实话,推出来挺激动的。

1.隐马尔科夫模型要研究什么

1.1.一个赌场的故事背景

在上一小节里,我们基本上把隐马尔科夫模型的运行机制和基本要素讲清楚了,那么他的关键研究要点是什么?或者说一般而言我们关注的研究问题聚焦在哪些方面呢?

我们不妨来看一个例子,这个例子可以更好的讲清楚我们为什么要研究这个模型,以及问题的关键点在哪。

这里我们举一个赌博的例子,大家应该都听说过用骰子猜大小的赌博游戏,掷出骰子,如果点数为$1,2,3$,则为小,如果点数为$4,5,6$,则为大。对于一个正常的骰子而言,掷出$1,2,3,4,5,6$的点数的概率都是相等的,即都为$frac{1}{6}$,因此大小的概率各半,可以说是听天由命了,这个结果对于赌客而言是公平的,纯凭运气。

但是如果掷骰子的人是一个老千呢?也就是说他手上的骰子是特制的,各个点数投掷出来的概率不再均等,那赌客的钱包可得遭殃了。

怎么讲?举个例子,老千手上有三个骰子,$1$号骰子是正常的,$2$号骰子和$3$号骰子都是特制的,他每次使用其中一个骰子进行投掷,并且不停的偷偷对这三个骰子进行切换使用,也就是说你不知道他使用的是哪个骰子,因此这对应的就是隐藏状态,而由骰子掷出的点数就是观测,这个很好理解。

那么由两个作弊的骰子掷出各个点数的概率,也就是输出概率如下图所示:
【概率图模型】S08E05 概率估计:隐马尔科夫模型观测序列描述

图1.作弊骰子的输出概率

同时,老千每次随机使用其中一个骰子,在三个骰子之间互相转换的过程符合马尔科夫性,因此这里还会包含有一个三个骰子之间相互切换的概率转移矩阵。

1.2.研究问题描述

基于上述背景,我们就来谈谈我们到底会去研究些什么。

第一个研究的内容是观测序列概率估计: 当我们知道老千切换三个骰子的转移概率矩阵以及各个骰子输出各个点数的概率的基础上,我们可以计算出任意一个观测序列出现的概率,比如老千连续掷出诡异的$8$个$6$,我们可以看看这种情况发生的概率有多大。

用隐马尔科夫模型的形式化语言概况就是:在给定隐马尔科夫模型三要素 $lambda=(A,B,pi)$ 的基础上,针对一个具体的观测序列$O=(o_1,o_2,…,o_T)$,求他出现的概率。

第二个研究的内容是隐含状态序列解码: 当我们知道老千切换三个骰子的转移概率以及各个骰子输出各个点数的概率时,我们可以通过已知的观测序列,也就是骰子的点数序列,来解码出老千所使用的骰子的序列,也就是隐状态序列。换句话说,就是可以推测出每一个掷出的点数背后,老千到底用的是哪一个骰子,可以判断他什么时候出千。

用隐马尔科夫模型的形式化语言概况就是:在给定隐马尔可夫模型三要素$lambda=(A,B,pi)$和观测序列$O=(o_1,o_2,…,o_T)$的基础上,求最有可能对应的隐藏状态序列$I=(i_1,i_2,…i_T)$。

那么具体该怎么做,我们接下来开始详细讲解,这一小节里我们首先介绍指定观测序列的概率估计问题:

即在已知隐马尔科夫模型$lambda=(A,B,pi)$的基础上,求指定观测序列$O=(o_1,o_2,…,o_T)$出现的概率,也就是我们上面一个例子中所说的,求扔出一串指定点数骰子的概率,那么用条件概率来表示我们的计算目标就是:求$P(O|lambda)$的概率。

2.一个直观的思路

首先来梳理一下这里面的思路,我们知道,对于同一个观测序列$O$而言,可以对应不同的隐含状态序列$I$,实际上所有的隐含状态序列$I$ 都能够以一定的概率生成这个观测序列$O$。

那么按这个思路,$P(O|lambda)$的求解过程就可以看作是通过对一系列不同$I$和指定对应$O$的联合概率进行求和,最终得到边缘概率的过程:$P(O|lambda)=sum_{I}P(O,I|lambda)$。

然后联合概率$P(O,I|lambda)$按照贝叶斯公式进行展开有:$P(O,I|lambda)=P(O|I,lambda)P(I|lambda)$,我们代入到原始公式中,就将目标式子转化成了:

$P(O|lambda)=sum_{I}P(O|I,lambda)P(I|lambda)$

这个概率怎么计算呢?对于任意一个隐含状态序列,我们设他的序列为:$I=(i_1,i_2,i_3,…,i_T)$,同时转移概率矩阵为$A$。那么首先利用马尔科夫链生成这个隐含状态:

$P(I|lambda)=pi_{i_1}a_{i_1i_2}a_{i_2i_3}a_{i_3i_4}…a_{i_{T-1}i_T}$

然后我们再接着求解概率$P(O|I,lambda)$,$P(O|I,lambda)$的本质就是利用这个已知的隐含状态序列$I=(i_1,i_2,i_3,…,i_T)$去生成指定的观测序列$O=(o_1,o_2,o_3,…,o_T)$,这里要运用一下输出概率矩阵$B$:

$P(O|I,lambda)=b_{i_1o_1}b_{i_2o_2}…b_{i_To_T}$

那么我们把他合并起来就有:

$P(O,I|lambda)=P(O|I,lambda)P(I|lambda)=pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}a_{i_2i_3}b_{i_3o_3}…a_{i_{T-1}i_T}b_{i_To_T}$

这里补充一句,大家从$P(O,I|lambda)$和$P(O|I,lambda)$的表达式的不同,就能体会到这两个概率式子的不同含义。

3.直接计算的问题

看上去$P(O,I|lambda)=P(O|I,lambda)P(I|lambda)$的计算并不难,就是$2T$次乘法运算,但是请你注意,他的外面还有一个求和的$sum$运算,恐怖的地方在这,相当于要对每一个可能出现的隐含状态序列都进行$2T$次乘法运算,所有的隐含状态序列有多少个?序列长度为$T$,隐含状态集中有$N$个状态,那么所有的隐含状态序列的个数就是 $N^T$,整个运算复杂度就是$O(TN^T)$,这恐怕是不能接受的。

4.更优的方法:前向概率算法

4.1.算法推导证明

这里我们一般采取的是基于递推的前向概率算法,这个算法有一定的推导过程,在这个过程中我们本质上就是不断的在条件概率、联合概率和边缘概率之间做着转换,这也是一个很好的复习的过程。

我们先定义一个变量:$alpha_t(i)=P(o_1,o_2,…,o_t,i_t=q_i|lambda)$

那么,我们来看看这个和我们的目标计算概率$P(O|lambda)$也就是$P(o_1,o_2,…,o_T|lambda)$有什么联系?还是那个思路:利用联合概率求解边缘概率:

$P(o_1,o_2,…,o_T|lambda)=sum_{i=1}^{N}P(o_1,o_2,…,o_T,i_T=q_i|lambda)$,看看同学们啊,$P(o_1,o_2,…,o_T,i_T=q_i|lambda)$这个是什么?这个不就是$alpha_T(i)$吗?

于是整个目标概率就变成了:$P(o_1,o_2,…,o_T|lambda)=sum_{i=1}^{N}alpha_T(i)$,问题就来了,如何求 $alpha_T(i)$?

这里我先抛出一个递推公式:$alpha_{t+1}(i)=[sum_{j=1}^{N}alpha_t(j)a_{ji}]b_{io_{t+1}}$。

这个公式是一个神器,他的物理意义很直观,$alpha_t(j)=P(o_1,o_2,…,o_t,i_t=q_j|lambda)$所表达的是在时刻$t$,一方面已经形成观测序列$(o_1,o_2,…,o_t)$ ,另一方面此时隐状态是$i_t=q_j$,很明显的是,当$j$取$1$到$N$任意一个值的时候,都可以通过转移概率在$t+1$时刻转移到$i_{t+1}=q_i$,因此合并所有$alpha_{t}(j)a_{ji}$之后,再在$i_{t+1}=q_i$的隐状态上输出$o_{t+1}$,就得到了$alpha_{t+1}(i)$。

这是从内涵意义层面进行的推导,如果我们下面来证明一下这个式子的成立,我们就能放心大胆的从$alpha_1(i)$一步一步的递推到$alpha_T(i)$。

那么怎么证明这个递推关系成立呢?按道理来说,其实大家都不喜欢看大篇幅的公式证明,但是这里确实是不可避免的,必须要真刀真枪的把问题说清楚,不过呢我来个庖丁解牛,一定要大家轻轻松松搞明白。

在推导之前,我还是要再强调一下:抓住两个关键点,所有的推导都是建立在其上的:

一个是联合概率到边缘概率的转换关系;
一个是条件概率到联合概率的转换关系,也就是贝叶斯公式;

让我们开始,首先拿出定义:$alpha_t(i)=P(o_1,o_2,o_3,…,o_t,i_t=q_i|lambda)$

然后看$a_{ji}$,这个再熟悉不过了,隐含状态从$t$时刻的状态$j$转移到$t+1$时刻的状态$i$的概率,写成条件概率就是:$a_{ji}=P(i_{t+1}=q_i|i_t=q_j,lambda)$。

好的,关键的地方来了,我们按照递推公式把他们写在一起:

$sum_{j=1}^{N}alpha_t(j)a_{ji}$
$=sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_i|lambda)P(i_{t+1}=q_i|i_t=q_j,lambda)$

下一步就是利用贝叶斯公式,将条件概率转换为联合概率,类似这样:$P(A,B)=P(A)P(B|A)$,那么,很显然:

$sum_{j=1}^{N}alpha_t(j)a_{ji}$
$=sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_j|lambda)P(i_{t+1}=q_i|i_t=q_j,lambda)$
$=sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_j,i_{t+1}=q_i|lambda)$

接下来怎么办,显然是一个联合概率到边缘概率的转换过程,说明白点就是经过$1$到$N$的求和之后,$i_t=q_j$这一块就被“边缘”了,就变成了:

$sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_j,i_{t+1}=q_i|lambda)$ $=P(o_1,o_2,o_3,…,o_t,i_{t+1}=q_i|lambda)$

还遥遥无期吗?说实话快了,最后一把,把$b_{io_{t+1}}$给结合上,$b_{io_{t+1}}$是观测输出概率,表示在时刻$i_{t+1}$,隐含状态为$q_i$时输出观测为$o_{t+1}$的概率,即:$b_{io_{t+1}}=P(o_{t+1}|i_{t+1}=q_i,lambda)$

最后我们把他加上,写成递推公式的完整形式:

$[sum_{j=1}^{N}alpha_t(j)a_{ji}]b_{io_{t+1}}=P(o_1,o_2,o_3,…,o_t,i_{t+1}=q_i|lambda)P(o_{t+1}|i_{t+1}=q_i,lambda)$,这又是一个条件概率到联合概率的转换过程:

$P(o_1,o_2,o_3,…,o_t,i_{t+1}=q_i|lambda)P(o_{t+1}|i_{t+1}=q_i,lambda)=P(o_1,o_2,o_3,…,o_{t+1},i_{t+1}=q_i|lambda)$

看看这是什么吧!$P(o_1,o_2,o_3,…,o_{t+1},i_{t+1}=q_i|lambda)$,不就是 $alpha_{t+1}(i)$吗?这样一来,$[sum_{j=1}^{N}alpha_t(j)a_{ji}]b_{io_{t+1}}=alpha_{t+1}(i)$就推导出来了。说实话,推出来挺激动的。

1.隐马尔科夫模型要研究什么

1.1.一个赌场的故事背景

在上一小节里,我们基本上把隐马尔科夫模型的运行机制和基本要素讲清楚了,那么他的关键研究要点是什么?或者说一般而言我们关注的研究问题聚焦在哪些方面呢?

我们不妨来看一个例子,这个例子可以更好的讲清楚我们为什么要研究这个模型,以及问题的关键点在哪。

这里我们举一个赌博的例子,大家应该都听说过用骰子猜大小的赌博游戏,掷出骰子,如果点数为$1,2,3$,则为小,如果点数为$4,5,6$,则为大。对于一个正常的骰子而言,掷出$1,2,3,4,5,6$的点数的概率都是相等的,即都为$frac{1}{6}$,因此大小的概率各半,可以说是听天由命了,这个结果对于赌客而言是公平的,纯凭运气。

但是如果掷骰子的人是一个老千呢?也就是说他手上的骰子是特制的,各个点数投掷出来的概率不再均等,那赌客的钱包可得遭殃了。

怎么讲?举个例子,老千手上有三个骰子,$1$号骰子是正常的,$2$号骰子和$3$号骰子都是特制的,他每次使用其中一个骰子进行投掷,并且不停的偷偷对这三个骰子进行切换使用,也就是说你不知道他使用的是哪个骰子,因此这对应的就是隐藏状态,而由骰子掷出的点数就是观测,这个很好理解。

那么由两个作弊的骰子掷出各个点数的概率,也就是输出概率如下图所示:
【概率图模型】S08E05 概率估计:隐马尔科夫模型观测序列描述

图1.作弊骰子的输出概率

同时,老千每次随机使用其中一个骰子,在三个骰子之间互相转换的过程符合马尔科夫性,因此这里还会包含有一个三个骰子之间相互切换的概率转移矩阵。

1.2.研究问题描述

基于上述背景,我们就来谈谈我们到底会去研究些什么。

第一个研究的内容是观测序列概率估计: 当我们知道老千切换三个骰子的转移概率矩阵以及各个骰子输出各个点数的概率的基础上,我们可以计算出任意一个观测序列出现的概率,比如老千连续掷出诡异的$8$个$6$,我们可以看看这种情况发生的概率有多大。

用隐马尔科夫模型的形式化语言概况就是:在给定隐马尔科夫模型三要素 $lambda=(A,B,pi)$ 的基础上,针对一个具体的观测序列$O=(o_1,o_2,…,o_T)$,求他出现的概率。

第二个研究的内容是隐含状态序列解码: 当我们知道老千切换三个骰子的转移概率以及各个骰子输出各个点数的概率时,我们可以通过已知的观测序列,也就是骰子的点数序列,来解码出老千所使用的骰子的序列,也就是隐状态序列。换句话说,就是可以推测出每一个掷出的点数背后,老千到底用的是哪一个骰子,可以判断他什么时候出千。

用隐马尔科夫模型的形式化语言概况就是:在给定隐马尔可夫模型三要素$lambda=(A,B,pi)$和观测序列$O=(o_1,o_2,…,o_T)$的基础上,求最有可能对应的隐藏状态序列$I=(i_1,i_2,…i_T)$。

那么具体该怎么做,我们接下来开始详细讲解,这一小节里我们首先介绍指定观测序列的概率估计问题:

即在已知隐马尔科夫模型$lambda=(A,B,pi)$的基础上,求指定观测序列$O=(o_1,o_2,…,o_T)$出现的概率,也就是我们上面一个例子中所说的,求扔出一串指定点数骰子的概率,那么用条件概率来表示我们的计算目标就是:求$P(O|lambda)$的概率。

2.一个直观的思路

首先来梳理一下这里面的思路,我们知道,对于同一个观测序列$O$而言,可以对应不同的隐含状态序列$I$,实际上所有的隐含状态序列$I$ 都能够以一定的概率生成这个观测序列$O$。

那么按这个思路,$P(O|lambda)$的求解过程就可以看作是通过对一系列不同$I$和指定对应$O$的联合概率进行求和,最终得到边缘概率的过程:$P(O|lambda)=sum_{I}P(O,I|lambda)$。

然后联合概率$P(O,I|lambda)$按照贝叶斯公式进行展开有:$P(O,I|lambda)=P(O|I,lambda)P(I|lambda)$,我们代入到原始公式中,就将目标式子转化成了:

$P(O|lambda)=sum_{I}P(O|I,lambda)P(I|lambda)$

这个概率怎么计算呢?对于任意一个隐含状态序列,我们设他的序列为:$I=(i_1,i_2,i_3,…,i_T)$,同时转移概率矩阵为$A$。那么首先利用马尔科夫链生成这个隐含状态:

$P(I|lambda)=pi_{i_1}a_{i_1i_2}a_{i_2i_3}a_{i_3i_4}…a_{i_{T-1}i_T}$

然后我们再接着求解概率$P(O|I,lambda)$,$P(O|I,lambda)$的本质就是利用这个已知的隐含状态序列$I=(i_1,i_2,i_3,…,i_T)$去生成指定的观测序列$O=(o_1,o_2,o_3,…,o_T)$,这里要运用一下输出概率矩阵$B$:

$P(O|I,lambda)=b_{i_1o_1}b_{i_2o_2}…b_{i_To_T}$

那么我们把他合并起来就有:

$P(O,I|lambda)=P(O|I,lambda)P(I|lambda)=pi_{i_1}b_{i_1o_1}a_{i_1i_2}b_{i_2o_2}a_{i_2i_3}b_{i_3o_3}…a_{i_{T-1}i_T}b_{i_To_T}$

这里补充一句,大家从$P(O,I|lambda)$和$P(O|I,lambda)$的表达式的不同,就能体会到这两个概率式子的不同含义。

3.直接计算的问题

看上去$P(O,I|lambda)=P(O|I,lambda)P(I|lambda)$的计算并不难,就是$2T$次乘法运算,但是请你注意,他的外面还有一个求和的$sum$运算,恐怖的地方在这,相当于要对每一个可能出现的隐含状态序列都进行$2T$次乘法运算,所有的隐含状态序列有多少个?序列长度为$T$,隐含状态集中有$N$个状态,那么所有的隐含状态序列的个数就是 $N^T$,整个运算复杂度就是$O(TN^T)$,这恐怕是不能接受的。

4.更优的方法:前向概率算法

4.1.算法推导证明

这里我们一般采取的是基于递推的前向概率算法,这个算法有一定的推导过程,在这个过程中我们本质上就是不断的在条件概率、联合概率和边缘概率之间做着转换,这也是一个很好的复习的过程。

我们先定义一个变量:$alpha_t(i)=P(o_1,o_2,…,o_t,i_t=q_i|lambda)$

那么,我们来看看这个和我们的目标计算概率$P(O|lambda)$也就是$P(o_1,o_2,…,o_T|lambda)$有什么联系?还是那个思路:利用联合概率求解边缘概率:

$P(o_1,o_2,…,o_T|lambda)=sum_{i=1}^{N}P(o_1,o_2,…,o_T,i_T=q_i|lambda)$,看看同学们啊,$P(o_1,o_2,…,o_T,i_T=q_i|lambda)$这个是什么?这个不就是$alpha_T(i)$吗?

于是整个目标概率就变成了:$P(o_1,o_2,…,o_T|lambda)=sum_{i=1}^{N}alpha_T(i)$,问题就来了,如何求 $alpha_T(i)$?

这里我先抛出一个递推公式:$alpha_{t+1}(i)=[sum_{j=1}^{N}alpha_t(j)a_{ji}]b_{io_{t+1}}$。

这个公式是一个神器,他的物理意义很直观,$alpha_t(j)=P(o_1,o_2,…,o_t,i_t=q_j|lambda)$所表达的是在时刻$t$,一方面已经形成观测序列$(o_1,o_2,…,o_t)$ ,另一方面此时隐状态是$i_t=q_j$,很明显的是,当$j$取$1$到$N$任意一个值的时候,都可以通过转移概率在$t+1$时刻转移到$i_{t+1}=q_i$,因此合并所有$alpha_{t}(j)a_{ji}$之后,再在$i_{t+1}=q_i$的隐状态上输出$o_{t+1}$,就得到了$alpha_{t+1}(i)$。

这是从内涵意义层面进行的推导,如果我们下面来证明一下这个式子的成立,我们就能放心大胆的从$alpha_1(i)$一步一步的递推到$alpha_T(i)$。

那么怎么证明这个递推关系成立呢?按道理来说,其实大家都不喜欢看大篇幅的公式证明,但是这里确实是不可避免的,必须要真刀真枪的把问题说清楚,不过呢我来个庖丁解牛,一定要大家轻轻松松搞明白。

在推导之前,我还是要再强调一下:抓住两个关键点,所有的推导都是建立在其上的:

一个是联合概率到边缘概率的转换关系;
一个是条件概率到联合概率的转换关系,也就是贝叶斯公式;

让我们开始,首先拿出定义:$alpha_t(i)=P(o_1,o_2,o_3,…,o_t,i_t=q_i|lambda)$

然后看$a_{ji}$,这个再熟悉不过了,隐含状态从$t$时刻的状态$j$转移到$t+1$时刻的状态$i$的概率,写成条件概率就是:$a_{ji}=P(i_{t+1}=q_i|i_t=q_j,lambda)$。

好的,关键的地方来了,我们按照递推公式把他们写在一起:

$sum_{j=1}^{N}alpha_t(j)a_{ji}$
$=sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_i|lambda)P(i_{t+1}=q_i|i_t=q_j,lambda)$

下一步就是利用贝叶斯公式,将条件概率转换为联合概率,类似这样:$P(A,B)=P(A)P(B|A)$,那么,很显然:

$sum_{j=1}^{N}alpha_t(j)a_{ji}$
$=sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_j|lambda)P(i_{t+1}=q_i|i_t=q_j,lambda)$
$=sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_j,i_{t+1}=q_i|lambda)$

接下来怎么办,显然是一个联合概率到边缘概率的转换过程,说明白点就是经过$1$到$N$的求和之后,$i_t=q_j$这一块就被“边缘”了,就变成了:

$sum_{j=1}^{N}P(o_1,o_2,o_3,…,o_t,i_t=q_j,i_{t+1}=q_i|lambda)$ $=P(o_1,o_2,o_3,…,o_t,i_{t+1}=q_i|lambda)$

还遥遥无期吗?说实话快了,最后一把,把$b_{io_{t+1}}$给结合上,$b_{io_{t+1}}$是观测输出概率,表示在时刻$i_{t+1}$,隐含状态为$q_i$时输出观测为$o_{t+1}$的概率,即:$b_{io_{t+1}}=P(o_{t+1}|i_{t+1}=q_i,lambda)$

最后我们把他加上,写成递推公式的完整形式:

$[sum_{j=1}^{N}alpha_t(j)a_{ji}]b_{io_{t+1}}=P(o_1,o_2,o_3,…,o_t,i_{t+1}=q_i|lambda)P(o_{t+1}|i_{t+1}=q_i,lambda)$,这又是一个条件概率到联合概率的转换过程:

$P(o_1,o_2,o_3,…,o_t,i_{t+1}=q_i|lambda)P(o_{t+1}|i_{t+1}=q_i,lambda)=P(o_1,o_2,o_3,…,o_{t+1},i_{t+1}=q_i|lambda)$

看看这是什么吧!$P(o_1,o_2,o_3,…,o_{t+1},i_{t+1}=q_i|lambda)$,不就是 $alpha_{t+1}(i)$吗?这样一来,$[sum_{j=1}^{N}alpha_t(j)a_{ji}]b_{io_{t+1}}=alpha_{t+1}(i)$就推导出来了。说实话,推出来挺激动的。

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 【概率图模型】S08E05 概率估计:隐马尔科夫模型观测序列描述求职学习资料
分享到: 更多 (0)
D0b2wT.gif

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们