每日一句: Build your own dreams, or someone else will hire you to build theirs. 打造自己的梦想,否则你就会被雇用去打造别人的梦想。 跟读

汉语站

2018年1月24日 星期三

丁酉(鸡)年十二月初八

(图)马尔可夫链模型
马尔可夫链模型
马尔可夫模型(HiddenMarkovModel,HMM)是统计模型,它用来描述一个含有隐含未知参数马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。在正常的马尔可夫模型中,状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中,状态并不是直接可见的,但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。

马尔可夫链模型 - 随机过程 [回目录]

马尔可夫链,因安德烈·马尔可夫(A.A.Markov,1856-1922)得名,是数学中具有马尔可夫性质的离散时间随机过程。该过程中,在给定当前知识或信息的情况下,过去(即当期以前的历史状态)对于猜测将来(即当期以后的未来状态)是无关的。马尔可夫链是满足下面两个假设的一种随机过程:

1、t+l时刻系统状态概率分布只与t时刻的状态有关,与t时刻以前的状态无关;

2、从t时刻到t+l时刻的状态转移与t的值无关。一个马尔可夫链模型可表示为=(S,P,Q),其中各元的含义如下:

1)S是系统所有可能的状态所组成的非空的状态集,有时也称之为系统的状态空间,它可以是有限的、可列的集合或任意非空集。本文中假定S是可数集(即有限或可列)。用小写字母i,j(或Si,Sj)等来表示状态。

2)是系统的状态转移概率矩阵,其中Pij表示系统在时刻t处于状态i,在下一时刻t+l处于状态i的概率,N是系统所有可能的状态的个数。对于任意i∈s,有。

3)是系统的初始概率分布,qi是系统在初始时刻处于状态i的概率,满足。

马尔可夫链模型 - 隐含马尔可夫模型 [回目录]

马尔可夫链模型(图)隐含马尔可夫模型
隐含马尔可夫模型
隐含马尔可夫模型是一个数学模型,到目前为之,它一直被认为是实现快速精确的语音识别系统的最成功的方法。复杂的语音识别问题通过隐含马尔可夫模型能非常简单地被表述、解决,让人们不由由衷地感叹数学模型之妙。

自然语言是人类交流信息的工具。很多自然语言处理问题都可以等同于通信系统中的解码问题--一个人根据接收到的信息,去猜测发话人要表达的意思。这其实就象通信中,人们根据接收端收到的信号去分析、理解、还原发送端传送过来的信息。右图就表示了一个典型的通信系统:其中s1,s2,s3...表示信息源发出的信号。o1,o2,o3...是接受器接收到的信号。通信中的解码就是根据接收到的信号o1,o2,o3...还原出发送的信号s1,s2,s3...。

其实人们平时在说话时,脑子就是一个信息源。人们的喉咙(声带),空气,就是如电线光缆般的信道。听众耳朵的就是接收端,而听到的声音就是传送过来的信号。根据声学信号来推测说话者的意思,就是语音识别。这样说来,如果接收端是一台计算机而不是人的话,那么计算机要做的就是语音的自动识别。同样,在计算机中,如果我们要根据接收到的英语信息,推测说话者的汉语意思,就是机器翻译;如果我们要根据带有拼写错误的语句推测说话者想表达的正确意思,那就是自动纠错。

那么怎么根据接收到的信息来推测说话者想表达的意思呢?人们可以利用叫做“隐含马尔可夫模型”(HiddenMarkovModel)来解决这些问题。以语音识别为例,当我们观测到语音信号o1,o2,o3时,要根据这组信号推测出发送的句子s1,s2,s3。显然,人们应该在所有可能的句子中找最有可能性的一个。用数学语言来描述,就是在已知o1,o2,o3,...的情况下,求使得条件概率
P(s1,s2,s3,...|o1,o2,o3....)达到最大值的那个句子s1,s2,s3,...

当然,上面的概率不容易直接求出,于是人们可以间接地计算它。利用贝叶斯公式并且省掉一个常数项,可以把上述公式等价变换成

P(o1,o2,o3,...|s1,s2,s3....)*P(s1,s2,s3,...)
其中
P(o1,o2,o3,...|s1,s2,s3....)表示某句话s1,s2,s3...被读成o1,o2,o3,...的可能性,而
P(s1,s2,s3,...)表示字串s1,s2,s3,...本身能够成为一个合乎情理的句子的可能性,所以这个公式的意义是用发送信号为s1,s2,s3...这个数列的可能性乘以s1,s2,s3...本身可以一个句子的可能性,得出概率。

(读者读到这里也许会问,你现在是不是把问题变得更复杂了,因为公式越写越长了。别着急,现在就来简化这个问题。)人们们在这里做两个假设:

