Kmeans

kmeans是一种相当简单和直观的聚类算法，主要分类两步：

1. 对于每个点，选择离他最近的聚类中心作为他的类别：

   $c^{(i)} :=\arg \min _{j}\left\|x^{(i)}-\mu_{j}\right\|^{2}$

2. 对于每个类别，求解聚类这个类的聚类中心： $\mu_{j}:=\frac{\sum_{i=1}^{m} 1{c^{(i)}=j} x^{(i)}}{\sum_{i=1}^{m} 1{c^{(i)}=j}}$

虽然算法很简单，但是我们还是需要回答一个很基本的问题，这个算法会收敛吗？

我们定义一个distortion function：$J(c, \mu)=\sum_{i=1}^{m}\left\|x^{(i)}-\mu_{c^{(i)}}\right\|^{2}$

这个函数衡量了点到对应的聚类中心的距离平方和，实际上，我们的kmeans算法能使得distortion function不断减小，具体来说：

1. 第一步是在$\mu$固定的情况下，我们通过$c$不断减小$J$
2. 第二步是在$c$固定的情况下，我们通过$\mu$不断减小$J$

因此，$J$一定是单调递减的，因此也保证了算法的收敛性。

但在实际应用中，kmeans算法并不能保证全局最优解，同时可能存在着震荡，这是因为我们的优化目标$J$不是一个凸函数。而kmeans算法的每一步都是在寻找局部最优解（local optima），因此，最好的办法是多次重复该算法，并选择最小的$J$。

GMM

Model

假设我们有一系列训练集$\{x^{(1)}, \ldots, x^{(m)}\}$，我们需要使用非监督学习的方法进行训练。

我们将这些数据建模成联合分布的形式：$p\left(x^{(i)}, z^{(i)}\right)= p\left(x^{(i)} | z^{(i)}\right) p\left(z^{(i)}\right)$。

• 在这里， $z^{(i)} \sim$ Multinomial $(\phi)$ (where $\phi_{j} \geq 0, \sum_{j=1}^{k} \phi_{j}=1$），也就是我们的隐变量
• 在给定$z$的条件下，假设$x^{(i)} | z^{(i)}=j \sim \mathcal{N}\left(\mu_{j}, \Sigma_{j}\right)$

因此，我们首先需要通过随机变量$z$产生一个$z^{(i)}$，然后再从对应的高斯分布中产生$x$，这种模型被称为高斯混合模型。

不难得到，对于这个模型来说，我们的参数为$\phi, \mu$ and $\Sigma$。写成似然函数的形式：

$\begin{aligned} \ell(\phi, \mu, \Sigma) &=\sum_{i=1}^{m} \log p\left(x^{(i)} ; \phi, \mu, \Sigma\right) \\ &=\sum_{i=1}^{m} \log \sum_{z^{(i)}=1}^{k} p\left(x^{(i)} | z^{(i)} ; \mu, \Sigma\right) p\left(z^{(i)} ; \phi\right) \end{aligned}$

但很遗憾的是，如果我们直接对这个似然函数求导，无法得到一个cloed form。

If $z$ is observed

但如果我们的隐变量$z$是已知的呢，我们是不是就很容易求解了呢？（这里与GDA算法相同，使用MLE求解）

我们重写似然函数为：

$\ell(\phi, \mu, \Sigma)=\sum_{i=1}^{m} \log p\left(x^{(i)} | z^{(i)} ; \mu, \Sigma\right)+\log p\left(z^{(i)} ; \phi\right)$

带入假设的分布，不难求得： $\phi_{j}=\frac{1}{m} \sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\}$

$\mu_{j}=\frac{\sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\} x^{(i)}}{\sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\}}$

$\Sigma_{j}=\frac{\sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\}\left(x^{(i)}-\mu_{j}\right)\left(x^{(i)}-\mu_{j}\right)^{T}}{\sum_{i=1}^{m} 1\left\{z^{(i)}=j\right\}}$

因此，如果我们已知$z$，那么MLE后的结果和之前的高斯判别模型完全一致了。

但实际上，$z$是未知的，那么怎么办呢？

EM algorithm

我们使用EM思想来处理。EM是一种迭代的算法，主要有两个步骤：

1. E步：通过期望去guss$z$的最可能的值 $w_{j}^{(i)} :=p\left(z^{(i)}=j | x^{(i)} ; \phi, \mu, \Sigma\right)$
   • 实际上我们是通过后验概率来进行估计：

$p\left(z^{(i)}=j | x^{(i)} ; \phi, \mu, \Sigma\right)=\frac{p\left(x^{(i)} | z^{(i)}=j ; \mu, \Sigma\right) p\left(z^{(i)}=j ; \phi\right)}{\sum_{l=1}^{k} p\left(x^{(i)} | z^{(i)}=l ; \mu, \Sigma\right) p\left(z^{(i)}=l ; \phi\right)}$

• 在这里，我们分子上的概率都可以直接得到，因此可以得到$x^{(i)} = j$的概率，也就是soft assignments $w^{(i)}_j$
  1. M步：通过已知的$z$来对模型参数进行估计（与上面一样）

$\phi_{j} :=\frac{1}{m} \sum_{i=1}^{m} w_{j}^{(i)}$

$\mu_{j} :=\frac{\sum_{i=1}^{m} w_{j}^{(i)} x^{(i)}}{\sum_{i=1}^{m} w_{j}^{(i)}}$

$\Sigma_{j} :=\frac{\sum_{i=1}^{m} w_{j}^{(i)}\left(x^{(i)}-\mu_{j}\right)\left(x^{(i)}-\mu_{j}\right)^{T}}{\sum_{i=1}^{m} w_{j}^{(i)}}$

我们会发现，EM算法和kmeans有着很微妙的关系，除了在E步时，kmeans使用了hard cluster assignments而不是soft assignments，也就是对每个点分配了一个类别而不是概率，其他的都完全一样。

因此，EM也是一种local optima的算法，因此随机初始化参数可能会得到不同的结果。

但对于EM而言，还有两个问题没有解决：

1. E步时，如何来估计隐变量是一种较好的选择？
2. 如何保证算法的收敛性？

这些内容在下一篇博客会详细介绍。