对距离度量与LMNN分类论文的理解

对距离度量与LMNN分类论文的理解

1.论文简介

这篇论文主要谈论的是距离度量的方式(Distance Metric)对分类问题的优化,论文中主要讨论了距离度量训练对KNN分类精度的影响。


2.距离度量

2.1 距离量度的定义

通常不满足第四个等式的Metric也叫作伪度量(pseudometric)。

2.2 Mahalanobis度量(马氏度量)

马氏度量的定义如下: D_{\mathbf{L}}\left(\vec{x}_{i}, \vec{x}_{j}\right)=\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{j}\right)\right\|_{2}^{2} , 其中L是一种线性变换,如果L满秩,拿么L就定义了一个有效度量,如果L 不是满秩,那么D就是一个伪度量。

其中 \mathbf{M}=\mathbf{L}^{\top} \mathbf{L}

从上面可以看出我们要定义一个度量要么定义一个线性变换L 要么定义一个矩阵M(这个矩阵需要是半正定的),有了这个概念之后下面就开始讨论集中度量的训练方式

2.2.1特征向量法(Eigenvector Methods)

2.2.1.1主值分析(Principal component Analysis)

\mathbf{C}=\frac{1}{n} \sum_{i=1}^{n}\left(\vec{x}_{i}-\vec{\mu}\right)^{\top}\left(\vec{x}_{i}-\vec{\mu}\right)

PCA思想的目标函数为

\max _{\mathbf{L}} \operatorname{Tr}\left(\mathbf{L}^{\top} \mathbf{C} \mathbf{L}\right) \text { subject to: } \mathbf{L L}^{\top}=\mathbf{I}

其中C是数据的协方差矩阵

\mathbf{C}=\frac{1}{n} \sum_{i=1}^{n}\left(\vec{x}_{i}-\vec{\mu}\right)^{\top}\left(\vec{x}_{i}-\vec{\mu}\right)

如果L是方形矩阵的话那么这个线性变换不会改变数据的维度,但是如果L是长方形的矩阵的话那么变换的数据的维度会受到减少,从目标函数求Trace来看,PCA是想要找到方差最大的空间方向从而达到降低维度的目的。PCA通常作为KNN降噪的方法,可以大大减少KNN的计算量。

2.2.1.2 LDA(Linear Discriminant Analysis)方法

LDA方法的思想简单来说是训练一个度量达到类内元素距离小,类见距离大的方法。

这里提出两种方差,类内方差和类间方差:

\mathbf{C}_{b}=\frac{1}{C} \sum_{c=1}^{C} \vec{\mu}_{c} \vec{\mu}_{c}^{\top}

\mathbf{C}_{w}=\frac{1}{n} \sum_{c=1}^{C} \sum_{i \in \Omega_{c}}\left(\vec{x}_{i}-\vec{\mu}_{c}\right)\left(\vec{x}_{i}-\vec{\mu}_{c}\right)^{\top}

\vec{\mu}_{c} 表示第C个类别的样本的均值。然后定义线性转换矩阵 \mathbf{L}

最后定义目标函数如下:

\max _{\mathbf{L}} \operatorname{Tr}\left(\frac{\mathbf{L}^{\top} \mathbf{C}_{b} \mathbf{L}}{\mathbf{L}^{\top} \mathbf{C}_{w} \mathbf{L}}\right) \text { subject to: } \mathbf{L} \mathbf{L}^{\top}=\mathbf{I}

LDA是一种常用的线性预处理的方式,LDA由于需要Label 所以它只适用于监督学习的预处 理。

2.2.1.3 RCA(Relevant Component Analysis)

RCA的是介于PCA和LDA之间的一种方法,它提出了chunklet(子类)的定义,子类是类(class)的真子集,也就是类里元素提取出的集合。

\mathbf{C}_{w}=\frac{1}{n} \sum_{l=1}^{L} \sum_{i \in \Omega_{l}}\left(\vec{x}_{i}-\vec{\mu}_{l}\right)\left(\vec{x}_{i}-\vec{\mu}_{l}\right)^{\top}

这个Cw简单的来说其实就每个子类协方差的和,我们得到的线性变换如下:

