2.5 度量学习与随机投影

降维既可以有目的地改变几何，也可以近似保留已有几何。度量学习利用相似性 信息判断哪些方向更重要；随机投影通过独立抽取的映射，保留固定有限点集 中的距离。两种方法都使用线性映射，但假设和成功标准并不相同。将映射表示 为矩阵，有助于明确这些差别。

动机

欧氏距离把各坐标差的平方以同样权重相加。当测量单位不同，或者有些特征 有利于分类、有些却与任务无关时，这种选择会改变近邻关系。学得的几何可以 缩放方向、组合相关特征，并忽略任务不需要的变化。

随机投影提出另一个问题：原有欧氏几何已适用，但每个点可能包含数千个 坐标。能否用更短的表示，仍让给定物体之间的距离接近原值？所要求的准确性 针对有限多个成对差向量，而不是整个原空间上的可逆变换。这一区别使显著 降低维数成为可能。

定义

定义

Mahalanobis 几何与平方距离

给定对称半正定矩阵 $M\in\mathbb R^{d\times d}$，定义

$$d_M(x,y)=\sqrt{(x-y)^TM(x-y)},\qquad \Delta_{ij}(M)=d_M(x_i,x_j)^2.$$

如果 $M=L^TL$，其中 $L\in\mathbb R^{r\times d}$，则

$$d_M(x,y)=\|Lx-Ly\|_2.$$

平方形式 $\Delta_{ij}$ 方便进行优化；具有三角不等式的对象，则是保留 平方根的距离 $d_M$。

对 $M$ 进行谱分解，取正特征值的平方根及对应特征向量，就能构造 $L$。 最少需要 $r=\operatorname{rank}(M)$ 行。因此，一个低秩学习矩阵既规定了 距离几何，也给出了更少坐标的表示。

命题

半正定产生伪度量，正定产生度量

对于 $M\succeq0$，$d_M$ 是伪度量：非负、对称、相同点之间为零，并满足 三角不等式。它在整个 $\mathbb R^d$ 上构成度量，当且仅当 $M\succ0$。

当 $M$ 奇异时，不同点距离为零，当且仅当它们的差向量属于 $\ker(M)=\ker(L)$。

线性表示给出直接证明。由欧氏范数的三角不等式，

$$\|L(x-z)\|_2 \le\|L(x-y)\|_2+\|L(y-z)\|_2.$$

此外，$(x-y)^TM(x-y)=\|L(x-y)\|_2^2$ 为零，恰好对应 $L(x-y)=0$。 正定矩阵没有非零核方向，奇异半正定矩阵则有。对于特定有限点集，只要 不同点的差都没有落进这个核，奇异矩阵仍可以分开所有物体。全空间可逆与 分开观测点，是两项不同的要求。

根据带标签的近邻学习

为每个锚点 $x_i$ 选择固定的同类目标近邻集合 $T_i$，排除锚点自身。 令 $\mathcal I_i$ 为异类点的指标集合，并取 $\lambda\ge0$。一种大间隔 最近邻目标是

$$F(M)=\sum_i\sum_{j\in T_i}\Delta_{ij}(M) +\lambda\sum_i\sum_{j\in T_i}\sum_{\ell\in\mathcal I_i} [1+\Delta_{ij}(M)-\Delta_{i\ell}(M)]_+, \qquad M\succeq0,$$

其中 $[a]_+=\max(a,0)$。第一项拉近目标近邻；铰链项惩罚未达到间隔的 异类点。异类平方距离应至少比目标平方距离大一，因此这里的间隔比较平方 距离，而不是普通长度差。

记 $v_{ij}=x_i-x_j$，$A_{ij}=v_{ij}v_{ij}^T$，则

$$\Delta_{ij}(M)=\operatorname{tr}(MA_{ij}).$$

该式对矩阵 $M$ 是线性的。固定目标近邻后，每个铰链项都是零与一个仿射 函数的最大值，因而是凸函数。求和保持凸性，半正定条件又给出凸可行集， 所以这个矩阵变量下的学习问题是凸的。

等价地，可以为每个三元组引入松弛变量，要求 $\xi_{ij\ell}\ge0$，以及 $\xi_{ij\ell}\ge1+\Delta_{ij}(M)-\Delta_{i\ell}(M)$，再最小化拉近项与 $\lambda\sum\xi_{ij\ell}$ 之和。这些不等式对矩阵和松弛变量都是仿射的。 论证要求近邻集合固定；更新近邻会改变进入目标的项。

秩与优化变量的选择

