混合高斯模型与EM算法

Mixtures of Gaussians

这一部分引入了高斯混合模型和EM算法的定义，但是没有进一步证明EM算法的导出。

引入

给定训练集$\{x^{(1)},…,x^{m}\}$，根据无监督学习的定义，这些数据不带有任何标签。现在通过一个联合分布对数据进行建模:

$$p(x^{(i)},z^{(i)})=p(x^{(i)}|z^{(i)})p(z^{(i)})$$

其中

• $z^{(i)}\sim Multinomial(\phi),p(z^{(i)}=j)=\phi_j \ge 0,\sum_{j=1}^{k}\phi_j=1$
• $x^{(i)}|z^{(i)} = j \sim \mathcal{N}(u_j,\Sigma_j)$

k表示$z^{(i)}$取值的个数，所以模型假设每个$x^{(i)}$是由随机选择(多项分布)的$z^{(i)}$生成的，且$x^{(i)}$来自由$z^{(i)}$所对应的高斯分布。这就叫做高斯混合模型。$z^{(i)}$被称作隐变量，这正是让根据观测数据预测模型参数$(\phi,\mu,\Sigma)$的困难所在。

最大似然估计

为了估计高斯混合模型的参数，其最大似然估计可以被表示为

$$\begin{align} \ell(\phi,\mu,\Sigma) &= \sum_{i=1}^{m}logp(x^{(i)};\phi;\Sigma) \\ & = \sum_{i=1}^m log \sum_{z^{(i)}=1}^kp(x^{(i)}|z^{(i)};\mu;\Sigma)p(z^{(i)};\phi) \end{align}$$

第一行到第二行的转变表示每个观测数据$x^{(i)}$被模型生成的概率是每个高斯分模型生成$x^{(i)}$的概率之和。
但是，将偏导置为0后会发现，最大似然估计的参数没有封闭解。
那么，如果已知$z^{(i)}$的值，即已经确定$x^{(i)}$来自于哪一个高斯分模型，则最大似然估计为

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

最大化这个似然函数：

$$\phi_j = \frac{1}{m}\sum_{i=1}^m1\{z^{(i)}=j\}$$ $$\mu_j = \frac{\sum_{i=1}^m1\{z^{(i)}=j\}x^{(i)}}{\sum_{i=1}^m1\{z^{(i)}=j\}}$$ $$\Sigma_j=\frac{\Sigma_{i=1}^m1\{z^{(i)}=j\}(x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum_{i=1}^m1\{z^{(i)}=j\}}$$

如果$z^{(i)}$是已知的，最大似然估计的结果和高斯判别分析非常相似。如果是未知的，就需要使用EM(Expectation Maximization)算法来解决该问题。

EM算法

EM算法分为两个主要步骤，在上述问题中，在E步中，算法将“猜测”$z^{(i)}$的取值，在M步中，算法将根据猜测的$z^{(i)}$更新高斯混合模型的参数。
E步:

$$w_j^{(i)}:=p(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma)$$

M步：

$$\phi_j = \frac{1}{m}\sum_{i=1}^mw_j^{(i)}$$ $$\mu_j = \frac{\sum_{i=1}^mw_j^{(i)}x^{(i)}}{\sum_{i=1}^mw_j^{(i)}}$$ $$\Sigma_j=\frac{\Sigma_{i=1}^mw_j^{(i)}(x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum_{i=1}^m1\{z^{(i)}=j\}}$$

在E步中，在给定$x^{(i)}$和模型参数下，计算$z^{(i)}$的后验概率。例如，使用贝叶斯公式：

$$p(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma)=\frac{p(x^{(i)}|z^{(i)}=j;\mu,\Sigma)p(z^{(i)}=j;\phi)}{\sum_{l=1}^kp(x^{(i)}|z^{(i)}=l;\mu,\Sigma)p(z^{(i)}=l;\phi)}$$

其中$p(x^{(i)}|z^{(i)}=j;\mu,\Sigma)$来自给定$u_j,\Sigma_j和x^{(i)}$之后的高斯分布，$p(z^{(i)}=j;\phi)$来自$\phi_j$。

现在比较已知$z^{(i)}$和未知的情况，如果已知，那么只有一个高斯模型，每个数据点都来自该模型，所以可以求解，如果未知，则不知道每个数据点到底来自那个分模型，所以只有使用EM算法(待证明)

和K-means法类似，EM算法有出现局部最优的可能，所有多次初始化参数会有更好的表现。现在对于该算法还有一些问题，即算法是如何推导的？如何保证该算法会收敛？,需要在接下来证明。