第2章 主流机器学习技术进展
2.1 度量学习
度量是计量的准则。脱离度量，收集的数据、分析的结果也就丧失了物理意义和现实指征。而距离的度量对众多机器学习方法的性能都起到了决定性作用：例如在分类方法中，K近邻分类器、使用了高斯核的核方法；在聚类方法中，K均值聚类、谱聚类方法都与距离度量密切相关。
一般来说，对于任意样本x, y, z而言，距离度量函数需要满足自反（任意样本到自身的距离为0）、对称（x到y的距离等于y到x的距离）、非负（任意样本对之间的距离大于等于0）以及直递（三个样本之间的距离满足三角不等式）等性质。为了适应不同的具体应用场景，人们提出了诸如闵可夫斯基距离（欧几里得距离、曼哈顿距离、切比雪夫距离均为其特例）、马氏距离、海明距离等距离度量函数，并针对某些特定问题，提出了一些衍生距离度量，例如，动态时间规整距离DTW[4], 推土机距离EMD[5]等。
随着机器学习应用面的日益拓展，通过人工设计或定义特定的衍生距离度量函数未必吻合面对的问题，因此，通过学习获得问题相关的度量成为研究主题，卡内基梅隆大学机器学习系的邢波教授于2003年提出了距离度量学习[6]。在随后的10余年里，各类距离度量学习方法不断被提出，并在诸如社交网络连接预测、强化学习的状态连接学习、信息检索与推荐、身份验证、甚至医疗效果评估等方面都获得了广泛应用。
对距离度量学习的研究首先始于对马氏距离的深入探讨。对于任意两个d维样本
，其马氏距离的平方定义为
.
其中M是度量矩阵，并且为了保持距离的非负对称性，M应当为对
3
称半正定矩阵。一般的距离度量学习针对度量矩阵M展开。例如：E. Xing等人提出的距离度量学习方法在已知某些样本在语义层面相似、某些样本相异的语境下，通过引入必连（must-link）和勿连（cannot link）约束集概念（分别记为和，即相似样本组成的样本对属于必连约束集、相异样本对属于勿连约束集），学习出一个满足给定约束的度量矩阵，为此设法学到一个M，使相似样本间距离尽量小、同时相异样本间距离尽量大，即优化如下式所列的约束优化问题[6]：
其中
限定M半正定。考虑到度量矩阵的对称正定性，必然存
，也即对度量矩阵M的学习，等效于学
在正交基P，使得
习一个线性空间变换矩阵P。更进一步地，若M是一个低秩矩阵，那么存在正交基
，
，该正交基可以作为降
维矩阵使用。也即低秩距离度量学习可以衍生出一个降维方法。图2-1给出了对距离度量学习（等效于对空间进行线性变换）前后3近邻分类结果变化的示意图。
图2-1 距离度量学习前后3近邻分类效果示意图，问号为测试样本，训练样本分属于红、黑两个类别。左侧为各向同性的欧氏空间，测试样本根据多数投票应当分类为黑；右侧为度量学习后的空间，可以发现某些特征组合对近邻选取的作用得到了放大/缩小，从而导致3近邻分类结果出现差异，分类为红。
4
必连、勿连约束往往来自于样本的标记信息，而且约束所有的样本，故而使用必连、勿连约束的距离度量学习方法往往是全局度量学习方法，此类方法的代表还有：将必连约束刻画为等价关系的相关成分分析[7]；使用对数行列式(logdet)差异度作为正则项的信息论度量学习[8]；全局距离度量学习也被多个知名研究团队推广到在线学习环境
[9][10]
。
图2-2 LMNN学习前后，黄色圆点为同类训练样本，其他异色方块为类别不同的样本。LMNN学习得到的度量旨在局部区域将同类样本点拉近、异类样本点排斥开，并在同类和异类样本之间建立一个边界区域以便于kNN取得较好的分类效果。
不同于这些全局度量学习方法，Weinberger和Saul提出了一种利用邻域内三元关系进行度量学习的方法LMNN[11]，图2-2给出了LMNN方法的直观示意。在LMNN中所有的约束关系都限于某个样本的局部邻域，故此类方法也被称为局部距离度量学习方法。自LMNN提出后，局部距离度量学习方案得到众多研究者的青睐，多种扩展方案被分别提出，例如，能处理多任务的mt-LMNN[16]，可在不同集簇中学习多个度量的mm-LMNN[12]等；在局部距离度量学习方面，Huang等人提出了能够处理一定噪音和错误的鲁棒度量学习方法
5
RML[13]；Chechik等人借鉴LMNN的思想，直接对内积形式的相似度利用局部约束加以学习，并将相关算法运用于大规模图像检索，取得了很好的效果[14]；利用与局部距离度量学习类似的思想，研究者不仅针对马氏距离度量矩阵进行学习，甚至对前述的EMD距离进行了学习，例如-LMNN就针对与直方图类特征对应的EMD距离进行学习[15]；在局部信息和性质的利用方面，有些研究者甚至为每个样本都学习了合适的距离度量[16]。
随着数据收集手段的提升，大数据时代已经开启。在大数据情境下，距离度量学习和降维之间的关系得到了研究者的关注。事实上，早在2003年Goldberger等人提出的NCA一文中就明确指出距离度量学习和降维之间的关系[17]，Bellet等人在2005年就明确指出：几乎每种线性距离度量学习方法都对应着一类降维策略[18]。在意识到距离度量学习和降维的关系之后，研究者们提出了很多能够直接进行降维或者利用降维能力简化计算的距离度量学习方法。例如，Shi等人提出在有限基上进行距离度量学习，其中仅需学习一组基的线性组合系数即可，从而消减了距离度量学习的计算量[19]。
值得注意的是，除了降维之外，距离度量学习研究者们也设计出了独到的高维数据处理方法，如Qian等人于2014年提出了一种基于随机投影的距离度量学习方法，通过随机投影降低数据维度，并通过对偶空间的基重构获得原空间的距离度量[20]；Schultz和Joachims、以及Gao等人都提出了学习一个对角距离度量矩阵代替学习完全的度量矩阵的替代方案等[21][22]。此外，最近兴起的稀疏学习技术在距离度量学习研究中也获得了运用[23]。
距离度量学习同样在计算机视觉、信息检索和生物信息学相关领域受到关注。在计算机视觉领域，距离度量学习除了被用于图像分类
[24]
、物体识别[25]、视觉追踪[26]之外，还在一些计算视觉的本质问题，
如图像表示方面等，被加以利用；信息检索的结果对距离和相似度的
6
定义十分敏感，因此这方面的工作也相对丰富[27][28]；对DNA和蛋白质分子的结构分析涉及诸如编辑距离和DTW方面的研究，度量学习在这些特殊距离度量处理方面也有对应的研究工作[29][30]。
2.2 多核学习
核方法是机器学习中一类强有力的统计学习技术，被广泛应用于分类、回归、聚类等诸多领域。核选择是核方法的关键内容，因其是提高核方法泛化性能的重要一环。多核学习（Multiple Kernel Learning，MKL）通过利用多个基本核的组合代替单核，将核选择问题转化为对组合系数的选择，有效地改进了核方法。其最早应用于生物信息学领域，例如在蛋白质功能预测与定位、蛋白质分子间的交互预测等问题中，由于来自异构源的数据具有不同的特性，可以通过多个基本核矩阵的线性组合实现异构数据源的融合，基于此训练分类器取得了很好的性能。
构造多核模型，最基本的方法就是考虑多个基本核函数的凸组合：
K(x,?)??i?1?iKi(x,?)，?i?0，?i?1?i?1
MM其中Ki(x,?)是基本核函数，M是基本核的总个数，?i是组合系数，条件?i?0可以确保由此产生的Gram矩阵是半正定的。因此，在MKL框架下，样本在特征空间中的表示问题转化为基本核与组合系数的选择问题[31]。在这个由多个特征空间构建的组合空间中，利用了各个基本核的特征映射能力，通过将异构数据的不同特征分量利用对应的核函数进行映射，使数据在新的特征空间中得到更好的表达，能显著提高分类性能[31]。MKL的本质问题就是，如何得到这个组合的特征空间，即如何通过学习得到组合系数[31]。近年来，研究者们提出了一系列MKL算法，主要侧重于算法的优化求解和性能提高两个方面。
Lanckriet等人考虑组合系数和分类器参数的联合优化，提出了基于二次约束二次规划问题的MKL算法[32]，但是算法仅适用于具有少
7