EM 思想

2019-04-18 本文已影响0人 zealscott

以Kmeans和GMM为例，阐述EM思想。

Kmeans

kmeans是一种相当简单和直观的聚类算法，主要分类两步：

对于每个点，选择离他最近的聚类中心作为他的类别： $c^{(i)} :=\arg \min _{j}\left\|x^{(i)}-\mu_{j}\right\|^{2}$
对于每个类别，求解聚类这个类的聚类中心： $\mu_{j} :=\frac{\sum_{i=1}^{m} 1\left\{c^{(i)}=j\right\} x^{(i)}}{\sum_{i=1}^{m} 1\left\{c^{(i)}=j\right\}}$

虽然算法很简单，但是我们还是需要回答一个很基本的问题，这个算法会收敛吗？

我们定义一个distortion function： $J(c, \mu)=\sum_{i=1}^{m}\left\|x^{(i)}-\mu_{c^{(i)}}\right\|^{2}$

这个函数衡量了点到对应的聚类中心的距离平方和，实际上，我们的kmeans算法能使得distortion function不断减小，具体来说：

第一步是在 $\mu$ 固定的情况下，我们通过 $c$ 不断减小 $J$
第二步是在 $c$ 固定的情况下，我们通过 $\mu$ 不断减小 $J$

因此， $J$ 一定是单调递减的，因此也保证了算法的收敛性。

但在实际应用中，kmeans算法并不能保证全局最优解，同时可能存在着震荡，这是因为我们的优化目标 $J$ 不是一个凸函数。而kmeans算法的每一步都是在寻找局部最优解（local optima），因此，最好的办法是多次重复该算法，并选择最小的 $J$ 。

GMM

Model

假设我们有一系列训练集 $\left\{x^{(1)}, \ldots, x^{(m)}\right\}$ ，我们需要使用非监督学习的方法进行训练。

我们将这些数据建模成联合分布的形式： $p\left(x^{(i)}, z^{(i)}\right)= p\left(x^{(i)} | z^{(i)}\right) p\left(z^{(i)}\right)$ 。

在这里， $z^{(i)} \sim$ Multinomial $(\phi)$ (where $\phi_{j} \geq 0, \sum_{j=1}^{k} \phi_{j}=1$ ），也就是我们的隐变量
在给定 $z$ 的条件下，假设 $x^{(i)} | z^{(i)}=j \sim \mathcal{N}\left(\mu_{j}, \Sigma_{j}\right)$

因此，我们首先需要通过随机变量 $z$ 产生一个 $z^{(i)}$ ，然后再从对应的高斯分布中产生 $x$ ，这种模型被称为高斯混合模型。

不难得到，对于这个模型来说，我们的参数为 $\phi, \mu$ and $\Sigma$ 。写成似然函数的形式：

$\begin{aligned} \ell(\phi, \mu, \Sigma) &=\sum_{i=1}^{m} \log p\left(x^{(i)} ; \phi, \mu, \Sigma\right) \\ &=\sum_{i=1}^{m} \log \sum_{z^{(i)}=1}^{k} p\left(x^{(i)} | z^{(i)} ; \mu, \Sigma\right) p\left(z^{(i)} ; \phi\right) \end{aligned}$

但很遗憾的是，如果我们直接对这个似然函数求导，无法得到一个cloed form。

If $z$ is observed

但如果我们的隐变量 $z$ 是已知的呢，我们是不是就很容易求解了呢？

我们重写似然函数为：

$\ell(\phi, \mu, \Sigma)=\sum_{i=1}^{m} \log p\left(x^{(i)} | z^{(i)} ; \mu, \Sigma\right)+\log p\left(z^{(i)} ; \phi\right)$

带入假设的分布，不难求得：
$\phi_{j}=\frac{1}{m} \sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\}$

$\mu_{j}=\frac{\sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\} x^{(i)}}{\sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\}}$

$\Sigma_{j}=\frac{\sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\}\left(x^{(i)}-\mu_{j}\right)\left(x^{(i)}-\mu_{j}\right)^{T}}{\sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\}}$

因此，如果我们已知 $z$ ，那么MLE几乎和之前的高斯判别模型完全一致了。

但实际上， $z$ 是未知的，那么怎么办呢？

EM algorithm

我们使用EM思想来处理。EM是一种迭代的算法，主要有两个步骤：

E步：通过期望去guss的最可能的值
- 实际上我们是通过后验概率来进行估计： $p\left(z^{(i)}=j | x^{(i)} ; \phi, \mu, \Sigma\right)=\frac{p\left(x^{(i)} | z^{(i)}=j ; \mu, \Sigma\right) p\left(z^{(i)}=j ; \phi\right)}{\sum_{l=1}^{k} p\left(x^{(i)} | z^{(i)}=l ; \mu, \Sigma\right) p\left(z^{(i)}=l ; \phi\right)}$
- 在这里，我们分子上的概率都可以直接得到，因此可以得到 $x^{(i)} = j$ 的概率，也就是soft assignments $w^{(i)}_j$
M步：通过已知的来对模型参数进行估计（与上面一样）
- $\phi_{j} :=\frac{1}{m} \sum_{i=1}^{m} w_{j}^{(i)}$
- $\mu_{j} :=\frac{\sum_{i=1}^{m} w_{j}^{(i)} x^{(i)}}{\sum_{i=1}^{m} w_{j}^{(i)}}$
- $\Sigma_{j} :=\frac{\sum_{i=1}^{m} w_{j}^{(i)}\left(x^{(i)}-\mu_{j}\right)\left(x^{(i)}-\mu_{j}\right)^{T}}{\sum_{i=1}^{m} w_{j}^{(i)}}$