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.
