EM算法

密度估计

密度估计 (Density Estimation) 的一个应用是: 异常检测 (Anomaly Detection) 训练数据集为$\{x_1, x_2, \cdots, x_m\}$, 推出对应的概率分布模型 $P(x)$, 如果某个点偏离$P(x)$很多, 那么很有可能是异常点.

EM算法

只有输入没有对应的输出, 属于非监督学习问题: 训练数据集为$\{(x^{(1)},\cdot), (x^{(2)},\cdot), \cdots, (x^{(m)}\cdot)\}, m$个独立样本,希望从中找到该组数据的模型$P(x,z)$的参数, $x$ 是可观察值, $z$ 是未知的.

目标函数

对数似然函数:

$\begin{align} l(\theta)&=log\prod_{i=1}^mp(x^{(i)}; \theta)\notag\\ &=\sum_{i=1}^mlogp(x^{(i)}; \theta)\notag\\ &=\sum_{i=1}^mlog\sum_{z^{(i)}} p(x^{(i)},z^{(i)}; \theta)\notag \end{align}$

最大化对数似然函数: z是隐随机变量, 不方便直接找到参数估计。

策略: 计算$l(\theta)$下界, 求该下界函数$B(\theta)$的最大值; 重复该过程, 直到收敛到局部最大值。

Jensen 不等式

1. 定理: $f(x)$ 是凸函数(e.g. $f''(x)\geq0$), X是随机变量, 则: $E[f(X)]\geq f(EX)$
2. 推论1: 若$f''(x)\geq0$ ($f(x)$是严格的凸函数), 则 $E[f(X)] = f(EX)$ 成立, $\stackrel{当且仅当}\Longleftrightarrow P(X=E[X])=1,即X为常量$
3. 推论2: 若$f''(x)\leq0$ ($f(x)$是严格的凹函数), 则 $E[f(X)]\leq f(EX)$

下界函数

$\begin{align} l(\theta)&=\sum_{i=1}^mlogp(x^{(i)}; \theta)\notag\\ &=\sum_{i=1}^mlog\sum_{z^{(i)}} p(x^{(i)},z^{(i)}; \theta)\notag\\ &=\sum_{i=1}^mlog\sum_{z^{(i)}} Q_i(z^{(i)}) \frac{P(x^{(i)},z^{(i)}; \theta)}{Q_i(z^{(i)})}\notag\\ &[Q_i(z^{(i)})\geq0, \sum_{z^{(i)}}Q_i(z^{(i)})=1] \notag\\ &=\sum_{i=1}^m logE[\frac{P(x^{(i)},z^{(i)}; \theta)}{Q_i(z^{(i)})}]\notag\\ &\stackrel{Jensen不等式} \geq \sum_{i=1}^m E[log\frac{P(x^{(i)},z^{(i)}; \theta)}{Q_i(z^{(i)})}]\notag\\ &= \sum_{i=1}^m\sum_{z^{(i)}} Q_i(z^{(i)}) log\frac{P(x^{(i)},z^{(i)}; \theta)}{Q_i(z^{(i)})}\notag \end{align}$

即: $l(\theta)\geq B(\theta):= \sum_{i=1}^m\sum_{z^{(i)}} Q_i(z^{(i)}) log\frac{P(x^{(i)},z^{(i)}; \theta)}{Q_i(z^{(i)})}$

求 $Q_i(z^{(i)})$

找尽量紧的下界函数, 即$l(\theta)= B(\theta)$,

根据Jensen不等式的推论, 当且仅当: $\frac{P(x^{(i)},z^{(i)}; \theta)}{Q_i(z^{(i)})}=c$

即: $Q_i(z^{(i)})\propto P(x^{(i)},z^{(i)}; \theta), 且\sum_{z^{(i)}}Q_i(z^{(i)})=1$

则: $Q_i(z^{(i)}) = \frac{P(x^{(i)},z^{(i)}; \theta)}{\sum_{z^{(i)}}P(x^{(i)},z^{(i)}; \theta)}\notag =\frac{P(x^{(i)},z^{(i)}; \theta)}{P(x^{(i)}; \theta)} =P(z^{(i)}\mid x^{(i)}; \theta)\notag$

EM算法整体框架 (非常重要!!@_@)