\mathbf{L}={\mathbf{C}_{w}}^{-1/2}

这个线性变换的作用标准化子类内的方差,RCA有个缺陷是会提高噪声方向,所以再做RCA之前做最好先用PCA进行降噪处理。

2.3 凸优化

由上述例子可以知道,论文的目的是要训练一个度量,要么用线性变换L表示要么用矩阵M表示. 这节讨论此种方式的度量训练。

2.3.1 MMC(Mahalanobis Metric for Clustering)

MMC如下表示

\begin{array}{l}{\text { Maximize } \sum_{i j}\left(1-y_{i j}\right) \sqrt{\mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{j}\right)} \text { subject to: }} \\ {\qquad \begin{array}{l}{(1) \sum_{i j} y_{i j} \mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{j}\right) \leq 1} \\ { (2) \mathbf{M} \succeq 0}\end{array}}\end{array}

由目标函数可以看出MMC的思想是提高不用类元素之间的距离,1号限制条件确保了问题是可行且有界的,2号限制使得M是一个半正定矩阵,这是一个凸优化问题,MMC没有超参数。

2.3.2 Pseudometric Online Learning Algorithm(POLA)

POLA的思想是训练一个马氏矩阵使得类间元素的距离大,类内元素的距离小。

它首先定义了一个三元组: \left(\vec{x}_{t}, \vec{x}_{t}^{\prime}, y_{t}\right) y_{t} = 1 表示输入的两个样本属于同一类别,否则 -1。接着POLA要去训练一个Mahalanobis矩阵满足以下限制:

y_{t}\left[b-\left(\vec{x}_{t}-\vec{x}_{t}^{\prime}\right)^{\top} \mathbf{M}\left(\vec{x}_{t}-\vec{x}_{t}^{\prime}\right)\right] \geq 1

这个条件训练的是一个标量b和一个马氏矩阵M,我们可以看处这个条件使得类间元素有了下界b+1,类内元素之间的距离为b-1,这样类间元素和类内元素之间就形成了至少2个单位长度的距离间隔,使得数据之间有了更明显的界限划分。

矩阵M和参数b在每次迭代以后更新,所以此种方法可以进行实时训练。


2.3.3 NCA(Neighbourhood Component Analysis)

NCA引入了softmax的思想

p_{i j}=\left\{\begin{array}{cc}{\frac{\exp \left(-\left\|\mathbf{L} x_{i}-\mathbf{L} x_{i}\right\|^{2}\right)}{\sum_{k \neq i} \exp \left(-\left\|\mathbf{x}_{i}-\mathbf{L} x_{k}\right\|^{2}\right)}} & {\text { if } i \neq j} \\ {0} & {\text { if } i=j}\end{array}\right.

其目标函数为

\varepsilon_{\mathrm{NCA}}=1-\frac{1}{n} \sum_{i j} p_{i j} y_{i j} , 其中当ij为同类别时 y_{ij} = 1 否则 y_{ij} = 0 .

该目标函数不是一个凸优化问题,得到的结果会被初始值影响。

3 LMNN模型

读到这里我们可以理解到要有好的分类结果,就要训练一个度量使得类内距离小,类间距离大来解决类间界限不明显的问题,类间距离不明显的条件下我们引入一个新的概念伪装(imposters),顾名思义就是在一个元素很近的地方然而又不属于同一类,它的数学表达如下:

\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{l}\right)\right\|^{2} \leq\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{j}\right)\right\|^{2}+1

\vec{x}_i 是任意输入的样本, \vec{x}_l 伪装。而 \vec{x}_j 是和输入样本相同类别的“邻近”样本。

那目标函数应该如何定义呢?它可以拆分成提高类间距离和降低类内距离。

我们定义两个距离

\varepsilon_{\text {pull }}(\mathbf{L})=\sum_{j \leadsto i}\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{j}\right)\right\|^{2}

\varepsilon_{\text {push }}(\mathbf{L})=\sum_{i, j \sim i} \sum_{l}\left(1-y_{i l}\right)\left[1+\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{j}\right)\right\|^{2}-\left\|\mathbf{L}\left(\vec{x}_{i}-\vec{x}_{l}\right)\right\|^{2}\right]_{+}

