最大期望值EM算法
最大期望值(Expectation-Maximization, EM)算法是一种统计学习方法，用于解决带有隐变量的概率模型参数估计问题。EM算法的主要思想是通过迭代求解局部最优解，并且能够保证每次迭代过程中目标函数值不减。
EM算法广泛应用于数据挖掘、图像处理、自然语言处理等领域，在金融、医学和社会科学等领域也有许多实际应用。本文将对EM算法的基本原理、迭代过程、理论基础和应用进行详细介绍。
一、基本原理
EM算法是一种迭代算法，包含两个步骤：E步和M步。其中，E步是求期望(expectation)的过程，用于更新隐变量对观测数据的条件概率分布；M步是求最大化(maximization)的过程，用于更新模型的参数。通过不断交替进行E步和M步，直到收敛为止，即可得到最优的参数估计。
二、迭代过程
1.初始化参数：随机给定模型参数的初始值。
2.E步：根据当前参数估计，计算隐变量对观测数据的条件概率分布。
3.M步：根据当前隐变量的条件概率分布，最大化观测数据的对数似然函数，更新模型的参数估计。
4.计算目标函数值：根据当前参数估计，计算目标函数的值。
5.判断是否满足停止条件：如果满足停止条件，则算法结束；否则，返回第2步。 三、理论基础
EM算法基于两个基本定理：数据的似然函数下界和KL散度的非负性。
1.数据的似然函数下界：对于给定的观测数据，EM算法通过求解数据的似然函数的下界来进行参数估计。这个下界是通过引入隐变量来扩展数据模型得到的，因此可以利用EM算法求解。
2.KL散度的非负性：KL散度是衡量两个概率分布之间的差异程度的指标。在EM算法中，通过最大化观测数据的对数似然函数来更新模型的参数，相当于最小化KL散度。
四、应用领域
EM算法在许多领域都有广泛的应用。以下是一些典型的应用实例：
1.聚类分析：EM算法可以用于高斯混合模型的参数估计，从而实现聚类分析。
2.隐马尔可夫模型(HMM)：EM算法可以用于HMM模型参数的估计，应用于自然语言处理、语音识别等领域。
EM算法-完整推导
前篇已经对EM过程,举了扔硬币和⾼斯分布等案例来直观认识了, ⽬标是参数估计, 分为 E-step 和 M-step, 不断循环, 直到收敛则求出了近似的估计参数, 不多说了, 本篇不说栗⼦, 直接来推导⼀波.
Jensen 不等式
在满⾜:
⼀个 concave 函数, 即 形状为 "⋂" 的函数 f(x)
λj≥0
∑jλj=1 类似于随机变量的分布
的前提条件下, 则有不等式:
f(∑jλjxj)≥∑jλjf(xj)
恒成⽴, 则该不等式称为 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)
最大期望算法（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）的参数估计。
EM算法是一种迭代优化策略，由于它的计算方法中每一次迭代都分两步，其中一个为期望步（E步），另一个为极大步（M步），所以算法被称为EM算法（Expectation-Maximization Algorithm）。EM算法受到缺失思想影响，最初是为了解决数据缺失情况下的参数估计问题，其算法基础和收敛有效性等问题在Dempster、Laird和Rubin三人于1977年所做的文章《Maximum likelihood from
incomplete data via the EM algorithm》中给出了详细的阐述。
其基本思想是：首先根据己经给出的观测数据，估计出模型参数的值；然后再依据上一步估计出的参数值估计缺失数据的值，再根据估计出的缺失数据加上之前己经观测到的数据重新再对参数值进行估计，然后反复迭代，直至最后收敛，迭代结束。
EM算法
EM算法--应用到三个模型： 高斯混合模型
，混合朴素贝叶斯模型，因子分析模型
判别模型求的是条件概率p(y|x)，
生成模型求的是联合概率p(x,y)
.即 = p(x|y) ? p(y)
常见的判别模型有线性回归、对数回归、线性判别分析、支持向量机、boosting、条件 随机场、神经网络等。
常见的生产模型有隐马尔科夫模型、朴素贝叶斯模型、高斯混合模型、LDA、Restricted
Boltzmann Machine等。
所以这里说的高斯混合模型，朴素贝叶斯模型都是求p(x,y)联合概率的。(下面推导会见原因)套路小结： 凡是生产模型，目的都是求出联合概率表达式，然后对联合概率表达式里的各个参数再进行估计，求出其表达式。下面的EM算法，GMM等三个模型都是做这同一件事：设法求出联合概率，然后对出现的参数进行估计。 一、EM算法：
作用是进行参数估计。
应用：（因为是无监督，所以一般应用在聚类上，也用在HMM参数估计上）所以凡是有EM算法的，一定是无监督学习.因为EM是对参数聚集
给定训练样本是高斯混合模型 ，混合朴素贝叶斯模型，因子分析模型"> 样例独立，
我们想要知道每个样例隐含的类别z，使是p(x,z)最大，（即
如果将样本x(i)看作观察值，
潜在类别z看作是隐藏变量， 则x可能是类别z， 那么聚类问题也就是参数估计问题，）
故p(x,z)最大似然估计是：
高斯混合模型 ，混合朴素贝叶斯模型，因子分析模型">
所以可见用到EM算法的模型（高斯混合模型，朴素贝叶斯模型）都是求p(x,y)联合概率，为生成模型。
对上面公式，直接求θ一般比较困难，因为有隐藏变量z存在，但是一般确定了z后，求解就容易了。
EM是一种解决存在隐含变量优化问题的有效方法。竟然不能直接最大化?(θ)，我们可建立?的下界（E步），再优化下界（M步），见下图第三步，取的就是下界
高斯混合模型 ，混合朴素贝叶斯模型，因子分析模型"
