Efficiently Learning the Metric with Side-Information

Bie Tijl De, Momma Michinari, Nello Cristianini

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

25 Citations (Scopus)


A crucial problem in machine learning is to choose an appropriate representation of data, in a way that emphasizes the relations we are interested in. In many cases this amounts to finding a suitable metric in the data space. In the supervised case, Linear Discriminant Analysis LDA can be used to find an appropriate subspace in which the data structure is apparent. Other ways to learn a suitable metric are found in 6 and 11. However recently significant attention has been devoted to the problem of learning a metric in the semi-supervised case. In particular the work by Xing et al. 15 has demonstrated how semi-definite programming SDP can be used to directly learn a distance measure that satisfies constraints in the form of side-information. They obtain a significant increase in clustering performance with the new representation. The approach is very interesting, however, the computational complexity of the method severely limits its applicability to real machine learning tasks. In this paper we present an alternative solution for dealing with the problem of incorporating side-information. This side-information specifies pairs of examples belonging to the same class. The approach is based on LDA, and is solved by the ecient eigenproblem. The performance reached is very similar, but the complexity is only Od 3 instead of Od 6 where d is the dimensionality of the data. We also show how our method can be extended to deal with more general types of side-information.
Translated title of the contributionEfficiently Learning the Metric with Side-Information
Original languageEnglish
Title of host publicationAlgorithmic Learning Theory
Subtitle of host publication14th International Conference, ALT 2003, Sapporo, Japan, October 17-19, 2003. Proceedings
Number of pages15
ISBN (Electronic)978-3-540-39624-6
ISBN (Print)978-3-540-20291-2
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science

Bibliographical note

ISBN: 9783540202912
Publisher: Springer
Name and Venue of Conference: ALT 2003
Other identifier: 2000794


Dive into the research topics of 'Efficiently Learning the Metric with Side-Information'. Together they form a unique fingerprint.

Cite this