Title: Efficiently learning the metric with side-information
Authors: De Bie, Tijl ×
Momma, M
Cristianini, N #
Issue Date: 2003
Publisher: Springer-verlag berlin
Series Title: Algorithmic learning theory, proceedings vol:2842 pages:175-189
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 efficient eigenproblem. The performance reached is very similar, but the complexity is only O(d(3)) instead of O(d(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.
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Electrical Engineering - miscellaneous
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science