EM算法
1.1 什么是EM算法
EM算法是解决含有隐变量的模型的参数估计问题 假设我们有一个估计问题，对于$m$个独立的样本${x^{(1)},…x^{(m)}}$，若将其拟合到一个参数模型$p(x,z)$中，其中$z$是无法观测的隐变量，这一系统的对数似然函数可写作： \(l(\theta)=\sum_{i=1}^{m}\log p(x^{(i)};\theta)=\sum_{i=1}^{m}\log\sum_{z^{(i)}}p(x^{(i)},z^{(i)};\theta)\) 这个系统中含有无法观测的隐变量$z^{i}$，不能直接给出系统的最大似然函数。EM算法的思想是不断地构造似然函数的下界(E-step)，然后优化似然函数的下界使其最大(M-step).
1.2 EM算法的数学推导
前面提到，如果我们知道隐函数$z^{(i)}$的分布，那整个系统的最大似然函数可求，记这一分布为$Q_{i}(z^{(i)})$, $Q_{i}(z^{(i)})$可以理解为第$i$个样本属于某一个特定类的概率，对每一个样本$i$满足：$\sum_{z^(i)}Q_{i}(z^{(i)})=1$, $Q_{i}(z^{(i)})>0$ 考虑： \(\sum_{i}\log p(x^{(i)};\theta)=\sum_{i}\log\sum_{z^{(i)}}p(x^{(i)},z^{(i)};\theta)\)
\[=\sum_{i}\log \sum_{z^{(i)}}Q_{i}(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}\ge \sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)})\log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}\]最后一个大于等于号是利用对数函数是凹函数(二阶导数小于0)以及琴生不等式(Jensen’s inequality). 这里要注意的是 \(\sum_{z^{(i)}}Q_{i}(z^{(i)})\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}\) 刚好是$p(x^{(i)},z^{(i)};\theta)/Q_{i}(z^{(i)})$对于分布$Q_{i}(z^{(i)})$的期望.
对于每一个$Q_{i}$, 都给定了一个似然函数的下界，假设现在我们有一个对参数的估计$\theta$, 如果我们想最大化似然函数，一个很自然的想法就是让上式取等号，根据琴生不等式取等号的条件，我们需要： \(\frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}=c\) 其中$c$是不依赖于$z^{(i)}$分布的常量，即${Q_{i}(z^{(i)})} \propto p(x^{(i)},z^{(i)};\theta)$, 注意到$\sum_{z}Q_{i}(z^{(i)})=1$, 将$c$移动到等式一边，整理可得： \(\frac{1}{c}\sum_{z}p(x^{(i)},z^{(i)};\theta)=\sum_{z}Q_{i}(z^{(i)})=1\)
\[c=\sum_{z}p(x^{(i)},z^{(i)};\theta)\]即： \(Q_{i}(z^{(i)})=\frac{p(x^{(i)},z^{(i)};\theta)}{\sum_{z}p(x^{(i)},z^{(i)};\theta)}=\frac{p(x^{(i)},z^{(i)};\theta)}{p(x^{(i)};\theta)}=p(z^{(i)}|x^{(i)};\theta)\)
这一概率正好是在给定观测值$x^{(i)}$和参数$\theta$下，隐变量$z$的条件概率分布.
根据前面的推导，EM算法的具体过程是：
初始化参数$\theta$
(1) E-step: 对每一个样本$i$, 计算 $Q_{i}(z^{(i)})=p(z^i|x^i;\theta)$
(2) M-step:计算使得 $\sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)})\log \frac{p(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})}$ 取得最大值的参数$\theta$, 并更新参数
(3) 重复E-step和M-step直至收敛
1.3 EM算法的应用-高斯混合模型
EM算法的一个典型的应用就是用来估计混合高斯模型的参数，在介绍混合高斯模型之前，我们先回顾一下单高斯模型的定义.
1.3.1 单高斯模型的回顾
高斯分布是统计学中最基本的变量分布模型，一维高斯模型的概率分布函数可以写作： \(f(x)=\frac{1}{\sqrt{2\pi}\sigma}\exp{-\frac{(x-\,u)^{2}}{2\sigma^{2}}}\) 其中$\mu$是高斯分布的均值，$\sigma^{2}$是高斯分布的方差.
高斯分布可以推广到多维的情形，$n$维随机向量$X=(x_{1}, x_{2}, …x_{n})$满足$d$维高斯分布，其联合概率密度函数可写作： \(f(X)=\frac{1}{(2\pi)^{(d/2)}|\Sigma|^{(1/2)}}\exp[-\frac{1}{2}(X-\mu)^{T}\Sigma^{-1}(X-\mu)], X=(x_{1}, x_{2}, ...x_{n})\)
其中$\mu=(\mu_{1}, \,u_{2}, …\,u_{n})$是$X$每一维向量的均值，$\Sigma$是协方差矩阵，描述每一维之间的相关性.
1.3.2 混合高斯模型（Gaussian mixture model, GMM）
通过一定的权重，将若干个高斯模型融合成一个模型，就称为混合高斯模型。更一般化的描述为：假设一个模型由$K$个高斯模型组成，则混合高斯模型的概率密度函数可以写作： \(p(x)=\sum_{k=1}^{K}p(k)p(x|k)=\sum_{k=1}^{K}\pi(k)N(x|\Sigma_{k}, \mu_{k})\)
其中$p(x|k)=N (x|\Sigma_{k}, \mu_{k})$是第$k$个高斯分布的概率密度函数，可以看做选定第$k$个模型后，该模型生成观测变量$x$的分布. $p_{k}=\pi_{k}$是第$k$个高斯分布的权重，满足$\sum_{k}\pi_{k}=1$. 理论上，足够数量的高斯分布通过一定的权重融合，可以拟合任意形式的分布.
下面我们试图写出混合高斯模型的极大似然函数，假设我们有一批样本$Y=(y_{1}, y_{2},…y_{m})$, 那么整个系统的极大似然函数就是这些样本的联合概率. 如果所有样本都出自同一个单高斯模型，那么这个联合概率分布很容易给出，然而现在有$k$个高斯模型以权重$\pi_{k}$混合，我们无法决定每一个样本来自哪一个高斯分布. 因此，我们引入一个隐变量$\gamma $，第$i$个样本来自第$k$个高斯分布的概率为$p(\gamma_{k}=1)$显然就是$\pi_{k}$. 于是，观测到样本$y$的概率是： \(p(y)=\sum_{k=1}^{K}p(\gamma_{k}=1)p(y|\gamma_k=1)=\sum_{k=1}^{k}\pi_{k}N(y|\Sigma_{k}, \mu_{k})\) 那么对整个样本集$Y=(y_{1}, y_{2},…y_{m})$， 系统的对数似然函数可以写作： \(l(\mu,\Sigma,\pi )=\sum_{1}^{m}\log\sum_{k=1}^{k}\pi_{k}N(y|\Sigma_{k}, \mu_{k})\) 对参数$(\mu,\Sigma,\pi )$的估计无法直接用极大化对数似然函数的办法求得（对数函数里套嵌求和项），很容易看出这是一个典型的前面讨论过的EM算法的应用场合.