漫谈度量学习（Distance Metric Learning）

算法进阶

发布于 2023-10-07 11:14:49

2720

发布于 2023-10-07 11:14:49

1 前言

上图为 2018 年 4 月在杭州阿里中心听 Michael Jordan 讲座时所摄，他本人也是 distance metric learning 研究的开山鼻祖之一。当时只知大佬名气、不知大佬风范，现如今读起文章来，才觉得很幸运曾经有过的时空上的交集，希望以后能努力做好自己的研究。

在机器学习中，distance metric learning（也称 metric learning，度量学习）是一个很典型的任务，通常与很多熟知的 metric-based methods（如 KNN、K-means 等）结合起来使用以实现分类或者聚类，效果通常非常不错。很多机器学习方面的研究已经发现：如果 distance metric 学得足够好，学出来的 metric 结合最简单的 1NN 分类器其结果在很多任务上完全可以媲美很多很复杂的分类器，甚至在某些任务上还能达到 SOTA 的效果。此外，大部分 distance metric learning 的方法其数学模型和求解方法定义得都很清楚，让人看起来很舒服，也给后续研究可能进行的拓展留足了想象空间。

在去年下半年有一小段时间中，我因为某些原因曾经短暂的接触过 distance metric learning，当时是完全小白的状态，但无奈需要解决手里的问题，试图去检索了很多资料和信息。这个学习过程很痛苦，主要是由于资料大多零零散散，也没什么高质量的信息，看到的很多中文博客写的并不友好，兜兜转转一圈还是不知道如何入手。虽然我现在因研究方向调整已经不再做这个方向了，但还是希望留下这篇文章：一是分享一下自己从初学者角度对 distance metric learning 的理解，供大家参考；二是把自己之前花了很多时间找的我个人觉得很有价值的资料和 references 分享给后来者，希望对感兴趣的伙伴有帮助。

本文从传统的 distance metric 开始介绍、聊聊为什么要从数据中学习出一个 metric 以及 distance metric learning 的简单历史，并且以 LMNN 为例谈谈其作为 distance metric learning 经典方法之一的特点，最后再简单总结并把我之前觉得很有价值的资料和 references 附在文末分享给大家。

要想理解 distance metric learning，故事得从其中的“distance”开始讲起。

2 Distance

所谓的距离，通常指的是两个向量（空间中的两个点）之间的距离。那么，如果两个向量之间的距离很大意味着什么？距离很小又意味着什么？事实上，距离还可以从另外一个角度来理解：相似度。

在机器学习任务中，通常不同的向量代表着不同的样本，换句话说如果两个样本之间的距离很小，我们可以理解为两个样本的相似度很高，反之如果两个样本之间距离很大，其之间的相似度就很低。如果是在分类任务中，借由距离和相似度的概念我们有一个很直观的认识就是：相似度高（距离小）的样本，其属于同一类的概率会大于相似度低（距离大）的样本属于同一类的概率。KNN 无疑就是这种理念的最佳践行者，其本身蕴含的思想就是基于距离来对样本进行分类。这种思想也启发、指导了很多 distance metric learning 方法的设计和实现。

提到距离，就必须说说距离度量的方式，也就是说：我们该如何计算两个向量之间的距离？

1. 我们最常用最熟知的距离度量方式无非就是欧氏距离（Euclidean distance），两个向量和之间的欧氏距离被定义为：。因为与大家早在高中阶段接触的二维乃至三维向量距离计算方式相同，欧氏距离理解起来很容易。但是欧氏距离同样也存在其最显著的缺点：欧氏距离只能建立样本间点对点的联系、处理长度相等的数据。如果输入数据长度不相等，或是两个向量在时间轴上有偏移，那么欧氏距离的效果一般就会较差，这种情况下 Dynamic Time Warping（DTW）距离是一个很好的替代品，关于 DTW 距离之前写过一篇文章，供大家参考：

度量时间序列相似度的方法：从欧氏距离到DTW及其变种

