Metric and Kernel Learning using a Linear Transformation

Prateek Jain; Brian Kulis; Jason V. Davis; Inderjit S. Dhillon

Source-linked AI summary

Metric and Kernel Learning using a Linear Transformation

Prateek Jain, Brian Kulis, Jason V. Davis, Inderjit S. Dhillon

arXiv:0910.5932v1Oct 30, 2009cs.LGcs.CVcs.IR

TL;DR

Metric and kernel learning need methods that handle high-dimensional data and generalize beyond the transductive setting. This paper learns linear transformations with a LogDet-based framework, efficiently kernelizes them and broader convex losses, and applies the approach to large-scale vision and text problems, where it improves over state-of-the-art techniques.

Problem
Existing metric-learning methods are limited for high-dimensional data, while many kernel-learning methods are transductive and do not generalize to new points.
Method
The paper learns a linear transformation in kernel space using a LogDet divergence and extends kernelization to a wider class of convex loss functions.
Results
The approach improves over state-of-the-art techniques across large-scale computer vision and text-mining problems.
Takeaways & Limitations
The resulting learned distance and kernel functions support high-dimensional data and out-of-sample extensions while scaling to very large datasets.
Takeaways & Limitations
Mahalanobis-style linear transformations remain inadequate for datasets with nonlinear decision boundaries, motivating the kernelized formulation.

Abstract

from arXiv · show

Metric and kernel learning are important in several machine learning applications. However, most existing metric learning algorithms are limited to learning metrics over low-dimensional data, while existing kernel learning algorithms are often limited to the transductive setting and do not generalize to new data points. In this paper, we study metric learning as a problem of learning a linear transformation of the input data. We show that for high-dimensional data, a particular framework for learning a linear transformation of the data based on the LogDet divergence can be efficiently kernelized to learn a metric (or equivalently, a kernel function) over an arbitrarily high dimensional space. We further demonstrate that a wide class of convex loss functions for learning linear transformations can similarly be kernelized, thereby considerably expanding the potential applications of metric learning. We demonstrate our learning approach by applying it to large-scale real world problems in computer vision and text mining.

1 Introduction

The paper targets limitations of metric and kernel learning by kernelizing linear-transformation learning for arbitrarily high-dimensional spaces while supporting unseen data. It develops a scalable LogDet-based approach, extends kernelization to broader convex losses, and reports improvements on computer vision and text-mining problems.

Motivation: Standard similarities and distances are not appropriate for every machine learning problem, motivating learned comparisons from side information.Examples include semi-supervised clustering, nearest-neighbor classification, and text retrieval.
Existing limitations: Mahalanobis metric learning has quadratic parameter growth with dimension and is inadequate for datasets with nonlinear decision boundaries.Its linear transformation followed by squared Euclidean distance provides generalization, but creates these two limitations.
Existing limitations: Kernel learning can overcome linear limitations through nonlinear feature mappings, but many methods remain transductive and do not generalize to new points.These methods assume all labeled and unlabeled data are available upfront.
Approach: The paper kernelizes linear-transformation metric learning using the LogDet divergence, producing parameterized kernels over arbitrarily high-dimensional spaces.The learned function is φ(x)T Wφ(y), given an input kernel φ(x)T φ(y).
Approach: The proposed optimization scales to datasets with millions of objects and supports out-of-sample extensions to unseen data.The LogDet formulation also permits efficient kernelization while effectively handling positive-definiteness constraints.
Extensions: Kernelization extends beyond LogDet to a wider class of convex losses, with infinite-dimensional W representable using constrained training data.This representation enables evaluation of the learned kernel on arbitrary points.
Experiments: Experiments in computer vision and text mining show improvements over state-of-the-art techniques across several real-world learning problems.The claim concerns learned linear-transformation-based distance or kernel functions.

2 Related Work

Related work spans Mahalanobis, nonlinear metric, and kernel learning methods. The paper distinguishes its approach through more efficient LogDet-based computation, broader convex-loss kernelization, inductive generalization, and large-scale experiments.

