资源描述：
《计算语言学讲义(05)词法分析(三)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、计算语言学第5讲词法分析（三）刘群中国科学院计算技术研究所liuqun@ict.ac.cn中国科学院研究生院2011年春季课程讲义内容提要计算语言学讲义(05)词法分析(三)2隐马尔科夫模型－假设对于一个随机事件，有一个观察值序列：O,...,O1T该事件隐含着一个状态序列：X,...,X1T假设1：马尔可夫假设（状态构成一阶马尔可夫链）p(X
2、X…X)=p(X
3、X)ii-11ii-1假设2：不动性假设（状态与具体时间无关）p(X
4、X)=p(X
5、X)，对任意i,j成立i+1ij+1j假设3：输出独立性假设（输出仅
6、与当前状态有关）p(O,...,O
7、X,...,X)=Πp(O
8、X)1T1Ttt计算语言学讲义(05)词法分析(三)3隐马尔科夫模型－图示XX…………X12T…………OOO12T状态转移观察值输出计算语言学讲义(05)词法分析(三)4隐马尔科夫模型－定义一个隐马尔可夫模型(HMM)是一个五元组：(Ω,Ω,A,B,π)XO其中：Ω={q,...q}：状态的有限集合X1NΩ={v,...,v}：观察值的有限集合O1MA={a}，a=p(X=q
9、X=q)：转移概率ijijt+1jtiB={b}，b=p(O=v
10、X=q)
11、：输出概率ikiktktiπ={π}，π=p(X=q)：初始状态分布ii1i计算语言学讲义(05)词法分析(三)5隐马尔科夫模型－问题令λ={A,B,π}为给定HMM的参数，令σ=O,...,O为观察值序列，1T隐马尔可夫模型（HMM）的三个基本问题：1.评估问题：对于给定模型，求某个观察值序列的概率p(σ
12、λ)；（语言模型）2.解码问题：对于给定模型和观察值序列，求可能性最大的状态序列；3.学习问题：对于给定的一个观察值序列，调整参数λ，使得观察值出现的概率p(σ
13、λ)最大。计算语言学讲义(05)词法分析(三)
14、6隐马尔科夫模型－算法•评估问题：向前算法–定义向前变量–采用动态规划算法，复杂度O(N2T)•解码问题：韦特比（Viterbi）算法–采用动态规划算法，复杂度O(N2T)•学习问题：向前向后算法–EM算法计算语言学讲义(05)词法分析(三)7隐马尔科夫模型－例子•假设：某一时刻只有一种疾病，且只依赖于上一时刻疾病一种疾病只有一种症状，且只依赖于当时的疾病•症状(观察值)：发烧，咳嗽，咽喉肿痛，流涕•疾病(状态值)：感冒，肺炎，扁桃体炎•转移概率：从一种疾病转变到另一种疾病的概率•输出概率：某一疾病呈现出某一症状
15、的概率•初始分布：初始疾病的概率•解码问题：某人症状为：咳嗽→咽喉痛→流涕→发烧请问：其疾病转化的最大可能性如何？计算语言学讲义(05)词法分析(三)8隐马尔科夫模型－例子（续）•转移概率感冒肺炎扁桃体炎感冒0.40.30.3肺炎0.20.60.2扁桃体炎0.10.10.8•输出概率发烧咳嗽咽喉痛流涕感冒0.40.30.10.2肺炎0.30.50.10.1扁桃体炎0.20.10.60.1•初始分布感冒肺炎扁桃体炎0.50.20.3计算语言学讲义(05)词法分析(三)9HMM评估问题评估问题：对于给定模型，求某个观
16、察值序列的概率p(σ
17、λ)；（语言模型）P(O∣λ)=∑P(O,X∣λ)X=∑P(X∣λ)P(O∣X,λ)XTT=∑(πX1∏aXi−1Xi)(∏bXiOi)Xi=2i=1T=∑(πX1bX1O1∏aXi−1XibXiOi)Xi=2可能的状态序列有NT种可能性，计算复杂度极高计算语言学讲义(05)词法分析(三)10HMM评估问题所有可能的状态值序列：qq0N+1观察值：OOO123计算语言学讲义(05)词法分析(三)11HMM评估问题所有可能所有路径的状态值概率之和序列：qq0N+1观察值：OOO123可能的状态
18、序列有NT种计算语言学讲义(05)词法分析(三)12HMM评估问题－向前算法(1)定义前向变量为HMM在时间t输出序列O…1O，并且位于状态X的概率：ttα(i)=P(O...O,X=q∣λ)t1tti初始化：α(i)=πb1iiO1N迭代公式为：αt+1(j)=[∑αt(i)aij]bjOt+1i=1N最终结果为：P(O∣λ)=∑αT(i)i=1计算语言学讲义(05)词法分析(三)13HMM评估问题－向前算法(2)α(1)q1ta1jaq2jα(2)2qα(j)tjt＋1anj……qα(n)nt时间t时间t+1
19、向前算法的时间复杂度：O(N2T)计算语言学讲义(05)词法分析(三)14HMM评估问题－向前算法(3)•ForwardAlgorithm–Assignp(source_state)=1–Foreachobservationofromsourcetodestination•Foreachpossiblestatenofobservationo–p(n)=0,previou