2. 除了欧氏距离，常用的距离度量还有闵氏距离（Minkowski distance），其被定义为两个向量的 p 阶距离，可以写成：，很明显，欧氏距离就是闵氏距离中时的特例。当时，其为曼哈顿距离（Manhattan distance），也就是对应点之间相减取绝对值的算法。

3. 另外一个常见的距离度量是由印度统计学家马哈拉诺比斯（P. C. Mahalanobis）提出的，因此被称为马氏距离（Mahalanobis distance）。马氏距离同样也是定义在两个向量上，这两个样本点来自同一个分布。马氏距离可以写为：，其中是这个分布的协方差矩阵。显然，当协方差矩阵时，马氏距离退化为欧氏距离。

在机器学习的众多应用中，还有很多很多距离度量的方式，如：余弦相似度（利用向量夹角的余弦衡量两个向量的距离）、Hamming distance（衡量两个等长字符串之间的距离）、KL 散度（衡量两个概率分布间的距离）、JS 距离（基于 KL 散度的一个对称的距离度量方式）等。此处空间有限不再细说，感兴趣的伙伴可以自行了解：全面归纳距离和相似度方法(7种)

很显然，对于两个样本向量和，如果我们利用不同的距离度量方式，得出的距离也就完全不同了。这同时也提醒我们，度量样本间距离的方法对于我们的结果有着至关重要的作用。这其实也就是 distance metric learning 最核心的 motivation：希望从训练数据中学习出一个最适合这个任务的 distance metric，以期达到最好的效果。

3 Distance metric learning 与 LMNN

distance metric learning 相关的研究大约始于二十年前，要认真算起来的话，其代表性的开山之作应该是 2002 年 Eric Xing 与 Andrew Ng、Michael Jordan 等人（真是每个名字都是大佬啊 hhh）合作在 NIPS 上发表的题为“Distance metric learning with application to clustering with side-information”的论文：

https://proceedings.neurips.cc/paper/2002/file/c3e4035af2a1cde9f21e1ae1951ac80b-Paper.pdf

这篇文章除了作为 distance metric learning 的开山之作以外，还创造性的将 metric learning 的过程构造成了一个凸优化问题，这给当时初生的 metric learning 的可靠性和稳定性提供了很大的保障和帮助。

在这篇文章中，他们定义 distance metric 并且从 side-information 中学习出 metric 的做法在今天其实可以被称为 mahalanobis distance metric learning。顾名思义，其原因是直接借用了马氏距离中度量距离的方法，其距离可写成此形式：，其中是一个对称的半正定矩阵，而在马氏距离中是协方差矩阵的逆。这种构造方法还可以从另外一个角度来理解，由于是一个对称的半正定矩阵，则有：

很显然，这实际上就是对原样本空间利用矩阵进行线性投影后在新样本空间内的欧氏距离！而 distance metric learning 的目标，就是学出这样的矩阵（或矩阵）。到这里可能有伙伴会好奇，为什么不在原样本空间用欧氏距离，一定要经过一个线性投影呢？答案很简单，在原样本空间里我们无法通过欧氏距离来很好的区分不同类别的样本，原样本空间中不同类别的样本混在一起，导致其欧氏距离很小，如果此时我们用一些 metric-based 的分类器效果就很差。

为了提高分类准确率，我们对原样本空间做线性投影后，在新的空间可能不同类别的样本就会分得比较开，此时用”欧氏距离“（投影后的新空间内）效果就会比较好。下图一看便知：

▲ metric learning的几何直觉

当然，不是所有的 distance metric 都是线性的，有线性的、也有非线性的，有监督的、也有非监督的。本文只为简单介绍 distance metric learning 的概念，更多的内容留待感兴趣的伙伴自由探索。在过去二十年 CS、AI 领域的研究中，涌现出了众多 distance metric learning 的经典方法，例如 NCA、LMNN、ITML 等，还有后续的一系列 online learning、linear similarity learning、nonlinear metric learning、multi-task metric learning、deep distance metric learning 等等。20 年前的方兴未艾，20 年后的浩如烟海，大致就是如此了。

