EM算法(讲解+程序)

分类em算法摘要：1.引言2.EM 算法的基本原理3.EM 算法的分类应用4.结论正文：1.引言EM 算法，全称Expectation-Maximization 算法，是一种常见的概率模型优化算法。

该算法在统计学、机器学习等领域具有广泛的应用，特别是在分类问题上表现出色。

本文将重点介绍EM 算法在分类问题上的应用及其基本原理。

2.EM 算法的基本原理EM 算法是一种迭代优化算法，主要通过两个步骤进行：E 步（Expectation）和M 步（Maximization）。

在E 步中，根据观测数据计算样本的隐含变量的期望值；在M 步中，根据隐含变量的期望值最大化模型参数的似然函数。

这两个步骤交替进行，直至收敛。

EM 算法的基本原理可以概括为：对于一个包含隐含变量的概率模型，通过迭代优化模型参数，使得观测数据的似然函数最大化。

在这个过程中，EM 算法引入了Jensen 不等式，保证了算法的收敛性。

3.EM 算法的分类应用EM 算法在分类问题上的应用非常广泛，典型的例子包括高斯混合模型（GMM）和隐马尔可夫模型（HMM）。

（1）高斯混合模型（GMM）在传统的分类问题中，我们通常使用极大似然估计（MLE）来求解最佳分类模型。

然而，当数据分布复杂时，MLE 可能无法得到一个好的解。

此时，我们可以引入EM 算法，通过迭代优化模型参数，提高分类的准确性。

在GMM 中，EM 算法可以有效地处理数据的多峰分布，从而提高分类效果。

（2）隐马尔可夫模型（HMM）HMM 是一种基于序列数据的概率模型，广泛应用于语音识别、时间序列分析等领域。

在HMM 中，EM 算法被用于求解最优路径和状态转移概率。

通过EM 算法，我们可以有效地处理观测序列与隐状态之间的不确定性，从而提高分类效果。

4.结论EM 算法作为一种强大的概率模型优化算法，在分类问题上表现出色。

通过引入隐含变量和迭代优化，EM 算法可以有效地处理数据的复杂性和不确定性，提高分类的准确性。

