Q

隐含变量是什么？
参数估计估计的什么参数？
EM算法用来干什么的的？E是什么？M又是什么？
流程是什么？
原理是什么？
应用场景？

背景知识

极大似然估计

一种参数估计方法。什么是参数估计？用在概率模型中，一般认为事件概率符合一定的分布，而这个分布的参数就是要估计的参数。参数估计就是用实验观测的结果取估计可能概率分布的参数，或者说是知道结果推原因。最大似然估计会寻找关于θ的最可能的值（即，在所有可能的 θ取值中，寻找一个值使这个采样的“可能性”最大化）。从数学上来说，我们可以在θ的所有可能取值中寻找一个值使得似然函数取到最大值。这个使可能性最大的$\hat{\theta}$值即称为θ的最大似然估计。由定义，最大似然估计是样本的函数。极大似然估计是建立在这样的思想上：已知某个参数能使这个样本出现的概率最大，我们当然不会再去选择其他小概率的样本，所以干脆就把这个参数作为估计的真实值。

自己理解的话就是说，概率模型，观察结果符合某种概率分布，每个事件(观测结果的取值)都是可以用某个参数的表达式(符合的分布)来表示，即事件发生的概率是概率模型参数的一个函数。另一方面，我们可以认为在事件所有可能的结果中，观察到的结果是最有可能发生的。也就是说观察结果是概率模型中取值最大的，因为观察结果是符合一定的概率分布，其参数表示为$\theta$。依据实验的观察结果，假设事件之间相互独立(每种观察结果之间互不影响)，我们就可以得到一个似然函数(可能函数)：每个事件对应的$theta$函数的连乘积。我们通过最大化这个似然函数(去逼近观察结果，因为现在观察结果由theta表示，而theta取值有无数种可能，通过最大化，逼近观察结果，对应的参数theta，就是所求结果)就可以估计出分布的参数$\theta$.

极大似然估计是我们知道事件服从某种分布，只是不知道分布的参数。

EM算法

复杂化的极大似然估计。概率模型存在隐变量，通俗讲就是观察结果并不是一种变量，并不完全相同(同质)，它们又可以继续划分，分成若干个份，每份符合同种分布(同质)，相似性更高。而这个份的划分就是隐变量。比如，现有100个男生，100个女生的共200人统计身高(假设身高服从正态分布)，现在我们需要估计男生和女生各自身高的正态分布的参数。200个人的身高，每个样本，我们并不知道它是男生还是女生，或者说200个样本中又可以细分成2份，男生和女生身高，各自服从自己的分布。现在的观测结果是忽略掉性别，只统计了身高，而我们的目标又是估计男生和女生的身高分布的参数(每个样本属于男生还是女生，这个变量也可以用一个分布来表示，但是这并不是我们需要求解的参数)。

EM用来估计观测结果的参数，而不是隐变量的参数。

定义

最大期望算法（Expectation-maximization algorithm，又译期望最大化算法）在统计中被用于寻找，依赖于不可观察的隐性变量的概率模型中，参数的最大似然估计。

在统计计算中，最大期望（EM）算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐变量。——–所以不能直接使用极大似然估计。最大期望算法经过两个步骤交替进行计算：

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

第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

EM算法的隐变量

一般用Y表示观测到的随机变量的数据，Z表示隐随机变量的数据， Y和Z连在一起称为完全数据，仅Y一个被称为不完全数据。EM算法面临的主要问题就是这个隐变量Z，加入Z已知的话，就可以划分极大似然估计问题来求解。那么如何把Z变成已知的？

假如，我们知道随机变量的估计参数，那么我们依据参数以及Y观察结果，可以估计隐变量Z服从分布的参数，这样就可以估计出Z的分布(也就是说Z分布变成了已知)；接下来根据估计出的Z分布，来对观测结果的参数进行估计(隐含变量已知)，使用极大似然估计进行求解，如果这个估计值和起始假设值相同，那么终止迭代；如果不同过程反复，直到参数收敛。

第一步，给出参数的一个假设值后，依据参数值和观测结果，可以推导出隐变量Z的一个可能结果，然后根据这个Z的结果，对Z的参数进行极大似然估计；第二步，知道Z的分布后，可以依据Y，Z完全数据使用极大似然估计来估计计算参数。

但实际上Z的参数并不需要估计，只需要知道每个样本上Z的取值结果即可。

这个过程相当于进行了两次极大似然估计：第一次，假设参数已知，估计隐变量的参数；第二次已知隐变量分布，估计参数。

我们先给参数一个估计值，然后再估计隐变量，再计算参数的新的估计估计值。如果两个估计值相同，那么返回结果，终止迭代；如果不同，反复迭代，直到参数收敛。

