Icy*_*now 9 algorithm computer-science machine-learning data-mining expectation-maximization
我最近一直在自我研究期望最大化,并在这个过程中抓住了一些简单的例子:
http://cs.dartmouth.edu/~cs104/CS104_11.04.22.pdf 投掷时有3个硬币0,1和2,P0,P1和P2概率落在头上.投掷硬币0,如果结果是头,投掷硬币1三次,否则投掷硬币2三次.由硬币1和2产生的观察数据如下:HHH,TTT,HHH,TTT,HHH.隐藏数据是硬币0的结果.估计P0,P1和P2.
http://ai.stanford.edu/~chuongdo/papers/em_tutorial.pdf 有两个硬币A和B,PA和PB是投掷时落在头上的概率.每轮,随机选择一枚硬币,然后扔10次,然后记录结果.观察到的数据是由这两个硬币提供的折腾结果.但是,我们不知道为特定回合选择了哪一枚硬币.估计PA和PB.
虽然我可以得到计算,但我无法将它们的解决方式与原始的EM理论联系起来.具体来说,在两个例子的M-Step期间,我看不出它们是如何最大化任何东西的.它们似乎正在重新计算参数,不知何故,新参数比旧参数更好.而且,两个E-Steps甚至看起来都不相似,更不用说原始理论的E-Step了.
那么这些例子究竟是如何运作的呢？
第二个PDF不会为我下载,但我也访问了维基百科页面http://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm,其中包含更多信息.http://melodi.ee.washington.edu/people/bilmes/mypapers/em.pdf(声称是一个温和的介绍)也许值得一看.
EM算法的重点是找到最大化观测数据可能性的参数.这是第一页PDF第8页的唯一要点,即资本Theta下标ML的等式.
EM算法在有隐藏数据的情况下派上用场,如果您知道这些数据会使问题变得容易.在三个硬币的例子中,这是投掷硬币0的结果.如果你知道结果,你可以(当然)产生估计硬币0转向头的概率.您还可以知道硬币1或硬币2是否在下一阶段被抛掷三次,这将允许您估计硬币1和硬币2翻转头的概率.这些估计是合理的,他们说他们最大化观察数据的可能性,这不仅包括你给出的结果,还包括你不是的隐藏数据 - 硬币0的结果.对于得到的硬币A头和B尾你发现A头概率的最大可能性是A /(A + B) - 你可能值得详细解决这个问题,因为它是M步的构建块.
在EM算法中,您说虽然您不知道隐藏数据,但您可以使用概率估计值来记录它的概率分布.对于隐藏数据的每个可能值,您可以找到参数值,这些参数值将优化数据的对数似然性,包括隐藏数据,这几乎总是意味着计算某种加权平均值(如果它不是EM步骤可能太难实用).
什么是EM算法要求你做的是找到这些参数最大限度地通过所有可能隐藏的数据值,其中权重由相关的隐藏数据的概率给定的日志可能性的加权和给出了使用的参数观测EM步骤的开始.这几乎所有人,包括维基百科算法,都称之为Q函数.维基百科文章中给出的EM算法背后的证据表明,如果你改变参数以增加Q函数(这只是达到目的的手段),你也会改变它们以便增加观察数据的可能性(您关心的).您在实践中往往会发现,如果您知道隐藏数据,可以使用您将要做的变化来最大化Q函数,但是使用隐藏数据的概率,给出EM-开始时的估计值步骤,以某种方式加权观察.
在你的例子中,它意味着总计每个硬币产生的头部和尾部的数量.在PDF中,他们计算出P(Y = H | X =)= 0.6967.这意味着,使用重量0.6967的情况下Y = H,这意味着您由0.6967递增计数Y = H和3*0.6967递增计数X = H在硬币1,而你递增Y的计数= T乘0.3033并将硬币2中X = H的计数增加3*0.3033.如果您对为什么A /(A + B)是在标准情况下硬币概率的最大似然的详细理由,你应该准备把它变成为为什么这个加权更新方案最大化Q函数的理由.
最后,观察数据的对数可能性(您正在最大化的事物)为您提供了非常有用的检查.它应该随着每个EM步骤而增加,至少在你接近收敛时会出现舍入误差,在这种情况下,你可能会有一个非常小的减少,信号收敛.如果它急剧减少,你的程序或数学中就会出现错误.
幸运的是,我最近也在努力研究这种材料.以下是我如何看待它:
考虑一种相关但不同的算法,称为分类最大化算法,我们可以将其用作混合模型问题的解决方案技术.混合模型问题是我们有一系列数据可以由N个不同过程中的任何一个产生的问题,我们知道它们的一般形式(例如,高斯)但我们不知道过程的参数(例如,手段和/或方差)甚至可能不知道过程的相对可能性.(通常我们至少知道进程的数量.没有它,我们进入所谓的"非参数"领域.)从某种意义上说,生成每个数据的过程是"缺失"或"隐藏"数据这个问题.
现在,这个相关的分类 - 最大化算法所做的是从过程参数的一些任意猜测开始.根据这些参数过程中的每一个来评估每个数据点,并且生成一组概率 - 由第一过程,第二过程等生成数据点的概率,直到最后的第N过程.然后根据最可能的过程对每个数据点进行分类.
此时,我们将数据分为N个不同的类.因此,对于每类数据,我们可以通过一些相对简单的微积分,使用最大似然技术优化该聚类的参数.(如果我们在分类之前尝试在整个数据集上执行此操作,则通常在分析上难以处理.)
然后我们更新我们的参数猜测,重新分类,更新我们的参数,重新分类等,直到收敛.
期望最大化算法的作用是相似的,但更为通用:我们现在使用软分类,而不是将数据点硬分类到类1,类2,...到N类,其中每个数据点属于每个过程都有一定的概率.(显然,每个点的概率需要总和为1,所以有一些标准化正在进行.)我认为我们也可能会想到这一点,因为每个过程/猜测对每个数据都有一定的"解释力"点.
所以现在,我们不是优化关于绝对属于每个类的点的猜测(忽略绝对不属于的点),而是重新优化那些软分类或那些解释力的上下文中的猜测.碰巧的是,如果你以正确的方式写出表达式,那么你最大化的是一个函数,它是一种形式的期望.
话虽如此,但有一些警告:
1)这听起来很容易.至少对我而言,这不是.文献中充斥着一些特殊技巧和技巧 - 使用似然表达而不是概率表达式,转换为对数似然,使用指标变量,将它们置于基础向量形式并将它们放入指数等等.
一旦你有了一般的想法,这些可能会更有帮助,但它们也可以混淆核心思想.
2)无论您对问题有什么限制,都可能很难融入框架.特别是,如果您知道每个过程的概率,那么您可能处于良好状态.如果没有,你也在估算那些,并且过程概率的总和必须是1; 他们必须依靠单纯概率生活.如何保持这些约束完整并不总是显而易见的.
3)这是一种足够通用的技术,我不知道如何编写一般的代码.这些应用程序远远超出了简单的集群,并且扩展到了实际上缺少数据的许多情况,或者缺少数据的假设可能对您有所帮助. 对于许多应用来说,这里有一种恶魔般的聪明才智.
4)这种技术被证明是收敛的,但收敛不一定是全局最大值; 警惕.
我发现以下链接有助于提出上述解释:统计学习幻灯片
以下文章详细介绍了一些痛苦的数学细节: 迈克尔柯林斯的写作