Repeat until convergence {

Step1. E-step (猜测 类标记 $z^{(i)}$ 的值):

$Q_i(z^{(i)}) :=P(z^{(i)}\mid x^{(i)}; \theta)$

Step2. M-step (更新参数的估计):

$\begin{align} \theta^{\rm{new}}&=arg\max_{\theta} \sum_{i=1}^m\sum_{z^{(i)}} Q_i(z^{(i)};\theta^{\rm{old}}) log\frac{P(x^{(i)},z^{(i)}; \theta)}{Q_i(z^{(i)};\theta^{\rm{old}})}\notag\\ &=arg\max_{\theta} \sum_{i=1}^m\sum_{z^{(i)}} Q_i(z^{(i)};\theta^{\rm{old}}) log{P(x^{(i)},z^{(i)}; \theta)}\notag\\ \end{align}$

Remark:

$B(\theta)$并列上升最优化( coordinate ascent optimization)

E-step: 求期望 $\sum_{z^{(i)}} Q_i(z^{(i)};\theta^{\rm{old}}) log{P(x^{(i)},z^{(i)}; \theta)}$

M-step: 关于 $\theta$ 最大化

EM在高斯混合模型中的应用

定义

• 一维高斯混合分布的例子。蓝色曲线给出了三个高斯分布(使用某个系数进行了缩放), 红色曲线表示它们的和:

• 

• 每个GMM由K个Gaussian分布组成: $p(x)=\sum_{k=1}^K\pi_k {\scr{N}}(x\mid \mu_k,\Sigma_k)$

  • 每个Gaussian概率密度${\scr{N}}(x\mid \mu_k,\Sigma_k)$称为一个Component, 并且有自己的均值 $\mu_k$ 和协方差 $\Sigma_k$ .
  • 混合系数(mixing coefficient)为$\pi_k$, 即每个 Component 被选中的概率, 满足: $\sum_{k=1}^K\pi_k=1, 0\leq\pi_k\leq1$

加入隐变量

随机变量 $z$ 是隐变量 ( latent / hidden / unobserved variables ) ,

$x^{(i)},z^{(i)}$之间的联合概率分布为: $P(x^{(i)},z^{(i)})=P(x^{(i)}\mid z^{(i)}) P(z^{(i)})$,

$z^{(i)} \sim Multinomial(\phi)$

$\phi_j=P(z^{(i)}=j), \sum_{j=1}^k\phi_j=1, \phi_j\geq0$

$x^{(i)}\mid z^{(i)}=j \sim {\scr{N}} (\mu_j,\Sigma_j)$

假设: $z^{(i)}=j$ 从$\{1,\dots,k\}$中随机选择得到; 而 $x^{(i)}$ 根据 $z^{(i)}$ 的取值, 由 $k$ 个高斯分布中, 取第 $j$ 个高斯分布中任意一点. 该模型称为高斯混合模型(GMM).

PS: GMM由2个高斯分布组成时, $z^{(i)} \sim Bernouli(\phi)$

目标函数

对数似然函数:

$\begin{align} l(\phi,\mu, \Sigma)&=log\prod_{i=1}^mp(x^{(i)},z^{(i)}; \phi,\mu, \Sigma)\notag\\ &=\sum_{i=1}^mlogp(x^{(i)},z^{(i)}; \phi,\mu, \Sigma)\notag\\ &=\sum_{i=1}^mlog\sum_{z^{(i)}=1}^k p(x^{(i)}\mid z^{(i)}; \mu, \Sigma)p(z^{(i)}; \phi)\notag \end{align}$

最大似然函数, 即求偏导,可得到参数的最大似然估计 (设问题集为${\Bbb{1}}$): $\phi_j=\frac{1}{m}\sum_{i=1}^m{\Bbb{1}}\{z^{(i)}=j\},$

$\mu_j=\frac{\sum_{i=1}^m{\Bbb{1}}\{z^{(i)}=j\}\cdot x^{(i)}}{\sum_{i=1}^m{\Bbb{1}}\{z^{(i)}=j\}},$

$\Sigma_j=\frac{\sum_{i=1}^m{\Bbb{1}}\{z^{(i)}=j\}\cdot (x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum_{i=1}^m{\Bbb{1}}\{z^{(i)}=j\}},$

EM在高斯混合模型中的算法过程

Repeat until convergence {

Step1. E-step (猜测 类标记 $z^{(i)}$ 的值, 即计算此时隐变量的后验概率):

$\begin{gather} w_j^{(i)} := Q_i(z^{(i)}=j)=P(z^{(i)}=j\mid x^{(i)}; \phi, \mu,\Sigma)\notag\\ \stackrel{贝叶斯定理}= \frac{P(x^{(i)}\mid z^{(i)}=j)P(z^{(i)}=j)}{\sum_{l=1}^k P(x^{(i)}\mid z^{(i)}=l)P(z^{(i)}=l)}\notag\\ \stackrel{x^{(i)}\mid z^{(i)}=j \sim {\scr{N}} (\mu_j,\Sigma_j)}=\frac{\frac{1}{(2\pi)^{n/2} |\Sigma|^{1/2}}exp(-\frac{1}{2}(x_{(i)}-\mu_j)^T\Sigma^{-1}(x_{(i)}-\mu_j))\cdot\phi_j}{\sum_{l=1}^k\frac{1}{(2\pi)^{n/2} |\Sigma|^{1/2}}exp(-\frac{1}{2}(x_{(i)}-\mu_l)^T\Sigma^{-1}(x_{(i)}-\mu_l))\cdot\phi_l}\notag \end{gather}$

Step2. M-step (更新参数的估计):

$\begin{gather} \phi_j:=\frac{1}{m}\sum_{i=1}^m w_j^{(i)}\notag\\ \mu_j:=\frac{\sum_{i=1}^m w_j^{(i)}x^{(i)}}{\sum_{i=1}^m w_j^{(i)}}\notag\\ \Sigma_j:=\frac{\sum_{i=1}^m w_j^{(i)}(x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum_{i=1}^m w_j^{(i)}}\notag \end{gather}$

}

EM & GDA

• 高斯判别分析 (Gaussian Discriminant Analysis, GDA)中, 类标记已知: $\phi_j=P(z^{(i)}=j)=\frac{1}{m}\sum_{i=1}^m{\Bbb{1}}\{z^{(i)}=j\}$
• EM中, $x^{(i)}$已知, 而类标记 $z^{(i)}$ 未知: $\phi_j=\frac{1}{m}\sum_{i=1}^m w_j^{(i)} , 其中: w_j^{(i)} =P(z^{(i)}=j\mid x^{(i)})\\$

M-step的推导

$\begin{align} \theta&=arg\max_{\theta} B(\theta)\notag\\ &=arg\max_{\theta} \sum_{i=1}^m\sum_{z^{(i)}} Q_i(z^{(i)}) log\frac{P(x^{(i)},z^{(i)}; \phi, \mu, \Sigma)}{Q_i(z^{(i)})}\notag\\ &=arg\max_{\theta} \sum_{i=1}^m\sum_{j=1}^k Q_i(z^{(i)}=j) log\frac{P(x^{(i)},z^{(i)}; \phi, \mu, \Sigma)}{Q_i(z^{(i)}=j)}\notag\\ &=arg\max_{\theta} \sum_{i=1}^m\sum_{j=1}^k w_j^{(i)} log\frac{\frac{1}{(2\pi)^{n/2} |\Sigma|^{1/2}}exp(-\frac{1}{2}(x_{(i)}-\mu_j)^T\Sigma^{-1}(x_{(i)}-\mu_j))\cdot\phi_j}{w_j^{(i)}}\notag\\ \end{align}$

为求最大, 对各个参数求偏导:

• 对于 $\mu_l$:

$\begin{align} \nabla_{\mu_l}B(\theta)&=-\nabla_{\mu_l}\sum_{i=1}^m\sum_{j=1}^k w_j^{(i)}\frac{1}{2}(x_{(i)}-\mu_j)^T\Sigma^{-1}(x_{(i)}-\mu_j)\notag\\ &=\frac{1}{2}\sum_{i=1}^m w_l^{(i)}\nabla_{\mu_l}(2\mu_l^T\Sigma_l^{-1}x^{(i)}-\mu_l^T\Sigma_l^{-1}\mu_l)\notag\\ &=\sum_{i=1}^m w_l^{(i)}(\Sigma_l^{-1}x^{(i)}-\Sigma_l^{-1}\mu_l)\stackrel{set}=0\notag \end{align}$

得到: $\mu_l:=\frac{\sum_{i=1}^m w_l^{(i)}x^{(i)}}{\sum_{i=1}^m w_l^{(i)}}$

• 对于 $\phi$:

考察M-step的目标函数, 对于$\phi$, 删除常数项, 得到: $\sum_{i=1}^m\sum_{j=1}^k w_j^{(i)}log\phi_j$

$\because \sum_{j=1}^k\phi_j=1$, 建立拉格朗日方程:

${\scr{L}}(\phi)=\sum_{i=1}^m\sum_{j=1}^k w_j^{(i)}log\phi_j+\beta ( \sum_{j=1}^k\phi_j-1)$

注: 这样求解的φi一定非负,所以,不用考虑 $\phi\geq0$ 这个条件. $\begin{gather} \frac{\partial}{\partial \phi_j}{\scr{L}}(\phi)= \sum_{i=1}^m\frac{ w_j^{(i)}}{\phi_j}+\beta\stackrel{set}=0\notag\\ \therefore \phi_j=\frac{\sum_{i=1}^m w_j^{(i)}}{-\beta}\notag\\ \because \sum_j\phi_j=1, \therefore -\beta=\sum_{i=1}^m\sum_{j=1}^k w_j^{(i)}=\sum_{i=1}^m 1 = m\notag \end{gather}$

得到: $\phi_j:=\frac{1}{m}\sum_{i=1}^m w_j^{(i)}$

反馈与建议

• 微博：@Girl_AI

参考文献

• Prof. Andrew Ng. Machine Learning. Stanford University
• Pattern Recognition and Machine Learning
• 统计学习方法
• 七月算法机器学习在线班