高斯混合算法（GMM）与最大期望算法（EM）的推导

由于EM算法的推导常使用GMM算法来举例子，故下面先介绍高斯混合算法

一般的高斯算法（单个高斯）

上式是单个高斯分布，对于单个高斯分布，给定一组观测数据，求参数时通常用MLE（极大似然估计)就可以了，具体做法就是分别对均值和方差求导数，然后令导数=0求解即可。

高斯混合算法

上面是高斯混合算法的一般形式和对数似然函数形式。与单个高斯分布相比，GMM算法是由k个高斯加权平均混合而成的，$\pi_{k}$πk​是第k个高斯所占的权重（也就是每个高斯的先验概率），每个高斯均有自己的均值和方差，因此GMM共有$3k$3k个未知参数，但是又因为$\pi_{k}$πk​的和为1，故最终若确定了前面$k-1$k−1个$\pi_{i}$πi​，最后一个$\pi_{k}$πk​就确定了，故共有$3k-1$3k−1个未知参数。

从似然函数可以看出，GMM算法的对数似然函数中$log$log里面是和式，故不能使用MLE来求解这$3k-1$3k−1个未知参数。应该使用EM算法来求解。

从这个图可以看出，样本空间中的一个样本点$x_{1}$x1​的概率值是$x_{1}$x1​分别由2个高斯产生的概率加权而成的，这个权值就是前面的$\pi_{k}$πk​。从这里也可以看出GMM算法是软聚类算法，一个样本点是同时属于多个cluster，只是属于每个cluster的程度不同，样本点$x_{1}$x1​最终属于哪个类就取$\pi_{k}$πk​最大的那一类。

公式推导

下面的公式推导要用到贝叶斯公式和全概率公式，如果不清楚可以看链接：全概率公式、贝叶斯公式推导过程

单个样本$x$x的概率如下式

对于(1)式，对于单个样本点$x$x，虽然我们并不能观测到$x$x是属于哪一类的，但是$x$x肯定是属于$k$k类中的某一类，因此这里就存在一个隐变量，我们设为$z$z，表示样本点$x$x属于哪一类，通过引入隐变量可以简化参数求解。其中$z \isin {1,,,k}$z∈1,,,k

上面的式子表示样本点$x$x属于第k类的概率是$\pi_{k}$πk​，若确定了样本点$x$x属于第k类的概率$\pi_{k}$πk​，则在这个条件下，样本点在第k类高斯分布中的概率分布就变成了单个的高斯分布。

最终将样本点$x$x在k个高斯分布下的概率累加就是(2)式，也就是最终的GMM分布的概率公式

（2）式是由全概率公式得到的
（$可以看作最终的概率p(x)被分割为k个独立的子事件p(x|z=k)$可以看作最终的概率p(x)被分割为k个独立的子事件p(x∣z=k)），但是将值代入之后，与（1）式具有相同形式，但是含有参数隐变量，通过（2）式我们就可以证明，引入隐变量$z$z之后，$x$x的概率分布并没有发生变化。

可以将（2）式改写为（3）式，也就是加了一些GMM的参数，可以这样改写的原因是很简单，比如以$p(x|z=k)$p(x∣z=k)为列，这个公式必定是样本点在第k个高斯分布下的概率分布，所以在算$p(x|z=k)$p(x∣z=k)时必定已经知道了第k个高斯分布的参数$\mu_{k}，\Sigma_{k}$μk​，Σk​，分别表示第k个高斯分布的均值和方差。故可以将$p(x|z=k)$p(x∣z=k)改写为$p(x|z=k，\mu_{k}，\Sigma_{k})$p(x∣z=k，μk​，Σk​)，其他也类似。

由贝叶斯定理可以知道，$p(z=k)是先验概率，p(x|z=k)是似然概率$p(z=k)是先验概率，p(x∣z=k)是似然概率，那么可以很方便的求出后验概率$p(z|x)$p(z∣x)。

给定一个样本点$x_{n}$xn​，

对于一个样本$x_{n}$xn​，其后验概率$\gamma_{nk}$γnk​的和为1，表示样本$x_{n}$xn​属于第k类cluster的概率。（4）式的意义就是，在已知样本$x_{n}$xn​和GMM参数的情况下，这个样本是由第k个高斯产生的概率有多大。

将（1）式变形为（5）式，其中????是k个高斯的参数，每个高斯含有3个参数，X是样本空间。

EM算法的推导

（6）式可由概率论的知识得到，其含义是在已知GMM参数的情况下，$X,Z$X,Z的联合概率分布。
将（6）式中的$p(Z|X，\theta)$p(Z∣X，θ)移到等号左边并取对数
$\tag{7} logp(X|\theta) = log{p(X, Z|\theta) \over p(Z|X,\theta)}$logp(X∣θ)=logp(Z∣X,θ)p(X,Z∣θ)​(7)

将（7）式等号右边分子分母同时除以$Z的真实分布q(Z)$Z的真实分布q(Z)：

在上式两边同时乘以$Z的真实分布q(Z)并对Z积分$Z的真实分布q(Z)并对Z积分得（相当于对$logp(X|\theta)$logp(X∣θ)求期望）

由于$logp(X|\theta)$logp(X∣θ)不含有Z，故最后$q(Z)$q(Z)积分结果为1。
对等式右边积分结果如下：

第二项连同负号是KL散度的形式，恒大于等于0，故有$logp(X|\theta) \ge Q$logp(X∣θ)≥Q

即Q函数是似然函数$logp(X|\theta)$logp(X∣θ)的一个下界，要最大化似然函数，只要最大化Q函数就可以了。$q(Z)是Z$q(Z)是Z的真实分布，虽然我们无法观测到，但是必定存在，在推导中用$Z的上一次分布的结果p(Z|X, \theta^{old})$Z的上一次分布的结果p(Z∣X,θold)来代替$q(Z)$q(Z)。$argmax$argmax中，后面那一项与????没有关系，故可以甩掉。

最后令上面的结果等于新的$Q$Q，新的Q函数中含有已知量$\theta^{old}和未知量\theta$θold和未知量θ。
至此，EM算法推导结束。

下面总结一下EM算法：

E-step：根据参数$\theta^{old}$θold计算每个样本由第k类高斯产生的概率，也就是前面提到的后验概率$\gamma_{nk}$γnk​，将其值带入 $Q$Q函数，如上式所示。
根据Q函数的表达式可以看出，Q函数相当于是对变量$logp(z_{i}, x_{i}│\theta)$logp(zi​,xi​│θ)求期望（将$p(z_{i}|x_{i}, \theta^{old})$p(zi​∣xi​,θold)看作其概率分布）。
这里的Q函数其实就是我们要求的似然函数的下界。

M-Step：根据计算得到的$\gamma_{nk}$γnk​，求出含有$θ$θ的似然函数的下界（也就是Q函数）并最大化它，得到参数$θ$θ的新值。
从图中可以看出，EM算法是迭代的求解参数，但是直接求解似然函数有困难，所以找到似然函数的一个下界Q函数，
每次先固定$Θ$Θ，然后求出$Q(Θ)$Q(Θ)的表达式，再最大化$Q(Θ)$Q(Θ)。$Q$Q函数相当于是对$logp(z_{i}, x_{i}│\theta)$logp(zi​,xi​│θ)求期望，故称作最大期望算法。

看不懂的同学可以看悉尼科技大学徐亦达的视频或者b站上的白板推导视频。