第一个距离是类内距离,第二个是类间的距离,我们希望类间分界明显的话直白的说就是要把同种元素拉近,不同元素推远。

这两个距离构造的最终目标函数就是

\varepsilon(\mathbf{L})=(1-\mu) \varepsilon_{p u l l}(\mathbf{L})+\mu \varepsilon_{p u s h}(\mathbf{L})

\mu 是一个超参数,它表示的是推的权重,既类间距离的重要性,一般来说取0.5就行。

实验结果表明只有NCA和LMNN降低了1-NN分类的的误差,其它的方法还增加了误差。


3.1 问题的凸优化

前面已经构造了如下的目标函数:

\varepsilon(\mathbf{M})=(1-\mu) \sum_{i, j \sim i} \mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{j}\right)+\mu \sum_{i, j \sim i} \sum_{l}\left(1-y_{i l}\right)\left[1+\mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{j}\right)-\mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{l}\right)\right]_{+}

其中M是个半正定的矩阵,这个问题显然是个凸优化问题,我们下面引入一个松弛变量\xi_{i j l}将它变成一个更一般的形式:

\begin{array}{l}{\text { Minimize }(1-\mu) \sum_{i, j \sim i}\left(\vec{x}_{i}-\vec{x}_{j}\right)^{\top} \mathbf{M}\left(\vec{x}_{i}-\vec{x}_{j}\right)+\mu \sum_{i, j \rightarrow i, l}\left(1-y_{i l}\right) \xi_{i j l} \text { subject to: }} \\ {\text { (1) }\left(\vec{x}_{i}-\vec{x}_{l}\right)^{\top} \mathbf{M}\left(\vec{x}_{i}-\vec{x}_{l}\right)-\left(\vec{x}_{i}-\vec{x}_{j}\right)^{\top} \mathbf{M}\left(\vec{x}_{i}-\vec{x}_{j}\right) \geq 1-\xi_{i j l}} \\ {\text { (2) } \xi_{i j l} \geq 0} \\ {\text { (3) } \mathbf{M} \succeq 0}\end{array}

对于这个问题我们可以用标准的SDP的solver对其求解,一般来说松弛变量是稀疏的因为相对于类间距离来说类内距离一般都很小 ,因此这个问题有更优的solver来加速。

3.2 基于能量的分类

基于上面构造的目标函数。其实我们直接构造一个分类器。

\begin{equation} \left.\begin{array}{rl}{y_{t}=\operatorname{argmin}_{y_{t}}\left\{(1-\mu) \sum_{j \sim t} \mathcal{D}_{\mathbf{M}}\left(\vec{x}_{t}, \vec{x}_{j}\right)+\mu \sum_{j \sim t, l}\left(1-y_{t l}\right)\left[1+\mathcal{D}_{\mathbf{M}}\left(\vec{x}_{t}, \vec{x}_{j}\right)-\mathcal{D}_{\mathbf{M}}\left(\vec{x}_{t}, \vec{x}_{l}\right)\right]_{+}\right.} & {} \\ {+\mu \sum_{i, j \sim i}\left(1-y_{i t}\right)\left[1+\mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{j}\right)-\mathcal{D}_{\mathbf{M}}\left(\vec{x}_{i}, \vec{x}_{t}\right)\right]_{+}}\end{array}\right\} \end{equation}此类基于能量的分类器通常能够进一步减测试误差。

4.结果

作者通过实验得到了如下的结果表格

4.1 大数据集

论文对不同的线性变换构造与KNN算法共同使用对5个很大的数据集进行分类,这里的是3-NN的情况,然后 \mu 取0.5,得到了下列结果:

结果可以看出LMNN很多情况下都要优于PCA和LDA,多度量LMNN 可与多类支持向量机相比较。

测试结论:

1) 使用了Mahalanobis距离以后的KNN明显性能优于欧几里得距离的KNN,无论是在训练集还是测试集上。

2)LMNN-energy也能更进一步提升基于Mahalanobis距离计算的KNN分类器的性能。

