一

理论： 简版：猜（E-step）,反思（M-step）,重复； 啰嗦版： 你知道一些东西（观察的到的数据）， 你不知道一些东西（观察不到的），你很好奇，想知道点那些不了解的东西。怎么办呢，你就根据一些假设（parameter）先猜（E-step），把那些不知道的东西都猜出来，假装你全都知道了; 然后有了这些猜出来的数据，你反思一下，更新一下你的假设（parameter）, 让你观察到的数据更加可能(Maximize likelihood; M-stemp); 然后再猜，在反思，最后，你就得到了一个可以解释整个数据的假设了。 1. 注意，你猜的时候，要尽可能的猜遍所有情况，然后求期望（Expected）；就是你不能仅仅猜一个个例，而是要猜出来整个宇宙； 2. 为什么要猜，因为反思的时候，知道全部的东西比较好。（就是P(X,Z)要比P(X)好优化一些。Z是hidden states） 3. 最后你得到什么了？你得到了一个可以解释数据的假设，可能有好多假设都能解释数据，可能别的假设更好。不过没关系，有总比没有强，知足吧。（你陷入到local minimum了） ==== 实践： 背景：公司有很多领导=[A总，刘总，C总]，同时有很多漂亮的女职员=[小甲，小章，小乙]。（请勿对号入座）你迫切的怀疑这些老总跟这些女职员有问题。为了科学的验证你的猜想，你进行了细致的观察。于是， 观察数据： 1）A总，小甲，小乙一起出门了； 2）刘总，小甲，小章一起出门了； 3）刘总，小章，小乙一起出门了； 4）C总，小乙一起出门了； 收集到了数据，你开始了神秘的EM计算： 初始化，你觉得三个老总一样帅，一样有钱，三个美女一样漂亮，每个人都可能跟每个人有关系。所以，每个老总跟每个女职员“有问题”的概率都是1/3; 这样，（E step） 1） A总跟小甲出去过了 1/2 * 1/3 = 1/6 次，跟小乙也出去了1/6次；（所谓的fractional count） 2）刘总跟小甲，小章也都出去了1/6次 3）刘总跟小乙，小章又出去了1/6次 4）C总跟小乙出去了1/3次 总计，A总跟小甲出去了1/6次，跟小乙也出去了1/6次 ; 刘总跟小甲，小乙出去了1/6次，跟小章出去了1/3次；C总跟小章出去了1/3次； 你开始跟新你的八卦了(M step), A总跟小甲，小乙有问题的概率都是1/6 / (1/6 + 1/6) = 1/2； 刘总跟小甲，小乙有问题的概率是1/6 / (1/6+1/6+1/6+1/6) = 1/4; 跟小章有问题的概率是(1/6+1/6)/(1/6 * 4) = 1/2; C总跟小乙有问题的概率是 1。 然后，你有开始根据最新的概率计算了；（E-step） 1）A总跟小甲出去了 1/2 * 1/2 = 1/4 次，跟小乙也出去 1/4 次； 2）刘总跟小甲出去了1/2 * 1/4 = 1/12 次， 跟小章出去了 1/2 * 1/2 = 1/4 次； 3）刘总跟小乙出去了1/2 * 1/4 = 1/12 次， 跟小章又出去了 1/2 * 1/2 = 1/4 次； 4）C总跟小乙出去了1次； 重新反思你的八卦（M-step）: A总跟小甲，小乙有问题的概率都是1/4/ (1/4 + 1/4) = 1/2； B总跟小甲，小乙是 1/12 / (1/12 + 1/4 + 1/4 + 1/12) = 1/8 ; 跟小章是 3/4 ; C总跟小乙的概率是1。 你继续计算，反思，总之，最后，你得到了真相！

二

越简单越直观的往往越震撼。

EM算法是个神奇的东西， 这次将利用它来解决简单的句子对齐问题，并得到双语翻译概率表 假设语料库为： I laugh  我 笑 laugh loudly 大声地 笑 那么有英语词汇表}{I,laugh,loudly} 以及中文词汇表{我，笑，大声地} 最开始，我们并没有任何关于词汇间如何翻译的信息（也就是说，锅看不懂中文，更看不懂英文） 那么： P(我|I）=1/3      P(笑|I）=1/3     P(大声地|I）=1/3 P(我|laugh）=1/3  P(笑|laugh）=1/3  P(大声地|laugh）=1/3 P(我|loudly）=1/3  P(笑|loudly）=1/3  P(大声地|loudly）=1/3 对于 I laugh  我 笑 laugh loudly 大声地 笑 有2种对齐方式：顺序（I对应我，laugh对应笑），反序（I对应笑，laugh对应我） 这样 P(顺序，我 笑|I laugh）= P(我|I）   P(笑|laugh）=1/3*1/3=1/9 P(反序，我 笑|I laugh）= P(笑|I）   P(我|laugh）=1/3*1/3=1/9 规则化后，有： P(顺序，我 笑|I laugh）=1/2 P(反序，我 笑|I laugh） =1/2 同理，对于第二个句子对 P(顺序， 大声地 笑  | laughloudly  ）=1/2 P(反序， 大声地 笑  | laughloudly  ） =1/2 貌似到此为止，我们什么都没干 因为对于  I laugh 我 笑来说，计算机认为顺序，反序对齐都一样，但作为我们人来说，由于对这两门语言有背景知识，可以一下就说，这明显是顺序对齐嘛。 同样，对于第二个句子对，也可以马上回答肯定是反序对齐。 不急，继续下去。 现在重新计算词汇对译概率 可得： P(我|I）=1/2      P(笑|I）=1/2      P(大声地|I）=0 这个概率的得出步骤： 考虑 （我 I）这一对，他出现在（ I laugh 我 笑 的）的顺序对齐中，而其概率为1/2（其实称为权重更确切） (笑|I）出现在 （ Ilaugh  我 笑 的）的反序对齐中，而其概率为1/2 而 (大声地|I）没有出现。 所以，将上述步骤所得概率归一化后， 可得： P(我|I）=1/2      P(笑|I）=1/2      P(大声地|I）=0 P(我|laugh）=1/4  P(笑|laugh）=1/2  P(大声地|laugh）=1/4 P(我|loudly）=0   P(笑|loudly）=1/2  P(大声地|loudly）=1/2 渐渐的，似乎这概率意思着laugh可以被翻译为笑。。。 再接着，重新计算各句对顺序反序概率 P(顺序，我 笑|I laugh）= P(我|I）   P(笑|laugh）=1/2*1/2=1/4 P(反序，我 笑|I laugh）= P(笑|I）   P(我|laugh）=1/2*1/4=1/8 P(顺序，  大声地 笑  |  laughloudly  ）=1/8 P(反序，  大声地 笑  |  laughloudly  ） =1/4 归一后， P(顺序，我 笑|I laugh）=2/3 P(反序，我 笑|I laugh）= 1/3 P(顺序，  大声地 笑  |  laughloudly  ）= 1/3 P(反序，  大声地 笑  |  laughloudly  ） = 2/3 也就是说，现在计算机相信，第一个句子对更倾向于顺序对齐，第二个句子对更倾向于反序对齐，这与我们的直觉相符合。

相关资源：EM算法一个实例展示