大间隔最近邻居

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

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

Figure 1: Schematic illustration of LMNN.

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

第二个优化的目标是使输入样本${\displaystyle x_{i}}$到其目标邻居的距离与其到入侵近邻的距离至少保持1个单位的间隔。该约束可以表示为： ${\displaystyle \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})}$

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

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

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

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

${\displaystyle \xi _{ijl}\geq 0}$

${\displaystyle \mathbf {M} \succeq 0}$

其中${\displaystyle M}$为半定矩阵。

• Matlab Implementation
• ICML 2010 Tutorial on Metric Learning