Online and batch learning of pseudo-metrics

Shai Shalev-Shwartz, Yoram Singer, Andrew Y. Ng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

148 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings, Twenty-First International Conference on Machine Learning, ICML 2004
EditorsR. Greiner, D. Schuurmans
Pages743-750
Number of pages8
StatePublished - Dec 1 2004
Externally publishedYes
EventProceedings, Twenty-First International Conference on Machine Learning, ICML 2004 - Banff, Alta, Canada
Duration: Jul 4 2004Jul 8 2004

Publication series

NameProceedings, Twenty-First International Conference on Machine Learning, ICML 2004

Other

OtherProceedings, Twenty-First International Conference on Machine Learning, ICML 2004
CountryCanada
CityBanff, Alta
Period7/4/047/8/04

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Online and batch learning of pseudo-metrics'. Together they form a unique fingerprint.

  • Cite this

    Shalev-Shwartz, S., Singer, Y., & Ng, A. Y. (2004). Online and batch learning of pseudo-metrics. In R. Greiner, & D. Schuurmans (Eds.), Proceedings, Twenty-First International Conference on Machine Learning, ICML 2004 (pp. 743-750). (Proceedings, Twenty-First International Conference on Machine Learning, ICML 2004).