欢迎转载，作者：Ling，注明出处：自然语言处理：原理简明教程04-马尔可夫模型与EM模型
参考书：《统计自然语言处理（第2版）》，《形式语言与自动机理论》，《统计自然语言基础》，《自然语言处理综论》 ，《概率图模型：原理与技术》，《概率论与数理统计》

概率图模型（第４页，概率图模型）：

贝叶斯网络：有向图，通过贝叶斯公式计算所有的联合概率，同时由于概率图的存在，不必存储所有联合概率

• 推导：

• 优势：减少条件概率的数目，仅要存图中有的条件概率，箭头就是前提条件

马尔可夫网：无向图，通过分成团，得到因子，计算联合概率

产生式与判别式：

• 上图是产生式，即通过概率的连乘推导出来最后的概率
• 下图是判别式，即直接得到最后的概率公式，直接算结果
• 论文：

• 结论：规模大时判别式好，小时产生式好

产生式　VS　判别式

• 分类器：给出输入x，分类变量y，求p(y|x)
• 产生式模型的思想是先估算联合概率密度p(x,y)，再通过贝叶斯公式求出p(y|x)，判别式模型则直接估算p(y|x)
• 产生式模型典型代表：朴素贝叶斯，判别式模型典型代表：logistics回归
• 一般认为判别式模型更受喜爱，“人们应该更直接去解决问题，永进丌要把求解更复杂的问题作为中间阶段”（Vapnik），吴恩达的论文作了较全面的分析，产生式模型（朴素贝叶斯）在少量样本的情况下，可以取得更好的精确率，判别式模型（logistics回归）在样本增加的情况下，逐渐逼近前者的精确率
• 例子：

马尔科夫：

• 彼得堡数学学派：切比雪夫，马尔科夫和李雅普诺夫
• 学派主要贡献：复兴概率论，把概率论从濒临衰亡的境地挽救出来，恢复其作为一门数学学科的地位，幵把它推迚到现代化的门槛

随机过程（浙大书：300）：简单说就是每个时间t都有不同的分布，所以我们要研究子问题，平稳随机过程，随时间不变，马尔科夫随机过程：现在之和之前有关

马尔可夫随机过程：当前只和之前相关

马尔可夫链：时间和状态都是离散的马尔科夫过程称为马尔可夫链

转移概率：转移概率，转移概率矩阵，齐次马氏链，一步转移概率矩阵

齐次：每次走一样的步数，如：1步

随机游动：

求多步转移概率：即一步的转移矩阵的n次方

n次方好求：

遍历性：即无限次转移后，最终会稳定到一个状态

应用：

• Page Rank算法

       网页和网页之间的链接建立转移概率：

        但是，存在0值，不可逆
        修正：

        S表示原始G，U为全1矩阵，α表示去别的网页的概率，所以乘在S上，1-α表示停留在本页的概率

        利用修正后转移矩阵求下一个网页概率：

隐马尔可夫：

图：

形式化表示：

• 定义：

• 组成：

• 实例：http://www.cnblogs.com/skyme/p/4651331.html

HMM中三个基本问题（p111）

• 估计问题
• 序列问题
• 训练问题戒参数估计问题

第一个基本问题：解码问题，在所有状态组合中找，找到能够得到该观察序列的，统计总和

• 直接推导斱法（计算量出现“指数爆炸”）
• 基于动态规划思想的格架算法：写出递推公式

• 前向算法：

        其中αt(i)表示到si状态的概率

        推导：

• 后向算法：

第二个基本问题：确定状态序列

• at(i)表示t时到i点前向所有概率，βt（i）也表示t时到i点后向所有概率，下面表示t时到所有状态的概率和

• 归纳公式表示：t时在sj状态的最大概率等于，t-1时刻i状态最大概率，转移到j状态的所有I取值，中最大的，再乘上发射概率
• 注意还需要一个存路径的。

第三个基本问题：HMM的参数估计问题

