马尔可夫链 Markov Chain
目录

1. 一个例子

吴军在数学之美系列中用统计语言模型举了使用马尔可夫链的一个例子,用于找出句子S出现的概率,如下:

如果 S 表示一连串特定顺序排列的词 w1, w2,…, wn ,换句话说,S 可以表示某一个由一连串特定顺序排练的词而组成的一个有意义的句子。现在,机器对语言的识别从某种角度来说,就是想知道S在文本中出现的可能性,也就是数学上所说的S 的概率用 P(S) 来表示。利用条件概率的公式,S 这个序列出现的概率等于每一个词出现的概率相乘,于是P(S) 可展开为:

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

其中 P (w1) 表示第一个词w1 出现的概率;P (w2|w1) 是在已知第一个词的前提下,第二个词出现的概率;以次类推。不难看出,到了词wn,它的出现概率取决于它前面所有词。从计算上来看,各种可能性太多,无法实现。因此我们假定任意一个词wi的出现概率只同它前面的词 wi-1 有关(即马尔可夫假设),于是问题就变得很简单了。现在,S 出现的概率就变为:

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

(当然,也可以假设一个词又前面N-1个词决定,模型稍微复杂些。)

接下来的问题就是如何估计 P (wi|wi-1)。现在有了大量机读文本后,这个问题变得很简单,只要数一数这对词(wi-1,wi) 在统计的文本中出现了多少次,以及 wi-1 本身在同样的文本中前后相邻出现了多少次,然后用两个数一除就可以了,P(wi|wi-1) = P(wi-1,wi)/ P (wi-1)。

2. 马尔可夫性质

当一个随机过程在给定现在状态及所有过去状态情况下,其未来状态的条件概率分布仅依赖于当前状态; 换句话说,在给定现在状态时,未来状态与过去状态(即该过程的历史路径)是条件独立的,那么此随机过程即具有马尔可夫性质。 具有马尔可夫性质的过程通常称之为马尔可夫过程。

简单的说,马尔可夫性质就是说未来状态只和当前状态有关。

3. 马尔可夫链

马尔可夫链(markov charin)是数学中具有马尔可夫性质的离散时间随机过程

参考

发表评论