Extension of Similarity Learning for Nearest Neighbor Algorithm by incorporating control parameter using Passive Aggressive family of algorithms

Abstract

We present an On-line Passive Aggressive Similarity metric learning algo- rithm for fully supervised learning in a nearest neighbor setting. This algo- rithm incorporates aggressiveness and control parameter in similarity learn- ing. The update step is based on the analytical solution of a convex optimiza- tion problem that is constructed on the basis of margin maximization using K nearest neighbor algorithm. The solution is obtained using the methodol- ogy of passive aggressive algorithms and the resulting algorithm provides a global optimum solution due to the convex nature of the problem. The main aim of this algorithm is to learn a similarity matrix A such that it correctly classi es an existing example while retaining the information obtained from previous examples, this is done by utilizing the hinge loss function. If an example is closer to its target neighbors than the impostors then it su ers zero loss and no update step takes place. However if the example is closer to impostors rather than target neighbors then the algorithm su ers a loss which is equal to the di erence between impostors and target neighbors, to accommodate this loss an update step takes place and a matrix A is learned which reduces the loss in subsequent steps. Furthermore a control parameter C is added after mathematical justi cation; this is useful in case of label noise and provides an upper bound for the update rule of the algorithm. The algorithm is tested on several dataset from the standard UCI data repository and is shows promise against several leading machine learning algorithms.