LMNN

Large Margin Nearest Neighbor Classification

提出LMNN的动机

kNN在有先验知识的情况下表现很好，但在缺乏先验知识的时候往往使用欧氏距离，这将忽略隐藏在带有标签的数据之间的统计学关系。因此比较好的一种办法就是使用DML来学习度量相似度的距离，而在LMNN中学习的就是一种马氏距离来应用于kNN中。

具体而言，LMNN试图通过在使用欧氏距离来进行kNN聚类前学习一种线性变换来增加同一类别中数据的数量，这个线性变换是通过最小化一个损失函数来获得的。该损失函数由两个部分组成，第一部分惩罚相距较大的相同类别的点，第二部分惩罚相距较近的不同类别的点。而在经过这一线性变换的空间中，使用欧氏距离进行聚类相当于在源数据所在的空间中使用马氏距离。

背景知识

DML

度量，是一个映射，该映射，对于满足以下条件：

1. %2BD(x_j%2Cx_k)%5Cgeq%20D(x_i%2Cx_k)#card=math&code=D%28x_i%2Cx_j%29%2BD%28x_j%2Cx_k%29%5Cgeq%20D%28x_i%2Cx_k%29&id=PpGGF)
2. %5Cgeq%200#card=math&code=D%28x_i%2Cx_j%29%5Cgeq%200&id=qQMik)
3. %3DD(x_j%2Cx_i)#card=math&code=D%28x_i%2Cx_j%29%3DD%28x_j%2Cx_i%29&id=avFmD)
4. %3D0%20%5Ciff%20x_i%3Dx_j#card=math&code=D%28x_i%2Cx_j%29%3D0%20%5Ciff%20x_i%3Dx_j&id=QcgDS)

如果这个映射仅仅满足前三个条件而不满足最后一个条件，那该映射是一个伪度量。当不特别指明时，提到度量，一般指伪度量。

通过计算欧氏距离并辅以一个线性变换我们可以获得一个在上的度量集合：

%3D%7C%7CL(x_i-x_j)%7C%7C%5E2_2%20%5Ctag%7B1%7D%0A#card=math&code=D_L%28x_i%2Cx_j%29%3D%7C%7CL%28x_i-x_j%29%7C%7C%5E2_2%20%5Ctag%7B1%7D%0A&id=uq6bh)

这里线性变换被参数化为，当满秩时#card=math&code=D_L%28x_i%2Cx_j%29&id=EGM5r)是一个度量，当不满秩时是一个伪度量。

针对等式1中存在的平方，使用一个平方的矩阵来置换：

任何一个这样构成的矩阵军师一个半正定矩阵，带入等式1后有：

%3D(x_i-x_j)%5ETM(x_i-x_j)%20%5Ctag%7B3%7D%0A#card=math&code=D_M%28x_i%2Cx_j%29%3D%28x_i-x_j%29%5ETM%28x_i-x_j%29%20%5Ctag%7B3%7D%0A&id=UBqXU)

这也就是所谓的马氏距离。当设定是一个单位阵时，该距离变成欧氏距离。

可以看出上述等式1与等式3的表示是等价的，这就演化出DML中两种不同的策略：学习一个线性变换或者学习一个半正定矩阵。对于前者是一个没有约束的优化问题，对于后者必须的约束是必须是半正定的。作者认为解决后者这个有约束条件的优化问题会更加容易。

在kNN中，若使用上述等式1作为距离度量，人们往往在寻找一个线性变换使得按照该距离计算的最近邻拥有相同的标签。部分先前的方法在接下来会被回顾。

特征向量方法

特征向量方法已被广泛用于发现输入空间的信息线性变换。如前文所述，这些线性变换可以产生一个Mahalanobis距离度量。即将阐述的方法之间的差异在于它们是否使用带有标记的数据来从输入空间中获得这一线性变换。

PCA

本质上来说，按照前文提及的DML思想：寻找合适的线性变换，PCA将寻找一个线性变换，该线性变换可以将原输入空间投影到一个方差最大化的子空间中。

针对其中的两个要素：线性变换以及方差的方差进行规定，映射后的数据的方差可以被写成协方差的形式：

%5ET(xi-%5Cmu)%20%5Ctag%7B4%7D%0A#card=math&code=C%3D%5Cfrac%7B1%7D%7Bn%7D%20%5Csum%7Bi%3D1%7D%5En%28x_i-%5Cmu%29%5ET%28x_i-%5Cmu%29%20%5Ctag%7B4%7D%0A&id=P6RzE)

