This work focuses on active learning of distance metrics from relative comparison information. A relative comparison specifies, for a data point triplet @math , that instance @math is more similar to @math than to @math . Such constraints, when available, have been shown to be useful toward defining appropriate distance metrics. In real-world applications, acquiring constraints often require considerable human effort. This motivates us to study how to select and query the most useful relative comparisons to achieve effective metric learning with minimum user effort. Given an underlying class concept that is employed by the user to provide such constraints, we present an information-theoretic criterion that selects the triplet whose answer leads to the highest expected gain in information about the classes of a set of examples. Directly applying the proposed criterion requires examining @math triplets with @math instances, which is prohibitive even for datasets of moderate size. We show that a randomized selection strategy can be used to reduce the selection pool from @math to @math , allowing us to scale up to larger-size problems. Experiments show that the proposed method consistently outperforms two baseline policies.
Distance metric learning with relative comparisons has also been studied in different contexts @cite_5 @cite_7 . formulated a constrained optimization problem where the constraints are defined by relative comparisons and the objective is to learn a distance metric that remains as close to an un-weighted Euclidean metric as possible @cite_7 . @cite_5 proposed to learn a projection matrix from relative comparisons. This approach also employed relative comparisons to create constraints on the solution space, but optimized a different objective to encourage sparsity of the learned projection matrix. Both studies assumed that the relative comparisons are given and the constraints are a set of random or otherwise non-optimized set of pre-selected triplets. That is, the algorithm is not allowed to request comparisons outside of the given set.
@cite_5 @cite_7
2093357278 2118393783
Calculation of object similarity, for example through a distance function, is a common part of data mining and machine learning algorithms. This calculation is crucial for efficiency since distances are usually evaluated a large number of times, the classical example being query-by-example (find objects that are similar to a given query object). Moreover, the performance of these algorithms depends critically on choosing a good distance function. However, it is often the case that (1) the correct distance is unknown or chosen by hand, and (2) its calculation is computationally expensive (e.g., such as for large dimensional objects). In this paper, we propose a method for constructing relative-distance preserving low-dimensional mapping (sparse mappings). This method allows learning unknown distance functions (or approximating known functions) with the additional property of reducing distance computation time. We present an algorithm that given examples of proximity comparisons among triples of objects (object i is more like object j than object k), learns a distance function, in as few dimensions as possible, that preserves these distance relationships. The formulation is based on solving a linear programming optimization problem that finds an optimal mapping for the given dataset and distance relationships. Unlike other popular embedding algorithms, this method can easily generalize to new points, does not have local minima, and explicitly models computational efficiency by finding a mapping that is sparse, i.e. one that depends on a small subset of features or dimensions. Experimental evaluation shows that the proposed formulation compares favorably with a state-of-the art method in several publicly available datasets. This paper presents a method for learning a distance metric from relative comparison such as "A is closer to B than A is to C". Taking a Support Vector Machine (SVM) approach, we develop an algorithm that provides a flexible way of describing qualitative training data as a set of constraints. We show that such constraints lead to a convex quadratic programming problem that can be solved by adapting standard methods for SVM training. We empirically evaluate the performance and the modelling flexibility of the algorithm on a collection of text documents.