【机器学习】EM 期望最大化算法整理

小咪咪 2022-06-13 01:12 163阅读 0赞

极大似然估计，只是一种概率论在统计学的应用，它是参数估计的方法之一。说的是已知某个随机样本满足某种概率分布，但是其中具体的参数不清楚，参数估计就是通过若干次试验，观察其结果，利用结果推出参数的大概值。最大似然估计是建立在这样的思想上：已知某个参数能使这个样本出现的概率最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。

先假设这样一个问题：要求解人群（100人）中男女身高的分布，这里很明显有两种分布，男和女，但是事先我们并不知道他们服从哪种分布，而且我们也不知道男的有多少人，女的有多少人，那么怎么办呢？如果我们用混合高斯模型，我们假设男和女的分布都是符合高斯分布的，然后给定这个高斯分布一个初始值，这样这个高斯分布就是已知的了。接着，用这个已经的高斯分布来估计男的多少人，女的多少人，假设男和女的类别分布为Q(z)，这样我们就可以求Q(z)的期望了，用期望来表示下一次迭代类别的初始值，这样我们就知道男和女的所属类别了，我们就可以用最大似然函数来估新的高斯模型的参数了。重复上述步骤…直到收敛！

ps：极大似然估计，只是一种概率论在统计学的应用，它是参数估计的方法之一。说的是已知某个随机样本满足某种概率分布，但是其中具体的参数不清楚，参数估计就是通过若干次试验，观察其结果，利用结果推出参数的大概值。最大似然估计是建立在这样的思想上：已知某个参数能使这个样本出现的概率最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。

**EM算法**，这是cv界比较有名的一种算法了，虽然很早就听说过，但真正深究还是最近几天看斯坦福公开课笔记的时候。之所以EM和MoG放在一起，是因为我们在求解MoG模型的时候需要用到EM算法，所以这里我们先来介绍下EM算法。

在介绍EM算法的之前，我们先来普及下Jensen不等式的知识。首先我们来给出Jensen不等式的定义：

[![image][]][image 1]

定理很简单，总结下来就是这么几点。如果f是一个凸函数并且二阶导数大于零（上文中有提出），则有[![image][image 2]][image_image 2]。进一步， 若二阶导数恒大于 0，则不等式等号成立当且仅当 x=E\[x\]，即 x 是固定值。若二阶导数的不等号方向逆转，则不等式的不等号方向逆转。如下图：

[![image][image 3]][image_image 3]

好了，知道了Jensen不等式，我们下面来探讨EM算法的一般形式。

suppose we have a training set  [![image][image 4]][image_image 4] consist of  m independent examples，假设样本的类别z服从某种未知的分布，那么对于这种隐含变量的模型我们可以求出它的似然函数为（求似然函数是为了求解我们假设模型中的各个参数，我们在求解一个分类或者回归问题时，通常需要选定一个模型，比如NB，GDA，logistic regression，然后利用最大似然求解模型的参数）：

[![image][image 5]][image_image 5]

这里我们并不知道[![image][image 6]][image_image 6]所服从的分布，只知道它们服从某种概率分布就足够了。接下来我们需要求解参数[![image][image 7]][image_image 7]来使得以上的[![image][image 8]][image_image 8]最大即可，由于[![image][image 9]][image_image 9]中对数函数相加的情况使得求解非常困难。于是我们转化为下面这样处理：

[![image][image 10]][image_image 10]

式中我们引入了z的一种未知分布[![image][image 11]][image_image 11](怎么选择下面会讲)， 即[![image][image 12]][image_image 12]，继续推导我们有

[![image][image 13]][image_image 13]

上式中我们用到了Jensen不等式，由于log函数式一个凹函数，所以不等式的不等号要逆转了。简而言之就是：

[![image][image 14]][image_image 14]