第一,s1,s2,s3,...是一个马尔可夫链,也就是说,si只由si-1决定(详见系列一);
第二,第i时刻的接收信号oi只由发送信号si决定(又称为独立输出假设,即P(o1,o2,o3,...|s1,s2,s3....)=P(o1|s1)*P(o2|s2)*P(o3|s3)...。
那么人们就可以很容易利用算法Viterbi找出上面式子的最大值,进而找出要识别的句子s1,s2,s3,...。

满足上述两个假设的模型就叫隐含马尔可夫模型。我们之所以用“隐含”这个词,是因为状态s1,s2,s3,...是无法直接观测到的。

隐含马尔可夫模型的应用远不只在语音识别中。在上面的公式中,如果我们把s1,s2,s3,...当成中文,把o1,o2,o3,...当成对应的英文,那么人们就能利用这个模型解决机器翻译问题;如果我们把o1,o2,o3,...当成扫描文字得到的图像特征,就能利用这个模型解决印刷体和手写体的识别。

P(o1,o2,o3,...|s1,s2,s3....)根据应用的不同而又不同的名称,在语音识别中它被称为“声学模型”(AcousticModel),在机器翻译中是“翻译模型”(TranslationModel)而在拼写校正中是“纠错模型”(CorrectionModel)。而P(s1,s2,s3,...)就是我们在系列一中提到的语言模型。

在利用隐含马尔可夫模型解决语言处理问题前,先要进行模型的训练。常用的训练方法由伯姆(Baum)在60年代提出的,并以他的名字命名。隐含马尔可夫模型在处理语言问题早期的成功应用是语音识别。七十年代,当时IBM的FredJelinek(贾里尼克)和卡内基·梅隆大学的JimandJanetBaker(贝克夫妇,李开复的师兄师姐)分别独立地提出用隐含马尔可夫模型来识别语音,语音识别的错误率相比人工智能和模式匹配等方法降低了三倍(从30%到10%)。八十年代李开复博士坚持采用隐含马尔可夫模型的框架,成功地开发了世界上第一个大词汇量连续语音识别系统Sphinx。

马尔可夫链模型 - 演变 [回目录]

(图)马尔可夫链模型
马尔可夫链模型

上边的图示强调了HMM的状态变迁。有时,明确的表示出模型的演化也是有用的,人们用x(t1)与x(t2)来表达不同时刻t1和t2的状态。在这个图中,每一个时间块(x(t),y(t))都可以向前或向后延伸。通常,时间的起点被设置为t=0或t=1.

马尔可夫链模型 - 应用 [回目录]

HMM有三个经典(canonical)问题:

已知模型参数,计算某一特定输出序列的概率,通常使用forward算法解决;
已知模型参数,寻找最可能的能产生某一特定输出序列的隐含状态的序列,通常使用Viterbi算法解决;
已知输出序列,寻找最可能的状态转移以及输出概率,通常使用Baum-Welch算法以及ReversedViterbi算法解决;另外,最近的一些方法使用Junctiontree算法来解决这三个问题。

具体实例
假设你有一个住得很远的朋友,他每天跟你打电话告诉你他那天作了什么。你的朋友仅仅对三种活动感兴趣:公园散步,购物以及清理房间,他选择做什么事情只凭天气,你对于他所住的地方的天气情况并不了解,但是你知道总的趋势。在他告诉你每天所做的事情基础上,你想要猜测他所在地的天气情况。

你认为天气的运行就像一个马尔可夫链,其有两个状态“雨”和“晴”,但是你无法直接观察它们,也就是说,它们对于你是隐藏的,每天,你的朋友有一定的概率进行下列活动:“散步”,“购物”或“清理”。因为你朋友告诉你他的活动,所以这些活动就是你的观察数据。这整个系统就是一个隐马尔可夫模型HMM。

你知道这个地区的总的天气趋势,并且平时知道你朋友会做的事情,也就是说这个隐马尔可夫模型的参数是已知的。你可以用程序语言(Python)写下来:在这些代码中,start_probability代表了你对于你朋友第一次给你打电话时的天气情况的不确定性(你知道的只是那个地方平均起来下雨多些)。在这里,这个特定的概率分布并非平衡的,平衡概率应该接近(在给定变迁概率的情况下){'Rainy':0.571,'Sunny':0.429}天气变迁,在这个例子中,如果今天下雨,那么明天天晴的概率只有30%。代码emission_probability表示了你朋友每天作某件事的概率.如果下雨,有50%的概率他在清理房间;如果天晴,则有60%的概率他在外头散步。

这个例子在Viterbi算法页上有更多的解释。

马尔可夫链模型 - 应用 [回目录]

语音识别或光学字符识别
机器翻译
生物信息学和基因组学
基因组序列中蛋白质编码区域的预测
对于相互关联的DNA或蛋白质族的建模
从基本结构中预测第二结构元素

马尔可夫链模型 - 历史 [回目录]

马尔可夫模型最初是在二十世纪六十年代后半期LeonardE.Baum和其它一些作者在一系列的统计学论文中描述的。HMM最初的应用之一是开始于二十世纪七十年代中期的语音识别。在二十世纪八十年代后半期,HMM开始应用到生物序列尤其是DNA的分析中。从那时开始,在生物信息学领域它们已经变得无处不在。

词条内容仅供参考,如果您需要解决具体问题
(尤其在法律、医学等领域),建议您咨询相关领域专业人士。

标签: 马尔可夫链模型

同义词: 暂无同义词

词条统计

浏览次数 : 2224 次

编辑次数 : 1 次 历史版本

更新时间 : 2009-04-27

双语连环画