高斯混合模型与EM算法

这周主要学习了高斯混合模型以及EM算法的经典应用。Gaussian Mixture Model (GMM)即可以用于聚类,也可以用于估计概率密度函数。假设我们有一个训练集\(x^{(1)},\ldots,x^{(m)}\), 这训练集是无监督的,所以没有分类标签。

QQ截图20130411144057

我们假设假设数据服从 Mixture Gaussian Distribution ,即把数据看作是从许多个 Gaussian Distribution 中生成出来的。具体就是建立联合分布 \(p(x^{(i)},z^{(i)})=p(x^{(i)}|z^{(i)})p(z^{(i)})\)。 这里$z^{(i)} Multinomial() \(,其中\){j}0,^{k}{j=1}{j}=1\(,\){j}\(即\)p(z{(i)}=j)\(, 而\)x{(i)}|z^{(i)}=j N(_j,_j)\(。混合高斯模型的主要分为两个步骤,是首先随机地在这\){1,,K}\(个高斯分布中之中选一个(用\)z{(i)}\(表示),再根据选取分布中生成数据\)x{(i)}\(。要注意的是,因为这些数据都是未标注的,这里我们并不知道\)z{(i)}\(的值,所以\)z{(i)}$也被称作隐藏变量。

高斯混合模型的参数有\(\phi,\mu,\Sigma\)。为了估计这些参数,我们写出它们的似然函数:
\[\begin{split}l(\phi,\mu,\Sigma) & =\sum^{m}_{i=1}{\log{p(x^{(i)};\phi,\mu,\Sigma)}} \\& =\sum^{m}_{i=1}{\log{\sum^{K}_{z^{(i)}=1}p(x^{(i)}|z^{(i)};\mu,\Sigma)p(z^{(i)};\phi}}) \\ \end{split}\]
这个似然函数在log之中又存在加和,所以通过普通的求导方法是不能得出最大似然的。之前提到\(z^{(i)}\)是用来表示数据\(x^{(i)}\)是来自\(k\)个高斯分布中的哪一个的,假设我们已经知道了\(z^{(i)}\)是多少(比如说\(z^{(i)}=k\)),那么求解决这个极大似然问题就简单多了。因为\(z^{(i)}=k\),对于任意的\(j\),只有\(\phi_{k}=p(z^{(i)}=k)=1\),其余全部都是0,因此在1到\(K\)的加和中,只有一个值是存在的,其余全为0。 所以似然函数可以化简成下面这样:
\[\begin{split} l(\phi,\mu,\Sigma) & =\sum^{m}_{i=1}{ \log{p(x^{(i)}|z^{(i)};\mu,\Sigma)}+\log{p(z^{(i)},\phi)}} \\ \end{split}\]
对此似然函数求极大值,得到参数值如下:
\[ \begin{split} & \phi_j=\frac{1}{m}\sum^{m}_{i=1}1\{z^{(i)}=j\} \\ & \mu_j=\frac{\sum^m_{i=1}1\{z^{(i)}=j\}x^{(i)}}{\sum^m_{i=1}1\{z^{(i)}=j\}} \\ & \Sigma_j=\frac{\sum^m_{i=1}1\{z^{(i)}=j\}(x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum^m_{i=1}1\{z^{(i)}=j\}} \\ \end{split}\]

但是,事实上我们并不知道这些\(z^{(i)}\)的值是多少。如果我们有了这些值,所有的问题都迎刃而解了。下文对于混合高斯模型的EM算法主要分为两步。在E步里,我们猜出所有的\(z^{(i)}\)的值,然后在M步中根据猜出的值,更新模型中的参数,反复迭代。

  • E步: 具体地,对于所有的\(i,j\),我们设
    \[ \begin{split} w^{i}_j:=p(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma) \end{split}\]

    这里\(w^{i}_j\)\(z^{(i)}=j\)的一个后验概率。(为什么是后验概率?请见一般形式的EM算法)

  • M步: 我们假设\(w^{i}_j\)是已知的,求得参数(详细推导见高斯混合模型参数估计详细推导过程)
    \[ \begin{split} & \phi_j=\frac{1}{m}\sum^{m}_{i=1}w^{i}_j \\ & \mu_j=\frac{\sum^m_{i=1}w^{i}_jx^{(i)}}{\sum^m_{i=1}w^{i}_j} \\ & \Sigma_j=\frac{\sum^m_{i=1}w^{i}_j(x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum^m_{i=1}w^{i}_j} \\ \end{split}\]
    相互迭代直到似然函数的值收敛。 在E步中,我们使用了后验概率,可以通过贝叶斯公式来计算:
    \[ p(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma)=\frac{p(x^{(i)}|z^{(i)}=j;\mu,\Sigma)p(z^{(i)}=j;\phi)}{\sum^k_{l=1}{p(x^{(i)}|z^{(i)}=l;\mu,\Sigma)p(z^{(i)}=l;\phi)}}\]

    式子中的\(p(x^{(i)}|z^{(i)}=j;\mu,\Sigma)p(z^{(i)}=j;\phi)\)是用一个拥有平均值\(\mu_j\)和协方差\(\Sigma_j\)的高斯分布在\(x^{(i)}\)上的概率密度算出的;\(p(z^{(i)}=j;\phi)\)是由\(\phi_j\)算出的。计算得到的\(w^{i}_j\)代表了对\(z^{(i)}\)的软猜测。

PS:软猜测是指猜测的结果是\([0,1]\)之间的概率值,而硬猜测为单值(0或1)。

PPS:
2013年3月30日更新

今日重看EM算法,发现以前真是胡言乱语,重新更正下:

CS229中对EM的介绍没有任何问题,只是他先用EM的思想讲了混合高斯模型,再在之后的一章介绍一般的EM算法,并对高斯混合模型进行重述。

  1. 为什么选取后验概率\(p(w|x)\)

答:并不是特地选取的后验概率\(p(w|x)\),而是似然函数与其下界函数相等时的Z的概率分布刚好是后验分布。

  1. EM算法的全称是期望最大化算法,取的是什么的期望,没有详细说明。

答:其实在后一章已经说了,我没有仔细看,取的是似然函数\(L(X,Z;\theta)\)在分布\(Z\sim P(Z|X;\theta)\)上的期望\(E_{Z|X,\theta_t}[L(X,Z;\theta)]\)

这篇文章用于理解高斯混合模型挺好,但是用来理解EM算法还有一些欠缺(因为根本没介绍EM么)。除了CS229,PRML中还有第9章对EM算法的介绍(complete data和incomplete data),更加接近一般的EM思路。

参考: 1. 斯坦福大学公开课 :机器学习课程 CS229 2. 《Pattern Recognition And Machine Learning》