第六章 马尔可夫模型.ppt

马尔可夫模型,,马尔可夫模型,马尔可夫模型是一种统计模型,广泛地应用在语音识别，词性自动标注，音字转换，概率文法等各个自然语言处理的应用领域马尔可夫(1856～1922)，苏联数学家切比雪夫的学生在概率论、数论、函数逼近论和微分方程等方面卓有成就经过长期发展，尤其是在语音识别中的成功应用，使它成为一种通用的统计工具马尔可夫模型的典型应用,语音识别音字转换词性标注,回顾:n-gram语言模型,链规则：N-gram语言模型:N-1阶马尔可夫过程（链）仅适用一种概率分布进行统计推导，例如在trigram模型中，,马尔可夫假设（特征）,设 X=(X1, .., Xt)是随机变量序列，其中每个随机变量的取值 在有限集 S={s1, …, sn}, S称为状态空间, 马尔可夫特征是：有限历史假设（Limited (Horizon，Context,History）): P(Xt+1=sk|X1, .., Xt)=P(X t+1 = sk |Xt) 时间不变性假设（Time Invariant）（马尔可夫过程的稳定性假设）:这种条件依赖，不随时间的改变而改变如果X具有这些特征，那么这个随机变量序列称为一个马尔可夫过程（链）,N阶马尔可夫模型,Trigram的情形：只需修改状态空间的定义定义新的变量 使得并且约定：,马尔可夫模型的形式化表示,一个马尔可夫模型是一个三元组(S, , A)其中 S是状态的集合，是初始状态的概率, A是状态间的转移概率。

马尔可夫模型的图形表示,状态集合分布由状态i到状态j之间的转移弧上有一个条件转移概率:,隐马尔可夫模型(HMM),各个状态（或者状态转移弧）都有一个输出,但是状态是不可见的最简单的情形:不同的状态只能有不同的输出,隐马尔可夫模型,增加一点灵活性：不同的状态，可以输出相同的输出：,隐马尔可夫模型,再增加一点灵活性：输出在状态转移中进行隐马尔可夫模型,最大的灵活性：在状态转移中以特定的概率分布输出,HMM的形式化定义,HMM是一个五元组 (S, K, , A, B) ，其中 S是状态的集合，K是输出字符的集合， 是初始状态的概率，A是状态转移的概率B是状态转移时输出字符的概率马尔可夫过程程序,t:= 1;以概率i在状态 si 开始 (i.e., X1=i)Forever do Move from state si to state sj with probability aij (i.e., Xt+1 = j)Emit observation symbol ot = k with probability bijkt:= t+1End,隐马尔科夫模型的三个基本问题,给定一个模型 ，如何高效地计算某一输出字符序列的概率给定一个输出字符序列O，和一个模型 ，如何确定产生这一序列概率最大的状态序列给定一个输出字符的序列O，如何调整模型的参数使得产生这一序列的概率最大,网格（Trellis）,,问题1评价（Evaluation）,给定一个模型 ，如何高效地计算某一输出字符序列的概率,,,,,,,,,o1,ot,ot-1,ot+1,方案1,,,方案1（Cont.）,,,算法复杂度太高，需要,,方案2向前过程（forward procedure）,使用动态规划方法实现更加高效的算法动机：对于任意一个长度为t+1的状态序列来说，其前t个输出字符出现的概率是相同的定义:向前变量,方案2向前过程（forward procedure）cont.,,方案2向前过程（forward procedure）cont.,向前过程算法,1、初始化2、推导3、总合,向前过程例,,问题2 解码（decoding）,给定一个输出字符序列O，和一个模型 ，如何确定产生这一序列概率最大的状态序列,问题2 解码（decoding）cont.,,,,在t时刻到达状态j，输出字符Ot时，输出前面t-1个字符的最可能路径的概率,,Viterbi algorithm,初始化递归结束得到最优路径,,,,,1,2,3,states,Viterbi算法例,,,,,,,,,,问题3 参数估计,已知输出字符序列，找到产生该序列可能性最大的模型无法用分析方法求解给定一个模型和输出字符序列，任意设定初始参数值，通过不断循环更新参数的方法，设法达到最优Baum 1970,基本思想,1. 设定模型的初始值, μold.2. 基于μold ，计算输出O 的概率3. 如果 P(O|μnew)-P(O| μold) < 某个设定的阈值 (或者达到某个固定的循环次数), 停止.4. 否则, μold ← μnew 返回步骤 2.,Baum-Welch算法,,,,A,B,A,A,A,B,B,B,B,状态转移弧Si->Sj的转移概率,,,处于状态Si的概率,Baum-Welch算法（cont.）,Baum-Welch (cont.),,,,,A,B,A,A,A,B,B,B,B,,Now we can compute the new estimates of the model parameters.,,Baum-Welch (cont.),又称为向前向后算法（Forward-backward algorithm） Baum 等人证明了经常得到局部最优解-爬山法的固有缺点一种通用机器学习算法-期望最大值（Expectation Maximum Algorithm）算法的特殊形式一种无指导的机器学习算法，效果较有指导为差。

基于HMM的词性标注,词性标注（Part-of-Speech tagging）回顾：作用：句法分析的前期步骤难点：兼类词基于规则的词性标注基于转换的错误驱动的词性标注基于HMM的词性标注,基于HMM的词性标注,问题的形式化设词性标记为M个标记集合: {t_1,..,t_M}.词表中词的个数为 V 词集合: {w_1,..,w_V}.设有一个由n个词构成的词序列 S = w1,w2…wn目标为找到最优的词性序列T = t1,t2…tn,基于HMM的词性标注,如何计算 和 ?为使问题简化，假定：词wi 的出现，仅仅依赖于它的词性标记，不依赖于其他因素（例如它前一个词的出现）标记 ti 的出现仅仅条件依赖于它前面的标记ti-1 (马尔科夫假设),基于HMM的词性标注,HMM的状态集合：词性标记集合HMM输出字符集合：词汇集合 [notation:ti is the ith tag in a tag sequence , t_i represents the ith tag in the tag set {t_1,..,t_M}] pi : [p(t_i|*start*)] 状态t_i的起始概率aij : [p(t_j|t_i)] 从状态 t_i 到状态 t_j的转移概率bjk : [p(w_k|t_j)] 状态t_j的词w_k发射概率,参数训练,模型的参数未知假设有已经标注好的语料库:S = w1,w2…wnT = t1,t2…tn如何从语料库中得到这样的参数使用最大相似度估计,音字转换,状态集：词发射字符集：拼音pi : [p(t_i|*start*)] 状态t_i的起始概率aij : [p(t_j|t_i)] 从状态 t_i 到状态 t_j的转移概率bjk : [p(w_k|t_j)] 状态t_j的词w_k发射概率,结束语,,。