降维与度量学习

k 近邻学习

\(k\) 近邻（\(k\)-Nearest Neighbor，简称 kNN）学习是一种常用的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最相近的 \(k\) 个训练样本，然后基于这 \(k\) 个“邻居”的信息来进行预测：

• 在分类任务中可使用投票法，即选择这 \(k\) 个样本中出现最多的类别标记作为预测结果；
• 在回归任务中可使用平均法，即将这 \(k\) 个样本的实值输出标记的平均值作为预测结果；
• 还可基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。

\(k\) 近邻学习没有显示的训练过程，是懒惰学习（lazy learning）的代表，这类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理；相应的，那些在训练阶段就对样本进行学习处理的方法，称为急切学习（eager learning）。

暂且假定距离计算是“恰当”的，即能够恰当地找出 \(k\) 个近邻，我们来对最近邻分类器（1NN，即 \(k = 1\)）在二分类问题上的性能做一个简单的讨论。

给定测试样本 \(\bm{x}\)，若其最近邻样本为 \(\bm{z}\)，则最近邻分类器出错的概率就是 \(\bm{x}\) 与 \(\bm{z}\) 类别标记不同的概率，即

\[ P(err) = 1 - \sum_{c \in \mathcal{Y}} P(c | \bm{x}) P(c | \bm{z}) \]

假设样本独立同分布，且对任意 \(\bm{x}\) 和任意小正数 \(\delta\)，在 \(x\) 附近 \(\delta\) 距离范围内总能找到一个训练样本；换言之，对任意测试样本，总能在任意近的范围内找到上式中的训练样本 \(\bm{z}\)。令 \(c^* = \argmax_{c \in \mathcal{Y}} P(c | \bm{x})\)，表示贝叶斯最优分类器的结果，有

\[ \begin{aligned} P(err) & = 1 - \sum_{c \in \mathcal{Y}} P(c | \bm{x}) P(c | \bm{z}) \\ & \simeq 1 - \sum_{c \in \mathcal{Y}} P^2(c | \bm{x}) \\ & \le 1 - P^2(c^* | \bm{x}) \\ & = (1 + P(c^* | \bm{x}))(1 - P(c^* | \bm{x})) \\ & \le 2(1 - P(c^* | \bm{x})) \end{aligned} \]

于是我们可以得到这样一个令人惊讶的结论：最近邻分类器的泛化错误率不超过贝叶斯最优分类器的错误率的两倍。

低维嵌入

上一节的讨论是基于一个重要假设：任意测试样本 \(\bm{x}\) 附近任意小的 \(\epsilon\) 距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为密采样（dense sample）。然而，这个假设在现实任务中通常很难满足。此外，许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大的麻烦，例如当维数很高时甚至连计算内积都不再容易。

事实上，在高维情形下出现的数据样本稀疏、距离计算困难等问题，是所有机器学习方法共同面临的严重障碍，被称为维数灾难（curse of dimensionality）。

缓解维数灾难的一个重要途径是降维（dimension reduction），亦称维数约简，即通过某种数学变换将原始高维属性空间转变为一个低维子空间，在这个子空间中样本密度大幅提高，距离计算也变得更为容易。为什么能进行降维？这是因为在很多时候，人们观测或收集到的数据样本虽是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维嵌入（embedding）。

多维缩放降维

若要求原始空间中样本之间的距离在低维空间中得以保持，即得到多维缩放（Multiple Dimensional Scaling, 简称 MDS）这样一种经典的降维方法。下面做一个简单的介绍。

假定 \(m\) 个样本在原始空间的距离矩阵为 \(D \in \mathbb{R}^{m \times m}\)，其中第 \(i\) 行第 \(j\) 列的元素 \(\text{dist}_{ij}\) 为样本 \(\bm{x}_i\) 到 \(\bm{x}_j\) 的距离。我们的目标是获得样本在 \(d'\) 维空间的表示 \(Z \in \mathbb{R}^{d' \times m}\)，其中 \(d' \le d\)，且任意两个样本在 \(d'\) 维空间中的欧氏距离等于原始空间中的距离，即 \(\| \bm{z}_i - \bm{z}_j \| = \text{dist}_{ij}\)。

令 \(B = Z^T Z \in \mathbb{R}^{m \times m}\)，其中 \(B\) 为降维后样本的内积矩阵，\(\bm{z}_i^T \bm{z}_j = b_{ij}\)，有

\[ \begin{aligned} \text{dist}_{ij}^2 & = \| \bm{z}_i \|^2 + \| \bm{z}_j \|^2 - 2 \bm{z}_i^T \bm{z}_j \\ & = b_{ii} + b_{jj} - 2 b_{ij} \end{aligned} \]