半正定约束并不保证得到低秩矩阵。直接限制 $\operatorname{rank}(M)\le r$， 通常使可行集成为非凸集合。也可以优化 $L\in\mathbb R^{r\times d}$，设 $M=L^TL$，自动满足秩上限；但目标作为 $L$ 的函数一般是非凸的。 同一种距离的等价参数表示，不一定产生等价的凸优化问题。下文会用标量 因子直接检验这一点。

理解学得的几何

对角矩阵分别加权每个坐标差。完整矩阵还包含交叉项：

$$v^TMv=\sum_a M_{aa}v_a^2+2\sum_{a<b}M_{ab}v_av_b.$$

交叉项能够描述坐标组合。例如 $(v_1-v_2)^2$ 衡量两坐标之差的变化，忽略 两者共同等量变化。对应矩阵可以有负的非对角元素，同时仍然半正定。 特征向量给出被测量的方向，特征值指定平方距离权重。结合两者解读，比 只看对角元素更能说明学习结果。

坐标单位的改变也可以明确处理。若 $z=Sx$ 且 $S$ 可逆，同一几何在新坐标中 使用矩阵

$$M_z=S^{-T}M_xS^{-1}.$$

代入即可验证二次差值不变。该合同变换还保持半正定性和秩。如果只改变输入 尺度而保持矩阵不动，就改变了待拟合几何。因此特征表示和学习矩阵应当 放在一起解释。

拉近项与推远项也影响尺度。当 $M=0$，所有点重合，拉近项为零，但每个 铰链项等于一。若 $\lambda=0$，该重合解就是最优解；正的推远权重则把 间隔代价引入目标，与目标近邻的距离相权衡。间隔常数一固定了平方距离 尺度，所以缩放 $M$ 通常会改变目标。对因子的行进行正交旋转则不同， 它保留 $L^TL$ 及所有学得距离。

高斯随机投影

先固定数据点，使其与随机映射独立。抽取矩阵 $R\in\mathbb R^{k\times d}$， 要求所有元素独立，且

$$R_{ab}\sim\mathcal N(0,1/k),\qquad f(x)=Rx.$$

方差为 $1/k$，因此生成元素时使用的标准差是 $1/\sqrt{k}$。各行不必正交。 对于固定非零差向量 $v$，行独立性给出

$$(Rv)_a\sim\mathcal N(0,\|v\|_2^2/k),\qquad \frac{k\|Rv\|_2^2}{\|v\|_2^2}\sim\chi_k^2.$$

所以 $\mathbb E\|Rv\|_2^2=\|v\|_2^2$。这一期望等式描述对固定差向量 反复抽取映射的平均结果，并不说明某一次抽取会精确保留距离。

自由度为 $k$ 的卡方变量方差是 $2k$，所以归一化平方长度比的方差为 $2/k$，初步说明投影维数增加时的集中趋势。下面的指数界更强，可以让 同时控制越来越多差向量的维数，仅依赖点数的对数。

定理

固定有限点集的同时投影界

设 $0<\varepsilon<1$、$0<\delta<1$，$n\ge2$ 个固定点与 $R$ 独立，定义

$$c_\varepsilon=\frac{\varepsilon^2}{4}-\frac{\varepsilon^3}{6}, \qquad N=\frac{n(n-1)}2.$$

至少有一对违反

$$(1-\varepsilon)\|x_i-x_j\|_2^2 \le\|R(x_i-x_j)\|_2^2 \le(1+\varepsilon)\|x_i-x_j\|_2^2$$

的概率至多为 $2N\exp(-kc_\varepsilon)$。特别地，一个充分的维数选择为

$$k\ge\left\lceil\frac{\log(2N/\delta)}{c_\varepsilon}\right\rceil$$

此时全部成对界同时成立的概率至少为 $1-\delta$。这里 $\log$ 表示自然对数。

该界使用平方长度；相应普通长度处于原长的 $\sqrt{1-\varepsilon}$ 与 $\sqrt{1+\varepsilon}$ 倍之间。零差向量经过任意线性映射仍为零，无须进行 概率估计。

从单个差向量到全部配对

证明

卡方集中与并集界

对于 $Z\sim\chi_k^2$，矩母函数是 $\mathbb E e^{tZ}=(1-2t)^{-k/2}$，其中 $t<1/2$。利用指数 Markov 不等式并 选择最优 $t$，得到

$$\Pr(Z\ge k(1+\varepsilon)) \le e^{-k(\varepsilon-\log(1+\varepsilon))/2}, \qquad \Pr(Z\le k(1-\varepsilon)) \le e^{-k(-\varepsilon-\log(1-\varepsilon))/2}.$$