3)LMNN的在数据降维的时候,选择PCA会更优于用LDA降维。

4)在大的数据集上,LMNN的提升更大。

5)使用线性,多项式或者RBF核函数,并进行交叉验证。在多分类问题上Kernalized SVM取得了最好的性能。最后我们选择了一个非自同态(non-homogeneous 非线性)的4次多项式核函数。当然LMNN在3个大数据集上取得了比SVM更好的性能。

4.2 小数据集

wine iris bal数据都是小数据集合,训练样本少于500个。在随机 0.7 0.3 的数据划分下LMNN相对于欧式距离的KNN都有性能提高,但是小样本其实看不出来太多LMNN的优势,并且这些数据集的情况也不是LMNN重要应用的领域。

4.3 人脸识别任务

Olivetti 人脸识别数据包含了400张灰度图像,涵盖了40种10个不同角度的图像数据。首先用PCA把图像降维到38x31像素。测试任务是从每个类别中分别选取7张图像作为训练集,剩下的3张图像作测试集。这是一个40个类别的分类问题。

4.4 语音识别

Isolet 数据集是包含了6238个样本对26个字母的发音进行的采样,测试首先采用PCA降维保留172个主特征。然后进行测试。非线性的神经网络拥有3.5%的错误率,而LMNN基于engery-based的分类器达到了3.4%错误率。

4.5 字母识别

采用了UCI的数据集合涵盖了26个字母的20种字体

4.6 文本分类

基于20-newgroups 数据集,数据共有20个新闻分类。同样采用PCA降维并取了主要的200维特征。这种情况下虽然效果比欧式距离和PCA效果好,但是多类SVM的效果还是更优。

4.7 手写数字识别

采用了MNIST数据集,输入图像是28x28的灰度图片,采用了PCA降维到164维。

4.8 多次运行LMNN的结果

由此图可以看出多次运行的LMNN的结果优于单词运行的LMNN,无论是训练还是测试集上。


5 拓展

5.1 Multi Pass LMNN

LMNN的一个缺点是,在计算损失函数的时候对每个样本计算其“邻近”样本的时候依赖于“先验知识”。如果没有这种先验知识,默认采用欧几里得距离来寻找邻近样本。然而训练过程会要求“邻近”样本的关系保持不变,而训练的过程会影响样本位置的分布,就可能导致了“邻近”样本是发生变化的。

这里通过每次训练的Mahalanobis的L矩阵,并根据欧几里得距离来确定邻近样本。 \vec{x}_{i} \rightarrow \mathbf{L}_{p} \mathbf{L}_{p-1} \ldots \mathbf{L}_{1} \mathbf{L}_{0} \vec{x}_{i}\left(\text { with } \mathbf{L}_{0}=\mathbf{I}\right)

当然如何选择邻近的样本也是一个开放问题;而NCA算法不依赖与选择邻近的目标,但不是一个凸优化问题;LMNN是为了维持凸优化的定义,必须选择一个固定邻近目标。

5.2 Multi Metric LMNN


在某些数据集上,仅仅训练一个全局的Linear transformation并不能足够好的提升KNN分类的性能。理由是Mahalanobis是基于线性转换的,而有些非线性的多分类决策边界并不能很好的通过他来建模。

因此我们采用了根据样本来训练多个局部的Mahalanobis Metrix变换矩阵。

根据K-means将训练数据进行分割类聚。然后对每个Cluster训练一个局部的Mahalanobis metric,

\hat{\mathcal{D}}\left(\vec{x}_{i}, \vec{x}_{j}\right)=\left(\vec{x}_{i}-\vec{x}_{j}\right)^{\top} \mathbf{M}^{y_{j}}\left(\vec{x}_{i}-\vec{x}_{j}\right)

解决以下的优化问题:

