EM算法的丢硬币实例
起因
不记得是看哪篇文章的时候,提到优化某个目标函数的时候不能用SGD等方法,要用EM算法才行,因为涉及到隐变量.但由于自己学习顺序比较混乱,所以一直不了解这个是啥(之后得补下<凸优化>相关的内容).这里记录下nature上的一篇丢硬币问题来简单学习下EM算法,以后要用到的时候再仔细学下.
丢硬币问题
问题
简单的讲,就是有两个不均匀硬币A,B,然后每次实验抛10次,记录正面和反面次数,做多次这样的实验后,预测硬币A,B各自的正面概率.
第一种情况是实验员记录了每次丢的是哪个硬币,没有隐变量,直接最大似然就可以算出A,B的正面概率
θ^A,θ^B 第二种情况就是忘记记录每次丢的是A硬币还是B硬币了,所以每次实验结果需要特别考虑.
这里E-step就是对每种情况求了可能性,比如第一次如果丢的是硬币A,则丢到正面的概率为PA=C510(θA)5∗(1−θA)10−5 ,
然后同理可以求出此时PB ,
两者归一化后就可以得到这次用硬币A的概率为0.45 了,此时实际发生正面向上的次数是5 ,所以这次硬币A正面向上的期望为5∗0.45=2.2 ,
同理这样算完一轮,累加就可以得到θ^(1) ,这就是M-step,
迭代多次后正面向上概率收敛,就可以当做预测结果了.
具体的理论,可参考别人写的,大致是利用JENSEN不等式,将优化目标转化,然后迭代去优化下界.
可以参考后面几个链接.
http://nooverfit.com/wp/em%E7%AE%97%E6%B3%95/
http://www.hankcs.com/ml/em-algorithm-and-its-generalization.html