西瓜书第10章：降维与度量学习

---

K 近邻学习 (k-Nearest Neighbor, kNN)

K 近邻学习器是懒惰学习(lazy learning) 的代表，基本思路是近朱者赤，近墨者黑

与懒惰学习相反的是急切学习（eager learning），二者的差别在于在训练阶段是否对样本进行学习

主要需要注意两个方面：

• K 值的选取
• 距离的计算

最近邻学习器的误差分析

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

$$P(err) = 1 - \sum_{c\in \mathcal{Y}}P(c|\boldsymbol{x})P(c|\boldsymbol{z})$$

假设样本独立同分布，令 $c^\star=arg\ max_{c\in \mathcal{Y}} P(c|\boldsymbol{x})$ 表示贝叶斯最优分类器的结果，则有：

$$\begin{aligned} P(err) &= 1-\sum_{c\in \mathcal{Y}}P(c|\boldsymbol{x})P(c|\boldsymbol{z})\\ &\simeq 1-\sum_{c\in \mathcal{Y}}P^2(c|\boldsymbol{x})\\ &\leq 1-P^2(c^\star|\boldsymbol{x})\\ &\leq (1 + P(c^\star | \boldsymbol{x}) ) (1 - P(c^\star | \boldsymbol{x}) )\\ &\leq 2 \times (1 - P(c^\star|\boldsymbol{x})) \end{aligned}$$

也即：最邻近分类器的泛化误差不会超过贝叶斯最优分类器的两倍！

维数问题

上述结论是基于一个重要假设：任意测试样本 $\boldsymbol{x}$ 附近任意小的 $\delta$ 距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为“密采样”（dense sample）

然而这在现实中很难实现！

但维数为 1 时，若考虑 $\delta=0.001$，则需要 1000 个样本；若属性更多，如属性维数为 20，则需要$(10^3)^{20}=10^{60}$ 个样本！同样，对于一张并不是很清晰的图像：70余万维，我们为了找到恰当的近邻，需要多少样本？

另外一方面，高维空间给距离计算带来很大的麻烦，当维数很高时甚至连计算内积都不再容易！

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

降维

缓解维数灾难的一个重要途径是降维，亦称“维数约简”（dimension reduction）

即：通过某种数学变换将原始高维属性空间转变为一个低维子空间，在这个子空间中样本密度大幅提高，距离计算也变得更为容易。

为什么能进行降维？

数据样本虽是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维“嵌入” (embedding)

多维缩放方法（MDS）

如果要求原始空间中样本之间的距离在低维空间中得以保持，即为：多维缩放（Multiple Dimensional Scaling）

如何在距离矩阵和内积矩阵之间建立联系？

假定 m 个样本在原始空间的距离矩阵为 $D \in \mathbb{R}^{m \times m}$，其 $dist_{ij}$ 为样本 $\boldsymbol{x}_i$ 到 $\boldsymbol{x}_j$ 的距离。

目标为获得样本在 $d'$ 维空间的表示 $Z \in \mathbb{R}^{d' \times m}, d' \leq d$，且这两种表示下的距离不变，即有：$\Vert\boldsymbol{z}_i - \boldsymbol{z}_j\Vert=dist_{ij}$

令 $B=Z^TZ \in \mathbb{R}^{m \times m}$ 为降维后的样本的内积矩阵，即： $b_{ij}=\boldsymbol{z}_i^T\boldsymbol{z}_j$，有：

$$\begin{aligned} dist_{ij}^2 &= \Vert\boldsymbol{z}_i^2\Vert + \Vert\boldsymbol{z}_j^2\Vert - 2\boldsymbol{z}_i^T\boldsymbol{z}_j \\ &= b_{ii} + b_{jj} - 2b_{ij} \end{aligned}$$

设降维后的样本 $Z$ 被中心化，即：$\sum_{i=1}^m\boldsymbol{z}_i=0$

