Convergence of Multi-pass Large Margin Nearest Neighbor Metric Learning

Göpfert C, Paaßen B, Hammer B. Convergence of Multi-pass Large Margin Nearest Neighbor Metric Learning. In: E.P. Villa A, Masulli P, Pons Rivero AJ, eds. Artificial Neural Networks and Machine Learning – ICANN 2016: 25th International Conference on Artificial Neural Networks, Barcelona, Spain, September 6-9, 2016, Proceedings, Part II. Lecture Notes in Computer Science. Vol 9887. Cham: Springer Nature; 2016: 510-517.Large margin nearest neighbor classification (LMNN) is a popular technique to learn a metric that improves the accuracy of a simple k-nearest neighbor classifier via a convex optimization scheme. However, the optimization problem is convex only under the assumption that the nearest neighbors within classes remain constant. In this contribution we show that an iterated LMNN scheme (multi-pass LMNN) is a valid optimization technique for the original LMNN cost function without this assumption. We further provide an empirical evaluation of multi-pass LMNN, demonstrating that multi-pass LMNN can lead to notable improvements in classification accuracy for some datasets and does not necessarily show strong overfitting tendencies as reported before