期望最大算法

‘壹’ （十）EM算法

 EM算法的英文全称是 Expectation Maximization Algorithm——期望极大化算法 ，它采用迭代的方式逼近带隐变量的似然函数。通过对似然函数的一个下界求偏导，得到每一步参数估计的过程。
 这个名称由于缺乏作用对象，让人一头雾水。这里的期望是什么？为什么我们要极大化这个期望，我们试图优化什么？
 这里的期望的含义其实是针对 极大似然估计 中的 似然函数 来说的，这里的期望就是似然函数的一个 下界 ，我们的目的是求这样一个期望: 这个下界是根据 詹森不等式(Jensen's inequality） 放缩得到的，为什么要放缩呢？因为我们试图找出一个下界，极大化这个带参数的下界之后，可以无限近似于似然函数。你想，如果这个做法ok的话，意味着什么？意味着我们可以通过这个过程找出极大似然估计或最大后验估计的参数近似解。这也意味着我们可以搞一个迭代法来得到一个近似解。但是即便我说的天花乱坠，这个下界要是不收敛那也白搭。而下界要收敛必须满足两个条件：
 1.这个下界的取值要单调递增（因为每回迭代的结果要比上一次的取值更大）
 2.这个下界必须有上界(这个上界就是对数似然函数，且这一点可以由詹森不等式保证，这个也是EM的核心)
大白话就是 单调有界必有极限 。

我们来证明一下它确实是收敛的。
 首先，在极大似然估计中，我们的目的是根据手头上的 个样本，最大化 后，将参数 估计出来；引入对数： ;此时引入辅助变量 ;我们的对数似然函数就变成了：

设置变分函数： ;那么：

根据琴生不等式,对数函数为凸函数(因为 ：等号在 为常数时取到)：

上面的这个下界，就是用来逼近原对数似然函数的，这里我们已经证明了算法收敛的一个条件， 有界性 ；但是在继续进行下一步的时候，我们还有一个问题没搞清楚，那就是变分函数 的具体形式,实际上，我们可以通过琴生不等式等号成立的条件导出我们要的这个变分函数q。
令 为常数：
接着我们代入变分函数 的形式，定义这个下界的第一项：

定义下界的第二项：

对于第二项，我们看看随着迭代步数的增大，它是否是递增的，

我们将不同参数的 与 看作是两个分布，那么这个结果实际上是一个KL散度，它表征两个分布的相似度,其结果总是大于等于0的。
大于等于0的原因：

所以：

H为一个递增的序列，那么剩下的就是Q是否递增了，基于前面提到的这个下界是有上界的，上界就是我们的对数似然函数。在这个前提下，现在我们只要证明，Q递增是整个下界递增的充分必要条件即可。
必要性：

当整个下界递增，即：
那么：
所以 单调递增，必要性得证。
充分性：
因为：
前面已经证明：

又因为：

所以：

即，在 递增的情况下，整个下界递增。
充分性得证。
证毕。

 这个算法名称里提及的期望究竟是什么？
我们说了这么多，实际都是要做一件事，那就是：

由于前面证明过整个下界有界。且只要找到让第i次迭代的Q函数最大的 作为下一次迭代的参数，我们就可以让Q递增，让算法收敛。
我们来看看Q的形式。

这就是为什么叫期望最大算法的原因。

 我们以概率PCA，来展开EM的应用：
 当然这里的应用只涉及变分函数已知情况下的应用，并不涉及广义EM的内容，日后看完文献在来唠唠广义EM，AVE，GAN等内容。
 我们先来算一下PPCA的EM期望的形式：

在 概率PCA 中，我们有提到：


所以：


所以期望里面是这个式子：

我们的目的是要估计出 和 ;那么我们分别对它们求偏导:

所以：


因为：

代入偏导中

所以：

我们偏导得到的结果就是：

我们会发现我们还有两个估计量没解决，一个是一阶估计量 ,另一个是二阶估计量
在概率PCA中，我们提到过：

那么我们就有了一阶估计量：

二阶估计量可以通过简单的计算得到：

剩下的代入即可.

结果展示：

‘贰’ 程序员必须掌握哪些算法

1. 集束搜索（又名定向搜索，BeamSearch）——最佳优先搜索算法的优化。

2. A*搜寻算法——图形搜索算法，是最佳优先搜索的范例，从给定起点到给定终点计算出路径。

3. 数据压缩——采取特定编码方案，使用更少的字节数（或是其他信息承载单元）对信息编码的过程，又叫来源编码。

4. 离散微分算法（Discretedifferentiation）

5. 哈希算法（Hashing）

6. 堆排序（Heaps）

7. 合并排序（MergeSort）

8. 梯度下降（Gradientdescent）——一种数学上的最优化算法。

9. 牛顿法（Newton'smethod）——求非线性方程（组）零点的一种重要的迭代法。
   

10. 欧几里得算法（Euclideanalgorithm）——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

11. Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

12. 动态规划算法（DynamicProgramming）——展示互相覆盖的子问题和最优子架构算法。

13. Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。

14. Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。

15. 二分查找（BinarySearch）——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

16. 合并查找算法（Union-find）——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。

17. 期望-最大算法（Expectation-maximizationalgorithm，又名EM-Training）——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。

18. 快速傅里叶变换（FastFouriertransform，FFT）——计算离散的傅里叶变换（DFT）及其反转。

19. 最大流量算法（Maximumflow）——该算法试图从一个流量网络中找到最大的流。
    

20. LLL算法（Lenstra-Lenstra-Lovaszlatticerection）——以格规约（lattice）基数为输入，输出短正交向量基数。

21. 两次筛法（QuadraticSieve）——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法（仅次于数域筛法NumberFieldSieve）。

22. RANSAC——是“RANdomSAmpleConsensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。

23. 求解线性方程组（）——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法（Gauss-Jordanelimination），或是柯列斯基分解（Choleskydecomposition）。

24. Q-learning学习算法——这是一种通过学习动作值函数（action-valuefunction）完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。

25. Schönhage-Strassen算法——在数学中，Schönhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(Nlog(N)log(log(N)))，该算法使用了傅里叶变换。

26. RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。

27. Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域（homogenousregion），看看它是否属于边缘，还是是一个顶点。

28. 单纯型算法（SimplexAlgorithm）——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。

29. 奇异值分解（Singularvaluedecomposition，简称SVD）——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵（以求解最小二乘法问题）、解决超定线性系统（overdeterminedlinearsystems）、矩阵逼近、数值天气预报等等。

30. 维特比算法（Viterbialgorithm）——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。

‘叁’ 期望最大算法(EM)

1977年，DempSter首次提出EM算法。

假设四种实验结果，发生的概率依次为 ，且发生的次数为 ，求 的估计。
解：使用MLE，得到：

上式是关于 的一元三次方程，不易解。

因此，以下另作处理（引入隐变量）：

将第一部分 分为 ，且出现次数为 次

将第三部分 分为 ，且出现次数为 次；

则

(1)

现在，并不知道 （隐变量）的值，只能知道分布的信息， 服从的分布为二项分布，概率数值类似于条件概率，第一个的概率是用 除以 得到的，第二个同理：

其中， ，

第一步（E步）：求期望的目的是为了消去隐变量 。

;

代入(1)式，得到：

第二步（M步）：取最大值。

EM算法使用迭代法来更新参数。 （精髓）

任意取 ，就可以开始按照上面的公式进行迭代了。

收敛性 ：
DempSter证明：在很一般的条件下，最后会收敛。（可以参考李航老师的《统计学习方法》）

解析解：能列出公式解决的，数值上是更准确的（相比迭代解），比如MLE就是列出公式求解。
迭代解：退而求其次，当解析解难求的时候，通过迭代逼近的方式，可以获得令人满意的解，比如EM就是为了解决当MLE遇到高次方程难以求解的时候，提出的方法。

问：给定参数 ，观测变量 ，隐变量 ，如何估计参数 ？

从观测序列，可以获得：

此时，对数似然函数为：

由于包含和（积分）的对数，因此直接求解困难。

解析解困难，转而使用迭代解：假设第i次迭代后的 为 ，由于我们希望似然函数 是增大的，即 。

此时，考虑两者的差：

不等式右边是 的下界，记为 ，那么，使得下界尽可能大，即：

Algorithm: Estimation Maximum (EM)

举例：以三硬币模型为例。有A、B、C三枚硬币，分别有 的概率为正面。每次试验为：先投A硬币，如果A为正面，则投B硬币；否则，投C硬币。最终，可以观测到的结果为硬币的正/反面，但是不知道是由B还是C投出的（隐变量）。问：如果某次试验数为10的结果为：{1,1,0,1,0,0,1,0,1,1}，如何估计参数 ？

显然，题目的 隐变量为A硬币投出的结果，此时可以采用EM解法。
先从“E”入手，求解Q函数：

然后，逐一击破：

回代 函数：

极大似然求导数，令其为0，能取得极值点：

令上式为0

------对应书(9.6)式

令上式为0

------对应书(9.7)式

令上式为0

------对应书(9.8)式

至此，只要根据当前迭代下的 ，就能得到不同 下标的 ，进而得到下一次迭代的 。

‘肆’ 怎么通俗易懂地解释EM算法并且举个例子

在统计计算中，最大期望（EM）算法是在概率（probabilistic）模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variable）。最大期望经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。

最大期望算法经过两个步骤交替进行计算：

第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；

第二步是最大化（M），最大化在 E 步上求得的最大似然值来计算参数的值。

M 步上找到的参数估计值被用于下一个 E 步计算中，这个过程不断交替进行。

总体来说，EM的算法流程如下：

1. 初始化分布参数

2. 2.重复直到收敛：

3. E步骤：估计未知参数的期望值，给出当前的参数估计。

4. M步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。
   

‘伍’ 在计算机科学中，有哪些非常巧妙的算法

分支界定算法（Branch and Bound）——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

动态规划算法（Dynamic Programming）——展示互相覆盖的子问题和最优子架构算法

欧几里得算法（Euclidean algorithm）——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

期望-最大算法（Expectation-maximization algorithm，又名EM-Training）——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值；第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值

‘陆’ 大数据最常用的算法有哪些

奥地利符号计算研究所(Research Institute for Symbolic Computation，简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。

大数据等最核心的关键技术：32个算法

1、A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。

2、集束搜索(又名定向搜索，Beam Search)——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。

3、二分查找(Binary Search)——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

4、分支界定算法(Branch and Bound)——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。

5、Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

6、数据压缩——采取特定编码方案，使用更少的字节数(或是其他信息承载单元)对信息编码的过程，又叫来源编码。

7、Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。

8、Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。

9、离散微分算法(Discrete differentiation)。

10、动态规划算法(Dynamic Programming)——展示互相覆盖的子问题和最优子架构算法

11、欧几里得算法(Euclidean algorithm)——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

12、期望-最大算法(Expectation-maximization algorithm，又名EM-Training)——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值;第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值。

13、快速傅里叶变换(Fast Fourier transform，FFT)——计算离散的傅里叶变换(DFT)及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。

14、梯度下降(Gradient descent)——一种数学上的最优化算法。

15、哈希算法(Hashing)。

16、堆排序(Heaps)。

17、Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。

18、LLL算法(Lenstra-Lenstra-Lovasz lattice rection)——以格规约(lattice)基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用：背包加密系统(knapsack)、有特定设置的RSA加密等等。

19、最大流量算法(Maximum flow)——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关，这就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一个流网络中的最大流。

20、合并排序(Merge Sort)。

21、牛顿法(Newton’s method)——求非线性方程(组)零点的一种重要的迭代法。

22、Q-learning学习算法——这是一种通过学习动作值函数(action-value function)完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的情况下，可以对比可采纳行动的期望效用。

23、两次筛法(Quadratic Sieve)——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法(仅次于数域筛法Number Field Sieve)。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简单。

24、RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数解释的值，异化值就是那些不符合模型的数据点。

25、RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。

26、Sch?nhage-Strassen算法——在数学中，Sch?nhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(N log(N) log(log(N)))，该算法使用了傅里叶变换。

27、单纯型算法(Simplex Algorithm)——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待最大化(或最小化)的固定线性函数。

28、奇异值分解(Singular value decomposition，简称SVD)——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵(以求解最小二乘法问题)、解决超定线性系统(overdetermined linear systems)、矩阵逼近、数值天气预报等等。

29、求解线性方程组(Solving a system of linear equations)——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。

30、Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域( homogenous region)，看看它是否属于边缘，还是是一个顶点。

31、合并查找算法(Union-find)——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集(disjoint-set)的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作：

查找：判断某特定元素属于哪个组。

合并：联合或合并两个组为一个组。

32、维特比算法(Viterbi algorithm)——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。

以上就是Christoph博士对于最重要的算法的调查结果。你们熟悉哪些算法?又有哪些算法是你们经常使用的?

‘柒’ em算法是什么

最大期望算法（Expectation-Maximization algorithm, EM），或Dempster-Laird-Rubin算法，是一类通过迭代进行极大似然估计（Maximum Likelihood Estimation, MLE）的优化算法 ，通常作为牛顿迭代法（Newton-Raphson method）的替代用于对包含隐变量（latent variable）或缺失数据（incomplete-data）的概率模型进行参数估计。
EM算法的标准计算框架由E步（Expectation-step）和M步（Maximization step）交替组成，算法的收敛性可以确保迭代至少逼近局部极大值 。EM算法是MM算法（Minorize-Maximization algorithm）的特例之一，有多个改进版本，包括使用了贝叶斯推断的EM算法、EM梯度算法、广义EM算法等 。
由于迭代规则容易实现并可以灵活考虑隐变量，EM算法被广泛应用于处理数据的缺测值 ，以及很多机器学习（machine learning）算法，包括高斯混合模型（Gaussian Mixture Model, GMM） 和隐马尔可夫模型（Hidden Markov Model, HMM） 的参数估计。