code前端网十大经典机器学习算法详解：EM算法
EM算法的英文全称是Expectation-Maximization最大期望算法，最大期望算法或算法EM算法被称为机器学习算法之一十大机器学习算法。光听这个名字就知道不凡。我读了很多博客和资料，但是很少有资料能够清楚地解释这个算法的微妙之处以及其推导的细节，所以今天我正在阅读所长的各种书籍，并试图尽可能清楚地解释它。
从本质上来说，EM 算法是最大似然估计法的高级版本。还记得最大似然估计吗？我们在之前介绍贝叶斯模式的文章中提到过这一点。让我们简单回顾一下。一次。 假设我们现在有一枚硬币，我们想知道抛硬币后正面朝上的概率，所以我们抛硬币 10 次并进行实验。发现的匝数为5次，的匝数也为5次。所以我们认为硬币每次落地正面的概率是50%。 从表面上看，这个结论很正常，应该被视为理所当然。但当我们仔细分析时，我们发现它是有问题的。问题是我们所做的实验结果和实验参数没有强关联。这意味着如果硬币被篡改，正面朝上的概率为 60%。如果我们滚动 10 次，就有可能得到 5 个正面和 5 个反面。同样，如果正面的概率为 70%，我们也有一定概率得到 5 个正面和 5 个反面的结果。既然得到了这样的结果，怎么解释一定是50%概率的上涨呢？ 那么我们该怎么办，继续实验呢？ 显然，无论我们做多少实验，都无法从根本上解决这个问题。既然参数影响结果的概率，那么我们应该回到这个角度，从概率的角度开始。我们知道，抛硬币是一个二项分布事件。我们假设正面的概率为p，那么反面的概率为1-p。所以我们可以输入二项式分布公式，计算在当前参数p下，10次抛掷后出现5个正结果的概率，10次抛掷中正面朝上的概率最高最大似然估计
也就是说，我们使用实验结果和概率 来查找导致该结果的最可能的原因或参数 。这称为最大似然估计。
明白了原理，解决方案也就水到渠成了。
首先，我们需要用一个函数来表达实验结果的概率。这个函数的学名叫做概率函数。
一旦我们有了一个函数，我们就需要简化它。例如，对于一些进行多次的实验，我们需要求似然函数的对数，将累积乘法计算转化为累加运算等。
最后，我们推导简化的似然函数，设置导数到0，并找到极值点处的参数值，这就是我们使用最大似然估计方法找到的最佳参数。
引入潜在变量
以上只是最大似然估计的基本应用。如果我们稍微改变一下问题并引入一个变量，会发生什么？
让我们看一个经典的例子。同样是抛硬币，但是如果我们稍微修改一下题目条件，整个问题就会完全不同。
这个例子来自一篇解释 EM 算法的经典论文： 《Do, C. B., & Batzoglou, S. (2008). What is the expectation maximization algorithm?. Nature biotechnology, 26(8), 897.》在这个例子中我们有两个硬币 A 和 B。硬币 A 正面朝上的概率和硬币 B 正面朝上的概率是 我们随机选择其中之一两枚硬币用于实验。
每个实验总共进行5次，并记录正面和背面的数量。经过5轮实验，我们得到了以下结果：
由于我们知道每一轮选择了哪些币进行实验，所以整个过程还是很顺利的。如果我们删除有关硬币的信息，假设我们不知道每轮选择了哪些硬币来进行实验，我们如何找到A和B正面朝上的概率？
在新的实验中，我们不知道硬币选择情况，这意味着在实验中隐藏了一个我们无法知道的变量。这种变量称为潜变量。隐变量的存在打破了参数与实验结果之间的直接关系。例如，在这个问题中，我们想知道每枚硬币正面朝上的概率。为了计算这个概率，我们首先需要知道每轮使用哪种硬币。为了计算每个实验中使用的是哪种硬币，我们首先需要知道硬币正面落地的概率。换句话说，这两个变量是相互交织且相互依存的。我们掌握的信息太少，无法直接破译。这就像问先有鸡还是先有蛋一样，陷入了无限循环。
EM算法就是为了解决这个问题而诞生的。
EM 算法
正如我们之前所说，我们想要请求的隐藏变量和参数相互交织在一起，形成一个无限循环，但是我们已经拥有的信息不足以让我们解决这个纠结。既然无法解决，我们也不懂，所以直接通过暴力破解。
是的，您没看错。 EM 算法的本质非常简单粗暴：因为我们无法求解隐藏变量，所以我们不需要它们。我们直接假设一个初始值并将其插入到计算中，我们就得到了结果。然后重复。
例如，假设 p1 是硬币 A 正面朝上的概率，p2 是硬币 B 正面朝上的概率。本来我们希望用最大似然估计来求解p1和p2，这样就可以得到结果了。现在我们直接假设并迭代：
假设p1=，p2=，我们任意假设这个值，你可以假设你想要的。其他值。我们代入上述结果中的p1和p2进行计算。
例如，第一轮，结果是3个正面和2个反面。如果是硬币A，根据二项式分布可以很容易地计算出这样的结果的概率：^3 * ^2 = 0.030870.73*0.32=0.03087，同理，我们可以计算出硬币B的概率。为了计算所有概率，我们使用相同的方法：
现在我们有了概率，我们当然可以根据这个概率表来预测和猜测每轮使用了哪种硬币。
根据最大似然定律，我们可以得出每轮使用的硬币为：
第一轮是硬币 A
第二轮是硬币 ‶❙❙ 第三轮是硬币B
第四轮是硬币A
第五轮是硬币BB
算命有什么用？很简单，我们可以用猜测的结果来重新估计p1和p2的值。
例如，硬币A出现在第一轮和第四轮。这两轮总共进行了10次实验，其中6次为正面，4次为反面。然后我们可以将p1的值修正为。硬币B出现在第2、3、5轮中。这三轮中，进行了15次实验，总共5次正面，10次反面，所以正面的概率是1/3。可以发现，经过一次迭代，我们的结果更加接近的真实值。
虽然结果还不错，但是这个方法还是比较粗糙，我们有更好的方法。
改进示例
我们来改进上面示例的计算过程。主要问题是，我们根据预测概率计算出分布后，直接使用概率估计来估计当前轮中滚动了哪一个。硬币。这当然是可能的，但对我来说似乎不够准确，因为我们的直接估计有些武断并且不一定准确。
有更好的办法吗？
它确实存在。与直接猜测特定回合中选择了哪种硬币相比，我们可以使用硬币选择概率来计算期望。这样效果会比较好，比如根据现在的计算结果，我们可以计算出每一轮选择硬币的概率：
我们会用这个概率来计算实验结果中的期望，我们可以得到期望表p1：
p_1 = \ frac{2.1+ +0.0729+2.1+}{}=90p1=2.7+2.7+0.292+2.7+2.72.1+0.6+0.0729+2.1+0.6=0。
以同样的方式我们可以计算出新的p2期望表：通过替换
我们得到新的p2是77。
将估计结果更改为使用概率进行迭代后，我们估计的结果更加准确，这意味着我们的收敛速度更快。我们重复上述过程直到收敛。当收敛发生时，我们可以得到最大似然估计最大时的p1和p2的值。这也是整个EM算法的精髓。
我们来解决一下EM算法的运行过程。首先，我们随机将一个参数值插入到实验结果中，计算概率分布或隐藏变量值，然后通过隐藏变量迭代我们的参数值并重复迭代直到收敛。我们可以进一步将其抽象并总结为两个步骤，即步骤 E 步骤和步骤 M ：
在步骤 E 中，我们根据假设的参数值计算未知变量的预期估计。 ，应用于隐藏变量
在步骤M中，我们根据隐藏变量
的估计值计算当前参数的最大似然估计，根据这个理论，我们还可以改进上述过程。
这个方法就介绍到这里了。我想大家应该都能理解这一点，但是我们还没有从数学上证明这一点。为什么这个操作有效？为什么这个方法要强制收敛呢？我们收敛的值是否是最优解？所以我们还是要用数学来证明。
数学证明
假设我们有一个由 m 个样本组成的样本集 X。可以写成 ,⋯xm}，对于这 m 个样本，它们都有一个未知的隐藏变量 z。还有一个参数θ，这是我们希望使用最大似然估计求解的参数。因为它包含一个隐藏变量z，所以我们不能直接导出概率函数的极值并计算它。
首先我们写出包含隐藏变量的概率函数：
P_i = P(x_i, z_i; \theta)Pi=P(xi,zi;θ)
我们希望找到全局optimization 最优参数 \thetaθ，所以我们希望找到最大值 \prod_{i=1}^mP_i∏i=1mPi。我们求这个公式的对数，可以得到：
\sum_{i=1} ^m\log P_i= \sum_{i=1}^m \log \sum_{z_i}P(x_i, z_i; \theta)i =1ΣmlogPi=i=1ΣmlogziΣ P(xi,zi;θ)
我们假设隐藏变量 z 的概率分布为 Q_iQi，所以上面的公式可以转换为：
\sum_{i=1}^m\log P_i= \sum_ {i=1}^m \log \sum_{z_i}Q_i(z_i)\frac{P( x_i, z_i; \theta)} {Q_i(z_i)}i=1ΣmlogPi=i=1Σ mlogziΣQi(zi)Qi(zi)P(xi, zi;θ)
看起来我被困在这里了，但我没有。我们在之前的文章中写过，对于凸函数，存在 Jensen 不等式 ：E[f(x)] >= f(E[x])，因此函数的期望值 为大于或等于期望值函数值。对数函数广义上是凸函数，狭义上是凹函数。它可以使用Jensen不等式，但不等号的方向需要改变。
上式中，Q_i(z_i)Qi(zi)是隐变量的概率分布，所以\sum_{z_i}Q_i(z_i)[\frac{P(x_i, z_i; \theta) {Q_i ( z_i)}]ΣziQi(zi)[Qi(zi)P(xi,zi;θ)] 是\frac{P( x_i, z_i; \theta)}{Q_i ( z_i)}Qi(zi)P(xi,zi;θ)期望，因此我们可以代入 Jensen 不等式并得到：
\sum_{i =1}^m\log P_i \geq \ sum_ {i=1}^m \sum_{z_i}Q_i(z_i)\log \frac{P(x_i, z_i; \theta)}{Q_i(z_i)}i =1ΣmlogPi ≥i=1 Σ mziΣQi(zi)logQi(zi)P(xi,zi;θ)
右边的公式上述不等号的求解就容易多了。当我们固定 z 变量时，我们可以很容易地求解出似然最大时的参数θ。同理，当我们有\thetaθ的值时，我们就可以优化z，这种固定两个变量之一，优化另一个变量的方法称为坐标上升法，这也是一种非常好的方法。机器学习中常见的解决方法。
如上图所示，这个圆就是损失函数的轮廓。当我们使用坐标升序法时，我们每次固定一个轴的变量，优化另一个变量，然后交替进行。我们也可以获得全局最优解。
另外，我们还可以用数学来解释。
由于上面的公式是一个不等式，所以我们没有办法直接求解左边的最大值，所以我们用不断优化右边的公式，逼近左边的最大值 .我们留下左边的一系列公式L(\theta)L(θ)和不等号右边的公式J(z,\theta)J(z,θ)，然后看图，这张图这是我从大师博客上找到的神图：
上图中上部红色为L(\theta)L(θ)，下部图像为J。每次固定z时，我们可以找到更好的θ，因此J(z,θ)J(z,θ)不断逼近最高点，最终达到最大值。
直观上来说，这没问题，但我们仍然需要在数学上证明它。
根据 Jensen 不等式，只有当 自变量 x 是常数 时才能实现相等。我们的自变量是 \frac{P(x_i, z_i; \theta)}{Q_i(z_i) }Qi(zi)P(xi,zi;θ)，我们将使其等于常数 c :
\frac{P(x_i, z_i, \theta)}{Q_i(z_i)} = cQi (zi)P(xi,zi,θ)=c
Since\sum_{ z_i }Q_i( z_i)=1ΣziQi(zi)=1，所以我们可以知道 \sum_{z_i}P(x_i,z_i, \theta)=cΣziP(xi ,zi ,θ) =c，代入上式可得：
\begin{aligned} Q_i (z_i)\cdot c &= P(x_i, z_i, \theta) \\ Q_i( z_i) &=\frac{P( x_i.z_i; \theta)}{c}\\ Q_i(z_i) &= \frac{P(x_i.z_i; \theta)}{\sum_{z_i}P(x_i , z_i ; \theta)}\\ Q_i(z_i) &= \frac{P(x_i.z_i; \theta)}{ P(x_i; \theta)}\\ Q_i(z_i) &= P(z_i|x_i ; \theta)\\ \end{ 对齐}Qi(zi)⋅cQi(zi)Qi(zi )Qi(zi)Qi(zi)=P(xi,zi , θ)=cP(xi .zi;θ)=ΣziP(xi,zi; θ)P(xi.zi;θ)=P(xi;θ)P ( xi.zi;θ )=P(zi∣xi;θ)
经过弦变形后，我们得到计算公式 Q_i(z_i)Qi(zi) 实际上是 后验概率 。这一步就是我们刚才介绍的E步骤。然后，确定 Q_i(z_i)Qi(zi) 后，我们在最大化函数的同时，使用导数和极值方法求出 \thetaθ，正好是 M 步。
所以EM算法的整个过程就是重复这个过程直到收敛。
那么如何保证算法能够收敛呢？其实并不难。由于我们在执行步骤E得到z时遵循Jensen不等式的等式条件，所以我们可以保证我们能够得到一个等式，即：
L(\theta_t) = \sum_{i=1}^m \ suma_ {z_i}Q_i (z_i)\log \frac{P(x_i, z_i; \theta_t)}{Q_i(z_i)}L(θt)=i=1Σmzi ΣQi(zi ) logQi(zi )P(xi,zi;θt)
当我们固定 Q_i(z_i)Qi(zi) 时，我们可以通过导数 Po \theta_{t+ 1} 推导出最大化参数θt+1，我们得到正确的公式 ，它一定比 L(\theta)L(θ) 更好，但是我们不能确定对于新的 \theta_{t+1}θt+1 我们的分布前面的 Q_i(t_i)Qi(ti) 也可以满足 Jensen 不等式的等式条件，因此：
\begin{aligned} L(\theta_{t+1}) &\geq \sum_{ i=1 }^m \sum_{z_i}Q_i(z_i)\log \frac{P(x_i, z_i; \theta_{t+1})}{Q_i(z_i)}\\ &\geq \ sum_{i =1} ^m \sum_{z_i}Q_i(z_i)\log \ frac{P(x_i, z_i; \theta_{t})}{Q_i(z_i)} \\ &=L(\theta) \end{ 对齐}L (θt+1)≥i=1Σm ziΣQi(zi)logQi(zi)P(xi,zi;θt+1) ≥i= 1Σm ziΣQi(zi)logQi( zi)P(xi,zi;θt)=L(θ)
这样我们就证明了相似于自然的值功能增加。当它最终收敛时，它就是最大似然估计的值。此时的θ参数就是我们需要的最大似然估计方法得到的参数。
总结
至此，EM算法就介绍完了。整个算法我最大的感受就是它又是一个基于数学推理的算法。它的推导过程非常严格，效果也非常好。它可以解决很多直观无法解决的问题。而且更罕见的是，即使我们放弃数学上严格的证明和推导，也不妨碍我们直观地理解算法的思想。难怪这个算法可以被列为十大机器学习算法之一。这确实是一个经典。
总之，我想知道您在观看时是否有一种感觉，您以前在哪里见过EM算法的想法？感觉很熟悉吗？
这种感觉是对的。如果你回想一下上面提到的 Kmeans，你会发现我们一开始可能是在猜测，因为我们不知道簇的中心。然后通过迭代一点点接近它。如果你再思考一下，你会发现计算Kmeans的过程可以通过EM算法的过程来证实。
版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
