Abstract
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 contribution | Efficiently Learning the Metric with Side-Information |
---|---|
Original language | English |
Title of host publication | Algorithmic Learning Theory |
Subtitle of host publication | 14th International Conference, ALT 2003, Sapporo, Japan, October 17-19, 2003. Proceedings |
Publisher | Springer |
Pages | 175-189 |
Number of pages | 15 |
ISBN (Electronic) | 978-3-540-39624-6 |
ISBN (Print) | 978-3-540-20291-2 |
DOIs | |
Publication status | Published - 2003 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 2842 |
Bibliographical note
ISBN: 9783540202912Publisher: Springer
Name and Venue of Conference: ALT 2003
Other identifier: 2000794