则：矩阵 $B$ 中行与列之和均为0，即：$\sum_{i=1}^mb_{ij}=\sum_{j=1}^mb_{ij}=0$

$$\sum_{i=1}^mdist_{ij}^2=tr(B) + mb_{jj}$$

$$\sum_{j=1}^mdist_{ij}^2=tr(B) + mb_{ii}$$

$$\sum_{i=1}^m\sum_{j=1}^mdist_{ij}^2=2m\ tr(B)$$

其中 $tr(\cdot)$ 表示矩阵的迹，$tr(B)=\sum_{i=1}^m\Vert\boldsymbol{z}_i\Vert$。令：

$$dist_{i\cdot}^2=\frac{1}{m}\sum_{j=1}^mdist_{ij}^2$$

$$dist_{\cdot j}^2=\frac{1}{m}\sum_{i=1}^mdist_{ij}^2$$

$$dist_{\cdot\cdot}^2=\frac{1}{m^2}\sum_{i=1}^m\sum_{j=1}^mdist_{ij}^2$$

则可得：

$$b_{ij}=-\frac{1}{2}(dist_{ij}^2 - dist_{i\cdot}^2 - dist_{\cdot j}^2 + dist_{\cdot\cdot}^2)$$

至此，得到了距离矩阵到内积矩阵的变换公式。

如何在低维子空间和高维空间之间保持样本之间的内积不变？

对矩阵 $B$ 进行特征值分解：$B=V\Lambda V^T$

由谱分解的数学性质，我们知道：谱分布长尾，存在相当数量的小特征值，而只有少量的较大的特征值

因此可取 $d'\ll d$ 个最大特征值构成对角矩阵 $\tilde{\Lambda}=diag(\lambda_1, \dots, \lambda_{d'})$，且 $\tilde{V}$ 表示相应的特征向量矩阵，则可得到：

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

主成分分析（PCA）

另一种常用的降维方法为主成分分析（principal Component Analysis）

正交属性空间中的样本点，如何使用一个超平面对所有样本进行恰当的表达？

若存在这样的超平面，那么它大概应具有这样的性质：

• 最近重构性：样本点到这个超平面的距离都足够近
• 最大可分性：样本点在这个超平面上的投影能尽可能分开

基于最近重构性和最大可分性，可以得到主成分分析的两种等价推导。

最近重构性

假定对样本进行了中心化：$\sum_i\boldsymbol{x}_i=0$

假定投影变换后得到的新坐标系为 $\{\boldsymbol{w}_1,\dots ,\boldsymbol{w}_d\}$ ， 其中 $\boldsymbol{w}_i$ 是标准正交基向量，$\Vert\boldsymbol{w}_i\Vert_2=1, \boldsymbol{w}_i^T\boldsymbol{w}_j=0 (i\not ={j})$

若丢弃新坐标系中的部分坐标，即将维度降低到 $d'<d$，则样本点$\boldsymbol{x}_i$在低维坐标系中的投影是 $z_{i}=(z_{i1};z_{i2};\dots;z_{id'})$，其中$z_{ij}=\boldsymbol{w}_j^T\boldsymbol{x}_i$是 $\boldsymbol{x}_i$ 在低维坐标系下第 $j$ 维的坐标。