为便于讨论，令降维后的样本 \(Z\) 被中心化，即 \(\sum_{i=1}^m \bm{z}_i = 0\)。显然，矩阵 \(B\) 的行与列之和均为零，即 \(\sum_{i=1}^m b_{ij} = \sum_{j=1}^m b_{ij} = 0\)。易知

\[ \sum_{i=1}^m \text{dist}^2_{ij} = \text{tr}(B) + m b_{jj} \]

\[ \sum_{j=1}^m \text{dist}^2_{ij} = \text{tr}(B) + m b_{ii} \]

\[ \sum_{i=1}^m \sum_{j=1}^m \text{dist}^2_{ij} = 2m \ \text{tr}(B) \]

令

\[ \text{dist}^2_{i\cdot} = \frac{1}{m} \sum_{j=1}^m \text{dist}^2_{ij} \ , \ \ \text{dist}^2_{\cdot j} = \frac{1}{m} \sum_{i=1}^m \text{dist}^2_{ij} \ , \ \ \text{dist}^2_{\cdot\cdot} = \frac{1}{m^2} \sum_{i=1}^m \sum_{j=1}^m \text{dist}^2_{ij} \]

则由以上定义可得

\[ b_{ij} = -\frac{1}{2} (\text{dist}^2_{ij} - \text{dist}^2_{i\cdot} - \text{dist}^2_{\cdot j} + \text{dist}^2_{\cdot\cdot}) \]

由此即可通过降维前后保持不变的距离矩阵 \(D\) 求取内积矩阵 \(B\)。

对矩阵 \(B\) 做特征值分解（eigenvalue decomposition），\(B = V \Lambda V^T\)，其中 \(\Lambda = \text{diag}(\lambda_1, \lambda_2, ..., \lambda_d)\) 为特征值构成的对角矩阵，\(V\) 为特征向量矩阵。假定其中有 \(d^*\) 个非零特征值，它们构成对角矩阵 \(\Lambda_* = \text{diag}(\lambda_1, \lambda_2, ..., \lambda_{d^*})\)，令 \(V^*\) 表示相应的特征向量矩阵，则 \(Z\) 可表达为

\[ Z = \Lambda_*^{1/2} V^{T}_* \in \mathbb{R}^{d^* \times m} \]

在现实应用中为了有效降维，往往仅需降维后的距离与原始空间中的距离尽可能接近，而不必严格相等。此时可取最大 \(d' \ll d\) 个最大特征值构成对角矩阵 \(\tilde{\Lambda} = \text{diag}(\lambda_1, \lambda_2, ..., \lambda_{d'})\)，令 \(\tilde{V}\) 表示相应的特征向量矩阵，则 \(Z\) 可表达为