在 $[0,\varepsilon]$ 上积分 $t/(1+t)\ge t-t^2$ 与 $t/(1-t)\ge t$，可得

$$\varepsilon-\log(1+\varepsilon) \ge\varepsilon^2/2-\varepsilon^3/3, \qquad -\varepsilon-\log(1-\varepsilon)\ge\varepsilon^2/2.$$

两端尾概率均不超过 $e^{-kc_\varepsilon}$，因此一个非零差向量的双尾界是 $2e^{-kc_\varepsilon}$。将其应用于至多 $N$ 个无序配对，再将失败概率相加。 并集界不要求这些事件独立。求解 $2Ne^{-kc_\varepsilon}\le\delta$，就得到 定理中的充分维数。

由于 $c_\varepsilon\ge\varepsilon^2/12$，充分维数具有 $\varepsilon^{-2}(\log n+\log(1/\delta))$ 的量级，表达式中没有原维数 $d$。 固定一个小于一的失败概率，就有正概率抽到成功映射，也就证明合适映射 存在。这是 Johnson–Lindenstrauss 的存在性结论。显式概率界还进一步说明， 重新抽取一个高斯映射有多大机会成功。

如果充分维数大于 $d$，该估计不能为这组参数认证降维效果，也不能证明所有 更低维表示都必须失败。它的作用是针对给定有限点集，为指定构造提供 同时保证。

例题

例题

例题一：核方向使不同点重合

取

$$L=\begin{bmatrix}1&-1\end{bmatrix},\qquad M=L^TL=\begin{bmatrix}1&-1\\-1&1\end{bmatrix}.$$

特征值为 $2$ 与 $0$，学得表示只有一个坐标。点 $(0,0)$、$(1,1)$ 都映射为 零，因而学得距离为零。点 $(1,0)$ 映射为一，与前两点的距离都为一。 这些值满足伪度量性质，同时把 $(1,1)$ 方向的变化识别为无需区分的变化。

加上单位矩阵得到

$$M+I_2=\begin{bmatrix}2&-1\\-1&2\end{bmatrix},$$

其特征值为 $3$ 和 $1$，因此在整个平面上定义度量。原先重合的点现在 相距 $\sqrt2$。新增正方向恢复了该方向上的区分能力，矩阵也成为满秩。 这改变了所选几何，而不仅是更换坐标记法。

例题

例题二：凸矩阵目标与非凸因子目标

只考虑一个位于 $0$ 的锚点、位于 $1$ 的同类目标和位于 $2$ 的异类点。 令一维矩阵 $M=[m]$，$m\ge0$，并取 $\lambda=1$。单锚点目标为

$$F(m)=m+[1+m-4m]_+ =\begin{cases}1-2m,&0\le m\le1/3,\\m,&m\ge1/3.\end{cases}$$

斜率从 $-2$ 增加到 $1$，函数因而凸。它在 $m=1/3$ 处取得最小值 $1/3$。 此时异类平方距离超过目标平方距离 $4m-m=1$，正好满足间隔要求。

改用因子 $m=\ell^2$，目标成为 $F(\ell^2)=\ell^2+[1-3\ell^2]_+$。在 $\ell=\pm1/\sqrt3$ 处，目标值都是 $1/3$；两点中点 $\ell=0$ 的目标值却是 $1$，违反凸函数的中点不等式。 因子参数化保证非负性，却使因子变量下的目标失去凸性。高维低秩参数化 同样需要区分这两个优化问题。

例题

例题三：按明确失败概率选择维数

令 $n=20$、原维数 $d=2000$、平方距离容差 $\varepsilon=1/2$，并要求失败 概率至多为 $\delta=1/10$。则

$$N=190,\qquad c_\varepsilon=\frac1{24},\qquad k=\lceil24\log(3800)\rceil=198.$$

失败概率界为 $380e^{-198/24}\approx0.099278<0.1$。因此，重新抽取投影到 $198$ 维的高斯映射，至少有 $0.9$ 的概率同时满足所有配对界。这只要求 给定二十点的距离准确，并不要求 $\mathbb R^{2000}$ 中每个方向都保持长度。

事实上，$198\times2000$ 矩阵必有非平凡核，诱导的 $R^TR$ 奇异，在整个 空间上只能定义伪度量。但有限集的所有成对差向量仍可避开被压缩为零的 方向。因此低秩映射与给定有限集上的准确距离并不冲突。

