05 非监督学习

$k$-means 算法

下面我们讨论聚类问题(clustering)的算法。给定$n$个$p$维空间上的样本点，如何把它们分为$k$类，使得距离相近的点尽量在同一类里？$k$-means算法是这样做的：首先我们随机$k$个坐标点$\mu_1,\cdots,\mu_k$，称为聚类中心(cluster centroids)。对于每个样本点$x_i$，我们找到距离$x_i$最近的那个聚类中心作为$x_i$的类别。具体地，取$c_i=\arg\min\limits_j \|x_i-\mu_j\|^2$。接着，我们调整聚类中心的位置，使每个中心的位置等于当前属于这一类的所有坐标点的均值。具体地，$\mu_j'=\dfrac{\sum_i (\mathbb{1}[c_i=j]\cdot x_i)}{\sum_i \mathbb{1}[c_i=j]}$。得到新的聚类中心之后，我们再次更新$c_i$，接着再次更新$\mu_j$，不断重复上述过程。我们期待聚类中心的坐标最终会渐渐收敛，这样就得到了聚类的结果。

$k$-means算法一定会收敛吗？大体上来说是肯定的。我们定义distortion function如下：$J(c,\mu)=\sum\limits_{i=1}^{n}\|x_i-\mu_{c_i}\|^2$，表示每个样本点与其对应的聚类中心的距离平方和。我们发现，随着算法的进行这个函数一定是单调递减的：当我们固定$\mu$重新分配$c_i$时，每个$x_i$都会选择使得$\|x_i-\mu_{c_i}\|$最小的$c_i$，因此$J$一定减小；当我们固定$c_i$重新计算$\mu$时，我们会把聚类中心移到每个类别的均值的位置，这对于每个类都一定会减小距离平方和。综上根据单调有界必收敛，$J(c,\mu)$最终一定会收敛到某个值。虽然在某些极端例子中，$J$收敛并不能保证$c$和$\mu$也收敛，但即便那样聚类中心的位置也可以被认为是基本没有变化了。所以$k$-means一般就可以被认为是收敛的。

我们注意到，$J$函数并不是凸函数，因此$k$-means得到的可能只是局部最优解，这取决于初始时随机的情况。所以实际应用时，我们一般会多执行几次这个算法，取最优的结果。

期望最大化算法(Expectation-Maximization algorithm, EM)

依然考虑聚类问题。类似高斯判别分析，我们建立这样的模型：假设样本点是根据$k$个不同的高斯分布生成的，模型有一个参数向量$\phi$，$\phi_j$表示生成第$j$类点的概率；有每个类别的期望和协方差矩阵$\mu_j,\Sigma_j$。我们希望找到这样的$\phi,\mu,\Sigma$，使得样本点这样的分布是参数$\phi,\mu,\Sigma$下概率最大的分布。具体地，我们的假设下的模型生成一列点$(u_1,\cdots,u_m)$的概率是$\prod\limits_{i=1}^{m}p(u_i\mid \phi,\mu,\Sigma)$。因此我们训练的目标就是最大化$\prod\limits_{i=1}^{n}p(x_i\mid \phi,\mu,\Sigma)$，取对数等价于最大化$\sum\limits_{i=1}^{n}\log p(x_i\mid \phi,\mu,\Sigma)$。其中，为了计算$p(x_i\mid \phi,\mu,\Sigma)$，必须用到全概率公式枚举所有可能的类别的概率$p(x_i\mid \phi,\mu,\Sigma)=\sum\limits_{z=1}^{k}p(x_i\mid z,\mu,\Sigma)p(z,\phi)$。

