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

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

我是学理科出身的程序员，一直做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 暮夏阅读( ...) 评论( ...) 编辑收藏