Online Learning of Pseudo-Metrics
Shai Shalev-Shwartz - The Hebrew University Andrew Ng - Stanford University Yoram Singer - The Hebrew University
We describe and analyze an online algorithm for supervised learning ofpseudo-metrics. The algorithm receives pairs of instances and predicts theirsimilarity according to a pseudo-metric. The pseudo-metrics we use arequadratic forms parameterized by positive semi-definite matrices. The core ofthe algorithm is an update rule that is based on successive projections ontothe positive semi-definite cone and onto half-space constraints imposed by theexamples. We describe an efficient procedure for performing theseprojections, derive a worst case mistake bound on the similarity predictions,and discuss a dual version of the algorithm in which it is simple toincorporate kernel operators. The online algorithm also serves as a buildingblock for deriving a large-margin batch algorithm. We demonstrate the meritsof the proposed approach by conducting experiments on MNIST dataset and on document filtering.