EM是我一直想深入学习的算法之一，第一次听说是在NLP课中的HMM那一节，为了解决HMM的参数估计问题，使用了EM算法。在之后的MT中的词对齐中也用到了。在Mitchell的书中也提到EM可以用于贝叶斯网络中。
下面主要介绍EM的整个推导过程。
回顾优化理论中的一些概念。设[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WuhYE7Fl-1638514368784)(/wp/wp-content/ql-cache/-9c09a708375fde2676da319bcdfe8b24_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VA4ueAXx-1638514368786)(/wp/wp-content/ql-cache/-ede05c264bba0eda080918aaa09c4658_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dZvyyjj6-1638514368787)(/wp/wp-content/ql-cache/-7b5f0fc712bf4973bcda40c7437ba537_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hfALaJBr-1638514368788)(/wp/wp-content/ql-cache/-9c09a708375fde2676da319bcdfe8b24_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3IGU0CGM-1638514368789)(/wp/wp-content/ql-cache/-1824ee36a8c6aa92fa65a226c903333e_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L1PKBR0D-1638514368789)(/wp/wp-content/ql-cache/-9c09a708375fde2676da319bcdfe8b24_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PsouFXJH-1638514368791)(/wp/wp-content/ql-cache/-150ded9f8f95d5fa8c19759a4a4bd48e_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JcisOdeg-1638514368792)(/wp/wp-content/ql-cache/-75c163a3045b8ceed6133c1a627c6ea1_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tsluhjz0-1638514368793)(/wp/wp-content/ql-cache/-9c09a708375fde2676da319bcdfe8b24_l3.svg)]
Jensen不等式表述如下：
如果f是凸函数，X是随机变量，那么
None[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-X5EgnXfj-1638514368796)(/wp/wp-content/ql-cache/-2597074a5052e0a2c7716ca5d5c6cdc6_l3.svg)]
特别地，如果[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-daBckBGG-1638514368797)(/wp/wp-content/ql-cache/-9c09a708375fde2676da319bcdfe8b24_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mfkWoE8f-1638514368798)(/wp/wp-content/ql-cache/-6bf71ffc061e93b3dbecbfc9b45f1f5a_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-x8nlWzl8-1638514368799)(/wp/wp-content/ql-cache/-d4ee28752517d6062a3ca0314890342d_l3.svg)]
如果用图表示会很清晰：
None
给定的训练样本是[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m5fedcMS-1638514368800)(/wp/wp-content/ql-cache/-e230f2cbdda27fb14463a30bb37d6b87_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QFlO4OHQ-1638514368802)(/wp/wp-content/ql-cache/-4586e340cb83d5b642972e97a288fec2_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EMNF5Q4r-1638514368803)(/wp/wp-content/ql-cache/-45109993b7cae72ab0d61b9662bba6fd_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EU5KMOzg-1638514368803)(/wp/wp-content/ql-cache/-45109993b7cae72ab0d61b9662bba6fd_l3.svg)]
None
第一步是对极大似然取对数，第二步是对每个样例的每个可能类别[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-abfNQnuU-1638514368804)(/wp/wp-content/ql-cache/-4586e340cb83d5b642972e97a288fec2_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l6GMmc9k-1638514368804)(/wp/wp-content/ql-cache/-356a08e839ab6974a16448e16e56745d_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ocUjEtyC-1638514368805)(/wp/wp-content/ql-cache/-4586e340cb83d5b642972e97a288fec2_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-By5wPVme-1638514368805)(/wp/wp-content/ql-cache/-4586e340cb83d5b642972e97a288fec2_l3.svg)]
EM是一种解决存在隐含变量优化问题的有效方法。既然不能直接最大化[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wHZaMLYS-1638514368806)(/wp/wp-content/ql-cache/-64095ba305c5c63151fa6b54d9d75b95_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-db7QfE7b-1638514368807)(/wp/wp-content/ql-cache/-502276c66966e5a861539c7de60c26c0_l3.svg)]
对于每一个样例[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fbU7vZM2-1638514368808)(/wp/wp-content/ql-cache/-695d9d59bd04859c6c99e7feb11daab6_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JFqfzGVi-1638514368809)(/wp/wp-content/ql-cache/-3839ba95b8c5369ec6c5719ddf58aecd_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-P44CkKEh-1638514368809)(/wp/wp-content/ql-cache/-4586e340cb83d5b642972e97a288fec2_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eSJVQeZ7-1638514368810)(/wp/wp-content/ql-cache/-3839ba95b8c5369ec6c5719ddf58aecd_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kqG2Z4GL-1638514368810)(/wp/wp-content/ql-cache/-2f133c2dc0ef48c62af37f2d063ee7e2_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bkbSFRiU-1638514368811)(/wp/wp-content/ql-cache/-4586e340cb83d5b642972e97a288fec2_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Gb61J2B4-1638514368812)(/wp/wp-content/ql-cache/-3839ba95b8c5369ec6c5719ddf58aecd_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HWKvFDXu-1638514368812)(/wp/wp-content/ql-cache/-4586e340cb83d5b642972e97a288fec2_l3.svg)]
可以由前面阐述的内容得到下面的公式：
None
（1）到（2）比较直接，就是分子分母同乘以一个相等的函数。（2）到（3）利用了Jensen不等式，考虑到[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wiJw22aZ-1638514368813)(/wp/wp-content/ql-cache/-2e1bc7f1882e5bec029c5d7a550ad963_l3.svg)]
None
就是
这个过程可以看作是对[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AP9aE6we-1638514368813)(/wp/wp-content/ql-cache/-64095ba305c5c63151fa6b54d9d75b95_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bEegEA0d-1638514368814)(/wp/wp-content/ql-cache/-3839ba95b8c5369ec6c5719ddf58aecd_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Niz4mZTq-1638514368814)(/wp/wp-content/ql-cache/-356a08e839ab6974a16448e16e56745d_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-su7JCRn4-1638514368815)(/wp/wp-content/ql-cache/-64095ba305c5c63151fa6b54d9d75b95_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MGKdB5J7-1638514368816)(/wp/wp-content/ql-cache/-c1a933aed7c02cc5cc95b75a08401521_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XE59bcPH-1638514368816)(/wp/wp-content/ql-cache/-460bcfc223aca35aa87bf45b18c92669_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CuFb3MBJ-1638514368817)(/wp/wp-content/ql-cache/-64095ba305c5c63151fa6b54d9d75b95_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Y84ZvdGL-1638514368817)(/wp/wp-content/ql-cache/-64095ba305c5c63151fa6b54d9d75b95_l3.svg)]
c为常数，不依赖于[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YL7bNZRl-1638514368818)(/wp/wp-content/ql-cache/-54a01a820b3f2da446b08da25515394c_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zce1vpdv-1638514368818)(/wp/wp-content/ql-cache/-c0d33a0932fa41ca30e504176b642a0d_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9r1iSubb-1638514368819)(/wp/wp-content/ql-cache/-0ac603919544fd90dc32fd002fc579bd_l3.svg)]
None
至此，我们推出了在固定其他参数[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TUqa4aPH-1638514368819)(/wp/wp-content/ql-cache/-64095ba305c5c63151fa6b54d9d75b95_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZHfUydPH-1638514368820)(/wp/wp-content/ql-cache/-c1a933aed7c02cc5cc95b75a08401521_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t04LFNZ0-1638514368820)(/wp/wp-content/ql-cache/-c1a933aed7c02cc5cc95b75a08401521_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qplMA4QR-1638514368821)(/wp/wp-content/ql-cache/-64095ba305c5c63151fa6b54d9d75b95_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-myP8mTPT-1638514368821)(/wp/wp-content/ql-cache/-c1a933aed7c02cc5cc95b75a08401521_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5c03VDtB-1638514368822)(/wp/wp-content/ql-cache/-64095ba305c5c63151fa6b54d9d75b95_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lcZOouC6-1638514368822)(/wp/wp-content/ql-cache/-64095ba305c5c63151fa6b54d9d75b95_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m6lH0GNs-1638514368823)(/wp/wp-content/ql-cache/-c1a933aed7c02cc5cc95b75a08401521_l3.svg)]
循环重复直到收敛
（E步）对于每一个i，计算
None
（M步）计算
None
那么究竟怎么确保EM收敛？假定[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DsMINYQk-1638514368824)(/wp/wp-content/ql-cache/-7bfa9c43a549c6a7b8fde54865315717_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1KVGJZuf-1638514368824)(/wp/wp-content/ql-cache/-9493f00ba5d10b35530e0f447e3cef17_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KzhTuBcU-1638514368825)(/wp/wp-content/ql-cache/-045e02e71cb198b70d486d4d7d2f2a27_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-H2kmOgxi-1638514368825)(/wp/wp-content/ql-cache/-7bfa9c43a549c6a7b8fde54865315717_l3.svg)]
None
这一步保证了在给定[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-npEmA6ME-1638514368826)(/wp/wp-content/ql-cache/-7bfa9c43a549c6a7b8fde54865315717_l3.svg)]
None
然后进行M步，固定[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WtwR6BS0-1638514368826)(/wp/wp-content/ql-cache/-20cdd167791db4ef1ee0c2719a8f81e6_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tXCoRbyx-1638514368827)(/wp/wp-content/ql-cache/-7bfa9c43a549c6a7b8fde54865315717_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ZuyqNG8d-1638514368827)(/wp/wp-content/ql-cache/-8d2feec2d78a7bbdf1d71d2acc05c873_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BHSFOkjr-1638514368828)(/wp/wp-content/ql-cache/-eb96da6481078be5a9a082db690f19c6_l3.svg)]
None
我们已经知道了EM的精髓和推导过程，再次审视一下混合高斯模型。之前提到的混合高斯模型的参数[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gZHqJwbw-1638514368828)(/wp/wp-content/ql-cache/-5b2be26c0c1341f54b29baddda771346_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EPEEWcBA-1638514368829)(/wp/wp-content/ql-cache/-461fe1a58a75801541487ddf10d32abd_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-f4is4FTM-1638514368829)(/wp/wp-content/ql-cache/-14fb1e14301ad034b94e3db3ff52c0c9_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-97eFCDi4-1638514368829)(/wp/wp-content/ql-cache/-5b2be26c0c1341f54b29baddda771346_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g3DzeXLj-1638514368830)(/wp/wp-content/ql-cache/-461fe1a58a75801541487ddf10d32abd_l3.svg)]
E步很简单，按照一般EM公式得到：
None
简单解释就是每个样例i的隐含类别[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xISVnVpF-1638514368830)(/wp/wp-content/ql-cache/-54a01a820b3f2da446b08da25515394c_l3.svg)]
在M步中，我们需要在固定[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GnNPBB5Q-1638514368831)(/wp/wp-content/ql-cache/-c1a933aed7c02cc5cc95b75a08401521_l3.svg)]
None
这是将[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HZSf3igk-1638514368831)(/wp/wp-content/ql-cache/-c1a933aed7c02cc5cc95b75a08401521_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-26xLXYro-1638514368832)(/wp/wp-content/ql-cache/-1579e942acfb0a4a980e9d7cc3460850_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Kj8Iowpi-1638514368832)(/wp/wp-content/ql-cache/-d618df96dfffc42d9f51026a05523fc1_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-h9ZEEyp2-1638514368833)(/wp/wp-content/ql-cache/-ff128744be833aee7ea2f93e7652c099_l3.svg)]
固定[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v3SzFhiS-1638514368834)(/wp/wp-content/ql-cache/-1579e942acfb0a4a980e9d7cc3460850_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SH39cdbE-1638514368835)(/wp/wp-content/ql-cache/-ff128744be833aee7ea2f93e7652c099_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PnBNgcDz-1638514368835)(/wp/wp-content/ql-cache/-d618df96dfffc42d9f51026a05523fc1_l3.svg)]
None
等于0时，得到
None
这就是我们之前模型中的,[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0PDmc7Bq-1638514368836)(/wp/wp-content/ql-cache/-461fe1a58a75801541487ddf10d32abd_l3.svg)]
然后推导[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tEOeiNHu-1638514368836)(/wp/wp-content/ql-cache/-1579e942acfb0a4a980e9d7cc3460850_l3.svg)]
None[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jjvXhAAe-1638514368837)(/wp/wp-content/ql-cache/-5b2be26c0c1341f54b29baddda771346_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kl9y2XKc-1638514368837)(/wp/wp-content/ql-cache/-461fe1a58a75801541487ddf10d32abd_l3.svg)]
None
需要知道的是，[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3VXXTpbb-1638514368838)(/wp/wp-content/ql-cache/-5b2be26c0c1341f54b29baddda771346_l3.svg)]
None
还有一点就是[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4KLPT23t-1638514368839)(/wp/wp-content/ql-cache/-491dbff9df6ef3e53aae0c28506c5943_l3.svg)]
None
等于0，得到
None
也就是说
None
这样就神奇地得到了[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6XQ8o3pG-1638514368840)(/wp/wp-content/ql-cache/-b6a7605b1bcca8f1b416eaf733f34e08_l3.svg)][外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HpDmPMqW-1638514368840)(/wp/wp-content/ql-cache/-1579e942acfb0a4a980e9d7cc3460850_l3.svg)]
None
None[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2osMY64v-1638514368841)(/wp/wp-content/ql-cache/-14fb1e14301ad034b94e3db3ff52c0c9_l3.svg)]
如果将样本看作观察值，潜在类别看作是隐藏变量，那么聚类问题也就是参数估计问题，只不过聚类问题中参数分为隐含类别变量和其他参数，这犹如在x-y坐标系中找一个曲线的极值，然而曲线函数不能直接求导，因此什么梯度下降方法就不适用了。但固定一个变量后，另外一个可以通过求导得到，因此可以使用坐标上升法，一次固定一个变量，对另外的求极值，最后逐步逼近极值。对应到EM上，E步估计隐含变量，M步估计其他参数，交替将极值推向最大。EM中还有“硬”指定和“软”指定的概念，“软”指定看似更为合理，但计算量要大，“硬”指定在某些场合如K-means中更为实用（要是保持一个样本点到其他所有中心的概率，就会很麻烦）。
另外，EM的收敛性证明方法确实很牛，能够利用log的凹函数性质，还能够想到利用创造下界，拉平函数下界，优化下界的方法来逐步逼近极大值。而且每一步迭代都能保证是单调的。最重要的是证明的数学公式非常精妙，硬是分子分母都乘以z的概率变成期望来套上Jensen不等式，前人都是怎么想到的。
在Mitchell的Machine Learning书中也举了一个EM应用的例子，明白地说就是将班上学生的身高都放在一起，要求聚成两个类。这些身高可以看作是男生身高的高斯分布和女生身高的高斯分布组成。因此变成了如何估计每个样例是男生还是女生，然后在确定男女生情况下，如何估计均值和方差，里面也给出了公式，有兴趣可以参考。
转自：
None/jerrylead/archive//04/06/936.html
