距离度量学习综述：从马氏距离到结构化数据的 10 年脉络

  • 关联论文：1306.6709
  • 作者：flyP
  • 更新：2026-08-07
  • 审校：Jay（事实核查 + 可读性精修 + 工程节补强）

一句话结论

这篇由 Bellet、Habrard、Sebban 撰写的综述系统梳理了 2003-2013 十年间距离度量学习（Metric Learning）领域的方法谱系：以马氏距离学习（Mahalanobis Metric Learning）为主线，扩展到非线性度量、相似度学习、局部度量、半监督/弱监督、稀疏/正则化变体以及面向结构化数据（树、序列、图）的编辑距离学习，给出了统一符号、经验性优缺点对比和未来挑战，是后续十年度量学习与深度度量（Deep Metric Learning）研究最重要的引用锚点之一。

解决什么真问题

在 kNN、k-means、聚类、信息检索、人脸验证、推荐系统、蛋白质功能预测等所有"靠距离/相似度决策"的算法里，距离函数本身的质量决定了性能上限。然而传统做法用欧氏距离或余弦，对真实数据的高维、各向异性、类别不平衡极不友好。手调距离或加权几乎不可能。

度量学习的核心承诺：让算法从数据中自动学出"在某种监督下让同类的点靠近、异类的点远离"的距离函数 d(x, y)。但 2013 年时这个领域已分化为：

  • 监督/无监督/半监督；
  • 线性（马氏）/ 非线性（核化、神经网络、集成）；
  • 全局 / 局部（per-cluster、per-pair）；
  • 连续特征 / 结构化数据（字符串、树、图）；
  • 理论保证（泛化界、收敛性）/ 经验有效性。

读者需要一个统一框架把它们串起来。这篇综述正是回应这一需求的"目录书 + 坐标系"。

核心方法

1. 主线：监督式马氏距离学习

马氏距离定义为 d_M(x, y) = sqrt((x - y)^T M (x - y))，其中 M ≽ 0（半正定）保证三角不等式与非负性。学习 M 是这一支的核心。

信息论类（ITML, Davis et al. 2007）：在 LogDet 散度下做正则化

min_M  D_ld(M, M_0)
s.t.  d_M^2(x_i, x_j) ≤ u  for "similar" pairs
      d_M^2(x_i, x_j) ≥ l  for "dissimilar" pairs

M_0 是先验矩阵（常取单位阵）。优点是凸优化、有闭式步长、容易加约束。缺点是 log-det 步长要调，对大规模数据投影开销大。

Logistic 判别式（LDML, Guillaumin et al. 2009）：把距离当评分，用 logistic 概率建模相似/不相似

P(y = +1 | x_i, x_j) = σ(α - β d_M^2(x_i, x_j))

经典概率判别框架，cross-entropy 优化，EM-like 优化器收敛稳健。

LMNN（Weinberger & Saul, 2009）：Large Margin Nearest Neighbor。每个 anchor x_i 强制 K 个 target 邻居比所有 impostor 更近

min_M  Σ_i Σ_j∈N(i) d_M^2(x_i, x_j) + C Σ_i Σ_j∈N(i) Σ_l (1 - y_il) [1 + d_M^2(x_i, x_j) - d_M^2(x_i, x_l)]_+

hinge-style 大间隔，对 kNN 性能提升显著，但非凸（半正定约束 + hinge），常用 SDP 求解或投影梯度。

松散的 PSD 约束：MMC（Xing et al. 2002）通过 eigendecomposition 把 M 投影回半正定锥，简单但慢；后来的方法多用 Bregman 投影或流形优化。

2. 非线性度量学习

线性 M 等价于"在原空间做线性变换后再用欧氏距离"，表达能力有限。三条非线性路径：