若基于 $\boldsymbol{z}_i$ 来重构 $\boldsymbol{x}_i$，则会得到 $\hat{\boldsymbol{x}}_i=\sum_{j=1}^{d'}z_{ij}\boldsymbol{w}_j$

则原样本点 $\boldsymbol{x}_i$ 与基于投影重构的样本点 $\hat{\boldsymbol{x}}_i$ 之间的距离为：

$$\begin{aligned} \sum_{i=1}^m\Vert\sum_{j=1}^{d'}z_{ij}\boldsymbol{w}_j-\boldsymbol{x}_i\Vert_2^2 &= \sum_{i=1}^m\boldsymbol{z}_i^T\boldsymbol{z}_i-2\sum_{i=1}^m\boldsymbol{z}_i^TW^T\boldsymbol{x}_i+const \\ &\propto -tr\left(W^T\left(\sum_{i=1}^m \boldsymbol{x}_i\boldsymbol{x}_i^T\right)W \right) \end{aligned}$$

其中 $W=(\boldsymbol{w}_1,\dots,\boldsymbol{w}_d)$，根据最近重构性，上式应该被最小化，由于 $\boldsymbol{w}_j$ 是标准正交基，$\sum_i\boldsymbol{x}_i\boldsymbol{x}_i^T$ 是协方差矩阵，则有主成分分析的优化目标：

$${min}\ -tr(W^TXX^TW), \ s.t.\ W^TW=I$$

最大可分性

样本点 $\boldsymbol{x}_i$ 在新空间中超平面上的投影为 $W^T\boldsymbol{x}_i$，若所有的样本点的投影尽可能分开，则应该使投影后样本点的方差最大化

由于投影后样本点的协方差矩阵是 $\sum_iW^T\boldsymbol{x}_i\boldsymbol{x}_i^TW$，因此优化目标即为：

$${max}\ tr(W^TXX^TW), \ s.t.\ W^TW=I$$

PCA 求解

对优化目标使用拉格朗日乘子法:

$$XX^T\boldsymbol{w}_i=\lambda_i\boldsymbol{w}_i$$

于是只需对协方差矩阵 $XX^T$ 进行特征值分解，将求得的特征值排序：$\lambda_1\ge\lambda_2\ge\dots\ge\lambda_d$，再取前$d'$个特征值对应的特征向量构成

$$W^*=(\boldsymbol{w}_1, \boldsymbol{w}_2, \dots,\boldsymbol{w}_{d'})$$

这就是主成分分析的解

参数设置

$d'$ 的设置：

• 用户指定
• 在低维空间中对k近邻或其他分类器进行交叉验证
• 设置重构阈值，例如 $t=95\%$，然后选取最小的 $d'$ 使得 $\frac{\sum_{i=1}^{d'}\lambda_i}{\sum_{i=1}^d\lambda_i}\ge t$

PCA 是最常用的降维方法，在不同领域有不同的称谓

例如在人脸识别中该技术被称为“特征脸”(eigenface)，因为若将前 $d'$ 个特征值对应的特征向量还原为图像，则得到近似于人脸的识别模型示意图

非线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的，然而在许多现实任务中，可能需要非线性映射才能找到恰当的低维嵌入

非线性降维的常用方法：

• 核化线性降维: 如KPCA, KLDA, …
• 流形学习(manifold learning)

核化PCA方法（KPCA）

首先在高维特征空间中，将数据投影到由 $W=(\boldsymbol{w}_1, \dots , \boldsymbol{w}_d)$ 确定的超平面上。则有：

$$\left( \sum_{i=1}^m\boldsymbol{z}_i\boldsymbol{z}_i^T \right)\boldsymbol{w}_j=\lambda_j\boldsymbol{w}_j$$

$$\boldsymbol{w}_j=\frac{1}{\lambda_j}\left(\sum_{i=1}^m\boldsymbol{z}_i\boldsymbol{z}_i^T \right)\boldsymbol{w}_j=\sum_{i=1}^m\boldsymbol{z}_i\frac{\boldsymbol{z}_i^T\boldsymbol{w}_j}{\lambda_j}=\sum_{i=1}^m\boldsymbol{z}_i\alpha_i^j$$

其中 $\alpha_i^j=\frac{1}{\lambda_j}\boldsymbol{z}_i^T\boldsymbol{w}_j$ 是 $\alpha_i$ 的第 $j$ 个分量，$\boldsymbol{z}_i$ 是由样本点 $\boldsymbol{x}_i$ 在高维特征空间中通过映射 $\phi$ 产生，即 $\boldsymbol{z}_i=\phi(\boldsymbol{x}_i)$。

若 $\phi$ 能显式的表达出来，则可通过它将样本映射到高维特征空间，再在高维特征空间中实施 PCA 即可。从而有：

$$\left( \sum_{i=1}^m\phi(\boldsymbol{x}_i)\phi(\boldsymbol{x}_i)^T \right)\boldsymbol{w}_j=\lambda_j\boldsymbol{w}_j$$

$$\boldsymbol{w}_j=\sum_{i=1}^m\phi(\boldsymbol{x}_i)\alpha_i^j$$

但是一般情况下， $\phi$ 的形式不清楚，因此引入核函数：$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\phi(\boldsymbol{x}_i)^T\phi(\boldsymbol{x}_i), (K)_{ij}=\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)$，代入可得：

$$K\boldsymbol{\alpha}^j=\lambda_j\boldsymbol{\alpha}^j$$

显然这是特征值分解问题，取 $K$ 最大的 $d'$ 个特征值对应的特征向量即可。

从而，对于样本 $\boldsymbol{x}$ ，其投影后的第 $j$ 维坐标为：

$$z_j=\boldsymbol{w}_j^T\phi(\boldsymbol{x})=\sum_{i=1}^m\alpha_i^j\phi(\boldsymbol{x}_i)^T\phi(\boldsymbol{x}) = \sum_{i=1}^m\alpha_i^j\kappa(\boldsymbol{x}_i,\boldsymbol{x})$$

此式表明，为获得投影后的坐标，KPCA需要对所有样本求和，因此计算开销比较大。

流形学习

“流形”是在局部与欧氏空间同胚的空间，即在局部具有欧氏空间的性质，可用欧氏距离进行距离计算。

应用到降维：若低维流形嵌入到高维空间中，则数据样本在高维空间上的分布看似复杂，但在局部仍具有欧氏空间的性质，因此可以容易的在局部建立降维映射关系，然后再设法将局部映射推广到全局。

等度量映射（Isomap）

基本出发点：试图保持近邻样本之间的距离

但：低维流形嵌入到高维空间后，直接在高维空间中计算直线距离具有误导性，因为高维空间上的直线距离在低维空间中是不可达的。

低维空间上两点的距离是 “测地线” 距离，这是两点之间的本真距离。

如何计算测地线距离：

• 利用流形的距离性质，对每个点基于欧氏距离找出近邻点，图中近邻点之间存在连接，非近邻点之间无连接
• 距离问题就变成了计算近邻连接图上两点之间最短路径问题，可用 Dijkstra 算法或者 Floyd 算法
• 得到距离后，再使用 MDS 方法获得样本在低维空间中的坐标

Isomap 算法得到的是训练样本在低维空间的坐标，对于新样本，如何进行映射？

将训练样本的高维坐标作为输入，低维坐标作为输出，训练一个回归学习器。（权宜之计，暂时没有更好的办法）

如何构造近邻图：

• 指定近邻点个数，得到 $k$ 近邻图
• 指定距离阈值 $\epsilon$，得到 $\epsilon$ 近邻图

不足之处：

• 若近邻范围过大：距离比较远的点仍认为是近邻，导致“短路”问题
• 若距离范围过小：图中某些区域与其他区域会不存在连接，导致“断路”问题

局部线性嵌入（LLE）

基本出发点：试图保持邻域内样本间的线性关系，重构权值

// TODO： 添加推导步骤

基本步骤：

• 为每个样本构造近邻集合 $Q_i$

• 为每个样本计算基于 $Q_i$ 的线性重构系数：

  

• 在低维空间中保持 $W_{ij}$ 不变，求解：

  

度量学习

对高维数据进行降维的主要目的是希望找到一个“合适的”低维空间，从而获得更好的学习性能。

实际上，每个空间对应了在样本属性上定义的一个距离度量，寻找合适的空间，就是寻找一个合适的距离度量。

那么，能否直接尝试“学出”合适的距离度量？

马氏距离

首先，要有可以通过学习来“参数化”的距离度量形式: 马氏距离(Mahalanobis distance) 是一个很好的选择：

$$dist_{mah}^2(\boldsymbol{x}_i,\boldsymbol{x}_j) = (\boldsymbol{x}_i-\boldsymbol{x}_j)^TM(\boldsymbol{x}_i-\boldsymbol{x}_j) = \Vert\boldsymbol{x}_i-\boldsymbol{x}_j\Vert_M^2$$

其中 $M$ 即称之为度量矩阵，必须是半正定对称矩阵（$M=PP^T$, $P$为正交基），而度量学习即是对 $M$ 进行学习。

学习目标

其次，对 $M$ 进行学习需要设置一个目标：

• 某种分类器的性能

  例如，若以近邻分类器的性能为目标，则得到近邻成分分析（NCA）

• 领域知识

  例如，若已知“必连”(must-link) 约束集合与“勿连”(cannot-link)
  约束集合 ，则C可通过求解这个凸优化问题得到 M:

近邻成分分析（NCA）

近邻分类器在进行判别时通常使用多数投票法，邻域内的样本投1票，其他投0票。

不妨将其替换为概率投票法：对于任意样本 $\boldsymbol{x}_j$，他对 $\boldsymbol{x}_i$ 分类结果的影响的概率为：

$$p_{ij} = \frac{\exp(-\Vert\boldsymbol{x}_i-\boldsymbol{x}_j\Vert_M^2)}{\sum_l\exp(-\Vert\boldsymbol{x}_i-\boldsymbol{x}_l\Vert_M^2)}$$

显然，$\boldsymbol{x}_j$ 对 $\boldsymbol{x}_i$ 的影响随着它们之间距离的增大而减少。若以留一法（LOO）正确率的最大化为目标，则 $\boldsymbol{x}_i$ 的 LOO 正确率为：

$$p_i=\sum_{j \in \Omega_i}p_{ij}$$

整个样本集上的 LOO 正确率为：

$$\sum_{i=1}^mp_i=\sum_{i=1}^m\sum_{j \in \Omega_i}p_{ij}$$

则可得NCA的优化目标为：

$$min\ 1-\sum_{i=1}^m\sum_{j \in \Omega_i}\frac{\exp(-\Vert P^T\boldsymbol{x}_i-P^T\boldsymbol{x}_j\Vert_2^2)}{\sum_l\exp(-\Vert P^T\boldsymbol{x}_i-P^T\boldsymbol{x}_l\Vert_2^2)}$$

求解此式即可得到最大化近邻分类器LOO正确率的距离度量矩阵 $M$

LMNN

若已知某些样本相似，某些样本不相似，则可定义：

• “必连”约束集合：$M$, $(\boldsymbol{x}_i, \boldsymbol{x}_j)\in M$ 表示 $\boldsymbol{x}_i, \boldsymbol{x}_j$ 相似
• “勿连”约束集合：$C$, $(\boldsymbol{x}_i, \boldsymbol{x}_j)\in C$ 表示 $\boldsymbol{x}_i, \boldsymbol{x}_j$ 不相似

显然，我们希望相似的样本之间的距离较小，不相似的比较大，因此可以转化为下面这个凸优化问题获取适当的度量矩阵 $M$：

$$\begin{array}{ll} {\min _{\mathbf{M}}} & {\sum_{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \in \mathcal{M}}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|_{\mathrm{M}}^{2}} \\\\ {\text { s.t. }} & {\sum_{\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{k}\right) \in \mathcal{C}}\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{k}\right\|_{\mathbf{M}}^{2} \geqslant 1} \\\\ {} & {\mathbf{M} \succeq 0} \end{array}$$