也就是说[![image][image 15]][image_image 15]有一个下界，而这个下界中的对数已经放在了求和里面，因而求偏导比较容易。那么我们可不可以把minimum [![image][image 16]][image_image 16]转化为minimum lowbound呢。有了这个思想之后我们只需要证明即可。假设当前的参数为[![image][image 17]][image_image 17]，在下界上计算出极大似人函数的新的参数为[![image][image 18]][image_image 18]，如果能够保证[![image][image 19]][image_image 19]，我们就只需要在下界上进行极大似然估计就行了。证明如下：

[![image][image 20]][image_image 20]

这个式子前面几项不难理解，关键是最后的一个等式，怎么才能保证[![image][image 21]][image_image 21]呢？ 哈哈，还记得Jensen不等式里面等式成立的条件么，对的，就是这个x=E\[x\]，对应EM算法中就是要使

[![image][image 22]][image_image 22]

再加上条件[![image][image 23]][image_image 23]，对此式子做进一步推导，我们知道[![clip\_image067][clip_image067]][clip_image067_clip_image067]，那么也就有[![clip\_image069][clip_image069]][clip_image069_clip_image069],我们就可以这样选择Q(Z):

[![image][image 24]][image_image 24]

这样我们就可以选出对Z的概率估计Q了。于是我们就得到了EM算法的一半不周，如下：

[![image][image 25]][image_image 25]

为了便于理解，这里画一幅图来加深大家的印象

[![image][image 26]][image_image 26]

到此为此我们就用一个下界lowbound，通过在lowbound上求解最大似然函数，从而不断更新参数，最终解决EM算法的参数求解问题。

**Mixtures of Gaussians（GDA）**

混合高斯分布(MoG)也是一种无监督学习算法，常用于聚类。当聚类问题中各个类别的尺寸不同、聚类间有相关关系的时候，往往使用 MoG 更合适。对一个样本来说， MoG 得到的是其属于各个类的概率(通过计算后验概率得到)，而不是完全的属于某个类，这种聚类方法被成为软聚类。一般说来， 任意形状的概率分布都可以用多个高斯分布函数去近似，因而，MoG 的应用也比较广泛。

先来举一个例子帮助大家理解，如下图：

[![image][image 27]][image_image 27]

这是一个二维的高斯混合分布，数据点由均值为(-1,-2)和(1,2)的两个高斯分布生成。 根据数据点属于两个高斯分布的后验概率大小对数据点进行分类，可得下图所示的聚类结果：

[![image][image 28]][image_image 28]

在MoG中，由于事先我们不知道数据的分布情况，我们需要先提出两种假设：

假设 1 ：z 服从多项式分布， 即：

[![image][image 29]][image_image 29]

假设 2： 已知 z 时， x 服从正态分布，即条件概率 p(x|z)服从正态分布，即：

[![image][image 30]][image_image 30]

则 x 与 z 的联合分布概率函数为：

[![image][image 31]][image_image 31]

接下来求似然函数

[![image][image 32]][image_image 32]

利用似然函数求解参数的值

[![image][image 33]][image_image 33]

但是现在的问题是，我们的两个假设不一定是成立的，那么如果在事先不知道样本及其所属类别的分布情况是，我们又该怎么来求解各个参数的值呢。想到了没有，刚刚我们讲到的EM算法就是来解决这样一种问题的呀，所以我们想到了她-EM，就是水到渠成的事了。既然EM算法我们已经讲解了，那么现在就直接拿来解MoG就是了，步骤如下：

[![image][image 34]][image_image 34]

[![image][image 35]][image_image 35]

具体说来，在E-step中， Z的概率更新如下：

[![image][image 36]][image_image 36]

如假设所言，[![image][image 37]][image_image 37]是正态分布，[![image][image 38]][image_image 38]是多项式分布。

在 M-step中， 根据E-step得到的Z的分布情况，对参数进行重新估计：

[![image][image 39]][image_image 39]

[![image][image 40]][image_image 40]

这样通过不断的迭代，不断的更新参数，我们就可以求解出MoG模型的参数了。从分析过程来看，MoG对不确定分布的样本处理效果会比较好。

