无监督学习-3-维度规约

维度规约

维度规约，又叫降维，用于提取数据特征，将高维数据转换为低维数据。一方面方便对数据进行可视化和分析；另一方面对数据进行预处理可以加速后续训练，并且减少噪声，使得所训练模型更加简单。如果说密度估计和降维是在数据集样本轴上进行压缩，那么降维就是在数据集特征轴上进行压缩。

降维和聚类可以同时使用，且应该先降维后聚类，因为当数据维度 很大时，所有点之间的近乎是等距的，即

$$\frac{\max||X_i-X_j||}{\min||X_i-X_j||}=1+\mathcal{O}\left(\sqrt{\frac{\log n}{d}}\right)$$

直觉（Intuition）

降维任务的目标即要构造映射 ，其中 。但是在映射过程中，不可避免的会损失信息，直觉上容易想到，降维算法的目标即最小化降维过程中的信息损失。

有三种常见的指标用于衡量这种信息损失，他们各自可以推导出不同的目标函数：

最大惯性 (Large Inertia)

最大惯性方法认为降维后的数据之间距离应该最大化，即

$$\max_{\Phi}\frac{1}{n^2}\sum_{i,j}||\Phi(X_i)-\Phi(X_j)||^2$$

事实上该目标等价于

$$\max_{\Phi}\frac{1}{n}\sum_{i}||\Phi(X_i)-\bar{\Phi}||^2$$

其中

$$\bar{\Phi} = \frac{1}{n}\sum_{i}\Phi(X_i)$$

以下给出证明：

$$\begin{split} & \max_{\Phi}\frac{1}{n^2}\sum_{i,j}||\Phi(X_i)-\Phi(X_j)||^2 \\ = & \max_{\Phi}\frac{1}{n^2}\sum_{i,j}||\Phi(X_i)-\bar{\Phi}+\bar{\Phi}-\Phi(X_j)||^2 \\ = & \max_{\Phi}\frac{1}{n^2}\sum_{i,j}\left(||\Phi(X_i)-\bar{\Phi}||^2+||\bar{\Phi}-\Phi(X_j)||^2 + 2\left(\Phi(X_i)-\bar{\Phi}\right)^T\left(\Phi(X_j)-\bar{\Phi}\right)\right) \\ = & \max_{\Phi}\left(\frac{2}{n}\sum_{i}||\Phi(X_i)-\bar{\Phi}||^2+ \frac{2}{n^2}\left(\sum_{i}\Phi(X_i)-n\bar{\Phi}\right)^T\left(\sum_{j}\Phi(X_j)-n\bar{\Phi}\right)\right) \\ = & \max_{\Phi}\frac{2}{n}\sum_{i}||\Phi(X_i)-\bar{\Phi}||^2 \\ = & \max_{\Phi}\frac{1}{n}\sum_{i}||\Phi(X_i)-\bar{\Phi}||^2 \\ \end{split}$$

证毕。

此外，值得注意的是，在一维情况下，最大化的惯性实质上就是方差。

最小重建误差 (Small reconstruct error)

考虑另一个映射 用于从降维数据中重建原始数据，我们希望最小化重建误差

$$\min_\Phi \frac{1}{n}\sum_i||X_i-\widetilde\Phi(\Phi(X_i))||^2$$

保持原关系 (Relation Preservation)

考虑某种向量间的关系 ，我们希望最小化在原数据集上的距离关系和在降维后的数据集上的距离关系的差异，即降维前后数据之间距离的大小关系应该保持一致：

$$\min_\Phi \frac{1}{n^2}\sum_{i,j}||\Psi(X_i,X_j)-\Psi(\Phi(X_i),\Phi(X_j))||^2$$

主成分分析 (Principal Component Analysis, PCA)

在本节中，我们会先从最大惯性的角度进行求取最大主成分的推导；然后我们会证明 PCA 同样也是一种最小重建损失算法，并给出 PCA 的完整形式；最后我们会从多维标度 (Multidimensional scaling, MDS) 的角度证明 PCA 同样是一种保持原关系的算法，并在此基础上推导出非线性 PCA 。

最大惯性

正如前文所述，我们的目标是要找到这样一个映射函数 ，其中 ， 同时最大化惯性项

