隐性马尔科夫链

隐性马尔科夫链隐性马尔可夫链

我是学理科出身的程序员,一直做web,复杂的算法基本上很少用到。最近做了一个自然语言处理相关的项目,我把我的一些理解和大家分享一下。

1.首先来说一下马尔科夫链。

一个事件序列发生的概率可以用下面的概率论里面的乘法公式展开

P(w1,w2,…wn) = P(w1)P(w2|w1)P(w3| w1 w2)…P(wn|w1 w2…wn-1)

乘法公式的证明非常有意思,它本身就是一个递推的过程,

根据条件概率的定义:P(A|B) = P(AB)/ P(B)
那么 P(AB) = P(A|B) X P(B),由此可得:
P(w1,w2,…wn) = P(w1,w2,…wn-1) X P(wn|w1 w2…wn-1)
一路往下递推就能得到乘法公式的结果了。

假定任意一个事件wi的出现概率只同它前面的事件wi-1 有关(即一阶马尔可夫假设,多阶的情况这里不讨论)。那么上面那个乘法公式就变成下面的公式了:

P(w1,w2,…wn) = P(w1)P(w2|w1)P(w3|w2)…P(wi|wi-1)…

这个模型非常的简单,但是用处的确很大。举个例子,比如说要进行分词,我们用马尔科夫链来理解这个,假设句子中词的构成只和上一个词相关,那么这就是一个马尔可夫链,分词问题变成,要寻找一个划分 w1,w2,..wn使得 max(P(w1,w2,…wn)) 成立。一般来说 P(w2|w1) 比较小,要是 几千个这样小的数相乘的话,就会变成一个很小的数,在数学里面可以在等式两边加个 log,这样就得到
W = Log(P(w1,w2,…wn)) = P(w1)+P(w2|w1)+P(w3|w2)+…+P(wi|wi-1)+…现在求max (w) 就方便多了。

当然,接下来的工作还是有一定的难度,但是分词的基本的思想就是这样的。

2.隐性马尔可夫链。
隐性马尔可夫链要复杂一点,基本的问题是这样的:
有两个序列,一个序列是原因,一个序列是结果。现在,我们已经知道了结果,问,这个序列的原因是什么?如果对概率论比较熟悉,你肯定知道,由结果推导原因就是 是个贝叶斯推断问题。的确,隐性马尔可夫链 就是源于这样的一个问题,当然它也有很多其他的用途。比如,分词里面一个词的词性的标记问题。已知的是一个词序列,要求这个序列每个词隐含的词性。
用数学公式表示就是这样的:
P (h(t1),h(t2),h(t3),...|o(t1),o(t2),o(t3)....), o 表示 observed(结果,你可以观察到的) , h 表示 hidden states(原因,你不能观察到的,或者说是隐性的),t1, t2, t3 表示你观察的时间。注意,o(t1),o(t2),o(t3).... 是已经确定的。因此 P(o(t1),o(t2),o(t3)....) 是一个常数。对 P (h(t1),h(t2),h(t3),...|o(t1),o(t2),o(t3)....) 用贝叶斯公式展开,
我们可以得到
P(h(t1),h(t2),h(t3),...|o(t1),o(t2),o(t3)....) = P(h(t1),h(t2),h(t3)……) X P (o(t1),o(t2),o(t3)....|(h(t1),h(t2),h(t3),...) / P(o(t1),o(t2),o(t3)……)

其中 P(o(t1),o(t2),o(t3)……) 是一个常数,我们的目的是找原因,所以,我们要求概率最大的 P(h(t1),h(t2),h(t3),...|o(t1),o(t2),o(t3)....) ,因此常数可以忽略。

我们做下面的两个假设:
第一,h(t1),h(t2),h(t3),... 是一个马尔可夫链,也就是说,h(i) 只由 h(i-1) 决定。
第二,第 i 时刻的观察值 oi 只由第i时刻的原因 h(i) 决定(又称为独立输出假设, 即 P(o(t1),o(t2),o(t3)....| h(t1),h(t2),h(t3)....)
= P(o(t1)|h(t1)) X P(o(t2)|h(t2)) X P(o(t3)|h(t3))...。

这样问题就简单多了:
HHM = P(h(t1),h(t2),h(t3),...|o(t1),o(t2),o(t3)....)
= P(h(t1)) X P(h(t2)|h(t1))… XP(o(t1)|h(t1)) X P(o(t2)|h(t2)) X P(o(t3)|h(t3))...。

求Max HHM。

求解这个公式,最出名的一个算法就是 Viterbi 算法,在说这个算法之前,我们要强调的是 求 Max(HHM). 为了更好的理解上面的模型,我们举个HMM的例子。

周文王被关在 天牢里面,永不见天日。但是呢,他能说出外面是晴,还是下雨。这是怎么回事呢?根据以前的经验,房子里面的潮湿程度 和 外面的天气有一定的关系。


Dry
Dryish
Damp
Soggy
Sun
0.6
0.2
0.15
0.05
Cloud
0.25
0.25
0.25
0.25
Rain
0.05
0.1
0.35
0.50
(表示 P(o(ti)|h(ti)) 的所有情况)

我们还知道,天气之间的转移矩阵如下:

Sun
Cloud
Rain
Sun
0.5
0.375
0.125
Cloud
0.25
0.125
0.625
Rain
0.25
0.375
0.375
(表示:P(h(ti)|h(ti-1)) 的所有情况)

现在某几天他观察到 房子里面的干燥程度是这样的:
Dry Dryish Damp 问,这几天 天气最有可能的情况是什么?
也就是说要求:
HHM= P(h(t1),h(t2),h(t3)| Dry Dryish Damp) , 求 h(t1),h(t2),h(t3)的一个组合,使得 HHM最大。
当然,你肯定想到了,用枚举法就可以了。当然,这个是一个 指数级的 复杂度,很简单的就可以证明 复杂度为 N^N.

下面我简单说下用 Viterbi 算法求解的思路。它的基本思路就是递归。和我们前面证明乘法公式的算法一样,求t3 可以 先求 t2, 求 t2 可以先求 t1, t1 当然十分的好求解了,就是
【隐性马尔科夫链】Max(P(h(t1) | Dry)),h(t1) 只有三种情况,[sun,cloud,rain].然后再反推回去。所以关键就是推导这个递推公式了。关于这个递推公式的推导就留给大家自己去做了,相信,你也能够自己发现 Viterbi 算法,不用看书上枯燥的算法描述。要注意的是,t2 的最优解,不一定是 t3的最优解。
posted @ 2009-07-14 20:50 暮夏 阅读( ...) 评论( ...) 编辑 收藏

    推荐阅读