【机器学习】GMM和EM算法

【机器学习】GMM和EM算法

机器学习算法-GMM和EM算法

⽬录1. GMM模型

聚类问题是⼀个经典的⽆监督任务，其⽬标是将 \(N\) 个 \(D\) 维数据 \(\{\bf{x}_i\}_{i=1}^N\) 分成\(K\)个簇，使得每个簇中的样本尽可能相似。GMM算法对数据

分布做了⼀些假设：

第\(k\)个簇数据点服从正态分布，即\(\mathbf{x}|\mathbf{z}\sim \mathcal{N}(\mu_k, \Sigma_k)\)

簇标签\(\mathbf{z}\sim \mathrm{Dir}(\alpha)\)

其中簇标签\(\mathbf{z}\)满⾜\(\mathbf{z}\in \{0, 1\}^K, \quad \sum_{k=1}^K z_k = 1,\quad p(z_k=1)=\alpha_k\)。根据条件概率和边缘分布可得：\[p(\mathbf{x}) = \sum_\mathbf{z} p(\mathbf{x}, \mathbf{z})=\sum_\mathbf{z} p(\mathbf{x}|\mathbf{z})p(\mathbf{z}) \]

代⼊相关的概率分布得到：\[p(\mathbf{x})=\sum_{k=1}^K \alpha_k \mathcal{N}(\mathbf{x}|\mu_k, \Sigma_k) \]

需要求解的模型参数为\(\{\alpha_k, \mu_k, \sigma_k^2\}_{k=1}^K\)共计\(K\times(1+D+D^2)\)个参数。2. GMM模型参数求解

为了估计GMM分布中的参数，采⽤MLE或者MAP即可实现。以MLE为例，⽬标函数为：

\[f(\alpha, \mu, \Sigma)=\log p(\mathbf{x}) = \log \prod_{n=1}^N \sum_{k=1}^K \alpha_k \mathcal{N}(x_n|\mu_k, \Sigma_k) \]

2.1 参数\(\alpha\)的求解

参数\(\alpha\)需要满⾜\(\sum_k \alpha_k=1\)的条件，拉格朗⽇函数为：

\[\mathcal{L} = \sum_{n=1}^N\log \sum_{k=1}^K \alpha_k \mathcal{N}\mathbf{x}_n|\mu_k, \Sigma_k) + \lambda(\sum_{k=1}^K\alpha_k - 1) \\

\nabla_{\alpha_k}\mathcal{L} = \sum_{n=1}^N \frac{1}{\sum_{j=1}^K \alpha_j \mathcal{N}(\mathbf{x}_n|\mu_j, \Sigma_j)} \mathcal{N}(\mathbf{x}_n|\mu_k,

\Sigma_k)+\lambda = 0 \]

对梯度等式两边同乘上\(\alpha_k\)并对k求和得到\(\lambda = -\frac{1}{N}\)。定义模型对数据\(\mathbf{x}_n\)的响应\(\gamma_{nk}\)为：\[\gamma_{nk} = \frac{\alpha_k \mathcal{N}(\mathbf{x}_n|\mu_k, \Sigma_k)}{\sum_{j=1}^K \alpha_j \mathcal{N}(\mathbf{x}_n|\mu_j, \Sigma_j)} \]

得到参数\(\alpha\)的估计为：\[\alpha_k = \frac{1}{N}\sum_{n=1}^N \gamma_{nk} \triangleq \frac{N_k}{N} \]

2.2 参数\(\mu\)和\(\Sigma\)的求解

参数\(\mu\)和\(\Sigma\)没有任何限制，对似然函数直接求导即可得到：

\[\nabla_{\mu_k} f = \sum_{n=1}^N \frac{\alpha_k}{\sum_{j=1}^K \alpha_j \mathcal{N}(\mathbf{x}_n|\mu_j, \Sigma_j)} \frac{\partial \mathcal{N}

(\mathbf{x}_n|\mu_k, \Sigma_k)}{\partial \mu_k}\\ \nabla_{\Sigma_k} f = \sum_{n=1}^N \frac{\alpha_k}{\sum_{j=1}^K \alpha_j \mathcal{N}

(\mathbf{x}_n|\mu_j, \Sigma_j)} \frac{\partial \mathcal{N}(\mathbf{x}_n|\mu_k, \Sigma_k)}{\partial \Sigma_k} \]

代⼊正态分布的表达式\(\mathcal{N}(\mathbf{x}|\mu_k, \Sigma_k) = \frac{1}{(2\pi)^{\frac{D}{2}}|\Sigma|^{\frac{1}{2}}}\exp\{-\frac{1}{2}(\mathbf{x}-\mu_k)^T\Sigma_k^{-1}(\mathbf{x}-\mu_k)\}\)得到：

