机器学习笔记之高斯混合模型(四)EM算法求解高斯混合模型(M步操作)

引言

上一节介绍了使用EM算法求解高斯混合模型参数的E步操作，本节将继续介绍后续的M步操作。

回顾：EM算法求解高斯混合模型的E步操作

• 高斯混合模型$P(\mathcal{X})$引入隐变量$\mathcal{Z}$后的表示结果如下：
  $$P(\mathcal{X})=\sum _{i=1}^{\mathcal{K}}{p}_k\cdot \mathcal{N}(\mathcal{X}\mid {\mu }_k,{\Sigma }_k)$$
  $p_k$表示隐变量$\mathcal{Z}$选择具体某项离散参数$z_k$的概率分布：
  $$p_k=P(\mathcal{Z}=z_k)$$
  $\mathcal{N}(\mathcal{X}\mid {\mu }_k,{\Sigma }_k)$表示隐变量$\mathcal{Z}=z_k$条件下，样本$\mathcal{X}$服从均值为${\mu }_k$，协方差为${\Sigma }_k$ 的高斯分布：
  $$\mathcal{X}\mid \mathcal{Z}=z_k\sim \mathcal{N}(\mathcal{X}\mid {\mu }_k,{\Sigma }_k)$$
• 对应的联合概率分布$P(\mathcal{X},\mathcal{Z})$表示如下：
  $$\begin{array}{rl}P(\mathcal{X},\mathcal{Z})& =P(\mathcal{Z})\cdot P(\mathcal{X}\mid \mathcal{Z})\\ & =p_{\mathcal{Z}}\cdot \mathcal{N}(\mathcal{X}\mid {\mu }_{\mathcal{Z}},{\Sigma }_{\mathcal{Z}})\\ & =\prod _{i=1}^N{p}_{z^{(i)}}\cdot \mathcal{N}(\mathcal{X}\mid {\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}})\end{array}$$
  其中$p_{z^{(i)}}$表示 $x^{(i)}$属于各高斯分布的概率组成的向量。数学符号表示如下：
  $p_j^{(i)}$表示样本$x^{(i)}$属于离散常量$z_j$对应概率分布$\mathcal{N}({\mu }_j,{\Sigma }_j)$的概率结果。
  $$\begin{gathered} p_{z^{(i)}}={\left(p_1^{(i)},p_2^{(i)},\cdots ,p_{\mathcal{K}}^{(i)}\right)}^T \\ {p}_j^{(i)}=P(x^{(i)}\to z_j)=P(x^{(i)}\in \mathcal{N}({\mu }_j,{\Sigma }_j))(j=1,2,\cdots ,\mathcal{K}) \end{gathered}$$
  同理，${\mu }_{z^{(i)}}$表示$x^{(i)}$属于各高斯分布的期望组成的向量。数学符号表示如下：
  ${\mu }_j^{(i)}$表示$x^{(i)}$属于离散常量$z_j$对应概率分布$\mathcal{N}({\mu }_j,{\Sigma }_j)$的期望信息。
  $$\begin{gathered} {\mu }_{z^{(i)}}={\left({\mu }_1^{(i)},{\mu }_2^{(i)},\cdots ,{\mu }_{\mathcal{K}}^{(i)}\right)}^T \\ {\mu }_j^{(i)}={\mu }_j\in x^{(i)}\sim \mathcal{N}({\mu }_j,{\Sigma }_j)(j=1,2,\cdots ,\mathcal{K}) \end{gathered}$$
  ${\Sigma }_{z^{(i)}}$表示$x^{(i)}$属于各高斯分布的协方差组成的向量。数学符号表示如下：
  ${\Sigma }_j^{(i)}$表示$x^{(i)}$属于离散常量$z_j$对应概率分布$\mathcal{N}({\mu }_j,{\Sigma }_j)$的协方差信息。
  $$\begin{gathered} {\Sigma }_{z^{(i)}}={\left({\Sigma }_1^{(i)},{\Sigma }_2^{(i)},\cdots ,{\Sigma }_{\mathcal{K}}^{(i)}\right)}^T \\ {\Sigma }_j^{(i)}={\Sigma }_j\in x^{(i)}\sim \mathcal{N}({\mu }_j,{\Sigma }_j)(j=1,2,\cdots ,\mathcal{K}) \end{gathered}$$
