大间隔最近邻居

大间隔最近邻居（Large margin nearest neighbor (LMNN)）分类算法是统计学的一种机器学习算法。该算法是在$k$近邻分类其中学习一种欧式距离度量函数。该度量函数优化的目标是：对于一个输入$x_{i}$ 的$k$个近邻都属于同一类别，而不同类别的样本与$x_{i}$保持一定大的距离。$k$近邻规则是模式识别领域广泛使用的一种简单有效的方法。它的效果的好坏只依赖于确定最近邻的距离度量。基于欧式距离度量学习函数的大间隔最近邻居分类算法能够很好的改善$k$近邻算法分类效果。

定义

大间隔最近邻居算法的主要想法就是通过学习一种距离度量使得在一个新的转换空间中，对于一个输入$x_{i}$ 的$k$个近邻都属于同一类别，而不同类别的样本与$x_{i}$保持一定大的距离。如果该想法能够实现则留一（LOO）分类错误率将会最小化。该算法的最主要的任务就是求得满足条件的线性空间转换矩阵$M$。 定义有类别标签的训练数据集为：$D=\{({\vec {x}}_{1},y_{1}),\dots ,({\vec {x}}_{n},y_{n})\}\subset R^{d}\times C$, 其中类别标签集为：$C=\{1,\dots ,c\}$. 我们的目标是学习一种用来估计如下平方距离的线性变换$M$： $d({\vec {x}}_{i},{\vec {x}}_{j})=({\vec {x}}_{i}-{\vec {x}}_{j})^{\top }\mathbf {M} ({\vec {x}}_{i}-{\vec {x}}_{j})$

其中$M$是半正定矩阵。欧氏距离是该距离度量的特例（$M$为单位矩阵的形式）。该度量算法也被称作是马氏距离度量（Mahalanobis Metric）。 图1显示了，该算法的学习过程：

Figure 1: Schematic illustration of LMNN.

目标邻居的定义

对于每一个输入样本$x_{i}$，除了要知道其类别标签$y_{i}$外，还需要确定其$k$个目标邻居，即$k$个同类别的输入，并且希望通过上式求出的距离最小。当缺乏先验知识的话，属于同类别的目标邻居可以由欧氏距离确定。则属于同类别的$k$个的输入即为目标邻居。

入侵样本的定义

对于任何一个输入样本$x_{i}$，其入侵样本是指与其最近邻的$k$个样本中与其不同类的样本。该算法在对训练样本学习过程中应尽可能的使入侵样本的数目达到最小化。

算法

大间隔最近邻居算法的转换矩阵$M$可以通过半定规划得到优化。该算法的目标是：对于每一个输入样本，其$k$个目标邻居应尽可能的接近，而那些入侵样本应尽可能的远离该输入样本（即与其保持一定大的距离间隔）。图1显示了该算法的学习过程，通过学习使得输入向量$x_{i}$被其目标近邻包围。对于一个测试样本，我们取$k$为3的最近邻规则。 第一个优化的目标是实现输入样本$x_{i}$与其目标近邻的平均距离的最小化: $\sum _{i,j\in N_{i}}d({\vec {x}}_{i},{\vec {x}}_{j})$.

第二个优化的目标是使输入样本$x_{i}$到其目标邻居的距离与其到入侵近邻的距离至少保持1个单位的间隔。该约束可以表示为： $\forall _{i,j\in N_{i},l,y_{l}\neq y_{i}}d({\vec {x}}_{i},{\vec {x}}_{j})+1\leq d({\vec {x}}_{i},{\vec {x}}_{l})$

因此，最终的优化问题可以表示为：

$\min _{\mathbf {M} }\sum _{i,j\in N_{i}}d({\vec {x}}_{i},{\vec {x}}_{j})+\sum _{i,j,l}\xi _{ijl}$

$\forall _{i,j\in N_{i},l,y_{l}\neq y_{i}}$

$d({\vec {x}}_{i},{\vec {x}}_{j})+1\leq d({\vec {x}}_{i},{\vec {x}}_{l})+\xi _{ijl}$

$\xi _{ijl}\geq 0$

$\mathbf {M} \succeq 0$

其中$M$为半定矩阵。

外部链接

• Matlab Implementation
• ICML 2010 Tutorial on Metric Learning