Online and batch learning of pseudo-metrics

ABSTRACT

We describe and analyze an online algorithm for supervised learning of pseudo-metrics. The algorithm receives pairs of instances and predicts their similarity according to a pseudo-metric. The pseudo-metrics we use are quadratic forms parameterized by positive semi-definite matrices. The core of the algorithm is an update rule that is based on successive projections onto the positive semi-definite cone and onto half-space constraints imposed by the examples. We describe an efficient procedure for performing these projections, derive a worst case mistake bound on the similarity predictions, and discuss a dual version of the algorithm in which it is simple to incorporate kernel operators. The online algorithm also serves as a building block for deriving a large-margin batch algorithm. We demonstrate the merits of the proposed approach by conducting experiments on MNIST dataset and on document filtering.

REFERENCES

• 1: Yair Al Censor , Stavros A. Zenios, Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, 1997
• 2: Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions in Information Theory, IT-13, 21--27.
• 3: Cox, T., & Cox, M. (1994). Multidimensional scaling. Chapman and Hall, London.
• 4: Crammer, K., Dekel, O., Shalev-Shwartz, S., & Singer, Y. (2003). Online passive aggressive algorithms. Advances in Neural Information Processing Systems 16.
• 5: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 6: Golub, G., & Loan, C. V. (1989). Matrix computations. John Hopkins University Press.
• 7: Mark Herbster, Learning Additive Models Online with Fast Evaluating Kernels, Proceedings of the 14th Annual Conference on Computational Learning Theory and and 5th European Conference on Computational Learning Theory, p.444-460, July 16-19, 2001
• 8: Yaoyong Li , Hugo Zaragoza , Ralf Herbrich , John Shawe-Taylor , Jaz S. Kandola, The Perceptron Algorithm with Uneven Margins, Proceedings of the Nineteenth International Conference on Machine Learning, p.379-386, July 08-12, 2002
• 9: MacQueen, J. (1965). On convergence of k-means and partitions with minimum average variance. Ann. Math. Statist.
• 10: F. Rosenblatt, The perception: a probabilistic model for information storage and organization in the brain, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988
• 11: Noam Shental , Tomer Hertz , Daphna Weinshall , Misha Pavel, Adjustment Learning and Relevant Component Analysis, Proceedings of the 7th European Conference on Computer Vision-Part IV, p.776-792, May 28-31, 2002
• 12: Amit Singhal , Chris Buckley , Mandar Mitra, Pivoted document length normalization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-29, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243206]
• 13: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 14: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 15: Xing, E., Ng, A. Y., Jordan, M., & Russell, S. (2003). Distance metric learning, with application to clustering with side-information. Advances in Neural Information Processing Systems 15.