可复现的投影实验

下面先生成数据，再将数据固定后抽取投影。点按行存放，所以变换后的表是 $XR^T$。给定种子下，平方距离比的最小与最大值约为 $0.715409$、 $1.305531$，处于所需区间 $[0.5,1.5]$ 内。

import numpy as np

n, d, epsilon, delta = 20, 2000, 0.5, 0.1
pairs = n * (n - 1) // 2
c = epsilon**2 / 4 - epsilon**3 / 6
k = int(np.ceil(np.log(2 * pairs / delta) / c))
rng = np.random.default_rng(2026)
X = rng.normal(size=(n, d))
R = rng.normal(size=(k, d)) / np.sqrt(k)
Y = X @ R.T
i, j = np.triu_indices(n, k=1)
original = np.sum((X[i] - X[j])**2, axis=1)
projected = np.sum((Y[i] - Y[j])**2, axis=1)
ratios = projected / original
print(k)
print(np.round([ratios.min(), ratios.max()], 6))

实验检验一次抽样映射上的全部 $190$ 对距离。概率定理则在数据固定的条件 下，描述反复抽取映射的结果；这里的输出记录一次具体实现。两类证据分别 回答有关这一构造的不同问题。

常见错误

常见错误

区分对象及其概率保证

半正定矩阵可能压掉非零差向量；如果要求整个空间上的度量，就需要正定。 平方距离对 $M$ 线性，却通常没有三角不等式：数轴上 $0$ 到 $2$ 的平方 距离为 $4$，大于经过点 $1$ 的两段平方距离之和 $1+1$。

随机投影具有正确的期望平方长度，不等于同时高概率保证。集中控制一个固定 差向量，再由并集界控制有限集合。观察 $R$ 后才从其核中选一个新差向量， 不满足固定点集的假设。

总结

度量学习根据任务约束拟合半正定二次型。固定近邻的 LMNN 对矩阵变量凸， 但秩约束与因子优化可能改变凸性。高斯随机投影借助 $1/k$ 方差归一化、 卡方集中和成对并集界，以明确概率保留固定有限点集的距离。

练习

思考检查

练习一：对于 $M=\operatorname{diag}(9,0)$，写出一个单行因子 $L$、一对学得距离为零的不同点，以及表示的秩。

确定被忽略的坐标方向。

思考检查

练习二：锚点到目标的差为 $(1,0)^T$，到异类点的差为 $(0,2)^T$。只有一个三元组且 $\lambda=1$，求 $M=\operatorname{diag}(2,1)$ 与 $M=\operatorname{diag}(2,0)$ 的目标值。

先求两个平方距离，再计算铰链项。

思考检查

练习三：固定差向量的范数为 $3$，高斯映射维数为 $k=50$。求 $Rv$ 单个坐标的方差、平方范数的期望，以及卡方归一化。

注意方差与标准差的区别。

思考检查

练习四：仍取 $n=20$、$\varepsilon=1/2$，改为要求 $\delta=0.01$。根据有限集界，充分的整数维数是多少？

仍有 $190$ 个配对，且 $c_\varepsilon=1/24$。

解答

解答 · 练习一解答

可取 $L=\begin{bmatrix}3&0\end{bmatrix}$。点 $(0,0)$ 与 $(0,1)$ 都映射为零。 秩为一，因此 $d_M$ 在平面上是伪度量，并有一维表示。

解答 · 练习二解答

两种情形的目标平方距离均为 $2$，异类平方距离分别为 $4$ 和 $0$。 所以目标值为 $2+[1+2-4]_+=2$ 和 $2+[1+2-0]_+=5$。第二个矩阵压掉 异类差向量的方向，增加了间隔惩罚。

解答 · 练习三解答

单个坐标方差为 $9/50$，且 $\mathbb E\|Rv\|_2^2=9$。 归一化变量 $50\|Rv\|_2^2/9$ 服从 $\chi_{50}^2$ 分布，坐标标准差为 $3/\sqrt{50}$。

解答 · 练习四解答

这个界给出的充分维数是

$$k=\lceil24\log(38000)\rceil=254.$$

它保证至少 $0.99$ 的成功概率。更高置信水平带来对 $1/\delta$ 的对数 依赖，原始维数仍然不进入这一充分估计。

相关笔记

Fisher 判别与类别散布 利用标签选择投影方向。 奇异值分解与主成分 解释谱降秩， 经典与非度量多维尺度分析 则由成对关系构造坐标。 课程阅读书目集中列出课程使用的书籍。