Metric learning: Mahalanobis metric learning includes semidefinite, online, component-analysis, locally adaptive, and relative-comparison approaches.These methods represent established alternatives for learning Mahalanobis metrics.
Metric learning: Kernel-space Mahalanobis learning has been demonstrated, but one such construction requires cubic time per iteration to update parameters.The paper contrasts this cost with the more efficient implementation of its LogDet-based algorithm.
Metric learning: Nonlinear metric-learning methods include NCA, convolutional neural networks, and general Riemannian metric learning.The paper notes that these methods can suffer from suboptimal performance, non-convexity, or computational complexity.
Kernel learning: Kernel-learning research includes transductive methods and multiple-kernel learning that learns linear combinations of base kernels.Multiple-kernel learning has been applied to problems such as object recognition in computer vision.
This paper's relation to prior work: This paper broadens prior work by characterizing kernelization for a wider class of convex losses and analyzing large-scale kernel learning.It also extends earlier work to the inductive setting while not considering online models.

3 Metric and Kernel Learning via the LogDet Divergence

The paper formulates metric learning as learning a linear transformation, then kernelizes LogDet-based optimization so learned metrics can operate in arbitrarily high-dimensional spaces and generalize to new points. It also introduces compressed identity-plus-low-rank representations to reduce quadratic parameter costs for large datasets.

3.1 Mahalanobis Distances and Parameterized Kernels: Metric learning seeks a positive definite matrix W that defines Mahalanobis distances, equivalently measuring Euclidean distance after a linear transformation.In kernel space, the same formulation learns κ(x,y)=φ(x)^T Wφ(y) from an input kernel κ0(x,y)=φ(x)^Tφ(y).
3.2 LogDet Metric Learning: Pairwise similarity and dissimilarity constraints specify which objects should be close or far under the learned metric or kernel.The LogDet formulation finds W close to W0 while satisfying these constraints.
3.3 Kernelizing the Problem: LogDet divergence makes the metric-learning and kernel-learning formulations equivalent, allowing the kernel problem to be solved directly for the optimal kernel matrix K*.The equivalence follows from identical dual problems and yields an explicit optimal-W form through the Sherman-Morrison-Woodbury formula.
3.4 Generalizing to New Points: The learned kernel can be evaluated for arbitrary data objects, so kernelized distances generalize to new points using the learned kernel matrix and the input kernel function.The paper first solves for K and then computes learned distances through the resulting kernelized expression.
3.5 Kernel Learning Algorithm: O(n^2) projection updates preserve positive definiteness without eigenvector computations or semidefinite programming, whereas Frobenius-loss updates require O(n^3) computation.The LogDet algorithm therefore provides a simpler optimization route in kernel space.
3.6 Metric/Kernel Learning with Large Datasets: O(min(n^2, d^2)) parameters create a fundamental high-dimensional bottleneck, while identity-plus-low-rank representations reduce this to O(min(n,d)) values.The compressed representation is intended to make learning, storage, and evaluation efficient for high-dimensional data and large training sets.
3.6 Metric/Kernel Learning with Large Datasets: Basis selection for the compressed kernel representation may use random coefficients, clustering, or random subsets, while more careful selection is left for future research.The authors state that improved basis selection could further improve accuracy.

4 Kernelization with Other Convex Loss Functions

The paper extends kernelization beyond LogDet to a broad class of convex loss functions for learning linear transformations, reducing high-dimensional problems to finite computations over constrained data.

General result: Kernelization applies to a large class of convex objectives for learning a linear map in input or feature space.This complements earlier kernelization results for MCML and LMNN.
Kernelizability conditions: The kernelizable formulation requires efficient solvability without explicit feature vectors and efficient evaluation of tr(W*YCY^T) for new feature representations Y.These conditions define both training and evaluation requirements for kernelization.
Assumptions: The framework assumes f is convex with efficiently computable sub-gradients and uses spectral-function structure for the regularization term.The loss is applied to eigenvalues through f(W), with the formulation requiring positive-semidefinite structure.
Optimization: Assuming K0 = X^T X is invertible, the transformed problem has linear constraints and a strictly convex objective, making it a convex program.The required eigendecomposition of K0 can be computed in O(n^3), and standard convex optimization solves the reformulated problem in poly(n, m) time.
Representer form: For full-rank X, an optimal solution has the form W* = ηI + XS*X^T, so optimization can be performed using S* instead of W*.The representation establishes a one-to-one correspondence between W* and S* under the full-rank assumption.