在此我以我个人比较熟悉的 LMNN 方法为例，给大家分享一下该方法中 metric learning 的思想。LMNN 是 Large Margin Nearest Neighbor的缩写，原文最初发表于 2005 年的 NIPS，后来 2009 年在 JMLR 上补发了长文，逻辑很清晰、也很易懂，提纲挈领的同时又不失细节，算得上小半篇 review，强烈推荐：

https://www.jmlr.org/papers/volume10/weinberger09a/weinberger09a.pdf

LMNN 方法的核心思想也比较简单：在 LMNN 之前的很多方法（如 Eric Xing 等人的 MMC）约束都很强，要求同类别样本之间差距小而不同类别样本之间差距大，这在实际中是很难实现的。而且结合最近邻算法的思想，影响分类结果的就是最近的几个样本的类别，没有必要去要求那么强的约束，我们只要实现利用 metric 把离每个样本最近的几个样本都拉近到同类别，不就可以了吗？LMNN 的思想可以用下图来理解：

▲ Weinberger K Q, Saul L K. Distance metric learning for large margin nearest neighbor classification[J]. Journal of machine learning research, 2009, 10(2).

在左图所示原空间中，以样本为例，离其最近的三个同类别样本（target neighbors）形成的圈子中，有其他类别的样本存在，这意味着如果在原空间使用欧氏距离结合 KNN 算法，容易受到所谓的入侵者（impostors）的影响。所以 LMNN 的核心思想就是通过学习一个 distance metric，使其所对应的线性投影矩阵投影到新空间后，最近的数个同类别样本（target neighbors）们被拉得更近、而每个样本的入侵者（impostors）都被推得更远，以致最近的数个同类别样本（target neighbors）围成的圈与入侵者（impostors）的距离有一个边界（margin）（如上面右图所示）。这样的话，经过 LMNN 学习到的 distance metric，采用 KNN 的算法来进行分类，就会有很好的效果了~

那么，LMNN 是如何实现这一推一拉的呢？这得益于 LMNN 算法中巧妙的 loss function设计。LMNN 算法的 loss function 分为两个部分，一个部分负责拉近最近的数个同类别样本（target neighbors），一部分负责推开每个样本的入侵者（impostors）。

负责拉近的部分被构造为：

▲ j -&amp;gt; i 代表j是i的target neighbors

很显然，这部分通过惩罚同类别样本间的大距离达到拉近同类别样本的效果。

负责推开的部分被构造为：

▲ j -&amp;gt; i 代表j是i的target neighbors

其中代表标准的 hinge loss。如果是的 target neighbors，，那自然就不用推开了，此时这一项 loss 为 0；如果是的 impostors，，如果括号内大于 0，意味着在投影后的新空间中，仍然有 impostors 入侵到 margin 之内。所以此项 loss 通过惩罚括号内大于 0 的项（impostors 入侵进入 margin）来实现推开的 impostors 的功能。

最终这一推一拉利用一个参数实现了平衡和调整：

以上就是关于 LMNN 思想的简单介绍，当然学习 metric 的过程还需要一些构造优化问题并求解的过程，那又是另外一个故事了。事实上在众多的 metric learning 方法中，很多都有相近的思想（拉近同类、区别异类），只是大家的 formulation 不同，衍生出了不同的工具和方法。感兴趣的伙伴可以自行了解其他各种有趣的方法。

4 Distance metric learning 在工程应用中的实践

前文提到，我自己短暂的花了一段时间尝试了 distance metric learning 的学习和实践，这里以我自己之前解决的小问题作为一个 toy example，跟大家分享一下在非 CS 的工程学科中 distance metric learning 的大致实践过程。

为什么做：在智能制造的大背景下，随着传感器、控制、计算机等一系列技术的发展，各种过去无法被记录的制造过程中的数据现在可以被各种各样的传感器记录下来了，这给我们提供了很多数据驱动的制造过程分析和决策的机会，制造产品的质量预测与监控就是其中重要的一个分支。

过去传统的质量控制大多都是 post-process 的，也就是说得等产品完成很多工序直到质检工序时才被发现，而某些产品质量可能在其中某一个工序就出问题了，可这些有问题的产品依旧经过了后续的很多工序加工，这造成了很大的资源和成本浪费。所以我们需要一个 in-process 的质量监测工具帮助我们根据制造过程数据及时判断出哪些产品可能是有问题的、及时发现并防止浪费。