\begin{array}{l}{\text { Minimize }(1-\mu) \sum_{i, j \sim i}\left(\vec{x}_{i}-\vec{x}_{j}\right)^{\top} \mathbf{M}^{y_{j}}\left(\vec{x}_{i}-\vec{x}_{j}\right)+\mu \sum_{j \sim i, l}\left(1-y_{i l}\right) \xi_{i j l}} \\ {\text { subject to: }} \\ {\text { (1) }\left(\vec{x}_{i}-\vec{x}_{l}\right)^{\top} \mathbf{M}^{y_{l}}\left(\vec{x}_{i}-\vec{x}_{l}\right)-\left(\vec{x}_{i}-\vec{x}_{j}\right)^{\top} \mathbf{M}^{y_{j}}\left(\vec{x}_{i}-\vec{x}_{j}\right) \geq 1-\xi_{i j l}} \\ {\text { (2) } \xi_{i j l} \geq 0} \\ {\text { (3) } \mathbf{M}^{i} \succeq 0 \text { for } i=1, \ldots, c}\end{array}

5.3 Kernelize LMNN

\mathbf{K}_{i j}=\Phi\left(\vec{x}_{i}\right)^{\top} \Phi\left(\vec{x}_{j}\right)

定义基于Kernel的Mahalanobis metric, \mathbf{M}=\sum_{l m} \mathbf{A}_{l m} \Phi\left(\vec{x}_{l}\right) \Phi\left(\vec{x}_{m}\right)^{\top} ,核函数用于将数据映射到更高维度的控件上使得样本达到更好的“线性可分”。

5.4 使用LMNN监督降维

根据训练出来的方阵L,取他的主特征(特征值最大的特征向量)构建映射矩阵P,原数据就可以通过映射矩阵进行降维。

或者构建一个尺寸为rxd的L矩阵,r是想要降维后的维度,直接训练出L,但这就不是一个凸优化问题了。

5.5 Metric Trees

由于KNN的复杂度依赖于样本数量和样本的维度,当数据量和维度特别大的时候,每次计算的复杂度会很高。

作者提出了基于Ball Tree的KNN搜索优化:

可以通过构建ball tree对搜索时候的计算提升了相当大的性能。

6 Review Ball Tree

为了优化问题有人提出了KD Tree,Ball Tree和cover-tree等数据结构。他们的思想是将数据根据某种划分规则,划分到一定的“区间”内。而该区间保证从测试点到该区域的所有元素的距离都大于或等于从测试点到该区域的“边界”距离。在邻近搜索的时候,如果边界距离已经大于当前的K邻近的最远的候选样本的距离,则该区间内的所有样本都可以被排除。

ball tree的区间划分是一种球面。参考下图:

ball tree的每个分割点距离的边界等于球心到测试点距离减去球的半径。

假设样本的集合S被包括在一个球内。球心是 \vec{c} ,半径为 r ,对于所有球内的样本都满足一下条件: \forall \vec{x} \in S:\|\vec{x}-\vec{c}\| \leq r 。对于任意测试样本 \vec{x}_{t} 将满足以下关系:

\forall \vec{x}_{i} \in S \quad\left\|\vec{x}_{t}-\vec{x}_{i}\right\| \geq \max \left(\left\|\vec{x}_{t}-\vec{c}\right\|_{2}-r, 0\right)

根据这条规则就可以通过深度优先搜索(DFS)用来进行K邻近筛选。

  1. 在搜索的时候,通过上面的不等式可以用于判断目标球内是否可能包含测试样本的K邻近样本。如果边界到测试点的距离大于目前测试样本的最远的那个临近点则,该球内的所有样本都可以被排除。
  2. 当搜多到达一个叶子节点以后,叶子节点所对应球内的所有样本都会跟测试样本进行距离计算。


3-NN的经过ball tree优化的邻近搜索分类测试:

可以看到对于ball tree对于不同的维度数据都能达到搜索的优化。维度越低,这种优化效率越高。

7 参考文献

[1] Kilian Q. Weinberger, Lawrence K. Saul, Distance Metric Learning for Large Margin Nearest Neighbor Classification, Journal of Machine Learning Reserach 10 207-244

[2] Gao Huang, Chuan Guo, Supervised Word Mover's Distance, NIPS 2016

[3] Kusner, M. J., Sun, Y., Kolkin, N. I., and Weinberger, K. Q. From word embeddings to document distances. In ICML, 2015.

发布于 2021-01-23 07:53