\[\begin{align} \frac{\partial \mathcal{N}(\mathbf{x}|\mu_k, \Sigma_k^2)}{\partial \mu_k} &= \frac{1}{(2\pi)^{\frac{D}{2}}|\Sigma|^{\frac{1}{2}}}\exp\{-\frac{1}

{2}(\mathbf{x}-\mu_k)^T\Sigma_K^{-1}(\mathbf{x}-\mu_k)\} \times (-\frac{1}{2}\times 2 \times \Sigma_k^{-1}(\mathbf{x}-\mu_k)) \\ &= -\mathcal{N}

(\mathbf{x}|\mu_k, \Sigma_k)\Sigma_k^{-1}(\mathbf{x}-\mu_k) \end{align} \]

\[\begin{align} \frac{\partial \mathcal{N}(\mathbf{x}_n|\mu_k, \Sigma_k^2)}{\partial \Lambda_k} =& \frac{1}{\left(2\pi\right)^{\frac{D}{2}}}(\frac{1}

{2}|\Lambda_k|^{-\frac{1}{2}})\exp\{-\frac{1}{2}(\mathbf{x}-\mu_k)^T\Lambda_k(\mathbf{x}-\mu_k)\}\frac{\partial |\Lambda_k|}{\partial\Lambda_k} \\ &+

\frac{|\Lambda|^{\frac{1}{2}}}{(2\pi)^{\frac{D}{2}}}\exp\{-\frac{1}{2}(\mathbf{x}-\mu_k)^T\Lambda_k(\mathbf{x}-\mu_k)\}\Big(-\frac{1}{2}\Big)\frac{\partial}

{\partial \Lambda_k}\Big((\mathbf{x}-\mu_k)^T\Lambda_k(\mathbf{x}-\mu_k)\Big) \\ \end{align} \]

根据矩阵⾏列式的拉普拉斯展开\(|A| = \sum_{j=1}^M a_{ij}M_{ij}\)和逆矩阵计算公式\(A^{-1} = \frac{1}{|A|}A^*\)得到：\[\frac{\partial |A|}{\partial a_{ij}} = M_{ij} \Longrightarrow \frac{\partial |A|}{\partial A} = (A^*)^T \]

将上式和\(\frac{\partial \mathbf{x}^T A \mathbf{x}}{\partial A} = \mathbf{x}\mathbf{x}^T\)带⼊到梯度表达式得到：\[\begin{align} \frac{\partial \mathcal{N}(\mathbf{x}_n|\mu_k, \Sigma_k^2)}{\partial \Lambda_k} =& \frac{1}{2}\frac{|\Lambda_k|^{\frac{1}{2}}}

{\left(2\pi\right)^{\frac{D}{2}}}\exp\{-\frac{1}{2}(\mathbf{x}-\mu_k)^T\Lambda_k(\mathbf{x}-\mu_k)\}\Lambda_k^{-1} \\ &-\frac{1}{2} \frac{|\Lambda|^{\frac{1}

{2}}}{(2\pi)^{\frac{D}{2}}}\exp\{-\frac{1}{2}(\mathbf{x}-\mu_k)^T\Lambda_k(\mathbf{x}-\mu_k)\}(\mathbf{x}-\mu_k)(\mathbf{x}-\mu_k)^T \\ =& \frac{1}

{2}\mathcal{N}(\mathbf{x}|\mu_k, \Sigma_k)\{\Sigma_k - (\mathbf{x}-\mu_k)(\mathbf{x}-\mu_k)^T\} \end{align} \]

将上述求导结果代⼊到似然函数的梯度中得到：\[\mu_k = \frac{1}{N_k}\sum_{n=1}^N \gamma_{nk}\mathbf{x}_n\\ \Sigma_k = \frac{1}{N_k}\sum_{n=1}^N \gamma_{nk}(\mathbf{x}-\mu_k)(\mathbf{x}-

\mu_k)^T \]

3. GMM算法的实现

根据模型参数求解的结果可知，在更新参数时需要知道\(\gamma_{nk}\)，⽽计算\(\gamma_{nk}\)⼜需要知道模型参数，陷⼊到了⼀个循环中。GMM采⽤了EM

算法更新这两部分参数：E-step：固定模型，计算\(\gamma_{nk}\)

M-step：运⽤极⼤似然估计更新模型参数

重复迭代E-step和M-step直到模型收敛。3.1 gmm类的定义和实现

gmm类需要记录数据的维度和簇的数⽬，为了后续的⽅便，将样本数量也作为初始化参数记录；然后⽣成了三个模型参数，为了简化将协⽅差矩阵限定为对⾓

矩阵。⽅法包含了两个主要⽅法和三个辅助函数：train：训练函数，根据数据集计算出模型参数

step：单步的训练，包含了E-step和M-step

_prob：多元⾼斯密度计算

_log_likelihood：计算当前模型下的对数似然

cluster：预测函数，将数据集进⾏聚类

class gmm():

def __init__(self, dims, K, N):

self.dims = dims