$$\max_{\Phi}\frac{1}{n}\sum_{i}||\Phi(X_i)-\bar{\Phi}||^2$$

一个简单的想法是使用线性映射

$$\Phi(X) = V^TX$$

其中 ，为了解的唯一性，限制 。这样我们就得到了 PCA 的基础形式，接下来只需要求解优化目标即可。

不失一般性，我们先令 ，则有 。优化目标可改写为

$$\begin{split} \max_{\Phi}\frac{1}{n}\sum_{i}||\Phi(X_i)-\bar{\Phi}||^2 & = \max_{v_1^T}\frac{1}{n}\sum_{i}||v_1^TX_i-\frac{1}{n}\sum_{j}v_1^TX_j||^2 \\ & = \max_{v_1^T}\frac{1}{n}\sum_{i}||v_1^TX_i-v_1^T\bar{X}_n||^2 \\ & = \max_{v_1^T}\frac{1}{n}\sum_{i}\left(v_1^T(X_i-\bar{X}_n)^T(X_i-\bar{X}_n)v_1\right) \\ & = \max_{v_1^T}\left(v_1^T\left(\frac{1}{n}\sum_{i}(X_i-\bar{X}_n)^T(X_i-\bar{X}_n)\right)v_1\right) \\ & = \max_{v_1^T}\left(v_1^T\hat{\Sigma}_nv_1\right) \\ \texttt{s.t.} & \quad ||v_1^T||=1 \end{split}$$

其中 为原数据的均值， 为原数据集的协方差矩阵。另外观察上式第二步不难发现，优化目标实质上是最大化降维后数据的方差，这在上一节介绍最大惯性的定义时也已提及。

使用拉格朗日乘子法求解

$$\arg\max_{v_1^T}\left(v_1^T\hat{\Sigma}_nv_1\right) \quad\texttt{s.t.} \quad ||v_1^T||^2=1$$

即

$$\arg\max_{v_1^T,\lambda_1}L(v_1^T,\lambda_1) = \arg\max_{v_1^T,\lambda_1}\left(v_1^T\hat{\Sigma}_nv_1 + \lambda_1 (v_1^Tv_1-1) \right)$$

代入求导求解可得

$$\hat{\Sigma}_nv_1 = \lambda_1v_1$$

因此 是协方差矩阵 关于特征值 的特征向量。代回原始问题，有

$$v_1^T\hat{\Sigma}_nv_1 = v_1^T\lambda_1v_1 = \lambda_1$$

要使 最大，则 只能是协方差矩阵 的最大特征值，而 则为最大特征值所对应的特征向量。

从而我们得到了一维情形下的 PCA 的解，类似地，我们可以推广到 维情形下，有

$$V_k^T\hat{\Sigma}_nV_k = \texttt{diag}(\lambda_1,\lambda_2,\cdots,\lambda_k)$$

可得 为协方差矩阵 前 大特征值对应的特征向量组成的矩阵。

最小重建误差

考虑协方差矩阵的特征值分解

$$\hat{\Sigma}_n = V\texttt{diag}(\lambda_1,\lambda_2,\cdots,\lambda_d)V^T$$

其中 ，且 是一组标准正交基，。

我们首先给出完整的 PCA 算法如下

• INPUT: 数据集 , 保留成分数
• 计算样本均值和协方差矩阵
• 对 做特征值分解
• 记录前 大特征值 对应的特征向量
• 进行映射 $$\Phi(X_i) = \left(\begin{matrix} v_1^T(X_i-\bar{X}_n) \\ v_2^T(X_i-\bar{X}_n) \\ \cdots \\ v_k^T(X_i-\bar{X}_n) \end{matrix}\right) = V_k^T(X_i-\bar{X}_n)$$

我们首先证明 PCA 算法最小化了重建误差，考虑

$$\begin{split} \widetilde\Phi(\Phi(X_i)) &=V_kV_k^T(X_i-\bar{X}_n) + \bar{X}_n \end{split}$$

有重建误差

