机器学习-白板推导 11. 高斯混合模型

1. GMM 介绍

通过将更基本的概率分布(如高斯分布)进行线性组合的叠加方法，可以被形式化为概率模型，被称为混合模型(mixture distributions)。

——PRML p82

而GMM(Gaussian Mxture Model)是将多个高斯分布线性叠加在一起的概率模型。

如下图所示一维高斯混合分布例子。(PRML p82)

从两个角度来看GMM：

从几何角度：加权平均。

每个高斯分布可表示为 $N(\mu_k, \Sigma_k)$ ，根据定义加权平均即：

$P(x) = \sum_{k=1}^K \alpha_k N(\mu_k, \Sigma_k) , \quad 且 \sum_{k=1}^K \alpha_k=1 \tag{1}$

从混合模型(或者生成模型)角度

我们假定数据为 $x: \text{observerd variable}$ , 隐变量为 $z: \text{latent variable}$ ，其中 $z$ 是属于哪个高斯分布的隐变量(离散随机变量)。

z	$c_1$	$c_2$	…	$c_K$
p(z)	$p_1$	$p_2$	…	$p_k$

这里 $p_k$ 相当于几何角度的加权权重。而根据上述定义画出高斯混合模型的概率图如下：

其中 $N$ 代表样本个数。实际上，如下图所示(徐亦达em讲义 )，对于每个样本点，有可能来自于 $c_1, c_2, c_3$ 这3个类别的高斯分布，只是概率大小不同而已，如上表所示对应不同的概率。这就是引入隐变量z的意义，它代表着我们无法确定的量，但是决定了样本的来自与来哪些高斯分布，我们计算时按照概率线性叠加来确定模型。

2. MLE来求解GMM

由上小节中，我们知道GMM的pdf由观测数据和隐变量来决定：