5 Special Cases

The paper specializes its general kernelization theorem to matrix divergences, Frobenius objectives, and semidefinite programs, showing that these formulations can be solved in kernel space.

Summary: The special cases demonstrate that the general theorem covers multiple convex loss formulations, with standard convex optimization methods available for the resulting problems.The section derives each corresponding optimization problem and identifies applicable solution techniques.
von Neumann divergence: The von Neumann divergence is kernelizable because its generating function is strictly convex, minimized at 1, and satisfies the theorem’s required conditions.It generalizes KL-divergence to matrices and is defined for positive semidefinite matrices.
von Neumann divergence: The von Neumann formulation yields a dual problem solvable with first-order smooth optimization, while Bregman cyclic projections can solve the primal problem.The dual gradient uses traces involving exp(−C(λ)K0) and constraint matrices.
Squared Frobenius divergence: The squared Frobenius divergence produces a strictly convex kernelizable objective with scalar function f_frob(x) = (x − η)^2.For η = 0 and relative-distance constraints, the formulation matches the earlier method of.
Semidefinite programs: A linear-objective semidefinite program is also kernelizable after variational reformulation because its inner optimization satisfies the general theorem’s conditions.The paper separately establishes that problem (5.8) is kernelizable and considers regularizations for its potentially multiple solutions.
Semidefinite programs: The linear SDP may use Frobenius-norm or log-determinant regularization to select among multiple solutions of the non-strictly convex problem.The Frobenius option seeks a minimum-norm solution, while the log-determinant option seeks a minimum-determinant solution.

6 Experimental Results

Experiments evaluate kernelized and linear LogDet metric learning across UCI, software-support, object-recognition, and text-classification tasks. The results show robust classification performance, gains over baseline kernels and metrics, and efficient learning with reduced bases.

Experimental Results: Kernelization enables LogDet metric learning with nonlinear kernels and reduced bases, improving efficiency over optimizing the full O(n^2) kernel matrix.The learned kernel can be parameterized by O(k^2) values when a basis of size k is used.
Low-Dimensional Data Sets: LogDet Linear is optimal within 95% confidence intervals across all software-support datasets and remains robust as feature dimensionality increases.For Latex, its lowest reported error rate is 0.15 at d = 20 dimensions.
Low-Dimensional Data Sets: LogDet Linear generally trains significantly faster than MCML and LMNN in the software-support experiments.Training times are reported as averages over five runs on a dual-processor 3.2 GHz Intel Xeon system.
Metric Learning for Object Recognition: On Caltech-101, learned kernels improve nearest-neighbor recognition and outperform existing single-kernel classifier methods.The learned CORR kernel reaches 61.0% accuracy at T = 15 and 69.6% at T = 30; learned PMK reaches 52.2% and 62.1%, respectively.
Metric Learning for Text Classification: In text classification, LogDet Linear becomes increasingly more accurate as the basis size grows and significantly outperforms existing methods.The experiments use Classic3 and newsgroup datasets and compare against squared Euclidean distance and LSA.

7 Conclusions

The paper develops kernelized linear-transformation metric learning for high-dimensional spaces, extending beyond LogDet to broader convex losses. Experiments compare the approach with state-of-the-art techniques, while larger-scale online and local-metric settings remain future work.

LogDet divergence enables efficient kernel-space metric learning through Bregman projections and learned kernel functions.The learned metric can be restricted to a small-dimensional basis, supporting datasets with high-dimensional feature spaces.
Many convex loss functions for learning linear transformations can also be kernelized, although their optimizations may be more expensive than LogDet.
Experiments evaluate the method on benchmark, high-dimensional vision, and text classification problems against existing state-of-the-art techniques.
Online learning remains a promising direction for datasets larger than those considered, and future work will explore multiple local metrics with LogDet.