$$\begin{split} & \min_\Phi \frac{1}{n}\sum_i||X_i-\widetilde\Phi(\Phi(X_i))||^2 \\ =& \min_\Phi \frac{1}{n}\sum_i||X_i-V_kV_k^T(X_i-\bar{X}_n) -\bar{X}_n||^2 \\ =& \min_\Phi \frac{1}{n}\sum_i \left(||X_i-\bar{X}_n||^2+||V_kV_k^T(X_i-\bar{X}_n)||^2-2(X_i-\bar{X}_n)^T(V_kV_k^T(X_i-\bar{X}_n))\right) \\ =& \min_\Phi \frac{1}{n}\sum_i \left(||X_i-\bar{X}_n||^2+||V_kV_k^T(X_i-\bar{X}_n)||^2-2||V_kV_k^T(X_i-\bar{X}_n)||^2\right)\\ =& \min_\Phi \frac{1}{n}\sum_i \left(||X_i-\bar{X}_n||^2-||V_kV_k^T(X_i-\bar{X}_n)||^2\right) \\ =& \min_\Phi \sum_i\left(-||V_kV_k^T(X_i-\bar{X}_n)||^2\right) \\ =& \max_\Phi \sum_i||V_kV_k^T(X_i-\bar{X}_n)||^2 \\ =& \max_\Phi \sum_i(X_i-\bar{X}_n)^TV_kV_k^TV_kV_k^T(X_i-\bar{X}_n) \\ =& \max_\Phi \sum_i(X_i-\bar{X}_n)^TV_kV_k^T(X_i-\bar{X}_n) \\ =& \max_\Phi \sum_i||V_k^T(X_i-\bar{X}_n)||^2 \\ \end{split}$$

因此最小化重建误差等价于最大化惯性。因为在上一节中我们从最大惯性推出了 PCA 算法，从而我们可以证明 PCA 同样也是一种最小重建误差算法。

根据 定理，我们同样可以证明

$$\hat{\Sigma}_n^{(k)} = V\texttt{diag}(\lambda_1,\lambda_2,\cdots,\lambda_k)V^T$$

是 的一个低秩近似，即

$$\hat{\Sigma}_n^{(k)} = \arg\min_{S^{(k)}} ||\hat{\Sigma}_n-S^{(k)}||$$

保持原关系

考虑 Relation Preservation 的定义，有

$$\min_\Phi \frac{1}{n^2}\sum_{i,j}||\Psi(X_i,X_j)-\Psi(\Phi(X_i),\Phi(X_j))||^2$$

从 MDS (Multidimensional scaling) 的角度看，选择 为线性映射，选择 为向量点积分，我们同样可以推导出 PCA 算法，即

$$\begin{split} & \min_\Phi \frac{1}{n^2}\sum_{i,j}||\Psi(X_i,X_j)-\Psi(\Phi(X_i),\Phi(X_j))||^2 \\ = & \min_\Phi \frac{1}{n^2}\sum_{i,j}||(X_i-\bar{X}_n)^T(X_j-\bar{X}_n)-(X_i-\bar{X}_n)^TV_kV_k^T(X_j-\bar{X}_n)||^2 \\ = & \min_\Phi \frac{1}{n^2}\sum_{i,j}||(X_i-\bar{X}_n)^T(I_d-V_kV_k^T)(X_j-\bar{X}_n)||^2 \\ = & \max_\Phi \frac{1}{n^2}\sum_{i,j}||(X_i-\bar{X}_n)^T(V_kV_k^T)(X_j-\bar{X}_n)||^2 \end{split}$$

上述项即最大惯性，由此我们得到了和 PCA 一样的解。

在更广义的情形下，因为 MDS 只考虑点积，改写 为任意核函数，实质上可以通过核函数得到非线性的解。因此 MDS 又可以推导出 nonlinear PCA （即核 PCA）。

此外，从 MDS 的视角重新审视 PCA 。

考虑 为数据的协方差矩阵

$$S_{i,j} = (X_i-\bar{X}_n)^T(X_j-\bar{X}_n)$$

即 为向量之间的几何距离

$$D_{i,j}^2 = ||X_i-X_j||^2$$

有

$$-2HD^2H=S$$

其中

可以看出，MDS 从样本距离矩阵 可推导得到 PCA （以及核 PCA ），而传统 PCA 算法从协方差矩阵 出发推导得到，这两种方法在结果上是等价的。事实上，尽管结果是等价的，但是 MDS 方法在计算时输入往往是 而非 。