Treebank(49208个句子，45个标记)
Tasks,models and datasets
• 文档分类： • 每篇文档 x (x1,..., xl ) 包含L个单词，我们希
望预测文档的类别 z {z1,...z20} • 每篇文档的类别在其所包含的所有单词的类
别上建模 • 实验采用18828篇文档，20个类别。
n
log f (X i ,Yi | ) k 1 n
log f (X i ,Yi | ) i1 n
log( f (X i | Yi , ) f (Yi | )) i1
EM algorithms
• 观测数据X已知，参数的当前值 t已知， 在完整似然函数中，缺失数据(隐含变量) Y未知，完整log似然函数对Y求期望。

Tasks,models and datasets
• 定义一个概率模型 p(x, z; ) 其中x是输 入变量，z是隐含输出变量， 是参数。
给定一组没有标记的样本x1,….xn，训练 目标是最大化这些样本的对数似然：
Tasks,models and datasets
• 文章对四个任务进行了实验，分别是： • 词性标注（Part-of-speech tagging） • 文档分类(Document classification) • 分词(Word segmentation) • 词对齐(Word alignment)
• E步骤：estimate the expected values M步骤：re-estimate parameters
• 迭代使用EM步骤，直至收敛。
EM algorithms
• 完整似然函数： • 若隐含变量 (Y1,Y2 ,,Yn )的值已知，得到
完整数据的log似然函数为：
l( | , ) log L( | , )
Introduction
• 在无监督学习的NLP任务中，比如 tagging,parsing,alignment，往往需要引入 隐含的语言结构。
• 概率模型是解决这些问题的典范，而EM 算法是用于模型学习的驱动力，它简单 且直观。
Introduction
• 然而，EM算法存在收敛慢的问题，比如在词 性标注问题中，EM迭代大约需要100轮来达到 最高性能。
Experiments——词性标注
Experiments——文本分类
Experiments——分词
Experiments——词对齐
Experiments
Tasks,models and datasets
• 词对齐： 每一个互翻译的双语句对 要预测词语对齐 模型：IBM模型1 数据采用英法Hansards NAACL 2003
EM algorithms
• EM算法是机器学习中一个很重要的算法， 这种方法可以广泛地应用于处理不完整 数据 ，主要包括以下两个步骤：
• EM算法执行慢主要源自它的批特性，即每趟 遍历完所有的数据后参数只更新一次。
• 当参数估计仍然粗糙或者数据存在高冗余时， 计算全部数据后更新一次参数显然是浪费的。
Introduction
• 在这篇文章中作者调研了两种在线EM算法— —incremental EM and stepwise EM.
• Batch EM
EM algorithms
• Online EM
EM algorithms
• Online EM
EM algorithms
• Stepwise EM算法有两个重要参数： • Stepwise reduction power a：a越小，更新
越大，旧的统计数据衰减越快，可以导 致快速收敛，也会造成不稳定性。 • Mini-batch size m：可以通过在许多样本 后更新一次而不是每个样本更新一次来 增加稳定性，即把每一小批样本看成单 个样本。m越大更新越缓，越稳定。
Online EM for Unsupervised Models
Written by Percy Liang,Dan Klein Presented by Linzheng ACL-2009
Outline
• Introduction • Tasks,models and datasets • EM algorithms • Experiments • Conclusion
• 即在每个样本或者一小批样本后更新参数，在 线学习算法通过频繁更新来实现加速收敛。
• 文章主要研究stepwise EM，发现选择合适的 stepsize和mini-batch size非常重要。stepwise EM可以和 batch EM达到相同效果并且速度更 快，此外，stepwise EM甚至可以超越batch EM 的性能。
Tasks,models and datasets
• 分词： • 对文每 音个 素句 或子 者中x 文(x汉1,..字., x，l ) 想代要表将一其串分没变有间成隔单的词英序
列 z (z1,..., z|z| ) • 模型采用naïve unigram model,由于倾向于将每
个句子形成一个切分，所以对长切分进行惩罚 和最长字符限制。 • 数据采用CHILDES database(9790个句子)和 SIGHAN前100k个句子。
• 定义
其中 是待确定的参数 • 通过求期望，去掉了完整似然函数中的
变量Y。即EM的E步。
EM algorithms
• 对E步计算得到的完整似然函数的期望求极大 值（EM的M步），得到参数新的估计值，即
• 每次参数更新会增加非完整似然值 • 反复迭代后，会收敛到似然的局部最大值
EM algorithms
Tasks,models and datasets
• 词性标注: • 对每个句子 x (x1,..., xl ) ，代表一个词序列，
我们希望预测相应的词性标记序列 z (z1,..., zl ) • 模型采用二元隐马尔科夫模型 • 数据采用Wall Street Journal portion of the Penn