A gradient-based metric learning algorithm for k-nn classifiers

The Nearest Neighbor (NN) classification/regression techniques, besides their sim-plicity, is one of the most widely applied and well studied techniques for pattern recognition in machine learning. Their only drawback is the assumption of the avail-ability of a proper metric used to measure distances to k nearest neighbors. It has been shown that K-NN classifier’s with a right distance metric can perform better than other sophisticated alternatives like Support Vector Machines (SVM) and Gaussian Processes (GP) classifiers. That’s why recent research in k-NN methods has focused on metric learning i.e., finding an optimized metric. In this paper we have proposed a simple gradient based algorithm for metric learning. We discuss in detail the motiva-tions behind metric learning, i.e., error minimization and margin maximization. Our formulation is different from the prevalent techniques in metric learning where goal is to maximize the classifier’s margin. Instead our proposed technique (MEGM) finds an optimal metric by directly minimizing the mean square error. Our technique not only resulted in greatly improving k-NN performance but also performed better than competing metric learning techniques. We also compared our algorithm’s performance with that of SVM. Promising results are reported on major faces, digits, object and UCIML databases.