$\begin{align} P(x) &= \sum_zP(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 \cdot N(x|\mu_k, \Sigma_k) \\ \end{align} \tag{2}$

其中， $\sum_{k=1}^Kp_k=1$ 现在，整个模型中数据和参数可表示为：

$\begin{align} &X： \text{observerd variable}, \quad X= (x_1, x_2, \cdots, x_N)\\ &(X, Z)： \text{complete variable}\\ &\Theta: \text{parameter}, \quad \Theta=(p_1, p_2, \cdots,p_k, u_1, \cdots, u_k, \Sigma_1, \cdots, \Sigma_k)\\ \end{align} \tag{3}$

那么根据式2用MLE有：

$\begin{align} \hat \Theta_{MLE} &= \text{argmax}_\theta \log P(X)\\ & = \text{argmax}_\theta \log \prod_{i=1}^NP(x_i) \\ & = \text{argmax}_\theta\sum_{i=1}^N \log \sum_{i=1}^K p_k \cdot N(x_i|\mu_k, \Sigma_k) \\ \end{align} \tag{4}$

对于式4， $\log$ 里面是连加，非常难以计算其解析解。一般使用EM算法来计算。

3. EM求解GMM(E步)

直接用EM 算法公式7结论，即Q函数：

$\begin{align} \theta^{(t+1)} &=\text{argmax}_\theta \int_Z \log P(X, Z|\theta) P(Z|X, \theta^{(t)} dZ\\ &= \text{argmax}_\theta E_{P(Z|X, \theta^{(t)})}[\log P(X, Z|\theta)] \end{align} \tag{5}$

我们发现要用到后验概率 $p(z|x)$ 和联合概率。

$\begin{align} p(x, z) &= p(z)p(x|z) =p_z \cdot \mathcal{N}(x|\mu_z, \Sigma_z)\\ p(z|x)&= \frac{p(x,z)}{p(x)} = \frac{p_z \cdot \mathcal{N}(x|\mu_z, \Sigma_z)}{\sum_{k=1}^Kp_k \cdot \mathcal{N}(x|\mu_k, \Sigma_k)} \end{align} \tag{6}$

根据式5有：

$\begin{align} Q(\theta, \theta^{(t)}) &= \sum_Z \log p(X, Z|\theta) \cdot p(Z|X, \theta^{(t)})\\ &=\sum_{z_1, z_2, \cdots, z_N} \log \prod_{i=1}^N p(x_i, z_i|\theta) \cdot \prod_{i=1}^N p(z_i|x_i,\theta^{(t)}) \\ &=\sum_{z_1, z_2, \cdots, z_N} \sum_{i=1}^N\log p(x_i, z_i|\theta) \cdot \prod_{i=1}^N p(z_i|x_i,\theta^{(t)}) \\ &=\sum_{z_1, z_2, \cdots, z_N} \left ( \log p(x_1, z_1|\theta) + \log p(x_2, z_2|\theta) + \cdots + \log p(x_1, z_1|\theta) \log p(x_i, z_i|\theta) \right )\cdot \prod_{i=1}^N p(z_i|x_i,\theta^{(t)}) \\ \end{align} \tag{7}$

对于式7中，我们提出 $\log p(x_1, z_1|\theta)$ 项来化简：

$\begin{align} &\sum_{z_1, z_2, \cdots, z_N} \log p(x_1, z_1|\theta) \cdot \prod_{i=1}^N p(z_i|x_i,\theta^{(t)}) \\ &= \sum_{z_1, z_2, \cdots, z_N} \log p(x_1, z_1|\theta) \cdot p(z_1|x_1,\theta^{(t)}) \prod_{i=2}^N p(z_i|x_i,\theta^{(t)}) \\ &= \sum_{z_1} \log p(x_1, z_1|\theta) \cdot p(z_1|x_1,\theta^{(t)}) \sum_{z_2, \cdots, z_N}\prod_{i=2}^N p(z_i|x_i,\theta^{(t)}) \\ &= \sum_{z_1} \log p(x_1, z_1|\theta) \cdot p(z_1|x_1,\theta^{(t)}) \sum_{z_2} p(z_2|x_2,\theta^{(t)})\sum_{z_3} p(z_3|x_3,\theta^{(t)})\cdots\sum_{z_N} p(z_N|x_N,\theta^{(t)}) \\ &= \sum_{z_1} \log p(x_1, z_1|\theta) \cdot p(z_1|x_1,\theta^{(t)}) \cdot 1\cdot 1\cdots1 \\ &= \sum_{z_1} \log p(x_1, z_1|\theta) \cdot p(z_1|x_1,\theta^{(t)}) \end{align} \tag{8}$

同理，我们可以得到 $\log p(x_N, z_N|\theta)$ 简化表示，

$\begin{align} &\sum_{z_1, z_2, \cdots, z_N} \log p(x_i, z_i|\theta) \cdot \prod_{i=1}^N p(z_i|x_i,\theta^{(t)}) \\ &= \sum_{z_i} \log p(x_i, z_i|\theta) \cdot p(z_i|x_i,\theta^{(t)}) \end{align} \tag{9}$

综上，式7化简并用式6代入：

$\begin{align} Q(\theta, \theta^{(t)}) &=\sum_{z_1, z_2, \cdots, z_N} \left ( \log p(x_1, z_1|\theta) + \log p(x_2, z_2|\theta) + \cdots + \log p(x_1, z_1|\theta) \log p(x_i, z_i|\theta) \right )\cdot \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) \cdot p(z_i|x_i,\theta^{(t)}) \\ &=\sum_{i=1}^{N} \sum_{z_i} \log \left[p_{z_i} \cdot \mathcal{N}(x_i|\mu_{z_i}, \Sigma_{z_i})\right]\cdot \frac{p_{z_i}^{(t)} \cdot \mathcal{N}(x_{z_i}|\mu_{z_i}^{(t)} , \Sigma_{z_i}^{(t)} )}{\sum_{k=1}^Kp_k^{(t)} \cdot \mathcal{N}(x_i|\mu_k^{(t)} , \Sigma_k^{(t)} )}\\ \end{align} \tag{10}$

这里，由于 $\theta^{(t)}$ 是计算得到，跟 $\theta$ 无关，我们目的是求 $\theta$ ,不妨简写下。

$\frac{p_{z_i}^{(t)} \cdot \mathcal{N}(x_{z_i}|\mu_{z_i}^{(t)} , \Sigma_{z_i}^{(t)} )}{\sum_{k=1}^Kp_k^{(t)} \cdot \mathcal{N}(x_i|\mu_k^{(t)} , \Sigma_k^{(t)} )} = p(z_i|x_i, \theta^{(t)}) \tag{11}$

根据式10， 11继续简化：

$\begin{align} Q(\theta, \theta^{(t)}) &= \sum_{i=1}^{N} \sum_{z_i} \log \left[p_{z_i} \cdot \mathcal{N}(x_i|\mu_{z_i}, \Sigma_{z_i})\right]\cdotp(z_i|x_i, \theta^{(t)}) \\ &= \sum_{z_i} \sum_{i=1}^{N} \log \left[p_{z_i} \cdot \mathcal{N}(x_i|\mu_{z_i}, \Sigma_{z_i})\right]\cdotp(z_i|x_i, \theta^{(t)}) \\ &= \sum_{k=1}^K \sum_{i=1}^{N} \log \left[p_{k} \cdot \mathcal{N}(x_i|\mu_{k}, \Sigma_{k})\right]\cdot p(z_i=c_K|x_i, \theta^{(t)}) \\ &= \sum_{k=1}^K \sum_{i=1}^{N} \log \left[p_{k} + \log\mathcal{N}(x_i|\mu_{k}, \Sigma_{k})\right]\cdot p(z_i=c_K|x_i, \theta^{(t)}) \\ \end{align} \tag{12}$

4. EM求解GMM(M步)

EM算法中M步的迭代公式为：

$Q^{(t+1)} = \text{argmax}_\theta \ Q(\theta, \theta^{(t)}) \tag{13}$

我们只介绍怎么求参数中的 $p_k$ ,其余参数类似求解，根据式12有：

$\begin{align} p_{k}^{(t+1) }&= \text{argmax}_{p_k} \sum_{k=1}^K \sum_{i=1}^{N} \log \left[p_{k} + \log\mathcal{N}(x_i|\mu_{k}, \Sigma_{k})\right]\cdot p(z_i=c_K|x_i, \theta^{(t)})\\ &=\text{argmax}_{p_k} \sum_{k=1}^K \sum_{i=1}^{N} \log p_{k} \cdot p(z_i=c_K|x_i, \theta^{(t)}) \\ \quad \quad \quad &s.t. \ \sum_{k=1}^Kp_k=1 \end{align} \tag{14}$

这里将 $p_k$ 无关项忽略掉了，再利用拉格朗日乘子法有(转换为求极小值，加个负号)：

$L(p_k, \lambda)= - \sum_{k=1}^K \sum_{i=1}^{N} \log p_{k} \cdot p(z_i=c_K|x_i, \theta^{(t)}) + \lambda(\sum_{k=1}^Kp_k-1 ) \tag{15}$

式15对 $p_k$ 求偏导有:

$\begin{align} \frac{\partial L}{\partial p_k}&= - \sum_{i=1}^{N} \frac{1}{p_k}\cdot p(z_i=c_K|x_i, \theta^{(t)}) + \lambda =0\\ &\Longrightarrow p_{k}\lambda - \sum_{i=1}^{N} p(z_i=c_K|x_i, \theta^{(t)})=0 \end{align} \tag{16}$

因为对于所有的 $p_k$ 都要满足，那么有：

$\sum_{k=1}^Kp_{k}\lambda - \sum_{k=1}^K\sum_{i=1}^{N} p(z_i=c_K|x_i, \theta^{(t)})=0 \tag{17}$

而 $\sum_{k=1}^Kp(z_i=c_K|x_i, \theta^{(t)})=1$ ,因此式17有：

$\lambda - N=0 \tag{18}$

再代入是式16中有：

$p_k^{(t+1)} = \frac{1}{N}\sum_{i=1}^{N} p(z_i=c_K|x_i, \theta^{(t)}) \tag{19}$

这就是EM算法求解GMM模型参数的全部过程。