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 projection operator to find the solution.
Experiment
The authors compare their method with a number of other methods, including LMNN and LMNN-MM. They argue that they have acquired superior results on a number of different datasets. However, their method has a lot of parameters and it is not clear how much parameter tuning is necessary. Nevertheless, they report that their method is better than the state of the art, according to McNemar's test.
Furthermore, they experimentally verify that the method does not overfit, even if the number of basis metrics is large. They argue that this is because of manifold regularization.
-
Caption1
