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

OnlineEMforUnsupervisedModelsWrittenbyPercyLiang,DanKleinPresentedbyLinzhengACL-2009Outline•Introduction•Tasks,modelsanddatasets•EMalgorithms•Experiments•ConclusionIntroduction•在无监督学习的NLP任务中，比如tagging,parsing,alignment，往往需要引入隐含的语言结构。•概率模型是解决这些问题的典范，而EM算法是用于模型学习的驱动力，它简单且直观。Introduction•然而，EM算法存在收敛慢的问题，比如在词性标注问题中，EM迭代大约需要100轮来达到最高性能。•EM算法执行慢主要源自它的批特性，即每趟遍历完所有的数据后参数只更新一次。•当参数估计仍然粗糙或者数据存在高冗余时，计算全部数据后更新一次参数显然是浪费的。Introduction•在这篇文章中作者调研了两种在线EM算法——incrementalEMandstepwiseEM.•即在每个样本或者一小批样本后更新参数，在线学习算法通过频繁更新来实现加速收敛。•文章主要研究stepwiseEM，发现选择合适的stepsize和mini-batchsize非常重要。stepwiseEM可以和batchEM达到相同效果并且速度更快，此外，stepwiseEM甚至可以超越batchEM的性能。Tasks,modelsanddatasets•定义一个概率模型其中x是输入变量，z是隐含输出变量，是参数。给定一组没有标记的样本x1,….xn，训练目标是最大化这些样本的对数似然：(,;)pxzTasks,modelsanddatasets•文章对四个任务进行了实验，分别是：•词性标注（Part-of-speechtagging）•文档分类(Documentclassification)•分词(Wordsegmentation)•词对齐(Wordalignment)Tasks,modelsanddatasets•词性标注:•对每个句子，代表一个词序列，我们希望预测相应的词性标记序列•模型采用二元隐马尔科夫模型•数据采用WallStreetJournalportionofthePennTreebank(49208个句子，45个标记)1(,...,)lxxx1(,...,)lzzzTasks,modelsanddatasets•文档分类：•每篇文档包含L个单词，我们希望预测文档的类别•每篇文档的类别在其所包含的所有单词的类别上建模•实验采用18828篇文档，20个类别。1(,...,)lxxx120{,...}zzzTasks,modelsanddatasets•分词：•对每个句子代表一串没有间隔的英文音素或者中文汉字，想要将其分变成单词序列•模型采用naïveunigrammodel,由于倾向于将每个句子形成一个切分，所以对长切分进行惩罚和最长字符限制。•数据采用CHILDESdatabase(9790个句子)和SIGHAN前100k个句子。1(,...,)lxxx1||(,...,)zzzzTasks,modelsanddatasets•词对齐：每一个互翻译的双语句对要预测词语对齐模型：IBM模型1数据采用英法HansardsNAACL2003EMalgorithms•EM算法是机器学习中一个很重要的算法，这种方法可以广泛地应用于处理不完整数据，主要包括以下两个步骤：•E步骤：estimatetheexpectedvaluesM步骤：re-estimateparameters•迭代使用EM步骤，直至收敛。EMalgorithms•完整似然函数：•若隐含变量的值已知，得到完整数据的log似然函数为：))|(),|(log()|,(log)|,(log),|(log),|(111iiiniiininkiiYfYXfYXfYXfLl),,,(21nYYYEMalgorithms•观测数据X已知，参数的当前值已知，在完整似然函数中，缺失数据(隐含变量)Y未知，完整log似然函数对Y求期望。•定义其中是待确定的参数•通过求期望，去掉了完整似然函数中的变量Y。即EM的E步。tEMalgorithms•对E步计算得到的完整似然函数的期望求极大值（EM的M步），得到参数新的估计值，即•每次参数更新会增加非完整似然值•反复迭代后，会收敛到似然的局部最大值EMalgorithms•BatchEMEMalgorithms•OnlineEMEMalgorithms•OnlineEMEMalgorithms•StepwiseEM算法有两个重要参数：•Stepwisereductionpowera：a越小，更新越大，旧的统计数据衰减越快，可以导致快速收敛，也会造成不稳定性。•Mini-batchsizem：可以通过在许多样本后更新一次而不是每个样本更新一次来增加稳定性，即把每一小批样本看成单个样本。m越大更新越缓，越稳定。Experiments——词性标注Experiments——文本分类Experiments——分词Experiments——词对齐ExperimentsExperimentsExperimentsExperimentsConclusion•这篇文章探索了onlineEM算法在四个任务中的应用，展示了如何使用stepwiseEM克服随机性（stochasticity）的危险，使模型从快速学习中受益。•实验中发现stepwise确实可以提高正确率，这种现象值得深入研究。•Thanks