“上帝的算法”在高斯混合分布中的应用

た入场券 2022-07-26 04:24 176阅读 0赞

吴军老师在《数学之美》中称期望最大值化算法为“上帝的算法”，下面就讨论EM算法在高斯混合分布中的应用。

**接[高斯判别分析与高斯混合分布之庖丁解牛（第一集）][Link 1]最后剩下的问题继续讨论，以下先不谈什么隐含因子，只是单纯的数学演算，过程非常有意思！**

**以下的讨论会用到几点知识，我们先作为补充知识，说一下**：

**补充知识点一：凹函数的定义：**

**设![20140402105233375][]是定义在![20140402105256312][]上的函数，若对任意的![20140402105325812][]和任意的![20140402105354531][]，如果满足以下条件，**

**![20140402105440765][]，**

**则称函数![20140402105233375][]在![20140402105256312][]上是凹函数。**

**补充知识点二：若函数![20140402105233375][]的二阶导数![20140402110500687][]在![20140402105256312][]上满足![20140402110642453][]，则函数是凹函数。显然![20140402110817406][]就是凹函数。**

**补充知识点三：jensen不等式：**

**若函数![20140402105233375][]在![20140402105256312][]上是凹函数，则对任意的![20140402111606609][],![20140402111622296][],且![20140402111656296][]，满足**

**![20140402111741984][]。**

**\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_**

设数据集

![20140402094108000][]

是以下高斯混合分布的样本点：

# ![20140402094443328][] #

我们接着给出该模型的似然函数的对数：

![20140402095043875][]

下面就是对上面对数似然函数的变形，然后引出高斯混合分布:

![20140402100613421][]

![20140402100630125][]，

我们只是同乘以一个![20140402101118968][],接着又除以一个![20140402101118968][]，所以等号成立，其中对任意的![20140402101303937][]  ，![20140402101348453][]，![20140402101118968][]满足以下条件：

![20140402101834906][]

**（注意：因为![20140402101118968][]在分母上，我们暂时先考虑![20140402102303015][]的情况。后面引出EM算法时，我们会去掉分母上的![20140402101118968][]。还有演算到这一步，我们发现这个最优化问题，理论上可以通过梯度下降，kuhn-tucker条件等算法求解，但是太困难，这便是EM算法提出的动机）**

根据**补充知识点二**，得出log(x)是凹函数，然后再根据补充**知识点三jensen不等式**，我们便得到：

![Center][]，

更有意思的是，当（下面的公式会很眼熟，就是EM算法的E步）

**![Center 1][]**

时，等号成立。

E步，推出来了，那么M步就好做了，我不再仔细推了，直接给出M步：

![20140402114951343][]

**注意：在这一步，我们就把分母上的![20140402101118968][]去掉了。为什么去掉，还有为什么收敛，我就不啰嗦了！迭代步骤示意图：**

**![20140402115514687][]**

**以上便是“上帝的算法”**

————————————————————————————————————————————————————————————————————————————

学习EM算法参考资料：

1.【book】:Pattern Recognition and Machine Learning 第九章，这一章还讨论为什么k-均值聚类算法也是EM算法特例

2.Andrew Ng老师的讲义，及公开课视频教程

[Link 1]: http://blog.csdn.net/zhangping1987/article/details/22648215
[20140402105233375]: https://img-blog.csdn.net/20140402105233375
[20140402105256312]: /images/20220724/2548f3395ca44ec48048ceef17eaf2ca.png
[20140402105325812]: https://img-blog.csdn.net/20140402105325812
[20140402105354531]: /images/20220724/87eaa7d3fc694acdbdf040856a636cd2.png
[20140402105440765]: /images/20220724/95fbf8710ee241fc89a19d25ccf8ab27.png
[20140402110500687]: https://img-blog.csdn.net/20140402110500687
[20140402110642453]: https://img-blog.csdn.net/20140402110642453
[20140402110817406]: /images/20220724/da058e9a46724c89a6842bc6a39e1e13.png
[20140402111606609]: https://img-blog.csdn.net/20140402111606609
[20140402111622296]: https://img-blog.csdn.net/20140402111622296
[20140402111656296]: /images/20220724/e447021760fd4a0d84d5c3dffc60ea5c.png
[20140402111741984]: /images/20220724/d0a0fc5ed46b4d7dae47e3d81999f37f.png
[20140402094108000]: /images/20220724/10e34bc103454925b87cba6822529532.png
[20140402094443328]: /images/20220724/0d58e5a251954d039f1fafb2a49b1a2a.png
[20140402095043875]: /images/20220724/9d4189f1dc874ae388302267ee5c9596.png
[20140402100613421]: /images/20220724/415283c0201b4586a806e4f3f0870f7b.png
[20140402100630125]: /images/20220724/8737ba37fec3433a981ad7739cd2e66c.png
[20140402101118968]: /images/20220724/686d096e5e974393bd5d2a1e884890be.png
[20140402101303937]: https://img-blog.csdn.net/20140402101303937
[20140402101348453]: https://img-blog.csdn.net/20140402101348453
[20140402101834906]: /images/20220724/3022f41c0c224976be5f31af4b82f028.png
[20140402102303015]: https://img-blog.csdn.net/20140402102303015
[Center]: /images/20220724/0be5be38275d4d8e806bd391a2c5cccd.png
[Center 1]: /images/20220724/358efa82731c46fda84c71399142ccca.png
[20140402114951343]: /images/20220724/b47851434b114f3297c398810e854dc5.png
[20140402115514687]: /images/20220724/2b35a0d4b03a4ae286379d33baebe7cd.png