其中指的是所有数据的均值。

根据前文所言，PCA寻找线性变换来使得映射后的方差最大化，因此可以将设定成为一个投影矩阵，由此可以得到一个带有限制条件的优化问题：

%5Cquad%20s.t%20%5Cquad%20LL%5ET%3DI%20%5Ctag%7B5%7D%0A#card=math&code=max%20%5Cquad%20Tr%28L%5ETCL%29%5Cquad%20s.t%20%5Cquad%20LL%5ET%3DI%20%5Ctag%7B5%7D%0A&id=lJ0xu)

这个问题有严格的解法，公认的的取值是协方差矩阵为首的几个特征向量。

这里，PCA是一个不使用标签的无监督学习。在kNN中，PCA可以起到将降噪的效果并降低kNN错误率，同时通过维数约简减少计算量。

LDA

首先进行一些定义。约定代表标签类别为的数据的下标（）的集合。从DML的角度来看，LDA试图寻找一个线性变换，该线性变换可以最大化不同类别的类间方差与相同类别的类内方差的比值关系，类内方差与类间方差的定义如下：

(xi-%5Cmu_c)%5ET%20%5Ctag%7B6%7D%0A#card=math&code=Cov_b%3D%5Cfrac%7B1%7D%7BC%7D%5Csum%7Bc%3D1%7D%5E%7BC%7D%5Cmuc%5Cmu%5ET_c%20%5C%5C%20Cov_w%3D%5Cfrac%7B1%7D%7BC%7D%20%5Csum%7Bi%20%5Cin%20%5COmega_c%7D%28x_i-%5Cmu_c%29%28x_i-%5Cmu_c%29%5ET%20%5Ctag%7B6%7D%0A&id=jqkLw)

其中指的是第类别中数据的均值。LDA选择线性变换以最大化类间与类内方差之间的比率，同时需要对增加投影矩阵的约束，由此可得优化问题：

%20%5Cquad%20s.t%20%5Cquad%20LL%5ET%3DI%20%5Ctag%7B7%7D%0A#card=math&code=max_L%20%5Cquad%20Tr%28%5Cfrac%7BL%5ETC_bL%7D%7BL%5ETC_wL%7D%29%20%5Cquad%20s.t%20%5Cquad%20LL%5ET%3DI%20%5Ctag%7B7%7D%0A&id=uW0AA)

这个问题有严格的解法，公认的的取值是为首的几个特征向量。

LDA与PCA不同，使用监督学习与数据的标签。但LDA可能会提取不太适合kNN分类的杂散特征。

RCA

RCA在对于数据标签的使用方面是一种介乎于PCA与LDA之间的方法。RCA使用一种叫“条块”（Chunklet）的信息，类似与分类类别的子类，但有一个特性：相同条块内的数据确实属于同一个类别，但不同条块内的数据未必不属于同一个类别。从DML的角度出发来看，本质上RCA试图学习一个线性变换，该线性变换为相关的维度分配了较高的权重，为不相关的维度分配了较低的权重，也就是说在通过这一步变换后同一类别的数据之间的距离将会变得更小，而不同类别之间的距离将会增加。因此可以很好的保留数据中相关维度的信息。规定一个条块内的协方差在（类内协方差矩阵）为：

(xi-%5Cmu_l)%5ET%20%5Ctag%7B8%7D%0A#card=math&code=C_w%3D%5Cfrac%7B1%7D%7Bn%7D%5Csum%7Bl%3D1%7D%5EL%5Csum_%7Bi%5Cin%20%5COmega_l%7D%28x_i-%5Cmu_l%29%28x_i-%5Cmu_l%29%5ET%20%5Ctag%7B8%7D%0A&id=KdVET)

在RCA中线性变化的取值为。但RCA可能会将噪声方向放大，因此在执行RCA前往往需要结合PCA降噪。

凸优化

MMC

MMC如下表示

%5Csqrt%7BDM(x_i%2Cx_j)%7D%20%5C%5C%20%5Ctext%7Bs.t%20%20%7D%20%5Ctag%7B9%7D%20%5C%5C%20%5Csum%7BIj%7Dy%7Bij%7DD_M(x_i%2Cx_j)%5Cleq%201%20%5C%5CM%20%5Csucceq%200%0A#card=math&code=%5Ctext%7BMax%20%7D%20%5Csum%7Bij%7D%281-y%7Bij%7D%29%5Csqrt%7BD_M%28x_i%2Cx_j%29%7D%20%5C%5C%20%5Ctext%7Bs.t%20%20%7D%20%5Ctag%7B9%7D%20%5C%5C%20%5Csum%7BIj%7Dy_%7Bij%7DD_M%28x_i%2Cx_j%29%5Cleq%201%20%5C%5CM%20%5Csucceq%200%0A&id=sFbiH)

