GMM算法

高斯混合模型

高斯混合模型是一种生成模型，从几何角度来看，可视为数据的概率密度函数为多个高斯分布的加权平均，即： $$\begin{array}{rl}p(x)=\sum _{k=1}^K& {\alpha }_{k}N(x|{\mu }_k,{\Sigma }_k)\\ \sum _{k=1}^K{\alpha }_k& =1\end{array}$$

从混合模型上看，x为observed variable，而z为latent variable，z代表了变量x是属于哪一个高斯分布。则 $$\begin{array}{rl}p(x）& =\sum _{z}p(x,z)\\ & =\sum _{k=1}^{K}p(x,z=c_k)\\ & =\sum _{k=1}^{K}p(z=c_k)p(x|z=c_k)\\ & =\sum _{k=1}^K{p}_{k}N(x|{\mu }_k,{\Sigma }_k)\end{array}$$

在高斯混合模型中，我们需要计算的参数为$p_k,{\mu }_k,{\Sigma }_k$，即$\theta =\{p_1,p_2,\dots ,p_K,{\mu }_1,{\mu }_2,\dots ,{\mu }_K,{\Sigma }_1,{\Sigma }_2,\dots ,{\Sigma }_K\}$。设观测数据为$X=\{x_1,x_2,\dots ,x_N\}$，$(X,Z)$为完整数据。如果我们希望利用极大似然法来对参数进行求解，则计算公式为 $$\begin{array}{rl}\hat{\theta }& =\underset{\theta }{\mathrm{argmax}}\log P(X)\\ & =\underset{\theta }{\mathrm{argmax}}\log \prod _{i=1}^{N}P(x)\\ & =\underset{\theta }{\mathrm{argmax}}\sum _{i=1}^N\log \sum _{k=1}^K{p}_{k}N(x|{\mu }_k,{\Sigma }_k)\end{array}$$

然后，由于上式$\log$中含有加法，所以如果对其直接进行求导计算参数$\theta$，无法得到解析解。因此，我们采用EM算法来迭代的对高斯混合模型中的参数进行求解。

EM - E-step

EM算法：$$\begin{array}{rl}{\theta }^{t+1}& =\underset{\theta }{\mathrm{argmax}}{E}_{Z|X,{\theta }^t}\left[\log P(X,Z|\theta )\right]\\ & =\underset{e}{\mathrm{argmax}}\theta Q(\theta ,{\theta }^t)\end{array}$$

其中$$\begin{array}{rl}Q(\theta ,{\theta }^t)& ={\int }_z\log P(X,Z|\theta )P(Z|X,{\theta }^t)dZ\\ & =\sum _{z_1,z_2,\dots ,z_k}\log \prod _{i=1}^{N}P(x_i,z_i|\theta )\prod _{i=1}^{N}P(z_i|x_i,{\theta }^t)\\ & =\sum _{z_1,z_2,\dots ,z_k}\left(\sum _{i=1}^N\log P(x_i,z_i|\theta )\right)\prod _{i=1}^{N}P(z_i|x_i,{\theta }^t)\\ & =\sum _{i=1}^N\sum _{z_1,z_2,\dots ,z_k}\log P(x_i,z_i|\theta )\prod _{i=1}^{N}P(z_i|x_i,{\theta }^t)\\ & =\sum _{i=1}^N\sum _{z_i}\log P(x_i,z_i|\theta )P(z_i|x_i,{\theta }^t)\\ & =\sum _{i=1}^N\sum _{z_i}\log p_{z_i}N(x_i|{\mu }_k,{\Sigma }_k)\frac{p_{z_i}^{t}N(x_i|{\mu }_k^t,{\Sigma }_k^t)}{{\sum }_{k=1}^K{p}_k^{t}N(x|{\mu }_k^t,{\Sigma }_k^t)}\\ & =\sum _{i=1}^N\sum _{z_i}\left(\log p_{z_i}+\log N(x_i|{\mu }_k,{\Sigma }_k)\right)\frac{p_{z_i}^{t}N(x_i|{\mu }_k^t,{\Sigma }_k^t)}{{\sum }_{k=1}^K{p}_k^{t}N(x|{\mu }_k^t,{\Sigma }_k^t)}\\ & =\sum _{i=1}^N\sum _{k=1}^K(\log p_k+\log N(x_i|{\mu }_k,{\Sigma }_k))P(z_i=c_k|x_i,{\theta }^t)\end{array}$$

其中$\frac{p_{z_i}^{t}N(x_i|{\mu }_k^t,{\Sigma }_k^t)}{{\sum }_{k=1}^K{p}_k^{t}N(x|{\mu }_k^t,{\Sigma }_k^t)}=P(z_i|x_i,{\theta }^t)$与$\theta$无关。

我们先求$p_k^{(t+1)}$ $$\begin{array}{r}\{\begin{array}{lr}{p}_k^{(t+1)}=\underset{p_k}{\mathrm{argmax}}\sum _{i=1}^N\sum _{k=1}^K\log p_{k}P(z_i=c_k|x_i,{\theta }^t)& \\ \sum _{k=1}^K{p}_k=1& \end{array}\end{array}$$ 将上述带约束的优化问题化为拉格朗日方程 $$\begin{array}{r}\mathcal{L}(p_k.\lambda )=\sum _{i=1}^N\sum _{k=1}^K\log p_{k}P(z_i=c_k|x_i,{\theta }^t)+\lambda (\sum _{k=1}^K{p}_k-1)\end{array}$$ 有 $$\begin{array}{r}\frac{\partial \mathcal{L}(p_k,\lambda )}{\partial p_k}=\sum _{i=1}^N\frac{1}{p_k}P(z_i=c_k|x_i,{\theta }^t)+\lambda =0\end{array}$$ 两边同时对k求和有 $$\begin{array}{r}\sum _{k=1}^K\sum _{i=1}^{N}P(z_i=c_k|x_i,{\theta }^t)+\sum _{k=1}^K\lambda p_k=0\end{array}$$ 得$\lambda =-N$，则$p_k=\frac{\sum _{i=1}^{N}P(z_i=c_k|x_i,{\theta }^t)}{N}$。而${\mu }_t,{\Sigma }_k$的求解，因为无约束，所以可直接对$Q(\theta ,{\theta }^t)$求导。