公式推导

EM算法的目标函数

一般情况下的极大似然函数如下：

$L(\theta) = L(x_1,x_2,…,x_n; \theta) = \prod_{i=1}^n p(x_i; \theta)$

但是现在，我们的观测结果中隐变量的存在。假设一个样本集${x_1, x_2,…,x_m}$，包含m个样本，每个样本有隐含类别Z。这种情况下，对数极大似然函数如下：

$L(\theta) = \sum_{i=1}^mlog p(x; \theta) = \sum_{i=1}^mlog\sum_z p(x,z;\theta)$

其中需要对每个样本x_i的所有可能类别z求联合分布概率和(将类别z去掉)。但是直接求比较困难，因为隐变量z的存在，而且不知道z的分布情况，如果确定z之后，求解就容易了。

对于参数估计，本质上还是项获得一个使得似然函数最大化的那个参数$\theta$,但是现在似然函数中存在一个隐变量Z。现在的目标是找到合适的$\theta$和Z使得$L(\theta)$最大。

我们将上面的式子做一个变化，分子分母同时乘以一个相等的函数(即隐变量Z的概率分布$Q_i(z^{(i)})$, 其概率之和为1).

Jensen不等式 如果f是凸函数，X是随机变量，那么：E[f(X)]>=f(E[X])，通俗的说法是函数的期望大于等于期望的函数。特别地，如果f是严格凸函数，当且仅当 P(X = EX) = 1，即X是常量时，上式取等号，也就是$E[f(x)] = f(EX)$

同时利用Jensen不等式，可以得到：

$\sum_{i=1}^m logp(x^{(i)}; \theta) = \sum_{i=1}^m log \sum_z p(x^{(i)},z;\theta)=\sum_{i=1}^m log \sum_{z^{(i)}} Q_i(z^{(i)}) \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} \geq\sum_i \sum_{z^{(i)}} Q_i(z^{(i)})log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$

其中，$\sum_{z^{(i)}}Q_i(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$是$\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$的期望，相应概率为$Q_i(z^{(i)})$

如果要满足Jensen不等式的等号，则有：

$\frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})} = c$, c为常数。

由于$Q_i(z^{(i)})$是一个分布，所以满足：$\sum_zQ_i(z^{(i)}) = 1$

从上面两个式子可以知道，

$Q_i(z^{(i)}) = \frac{P(x^{(i)}, z^{(i)}; \theta)}{\sum_zP(x^{(i)}, z^{(i)}; \theta)}=\frac{P(x^{(i)}, z^{(i)};\theta)}{P(x^{(i)}; \theta)} = P(z^{(i)|x^{(i)}; \theta})$

一个条件概率，如果$Q_i(z^{(i)})=P(z^{(i)}|x^{(i)};\theta)$, 那么就可以算出包含隐变量的对数似然函数的一个下界。如果能极大化这个下界，也就相当于在极大化我们的对数似然函数。所以，我们需要极大化下式：

$argmax_{\theta} \sum_i^m \sum_{z^{(i)}} Q_i(z^{(i)})log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$

去掉常数部分，小极大化的对数似然下界为：

$argmax_{\theta} \sum_i^m \sum_{z^{(i)}} Q_i(z^{(i)})log p(x^{(i)},z^{(i)};\theta)$

这个式子是我们EM算法中的M步。E步是求logP(x(i)，z(i);θ)基于条件概率分布Qi(z(i))的期望 ∑z(i)Qi(z(i))logP(x(i)，z(i);θ)。

算法流程

输入：观察数据$x=(x^{(1)}, x^{(2)},…,x^{(m)})$，联合分布p(x,z;theta),条件分布p(z|x;theta)，最大迭代次数J

随机初始化模型参数$\theta$的初值$\theta^0$
for j from 1 to J 开始EM算法迭代：
- E步：计算联合分布的条件概率期望：
  - $Q_i(z^{(i)})=P(z^{(i)}|x^{(i)};\theta)$
  - $L(\theta, \theta^j) = \sum_{i=1}^m\sum_{z^{(i)}}Q_i(z^{(i)})logP(x^{(i)}, z^{(i)};\theta)$
- M步：极大化$L(\theta, \theta^j)$,得到$\theta^{j+1}$:
  - $\theta^{j+1} = argmax_{\theta}L(\theta, \theta^j)$
如果$\theta^{j+1}$已经收敛，则算法结束；否则继续回到E步进行迭代.

结尾

算法已知的是观察数据，未知的是隐含变量和模型参数。在E步，所做的事情就是固定模型参数的值，优化隐含数据的分布；而在M步，所做的事情就是固定隐含数据分布，优化模型参数的值。

Q