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 判別與類別散佈 利用標籤選取投影方向。 奇異值分解與主成分 解釋譜降秩，而 經典與非度量多維尺度分析 從成對關係建立座標。 課程閱讀書目集中列出課程使用的書籍。