类比派 (Analogizers)

派系一句话：相似的输入应该有相似的输出。学习的本质，是为"相似"找到一个好的度量。

类比派 (Analogizers) 是 Pedro Domingos 在《终极算法》(The Master Algorithm) 中划分的五大机器学习派系之一。这一派的核心信条朴素却深刻——预测一个新样本时，去找历史上"长得像它"的旧样本，把它们的答案搬过来用。从最古老的 k-近邻 (k-NN, 1950s)、到 1990 年代统治理论界的支持向量机 (SVM)、再到 2020 年后席卷工业界的 CLIP / RAG 体系，类比派以"度量 + 检索"的范式贯穿了机器学习史的每一个十年。

类比派与其他派系的根本分歧在于：它不显式建模数据生成过程（与贝叶斯派对立），不抽取一般规则（与符号派对立），不依赖可微分参数化（与联结派的早期形态对立），也不依赖种群搜索（与进化派对立）。它把"学习"问题归约为"相似度"问题：给我一个好度量 $K(x, x')$，我就能预测。

派系画像 (Tribe Profile)

维度	类比派 (Analogizers)
本体论 (Ontology)	世界由具体案例 (instances) 构成；普适规律是次要的
认识论 (Epistemology)	知识 = 案例库 + 相似度度量；推理 = 检索 + 类比外推
主算法 (Master Algorithm)	支持向量机 (SVM) / 核方法 (Kernel Methods)
核心问题	如何定义"相似"？(How to measure similarity?)
评价 (Evaluator)	间隔 (margin)、对比损失 (contrastive loss)、Recall@K
优化器 (Optimizer)	二次规划 (QP) / SMO / 随机梯度下降 (SGD)
代表方法	k-NN, SVM, 核 PCA, 核岭回归, LMNN, FaceNet, SimCLR, CLIP
现代分支	度量学习 (metric learning)、对比学习 (contrastive learning)、ANN 检索、RAG
致命弱点	维度灾难、相似度本身需要先验、计算检索成本
代表人物	Vladimir Vapnik, Bernhard Schölkopf, Tomasz Aamodt, Yann LeCun (Siamese), Geoffrey Hinton (t-SNE)

主算法 (Master Equation)

类比派几乎所有方法都可以写成同一个形式——一个对训练样本相似度的加权和：

\[ \hat{y}(x) = f\!\left(\sum_{i=1}^{N} \alpha_i \, K(x, x_i)\right) \]

其中：

$K(x, x_i)$ 是相似度核 (similarity kernel)：度量新样本 $x$ 与训练样本 $x_i$ 有多像；
$\alpha_i$ 是每个训练样本对预测的贡献权重（k-NN 中是 0/1 指示器，SVM 中是对偶变量，CF 中是用户/物品偏好）；
$f$ 是输出函数（分类时取 sign / softmax，回归时取恒等）。

这个框架的统一力极强：

方法	$K(x, x_i)$	$\alpha_i$
k-NN	$\mathbb{1}[x_i \in \mathrm{kNN}(x)]$	$y_i$
Nadaraya-Watson 回归	RBF 核 $\exp(-\\|x-x_i\\|^2/2\sigma^2)$	$y_i / \sum_j K_j$
SVM	任意 Mercer 核	拉格朗日乘子 $\alpha_i y_i$（仅支持向量非零）
核岭回归	任意 Mercer 核	$(K + \lambda I)^{-1} y$
协同过滤	用户相似度 $\mathrm{sim}(u, u_i)$	$r_{u_i, j}$（其他用户对物品 $j$ 的评分）
RAG	$\cos(\mathbf{e}_q, \mathbf{e}_{d_i})$	LLM 上下文中检索到的文档

统一视角：从 k-NN 到 RAG，60 年的方法演化只是在回答两个问题——怎样定义 $K$（如何度量相似？），怎样定义 $\alpha$（哪些案例值得借鉴？）。

算法谱系 (Lineage)

flowchart TD
    A["k-NN (Cover & Hart 1967)"] --> B["核方法 / Parzen 窗"]
    B --> C["SVM (Boser & Vapnik 1992)"]
    C --> D["核 PCA / 核岭回归"]
    A --> E["案例推理 CBR (Aamodt 1994)"]
    A --> F["协同过滤 CF (GroupLens 1994)"]
    F --> G["矩阵分解 FunkSVD (Netflix 2006)"]
    G --> H["BPR / NCF / 双塔模型"]
    A --> I["度量学习 LMNN/ITML (2007-2009)"]
    I --> J["Siamese / Triplet (FaceNet 2015)"]
    J --> K["对比学习 SimCLR / MoCo (2020)"]
    K --> L["跨模态 CLIP (2021)"]
    L --> M["RAG / RETRO / Atlas (2022+)"]
    E --> M
    H --> N["ANN 检索 FAISS / HNSW"]
    N --> M

    style C fill:#fde68a
    style L fill:#bbf7d0
    style M fill:#bbf7d0

三条主脉：

核方法主脉：k-NN → Parzen 窗 → SVM → 核 PCA / GP，统一在 RKHS 框架下。
检索主脉：k-NN → CBR → CF → 矩阵分解 → ANN → RAG，关注"怎样高效找到相似案例"。
度量学习主脉：LMNN → Siamese → Triplet → InfoNCE → CLIP，关注"怎样让神经网络学出好的相似度"。

三条主脉在 2020 年后被统一：深度模型学 embedding（度量学习），ANN 索引存 embedding（检索），LLM 用检索结果做推理（RAG）。

现代复兴 (Modern Renaissance)

类比派曾经历两次衰落：

第一次衰落（1986 年 backprop 被重新发现后）：联结派崛起，k-NN 被视作"原始"方法。
第二次衰落（2012 AlexNet 后）：深度学习统治视觉与 NLP，SVM 几乎从主流论文消失。

但类比派从未死去，并在 2020 年后强势复兴，原因有三：

对比学习成为自监督主流：SimCLR / MoCo / DINO 用对比损失训练，本质是在大规模无标签数据上做度量学习。"学一个好 embedding"成为基础模型 (foundation model) 的核心目标。
CLIP 打通模态壁垒：用图文对比训练得到的联合 embedding，让"零样本分类"和"语义搜索"成为新范式。CLIP 是迄今最成功的类比派系统。
RAG 取代纯参数化记忆：大语言模型 (LLM) 的"知识参数化"被证明有局限（幻觉、过时、无法溯源）。RAG 把外部知识库 + 向量检索接回 LLM——这就是 1994 年 Aamodt 的 CBR 在 GPT 时代的化身。

从冷门 k-NN 到 RAG 时代：2010 年的研究生说"做 k-NN？太朴素了吧"。2025 年的研究生说"我们的 LLM agent 用 HNSW 检索 1B 文档做 in-context learning"——这是同一件事。

与站内既有页的分工

本目录下三个子页深入展开类比派的三大支柱：

最近邻与核方法：k-NN、距离度量、核技巧、SVM 完整推导、Representer 定理、GP 视角。
度量学习与对比学习：LMNN/ITML、Siamese/Triplet、InfoNCE、SimCLR/MoCo/DINO、CLIP/SigLIP。
推荐系统与现代检索：CF/MF、深度推荐、CBR、ANN 索引、RAG 工程实践。

与站内其他页协调：

../../03_Machine_Learning/supervised.md 从"监督学习算法目录"角度介绍 k-NN/SVM 的接口。本目录从派系哲学与算法谱系角度组织。
../../03_Machine_Learning/kernel_methods.md 已有核方法基础。本目录的最近邻与核方法在其上增加：Representer 定理证明、SVM 对偶推导、GP 关联、SMO 算法。
../../03_Machine_Learning/贝叶斯学习.md 中的 GP 章节与本目录的核方法节互为镜像（贝叶斯派视角 vs 类比派视角）。

子页导航

子页	核心问题	关键词
最近邻与核方法	怎样定义"相似"？怎样把相似度变成预测器？	k-NN, KD-Tree, Mercer 条件, SVM 对偶, KKT, RKHS, Representer, 核 PCA, GP
度量学习与对比学习	怎样学出好的相似度？	LMNN, Siamese, Triplet, Contrastive, InfoNCE, SimCLR, MoCo, DINO, CLIP
推荐系统与现代检索	怎样高效检索相似案例？	CF, FunkSVD, BPR, NCF, 双塔, CBR, FAISS, HNSW, RAG

参考文献

Domingos, P. (2015). The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World. Basic Books. — 五大派系框架的原始出处，第 7 章专论类比派。
Cover, T. M., & Hart, P. E. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21–27. — k-NN 的奠基性工作，证明 1-NN 错误率不超过贝叶斯错误率的两倍。
Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer. — VC 维与 SVM 理论体系。
Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. COLT. — SVM 与核技巧 (kernel trick) 的开山论文。
Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels. MIT Press. — 核方法、Representer 定理、RKHS 的标准教科书。
Aamodt, A., & Plaza, E. (1994). Case-based reasoning: Foundational issues, methodological variations, and system approaches. AI Communications, 7(1), 39–59. — CBR 4R 循环的奠基论文。
Radford, A., et al. (2021). Learning transferable visual models from natural language supervision. ICML. — CLIP，类比派现代复兴的标志性工作。
Lewis, P., et al. (2020). Retrieval-Augmented Generation for knowledge-intensive NLP tasks. NeurIPS. — RAG 论文，把检索接回参数化模型。

最近邻与核方法

本页定位：把类比派的"骨架"——从最朴素的 k-NN 到统一框架的核方法/SVM——讲完整。重点是数学推导（SVM 对偶、KKT、Representer 定理）、几何直觉（核技巧 = 隐式升维）、工程加速（KD-Tree / LSH）三条线。

类比派最古老的方法是 k-近邻 (k-NN)：预测一个新样本时，找它的 $k$ 个最近邻居，用邻居的标签投票。这个 1950 年代提出、1967 年由 Cover & Hart 证明误差界的方法，今天仍然是各种向量检索系统的基本范式。

但 k-NN 有两个致命问题：

"最近"是什么？——距离度量直接决定结果，朴素的欧氏距离在高维下崩溃。
怎样把相似度组合成"决策面"？——k-NN 的边界是逐点拼出来的，理论性质差。

核方法 (kernel methods) 与 SVM 在 1990 年代回答了这两个问题，并把"相似度学习"提升为一个有完整数学基础的范式。

1. k-近邻 (k-NN) 完整框架

1.1 算法定义

给定训练集 $\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N$，距离度量 $d$，新样本 $x$：

计算 $x$ 到所有训练点的距离 $\{d(x, x_i)\}_{i=1}^N$。
找出最近的 $k$ 个邻居 $\mathrm{kNN}(x)$。
分类：$\hat y = \mathrm{mode}\{y_i : x_i \in \mathrm{kNN}(x)\}$（多数投票）。
回归：$\hat y = \frac{1}{k}\sum_{x_i \in \mathrm{kNN}(x)} y_i$（平均）。

1.2 加权 k-NN (weighted k-NN)

朴素 k-NN 把 $k$ 个邻居一视同仁，但显然"更近的邻居"应当贡献更多。加权版本：

\[ \hat y(x) = \frac{\sum_{x_i \in \mathrm{kNN}(x)} w_i \, y_i}{\sum_{x_i \in \mathrm{kNN}(x)} w_i}, \quad w_i = \exp\!\left(-\frac{d(x, x_i)^2}{2\sigma^2}\right) \]

这就是 Nadaraya-Watson 核回归。把 $k$ 取到 $N$（用所有点，但远点权重接近 0），就得到 Parzen 窗估计——一个非参数密度估计器。注意：k-NN $\to$ Parzen 窗 $\to$ 核回归是连续过渡的，三者数学本质相同。

1.3 k 的选择

$k$ 控制偏差-方差权衡：

$k$	偏差	方差	决策面	风险
$k=1$	极低	极高	锯齿状	过拟合（对噪声敏感）
$k$ 适中	平衡	平衡	平滑	—
$k=N$	极高	极低	退化为多数类	欠拟合

实践中用交叉验证选 $k$，常用经验值 $k = \sqrt{N}$。$k$ 应取奇数（避免二分类平票）。

1.4 1-NN 的理论保证 (Cover-Hart 1967)

设贝叶斯最优错误率为 $R^*$，1-NN 在 $N \to \infty$ 时的渐近错误率 $R_{1\text{-NN}}$ 满足：

\[ R^* \leq R_{1\text{-NN}} \leq R^* (2 - R^*) \leq 2 R^* \]

一句话总结：最朴素的 1-NN 错误率最多是贝叶斯最优的两倍——这是惊人的理论保证，部分解释了为什么类比派从未真正消亡。

2. 距离度量谱系

距离度量的选择是 k-NN（以及所有类比派方法）成败的关键。

2.1 常用度量

度量	公式	适用场景
欧氏 (Euclidean)	$d(x,y) = \sqrt{\sum_i (x_i - y_i)^2}$	各维度同尺度、同语义的连续特征
曼哈顿 (Manhattan, $\ell_1$)	$\sum_i	x_i - y_i
Chebyshev ($\ell_\infty$)	$\max_i	x_i - y_i
Minkowski ($\ell_p$)	$\left(\sum_i	x_i - y_i
Mahalanobis	$\sqrt{(x-y)^T \Sigma^{-1} (x-y)}$	各维度尺度/相关性不同的场景
余弦 (Cosine)	$1 - \frac{x^T y}{\\|x\\|\\|y\\|}$	文本 TF-IDF、embedding 相似度
Hamming	$\sum_i \mathbb{1}[x_i \neq y_i]$	二元串、分类特征
编辑距离 (Levenshtein)	DP 计算的最小编辑步数	字符串、生物序列
Jaccard	$1 - \frac{	A \cap B

2.2 Mahalanobis 度量

Mahalanobis 是欧氏距离的"自适应"推广：

\[ d_M(x, y) = \sqrt{(x-y)^T M (x-y)} \]

其中 $M = L^T L$ 为半正定矩阵。当 $M = I$ 退化为欧氏；当 $M = \Sigma^{-1}$（数据协方差矩阵的逆）则修正了不同维度的尺度和相关性。度量学习就是从数据中学这个 $M$——见度量学习与对比学习。

2.3 几何陷阱：为什么余弦在 NLP 中盛行

文本/embedding 中常用余弦而非欧氏，原因是 embedding 的长度通常携带"频率/置信度"信息而非"语义"信息。归一化到单位球面（$\|x\|=1$）后，余弦距离与欧氏距离单调相关：

\[ \|x - y\|^2 = 2 - 2 \cos\theta \quad \text{(when } \|x\|=\|y\|=1\text{)} \]

所以现代深度度量学习（CLIP, SimCLR）几乎都对 embedding 做 L2 归一化后用点积。

3. 维度灾难 (Curse of Dimensionality)

核心命题：在高维空间，"最近邻"几乎失去意义——所有点之间的距离趋于相等。

3.1 体积集中现象

考虑 $d$ 维单位超立方体 $[0,1]^d$ 中的均匀分布。要取得 1% 的体积，每维边长需要：

\[ \ell = (0.01)^{1/d} \]

$d$	$\ell$（覆盖 1% 体积所需边长）
1	0.01
2	0.1
10	0.63
100	0.955
1000	0.9954

在 $d=100$ 时，要捕获 1% 的"局部"邻居就需要每维覆盖 95.5% 的范围——根本谈不上"局部"。

3.2 距离集中 (Distance Concentration)

对于 $d$ 维单位球内的 $N$ 个均匀样本，最近距离 $D_{\min}$ 与最远距离 $D_{\max}$ 之比：

\[ \lim_{d \to \infty} \frac{D_{\max} - D_{\min}}{D_{\min}} \to 0 \]

即所有点之间的距离比例趋于 1——最近邻不再"近"，最远邻不再"远"。这是 Beyer 等人 (1999) 严格证明的结果，对 k-NN 是毁灭性的。

3.3 维度灾难的破解之道

类比派对抗维度灾难的三条路径：

降维 / 流形假设：真实数据在低维流形上（图像虽然 $d$ 万维，但有效维度低）。t-SNE / UMAP / 自编码器都属于此类。
学一个度量：度量学习把数据投到"语义有意义"的低维 embedding 空间——这就是深度度量学习的全部出发点。
核技巧：SVM 的核技巧反其道而行——升维到无穷维，但只通过相似度内积访问，避免显式存储。

4. k-NN 的算法复杂度与加速

朴素 k-NN 查询单点需要 $O(Nd)$，$N$ 大时不可接受。

4.1 KD-Tree

KD-Tree (k-dimensional tree) 用轴对齐超平面递归二分空间：

构建：$O(N \log N)$，深度 $O(\log N)$；
查询：低维 ($d \lesssim 20$) 时 $O(\log N)$，高维退化为 $O(N)$；
适用：低维稠密数据。

4.2 球树 (Ball Tree)

不再轴对齐，而用嵌套超球体。比 KD-Tree 在中等维度（20–100）下更鲁棒，但构建/查询常数项更大。

4.3 LSH (Locality-Sensitive Hashing)

把"近的点"哈希到同一个桶里——牺牲精度换取大幅加速。一个 LSH 族 $\mathcal{H}$ 满足：

\[ \Pr_{h \in \mathcal{H}}[h(x) = h(y)] = f(d(x, y)), \quad f \text{ 单调递减} \]

例如对余弦距离的 SimHash：随机超平面 $r$，$h(x) = \mathrm{sign}(r^T x)$。两个向量被映到同一 bit 的概率正比于它们夹角的余弦。

LSH 是早期 ANN（近似最近邻）的代表，2010 年代被基于图的 HNSW 全面超越——见推荐系统与现代检索第 8 节。

5. 核方法的统一视角

5.1 核 = 隐式相似度

核函数 $K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ 是一个对称函数，可以理解为"相似度"。核技巧 (kernel trick) 的核心洞察是：

\[ K(x, x') = \langle \phi(x), \phi(x') \rangle_{\mathcal{H}} \]

即 $K$ 等价于先把 $x$ 映射到某个（可能无穷维的）特征空间 $\mathcal{H}$，再在那里求内积。我们永远不需要显式构造 $\phi$，只要算 $K$。

flowchart LR
    A["输入空间 X<br/>(线性不可分)"] -->|"显式映射 φ"| B["特征空间 H<br/>(线性可分)"]
    A -->|"核 K(x,x') = ⟨φ(x), φ(x')⟩<br/>(避免显式构造 φ)"| C["相似度矩阵<br/>K ∈ R^{N×N}"]
    C --> D["对偶解<br/>仅依赖 K"]
    style C fill:#fde68a
    style D fill:#bbf7d0

5.2 Mercer 条件

并非所有"相似度函数"都是合法核。Mercer 定理：$K$ 是合法核 $\iff$ 对任意 $\{x_1, \dots, x_N\}$，Gram 矩阵 / kernel matrix

\[ \mathbf{K} = \begin{bmatrix} K(x_i, x_j) \end{bmatrix}_{i,j=1}^N \]

是对称半正定 (PSD) 矩阵，即对任意 $\alpha \in \mathbb{R}^N$：

\[ \alpha^T \mathbf{K} \alpha \geq 0 \]

PSD 性是核方法所有理论的基础——它保证了对偶问题是凸的、Representer 定理成立、解唯一。

5.3 核的代数运算

合法核可以组合出新核：

$K_1 + K_2$ 是核；
$c \cdot K$（$c > 0$）是核；
$K_1 \cdot K_2$ 是核（逐点乘）；
$f(x) f(x')$ 对任意 $f$ 是核；
$K(\psi(x), \psi(x'))$ 是核。

工程上，可以为不同特征族（数值、文本、图）分别设计核，再线性组合（多核学习 MKL）。

6. 支持向量机 (SVM) 完整推导

SVM 是类比派的"主算法"，把 k-NN 从"投票"升级为"最大间隔超平面"。

6.1 硬间隔 (Hard Margin) 原问题

二分类，$y_i \in \{-1, +1\}$。寻找超平面 $w^T x + b = 0$ 把两类分开，并使间隔 (margin) 最大。点 $x_i$ 到超平面距离 $\frac{|w^T x_i + b|}{\|w\|}$。规范化使最近点满足 $|w^T x_i + b| = 1$，则间隔为 $\frac{2}{\|w\|}$。

原问题 (primal)：

\[ \begin{aligned} \min_{w, b} \quad & \tfrac{1}{2} \|w\|^2 \\ \text{s.t.} \quad & y_i (w^T x_i + b) \geq 1, \quad i=1,\dots,N \end{aligned} \]

凸二次规划，可直接解，但维度等于 $\dim(x)$，无法用核。

6.2 拉格朗日对偶

引入乘子 $\alpha_i \geq 0$，拉格朗日函数：

\[ \mathcal{L}(w, b, \alpha) = \tfrac{1}{2}\|w\|^2 - \sum_i \alpha_i \left[y_i(w^T x_i + b) - 1\right] \]

对 $w, b$ 求偏导并置零：

\[ \frac{\partial \mathcal{L}}{\partial w} = 0 \Rightarrow w = \sum_i \alpha_i y_i x_i \]

\[ \frac{\partial \mathcal{L}}{\partial b} = 0 \Rightarrow \sum_i \alpha_i y_i = 0 \]

代回得对偶问题 (dual)：

\[ \begin{aligned} \max_\alpha \quad & \sum_i \alpha_i - \tfrac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j \, \langle x_i, x_j \rangle \\ \text{s.t.} \quad & \alpha_i \geq 0, \quad \sum_i \alpha_i y_i = 0 \end{aligned} \]

关键观察：对偶问题中 $x_i$ 只以内积 $\langle x_i, x_j \rangle$ 出现——这正是核技巧的入口。把内积换成 $K(x_i, x_j)$，瞬间获得无穷维特征空间的 SVM。

6.3 KKT 条件

最优解 $(w^*, b^*, \alpha^*)$ 必须满足 Karush-Kuhn-Tucker (KKT) 条件：

平稳性：$w^* = \sum_i \alpha_i^* y_i x_i$；
原可行：$y_i({w^*}^T x_i + b^*) \geq 1$；
对偶可行：$\alpha_i^* \geq 0$；
互补松弛：$\alpha_i^* \left[y_i({w^*}^T x_i + b^*) - 1\right] = 0$。

互补松弛蕴含一个深刻结论：$\alpha_i^* > 0 \Rightarrow y_i({w^*}^T x_i + b^*) = 1$——只有恰好落在间隔边界上的点才有非零 $\alpha$。这些点称为支持向量 (support vectors)。

SVM 的解只依赖训练集的一个子集（支持向量），这是它泛化能力的根源——VC 维由支持向量数控制。

6.4 软间隔与 Hinge Loss

实际数据线性不可分。引入松弛变量 $\xi_i \geq 0$：

\[ \begin{aligned} \min_{w, b, \xi} \quad & \tfrac{1}{2} \|w\|^2 + C \sum_i \xi_i \\ \text{s.t.} \quad & y_i (w^T x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0 \end{aligned} \]

$C$ 是正则化参数：$C \to \infty$ 退化为硬间隔；$C$ 小则容忍更多违例。等价的无约束形式：

\[ \min_{w, b} \tfrac{1}{2} \|w\|^2 + C \sum_i \max\left(0, 1 - y_i(w^T x_i + b)\right) \]

第二项是 hinge loss——SVM 的损失函数。

软间隔的对偶问题与硬间隔几乎相同，仅约束变为 $0 \leq \alpha_i \leq C$（箱式约束 box constraint）。

6.5 核 SVM 决策函数

学到 $\alpha^*$ 后，对新样本 $x$ 的预测：

\[ \hat y(x) = \mathrm{sign}\!\left(\sum_{i \in \mathrm{SV}} \alpha_i^* y_i \, K(x_i, x) + b^*\right) \]

完美匹配类比派主算法 $\hat y = f(\sum_i \alpha_i K(x, x_i))$ 的形式。

6.6 SMO 算法

求解 SVM 对偶问题的标准做法是 Sequential Minimal Optimization (SMO, Platt 1998)：

SMO 主循环：
  while 未收敛:
    选一对违反 KKT 的乘子 (α_i, α_j)
    固定其他乘子，把对偶问题化为对 (α_i, α_j) 的 2 维 QP
    解析解（一维 QP，闭式）
  end

SMO 的精妙在于：每次只优化两个变量（必须两个，因为约束 $\sum_i \alpha_i y_i = 0$），把 $N$ 维 QP 拆成大量 2 维子问题。LibSVM 就是 SMO 的高效实现。

7. 核函数动物园

核	公式	参数	适用场景
线性 (Linear)	$K(x,y) = x^T y$	—	高维稀疏文本（TF-IDF）
多项式 (Polynomial)	$(x^T y + c)^d$	$c, d$	特征交互（NLP 中的 N-gram-like）
RBF / Gaussian	$\exp(-\gamma \\|x-y\\|^2)$	$\gamma$	通用默认核；无穷维特征空间
Laplacian	$\exp(-\gamma \\|x-y\\|_1)$	$\gamma$	比 RBF 对离群更鲁棒
Sigmoid	$\tanh(\kappa x^T y + c)$	$\kappa, c$	历史上模拟两层网络（不严格 PSD）
字符串核 (String)	共同子串数	$k$ (子串长)	文本分类、生物序列
图核 (Graph)	随机游走/子图计数	—	化学分子、社交图
Fisher 核	$\nabla_\theta \log p(x	\theta)^T I^{-1} \nabla_\theta \log p(y	\theta)$

默认选择：表格特征 → RBF；文本 → 线性 + 高维特征；结构化对象 → 字符串/图核；不知道 → RBF + 网格搜索 $(\gamma, C)$。

8. 核 PCA 与核岭回归

8.1 核 PCA

PCA 是在原空间找最大方差方向；核 PCA 是在 $\phi$ 映射后的特征空间做 PCA。具体地，求中心化后的核矩阵 $\tilde{\mathbf{K}}$ 的特征向量：

\[ \tilde{\mathbf{K}} \alpha = \lambda N \alpha \]

第 $k$ 主成分对应特征向量 $\alpha^{(k)}$，新样本 $x$ 的第 $k$ 主成分坐标：

\[ \mathrm{PC}_k(x) = \sum_{i=1}^N \alpha^{(k)}_i \, K(x_i, x) \]

意义：在原空间非线性的流形结构，在 $\phi$ 空间可能线性可分——核 PCA 提取了非线性主成分。

8.2 核岭回归 (Kernel Ridge Regression)

岭回归 $\min_w \|y - Xw\|^2 + \lambda \|w\|^2$ 的核化版本闭式解：

\[ \hat y(x) = \sum_i \alpha_i K(x_i, x), \quad \alpha = (\mathbf{K} + \lambda I)^{-1} y \]

完美呈现类比派主算法形式。与 GP 回归的关系：核岭回归的预测均值与 GP 回归后验均值在数学上完全相同——见第 10 节。

9. Representer 定理

Representer 定理 (Schölkopf, Herbrich & Smola 2001)：在再生核希尔伯特空间 (RKHS) $\mathcal{H}_K$ 中求解的正则化经验风险最小化问题，最优解一定可以表示为训练样本核函数的线性组合。

形式化：考虑

\[ \min_{f \in \mathcal{H}_K} \;\; \sum_{i=1}^N L(y_i, f(x_i)) + \Omega(\|f\|_{\mathcal{H}_K}) \]

其中 $L$ 是任意损失，$\Omega$ 是单调递增正则项。则最优解必形如：

\[ f^*(x) = \sum_{i=1}^{N} \alpha_i \, K(x_i, x) \]

证明草图：把任意 $f \in \mathcal{H}_K$ 分解为 $f = f_\parallel + f_\perp$，其中 $f_\parallel \in \mathrm{span}\{K(\cdot, x_i)\}$，$f_\perp$ 与之正交。由再生性 $f(x_i) = \langle f, K(\cdot, x_i) \rangle = f_\parallel(x_i)$，所以 $f_\perp$ 不影响损失项；但 $\|f\|^2 = \|f_\parallel\|^2 + \|f_\perp\|^2 \geq \|f_\parallel\|^2$，所以 $f_\perp = 0$ 时正则项最小。$\square$

意义：

理论基础：把无限维优化问题归约为 $N$ 维 $\alpha$ 的有限优化；
算法统一：SVM、核岭回归、核 logistic 回归、GP——所有的解都形如 $\sum_i \alpha_i K(x_i, \cdot)$，差别仅在 $\alpha$ 怎样确定；
类比派合法性：从理论上说明"用训练样本相似度的加权和做预测"是所有 RKHS 方法的本质形式，而不是巧合。

10. 高斯过程作为核方法

高斯过程 (Gaussian Process, GP) 是贝叶斯派的回归方法，但它本质上是核方法。一个 GP 完全由均值函数 $m(x)$ 和协方差核 $K(x, x')$ 定义：

\[ f(x) \sim \mathcal{GP}(m(x), K(x, x')) \]

观测 $\mathbf{y} = f(\mathbf{X}) + \epsilon$（高斯噪声 $\epsilon \sim \mathcal{N}(0, \sigma^2 I)$）后，对新点 $x_*$ 的后验：

\[ \mathbb{E}[f(x_*) \mid \mathbf{X}, \mathbf{y}] = \mathbf{k}_*^T (\mathbf{K} + \sigma^2 I)^{-1} \mathbf{y} \]

\[ \mathrm{Var}[f(x_*) \mid \mathbf{X}, \mathbf{y}] = K(x_*, x_*) - \mathbf{k}_*^T (\mathbf{K} + \sigma^2 I)^{-1} \mathbf{k}_* \]

其中 $\mathbf{k}_* = [K(x_*, x_i)]_{i=1}^N$，$\mathbf{K}$ 是训练点核矩阵。

关键观察：后验均值

\[ \mathbb{E}[f(x_*) \mid \cdot] = \sum_i \alpha_i K(x_*, x_i), \quad \alpha = (\mathbf{K} + \sigma^2 I)^{-1} \mathbf{y} \]

与核岭回归的解形式完全一致（设 $\sigma^2 = \lambda$）。GP 与核岭回归的差异仅在：GP 还给出预测方差（不确定性量化），而核岭回归只给点估计。

派系视角：贝叶斯派看 GP 是"函数上的先验"；类比派看 GP 是"用训练点核相似度加权预测的非参方法"。两个视角等价，但叙事不同——这就是 ../../03_Machine_Learning/贝叶斯学习.md 中 GP 节与本节互为镜像的原因。

11. 与 [../../03_Machine_Learning/kernel_methods.md] 的分工

../../03_Machine_Learning/kernel_methods.md 已经介绍了核方法的基础概念（什么是核、核技巧的直觉、常见核函数）。本页不重复那些内容，而是深化：

主题	03_Machine_Learning/kernel_methods.md	本页
核技巧概念	介绍	假设已知，直接用
Mercer 条件	提及	PSD 性质 + 核运算代数
SVM 推导	简要叙述	完整原问题 + 对偶 + KKT + SMO
Representer 定理	—	完整陈述与证明草图
GP 与核方法关系	—	显式推导后验均值与核岭回归的等价性
维度灾难	—	完整数学分析（体积、距离集中）
算法工程	—	KD-Tree / LSH / SMO 实现概述

简言之：那一页是"核方法是什么"，这一页是"核方法为什么是类比派的主算法，以及它的全部数学骨架"。

代码示例：用 scikit-learn 把上述方法跑一遍

import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import SVC
from sklearn.kernel_ridge import KernelRidge
from sklearn.decomposition import KernelPCA

X, y = make_moons(n_samples=500, noise=0.2, random_state=42)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0)

# 1) k-NN
knn = KNeighborsClassifier(n_neighbors=5, weights="distance").fit(X_tr, y_tr)

# 2) RBF-SVM (类比派主算法)
svm = SVC(kernel="rbf", C=1.0, gamma="scale").fit(X_tr, y_tr)
print("支持向量数 / 训练样本数:", len(svm.support_), "/", len(X_tr))

# 3) 核岭回归 (回归形式的类比派)
krr = KernelRidge(alpha=0.1, kernel="rbf", gamma=1.0).fit(X_tr, y_tr)

# 4) 核 PCA (非线性降维)
kpca = KernelPCA(n_components=2, kernel="rbf", gamma=1.0).fit(X_tr)
Z = kpca.transform(X_te)

print("k-NN acc:", knn.score(X_te, y_te))
print("SVM acc:", svm.score(X_te, y_te))

交叉引用

类比派整体框架：本页 §1（派系入口）
站内核方法基础页：../../03_Machine_Learning/kernel_methods.md
监督学习算法目录（k-NN/SVM 接口）：../../03_Machine_Learning/supervised.md
贝叶斯派的 GP 视角：../../03_Machine_Learning/贝叶斯学习.md
度量怎样学出来：度量学习与对比学习
怎样高效检索相似样本：推荐系统与现代检索

参考文献

Cover, T. M., & Hart, P. E. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 21–27. — k-NN 的奠基论文与 1-NN 误差界。
Boser, B. E., Guyon, I. M., & Vapnik, V. N. (1992). A training algorithm for optimal margin classifiers. COLT. — SVM 与 kernel trick。
Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273–297. — 软间隔 SVM。
Platt, J. (1998). Sequential Minimal Optimization: A fast algorithm for training support vector machines. Microsoft Research TR. — SMO 算法。
Schölkopf, B., Herbrich, R., & Smola, A. J. (2001). A generalized representer theorem. COLT. — Representer 定理的现代陈述与证明。
Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels. MIT Press. — 核方法的标准教科书。
Rasmussen, C. E., & Williams, C. K. I. (2006). Gaussian Processes for Machine Learning. MIT Press. — GP 的标准教科书；与核方法的关系在第 6 章。
Beyer, K., et al. (1999). When is "nearest neighbor" meaningful? ICDT. — 距离集中现象的严格证明。
Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. CACM. — KD-Tree 原始论文。
Indyk, P., & Motwani, R. (1998). Approximate nearest neighbors: towards removing the curse of dimensionality. STOC. — LSH 奠基。

度量学习与对比学习

本页定位：把"相似度怎样学出来"讲透。从 2000 年代的浅层度量学习 (LMNN/ITML) 一路讲到 2020 年代的对比学习 (SimCLR/MoCo/BYOL/DINO) 与跨模态 CLIP——这是类比派在深度学习时代的复兴史。

最近邻与核方法解决了"给定相似度，怎样做预测"的问题。但更根本的问题是——相似度本身从哪里来？

朴素的欧氏距离在原始像素空间几乎没有语义意义：把同一张猫的图片平移 1 个像素，欧氏距离就比"猫 vs 狗"还远。要让"相似的输入有相似的输出"，必须学一个 embedding，让相似的输入在 embedding 空间真正靠近。

这就是度量学习 (metric learning) 的全部使命。当度量学习与深度网络结合，并放大到无标签数据，就成为 2020 年代基础模型的训练范式——对比学习 (contrastive learning)。

1. 度量学习的目标

形式化：找一个 embedding 函数 $f_\theta: \mathcal{X} \to \mathbb{R}^d$，使得对于任意"相似对" $(x, x^+)$ 和"不相似对" $(x, x^-)$：

\[ d(f_\theta(x), f_\theta(x^+)) < d(f_\theta(x), f_\theta(x^-)) \]

这里 $d$ 通常是欧氏距离或余弦距离。关键问题：

谁定义"相似"？——监督学习中由标签定义（同类相似），自监督中由数据增强定义（同张图的不同增强相似）。
怎样训练？——把"相似度排序约束"转化为可微损失函数。
embedding 空间的几何？——欧氏 / 球面 / 双曲。

2. 经典度量学习

2.1 Mahalanobis 度量学习

学一个半正定矩阵 $M = L^T L$，使

\[ d_M(x, y) = \sqrt{(x-y)^T M (x-y)} = \|L(x-y)\|_2 \]

成为对任务有意义的度量。注意 $L$ 等价于一个线性 embedding——所以 Mahalanobis 度量学习就是"学线性 embedding 后用欧氏距离"。

2.2 LMNN (Large Margin Nearest Neighbor, Weinberger & Saul 2009)

LMNN 直接为 k-NN 优化度量，目标是让每个点的"目标邻居"（同类）比"冒充者"（不同类）至少近一个间隔：

\[ \min_M \;\; \underbrace{\sum_{i,j \rightsquigarrow i} d_M(x_i, x_j)^2}_{\text{拉近同类}} + C \underbrace{\sum_{i,j \rightsquigarrow i, l} \left[1 + d_M(x_i, x_j)^2 - d_M(x_i, x_l)^2\right]_+ (1 - y_{il})}_{\text{推远不同类}} \]

其中 $j \rightsquigarrow i$ 表示 $j$ 是 $i$ 的预选目标邻居（同类中的 k 近邻），$l$ 遍历所有点。$M$ 必须保持 PSD（半正定锥投影）。

贡献：把 SVM 的"间隔"思想引入度量学习；可与核技巧结合。

2.3 ITML (Information-Theoretic Metric Learning, Davis et al. 2007)

用 KL 散度衡量度量距先验度量的偏离：

\[ \min_M \;\; D_{\mathrm{KL}}(\mathcal{N}(0, M^{-1}) \| \mathcal{N}(0, M_0^{-1})) \quad \text{s.t. 相似/不相似对约束} \]

求解形式特别简洁：Bregman 投影迭代。优势：参数化在 PSD 锥内自然，避免显式投影。

2.4 浅层度量学习的局限

LMNN/ITML 都假设线性变换够用——但图像/文本的语义相似显然是高度非线性的。把这两类方法换上深度网络，就成为下一节的 Siamese / Triplet。

3. 深度度量学习架构

3.1 Siamese 网络 (孪生网络)

Bromley, LeCun 1993 提出，2014 年后大爆发。两个共享参数的子网络分别处理两个输入，比较 embedding：

flowchart LR
    X1["x₁"] --> F1["fθ"]
    X2["x₂"] --> F2["fθ (共享权重)"]
    F1 --> Z1["z₁"]
    F2 --> Z2["z₂"]
    Z1 & Z2 --> D["d(z₁, z₂)"]
    D --> L["对比损失"]
    style F1 fill:#fde68a
    style F2 fill:#fde68a

应用：人脸验证（DeepFace, FaceNet）、签名验证、低样本分类（深化 ../../../1_DeepLearning/Computer_Vision/meta_learning.md 中的 Siamese 节）。

3.2 Triplet 网络 (FaceNet, Schroff et al. 2015)

三输入：anchor $a$、positive $p$（与 $a$ 同类）、negative $n$（与 $a$ 不同类）。损失推 $a$ 比 $n$ 更近 $p$ 至少一个间隔 $m$：

\[ L_{\mathrm{triplet}} = \max\left(0, \; \|f(a) - f(p)\|^2 - \|f(a) - f(n)\|^2 + m\right) \]

FaceNet 的实践：

L2 归一化 embedding 到单位球面（128 维）；
在 LFW 上人脸验证准确率 99.63%。

3.3 难样本挖掘 (Hard Negative Mining)

Triplet 训练的核心难题：随机选 negative 大部分已经满足约束（loss = 0），梯度无效。需要选难负例（最接近 anchor 的 negative）：

策略	描述	风险
Random	随机选 negative	训练不动
Semi-hard	选 $\\|f(a)-f(n)\\| > \\|f(a)-f(p)\\|$ 但仍违例	FaceNet 默认
Hardest	选 batch 内最近的 negative	容易塌缩到平凡解
Online (within batch)	在 mini-batch 内现算挖掘	高效，主流

4. 损失函数谱系

度量学习的损失函数演化是一条主线，每一代都在解决前一代的问题。

4.1 Contrastive Loss (Hadsell, Chopra & LeCun 2006)

最早的深度对比损失。给定一对样本 $(x_1, x_2)$ 与"是否相似"标签 $y \in \{0, 1\}$（0 = 相似，1 = 不相似）：

\[ L_{\mathrm{contrastive}} = (1 - y) \cdot D^2 + y \cdot \max(0, m - D)^2 \]

其中 $D = \|f(x_1) - f(x_2)\|$，$m$ 是间隔。直觉：

相似对（$y=0$）→ 拉近距离平方；
不相似对（$y=1$）→ 推开到至少 $m$ 之外。

4.2 Triplet Loss

见上节，把 contrastive 的"对"扩展为"三元组"，自动平衡正负。

4.3 Quadruplet / N-pair / Lifted Structure

损失	形式	改进点
Quadruplet (Chen 2017)	一个 anchor + 一个 positive + 两个 negatives，要求负负之间也分开	类间间距更大
N-pair (Sohn 2016)	一个 anchor + 一个 positive + (N-1) 个 negatives，softmax	单 mini-batch 利用率高
Lifted Structure (Oh Song 2016)	整个 batch 内所有正对、所有负对联合优化	全局结构
Angular Loss (Wang 2017)	三角形内角约束，对尺度不敏感	几何更直观

4.4 InfoNCE / NT-Xent: 现代对比学习的核心损失

InfoNCE (van den Oord et al. 2018) 把对比学习与互信息估计联系起来，NT-Xent (Normalized Temperature-scaled Cross Entropy, Chen et al. SimCLR 2020) 是其在自监督视觉中的标准形式。

设 batch 中有 $N$ 个原始样本，每个生成 2 个增强视图，共 $2N$ 个样本。视图 $i$ 与其配对正样本 $j$ 的损失：

\[ L_{i,j}^{\mathrm{NT\text{-}Xent}} = -\log \frac{\exp(\mathrm{sim}(z_i, z_j) / \tau)}{\sum_{k=1}^{2N} \mathbb{1}_{[k \neq i]} \exp(\mathrm{sim}(z_i, z_k) / \tau)} \]

其中 $\mathrm{sim}(u, v) = \frac{u^T v}{\|u\|\|v\|}$（余弦相似度），$\tau > 0$ 是温度。整个 batch 的损失是所有 $(i, j)$ 对的平均。

4.4.1 推导：与互信息下界的关系

InfoNCE 是互信息 $I(X; Y)$ 的一个下界估计：

\[ I(X; Y) \geq \log K - L_{\mathrm{InfoNCE}} \]

其中 $K$ 是 negative 数量。这给对比学习一个信息论解释：最大化对比性能 = 最大化两个视图之间的互信息。但这个下界很松——理论与实践的关系仍有争论 (Tschannen 2020)。

4.4.2 温度 τ 的作用

温度 $\tau$ 控制 softmax 的"锐度"：

$\tau$	行为	效果
极小 ($\tau \to 0$)	softmax 变 argmax	只关注最难负例（hardest negative），训练不稳
极大 ($\tau \to \infty$)	softmax 趋均匀	所有负例等权，几乎没有学习信号
适中 ($\tau \approx 0.05 \sim 0.5$)	平衡	SimCLR 默认 0.5；MoCo 默认 0.07；CLIP 学习温度

经验：温度过小是早期训练崩塌的常见原因。CLIP 把 $\log \tau^{-1}$ 设为可学习参数，初值 $\log 14$，并 clip 到 $\log 100$ 防止过小。

4.4.3 SupCon: 监督对比损失

把 NT-Xent 扩展到有标签场景 (Khosla et al. 2020)：把同类的所有样本都视为 positive：

\[ L_{\mathrm{SupCon}}_i = -\frac{1}{|P(i)|} \sum_{p \in P(i)} \log \frac{\exp(z_i \cdot z_p / \tau)}{\sum_{a \neq i} \exp(z_i \cdot z_a / \tau)} \]

其中 $P(i)$ 是与 $i$ 同类的样本集合。SupCon 在监督分类上常优于 cross-entropy。

5. 自监督对比学习

跨页深化：../../../1_DeepLearning/Computer_Vision/视觉自监督.md 已经介绍自监督学习的整体范式。本节聚焦对比学习路线的内部演化与算法细节。

5.1 SimCLR (Chen et al. 2020)

第一个把对比学习真正"做大"的工作。核心组件：

数据增强组合：随机裁剪 + 颜色抖动 + 高斯模糊（消融发现：裁剪 + 颜色是关键）。
投影头 (projection head)：encoder 后接一个 2 层 MLP $g$，对比损失在 $g(h)$ 上算，下游用 $h$。这是关键的 trick：投影头丢掉对增强敏感的特征，让 $h$ 更通用。
NT-Xent 损失。
大 batch：4096–8192，因为 batch 内每个样本贡献 $2N-2$ 个负例。

SimCLR 单步：
  for x in batch:
    x1, x2 ← 两次随机增强(x)
    h1, h2 ← encoder(x1), encoder(x2)
    z1, z2 ← projection_head(h1), projection_head(h2)
  L ← NT-Xent({(z1_i, z2_i)})
  反向传播

5.2 MoCo (Momentum Contrast, He et al. 2020)

SimCLR 依赖大 batch 提供负例，对显存要求极高。MoCo 的解决方案：

动量编码器 (momentum encoder)：维护一个 EMA 版本的 encoder：

\[ \theta_k \leftarrow m \theta_k + (1 - m) \theta_q, \quad m \in [0.99, 0.999] \]

队列 (queue)：保存最近 $K$ 个 mini-batch 的 key embedding（典型 $K = 65536$），作为负例池。
InfoNCE 损失：query $q$ 与正 key $k_+$、队列中所有负 key 比较。

好处：负例数解耦于 batch size，显存友好。缺点：动量更新引入 staleness，需要仔细调 $m$。MoCo v2 把 SimCLR 的投影头 + 强增强搬过来，性能进一步提升。

5.3 BYOL (Bootstrap Your Own Latent, Grill et al. 2020)

BYOL 的惊人观察：可以完全不用 negatives。

架构：两个网络 online + target，target 是 online 的 EMA。online 接一个预测头 (predictor) $q$，预测 target 的输出：

\[ L_{\mathrm{BYOL}} = \| \overline{q(z_\theta)} - \overline{z'_\xi} \|^2 \quad \text{(L2 normalized)} \]

关键 trick：

stop-gradient on target（target 不参与反向传播）；
predictor 的非对称性——若移除 predictor，模型立刻塌缩；
没有 negatives，但因为 stop-gradient + EMA + predictor 三重不对称，模型不会塌缩到平凡解。

BYOL 颠覆了"对比学习必须有 negatives"的信念，引发理论解释竞赛（如 Tian 2021 用动力学分析）。

5.4 SimSiam (Chen & He 2021)

比 BYOL 更极端：连 EMA target 都不要，只保留 stop-gradient + predictor：

\[ L_{\mathrm{SimSiam}} = -\frac{1}{2}\left(\cos(p_1, \mathrm{sg}(z_2)) + \cos(p_2, \mathrm{sg}(z_1))\right) \]

stop-gradient 是 BYOL/SimSiam 不塌缩的"灵魂"，这是 2021 年最神秘的理论问题之一。

5.5 DINO (Caron et al. 2021)

DINO = Self-Distillation with NO labels。把对比学习与知识蒸馏结合，并首次在 ViT 上展示自监督的强大涌现能力。

学生网络 $g_\theta$，教师网络 $g_{\xi}$（EMA），都用 ViT；
学生看局部 crop（小），教师看全局 crop（大）；
学生输出去匹配教师 softmax 输出（不是对比损失，是交叉熵）；
centering + sharpening 防止塌缩。

惊人发现：DINO ViT 的注意力图自动聚焦于物体边缘——纯无监督涌现出语义分割能力。这是 ViT + 自监督的标志性成果。

5.6 对比学习方法总览

方法	年份	损失	是否需要 negatives	关键创新
SimCLR	2020	NT-Xent	是（大 batch）	投影头 + 强增强
MoCo v2	2020	InfoNCE	是（队列）	动量编码器
BYOL	2020	L2 (predicted vs EMA)	否	predictor + stop-gradient
SwAV	2020	聚类预测	否	聚类原型 + 多视角
SimSiam	2021	cosine + stop-gradient	否	极简，无 EMA
Barlow Twins	2021	互相关矩阵	否	冗余消除
DINO	2021	交叉熵蒸馏	否	self-distillation + ViT 涌现

6. 跨模态度量学习

跨页深化：../../../1_DeepLearning/Foundation_Models/vision_foundation.md 已介绍 CLIP 的整体地位与下游应用。本节聚焦其对比学习算法细节。

6.1 CLIP (Contrastive Language-Image Pre-training, Radford et al. 2021)

问题设定：4 亿对（image, caption）从互联网爬取。任务：让图像与其对应的描述在 embedding 空间靠近。

架构：

图像编码器 $f_I$（ViT 或 ResNet）；
文本编码器 $f_T$（Transformer）；
各自后接线性投影到联合 $d$ 维空间；
L2 归一化。

损失：对称 InfoNCE。给 batch 内 $N$ 对 $(I_i, T_i)$，构造 $N \times N$ 相似度矩阵 $S$，$S_{ij} = f_I(I_i)^T f_T(T_j) / \tau$。则

\[ L_{\mathrm{CLIP}} = \frac{1}{2}\left( \mathrm{CE}(\mathrm{softmax}_{\text{row}}(S), I) + \mathrm{CE}(\mathrm{softmax}_{\text{col}}(S), I) \right) \]

即"每张图配对它的真 caption"+"每个 caption 配对它的真图"。

Zero-shot 分类：把类名 $c$ 包装成提示 "a photo of a {c}"，编码为 $f_T(t_c)$。新图像 $I$ 的预测：

\[ \hat c = \arg\max_c \; f_I(I)^T f_T(t_c) \]

CLIP 在 30+ 视觉数据集上零样本超越或逼近全监督模型，开启了 foundation model 的视觉-语言时代。

6.2 ALIGN (Jia et al. 2021)

与 CLIP 几乎同期，规模更大（18 亿对，含噪声 alt-text），损失相同。说明数据规模可以补偿数据质量。

6.3 SigLIP (Zhai et al. 2023)

关键改进：把 CLIP 的 softmax-based InfoNCE 换成 sigmoid-based 二元分类：

\[ L_{\mathrm{SigLIP}} = -\frac{1}{N}\sum_{i,j} \log \sigma\left(z_{ij} \cdot (t \cdot s_{ij} + b)\right) \]

其中 $z_{ij} = +1$ 若 $i = j$ 否则 $-1$，$s_{ij}$ 是相似度，$t, b$ 是可学温度与偏置。优势：

不需要全 batch softmax 归一化，分布式训练通信量大幅降低；
小 batch（如 8k）就能达到 SimCLR/CLIP 32k batch 的效果；
数学上是对每对独立做二分类，更鲁棒。

SigLIP 已成为 2024 年后 CLIP 替代品的事实标准。

7. 度量空间几何

embedding 空间的几何选择对类比派至关重要。

7.1 欧氏 (Euclidean) embedding

最常见。但欧氏几何对"层次结构"建模能力有限——见下文双曲。

7.2 球面 (Spherical) embedding

强制 $\|z\| = 1$，相似度退化为余弦。优势：

数值稳定（梯度不会因 norm 爆炸）；
与 softmax 兼容（softmax 假设 logits 数值有界）；
几何均匀性（hyperspherical uniformity, Wang & Isola 2020）。

Wang & Isola 2020 的著名分析把对比学习目标分解为：

\[ L_{\mathrm{contrastive}} \approx -\underbrace{\mathbb{E}[\mathrm{sim}(z, z^+)]}_{\text{对齐 (alignment)}} + \underbrace{\log \mathbb{E}[\exp(\mathrm{sim}(z, z^-) / \tau)]}_{\text{均匀 (uniformity)}} \]

好的对比学习模型同时做到对齐（同类靠近）+均匀（在球面上分布均匀），两者缺一不可。

7.3 双曲 (Hyperbolic) embedding

双曲空间（如 Poincaré 球模型）的体积随半径指数增长，天然适合表征树状/层次结构。Nickel & Kiela (2017) 证明双曲 embedding 用更少维度就能精确表示 WordNet。但梯度优化在黎曼流形上需要特殊处理（Riemannian Adam）。

8. 度量学习架构演进图

flowchart TD
    A["k-NN<br/>固定欧氏"] --> B["Mahalanobis 度量学习"]
    B --> C["LMNN (2009)"]
    B --> D["ITML (2007)"]
    C --> E["Siamese 网络<br/>(Bromley 1993, 复兴 2014)"]
    D --> E
    E --> F["Triplet 网络<br/>FaceNet (2015)"]
    F --> G["对比损失 NT-Xent<br/>SimCLR (2020)"]
    G --> H["MoCo (2020)<br/>队列+动量"]
    G --> I["BYOL (2020)<br/>无 negatives"]
    G --> J["DINO (2021)<br/>self-distillation"]
    G --> K["CLIP (2021)<br/>跨模态"]
    K --> L["SigLIP (2023)<br/>sigmoid"]
    K --> M["BLIP/Flamingo/<br/>多模态 LLM"]
    H --> N["RAG 时代<br/>检索 embedding"]

    style G fill:#fde68a
    style K fill:#bbf7d0
    style N fill:#bbf7d0

9. 评估

度量学习评估不能用准确率——评估的是 embedding 质量，而非分类。常用指标：

9.1 Recall@K

测试集每个 query，看它的最近 $K$ 个邻居中是否有同类样本：

\[ \mathrm{Recall@K} = \frac{1}{|Q|} \sum_{q \in Q} \mathbb{1}\left[\exists i \in \mathrm{kNN}_K(q): y_i = y_q\right] \]

人脸识别、图像检索的标准指标。

9.2 mAP (mean Average Precision)

对每个 query，按相似度排序后计算 AP：

\[ \mathrm{AP}(q) = \frac{1}{|R_q|} \sum_{k=1}^{N} P(k) \cdot \mathrm{rel}(k) \]

mAP = 所有 query 的 AP 平均。比 Recall@K 更全面，但成本更高。

9.3 NMI (Normalized Mutual Information)

把 embedding 聚类后，与真标签计算互信息——衡量 embedding 空间的语义一致性。

9.4 t-SNE / UMAP 可视化

把高维 embedding 降到 2D 直观看。t-SNE 强调局部结构，UMAP 兼顾全局——但可视化只是辅助，不能作为主要评估。

9.5 线性探测 (Linear Probing)

冻结 encoder，在 embedding 上训练一个线性分类器。准确率代表 embedding 的"线性可分性"——这是 SimCLR 之后自监督预训练的标准评估指标。

9.6 KNN 评估

冻结 encoder，直接做 k-NN 分类。比 linear probing 更"原教旨"——它直接验证类比派的预设：好 embedding ⇒ 邻居有用。

代码示例：SimCLR 风格的 NT-Xent 损失实现

import torch
import torch.nn.functional as F

def nt_xent_loss(z1: torch.Tensor, z2: torch.Tensor, tau: float = 0.5) -> torch.Tensor:
    """
    z1, z2: shape [N, d]，同 batch 的两个增强视图的 embedding
    返回: 标量 NT-Xent 损失
    """
    N = z1.shape[0]
    z = torch.cat([z1, z2], dim=0)            # [2N, d]
    z = F.normalize(z, dim=1)                 # L2 归一化到单位球面
    sim = z @ z.T / tau                       # [2N, 2N] 余弦相似度
    sim.fill_diagonal_(-1e9)                  # 排除自己

    # 正例索引：i 的正例是 i+N（或 i-N）
    targets = torch.cat([torch.arange(N, 2*N), torch.arange(0, N)]).to(z.device)
    return F.cross_entropy(sim, targets)

交叉引用

类比派整体框架：本页 §1（派系入口）
视觉自监督上层叙事：../../../1_DeepLearning/Computer_Vision/视觉自监督.md
元学习与少样本中的 Siamese 应用：../../../1_DeepLearning/Computer_Vision/meta_learning.md
CLIP 在基础模型谱系中的位置：../../../1_DeepLearning/Foundation_Models/vision_foundation.md
怎样部署学到的 embedding（向量库、ANN、RAG）：推荐系统与现代检索

参考文献

Hadsell, R., Chopra, S., & LeCun, Y. (2006). Dimensionality reduction by learning an invariant mapping. CVPR. — Contrastive loss 的奠基论文。
Bromley, J., et al. (1993). Signature verification using a Siamese time delay neural network. NIPS. — Siamese 网络原始论文。
Davis, J. V., et al. (2007). Information-theoretic metric learning. ICML. — ITML。
Weinberger, K. Q., & Saul, L. K. (2009). Distance metric learning for large margin nearest neighbor classification. JMLR. — LMNN。
Schroff, F., Kalenichenko, D., & Philbin, J. (2015). FaceNet: A unified embedding for face recognition and clustering. CVPR. — Triplet loss + 大规模人脸识别。
Sohn, K. (2016). Improved deep metric learning with multi-class N-pair loss. NIPS.
van den Oord, A., Li, Y., & Vinyals, O. (2018). Representation learning with contrastive predictive coding. arXiv:1807.03748. — InfoNCE 与互信息下界。
Chen, T., et al. (2020). A simple framework for contrastive learning of visual representations. ICML. — SimCLR / NT-Xent。
He, K., et al. (2020). Momentum contrast for unsupervised visual representation learning. CVPR. — MoCo。
Grill, J.-B., et al. (2020). Bootstrap your own latent: A new approach to self-supervised learning. NeurIPS. — BYOL，证明可以不用 negatives。
Chen, X., & He, K. (2021). Exploring simple Siamese representation learning. CVPR. — SimSiam。
Caron, M., et al. (2021). Emerging properties in self-supervised vision Transformers. ICCV. — DINO。
Radford, A., et al. (2021). Learning transferable visual models from natural language supervision. ICML. — CLIP。
Zhai, X., et al. (2023). Sigmoid loss for language image pre-training. ICCV. — SigLIP。
Khosla, P., et al. (2020). Supervised contrastive learning. NeurIPS. — SupCon。
Wang, T., & Isola, P. (2020). Understanding contrastive representation learning through alignment and uniformity on the hypersphere. ICML. — 对齐+均匀分解。
Nickel, M., & Kiela, D. (2017). Poincaré embeddings for learning hierarchical representations. NeurIPS. — 双曲 embedding。

推荐系统与现代检索

本页定位：这是 Analogizers 三页中站内空白最大的一页，要写得最深。从 1990 年代的协同过滤一路讲到 2025 年的 RAG / RETRO——推荐系统、案例推理 (CBR) 与向量检索是同一件事：在大规模案例库里，找到与当前 query 最相似的案例，把它们的答案"借"过来。这是类比派在工业界的核心生产力。

类比派最大的工业应用从来不是 SVM，而是推荐系统。Amazon 的"看了这个的人也看了"、Netflix 的电影推荐、YouTube 的视频流——它们的内核都是找相似用户/物品。同样的思想在 2010 年代被搬到 ANN 检索（FAISS / HNSW），在 2020 年代成为 RAG 的基础设施。

本页把这条工程主脉一以贯之地讲完整。

1. 推荐系统综述

推荐系统按"信息源"分为三大范式：

范式	输入	思想	代表方法	优势	劣势
内容推荐 (Content-based)	物品特征 + 用户历史	推荐与用户喜欢过的物品特征相似的物品	TF-IDF + 余弦	冷启动新物品有优势；可解释	受限于显式特征工程；视野窄
协同过滤 (Collaborative Filtering, CF)	用户-物品交互矩阵	利用"群体智慧"——相似用户喜欢相似物品	k-NN CF, 矩阵分解	不需要内容特征；自动发现潜在模式	用户/物品冷启动；稀疏性
混合 (Hybrid)	两者皆有	加权 / 切换 / 特征融合	Wide & Deep, 双塔	两全其美	工程复杂

推荐 = 类比派典型应用：新 query (用户) 来时，找历史上的相似 query，参考它们的答案 (物品)。

2. 协同过滤 (Collaborative Filtering)

2.1 用户-物品矩阵

设 $U$ 个用户、$I$ 个物品。评分矩阵 $R \in \mathbb{R}^{U \times I}$，$R_{ui}$ 是用户 $u$ 对物品 $i$ 的评分（多数为缺失）。任务：填补缺失项。

2.2 User-based CF (Goldberg 1992; GroupLens 1994)

对用户 $u$ 推荐物品 $i$ 的预测评分：

\[ \hat r_{ui} = \bar r_u + \frac{\sum_{v \in N(u)} \mathrm{sim}(u, v) \cdot (r_{vi} - \bar r_v)}{\sum_{v \in N(u)} |\mathrm{sim}(u, v)|} \]

其中 $N(u)$ 是与 $u$ 最相似的 $k$ 个用户，$\bar r_u$ 是用户 $u$ 的平均评分（用于减除每个用户的整体偏置）。

2.3 Item-based CF (Sarwar et al. 2001)

Amazon 的关键创新：用物品相似度而非用户相似度——物品相似度更稳定（用户兴趣会变，物品特征不变），且物品数往往远小于用户数：

\[ \hat r_{ui} = \frac{\sum_{j \in N(i; u)} \mathrm{sim}(i, j) \cdot r_{uj}}{\sum_{j \in N(i; u)} |\mathrm{sim}(i, j)|} \]

其中 $N(i; u)$ 是用户 $u$ 评过、且与物品 $i$ 最相似的 $k$ 个物品。

2.4 相似度度量

度量	公式	备注
皮尔逊 (Pearson)	$\frac{\sum_i (r_{ui} - \bar r_u)(r_{vi} - \bar r_v)}{\sqrt{\sum (r_{ui}-\bar r_u)^2} \sqrt{\sum (r_{vi}-\bar r_v)^2}}$	自动减除均值；处理打分尺度差异
余弦 (Cosine)	$\frac{r_u^T r_v}{\\|r_u\\|\\|r_v\\|}$	简单高效；隐含假设缺失 = 0（有问题）
调整余弦 (Adjusted Cosine)	减除每个物品的均值后求余弦	item-based 的最佳选择
Jaccard	$\frac{	R_u \cap R_v

2.5 冷启动问题

CF 的死穴：

类型	描述	对策
新用户冷启动	没有历史评分	引导评分 / 用人口统计 / 内容推荐兜底
新物品冷启动	没人评过	内容推荐 / 用物品特征做侧信息
稀疏冷启动	整体矩阵 99.9% 缺失	矩阵分解（学低维表示，泛化）

3. 矩阵分解 (Matrix Factorization)

CF 的稀疏问题被矩阵分解优雅地解决——把 $R$ 分解为低秩近似。

3.1 Truncated SVD

\[ R \approx U_k \Sigma_k V_k^T \]

但传统 SVD 假设矩阵稠密，无法处理缺失。

3.2 FunkSVD (Funk 2006, Netflix Prize)

只在已观测项上拟合：

\[ \hat r_{ui} = \mu + b_u + b_i + p_u^T q_i \]

参数：

$\mu$: 全局平均；
$b_u$: 用户偏置（"严苛/宽松"）；
$b_i$: 物品偏置（"热门/冷门"）；
$p_u, q_i \in \mathbb{R}^k$: 用户与物品的潜在因子向量。

目标：

\[ \min_{p, q, b} \sum_{(u,i) \in \mathcal{O}} (r_{ui} - \hat r_{ui})^2 + \lambda (\|p_u\|^2 + \|q_i\|^2 + b_u^2 + b_i^2) \]

只在观测集 $\mathcal{O}$ 上求和。SGD 求解：

for (u, i, r) in 观测对:
    e = r - μ - b_u - b_i - p_u^T q_i
    b_u ← b_u + η (e - λ b_u)
    b_i ← b_i + η (e - λ b_i)
    p_u ← p_u + η (e q_i - λ p_u)
    q_i ← q_i + η (e p_u - λ q_i)

Funk 用此方法把 Netflix Prize 的 RMSE 推进了 7%，是 2006 年的现象级成果。

3.3 ALS (Alternating Least Squares)

$P, Q$ 联合优化非凸，但固定一边对另一边是凸最小二乘——交替求解：

\[ P \leftarrow \arg\min_P \|R - PQ^T\|_F^2 + \lambda \|P\|_F^2 \quad \text{(闭式)} \]

\[ Q \leftarrow \arg\min_Q \|R - PQ^T\|_F^2 + \lambda \|Q\|_F^2 \quad \text{(闭式)} \]

ALS 易于并行（每行独立），是 Spark MLlib 的默认推荐算法。

3.4 NMF (Non-negative Matrix Factorization)

约束 $P, Q \geq 0$。可解释性更好（因子可视为"主题"），但拟合能力弱于无约束 MF。

4. 隐式反馈 (Implicit Feedback)

关键观察：现实中显式评分（1-5 星）很少，隐式信号（点击、观看时长、购买）才是主流。隐式反馈的难点：未观察 ≠ 不喜欢——可能只是没看到。

4.1 WMF (Weighted Matrix Factorization, Hu et al. 2008)

把 0/1 矩阵 $P$ 与置信度 $C$ 分开：

$p_{ui} = 1$ 若 $r_{ui} > 0$（有交互）；
$c_{ui} = 1 + \alpha r_{ui}$（交互越多，越置信"喜欢"）。

目标：

\[ \min_{P, Q} \sum_{u, i} c_{ui} (p_{ui} - p_u^T q_i)^2 + \lambda (\|P\|^2 + \|Q\|^2) \]

注意：求和遍历所有 $(u, i)$，包括未观测对（视为 0 但低置信度）。复杂度通过 ALS 的代数技巧 ($Y^T C^u Y = Y^T Y + Y^T (C^u - I) Y$) 控制在线性。

4.2 BPR (Bayesian Personalized Ranking, Rendle et al. 2009)

革命性思路：不预测分数，直接优化排序。三元组 $(u, i, j)$，$i$ 是用户 $u$ 交互过的（正），$j$ 是没交互过的（负）。BPR 假设用户偏好 $i > j$：

\[ L_{\mathrm{BPR}} = -\sum_{(u, i, j) \in D_S} \log \sigma(\hat x_{uij}) + \lambda \|\Theta\|^2 \]

其中 $\hat x_{uij} = \hat r_{ui} - \hat r_{uj}$（任意打分模型，常用 MF）。

优势：

直接优化 AUC（pairwise ranking）；
与隐式反馈天然契合；
形式与 SVM hinge loss 类似（"间隔"思想）。

BPR 至今仍是隐式推荐的 baseline——任何新方法都要与 BPR-MF 对比。

5. 深度推荐

2014 年后深度学习席卷推荐系统。

5.1 NCF (Neural Collaborative Filtering, He et al. 2017)

把 MF 的"点积 $p_u^T q_i$"换成 MLP：

\[ \hat r_{ui} = \mathrm{MLP}\left(\mathrm{concat}(\mathbf{e}_u, \mathbf{e}_i)\right) \]

其中 $\mathbf{e}_u, \mathbf{e}_i$ 是 ID embedding。NeuMF 进一步把 GMF（generalized MF）和 MLP 并联融合。

争议：Rendle et al. 2020 用调好的 MF 反超 NCF，引发"是 NCF 真的更好，还是只是调参更多"的反思——推荐系统的"伪进步"问题。

5.2 AutoRec (Sedhain et al. 2015)

把推荐看作自编码器任务：输入用户的评分向量 $r_u$（带缺失），输出重构后的稠密向量 $\hat r_u$。

5.3 Wide & Deep (Cheng et al. 2016)

Google Play 部署的双轨架构：

Wide 部分：交叉特征的线性模型，记忆显式规则（"安装了 A 的人会装 B"）；
Deep 部分：embedding + MLP，泛化到未见组合。

联合训练，工业界爆款。后续衍生：DeepFM、xDeepFM、DCN——目标都是更好处理特征交互。

5.4 DIN (Deep Interest Network, Zhou et al. 2018)

阿里电商场景：用户兴趣是多模态、动态的——给 query 物品 $i$，注意力地聚合用户历史交互序列：

\[ \mathbf{v}_u = \sum_{j \in H_u} a(\mathbf{e}_j, \mathbf{e}_i) \cdot \mathbf{e}_j \]

权重 $a$ 由小 MLP 给出。这是注意力机制在推荐中的早期成功应用，比 Transformer 还早。后续 DIEN、SIM 走向更长序列建模。

5.5 双塔模型 (Two-Tower Models): 现代召回的事实标准

flowchart LR
    U["用户特征<br/>(ID, 历史, demographics)"] --> UT["用户塔 fU"]
    I["物品特征<br/>(ID, 内容, 属性)"] --> IT["物品塔 fI"]
    UT --> ZU["用户 embedding zu"]
    IT --> ZI["物品 embedding zi"]
    ZU & ZI --> S["相似度 zu · zi"]
    S --> P["预测 / 排序"]
    style UT fill:#fde68a
    style IT fill:#fde68a
    style S fill:#bbf7d0

关键属性：用户和物品的 embedding 完全解耦计算——

离线：批量算所有物品 embedding，存进 ANN 索引；
在线：来一个用户，实时算用户 embedding，做 k-NN 查询。

延迟可以做到亚毫秒——这就是工业级召回。代表论文：YouTube DNN (Covington 2016)、Sampling-bias-corrected (Yi 2019)。

训练：通常用 in-batch negatives + InfoNCE（和对比学习一模一样）：

\[ L = -\log \frac{\exp(z_u^T z_{i^+} / \tau)}{\sum_{j \in B} \exp(z_u^T z_j / \tau)} \]

对比学习 = 度量学习 = 双塔召回 = 现代 RAG 检索器训练——它们本质上是同一个目标。

5.6 排序 vs 召回

工业界推荐分两阶段：

阶段	任务	候选规模	主流方法
召回 (Retrieval)	从亿级候选选千级	$10^9 \to 10^3$	双塔 + ANN
精排 (Ranking)	从千级精确打分排序	$10^3 \to 10^1$	DIN / DCN / GBDT

双塔不能用于精排——精排需要细粒度交叉特征，无法用解耦的塔。

6. 图推荐

用户-物品交互天然是二部图，GNN 自然适用。

6.1 PinSage (Ying et al. 2018)

Pinterest 30 亿节点的工业级 GraphSAGE：

邻居采样：随机游走计算重要性；
卷积：把邻居 embedding 加权聚合到中心节点；
MapReduce 式离线训练。

PinSage 服务 2 亿月活用户，是 GNN 工业落地的标志性案例。

6.2 LightGCN (He et al. 2020)

反向工程：消融 GCN 的非线性变换和特征变换，只保留邻居聚合：

\[ \mathbf{e}_u^{(k+1)} = \sum_{i \in N(u)} \frac{1}{\sqrt{|N(u)| |N(i)|}} \mathbf{e}_i^{(k)} \]

最终 embedding = 各层加权平均。惊人发现：去掉非线性反而更好——推荐场景的特征本就是 ID embedding，非线性变换没必要。LightGCN 是 BPR-MF 之后的强 baseline。

7. 案例推理 (Case-Based Reasoning, CBR)

CBR 是符号 AI 时代的"原始 RAG"——理解 CBR 就理解了 RAG 的思想根源。

7.1 Aamodt & Plaza 1994: 4R 循环

flowchart LR
    P["新问题<br/>(Problem)"] --> R1["1. Retrieve<br/>检索相似案例"]
    R1 --> R2["2. Reuse<br/>复用案例的解"]
    R2 --> R3["3. Revise<br/>调整以适应新问题"]
    R3 --> R4["4. Retain<br/>把新案例存入案例库"]
    R4 --> CB[("案例库<br/>Case Base")]
    CB --> R1
    style R1 fill:#fde68a
    style R4 fill:#bbf7d0

阶段	关键问题
Retrieve	用什么相似度？怎样高效检索？
Reuse	直接复用？还是抽取经验？
Revise	用领域知识调整解（人工 / 规则 / 模型）
Retain	存哪些（避免案例库膨胀）？怎样组织？

7.2 案例库结构

平面案例库：所有案例线性存储，依赖好的索引（k-d tree、倒排）；
层次案例库：按抽象度组织（如医疗：器官 → 系统 → 症状 → 诊断）；
原型 + 实例：每个原型代表一类案例，实例挂在原型下。

7.3 经典 CBR 系统

系统	领域	时期	备注
CASEY (Koton 1989)	心脏病诊断	1980s	与 MYCIN 风格规则系统的混合
HYPO (Ashley 1990)	法律推理	1990s	商业秘密案例；引入"factor"概念
CHEF (Hammond 1986)	烹饪计划	1980s	食谱适配
客服 helpdesk	工单匹配	1990s+	至今仍在用——"找以前的相似工单"

7.4 CBR vs ML

CBR 长期被 ML 主流忽视，但它的范式是健壮的：

维度	传统 ML	CBR
知识形式	参数化模型	案例 + 相似度
学习成本	高（重训练）	低（增量加案例）
可解释	通常差	"因为类似案例 X"
适应新数据	需要重训练	Retain 即可

现代视角：CBR 的 Retrieve-Reuse-Revise-Retain 循环在 RAG/Agent 时代焕发新生——把 LLM 当作 Reuse+Revise 的引擎，把向量库当作案例库，就得到了"LLM agent + memory"的范式。

8. 现代检索：类比派与大模型时代的桥梁

跨页深化：../../../AI_Agents/04_Memory_Systems/长期记忆与向量数据库.md 已介绍向量库在 agent memory 中的角色。本节聚焦算法层面的检索方法，是其前置基础。

8.1 检索范式：dense vs sparse

范式	表示	相似度	代表
稀疏 (Sparse)	高维稀疏（词袋）	BM25, TF-IDF	Lucene, Elasticsearch
稠密 (Dense)	低维稠密 embedding	余弦, 点积	DPR, ColBERT, Sentence-BERT
混合 (Hybrid)	两者结合	加权融合 / RRF	Vespa, Weaviate

BM25 (1994)

经典稀疏检索：

\[ \mathrm{BM25}(q, d) = \sum_{t \in q} \mathrm{IDF}(t) \cdot \frac{\mathrm{tf}(t, d) (k_1 + 1)}{\mathrm{tf}(t, d) + k_1 \left(1 - b + b \frac{|d|}{\mathrm{avgdl}}\right)} \]

调参 $k_1 \approx 1.2 \sim 2.0$, $b \approx 0.75$。至今仍是最强 baseline 之一——很多稠密检索论文吹得天花乱坠，回头一看 BM25 只差几个点。

DPR (Dense Passage Retrieval, Karpukhin et al. 2020)

双塔 BERT 训练问答检索：

query encoder + passage encoder（不共享权重）；
in-batch negatives + InfoNCE；
训练后 passage 离线编码进 FAISS。

DPR 在 NaturalQuestions 上击败 BM25，开启稠密检索时代。

8.2 ANN 算法对比

向量数已达亿级时，精确 k-NN 不可行。ANN (Approximate Nearest Neighbor) 用精度换速度。

算法	思想	精度	速度	内存	索引构建	适用场景
暴力 (Flat)	逐个比较	100%	慢 ($O(N)$)	$O(N)$	$O(1)$	$N < 10^6$ 或 ground truth
IVF (Inverted File)	先聚类 ($k$-means)，再倒排	90-99%	快	$O(N)$	$O(Nk)$	大数据，需粗+精排
PQ (Product Quantization)	子向量量化压缩	中	极快	极小	中	内存受限场景
IVF-PQ	IVF + PQ 组合	中-高	极快	极小	中	FAISS 默认大规模配置
HNSW	分层小世界图	极高	极快	大 ($O(N \log N)$ 边)	慢	通用最强；标准选择
LSH	局部敏感哈希	中	快	中	快	历史方法，已被 HNSW 超越
ScaNN (Google)	IVF + 各向异性量化	高	极快	小	中	Google 内部主力
Annoy (Spotify)	随机投影森林	中	快	中	快	静态索引

工业实践决策树：

数据 < 1M、追求精度 → Flat（FAISS IndexFlatIP）；
数据 1M–100M、内存够 → HNSW（默认选择）；
数据 100M+、内存紧 → IVF-PQ；
需要在线插入 → HNSW（IVF 不易动态更新）。

8.3 HNSW (Hierarchical Navigable Small World) 详解

Malkov & Yashunin 2016 的 HNSW 是 ANN 的"教科书选择"——精度近 100%、查询亚毫秒、增量插入友好。

核心思想：把数据点组织成多层图，每层是"小世界"图（近邻 + 少量长连接），高层稀疏（用于快速跳跃），低层稠密（用于精细搜索）。

flowchart TD
    subgraph L2["Layer 2 (稀疏，长跳)"]
      A2["A"] -.- F2["F"]
    end
    subgraph L1["Layer 1 (中等密度)"]
      A1["A"] --- B1["B"] --- F1["F"]
      B1 --- D1["D"]
    end
    subgraph L0["Layer 0 (全部点，稠密)"]
      A0["A"] --- B0["B"] --- C0["C"] --- D0["D"]
      D0 --- E0["E"] --- F0["F"]
      C0 --- E0
    end
    A2 -.-> A1 -.-> A0
    F2 -.-> F1 -.-> F0

搜索算法：

HNSW 搜索 query q:
  current ← 入口点 (顶层)
  for level from top to 1:
    用贪心搜索找到当前层 q 的最近点 → current
  在 layer 0 用 ef-search 限定的 best-first beam search
  返回 top-k

插入：

随机选层数 $\ell$（指数分布，$\ell = \lfloor -\ln(r) \cdot m_L \rfloor$）；
从顶层贪心搜到 $\ell + 1$ 层；
在 $\ell$ 到 0 层每层连 $M$ 个最近邻（用 heuristic 选择保多样性）。

关键参数：

$M$：每节点最大连接数（典型 16–48）；
ef-construction：构建期搜索宽度（典型 200）；
ef-search：查询期搜索宽度（精度-速度旋钮，典型 50–200）。

距离公式：HNSW 不限定度量；常见有 L2、内积、余弦——只要满足三角不等式或近似满足即可（实践中即使非度量也常有效）。

8.4 RAG = 类比派的复兴

flowchart LR
    Q["用户 query"] --> EM["embedding 模型<br/>(度量学习训练)"]
    EM --> QV["query 向量"]
    QV --> ANN["ANN 索引<br/>(HNSW/FAISS)"]
    DB[("文档库<br/>(预先 embed)")] --> ANN
    ANN --> TOPK["Top-K 文档"]
    TOPK --> LLM["LLM<br/>(in-context 推理)"]
    Q --> LLM
    LLM --> ANS["回答 + 引用"]
    style ANN fill:#fde68a
    style LLM fill:#bbf7d0

RAG (Retrieval-Augmented Generation, Lewis et al. 2020) 把检索到的 top-k 文档作为 LLM 的上下文，让 LLM 在"看过相关资料"的前提下回答问题。

RAG vs 传统 CBR 对照：

维度	传统 CBR (Aamodt 1994)	RAG (2020+)
案例库	结构化案例	文档/段落 (chunks)
检索	手工相似度（特征匹配）	embedding + ANN
Reuse 引擎	规则系统 / 人工	LLM (Transformer)
Revise	人工编辑	LLM in-context
Retain	添加到案例库	添加到文档库（增量索引）
评估	案例命中率	Recall@K + 端到端 QA 准确率

派系视角：RAG 不是 LLM 的"补丁"——它是类比派对参数化方法的回归。LLM 把"知识"压进权重的范式有根本局限（幻觉、过时、无法溯源），类比派的"案例库 + 检索"在大模型时代以 RAG 之名复活并主导。

8.5 检索增强训练

把检索从"推理时"延伸到"训练时"：

RETRO (Borgeaud et al. 2022, DeepMind)

思想：训练 LLM 时，每个 chunk 都从 2 万亿 token 的库中检索 top-k 邻居，通过 cross-attention 注入 Transformer。

效果：7.5B 参数 + 检索 ≈ 175B 参数无检索；
意义：参数效率的革命——不必把所有知识塞进权重。

Atlas (Izacard et al. 2022, Meta)

为知识密集型 NLP 任务（QA、事实核查）端到端训练 retrieval + generation。few-shot 性能超过 50× 大的 PaLM。

REPLUG (Shi et al. 2023)

更轻量：只训练 retriever，让它"配合"冻结的黑盒 LLM。把 LLM 的输出反馈作为 retriever 的监督信号——retriever 学会"挑出对 LLM 最有用的文档"。

9. 工程实践：向量库选型

9.1 主流向量数据库对比

库	类型	索引	持久化	元数据过滤	分布式	适合场景
FAISS	库 (lib)	Flat/IVF/PQ/HNSW 全	需自己管	弱	无	离线、研究、高级用户
Milvus	服务	HNSW/IVF/DiskANN	强	强	强（云原生）	大规模生产
Qdrant	服务 (Rust)	HNSW	强	强（payload 过滤）	集群	中小规模、需要过滤
Weaviate	服务	HNSW	强	强（GraphQL）	集群	多模态、模式化数据
pgvector	Postgres 扩展	IVF/HNSW	复用 PG	SQL	复用 PG	已有 PG 栈、中等规模
Pinecone	SaaS	私有	托管	强	托管	不想运维
Chroma	嵌入式	HNSW	文件	中	弱	原型、小型应用

选型建议：

原型 / 小型 RAG → Chroma 或 FAISS in-memory；
已有 PG / 量级 < 1000 万 → pgvector；
需要过滤 + 中等规模 → Qdrant；
大规模 / 多租户 → Milvus 或 Pinecone（前者自托管，后者托管）。

9.2 实时召回的延迟预算

工业级搜索 / 推荐的端到端预算 ≈ 100ms。各阶段分配：

阶段	延迟预算	备注
网络 + 反序列化	5–10ms	gRPC + 二进制协议
Query encoder (embedding 模型)	10–30ms	模型蒸馏 / 量化关键
ANN 检索 (top-1000)	5–20ms	HNSW 在 1B 量级仍 < 20ms
元数据过滤	1–5ms	倒排索引
精排 (深度模型)	30–50ms	主要时间
后处理 / 多样性	5–10ms	re-rank

工程难点：embedding 模型的延迟。常用对策：模型蒸馏（双塔的小模型）、ONNX Runtime / TensorRT 推理加速、INT8 量化、缓存常见 query。

9.3 索引更新策略

向量库的"实时性"挑战：

策略	描述	优劣
全量重建	离线定期重建索引	简单；不实时
增量插入	HNSW 支持 add	实时；图质量随时间退化
双索引切换	热索引（在线增量）+ 冷索引（离线全量），定期切换	工业主流；运维成本高
Delta 索引	主索引（冷）+ Delta（热小索引），查询时合并	Milvus / Vespa 风格

10. 公式速查

10.1 BPR loss

\[ L_{\mathrm{BPR}} = -\sum_{(u, i, j)} \log \sigma\left(\hat r_{ui} - \hat r_{uj}\right) + \lambda \|\Theta\|^2 \]

10.2 FunkSVD 目标

\[ \min_{p, q, b} \sum_{(u,i) \in \mathcal{O}} (r_{ui} - \mu - b_u - b_i - p_u^T q_i)^2 + \lambda \cdot \mathrm{Reg} \]

10.3 双塔 in-batch InfoNCE

\[ L = -\frac{1}{|B|} \sum_{(u, i) \in B} \log \frac{\exp(z_u^T z_i / \tau)}{\sum_{j \in B} \exp(z_u^T z_j / \tau)} \]

10.4 HNSW 距离（任意度量，常见三种）

\[ d_2(x, y) = \|x - y\|_2, \quad d_{\text{IP}}(x, y) = -x^T y, \quad d_{\cos}(x, y) = 1 - \frac{x^T y}{\|x\|\|y\|} \]

代码示例：FAISS HNSW 索引 + 查询

import numpy as np
import faiss

d = 128                            # embedding 维度
N = 1_000_000                      # 向量数

# 1. 构建 HNSW 索引
index = faiss.IndexHNSWFlat(d, M=32)  # 每节点 32 邻居
index.hnsw.efConstruction = 200
index.hnsw.efSearch = 64

# 2. 插入向量（已是单位归一化的 embedding）
embeddings = np.random.randn(N, d).astype("float32")
embeddings /= np.linalg.norm(embeddings, axis=1, keepdims=True)
index.add(embeddings)

# 3. 查询
query = np.random.randn(1, d).astype("float32")
query /= np.linalg.norm(query)
D, I = index.search(query, k=10)   # top-10 最近邻
print("top-10 距离:", D[0])
print("top-10 索引:", I[0])

代码示例：BPR-MF 的 NumPy 实现

import numpy as np

def bpr_mf(triples, U, I, k=32, lr=0.05, lam=0.01, epochs=20):
    """
    triples: list of (u, i, j)，u 偏好 i 而非 j
    U, I: 用户、物品总数
    """
    P = np.random.randn(U, k) * 0.01
    Q = np.random.randn(I, k) * 0.01
    for ep in range(epochs):
        np.random.shuffle(triples)
        for (u, i, j) in triples:
            x_uij = P[u] @ (Q[i] - Q[j])
            sig = 1.0 / (1.0 + np.exp(x_uij))
            P[u] += lr * (sig * (Q[i] - Q[j]) - lam * P[u])
            Q[i] += lr * (sig * P[u] - lam * Q[i])
            Q[j] += lr * (-sig * P[u] - lam * Q[j])
    return P, Q

交叉引用

类比派整体框架：本页 §1（派系入口）
度量学习（embedding 怎么训）：度量学习与对比学习
核方法与 k-NN 数学基础：最近邻与核方法
Agent 长期记忆中的向量库工程：../../../AI_Agents/04_Memory_Systems/长期记忆与向量数据库.md

参考文献

Goldberg, D., et al. (1992). Using collaborative filtering to weave an information tapestry. CACM. — 协同过滤的最早提出。
Resnick, P., et al. (1994). GroupLens: An open architecture for collaborative filtering of netnews. CSCW. — User-based CF。
Sarwar, B., et al. (2001). Item-based collaborative filtering recommendation algorithms. WWW. — Item-based CF（Amazon 的核心）。
Funk, S. (2006). Netflix Update: Try this at home. — FunkSVD 的博客原始出处。
Koren, Y., Bell, R., & Volinsky, C. (2009). Matrix factorization techniques for recommender systems. Computer. — MF 的现代综述。
Hu, Y., Koren, Y., & Volinsky, C. (2008). Collaborative filtering for implicit feedback datasets. ICDM. — WMF。
Rendle, S., et al. (2009). BPR: Bayesian Personalized Ranking from implicit feedback. UAI. — BPR。
He, X., et al. (2017). Neural collaborative filtering. WWW. — NCF。
Cheng, H.-T., et al. (2016). Wide & Deep learning for recommender systems. DLRS@RecSys. — Wide & Deep。
Zhou, G., et al. (2018). Deep Interest Network for click-through rate prediction. KDD. — DIN。
Covington, P., Adams, J., & Sargin, E. (2016). Deep neural networks for YouTube recommendations. RecSys. — YouTube 双塔召回。
Ying, R., et al. (2018). Graph convolutional neural networks for web-scale recommender systems. KDD. — PinSage。
He, X., et al. (2020). LightGCN: Simplifying and powering graph convolution network for recommendation. SIGIR. — LightGCN。
Aamodt, A., & Plaza, E. (1994). Case-based reasoning: Foundational issues, methodological variations, and system approaches. AI Communications. — CBR 4R 循环奠基。
Robertson, S., & Zaragoza, H. (2009). The probabilistic relevance framework: BM25 and beyond. Foundations and Trends in Information Retrieval.
Karpukhin, V., et al. (2020). Dense Passage Retrieval for open-domain question answering. EMNLP. — DPR。
Malkov, Y. A., & Yashunin, D. A. (2016). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. TPAMI. — HNSW。
Johnson, J., Douze, M., & Jégou, H. (2019). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3), 535–547. — FAISS 论文。
Lewis, P., et al. (2020). Retrieval-Augmented Generation for knowledge-intensive NLP tasks. NeurIPS. — RAG。
Borgeaud, S., et al. (2022). Improving language models by retrieving from trillions of tokens. ICML. — RETRO。
Izacard, G., et al. (2022). Atlas: Few-shot learning with retrieval augmented language models. arXiv:2208.03299. — Atlas。
Shi, W., et al. (2023). REPLUG: Retrieval-augmented black-box language models. arXiv:2301.12652.
Rendle, S., et al. (2020). Neural collaborative filtering vs. matrix factorization revisited. RecSys. — NCF 与 MF 的争议。

方法	\(K(x, x_i)\)	\(\alpha_i\)
k-NN	\(\mathbb{1}[x_i \in \mathrm{kNN}(x)]\)	\(y_i\)
Nadaraya-Watson 回归	RBF 核 \(\exp(-\\|x-x_i\\|^2/2\sigma^2)\)	\(y_i / \sum_j K_j\)
SVM	任意 Mercer 核	拉格朗日乘子 \(\alpha_i y_i\)（仅支持向量非零）
核岭回归	任意 Mercer 核	\((K + \lambda I)^{-1} y\)
协同过滤	用户相似度 \(\mathrm{sim}(u, u_i)\)	\(r_{u_i, j}\)（其他用户对物品 \(j\) 的评分）
RAG	\(\cos(\mathbf{e}_q, \mathbf{e}_{d_i})\)	LLM 上下文中检索到的文档

\(k\)	偏差	方差	决策面	风险
\(k=1\)	极低	极高	锯齿状	过拟合（对噪声敏感）
\(k\) 适中	平衡	平衡	平滑	—
\(k=N\)	极高	极低	退化为多数类	欠拟合

度量	公式	适用场景
欧氏 (Euclidean)	\(d(x,y) = \sqrt{\sum_i (x_i - y_i)^2}\)	各维度同尺度、同语义的连续特征
曼哈顿 (Manhattan, \(\ell_1\))	$\sum_i	x_i - y_i
Chebyshev (\(\ell_\infty\))	$\max_i	x_i - y_i
Minkowski (\(\ell_p\))	$\left(\sum_i	x_i - y_i
Mahalanobis	\(\sqrt{(x-y)^T \Sigma^{-1} (x-y)}\)	各维度尺度/相关性不同的场景
余弦 (Cosine)	\(1 - \frac{x^T y}{\\|x\\|\\|y\\|}\)	文本 TF-IDF、embedding 相似度
Hamming	\(\sum_i \mathbb{1}[x_i \neq y_i]\)	二元串、分类特征
编辑距离 (Levenshtein)	DP 计算的最小编辑步数	字符串、生物序列
Jaccard	$1 - \frac{	A \cap B

核	公式	参数	适用场景
线性 (Linear)	\(K(x,y) = x^T y\)	—	高维稀疏文本（TF-IDF）
多项式 (Polynomial)	\((x^T y + c)^d\)	\(c, d\)	特征交互（NLP 中的 N-gram-like）
RBF / Gaussian	\(\exp(-\gamma \\|x-y\\|^2)\)	\(\gamma\)	通用默认核；无穷维特征空间
Laplacian	\(\exp(-\gamma \\|x-y\\|_1)\)	\(\gamma\)	比 RBF 对离群更鲁棒
Sigmoid	\(\tanh(\kappa x^T y + c)\)	\(\kappa, c\)	历史上模拟两层网络（不严格 PSD）
字符串核 (String)	共同子串数	\(k\) (子串长)	文本分类、生物序列
图核 (Graph)	随机游走/子图计数	—	化学分子、社交图
Fisher 核	$\nabla_\theta \log p(x	\theta)^T I^{-1} \nabla_\theta \log p(y	\theta)$

\(\tau\)	行为	效果
极小 (\(\tau \to 0\))	softmax 变 argmax	只关注最难负例（hardest negative），训练不稳
极大 (\(\tau \to \infty\))	softmax 趋均匀	所有负例等权，几乎没有学习信号
适中 (\(\tau \approx 0.05 \sim 0.5\))	平衡	SimCLR 默认 0.5；MoCo 默认 0.07；CLIP 学习温度

度量	公式	备注
皮尔逊 (Pearson)	\(\frac{\sum_i (r_{ui} - \bar r_u)(r_{vi} - \bar r_v)}{\sqrt{\sum (r_{ui}-\bar r_u)^2} \sqrt{\sum (r_{vi}-\bar r_v)^2}}\)	自动减除均值；处理打分尺度差异
余弦 (Cosine)	\(\frac{r_u^T r_v}{\\|r_u\\|\\|r_v\\|}\)	简单高效；隐含假设缺失 = 0（有问题）
调整余弦 (Adjusted Cosine)	减除每个物品的均值后求余弦	item-based 的最佳选择
Jaccard	$\frac{	R_u \cap R_v

阶段	任务	候选规模	主流方法
召回 (Retrieval)	从亿级候选选千级	\(10^9 \to 10^3\)	双塔 + ANN
精排 (Ranking)	从千级精确打分排序	\(10^3 \to 10^1\)	DIN / DCN / GBDT