• 关于隐变量的后验概率$P(\mathcal{Z}\mid \mathcal{X})$表示如下：
  $$\begin{array}{rl}P(\mathcal{Z}\mid \mathcal{X})& =\frac{P(\mathcal{X},\mathcal{Z})}{P(\mathcal{X})}\\ & =\frac{{\prod }_{i=1}^N{p}_{z^{(i)}}\cdot \mathcal{N}(\mathcal{X}\mid {\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}})}{{\sum }_{i=1}^{\mathcal{K}}{p}_k\cdot \mathcal{N}(\mathcal{X}\mid {\mu }_k,{\Sigma }_k)}\end{array}$$
• 至此，E步操作表示如下：
  令${\mathbb{E}}_{\mathcal{Z}\mid \mathcal{X},{\theta }^{(t)}}\left[\log P(\mathcal{X},\mathcal{Z}\mid \theta )\right]$是关于$\theta ,{\theta }^{(t)}$的函数。即：
  $$\begin{array}{rl}\mathcal{L}(\theta ,{\theta }^{(t)})& ={\mathbb{E}}_{\mathcal{Z}\mid \mathcal{X},{\theta }^{(t)}}\left[\log P(\mathcal{X},\mathcal{Z}\mid \theta )\right]\\ & ={\int }_{\mathcal{Z}}P(\mathcal{Z}\mid \mathcal{X},{\theta }^{(t)})\log P(\mathcal{X},\mathcal{Z}\mid \theta )d\mathcal{Z}\end{array}$$
  经过E步的求解过程，求得最终表示结果如下：
  $$\mathcal{L}(\theta ,{\theta }^{(t)})=\sum _{i=1}^N\sum _{z^{(i)}}\left[\log p_{z^{(i)}}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}})\right]\cdot \frac{p_{z^{(i)}}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}})}{{\sum }_{k=1}^{\mathcal{K}}{p}_k\cdot \mathcal{N}(x^{(i)}\mid {\mu }_k,{\Sigma }_k)}$$

EM算法M步操作

重新观察E步结果：
$$\mathcal{L}(\theta ,{\theta }^{(t)})=\sum _{i=1}^N\sum _{z^{(i)}}\left[\log p_{z^{(i)}}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}})\right]\cdot \frac{p_{z^{(i)}}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}})}{{\sum }_{k=1}^{\mathcal{K}}{p}_k\cdot \mathcal{N}(x^{(i)}\mid {\mu }_k,{\Sigma }_k)}$$

• 其中$P(\mathcal{X},\mathcal{Z}\mid \theta )$部分表示如下：
  $$\log P(x^{(i)},z^{(i)}\mid \theta )=\log \left[p_{z^{(i)}}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}})\right]$$
  $\theta$具体指(共三项)：
  $$p_{z^{(i)}},{\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}}(i=1,2,\cdots ,N)$$

• $P(\mathcal{Z}\mid \mathcal{X},{\theta }^{(t)})$部分表示如下：
  $$P(z^{(i)}\mid z^{(i)},{\theta }^{(t)})=\frac{p_{z^{(i)}}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}})}{{\sum }_{k=1}^{\mathcal{K}}{p}_k\cdot \mathcal{N}(x^{(i)}\mid {\mu }_k,{\Sigma }_k)}$$
  ${\theta }^{(t)}$具体指(共6项)：
  $$\begin{gathered} p_{z^{(i)}},{\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}}(i=1,2,\cdots ,N) \\ {p}_k,{\mu }_k,{\Sigma }_k(k=1,2,\cdots ,\mathcal{K}) \end{gathered}$$
  由于${\theta }^{(t)}$是上一次迭代得到的参数结果，是已知量；因此将$\mathcal{L}(\theta ,{\theta }^{(t)})$中的${\theta }^{(t)}$项修正过来：
  例如$p_{z^{(i)}}^{(t)}$是${\theta }^{(t)}$的一个解，区别于对应$\theta$的解$p_{z^{(i)}}$。
  $$\mathcal{L}(\theta ,{\theta }^{(t)})=\sum _{z^{(i)}}\sum _{i=1}^N\left[\log p_{z^{(i)}}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}})\right]\cdot \frac{p_{z^{(i)}}^{(t)}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_{z^{(i)}}^{(t)},{\Sigma }_{z^{(i)}}^{(t)})}{{\sum }_{k=1}^{\mathcal{K}}{p}_k^{(t)}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_k^{(t)},{\Sigma }_k^{(t)})}$$
  实际上$\frac{p_{z^{(i)}}^{(t)}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_{z^{(i)}}^{(t)},{\Sigma }_{z^{(i)}}^{(t)})}{{\sum }_{k=1}^{\mathcal{K}}{p}_k^{(t)}\cdot \mathcal{N}(x^{(i)}\mid {\mu }_k^{(t)},{\Sigma }_k^{(t)})}$是由${\theta }^{(t)}$构成的量，它的结果不会对当前迭代步骤$\theta$的最优值产生影响。因此，在这里将其缩写成$P(z^{(i)}\mid x^{(i)},{\theta }^{(t)})$。