[image]: /images/20220613/c92fc31238d24f2380af8b6cbaee4944.png
[image 1]: https://images0.cnblogs.com/blog/673322/201411/141605029444982.png
[image 2]: https://images0.cnblogs.com/blog/673322/201411/141605046477769.png
[image_image 2]: https://images0.cnblogs.com/blog/673322/201411/141605042418711.png
[image 3]: https://images0.cnblogs.com/blog/673322/201411/141605055383441.png
[image_image 3]: /images/20220613/9766d6edc20f48eb8144cc76daf7842f.png
[image 4]: https://images0.cnblogs.com/blog/673322/201411/141605063031841.png
[image_image 4]: /images/20220613/b6e8b5fc3adb4e6191b86fdc350152cb.png
[image 5]: https://images0.cnblogs.com/blog/673322/201411/141605070851713.png
[image_image 5]: /images/20220613/15097ffc0cf0461fa39fcae47f6da1bb.png
[image 6]: https://images0.cnblogs.com/blog/673322/201411/141605077252842.png
[image_image 6]: https://images0.cnblogs.com/blog/673322/201411/141605074284284.png
[image 7]: https://images0.cnblogs.com/blog/673322/201411/141605082729643.png
[image_image 7]: https://images0.cnblogs.com/blog/673322/201411/141605079756384.png
[image 8]: https://images0.cnblogs.com/blog/673322/201411/141605089449015.png
[image_image 8]: https://images0.cnblogs.com/blog/673322/201411/141605086001742.png
[image 9]: https://images0.cnblogs.com/blog/673322/201411/141605095067886.png
[image_image 9]: /images/20220613/0ad521703d1841c589788ca536e8998d.png
[image 10]: https://images0.cnblogs.com/blog/673322/201411/141605104609044.png
[image_image 10]: /images/20220613/32f3a7bb56234588986e36fc8065fe12.png
[image 11]: https://images0.cnblogs.com/blog/673322/201411/141605111318415.png
[image_image 11]: https://images0.cnblogs.com/blog/673322/201411/141605108194088.png
[image 12]: https://images0.cnblogs.com/blog/673322/201411/141605121006344.png
[image_image 12]: /images/20220613/c47ed044578a46c8a4192e36fb065b67.png
[image 13]: https://images0.cnblogs.com/blog/673322/201411/141605133506060.png
[image_image 13]: /images/20220613/007c4a7a4ed146ed949a42703f827ca5.png
[image 14]: https://images0.cnblogs.com/blog/673322/201411/141605143198690.png
[image_image 14]: /images/20220613/6d58fcdaf4e74ab8b2b21cc8ed0f9510.png
[image 15]: https://images0.cnblogs.com/blog/673322/201411/141605152104362.png
[image_image 15]: https://images0.cnblogs.com/blog/673322/201411/141605146949505.png
[image 16]: https://images0.cnblogs.com/blog/673322/201411/141605158666963.png
[image_image 16]: https://images0.cnblogs.com/blog/673322/201411/141605155062919.png
[image 17]: https://images0.cnblogs.com/blog/673322/201411/141605166633606.png
[image_image 17]: https://images0.cnblogs.com/blog/673322/201411/141605164139063.png
[image 18]: https://images0.cnblogs.com/blog/673322/201411/141605172887963.png
[image_image 18]: https://images0.cnblogs.com/blog/673322/201411/141605169919406.png
[image 19]: https://images0.cnblogs.com/blog/673322/201411/141605179441565.png
[image_image 19]: /images/20220613/e895d9b5a9a14fbfb2f3ae5c73cf6db1.png
[image 20]: https://images0.cnblogs.com/blog/673322/201411/141605187563979.png
[image_image 20]: /images/20220613/85b7a03c8360469cbf6239049255dd46.png
[image 21]: https://images0.cnblogs.com/blog/673322/201411/141605195857865.png
[image_image 21]: https://images0.cnblogs.com/blog/673322/201411/141605191314793.png
[image 22]: https://images0.cnblogs.com/blog/673322/201411/141605204449994.png
[image_image 22]: /images/20220613/cb22da8abbba48c594fa949345bdd7c9.png
[image 23]: https://images0.cnblogs.com/blog/673322/201411/141605210695353.png
[image_image 23]: https://images0.cnblogs.com/blog/673322/201411/141605207726795.png
[clip_image067]: https://images.cnblogs.com/cnblogs_com/jerrylead/201104/201104061616254123.png
[clip_image067_clip_image067]: http://images.cnblogs.com/cnblogs_com/jerrylead/201104/201104061616259422.png
[clip_image069]: https://images.cnblogs.com/cnblogs_com/jerrylead/201104/20110406161626568.png
[clip_image069_clip_image069]: /images/20220613/c99fb1efc17f45489db73f3484b88878.png
[image 24]: https://images0.cnblogs.com/blog/673322/201411/141605219282781.png
[image_image 24]: /images/20220613/7f053b69713e49108698dfdd09813d6d.png
[image 25]: https://images0.cnblogs.com/blog/673322/201411/141605231009238.png
[image_image 25]: /images/20220613/7778383cb4094de09579b74fc6a3cb24.png
[image 26]: https://images0.cnblogs.com/blog/673322/201411/141605246473213.png
[image_image 26]: /images/20220613/e254bfd2e3fe4e16bd7473d4c4c4bc6f.png
[image 27]: https://images0.cnblogs.com/blog/673322/201411/141605257564184.png
[image_image 27]: /images/20220613/0d231286874f4a9498c9d4ba1b3849db.png
[image 28]: https://images0.cnblogs.com/blog/673322/201411/141605267569355.png
[image_image 28]: /images/20220613/6845dd7fd47d48db8f8ae0e732122993.png
[image 29]: https://images0.cnblogs.com/blog/673322/201411/141605280069071.png
[image_image 29]: /images/20220613/785e0303363f43ecbf2c1a0e11321057.png
[image 30]: https://images0.cnblogs.com/blog/673322/201411/141605289444459.png
[image_image 30]: /images/20220613/cc269b873a42428b8766bcc11fc1ae4e.png
[image 31]: https://images0.cnblogs.com/blog/673322/201411/141605300388658.png
[image_image 31]: /images/20220613/5f993e48d2c54448918a710b66996275.png
[image 32]: https://images0.cnblogs.com/blog/673322/201411/141605313353388.png
[image_image 32]: /images/20220613/2c253684cdad4ba3b1e52ab071d5f54d.png
[image 33]: https://images0.cnblogs.com/blog/673322/201411/141605326782132.png
[image_image 33]: /images/20220613/177bd7030c824256848e7524b73b94b8.png
[image 34]: https://images0.cnblogs.com/blog/673322/201411/141605352417048.png
[image_image 34]: /images/20220613/9f6a62f7c4184d7fb63d0d712fe7aad2.png
[image 35]: https://images0.cnblogs.com/blog/673322/201411/141605365381778.png
[image_image 35]: /images/20220613/f30131fce1a54785a84d67e7ab33eef3.png
[image 36]: https://images0.cnblogs.com/blog/673322/201411/141605374912936.png
[image_image 36]: /images/20220613/b4cdddd2f363407fb7e3a51a33667d70.png
[image 37]: https://images0.cnblogs.com/blog/673322/201411/141605384609864.png
[image_image 37]: https://images0.cnblogs.com/blog/673322/201411/141605380066793.png
[image 38]: https://images0.cnblogs.com/blog/673322/201411/141605391319236.png
[image_image 38]: /images/20220613/58b2389a22834698a553cf72ce63dcb9.png
[image 39]: https://images0.cnblogs.com/blog/673322/201411/141605400068137.png
[image_image 39]: /images/20220613/f59e2a72cfeb4150a8645bf604987430.png
[image 40]: https://images0.cnblogs.com/blog/673322/201411/141605409135281.png
[image_image 40]: /images/20220613/59f0c6037211499c9d7b6f8c6e54d840.png