单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Online EM for Unsupervised Models,Written by Percy Liang,Dan Klein,Presented by Linzheng,ACL-2009,Online EM for Unsupervised Mod,1,Outline,Introduction,Tasks,models and datasets,EM algorithms,Experiments,Conclusion,OutlineIntroduction,2,Introduction,在无监督学习的NLP任务中，比如tagging,parsing,alignment，往往需要引入隐含的语言结构。,概率模型是解决这些问题的典范，而EM算法是用于模型学习的驱动力，它简单且直观。,Introduction在无监督学习的NLP任务中，比如ta,3,Introduction,然而，,EM,算法存在收敛慢的问题，比如在词性标注问题中，,EM,迭代大约需要,100,轮来达到最高性能。,EM,算法执行慢主要源自它的批特性，即每趟遍历完所有的数据后参数只更新一次。,当参数估计仍然粗糙或者数据存在高冗余时，计算全部数据后更新一次参数显然是浪费的。,Introduction然而，EM算法存在收敛慢的问题，比如,4,Introduction,在这篇文章中作者调研了两种在线,EM,算法,incremental EM and stepwise EM.,即在每个样本或者一小批样本后更新参数，在线学习算法通过频繁更新来实现加速收敛。,文章主要研究,stepwise EM,，发现选择合适的,stepsize,和,mini-batch size,非常重要。,stepwise EM,可以和,batch EM,达到相同效果并且速度更快，此外，,stepwise EM,甚至可以超越,batch EM,的性能。,Introduction在这篇文章中作者调研了两种在线EM算,5,Tasks,models and datasets,定义一个概率模型 其中,x,是输入变量，,z,是隐含输出变量，是参数。给定一组没有标记的样本,x1,.xn,，训练目标是最大化这些样本的对数似然：,Tasks,models and datasets,6,Tasks,models and datasets,文章对四个任务进行了实验，分别是：,词性标注（Part-of-speech tagging）,文档分类(Document classification),分词(Word segmentation),词对齐(Word alignment),Tasks,models and datasets文章对四个,7,Tasks,models and datasets,词性标注,:,对每个句子 ，代表一个词序列，我们希望预测相应的词性标记序列,模型采用二元隐马尔科夫模型,数据采用,Wall Street Journal portion of the Penn Treebank(49208,个句子，,45,个标记,),Tasks,models and datasets词性标注:,8,Tasks,models and datasets,文档分类：,每篇文档 包含,L,个单词，我们希望预测文档的类别,每篇文档的类别在其所包含的所有单词的类别上建模,实验采用,18828,篇文档，,20,个类别。,Tasks,models and datasets文档分类：,9,Tasks,models and datasets,分词：,对每个句子 代表一串没有间隔的英文音素或者中文汉字，想要将其分变成单词序列,模型采用,nave unigram model,由于倾向于将每个句子形成一个切分，所以对长切分进行惩罚和最长字符限制。,数据采用,CHILDES database(9790,个句子,),和,SIGHAN,前,100k,个句子。,Tasks,models and datasets分词：,10,Tasks,models and datasets,词对齐：,每一个互翻译的双语句对,要预测词语对齐,模型：,IBM,模型,1,数据采用英法,Hansards NAACL 2003,Tasks,models and datasets词对齐：,11,EM algorithms,EM算法是机器学习中一个很重要的算法，这种方法可以广泛地应用于处理不完整数据，主要包括以下两个步骤：,E步骤：estimate the expected valuesM步骤：re-estimate parameters,迭代使用EM步骤，直至收敛。,EM algorithmsEM算法是机器学习中一个很重要的算,12,EM algorithms,完整似然函数：,若隐含变量 的值已知，得到完整数据的log似然函数为：,EM algorithms完整似然函数：,13,EM algorithms,观测数据,X,已知，参数的当前值 已知，在完整似然函数中，缺失数据(隐含变量),Y,未知，完整,log,似然函数对,Y,求期望。,定义,其中 是待确定的参数,通过求期望，去掉了完整似然函数中的变量,Y。,即,EM,的,E,步。,EM algorithms观测数据X已知，参数的当前值,14,EM algorithms,对,E,步计算得到的完整似然函数的期望求极大值（,EM,的,M,步），得到参数新的估计值，即,每次参数更新会增加非完整似然值,反复迭代后，会收敛到似然的局部最大值,EM algorithms对E步计算得到的完整似然函数的期望,15,EM algorithms,Batch EM,EM algorithmsBatch EM,16,EM algorithms,Online EM,EM algorithmsOnline EM,17,EM algorithms,Online EM,EM algorithmsOnline EM,18,EM algorithms,Stepwise EM,算法有两个重要参数：,Stepwise reduction power,a,：,a,越小，更新越大，旧的统计数据衰减越快，可以导致快速收敛，也会造成不稳定性。,Mini-batch size,m,：可以通过在许多样本后更新一次而不是每个样本更新一次来增加稳定性，即把每一小批样本看成单个样本。,m,越大更新越缓，越稳定。,EM algorithmsStepwise EM算法有两个重,19,Experiments词性标注,Experiments词性标注,20,Experiments文本分类,Experiments文本分类,21,Experiments分词,Experiments分词,22,Experiments词对齐,Experiments词对齐,23,Experiments,Experiments,24,Experiments,Experiments,25,Experiments,Experiments,26,Experiments,Experiments,27,Conclusion,这篇文章探索了online EM算法在四个任务中的应用，展示了如何使用stepwise EM克服随机性（stochasticity）的危险，使模型从快速学习中受益。,实验中发现stepwise确实可以提高正确率，这种现象值得深入研究。,Conclusion这篇文章探索了online EM算法在四,28,Thanks,29,