由目标函数可以看出MMC的思想是提高不同类的元素之间的距离。

限制条件1确保了问题是可行且有界的，限制条件2使得M是一个半正定矩阵，这是一个凸优化问题，MMC没有超参数。

POLA

与LDA和MMC类似，POLA也试图去学习一种可以使得同类样本更接近、不同类样本更远的度量，但不同之处在于POLA显式地指明了不同标签输入数据之间的边界的大小，并且POLA可以实时训练。

在POLA中，在时刻，POLA定义一个三元组#card=math&code=%28x_t%2Cx%5E%7B%27%7D_t%2Cy_t%29&id=ZFPPV)，其中表明和是否是同同意标签的，相同时，不同时为-1。POLA通过流式输入三元组训练一个马氏距离来符合下列不等关系：

%5ETM(x_t-x_t%5E%7B’%7D)%5D%5Cgeq%201%20%5Ctag%7B10%7D%0A#card=math&code=y_t%5Bb-%28x_t-x_t%5E%7B%27%7D%29%5ETM%28x_t-x_t%5E%7B%27%7D%29%5D%5Cgeq%201%20%5Ctag%7B10%7D%0A&id=PfQ9R)

与阈值都将根据流式输入的三元组更新以保证上述不等条件成立。

上诉不等条件使得类间元素距离有了下界b+1，类内元素之间的距离为b-1，这样类间元素和类内元素之间就形成了长度至少为2的间隔。

NCA

NCA是一种将Stochastic KNN分类器与DML思想结合的产物。

在NCA中，一个样本的近邻是按照Softmax的概率分布进行抽取（这采用的Stochastic kNN中的思想），作为的参照样本，被抽取的概率为：

%7D%7B%5Csum%7Bk%5Cneq%20i%7Dexp(-%7C%7CLx_i-Lx_j%7C%7C%5E2)%7D%5Cquad%20i%5Cneq%20j%5C%5C0%5Cquad%20i%3Dj%5Cend%7Bcases%7D%20%5Ctag%7B11%7D#card=math&code=%5Cbegin%7Bequation%2A%7Dp%7Bij%7D%3D%20%5Cend%7Bequation%2A%7D%20%0A%5Cbegin%7Bcases%7D%5Cfrac%7Bexp%28-%7C%7CLxi-Lx_j%7C%7C%5E2%29%7D%7B%5Csum%7Bk%5Cneq%20i%7Dexp%28-%7C%7CLx_i-Lx_j%7C%7C%5E2%29%7D%5Cquad%20i%5Cneq%20j%5C%5C0%5Cquad%20i%3Dj%5Cend%7Bcases%7D%20%5Ctag%7B11%7D&id=huXIW)

在这里，限制了被抽取样本所可能处在的范围。所以根据上式，可以获得NCA的错误率为：

这里时，，否则等于0。

通过求导最小化错误率，也就是让按照上述概率被抽取的元素的标签尽可能一致，可以最终确定。

LMNN Model

概述

LMNN 借鉴了前文所描述的三个算法的特点：

1. 借鉴了MMC，将LMNN的参数估计也使用在半正定矩阵上的凸优化方法求解
2. 借鉴了POLA，试图将分类正确的训练集数据之间的间隔最大化
3. 借鉴了NCA，试图学习一种马氏距离来提高kNN聚类的准确率

具体地，LMNN试图学习一个线性变换来使得输入空间中的数据满足kNN中的两个特性：

1. 每个训练样本的标签都应当和和它的k个近邻的标签相同
2. 不同标签的数据应当被间隔很大地分离

这样的目的在LMNN的损失函数中得到了体现。

为了便于阐述LMNN的整体框架，再次引入若干概念。首先，LMNN是需要一些辅助信息的，这些辅助信息是在算法执行之前通过一些途径，包括相似度图或者使用欧氏距离直接进行kNN。之所以要求这些先验的知识，是因为LMNN需要基于这些先验的知识设计一个“目标邻居”来满足任意一个数据的k个近邻都拥有同样的标签这一要求的。因此，LMNN需要获得的线性变换的目标也包括了在针对输入空间进行线性变换后原本某一数据的目标邻居依然是该数据的最近邻，因此目标邻居是一开始就固定的、不会因为算法执行而改变的。使用标记表示数据是的目标邻居。这一关系并不是对称的。