• 由于$z_i$本质上是样本$x^{(i)}$所有可能属于的高斯分布组成的向量，即：
  $$z^{(i)}=(z_1^{(i)},z_2^{(i)},\cdots ,z_{\mathcal{K}}^{(i)}{)}^T$$
  并且对应的$p_{z^{(i)}},{\mu }_{z^{(i)}},{\Sigma }_{z^{(i)}}$分别表示如下：
  查看详情移步至传送门
  $$\begin{gathered} p_{z^{(i)}}=(p_1^{(i)},p_2^{(i)},\cdots ,p_{\mathcal{K}}^{(i)}{)}^T \\ {\mu }_{z^{(i)}}=({\mu }_1^{(i)},{\mu }_2^{(i)},\cdots ,{\mu }_{\mathcal{K}}^{(i)}{)}^T \\ {\Sigma }_{z^{(i)}}=({\Sigma }_1^{(i)},{\Sigma }_2^{(i)},\cdots ,{\Sigma }_{\mathcal{K}}^{(i)}{)}^T \end{gathered}$$
  因此，${\sum }_{z^{(i)}}{p}_{z^{(i)}}$分别表示如下：
  $$\sum _{z^{(i)}}{p}_{z^{(i)}}=\sum _{k=1}^{\mathcal{K}}{p}_k^{(i)}\sum _{z^{(i)}}{\mu }_{z^{(i)}}=\sum _{k=1}^{\mathcal{K}}{\mu }_k^{(i)}\sum _{z^{(i)}}{\Sigma }_{z^{(i)}}=\sum _{k=1}^{\mathcal{K}}{\Sigma }_k^{(i)}$$
  基于上述公式，对$\mathcal{L}(\theta ,{\theta }^{(t)})$进行变换：
  L ( θ , θ ( t ) ) = ∑ k = 1 K ∑ i = 1 N log ⁡ [ p k ( i ) ⋅ N ( x ( i ) ∣ μ k ( i ) , Σ k ( i ) ) ] P ( z ( i ) = z k ∣ x ( i ) , θ ( t ) ) = ∑ k = 1 K ∑ i = 1 N [ log ⁡ p k ( i ) + log ⁡ N ( x ( i ) ∣ μ k ( i ) , Σ k ( i ) ) ] P ( z ( i ) = z k ∣ x ( i ) , θ ( t ) ) L(θ,θ(t))=K∑k=1N∑i=1log[p(i)k⋅N(x(i)∣μ(i)k,Σ(i)k)]P(z(i)=zk∣x(i),θ(t))=K∑k=1N∑i=1[logp(i)k+logN(x(i)∣μ(i)k,Σ(i)k)]P(z(i)=zk∣x(i),θ(t))

  L(θ,θ(t))​=k=1∑K​i=1∑N​log[pk(i)​⋅N(x(i)∣μk(i)​,Σk(i)​)]P(z(i)=zk​∣x(i),θ(t))=k=1∑K​i=1∑N​[logpk(i)​+logN(x(i)∣μk(i)​,Σk(i)​)]P(z(i)=zk​∣x(i),θ(t))​
  我们以求解$p_k^{(i)}$在当前时刻的最优解$[p_k^{(i)}{]}^{(t+1)}$为例。上述式子中只有方括号内第一项包含$p_k^{(i)}$，因此则有：
  $$[p_k^{(i)}{]}^{(t+1)}=\underset{p_k^{(i)}}{\mathrm{argmax}}\sum _{k=1}^{\mathcal{K}}\sum _{i=1}^N\log p_k^{(i)}P(z^{(i)}=z_k\mid x^{(i)},{\theta }^{(t)})$$
  并且$p_k^{(i)}$是概率结果，因此$p_k^{(i)}$需要满足约束条件：
  $$\sum _{k=1}^{\mathcal{K}}{p}_k^{(i)}=1$$
  至此，求解$p_{z^{(i)}}$的最优解$p_{z^{(i)}}^{(t+1)}$即：
  $$p_{z^{(i)}}^{(t+1)}=([p_1^{(i)}{]}^{(t+1)},[p_2^{(i)}{]}^{(t+1)},\cdots ,[p_{\mathcal{K}}^{(i)}{]}^{(t+1)}{)}^T$$
  其中任意一项$[p_k^{(i)}{]}^{(t+1)}(k=1,2,\cdots ,\mathcal{K})$使用如下优化函数进行表示：
  $$\{\begin{array}{l}\underset{p_k^{(i)}}{\mathrm{argmax}}{\sum }_{k=1}^{\mathcal{K}}{\sum }_{i=1}^N\log p_k^{(i)}\cdot P(z^{(i)}=z_k\mid x^{(i)},{\theta }^{(t)})\\ s.t.{\sum }_{k=1}^{\mathcal{K}}{p}_k^{(i)}=1\end{array}$$

求解过程

使用拉格朗日乘数法进行求解：

• 构建拉格朗日函数$\mathcal{S}(p_k^{(i)},\lambda )$：
  $$\mathcal{S}(p_k^{(i)},\lambda )=\sum _{k=1}^{\mathcal{K}}\sum _{i=1}^N\log p_k^{(i)}\cdot P(z^{(i)}=z_k\mid x^{(i)},{\theta }^{(t)})+\lambda (\sum _{k=1}^{\mathcal{K}}{p}_k^{(i)}-1)$$
• 拉格朗日函数$\mathcal{S}(p_k^{(i)},\lambda )$对$p_k^{(i)}$求偏导：
  观察第一个连加号${\sum }_{k=1}^{\mathcal{K}}$,只有唯一一个$k$和$p_k^{(i)}$相关，其余均为常数;
  $$\frac{\partial \mathcal{S}(p_k^{(i)},\lambda )}{\partial p_k^{(i)}}=\sum _{i=1}^N\frac{1}{p_k^{(i)}}\cdot P(z^{(i)}=z_k\mid x^{(i)},{\theta }^{(t)})+\lambda$$
• 令$\frac{\partial \mathcal{S}(p_k^{(i)},\lambda )}{\partial p_k^{(i)}}\triangleq 0$，等式两端同乘$p_k^{(i)}$：
  $$\sum _{i=1}^{N}P(z^{(i)}=z_k\mid x^{(i)},{\theta }^{(t)})+p_k^{(i)}\lambda =0$$
• 对 ∀ k ∈ { 1 , 2 , ⋯   , K } \forall k \in \{1,2,\cdots,\mathcal K\} ∀k∈{1,2,⋯,K}，均进行求导并等于0，则有：
  $$\sum _{i=1}^N\sum _{k=1}^{\mathcal{K}}P(z^{(i)}=z_k\mid x^{(i)},{\theta }^{(t)})+\sum _{k=1}^{\mathcal{K}}{p}_k^{(i)}\lambda =0+\cdots +0=0$$
  其中：
  条件概率密度积分~约束条件~
  $$\begin{gathered} \sum _{k=1}^{\mathcal{K}}P(z^{(i)}=z_k\mid x^{(i)},{\theta }^{(t)})=1 \\ \sum _{k=1}^{\mathcal{K}}{p}_k^{(i)}=1 \end{gathered}$$
  整理得：
  $$\lambda =-N$$
  因此，将$\lambda =-N$带回原式，则有：
  $$[p_k^{(i)}{]}^{(t+1)}=\frac{1}{N}\sum _{i=1}^{N}P(z^{(i)}=z_k\mid x^{(i)},{\theta }^{(t)})$$
  基于上式，可以求出$[p_1^{(i)}{]}^{(t+1)},[p_2^{(i)}{]}^{(t+1)},\cdots ,[p_{\mathcal{K}}^{(i)}{]}^{(t+1)}$
  因而最终求解隐变量$z^{(i)}$的后验概率分布结果$p_{z^{(i)}}^{(t+1)}$：
  $$p_{z^{(i)}}^{(t+1)}={\left([p_1^{(i)}{]}^{(t+1)},[p_2^{(i)}{]}^{(t+1)},\cdots ,[p_{\mathcal{K}}^{(i)}{]}^{(t+1)}\right)}^T$$

同理，可求出其他隐变量$z^{(1)},z^{(2)},\cdots ,z^{(N)}$的离散参数的迭代概率结果。

$$p_{z^{(1)}}^{(t+1)},p_{z^{(2)}}^{(t+1)},\cdots ,p_{z^{(N)}}^{(t+1)}$$

至此，高斯混合模型部分介绍结束。下一节将介绍隐马尔可夫模型
推导过程本身不是重点，只需要知道‘高斯混合模型’可以使用‘狭义EM’直接求解即可。高斯混合模型作为最经典的‘概率生成模型’，它的‘生成模型思想’需要留意。

相关参考：
机器学习-高斯混合模型（4）-EM求解-M-Step