遗憾的是，尽管看上去和高斯判别分析很类似，以上目标函数梯度为零的方程却是没有封闭解的。原因在于，我们引入了隐变量$z$（latent variable）。如果我们能提前给出每个样本点应该属于哪一类，那么目标函数的求导就和高斯判别分析中一样了，也就有封闭解了。为此，我们每一次先猜测$z$，然后代入$z$优化得到$\phi,\mu,\Sigma$。接着再次猜测，再次优化，直到猜测收敛位置。这就是EM算法，猜测的过程称为E-step，优化的过程称为M-step。具体地，在E-step中我们不给出每个$z$的具体值而是计算分布：$w_j^{(i)}=p(z=j\mid x_i,\phi,\mu,\Sigma)$（这可以直接由多元高斯分布的density表达式计算得到）。在M-step中，仿照高斯判别分析的结果得到$\phi_j=\dfrac{1}{n}\sum\limits_{i=1}^{n}w_j^{(i)}$，$\mu_j=\dfrac{\sum\limits_{i} w_j^{(i)}x_i}{\sum\limits_{i} w_j^{(i)}}$，$\Sigma_j=\dfrac{\sum\limits_{i} w_j^{(i)}(x_i-\mu_j)(x_i-\mu_j)^\top}{\sum\limits_{i} w_j^{(i)}}$，也即新的类别分布取决于上一阶段每个点位于每种类别的概率之和，新的均值点和方差是上一阶段每个点在该类别上的概率加权平均。重复以上过程直到收敛以后，对于每个样本点输出概率最大的那个高斯分布即可。

主成分分析(Principle component analysis, PCA)

对于高维空间中的样本点（假设是$p$维的），它们可能在某些方向上有较大的方差，有些方向上则有较小的方差。如果我们选取若干个两两垂直的方差最大的方向（不妨设$k$维），把样本点投影到这$k$个方向向量上，我们就可以看作把样本点降到了$k$维。由于我们舍弃的是方差最小的方向，我们认为这样做损失的样本信息是较少的。这个降维方法就称为主成分分析。

假设我们有$n$个$p$维的样本点$x_i$，$k$个主方向$w_i$，那么降维的过程可以写作矩阵乘法：$\begin{bmatrix}x_1^\top\\\vdots\\x_n^\top\end{bmatrix}\begin{bmatrix}w_1&\cdots &w_k\end{bmatrix}=\begin{bmatrix}t_1^\top\\\vdots\\t_n^\top\end{bmatrix}$，其中$t_i=(\lang x_i,w_1\rang,\cdots,\lang x_i,w_k\rang)$。我们把上式简记为$XW=T$。

如何选取主方向呢？首先我们假设所有样本点的期望就落在原点，不然我们可以先做平移。为了选取方差最大的第一主方向$w_1$，我们就是要使得样本点在这个方向上投影的方差（平方和）最大，也即$\max \sum\limits_{i=1}^{n}\lang x_i,w_1\rang^2$，其中$\|w_1\|=1$。注意到，$\sum\limits_{i=1}^{n}\lang x_i,w_1\rang^2=\|Xw_1\|^2$，因此等价于最大化$(Xw_1)^2=w_1^\top X^\top Xw_1$，$\|w_1\|=1$。这等价于$\max\dfrac{w_1^\top X^\top Xw_1}{\|w_1\|^2}$。在组合数学中我们学过Rayleigh Quotient，这个最大值就是矩阵$X^\top X$的最大特征值$\lambda_1$，当$w_1$取$\lambda_1$对应的特征向量时取到。这样我们就找到了第一主方向。接下来要求第二主方向，我们首先所有样本点在$w_1$方向上的分量：$\hat x_i=x_i-(w_1^\top x_i)w_1$。这样所有样本点都与$w_1$垂直了，换言之样本点已经没有$w_1$方向上的维度了。我们再用同样的方法求新的矩阵$\hat X^\top \hat X$的最大特征值与特征向量，得到的方向一定是与$w_1$垂直的方向上样本点方差最大的方向， 这就是第二主方向。以此类推，一般地，求第$k$主方向的方法是：$\hat x_i=x_i-\sum\limits_{j=1}^{k-1}(w_j^\top x_i)w_j$，求$\max\dfrac{w_k^\top \hat X^\top \hat X w_k}{\|w_k\|^2}$。