计算语言学第5讲词法分析（三）刘群中国科学院计算技术研究所liuqun@ict.ac.cn中国科学院研究生院2012年春季课程讲义内容提要计算语言学讲义(05)词法分析(三)2隐马尔科夫模型－图示…………X1X2XT…………O1O2OT状态转移观察值输出计算语言学讲义(05)词法分析(三)3隐马尔科夫模型－假设对于一个随机事件，有一个观察值序列：O1,...,OT该事件隐含着一个状态序列：X1,...,XT假设1：马尔可夫假设（状态构成一阶马尔可夫链）p(Xi|Xi-1…X1)=p(Xi|Xi-1)假设2：不动性假设（状态与具体时间无关），对任意成立p(Xi+1|Xi)=p(Xj+1|Xj)i,j假设3：输出独立性假设（输出仅与当前状态有关）p(O1,...,OT|X1,...,XT)=Πp(Ot|Xt)计算语言学讲义(05)词法分析(三)4隐马尔科夫模型－定义一个隐马尔可夫模型(HMM)是一个五元组：(ΩX,ΩO,A,B,π)其中：：状态的有限集合ΩX={q1,...qN}：观察值的有限集合ΩO={v1,...,vM}，：转移概率A={aij}aij=p(Xt+1=qj|Xt=qi)，：输出概率B={bik}bik=p(Ot=vk|Xt=qi)，：初始状态分布π={πi}πi=p(X1=qi)计算语言学讲义(05)词法分析(三)5隐马尔科夫模型－例子•假设：某一时刻只有一种疾病，且只依赖于上一时刻疾病一种疾病只有一种症状，且只依赖于当时的疾病•症状(观察值)：发烧，咳嗽，咽喉肿痛，流涕•疾病(状态值)：感冒，肺炎，扁桃体炎•转移概率：从一种疾病转变到另一种疾病的概率•输出概率：某一疾病呈现出某一症状的概率•初始分布：初始疾病的概率•解码问题：某人症状为：咳嗽→咽喉痛→流涕→发烧请问：其疾病转化的最大可能性如何？计算语言学讲义(05)词法分析(三)6隐马尔科夫模型－例子（续）•转移概率感冒肺炎扁桃体炎感冒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)词法分析(三)7隐马尔科夫模型－问题令λ={A,B,π}为给定HMM的参数，令为观察值序列，σ=O1,...,OT隐马尔可夫模型（HMM）的三个基本问题：1.评估问题：对于给定模型，求某个观察值序列的概率p(σ|λ)；（语言模型）2.解码问题：对于给定模型和观察值序列，求可能性最大的状态序列；3.学习问题：对于给定的一个观察值序列，调整参数λ，使得观察值出现的概率p(σ|λ)最大。计算语言学讲义(05)词法分析(三)8隐马尔科夫模型－算法•评估问题：向前算法–定义向前变量–采用动态规划算法，复杂度O(N2T)•解码问题：韦特比（Viterbi）算法–采用动态规划算法，复杂度O(N2T)•学习问题：向前向后算法–EM算法计算语言学讲义(05)词法分析(三)9HMM评估问题评估问题：对于给定模型，求某个观察值序列的概率p(σ|λ)；（语言模型）P(O∣λ)=∑P(O,X∣λ)X=∑P(X∣λ)P(O∣X,λ)XTT=∑(π∏a)(∏b)X1Xi−1XiXiOiXi=2i=1T=∑(πb∏ab)X1X1O1Xi−1XiXiOiXi=2可能的状态序列有NT种可能性，计算复杂度极高计算语言学讲义(05)词法分析(三)10HMM评估问题所有可能的状态值序列：q0qN+1观察值：O1O2O3计算语言学讲义(05)词法分析(三)11HMM评估问题所有可能所有路径的状态值概率之和序列：q0qN+1观察值：O1O2O3可能的状态序列有NT种计算语言学讲义(05)词法分析(三)12HMM评估问题－向前算法(1)定义前向变量为在时间输出序列HMMtO1…，并且位于状态的概率：OtXtα()=(=∣λ)tiPO1...Ot,Xtqi初始化：α(i)=πb1iiO1Nα()=[∑α()]迭代公式为：+jiabt1tijjOt+1i=1N最终结果为：(∣λ)=∑α()POTii=1计算语言学讲义(05)词法分析(三)13HMM评估问题－向前算法(2)α(1)q1ta1jaq2jαt(2)2qjαt＋1(j