在无监督学习的NLP任务中课件.ppt

1、Online EM for Unsupervised ModelsWritten by Percy Liang,Dan KleinPresented by LinzhengACL-2009Outline Introduction Tasks,models and datasets EM algorithms Experiments ConclusionIntroduction 在无监督学习的NLP任务中，比如tagging,parsing,alignment，往往需要引入隐含的语言结构。概率模型是解决这些问题的典范，而EM算法是用于模型学习的驱动力，它简单且直观。Introduction 然而

2、，EM算法存在收敛慢的问题，比如在词性标注问题中，EM迭代大约需要100轮来达到最高性能。EM算法执行慢主要源自它的批特性，即每趟遍历完所有的数据后参数只更新一次。当参数估计仍然粗糙或者数据存在高冗余时，计算全部数据后更新一次参数显然是浪费的。Introduction 在这篇文章中作者调研了两种在线EM算法incremental EM and stepwise EM.即在每个样本或者一小批样本后更新参数，在线学习算法通过频繁更新来实现加速收敛。文章主要研究stepwise EM，发现选择合适的stepsize和mini-batch size非常重要。stepwise EM可以和 batch E

3、M达到相同效果并且速度更快，此外，stepwise EM甚至可以超越batch EM的性能。Tasks,models and datasets 定义一个概率模型 其中x是输入变量，z是隐含输出变量，是参数。给定一组没有标记的样本x1,.xn，训练目标是最大化这些样本的对数似然：(,;)p x zTasks,models and datasets 文章对四个任务进行了实验，分别是：词性标注（Part-of-speech tagging）文档分类(Document classification)分词(Word segmentation)词对齐(Word alignment)Tasks,models

4、 and datasets 词性标注词性标注:对每个句子 ，代表一个词序列，我们希望预测相应的词性标记序列 模型采用二元隐马尔科夫模型 数据采用Wall Street Journal portion of the Penn Treebank(49208个句子，45个标记)1(,.,)lxxx1(,.,)lzzzTasks,models and datasets 文档分类：文档分类：每篇文档 包含L个单词，我们希望预测文档的类别 每篇文档的类别在其所包含的所有单词的类别上建模 实验采用18828篇文档，20个类别。1(,.,)lxxx120,.zzzTasks,models and datase

5、ts 分词：分词：对每个句子 代表一串没有间隔的英文音素或者中文汉字，想要将其分变成单词序列 模型采用nave unigram model,由于倾向于将每个句子形成一个切分，所以对长切分进行惩罚和最长字符限制。数据采用CHILDES database(9790个句子)和SIGHAN前100k个句子。1(,.,)lxxx1|(,.,)zzzzTasks,models and datasets 词对齐：词对齐：每一个互翻译的双语句对要预测词语对齐模型：IBM模型1数据采用英法Hansards NAACL 2003 EM algorithms EM算法是机器学习中一个很重要的算法，这种方法可以广泛地

6、应用于处理不完整数据，主要包括以下两个步骤：E步骤：estimate the expected valuesM步骤：re-estimate parameters 迭代使用EM步骤，直至收敛。EM algorithms 完整似然函数：若隐含变量 的值已知，得到完整数据的log似然函数为：)|(),|(log()|,(log)|,(log),|(log),|(111iiiniiininkiiYfYXfYXfYXfLl),(21nYYYEM algorithms 观测数据X已知，参数的当前值 已知，在完整似然函数中，缺失数据(隐含变量)Y未知，完整log似然函数对Y求期望。定义 其中 是待确定的参数

7、 通过求期望，去掉了完整似然函数中的变量Y。即EM的E步。tEM algorithms 对E步计算得到的完整似然函数的期望求极大值（EM的M步），得到参数新的估计值，即 每次参数更新会增加非完整似然值 反复迭代后，会收敛到似然的局部最大值EM algorithms Batch EMEM algorithms Online EMEM algorithms Online EMEM algorithms Stepwise EM算法有两个重要参数：Stepwise reduction power a：a越小，更新越大，旧的统计数据衰减越快，可以导致快速收敛，也会造成不稳定性。Mini-batch size m：可以通过在许多样本后更新一次而不是每个样本更新一次来增加稳定性，即把每一小批样本看成单个样本。m越大更新越缓，越稳定。Experiments词性标注Experiments文本分类Experiments分词Experiments词对齐ExperimentsExperimentsExperimentsExperimentsConclusion 这篇文章探索了online EM算法在四个任务中的应用，展示了如何使用stepwise EM克服随机性（stochasticity）的危险，使模型从快速学习中受益。实验中发现stepwise确实可以提高正确率，这种现象值得深入研究。Thanks