核化（Kernelized Metric Learning）：用核函数 k(x, x') 隐式升维，学 M 在核空间的形式。代表：KLMNN、KITML。优点是理论干净，缺点是核矩阵 O(n²) 存储，扩展性差。

多局部马氏距离（Local Metric Learning, LVMML）：把数据分簇，每簇一个 M，预测时根据输入选哪簇的 M。代价：K 个 M 矩阵存储和聚类质量敏感。

深度度量（Deep Metric Learning, Siamese/Triplet Nets）：综述发表于 2013 年所以仅用一节前瞻式提及（当时 Siamese Network 已在签名验证崭露头角）。2014 年 FaceNet / Triplet Loss 爆发后该方向独立成一支，本综述作为引文锚点仍被反复回引。

3. 相似度学习（Similarity Learning）

直接学对称函数 s(x, y)，放弃距离公理（如三角不等式）。代表：基于 pairwise 比对的人脸/图像检索、用 boosting/RBF 网络训的相似度。优势是表达力更强，劣势是没有距离的"传递闭包"性质，索引和检索算法不能复用。

4. 半监督 / 弱监督

利用未标注数据或 cluster side info：

  • Semi-supervised：构造图拉普拉斯正则 Σ_(i,j) w_ij d_M^2(x_i, x_j)，强制距离函数平滑于数据流形。
  • For Pairwise Constraints (Must-link / Cannot-link)：在聚类语境下给定少量成对约束学习 M。
  • 基于概率模型：把 M 看作高斯混合的协方差逆，从生成式角度学。

5. 结构化数据上的度量学习

这是 2013 年综述相对新颖的章节：

  • 字符串/序列上的编辑距离学习：经典 Levenshtein 用字符替换/插入/删除代价固定或简单加权，综述讨论了 learn-to-rank 风格的代价学习（McCallum 等、Lehalle 等）。
  • 树/图上的编辑距离：基于树核或图核的扩展，使用光谱方法（spectral graph distance）作为可学习的目标。
  • 核与嵌入的统一视角：用图核（Weisfeiler-Lehman、Propagation kernels）作为"隐式可学习度量"。

6. 理论保证

综述对每个家族的泛化界、样本复杂度做了对比：

  • 马氏距离学习 PAC 风格界由 Jain et al. (2009) 等给出，依赖矩阵的秩与谱界。
  • 局部/集成方法的界松一些。
  • 半监督方法的界依赖流形假设的合理性。

关键实验与数据

作为综述，本文不主推单一 SOTA，而是给出"经验性观察"：

  • 在 UCI 标准数据（Iris、Wine、Sonar 等）上：LMNN、LDML、ITML 三者分类准确率差距通常在 1-3% 之内，选择依据更多是"训练数据规模、是否要 PSD 投影、是否需要概率输出"。
  • 在人脸识别（Labeled Faces in the Wild, LFW 早期版本）：监督马氏距离已能把 LFW 准确率从 60+% 推到 80%+，但离深度方法的 99%+ 还很远——这是综述发表后两年内被深度度量完全刷榜的领域。
  • 字符串编辑距离学习在 OCR 词形校正上，比固定 Levenshtein 在 WER 上能省 1-3 个绝对点（具体数字原文未给统一 benchmark）。

⚠️ 数字说明：综述实验数字均为 2013 年前后的经验性观察，未在统一 benchmark 下做严格对照；UCI/LFW 数字区间与当时 State-of-the-Art 一致，但 2026 年已严重过时，建议仅作方向性参考而非绝对值引用。

亮点与局限

亮点

  1. 统一符号体系：综述提出了一套统一表示相似对 S = {(i,j): y_ij = +1}、不相似对 D = {(i,j): y_ij = -1} 的符号体系，让十几年工作在符号上互通。
  2. 谱系完整：从 2002 Xing 到 2013 同期工作几乎全部覆盖，并把"结构化数据"这一支首次系统整理。
  3. 优缺点对偶比较：每个家族一节"pros / cons / when to use"，是 10 年综述里少有的工程友好型总结。
  4. 前瞻性章节：对深度度量、半监督、概率图模型与度量学习的交叉给了方向性判断，部分预言后来成为现实。
  5. 泛化界讨论：把"学出来的 M 在 unseen 样本上能否保持"作为独立章节，对后续的理论工作有承接。

局限（反方 / 边界段）

  1. 2013 年截止：深度度量学习（FaceNet、Triplet、Siamese、Contrastive、Proxy-NCA）几乎全部在 2014-2017 才爆发，本综述仅作前瞻式提及，未覆盖后来十年最重要的进展。
  2. 实验数据偏小：基准多为 UCI 级小数据集（10² - 10⁴ 样本），与今天 ImageNet-1M 级别对比不在同一量级。
  3. 未提供统一 benchmark 代码：不同方法实现分布在 5+ 不同的作者仓库，今天想复现全部方法做公平对比仍需重写。
  4. 结构化数据章较薄：编辑距离学习在 NLP 上的应用（命名实体匹配、实体对齐）本综述只是引子，2020 年后 STR 等深度方法完全改写了该子领域。
  5. 未深入讨论计算复杂度：大规模数据下 LMNN 求解的 O(n³) 复杂度、ITML 的迭代投影在大数据上的不可行性，综述只是点到即止。

对工程落地的启发

  1. 小数据 + kNN / k-means 场景：先试 LMNN 或 ITML，比直接训深度模型快 10-100 倍。LMNN 用 metric-learn 库（Python）一行 API。
  2. 概率输出需求：选 LDML（logistic 判别），因为它天然输出"是否同类"的概率，方便做拒绝与阈值。
  3. 类别分布极度不平衡：考虑局部度量（per-cluster M），但要承担聚类失败的代价；或直接走"proxy anchor"系深度方法。
  4. 结构化数据（字符串 / 树 / 图）：如果不能用 BERT 类的预训练 embedding，先用编辑距离学习做 base，远比固定 Levenshtein 准。
  5. 大规模 + 高维：综述里的线性方法不适用，应跳到 deep metric（FaceNet, Proxy Anchor, SupCon）；2013 综述作为原理基础。
  6. A/B 测试设计：用度量学习前后，kNN/聚类对样本的"投票分布"会变化，建议在 ablation 里加"保持算法不变，仅换度量"的对照。

与同方向工作的关系

  • 同年代对比：
  • Yang & Jin (2006) 综述偏 SVM + metric learning 的判别式视角。
  • Kulis (2012) 教程更偏核度量，方法覆盖窄。
  • 本文是覆盖最广、理论 + 实践双轨最完整的一份。
  • 后续综述：
  • Deep Metric Learning to Rank (2019, Roth et al.)、A Survey on Deep Metric Learning (2020, Musgrave et al.)：聚焦深度时代的方法论（Contrastive、Triplet、Proxy-NCA、SupCon、ArcFace）。
  • 综述 [1306.6709] 被这些后辈综述一致列为"前期工作的核心参考"。
  • 代表后续工作：
  • FaceNet (2015)：把度量学习推到亿级人脸检索。
  • DML/Proxy-NCA / SoftTriple (2019-2020)：处理 Triplet 收敛与类不平衡。
  • SupCon (2020)：把 contrastive loss 简化到 batch 级别，与度量学习中的"大间隔判别"思路一脉相承。
  • 结构化数据分支：
  • String Transducer / Edit distance learning (Ristad & Yianilos, 1998) 是经典先驱；
  • 神经编辑距离 / String Embedding (2018+) 把字符串度量迁移到深度。

适合谁读

  • 机器学习研究生：想搞清楚"为什么 Mahalanobis 不是个玄学"的人，这篇是必读坐标。
  • 传统行业算法工程师（金融风控、推荐冷启动、异常检测）：当数据量小（10³ - 10⁴）但特征异质时，度量学习仍是最稳妥的 baseline。
  • 做检索 / RAG / 向量库选型的工程负责人：度量学习是 vector search 的灵魂，理解 LMNN/ITML 帮你判断"HNSW + cosine"是否真的够用。
  • 深度度量研究者：写新论文时引言里"早期度量学习"那段的权威引用。

一句话总结

[1306.6709] 是 2013 年度量学习领域的"目录书 + 坐标系"，用 59 页把十年工作装进马氏距离学习、非线性、相似度、半监督、结构化五条主线，配统一符号、经验性优劣对比与未来挑战；它不是新方法的发明，而是后来所有度量学习论文的引文锚点——读完这篇再去读 Deep Metric Learning 综述会事半功倍。

不确定处

  • 综述实验数字（UCI 1-3% 差距区间、LFW 60+%→80%+）均为 2013 年前后数据，2026 年已严重过时。
  • 各方法消融（仅 MCMC vs ITML vs LMNN 各自贡献）在综述中以经验性描述呈现，无系统消融实验表格。
  • FaceNet(2015) / SupCon(2020) 等后续工作如何受本综述影响，无定量分析。

工程落地与核查（Jay）

实际系统怎么用

  1. Python 库首选 metric-learn： ```python from metric_learn import LMNN, ITML, NCA # LMNN（适合 kNN 下游） lmnn = LMNN(k=5, learn_rate=1e-7) lmnn.fit(X_train, y_train) X_test_transformed = lmnn.transform(X_test)

# ITML（适合有 Must-link/Cannot-link 约束） from metric_learn import ITML itml = ITML() itml.fit(X_train, constraints_S, constraints_D)

# kNN 做下游分类 from sklearn.neighbors import KNeighborsClassifier knn = KNeighborsClassifier(n_neighbors=5, metric='euclidean') knn.fit(X_test_transformed, y_test) `` -metric-learn支持 LMNN、ITML、NCA、SDML、LSML 等主流算法，API 统一，文档完整。 - **注意**：metric-learn` 最后维护于 2020 年，Python 3.8+ 偶有 compatibility 问题，建议用 conda 或 Docker 隔离环境。

  1. 向量数据库选型（现代 RAG / 检索场景）： - 2013 年的度量学习→今天等价于 ANN（Approximate Nearest Neighbor）索引选型。 - cosine（余弦）是最常用的"朴素度量"——但它对各向异性数据效果差（高维稀疏文本embedding 的常见问题）。 - 用 LMNN/ITML 学出的 M 替换 cosine 等价于：在 HNSW / FAISS 之前，先把向量空间"掰直"。 - 现代替代：对比学习（SimCSE、CLIP）+ HNSW 的效果通常优于手工度量学习。

  2. 人脸/图像检索（2019 年后推荐直接用 ArcFace）： - 本综述的 LMNN/ITML 在 LFW 上推到 80%+，ArcFace 在 LFW 可达 99%+； - 工程路径：直接用 InsightFace（ArcFace 实现）+ faiss.IndexFlatIP，零调参，效果碾压所有线性度量学习方法。

  3. 结构化数据（字符串/实体匹配）： - 综述的编辑距离学习在 2026 年已被 BERT-style embedding 大幅替代； - 推荐 pipeline：Dirty-Tags / Starmie 实体匹配框架（2020+）>> 手工编辑距离学习； - 快速 baseline：用 rapidfuzz 库（Python）做字符串相似度，比 metric-learn 里的字符串方法快 10-100×。

坑位清单

坑点 描述 缓解方案
LMNN O(n³) 复杂度 N=10K 时训练耗时数小时，N=100K 时基本不可行 先 PCA 降维到 d≤50；或换 NCA（O(nd²)）做近似
PSD 投影不稳定 LMNN 的 SDP 投影在数值不健康时 NaN 用 metric-learn 的 LMNN(sgd=True)（随机梯度版），或换 ITML（有闭式闭式投影）
小数据容易过拟合 M 监督式度量学习依赖正负样本对数量，样本少时 M 病态 增加 Must-link/Cannot-link 约束数量；或加 LogDet 正则（ITML）
深度时代降级 2013 年方法在图像/NLP 上已被深度度量完全超越 仅用于"快速 baseline + 可解释"场景；主任务切深度模型
语义 vs 字面 度量学习学的是"特征空间距离"，对语义相似但字面不同的样本无效 结合 contrastive learning 或 cross-encoder 做二阶段：metric-learn 粗排 + BERT cross-encoder 精排

最小可跑命令（metric-learn 路径）

pip install metric-learn scikit-learn numpy

python << 'EOF'
import numpy as np
from metric_learn import LMNN
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

X, y = load_iris(return_X_y=True)
X = StandardScaler().fit_transform(X)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, random_state=42)

# 学度量
lmnn = LMNN(k=3, learn_rate=1e-7)
lmnn.fit(X_tr, y_tr)
X_tr_mahal = lmnn.transform(X_tr)
X_te_mahal = lmnn.transform(X_te)

# 下游 kNN
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_tr_mahal, y_tr)
acc = knn.score(X_te_mahal, y_te)
print(f"LMNN+kNN accuracy: {acc:.3f}")

# 对比：原始空间
knn_raw = KNeighborsClassifier(n_neighbors=3)
knn_raw.fit(X_tr, y_tr)
acc_raw = knn_raw.score(X_te, y_te)
print(f"Raw kNN accuracy: {acc_raw:.3f}")
EOF

核查备忘录

  • 实验数字均为历史快照：UCI/LFW 数字仅反映 2013 年前后的技术状态，不应用于 2026 年技术选型的绝对参考。
  • metric-learn 库状态：2020 年后更新稀疏，使用前确认 Python 版本兼容性；生产级使用建议封装成独立 Docker 镜像。
  • FaceNet (2015) / ArcFace (2018) 关系：本综述作为 FaceNet 之前的方法论基础；两者之间无直接数字可比性（因为不是一个年代的技术）。