EM（期望+最大似然）：

期望最大化(Expectation Maximization) 算法最初是由Ceppellini 等

人1950 年在讨论基因频率的估计的时候提出的。后来又被Hartley 和

Baum 等人发展的更加广泛。目前引用的较多的是1977 年Dempster

等人的工作。它主要用于从不完整的数据中计算最大似然估计。后来经过

其他学者的发展，这个算法也被用于聚类等应用

要点：

• 在数据信息完全时，θ可以通过两种方式求，一种时统计出现次数的方式（称１方式），一种时极大似然的方法，让样本概率最大（２方式）
• 当数据信息缺失的情况下，先随机取θ值，然后根据θ值补充完全信息，然后就可以用２方式求解θ，然后用新θ替代老θ，如此反复。

实例：参考《EM算法详细例子及推导》

• 总结：注意投掷哪枚硬币是不知道的
• E步：

          （1） 随机给θ值

           （2）在给定θ值的情况下，目前A,B状态序列位置，可以通过θ推算。

• M步：

           （3）根据硬币和最后结果，假设θ未知，得到一个概率公式，用最大似然公式计算θ，得到后重新计算（2），直到收敛

数学意义：

• 几点说明：

        （1）式子（5）表示要让最后所有概率乘积最大，用了ln后就是相加

        （2）式子（6）表示每个X的取值，需要把每个Z取值对应的x都加起来

        （3）引入一个aj (7)

        （4）式子（8）是当图形为下凸时候的jesson不等式

• 如图：

        （5）式子（9）相反，因为ln是上凸，所以刚好相反

        （6）式子（10）目的是说明，只有这个为常数，才会有等号成立

        （7）式子（11）的证明如下

         （8）提出aj目的就是，通过θ可以求aj，算出aj后，可以直到zj,有了zj,假设aj中参数未知，即可有l(θ)，用极大似然函数求即可

对于期望最大化算法收敛性讨论：

• 说明：

        （1）只要每次似然函数值都在增大即可保证收敛，因为单调的凸函数，肯定有极值

        （2）第一个不等号，由E步决定，每次都要让那个条件概率公式更大，第二个不等号，由M步决定，每次最大似然要变大

• 宗书的描述一般，所以这里只是附上，不解释：

应用：

语音识别：

• 将语音分成因子，然后单词是隐藏状态，发音序列是观测序列
• 注意这里隐藏状态其实跨多个马尔科夫模型，每个单词是一个
• 汉语容易，英语难
• 具体不讲解，以后专门讲

分词

层次化隐马尔可夫模型（HHMM）：用得不多，不细讲

• HHMM的提出：在自然语言处理等应用中，由于处理序列具有递归特性，尤其当序列长度较大时，HMM的复杂度会急剧增大，因此，ShaiFine等人提出了HHMM。
• HHMM的结构机制：HHMM是由多层随机过程构成。在HHMM中每个状态本身就是一个独立的HHMM，因此一个HHMM的状态产生一个观察序列。HHMM通过状态转移递归地产生观察序列，一个状态可以激活下层状态中的某一个状态，如此循环，直到到达某个特定的状态这一递归结束，该特定状态称为生产状态。丌直接产生可观察符号的隐匿状态称作内部状态。丌同层次之间的转移叫做垂直转移，同一层次之间的转移叫做水平转移。
• HHMM的形式化描述（p120）
• HHMM需解决的三个基本问题（p120）
• 适用于长文本分类

马尔科夫网络：之后会被条件随机场借鉴

• 实例：（概率图模型书82页）

特点：

• 无向图：不是有向图，无法用贝叶斯网络
• 联合概率密度
• 定义因子
• 计算一切

• 说明：

        （1）将图分解为子团，所谓团就是一个图形中所有点都是互连的

         如：

        （2）每个子团为一个因子

        （3）联合概率等于因子的乘积

        （4）有了联合概率可以计算一切

        （5）要正规化，可参考宗书121页