做什么：在某个特殊的产品制造过程中，行业专家告诉我们制造过程中的某种数据（记为）是跟产品的质量有重要联系的。于是，我们借由传感器收集到了多个样本制造过程种每个样本的数据，根据现有制造产线后续的质检工序，制造方为我们提供了这些样本的真实标签（记为，两种：合格品和不合格品）。

这个问题中有两个小的 challenges：由于制造过程中的随机性，每个样本的数据其长度大多是不相等的；此外，我们收集数据的样本中，样本量较为有限，且合格品的数量远大于不合格品的数量，比率大概在 20:1 左右，换句话说，这是个样本量有限的不平衡数据集。而我们的目标就是根据收集到的数据来构建一个预测产品质量是否合格（标签）的模型，这样就可以针对每个制造过程中的新样本根据收集到的过程数据实现 in-process 的质量预测和监控了。

怎么做：前期我做了其他方法的很多探索，就不在此一一赘述了，此处直接阐述利用 distance metric learning 的做法。在将样本简单划分为 training set 和 test set 后，由于 distance metric learning 不能处理非等长的数据，我先随机选取了一个样本作为参考样本利用 DTW 将其他所有样本（包括 training set 和 test set）进行拉齐处理（这里有一个 trick：利用各种 MATLAB 或 python 内嵌的包确实可以根据 DTW 拉齐两个不等长的样本，但拉齐后的长度跟两个样本的原长度都不相等，所以我后面自己写了一段代码解决了），这样就得到了等长的数据集。如下所示：

▲ 利用DTW拉齐两个不等长样本

尝试过多种 metric learning 方法后，我最终使用了经典的 LMNN 方法在 training set 上学习了特定的 distance metric，并将其应用到 test set 上，结合 1NN 分类器最终输出预测的样本标签。由于样本量有限，我对整个数据集做了 100 次 random split，最后取平均的 performance。以上就是我之前所做的对于不等长的数据集如何进行 distance metric learning 的基本思路。

但是当时我觉得 performance 还是不够好，于是引入了另一个基于 DTW 拉齐处理的 trick：在拉齐过程中，我针对每一个 split 下的 training set 和 test set 利用多个样本作为参考样本来进行拉齐，这样经过 DTW 的处理，每一个 split 下我就有了个不同长度的数据集，根据这个不同长度的数据集可以用 metric learning 学习出个不同的 distance metric，再构建个 1NN 分类器并将它们 ensembling 在一起根据个分类结果利用 majority voting 的方法最终得出预测标签。这一 trick 大大的帮助我在这一问题上提升了预测的 performance。

结果：在此我比较了三种方法：1、直接利用 DTW 距离结合 1NN 进行分类；2、先利用 DTW 拉齐、LMNN 学习 distance metric、1NN 分类；3、先利用 DTW 基于多个参考样本拉齐、LMNN 学习多个 distance metrics、多个 1NN 分类最终 majority voting。结果如下：

▲ 三种方法的分类结果对比

在 accuracy 方面三种方法都很高，但这是由之前提到的不平衡数据所造成的，而且可以由 precision, recall, F1-score 三项很明显的看出来：DTW+1NN 对于我们最关注的不合格品的分类准确度并不高。利用 distance metric learning 的确进一步改进了对不合格品的分类准确度，但最终引入的 ensembling 的 trick 帮助我们达到了整体大于 99.4% 的准确度，而且对不合格品的分类准确度超过了95%。

事实上，在解决这个问题的过程中，我尝试了很多很多方法，也曾经试图对 LMNN 的模型结构做更改，但效果都不好，最后还是老老实实把 distance metric learning 单纯的当作工具来使用。没能在理论方面做出啥贡献确实汗颜，但我想这个 toy example 的用处也正是跟大家分享 distance metric learning 的用法和其中遇到的坑和可能的解决办法，倒也恰如其分。请大佬们轻拍~