\[ Z = \tilde{\Lambda}^{1/2} \tilde{V}^T \in \mathbb{R}^{d' \times m} \]

线性降维

一般来说，欲获得低维子空间，最简单的是对原始高维空间进行线性变换。给定 \(d\) 维空间中的样本 \(X = (\bm{x}_1, \bm{x}_2, ..., \bm{x}_m) \in \mathbb{R}^{d \times m}\)，变换之后得到 \(d'\) 维空间中的样本

\[ Z = W^T X \in \mathbb{R}^{d' \times m} \]

其中 \(W \in \mathbb{R}^{d \times d'}\) 是变换矩阵，\(\bm{z}_i = W^T \bm{x}_i\) 是原属性向量 \(\bm{x}_i\) 在新坐标系 \(\{ \bm{w}_1, \bm{w}_2, ..., \bm{w}_{d'} \}\) 中的坐标向量。

基于线性变换来进行降维的方法称为线性降维方法，它们都符合上述基本形式，不同之处是对低维子空间的性质有不同的要求，相当于对 \(W\) 施加了不同的约束。

主成分分析

假定数据样本进行了中心化，即 \(\sum_{i=1}^m \bm{x}_i = 0\)，再假定投影变换 \(W \in \mathbb{R}^{d \times d'}\) 后得到的新坐标系 \(\{ \bm{w}_1, \bm{w}_2, ..., \bm{w}_{d'} \}\) 为标准正交坐标系。样本点 \(\bm{x}_i\) 在低维坐标系中的投影是 \(\bm{z}_i = W^T \bm{x}_i\)，其中 \(z_{ij} = \bm{w}_j^T \bm{x}_i\) 是 \(\bm{x}_i\) 在低维坐标系下第 \(j\) 维的坐标。若基于 \(\bm{z}_i\) 来重构 \(\bm{x}_i\)，则会得到 \(\hat{\bm{x}}_i = \sum_{j=1}^{d'} z_{ij} \bm{w}_j = W \bm{z}_i\)

考虑整个训练集，原样本点 \(\bm{x}_i\) 与基于投影重构的样本点 \(\hat{\bm{x}}_i\) 之间的距离为

\[ \begin{aligned} \sum_{i=1}^m \left\| W\bm{z}_i - \bm{x}_i \right\|_2^2 & = \sum_{i=1}^m \bm{z}_i^T \bm{z}_i - 2 \sum_{i=1}^m \bm{z}_i^T W^T \bm{x}_i + \text{const} \\ & = - \sum_{i=1}^m \bm{z}_i^T \bm{z}_i + \text{const} \\ & \propto - \text{tr} \left( W^T XX^T W \right) \end{aligned} \]

根据最近重构性，即样本点到超平面的距离应尽可能近，上式应被最小化，考虑到 \(\bm{w}_j\) 是标准正交基，\(XX^T\) 是协方差矩阵，有

\[ \min_{W} - \text{tr} \left( W^T XX^T W \right) \]

\[ \text{s.t.} \quad W^T W = I \]

这就是主成分分析（Principal Component Analysis，简称 PCA）的优化目标。

从最大可分性出发，即样本点在这个超平面上的投影应尽可能分开，能得到主成分分析的另一种解释。若所有样本点的投影能尽可能分开，则应该使投影后样本点的方差 \(W^T XX^T W\) 最大化，于是优化目标可写为

\[ \max_{W} \text{tr} \left( W^T XX^T W \right) \]

\[ \text{s.t.} \quad W^T W = I \]

对上面任意一个优化目标使用拉格朗日乘子法可得

\[ XX^T W = \lambda W \]

观察上式可以发现，\(\lambda\) 是 \(XX^T\) 的特征值的集合，\(W\) 是 \(XX^T\) 的特征向量的集合。同时，将上式代入目标，目标就会变成

\[ \max_{W} \sum_{i=1}^{d'} \lambda_i \]

于是，只需要对协方差矩阵 \(XX^T\) 进行特征值分解，将求得的特征值排序，再取最大的 \(d'\) 个特征值对应的特征向量构成 \(W = (\bm{w}_1, \bm{w}_2, ..., \bm{w}_{d'})\)，这就是主成分分析的解。

PCA 算法描述如下：

1. 对所有样本进行中心化：\(\bm{x}_i \leftarrow \bm{x}_i - \bar{\bm{x}}\)
2. 计算样本的协方差矩阵 \(XX^T\)
3. 对协方差矩阵 \(XX^T\) 做特征值分解
4. 取最大的 \(d'\) 个特征值所对应的特征向量 \(\bm{w}_1, \bm{w}_2, ..., \bm{w}_{d'}\) 组成投影矩阵 \(W\)

对 PCA，还可从重构的角度设置一个重构阈值 \(t\)，然后选取使下式成立的最小 \(d'\) 值：

\[ \frac{\sum_{i=1}^{d'} \lambda_i}{\sum_{i=1}^d \lambda_i} \ge t \]

核化线性降维

非线性降维的一种常用方法，是基于核技巧对线性降维方法进行核化（kernelized）。下面我们以核主成分分析（Kernelized PCA，简称 KPCA）为例来进行演示。

假定我们先通过 \(\phi\) 将样本 \(\bm{x}_i\) 映射至高维特征空间，再在特征空间中实施 PCA，则求解目标就会变为

\[ \left( \sum_{i=1}^m \phi(\bm{x}_i) \phi(\bm{x}_i)^T \right) W = \lambda W \tag{1} \]

对该式进行变换可得

\[ W = \sum_{i=1}^m \phi(\bm{x}_i) \frac{\phi(\bm{x}_i)^T W}{\lambda} = \sum_{i=1}^m \phi(\bm{x}_i) \bm{\alpha}_i = \phi(X) A \tag{2} \]

其中 \(\phi(X) = (\phi(\bm{x}_1), \phi(\bm{x}_2), ..., \phi(\bm{x}_m))\)，\(A = (\bm{\alpha}_1; \bm{\alpha}_2; ...; \bm{\alpha}_m)\)。

一般情况下，我们不清楚 \(\phi\) 的具体形式，于是引入核函数及其对应的核矩阵 \(K\)，即

\[ \kappa(\bm{x}_i, \bm{x}_j) = \phi(\bm{x}_i)^T \phi(\bm{x}_j) \]

\[ K = \phi(X)^T \phi(X) \tag{3} \]

将式 (2) 和 (3) 代入式 (1) 后化简可得

\[ \begin{aligned} & \phi(X) \phi(X)^T \phi(X) A = \lambda \phi(X) A \\ \Rightarrow \ \ & \phi(X)^T \phi(X) \phi(X)^T \phi(X) A = \lambda \phi(X)^T \phi(X) A \\ \Rightarrow \ \ & K K A = \lambda K A \\ \Rightarrow \ \ & K A = \lambda A \end{aligned} \]

对新样本 \(\bm{x}\)，其投影后的第 \(j\)（\(j = 1, 2, ..., d'\)）维坐标为

\[ z_j = \bm{w}_j^T \phi(\bm{x}) = \sum_{i=1}^m A_{ij} \phi(\bm{x}_i)^T \phi(\bm{x}) = \sum_{i=1}^m A_{ij} \kappa(\bm{x}_i, \bm{x}) \]

可以看到，\(\phi(\bm{x})\) 和 \(W\) 并不需要显式地计算。为了获得投影后的坐标，KPCA 需对所有样本求和，因此它的计算开销较大。

流形学习

流形学习（manifold learning）是一类借鉴了拓扑流形概念的降维方法。流形是在局部与欧氏空间同胚的空间，换言之，它在局部具有欧氏空间的性质，能用欧氏距离来进行距离计算。这给降维方法带来了很大的启发：若低维流形嵌入到高维空间中，则数据样本在高维空间的分布虽然看上去非常复杂，但在局部上仍具有欧氏空间的性质，因此，可以容易地在局部建立降维映射关系，然后再设法将局部映射关系推广到全局。当维数被降至二维或三维时，能对数据进行可视化展示，因此流形学习也可被用于可视化。

等度量映射

等度量映射（Isometric Mapping，简称 Isomap）的基本出发点，是认为低维流形嵌入到高维空间之后，直接在高维空间中计算直线距离具有误导性，因为高维空间中的直线距离在低维嵌入流形上是不可达的。因此，应该使用测地线（geodesic）距离，即两点在高维曲面上的最短路径距离。

那么，如何计算测地线距离呢？这时我们可利用流形在局部上与欧氏空间同胚这个性质，对每个点基于欧氏距离找出其近邻点，然后就能建立一个近邻连接图，图中近邻点之间存在连接，而非近邻点之间不存在连接，于是，计算两点之间测地线距离的问题，就转变为计算近邻连接图上两点之间的最短路径问题。在近邻连接图上计算两点间的最短路径，可采用著名的 Dijkstra 算法或 Floyd 算法。在得到任意两点的距离之后，就可通过 MDS 方法来获得样本点在低维空间中的坐标。

Isomap 算法描述如下：

1. 确定每个样本 \(x_i\) 的 \(k\) 近邻
2. 将 \(x_i\) 与其 \(k\) 个近邻点之间的距离设置为欧氏距离，与其他点的距离设置为无穷大
3. 调用最短路径算法计算任意两样本点之间的距离
4. 将这个距离作为 MDS 算法的输入

需注意的是，Isomap 仅是得到了训练样本在低维空间的坐标，还无法直接映射新样本。这个问题的常用解决方案，是将训练样本的高维空间坐标作为输入、低维空间坐标作为输出，训练一个回归学习器来对新样本的低维空间坐标进行预测。

局部线性嵌入

与 Isomap 试图保持流形上的测地线距离不同，局部线性嵌入（Locally Linear Embedding，简称 LLE）试图保持流形上的局部线性关系。

LLE 先为每个样本找到其近邻下标集合 \(Q_i\)，然后计算出基于 \(Q_i\) 中的样本点对 \(x_i\) 进行线性重构的系数 \(W_{ij}\)：

\[ \min_{\bm{w}_1, \bm{w}_2, ..., \bm{w}_m} \sum_{i=1}^m \left\| \bm{x}_i - \sum_{j \in Q_i} w_{ij} \bm{x}_j \right\|_2^2 \tag{1}\]

\[ \text{s.t.} \quad \sum_{j \in Q_i} w_{ij} = 1 \]

令 \(C_{jk} = (\bm{x}_i - \bm{x}_k)^T (\bm{x}_i - \bm{x}_k)\)，\(W = \sum_{k \in Q_i} w_{ik}\)，\(w_{ij}\) 有闭式解

\[ w = \frac{\sum_{k \in Q_i} C_{jk}^{-1}}{\sum_{l, s \in Q_i} C_{ls}^{-1}} \]

LLE 在低维空间保持 \(\bm{w}_i\) 不变，于是 \(x_i\) 对应的低维空间坐标 \(z_i\) 可通过下式求解：

\[ \min_{\bm{z}_1, \bm{z}_2, ..., \bm{z}_m} \sum_{i=1}^m \left\| \bm{\bm{z}}_i - \sum_{j \in Q_i} w_{ij} \bm{\bm{z}}_j \right\|_2^2 \]

令 \(Z = (\bm{z}_1, \bm{z}_2, ..., \bm{z}_m) \in \mathbb{R}^{d' \times m}\)，\((W)_{ij} = w_{ij}\)，\(M = (I - W)^T (I - W)\)，则上式可重写为

\[ \min_{Z} \text{tr}(ZMZ^T) \]

\[ \text{s.t.} \quad ZZ^T = I \]

LLE 的算法描述如下：

1. 确定每个样本 \(x_i\) 的 \(k\) 近邻
2. 若 \(j \in Q_i\)，则从式 (1) 求得 \(w_{ij}\)，否则 \(w_{ij} = 0\)
3. 从 \(W\) 计算得到 \(M\)
4. 对 \(M\) 进行特征值分解，取最小的 \(d'\) 个特征值对应的特征向量组成的矩阵即为 \(Z\)

度量学习

在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，使得在此空间中进行学习能比原始空间性能更好。事实上，每个空间对应了在样本属性上定义的一个距离度量，而寻找合适的空间，实质上就是在寻找一个合适的距离度量。度量学习（metric learning），亦称距离度量学习（distance metric learning）的目的，就是找到一个“合适”低维空间下的距离度量。

首先，需要能够通过“参数化”来学习距离度量，马氏距离（Mahalanobis distance）就是一个很好的选择。它是出自这样的考量：在现实问题中，不同属性的重要性不同，属性之间也可能相关，因此，我们可以引入一个半正定对称矩阵 \(M\)，得到

\[ \text{dist}^2_{\text{mah}}(\bm{x}_i, \bm{x}_j) = (\bm{x}_i - \bm{x}_j)^T M (\bm{x}_i - \bm{x}_j) = \| \bm{x}_i - \bm{x}_y \|^2_{M} \]

其中 \(M\) 被称为度量矩阵，而度量学习则是对 \(M\) 进行学习。注意到为了保持距离非负且对称，\(M\) 必须是（半）正定对称矩阵，即必有正交基 \(P\) 使得 \(M = P P^T\)。

对 \(M\) 进行学习当然要设置一个目标。一种设置方法是结合具体分类器的性能。例如，在近邻成分分析（Neighbourhood Component Analysis，简称 NCA）中，我们可以将多数投票法替换为概率投票法，从而将 \(M\) 直接嵌入到近邻分类器的评价指标中，通过优化该性能指标相应地求得 \(M\)。具体来说，对于任意样本 \(\bm{x}_j\)，它对 \(\bm{x}_i\) 的分类结果影响的概率为

\[ p_{ij} = \frac{\exp(-\| \bm{x}_i - \bm{x}_j \|^2_{M})}{\sum_{l} \exp(-\| \bm{x}_i - \bm{x}_l \|^2_{M})} \]

另一种设置方法是结合领域知识。例如，若已知某些样本相似、某些样本不相似，则可定义“必连”（must-link）约束集合 \(\mathcal{M}\) 与“勿连”（cannot-link）约束集合 \(\mathcal{C}\)，即 \((\bm{x}_i, \bm{x}_j) \in \mathcal{M}\) 表示 \(\bm{x}_i\) 与 \(\bm{x}_j\) 相似，\((\bm{x}_i, \bm{x}_k) \in \mathcal{C}\) 表示 \(\bm{x}_i\) 与 \(\bm{x}_k\) 不相似。于是，我们希望相似的样本之间距离较小，不相似的样本之间距离较大，于是可通过求解下面这个凸优化问题获得适当的度量矩阵 \(M\)

\[ \min_{M} \sum_{(i, j) \in \mathcal{M}} \| \bm{x}_i - \bm{x}_j \|^2_{M} \]

\[ \text{s.t.} \quad \sum_{(\bm{x}_i, \bm{x}_k) \in \mathcal{C}} \| \bm{x}_i - \bm{x}_k \|^2_{M} \ge 1, \quad M \succeq 0 \]

不同的度量学习方法针对不同目标获得“好”的半正定对称距离度量矩阵 \(M\)，若 \(M\) 是一个低秩矩阵，则通过对 \(M\) 进行特征值分解，总能找到一组正交基，其正交基数目为矩阵 \(M\) 的秩，小于原属性数 \(d\)。于是，度量学习学得的结果可衍生出一个降维矩阵 \(P \in \mathbb{R}^{d \times \text{rank}(M)}\)，能用于降维之目的。