目标邻居设立的目的是保证在一定范围内没有不同标签的数据点，因为某个数据点的目标邻居应当比任何其他标签的数据距离该数据点更近。更进一步的，我们称呼那些在这个不应当有不同标签的范围内的不同标签的数据为“入侵者”，粗略的来讲学习的一个目标就是最小化这些入侵者的数量。

事实上，为了使得kNN拥有更好的鲁棒性，实际学习中采用了一个更加严格的目标：尽可能地增大在目标邻居确定的范围与入侵者之间的距离，这件减少少数噪声对于算法的影响，也确定了该算法的名称：large margin nearest neighbor。

入侵者由不等式进行数学定义：

%7C%7C%5E2%5Cleq%20%7C%7CL(x_i-x_l)%7C%7C%5E2%2B1%20%5Ctag%7B13%7D%0A#card=math&code=%7C%7CL%28x_i-x_l%29%7C%7C%5E2%5Cleq%20%7C%7CL%28x_i-x_l%29%7C%7C%5E2%2B1%20%5Ctag%7B13%7D%0A&id=z1e4b)

其中，是输入的数据，是其任意一个目标邻居，是入侵者。

文章给出了一个示意图：

在学习过程中，入侵者将被推出有目标邻居确定的一定周长的区域。

损失函数

LMNN的损失函数主要包括两个部分，其中一个部分将目标邻居拉得更近，另一个将不同标签的数据推地更远。

损失函数的第一部分惩罚每个输入和它的目标邻居之间的较大的距离：

%3D%5Csum%7Bj%5Cleadsto%20i%7D%7C%7CL(x_i-x_j)%7C%7C%5E2%20%5Ctag%7B14%7D%0A#card=math&code=%5Cvarepsilon%7Bpull%7D%28L%29%3D%5Csum_%7Bj%5Cleadsto%20i%7D%7C%7CL%28x_i-x_j%29%7C%7C%5E2%20%5Ctag%7B14%7D%0A&id=vT2zK)

该式的梯度将在经过线性变换的空间中生成针对目标邻居的拉力。需要注意的是，和前文介绍的部分方法有所不同，LMNN仅仅针对目标邻居之间的大间距进行惩罚，并不是针对所有相同标签的数据之间的间距。

损失函数的第二部分惩罚不同标签的样本之间的小间距。具体而言，该部分的损失函数试图惩罚那些符号了公式13中的不等关系的数据（也就是入侵者）。引入新的变量来表示和之间的关系：当且仅当

时，其他情况均为0。第二部分的损失函数可被表示为：

%3D%5Csum%7Bi%2Cj%5Cleadsto%20i%7D%5Csum%7Bl%7D(1-y%7Bil%7D)%5B1%2B%7C%7CL(x_i-x_l)%7C%7C%5E2-%7C%7CL(x_i-x_l)%7C%7C%5E2%5D%2B%20%5Ctag%7B15%7D%0A#card=math&code=%5Cvarepsilon%7Bpush%7D%28L%29%3D%5Csum%7Bi%2Cj%5Cleadsto%20i%7D%5Csum%7Bl%7D%281-y%7Bil%7D%29%5B1%2B%7C%7CL%28xi-x_l%29%7C%7C%5E2-%7C%7CL%28x_i-x_l%29%7C%7C%5E2%5D%2B%20%5Ctag%7B15%7D%0A&id=wXKxB)

这里的是Hinge Loss：#card=math&code=%5Bz%5D_%2B%3D%5Ctext%7Bmax%7D%28z%2C0%29&id=G1EXs)，目的在于使得那些不同标签但不满足公式13不等关系条件的数据不会被惩罚，也就是不会惩罚那些在目标邻居划定范围之外的不同标签的数据点。该损失函数的梯度将会产生推力将入侵者推离。

将两个部分整合获得完整的损失函数：

%3D(1-%5Cmu%20)%5Cvarepsilon%7Bpull%7D(L)%2B%5Cmu%5Cvarepsilon%7Bpush%7D(L)%20%5Ctag%7B15%7D%0A#card=math&code=%5Cvarepsilon%28L%29%3D%281-%5Cmu%20%29%5Cvarepsilon%7Bpull%7D%28L%29%2B%5Cmu%5Cvarepsilon%7Bpush%7D%28L%29%20%5Ctag%7B15%7D%0A&id=wXyQn)

