软聚类与硬聚类
硬分类：以kmean为代表，每个数据点只被赋给一个簇，即便该数据点离簇的中心点很远 软分类：会对每个点属于哪个簇赋予一个概率（breaks the data across clusters intelligently）
如果使用加权算法，可以把硬聚类的kmean变成软聚类
输入：数据点\(x_1, \ldots, x_n\)，每个\(x \in \mathbb{R}^d\) 目标：以\(\phi_i\)和\(\mu_k\)为变量，最小化\(\mathcal{L} = \sum_{i=1}^n\sum_{k=1}^K\phi_i(k)\frac{||x_i - \mu_k||^2}{\beta}\) 条件：\(\phi_i(k)>0, \sum_{i=1}^K \phi_i(k) = 1, \beta>0\) 迭代执行以下两步直至算法终止 1. 更新\(\phi\)：对每个\(i\)，更新其所属簇的权重 \[ \phi_i(k) = \frac{\exp\{-\frac{1}{\beta}||x_i - \mu_k||^2\}}{\sum_j \exp\{-\frac{1}{\beta}||x_i - \mu_j||^2\}},\ {\rm for\ }k=1,\ldots,K \] 2. 更新\(\mu\)：对每个\(k\)，使用加权均值更新\(\mu_k\) \[ \mu_k = \frac{\sum_i x_i\phi_i(k)}{\sum_i \phi_i(k)} \]
混合模型
在之前的加权kmeans算法中，权重向量\(\phi_i\)可以看作是\(x_i\)赋给每个簇的概率。实际上，混合模型是一种概率模型，其中\(\phi_i\)是根据模型得出的概率分布。它定义了
- 每个簇 (cluster) \(c_i\)的先验分布
- 给定簇\(c_i\)时，数据\(x_i\)的似然分布
可以把这两个概念和Bayes分类器中的类别先验和类条件似然相对比。不过贝叶斯分类器是有监督学习，类（class）是给定的，而混合模型是无监督学习，簇（cluster）是自己推出的
混合模型是一种生成模型（定义了数据上的概率分布），可以看做是简单分布的加权组合，权重由离散概率分布定义。注意简单分布必须来自于同一个分布族
混合模型 数据：\(x_1,\ldots, x_n\)，其中每个\(x_i \in \mathcal{X}\) 模型参数：\(K\)维空间上的分布\(\pi\)和参数\(\theta_1, \ldots, \theta_K\) 生成过程： 1. 生成簇：\(c_i \mathop{\sim}^{iid} {\rm Discrete}(\pi) \Rightarrow {\rm Prob}(c_i = k|\pi) = \pi_k\) 2. 生成数据：\(x_i \sim p(x|\theta_{c_i})\)
每个\(x_i\)在初始时会依离散分布\(\pi\)分给某个簇\(c_i\)。注意簇的参数\(\theta\)随其所依赖的分布不同而不同。若我们假设数据是由正态分布生成，则\(\theta\)就是\(\mu\)和\(\Sigma\)。如果两个数据划给同一个簇，则意味着我们假设这两个数据由同一个分布生成。分布实际定义了数据可能出现的区域，权重定义了区域内数据的密度
高斯混合模型
这里假设\(\pi\)是\(K\)维的概率分布（感觉是离散随机变量\(\pi\)有\(K\)个可能值），对第\(k\)个\(\mathbb{R}^d\)上的正态分布，其期望和方差为\((\mu_k, \Sigma_k)\)。定义\(\boldsymbol{\mu} = \{\mu_1, \ldots, \mu_K\}\)，\(\boldsymbol{\Sigma} = \{\Sigma_1, \ldots, \Sigma_k\}\)，我们的目的是从给定的数据学习\(\pi, \boldsymbol{\mu},\boldsymbol{\Sigma}\)。其中，给定的数据假设以\({\rm Discrete}(\pi)\)的分布分配给簇\(c_i\)，\(c_i\)中的数据\(x_i \sim N(\mu_{c_i}, \Sigma_{c_i})\)
解决方法还是求最大似然，具体使用的是EM算法，其中簇\(c_i\)是隐变量（辅助变量） \[ p(x_1, \ldots, x_n|\pi, \boldsymbol{\mu}, \boldsymbol{\Sigma}) = \prod_{i=1}^n p(x_i|\pi, \boldsymbol{\mu}, \boldsymbol{\Sigma}) = \prod_{i=1}^n \sum_{k=1}^K p(x_i,c_i = k | \pi, \boldsymbol{\mu}, \boldsymbol{\Sigma}) \] 由于\(c_i\)是离散变量，因此将其求和相当于对其积分，也可以消掉辅助变量。这里不通过坐标下降计算\(\prod_{i=1}^n p(x_i, c_i|\pi, \boldsymbol{\mu}, \boldsymbol{\Sigma})\)的原因是求解结果最终会把每个数据点指定给一个簇，从而把问题转变成了硬聚类问题。因此，通过把\(c_i\)看作是辅助变量，我们使用EM算法是通过\(\sum_{i=1}^n \ln p(x_i, c_i|\pi, \boldsymbol{\mu}, \boldsymbol{\Sigma})\)来最大化\(\sum_{i=1}^n \ln p(x_i|\pi, \boldsymbol{\mu}, \boldsymbol{\Sigma})\)
套用公式 \[ \ln p(x|\theta_1) = \int q(\theta_2)\ln\frac{p(x,\theta_2|\theta_1)}{q(\theta_2)}d\theta_2 + \int q(\theta_2) \ln \frac{q(\theta_2)}{p(\theta_2|x,\theta_1)}d\theta_2 \] 可知高斯混合模型的EM目标函数是 \[ \sum_{i=1}^n \ln p(x_i|\pi, \boldsymbol{\mu}, \boldsymbol{\Sigma}) = \sum_{i=1}^n\sum_{k=1}^K q(c_i = k) \ln \frac{p(x_i, c_i = k|\pi, \boldsymbol{\mu}, \boldsymbol{\Sigma})}{q(c_i = k)} + \sum_{i=1}^n\sum_{k=1}^K q(c_i = k)\ln\frac{q(c_i = k)}{p(c_i|x_i, \pi, \boldsymbol{\mu}, \boldsymbol{\Sigma})} \] 在EM算法的一次迭代中，首先要把\(q(c_i = k)\)置为\(p(c_i = k|x_i ,\pi, \boldsymbol{\mu}, \boldsymbol{\Sigma})\)。由贝叶斯定律\(P(A|B) \propto P(A)P(B|A)\)，有 \[ \begin{align*} p(c_i = k|x_i, \pi, \boldsymbol{\mu}, \boldsymbol{\Sigma}) & \propto p(c_i = k | \pi, \boldsymbol{\mu}, \boldsymbol{\Sigma}) p(x_i|c_i=k, \pi, \boldsymbol{\mu}, \boldsymbol{\Sigma})\\ &= p(c_i = k|\pi)p(x_i|c_i = k, \boldsymbol{\mu}, \boldsymbol{\Sigma}) \end{align*} \] 可以解得给定\(\pi, \boldsymbol{\mu}, \boldsymbol{\Sigma}\)时\(c_i\)的后验分布 \[ q(c_i = k) = \frac{\pi_k N(x_i|\mu_k, \Sigma_k)}{\sum_j \pi_j N(x_i|\mu_j, \Sigma_j)} \] 记上式为\(\phi_i(k)\)，则EM算法的E-step和M-step分别为
- E-step：使用更新的\(q\)求\(Q\)的期望，其中 \[ Q= \sum_{i=1}^n\sum_{k=1}^K \phi_i (k) \ln p(x_i,c_i=k|\pi, \mu_k, \Sigma_k) + C \]
- M-step：对\(\pi\)和各自的\(\mu_k,\Sigma_k\)求\(Q\)的最大值 由于\(p(x_i,c_i = k|\pi, \mu_k, \Sigma_k) = \pi_kN(x_i|\mu_k, \Sigma_k)\)，因此\(Q=\sum_{i=1}^n \sum_{k=1}^K \phi_i(k) \{\ln \pi_k + \ln N(x_i|\mu_k, \Sigma_k)\}\)
具体的过程如下
- E-step：对\(i=1,\ldots,n\)，令 \[ \phi_i(k) = \frac{\pi_k N(x_i|\mu_k, \Sigma_k)}{\sum_j \pi_j N(x_i|\mu_j, \Sigma_j)},\ {\rm for\ }k=1,\ldots,K \]
- M-step：对\(k=1,\ldots,K\)，定义\(n_k = \sum_{i=1}^n \phi_i(k)\)，更新 \[ \begin{align*} \pi_k &= \frac{n_k}{n} \\ \mu_k &= \frac{1}{n_k}\sum_{i=1}^n \phi_i (k)x_i \\ \Sigma_k &= \frac{1}{n_k}\sum_{i=1}^n \phi_i(k)(x_i - \mu_k)(x_i - \mu_k)^T \end{align*} \]
GMM理论上可以学到任意数量的分类，因此会过拟合。解决方法是假设\(\pi\)满足Dirichlet分布
广义混合模型的求解
输入：\(x_1,\ldots, x_n\)，其中\(x\in \mathcal{X}\) 目标：最大化\(\mathcal{L} = \sum_{i=1}^n \ln p(x_i|\pi, \boldsymbol{\theta})\)，其中\(p(x|\theta_k)\)是问题相关的 步骤：迭代EM两步直到\(\mathcal{L}\)足够小
- E-step：对\(i=1,\ldots, n\)，令 \[ \phi_i(k) = \frac{\pi_k p(x_i|\theta_k)}{\sum_j \pi_j p(x_i|\theta_j)},\ {\rm for\ }k=1,\ldots,K \]
- M-step：对\(k=1,\ldots, K\)，定义\(n_k = \sum_{i=1}^n \phi_i(k)\)，令 \[ \pi_k = \frac{n_k}{n}, \theta_k = {\rm arg}\max_\theta \sum_{i=1}^n \phi_i(k)\ln p(x_i|\theta) \]
