parametric Local Metric Learning for Nearest Neighbor Classification

Overview

This paper addresses the problem of supervised local metric learning for nearest neighbor (or generally K-NN) classifiers. Here, by local, we mean that separate metrics are found for each data point. These metrics are formed by a linear combination of some "basis metrics". In the algorithm, both the basis metrics and the local weights of each data point are learned. While basis metrics are learned in a supervised way, the local weights are learned in an unsupervised manner, which reduces the risk of overfitting. Furthermore, the authors use the idea of manifold regularization to further overcome overfitting. Also, large margin triplet constraints are used to find basis metrics, which further improves the results.

Introduction

The squared Mahalanobis distance between two instances is given by

[math]\displaystyle{ d^{2}_{M} = (x_{i} - x_{j})^{T}M(x_{i} - x_{j}) }[/math]

One way of having local metrics, is to define different distance metrics for different training samples.

[math]\displaystyle{ d^{2}_{M_i} = (x_{i} - x_{j})^{T}M_i(x_{i} - x_{j}) }[/math]

In fact, this way of defining local metrics does not satisfy the symmetric property of a metric. However, although not a metric, in the paper it is called metric learning. Nevertheless, this abuse of notation can give intuitions.

We assume that each local metric [math]\displaystyle{ M_i }[/math] is a linear combination of the basis metrics, [math]\displaystyle{ M_{b_k} }[/math]

[math]\displaystyle{ {M_i} = \sum_{b_k}W_{i,b_k}M_{b_k}, W_{i,b_k}\gt =0, \sum_{b_k}W_{i,b_k}=1 }[/math]

As can be seen, the basis metrics [math]\displaystyle{ M_{b_k} }[/math] and the weights [math]\displaystyle{ W_{i,b_k} }[/math] should be learned; once they are known, we will have the local metric (well, if we can call it a metric).

Furthermore, each basis metric corresponds to an anchor point in the input space. These anchor points are found using k-means clustering (other methods could also be used).

Learning the Weights

The weights are learned in an unsupervised way. In fact, the weights do not even depend on the basis metrics [math]\displaystyle{ M_{b_k} }[/math]. We compute the weights in a way that

• Each training point is approximated as a weighted combination of the anchor points.
• The weights should be local; if a training sample is far from an anchor point, the corresponding weight should be small.
• The weights of nearby training points should be similar (i.e., manifold regularization)

Therefore, the optimization problem is defined as follows

[math]\displaystyle{ min_{w}g(W) = |X-WU|^2_F + \lambda_{1}tr(WG) + \lambda_{2}tr(W^{T}LW) }[/math]

[math]\displaystyle{ s.t. W_{i,b_k}\gt =0, \sum_{b_k}W_{i,b_k}=1 }[/math]

where [math]\displaystyle{ G }[/math] is the distance matrix between the anchor points and the training points. [math]\displaystyle{ L }[/math] is the Laplacian matrix over the training points which can be computed used k-nearest-neighbor graph.

This optimization problem is quadratic (and also convex) and has a unique solution. It can be solved using gradient based methods. The authors use a projected gradient method and improve it by first order FISTA method.

Learning the Basis Metrics

The basis metrics, which correspond to the anchor points, are learned in a supervised way. In fact, they are learned in a way that the triplet constraints are satisfied. However, this might not be possible all the time. Therefore, they use a soft margin constraint.

[math]\displaystyle{ min_{M_{b_k}, \epsilon} \alpha_{1}\sum_{b_l}|M_{b_l}|^2_F + \sum_{i,j,k}\epsilon_{i,j,k} +\alpha_{2}\sum_{i,j}\sum_{b_l}W_{i,b_l}d_{M_{b_l}}^{2}(x_i,x_j) }[/math]

[math]\displaystyle{ s.t. \sum_{b_l}(W_{i,b_l}d_{M_{b_l}}^{2}(x_i,x_j)-W_{i,b_l}d_{M_{b_l}}^{2}(x_i,x_j)) \gt = 1-\epsilon_{i,j,k} , \epsilon_{i,j,k} \gt = 0, M_{b_l}\gt =0 }[/math]

The soft margin triplet constraints for each sample are generated in a way that k1 nearest neighbors of the same class be closer than the k2 nearest neighbor of the other classes.

The above optimization problem can be solved efficiently by taking into account the Lagrangian dual problem. The benefit of the dual problem is that with a fixed Lagrangian multiplier, the problem has a closed form solution. Therefore, we just need to find the Lagrange multipliers. The authors use a Box operation operator to find the solution.