其中是用来调和平和前半部分与后半部分之间的关系的超参数，可以经由交叉验证获得比较好的取值。LMNN对于不敏感，取即可获得很好的结果。这里其实借鉴了SVM中的损失函数：正如SVM中的HingeLoss损失函数被那些接近决策超平面的数据驱动一样，LMNN中的损失函数仅仅被在每个数据由目标邻居确定的区域内的入侵者驱动，LMNN也与SVM一样可以使用核方法与凸优化。

局部距离 vs 全局距离

作者使用一个玩具数据集进行测试，该测试集类内的水平方向的方差更大，竖直方向的方差较小，但是聚类的判别更多依赖的是竖直方向的数据。NCA与LMNN可以很好的适应这一种带状的分布，其他算法如PCA，LDA等等试图收缩所有同类样本的间距使得错误率更高。

凸优化

针对上文的损失函数公式15结合前文的公式3，可以转化出损失函数的另一种形式：

%3D(1-%5Cmu)%5Csum%7Bi%2Cj%5Cleadsto%20i%7DD_M(x_i%2Cx_j)%2B%5Cmu%20%5Csum%7Bi%2Cj%5Cleadsto%20i%7D%5Csuml(1-y%7Bil%7D)%5B1%2BDM(x_i%2Cx_j)-D_M(x_i%2Cx_l)%5D%2B%20%5Ctag%7B16%7D%0A#card=math&code=%5Cvarepsilon%28M%29%3D%281-%5Cmu%29%5Csum%7Bi%2Cj%5Cleadsto%20i%7DD_M%28x_i%2Cx_j%29%2B%5Cmu%20%5Csum%7Bi%2Cj%5Cleadsto%20i%7D%5Csuml%281-y%7Bil%7D%29%5B1%2BDM%28x_i%2Cx_j%29-D_M%28x_i%2Cx_l%29%5D%2B%20%5Ctag%7B16%7D%0A&id=WBZTj)

而后可以引入一个松弛变量进而采用SDP求解。

基于能量的分类

尽管LMNN的目的是设计出一种使得kNN分类更加准确的算法，但根据前人的研究，公式16这一损失函数本身也是可以被用来估计数据的标签的。

通过针对某一数据可能的标签取值逐一计算损失函数的数值，并取得使得损失函数最小的标签作为分类的标签：

%5Csum%7Bj%5Cleadsto%20i%7DD_M(x_t%2Cx_j)%2B%5Cmu%20%5Csum%7Bj%5Cleadsto%20t%2Cl%7D(1-y%7Btl%7D)%5B1%2BD_M(x_t%2Cx_j)-D_M(x_t%2Cx_l)%5D%2B%2B%5Cmu%20%5Csum%7Bi%2Cj%5Cleadsto%20i%7D(1-y%7Bit%7D)%5B1%2BDM(x_i%2Cx_j)-D_M(x_i%2Cx_t)%5D%2B%5C%7D%20%5Ctag%7B17%7D%0A#card=math&code=yt%3D%5Ctext%7Bargmin%7D%7Byt%7D%5C%7B%281-%5Cmu%29%5Csum%7Bj%5Cleadsto%20i%7DDM%28x_t%2Cx_j%29%2B%5Cmu%20%5Csum%7Bj%5Cleadsto%20t%2Cl%7D%281-y%7Btl%7D%29%5B1%2BD_M%28x_t%2Cx_j%29-D_M%28x_t%2Cx_l%29%5D%2B%2B%5Cmu%20%5Csum%7Bi%2Cj%5Cleadsto%20i%7D%281-y%7Bit%7D%29%5B1%2BDM%28x_i%2Cx_j%29-D_M%28x_i%2Cx_t%29%5D%2B%5C%7D%20%5Ctag%7B17%7D%0A&id=G8OPZ)

针对第一项，针对被输入的数据的个目标邻居计算累加的平方距离；针对第二项，累加在附近的入侵者的Hinge Loss；同时也加上第三项，也就是那些被入侵的数据中由引起的Hinge Loss。能够最小化的等式17的标签就是最终的标签。

扩展

在扩展部分，作者还研究了一些可以提高LMNN表现的方法或者其他用途，包括：

• Multi-pass LMNN
• 训练多个Metric
• 核方法的LMNN
• 使用LMNN进行维数约简
• 基于Ball Tree的kNN搜索优化