EM算法-完整推导前篇已经对EM过程,举了扔硬币和⾼斯分布等案例来直观认识了, ⽬标是参数估计, 分为 E-step 和 M-step, 不断循环, 直到收敛则求出了近似的估计参数, 不多说了, 本篇不说栗⼦, 直接来推导⼀波.Jensen 不等式在满⾜:⼀个 concave 函数, 即形状为 "⋂" 的函数f(x)λj≥0∑jλj=1 类似于随机变量的分布的前提条件下, 则有不等式:f(∑jλj x j)≥∑jλj f(x j)恒成⽴, 则该不等式称为 Jensen 不等式. 是有些不太直观哦, (sum 是最后哦, 有时候会犯晕).为了更直观⼀点, 考虑λ只有两个值, 即:λ1=1−tλ2=1其中,0⩽"\bigcap" 函数 f(x) 中有⼀段区间 [a, b], 构造出该范围内的⼀个点x_t当, x_t = (1+t)a + tb则有:f((1-t)a +tb) \ge (1-t)f(a) + tf(b)这⾥跟之前写过的 convex 其实是⼀模⼀样的, 要是还不直观, 就⾃个画个草图就秒懂了.左边是函数的值, 右边连接两个端点a,b的函数值的直线, 因为是 "\bigcap 的", 故函数值必然在直线的上⽅.⽤数学归纳法, 当 M > 2:f(\sum \limits _{j=1}^M \lambda_j x_j) \ge \sum \limits _{j=1}^M \lambda_j f(x_j)EM算法推导假设给定⼀个包含 n 个独⽴的训练样本的数据集, D = \{ x_1, x_2, x_3...x_n) \}希望拟合⼀个概率模型p(x, z) , 其对数似然函数(log likelihood)为:为啥要 log, 乘法变加法, 不太想说了, ⾃⼰都重复吐⾎了似然, 不加log 前是: l(\theta) = \prod \limits _{i=1}^n p(x; \theta)的嘛, 样本的联合概率最⼤l(\theta) = \sum \limits _{i=1}^n log \ p(x; \theta)= \sum \limits _{i=1}^n log \ \sum \limits _{z} p(x, z; \theta)理解\sum \limits _{z} p(x, z; \theta)给定\theta的前提下, 关于 x, z 的联合概率跟之前扔硬币是⼀样的, 对于每个独⽴数据的产⽣, 其实还有⼀个隐含的因素 z (扔硬币中,到底这次试验是来⾃于硬币A 还是硬币B每个Z因素, 影响着 p(x,z) 的联合概率分布. 考虑所有的 z, 则是全概率了呀.对于p(x; \theta)直接通过 x 来观测\theta⽐较难 (扔硬币中, 没有上帝视⾓, 不知道扔结果是哪个硬币产⽣的)z^{(i)}是⼀个隐变量(latent), 如果能观测到z^{(i)}则参数预测会容易很多, EM算法就是来解决这个问题的EM 算法呢, 分为两个步骤:在 E 步中, 构建l(\theta)的下界函数 (给定\theta来找 z)在 M 步中, 最⼤化这个下界函数不太直观, 就回顾上篇扔硬币的栗⼦, 这⾥的 z 就是那个来⾃哪⾥A 还是 B 的概率(每次试验)设Q_i为关于 z 的概率分布, 即\sum \limits _{z} Q_i(z) = 1 (z 如是连续变量则\sum \rightarrow \int_z) ,则对于上⾯的对数似然函数:= \sum \limits _{i=1}^n log \ \sum \limits _{z} p(x_i, z_i; \theta) \ (1)对 p 的部分, 同时乘上和除以Q_i(z_i)不改变等式 , 这种技巧, 中学的 "配平⽅或数列裂项求和" ⼀样滴= \sum \limits _i log \sum \limits _{z_i} Q_i(z_i) \frac {p(x_i, z_i; \theta)}{Q_i(z_i) } \ (2)log 函数是 concave 的, 联想 jensen不等式f(\sum \limits _j \lambda_j x_j) \ge \sum \limits _j \lambda_j f(x_j)即 log 对于与 f(); \sum \limits _{z_i} Q_i(z_i) 对应于 \sum \limits _j \lambda_j ; 最后⼀项对x_j\ge \sum \limits_{i} \sum \limits_{z_i}Q_i(z_i) \ log \frac {p(x_i, z_i; \theta)}{Q_i(z_i) } \ (3)就类似与, 把⼀个, 函数⾥⾯的参数, 提取到函数外⾯来. 如还是不理解, 回看之前写的 convex 篇什么时候会取到等于?即当\frac {p(x_i, z_i; \theta)}{Q_i(z_i) } = c是个常数的时候, (2) 和 (3) 是相等的.即p(x_i, z_i; \theta) = c \ * Q_i(z_i)在\theta给定下, 关于 x, z 的联合概率分布与隐变量 z 的分布是⼀个线性关系因为\sum \limits_{z_i} Q_i(z_i) = 1, 如果将Q_i(z_i)认为是给定x_i 和 z_i的后验概率分布, 这样就得到了该似然函数的⼀个下界,根据全概率(后验) 与贝叶斯公式:Q_i(x_i) = \frac {p(x_i, z_i; \theta)}{\sum \limits _{z_i} p(x_i, z_i; \theta)}=\frac {p(x_i, z_i; \theta)}{p(x; \theta)}=p(z_i|x_i, \theta)相当于求给定\theta 和 x_i的情况下, 求 z_i 的条件概率, 果然, 深刻理解贝叶斯公式显得多么重要呀再回顾⼀波贝叶斯公式:设A1,A2,A3..构成完备事件组, 则对任意⼀事件B有:P(A_i|B) = \frac {P(A_i)P(B|A_i)}{\sum \limits _{i=1}^n P(A_i)P(B|A_i)}同上述, 只要当我们取Q_i(z_i)的值为给定\theta 和 x_i的后验概率分布的时候, 就能保证:\frac {p(x_i, z_i; \theta)}{Q_i(z_i) }的值是⼀个常数 (反过来推的), 既然是个常数, 也就**前⾯ (3) 的地⽅可以取等号啦, 即: **\sum \limits _{i=1}^n log \ \sum \limits _{z} p(x_i, z_i; \theta) = \sum \limits_{i} \sum \limits_{z_i}Q_i(z_i) \ log \frac {p(x_i, z_i; \theta)}{Q_i(z_i) }这样⼀来, 相当于在 E 步得到了似然函数的⼀个下界, 然后在 M 步, 求解(3) 最⼤值时候的参数\theta . 然后重复以上的 E, M 步骤:E-步: For each i:Q_i(z_i) = p(z_i | x_i; \theta)M-步, 更新\theta:\theta = arg \ max _\theta \sum \limits_{i} \sum \limits_{z_i}Q_i(z_i) \ log \frac {p(x_i, z_i; \theta)}{Q_i(z_i) }....循环直到收敛, 则估计出了参数\theta但, 万⼀不收敛呢?, so, 必须证明⼀波, EM算法是收敛的哦证明EM算法会收敛假设\theta^{(t)} 和 \theta^{(t+1)}为EM算法的连续两个步骤的参数值, 欲证l (\theta)收敛, 只需证:l(\theta^{(t)}) \leq l(\theta^{(t+1)})即可EM算法使得似然函数的值单调递增即可根据前⾯关于⽤ jensen不等式的取等条件, 推导出, 取得Q_i(z_i)^{(t)}的⽅式是:Q_i ^{(t)} (z_i) = p(z_i | x_i; \theta ^{(t)})此条件下, 使得jensen不等式取等即:l(\theta^{(t)}) = \sum \limits_{i} \sum \limits_{z_i}Q_i(z_i) \ log \frac {p(x_i, z_i; \theta ^t)}{Q_i(z_i) }⽽参数\theta^{(t+1)}的取值⽅式, 是使得上⾯的这个等式的值最⼤, 则必然l(\theta^{(t+1)}) \ge l(\theta^{(t)})展开⼀波:l(\theta^{(t+1)}) \ge \sum \limits_{i} \sum \limits_{z_i}Q_i^t(z_i) \ log \frac {p(x_i, z_i; \theta ^{(t+1)})}{Q_i^t(z_i) } \ (4)\ge \sum \limits_{i} \sum \limits_{z_i}Q_i^t(z_i) \ log \frac {p(x_i, z_i; \theta^t)}{Q_i^t(z_i) }\ (5)=l(\theta^{(t)}) \ (6)(4) 源于不等式的性质, 必然成⽴嘛(5) 就是取最⼤值的⼀个过程必然成⽴(6) 取相等的⽅式去是应⽤了 Jensen不等式即证明了l(\theta^{(t)}) \leq l(\theta^{(t+1)}) , 即EM算法是收敛的呀.⼩结⾸先是要理解,参数估计的是在⼲嘛, 需要回顾统计学的基础知识, 或理解上篇扔硬币的栗⼦核⼼, ⽤到了⼀个jensen 不等式, 需要回顾凸函数的⼀些性质来理解⼀波推导的⽅式呢, 依旧是极⼤似然估计, 带log (乘法边加法)推导核⼼技巧是全概率与贝叶斯公式, 真正理解太重要, 如LDA, 逻辑回归, 贝叶斯...这些算法都⽤到了.证明收敛, 其实只是⼀些, 推理的技巧, 还是挺有意思的.总体上, EM算法, 理解起来,我感觉不是很容易, 但, 也没有想象的那样难, 只要肯坚持, 正如爱因斯坦所说的那样嘛, 当然也为了⾃勉⽬前在经济和精神双重困境中的⾃⼰:耐⼼和恒⼼, 总会获得收获的Loading [MathJax]/jax/element/mml/optable/SuppMathOperators.js。

【机器学习】EM算法详细推导和讲解 今天不太想学习，炒个冷饭，讲讲机器学习⼗⼤算法⾥有名的EM算法，⽂章⾥⾯有些个⼈理解，如有错漏，还请读者不吝赐教。

众所周知，极⼤似然估计是⼀种应⽤很⼴泛的参数估计⽅法。

例如我⼿头有⼀些东北⼈的⾝⾼的数据，⼜知道⾝⾼的概率模型是⾼斯分布，那么利⽤极⼤化似然函数的⽅法可以估计出⾼斯分布的两个参数，均值和⽅差。

这个⽅法基本上所有概率课本上都会讲，我这就不多说了，不清楚的请百度。

然⽽现在我⾯临的是这种情况，我⼿上的数据是四川⼈和东北⼈的⾝⾼合集，然⽽对于其中具体的每⼀个数据，并没有标定出它来⾃“东北⼈”还是“四川⼈”，我想如果把这个数据集的概率密度画出来，⼤约是这个样⼦： 好了不要吐槽了，能画成这个样⼦我已经很⽤⼼了= = 其实这个双峰的概率密度函数是有模型的，称作⾼斯混合模型（GMM），写作： 话说往博客上加公式真是费劲= =这模型很好理解，就是k个⾼斯模型加权组成，α是各⾼斯分布的权重，Θ是参数。

对GMM模型的参数估计，就要⽤EM算法。

更⼀般的讲，EM算法适⽤于带有隐变量的概率模型的估计，什么是隐变量呢？就是观测不到的变量，对于上⾯四川⼈和东北⼈的例⼦，对每⼀个⾝⾼⽽⾔，它来⾃四川还是东北，就是⼀个隐变量。

为什么要⽤EM，我们来具体考虑⼀下上⾯这个问题。

如果使⽤极⼤似然估计——这是我们最开始最单纯的想法，那么我们需要极⼤化的似然函数应该是这个： 然⽽我们并不知道p(x;θ)的表达式，有同学说我知道啊，不就是上⾯那个混个⾼斯模型？不就是参数多⼀点麽。

仔细想想，GMM⾥的θ可是由四川⼈和东北⼈两部分组成哟，假如你要估计四川⼈的⾝⾼均值，直接⽤GMM做似然函数，会把四川⼈和东北⼈全考虑进去，显然不合适。

另⼀个想法是考虑隐变量，如果我们已经知道哪些样本来⾃四川，哪些样本来⾃东北，那就好了。

⽤Z=0或Z=1标记样本来⾃哪个总体，则Z就是隐变量，需要最⼤化的似然函数就变为： 然⽽并没有卵⽤，因为隐变量确实不知道。

EM算法（坐标上升算法）⼗⼤算法之⼀：EM算法。

能评得上⼗⼤之⼀，让⼈听起来觉得挺NB的。

什么是NB啊，我们⼀般说某个⼈很NB，是因为他能解决⼀些别⼈解决不了的问题。

神为什么是神，因为神能做很多⼈做不了的事。

那么EM算法能解决什么问题呢？或者说EM算法是因为什么⽽来到这个世界上，还吸引了那么多世⼈的⽬光。

我希望⾃⼰能通俗地把它理解或者说明⽩，但是，EM这个问题感觉真的不太好⽤通俗的语⾔去说明⽩，因为它很简单，⼜很复杂。

简单在于它的思想，简单在于其仅包含了两个步骤就能完成强⼤的功能，复杂在于它的数学推理涉及到⽐较繁杂的概率公式等。

如果只讲简单的，就丢失了EM算法的精髓，如果只讲数学推理，⼜过于枯燥和⽣涩，但另⼀⽅⾯，想把两者结合起来也不是件容易的事。

所以，我也没法期待我能把它讲得怎样。

希望各位不吝指导。

⼀、最⼤似然扯了太多，得⼊正题了。

假设我们遇到的是下⾯这样的问题：假设我们需要调查我们学校的男⽣和⼥⽣的⾝⾼分布。

你怎么做啊？你说那么多⼈不可能⼀个⼀个去问吧，肯定是抽样了。

假设你在校园⾥随便地活捉了100个男⽣和100个⼥⽣。

他们共200个⼈（也就是200个⾝⾼的样本数据，为了⽅便表⽰，下⾯，我说“⼈”的意思就是对应的⾝⾼）都在教室⾥⾯了。

那下⼀步怎么办啊？你开始喊：“男的左边，⼥的右边，其他的站中间！”。

然后你就先统计抽样得到的100个男⽣的⾝⾼。

假设他们的⾝⾼是服从⾼斯分布的。

但是这个分布的均值u和⽅差∂2我们不知道，这两个参数就是我们要估计的。

记作θ= [u, ∂]T。

⽤数学的语⾔来说就是：在学校那么多男⽣（⾝⾼）中，我们独⽴地按照概率密度p(x|θ)抽取100了个（⾝⾼），组成样本集X，我们想通过样本集X来估计出未知参数θ。

这⾥概率密度p(x|θ)我们知道了是⾼斯分布N(u,∂)的形式，其中的未知参数是θ=[u, ∂]T。

抽到的样本集是X={x1,x2,…,x N}，其中x i表⽰抽到的第i个⼈的⾝⾼，这⾥N就是100，表⽰抽到的样本个数。

一文让你完全入门EM算法重磅干货，第一时间送达EM（Expectation Maximum，期望最大化）是一种迭代算法，用于对含有隐变量概率参数模型的极大似然估计或极大后验估计。

模型参数的每一次迭代，含有隐变量概率参数模型的似然函数都会增加，当似然函数不再增加或增加的值小于设置的阈值时，迭代结束。

EM算法在机器学习和计算机视觉的数据聚类领域有广泛的应用，只要是涉及到后验概率的应用，我们都可以考虑用EM算法去解决问题。

EM算法更像是一种数值分析方法，正确理解了EM算法，会增强你机器学习的自学能力，也能让你对机器学习算法有新的认识，本文详细总结了EM算法原理。

目录1. 只含有观测变量的模型估计2. 含有观测变量和未观测变量的模型参数估计3. EM算法流程4. 抛硬币问题举例5. 高斯混合模型的参数估计6. 聚类蕴含的EM算法思想7. 小结1. 只含有观测变量的模型估计我们首先考虑比较简单的情况，即模型只含有观测变量不含有隐藏变量，如何估计模型的参数？我们用逻辑斯蒂回归模型（logistic regression model）来解释这一过程。

假设数据集有d维的特征向量X和相应的目标向量Y，其中，。

下图表示逻辑斯蒂回归模型：由之前的文章介绍，逻辑斯蒂回归模型的目标预测概率是S型函数计算得到，定义为：若，则目标预测变量为1；反之，目标预测变量为0。

其中w是待估计的模型参数向量。

机器学习模型的核心问题是如何通过观测变量来构建模型参数w，最大似然方法是使观测数据的概率最大化，下面介绍用最大似然方法（Maximum Likelihood Approach）求解模型参数w。

假设数据集，样本数据，模型参数。

观测数据的对数似然函数可写为：由对数性质可知，上式等价于：式(1)代入式(2)，得：其中：由于(3)式是各个样本的和且模型参数间并无耦合，因此用类似梯度上升的迭代优化算法去求解模型参数w。

因为：由式(4)(5)(6)可得：因此，模型参数w的更新方程为：其中η是学习率。

em算法原理EM算法（Expectation-Maximization Algorithm）是一种常用的统计学习方法，用于求解含有隐变量的概率模型中的参数估计问题。

EM算法的基本思想是通过迭代的方式寻找概率模型的最大似然解。

在实际应用中，有时候概率模型中的一些变量是无法直接观测到的，这些变量称为隐变量。

如何利用观测变量来估计隐变量和模型参数就是EM算法所要解决的问题。

假设我们有一个包含观测变量X和隐变量Z的概率模型，其中X表示观测数据，Z表示对应的隐变量。

我们的目标是通过已知的观测数据X来估计模型的参数θ。

由于无法直接观测到隐变量Z，所以不能直接用最大似然估计的方法来估计参数θ。

EM算法的基本思想是通过引入一个辅助函数Q函数来进行估计。

具体地，EM算法将参数估计问题分为两步进行迭代。

首先，E步（Expectation）：在E步，根据当前的参数估计值θ(t)计算Q函数的期望值。

这里的Q函数是关于隐变量Z和模型参数θ的函数。

在计算Q函数的期望值时，需要使用当前的参数估计值θ(t)来代替真实的参数θ。

通过计算Q函数的期望值，可以得到对应的隐变量的概率分布。

然后，M步（Maximization）：在M步，根据E步得到的隐变量的概率分布，计算使得Q函数取得最大值时的模型参数估计值θ(t+1)。

这一步相当于求解一个参数最优化问题，可以使用极大似然估计或其他优化方法来进行求解。

通过不断地迭代E步和M步，直到收敛，就可以得到概率模型的最大似然解，即参数的估计值。

EM算法的优点在于可以处理含有隐变量的复杂概率模型，且收敛到全局最优解的可能性较大。

然而，EM算法也存在一些问题，比如可能陷入局部最优解，对初始值敏感等。

总之，EM算法是一种迭代求解含有隐变量的概率模型参数估计问题的方法，通过迭代的方式不断提高参数估计值的精度，从而得到对应的模型参数的估计值。

EM算法原理一、简介EM（Expectation Maximization）算法是一种常见的统计学习方法，用于估计参数和解决一些难以处理的问题，特别是在存在隐变量的情况下。

EM算法最初由数学家罗伯特·卢德米勒（RobertLushmiller）和理查德·贝尔曼（RichardBellman）在20世纪50年代提出，后来由 statisticiansDempster, Laird, and Rubin 进一步发展，因此也被命名为Dempster-Laird-Rubin算法。

EM算法在许多领域都有广泛的应用，如混合高斯模型、隐马尔可夫模型、高斯过程回归等。

二、EM算法的步骤EM算法主要由两个步骤组成：E步（ExpectationStep）和M步（Maximization Step），这两个步骤在迭代过程中交替进行。

1.E步：计算隐变量的条件期望。

给定当前的参数估计值，计算隐变量的条件期望，通常表示为参数的函数。

这个步骤中，隐变量对数似然函数的参数更新起着关键作用。

2.M步：最大化期望值函数。

在E步计算出期望值之后，M步将尝试找到一组参数，使得这个期望值函数最大。

这个步骤中，通常使用优化算法来找到使期望值函数最大的参数值。

这两个步骤在迭代过程中交替进行，每次迭代都更新了参数的估计值，直到满足某个停止准则（如参数收敛或达到预设的最大迭代次数）。

三、EM算法的特点与优点1.处理隐变量：EM算法能够处理数据中存在的隐变量问题，这是它与其他参数估计方法相比的一大优势。

通过估计隐变量的概率分布，EM算法能够更准确地描述数据的生成过程。

2.简单易行：相对于其他优化算法，EM算法相对简单易懂，也容易实现。

它的主要目标是最优化一个简单的对数似然函数，这使得EM算法在许多情况下都能给出很好的结果。

3.稳健性：对于一些数据异常或丢失的情况，EM算法往往表现出较好的稳健性。

这是因为EM算法在估计参数时，会考虑到所有可用的数据，而不仅仅是正常的数据点。