Active Metric Learning for Supervised Classification

Krishnan Kumaran, Dimitri Papageorgiou, Yutong Chang, Minhan Li, Martin TakácarXiv 2018 · OpenReview

TL;DR

This paper introduces a novel approach to metric learning for supervised classification that avoids the need for pre-defined "target neighbors" or "triplets," making it more general and robust. Crucially, it integrates active learning to intelligently select data points for acquisition, significantly reducing computational burden and improving classification performance.

What Problem Does This Paper Address?

Choosing the right distance metric is fundamental for many machine learning algorithms, from clustering (like k-means) to classification (like nearest neighbors). The effectiveness of these algorithms hinges on how well the chosen metric captures the underlying structure of the data. Traditional metric learning methods often rely on user-defined "target neighbors" (specific points that should be close) or "triplets" (sets of three points with defined relationships). However, this reliance introduces a significant dependency on user expertise and can lead to distorted or infeasible metrics if these targets are poorly chosen. Furthermore, many real-world scenarios involve iterative learning where data is acquired over time, and existing methods don't effectively guide this acquisition process. This paper addresses the challenge of learning optimal distance metrics in a more general, data-driven way, and importantly, leverages this learned metric to guide efficient data acquisition for improved learning.

Methods

The core of this paper lies in formulating the metric learning problem as a mixed-integer linear optimization (MILP) problem. This is a significant contribution, as the authors claim it's the first time this has been done for metric learning. They propose a general form for the distance metric that extends the Mahalanobis metric.

Key methodological innovations include:

  • Elimination of Pre-defined Targets: Unlike methods like LMNN (Large Margin Nearest Neighbor), this approach does not require explicit "target neighbors," "triplets," or "similarity pairs." Instead, it defines optimality based on ensuring co-class points are generally closer than non-class points, making it more applicable to scenarios where such explicit guidance is unavailable.
  • Mixed-Integer Linear Optimization (MILP): The problem of finding the optimal metric is framed as an MILP. This allows for the incorporation of complex constraints and the handling of discrete decisions (e.g., whether a point is an outlier).
  • Active Learning for Data Acquisition: A novel aspect is the integration of active learning. After an initial metric is learned, the algorithm identifies "outlier" and "boundary" points based on a derived R-ratio. The recommendation is to prioritize acquiring new data in these regions, as they are most informative for refining the metric and improving classification. This targeted acquisition is presented as a "value-of-information" criterion.
  • Handling Outliers: The framework explicitly incorporates mechanisms to identify and potentially remove outliers, leading to more robust metric learning.

Datasets

The paper evaluates its approach on both synthetic and real-world datasets:

  • Synthetic Data: Used to illustrate the geometric properties of the learned metrics, class boundaries, and the effectiveness of outlier identification. Examples include 2D datasets with complex class structures and a 6D dataset.
  • Real Datasets:
    • MNIST: Handwritten digit recognition dataset. The authors used a compressed 16D feature representation.
  • Medical/Biological Datasets: Specifically, cod-rna, diabetes, and iris datasets were used.

The paper does not introduce new benchmark datasets but rather applies its method to existing ones for comparison.

Key Insights and Ideas

  • Data-Driven Metric Learning is Powerful: By removing the reliance on user-defined targets, the learned metric becomes more general and less prone to biases introduced by potentially incorrect human annotations.
  • MILP is a Game-Changer for Metric Learning: Framing metric learning as an MILP opens up possibilities for solving complex optimization problems that were previously intractable or required heuristic approximations. This allows for more principled and potentially optimal solutions.
  • Intelligent Data Acquisition is Key to Efficiency: The most significant insight is the synergy between metric learning and active learning. Identifying "boundary" and "outlier" points based on the learned metric provides a principled way to select the most informative data for acquisition, leading to substantial computational savings and faster convergence.
  • Outliers and Boundary Points are Informative: The R-ratio metric effectively highlights points that are critical for understanding class separation and refining the distance metric. Prioritizing these points for data acquisition is a highly effective strategy.
  • Smoother Class Boundaries: The learned metrics tend to produce smoother and more robust class boundaries compared to standard metrics like Euclidean, especially in the presence of noise or outliers.

Key Results

  • Competitive Classification Performance: The proposed method achieves competitive classification accuracy on real datasets (MNIST, cod-rna, diabetes, iris) compared to state-of-the-art alternatives like LMNN, often with less tuning. For instance, on cod-rna and diabetes, their method (MeLL0) showed improvement over Euclidean distance and various LMNN configurations.
  • Data Economy: The active learning component demonstrated significant potential for data economy. For example, learning a metric from only boundary points on a synthetic dataset yielded a metric very close to one learned from the full dataset. Similarly, training a DNN using only boundary points achieved very low testing error.
  • Robustness to Outliers: The outlier removal procedure improved the robustness of the learned metric, leading to smoother class boundaries and better performance compared to standard metrics when outliers were present.
  • Interpretability: The learned Mahalanobis metric, visualized through eigenvalues and eigenvectors, offers insights into the relative importance of different features for classification.

Limitations and Future Work

  • Computational Cost: While MILP solvers have improved, solving these problems can still be computationally intensive, especially for very large datasets. The paper mentions that challenging MILPs are routinely solved, but this remains a practical consideration.
  • Positive Semidefiniteness: The paper notes that enforcing positive semidefiniteness for the matrix B (a desirable property for a true Mahalanobis metric) requires extensions and can complicate the MILP formulation. While they show it's not always essential for good performance, it's a limitation for achieving a strictly valid Mahalanobis metric.
  • Generalization of Active Learning: The active learning strategy is primarily demonstrated for the K=1 nearest neighbor case, though the authors suggest it can be extended to K>1 with modifications.
  • Future Work: The authors suggest exploring extensions for enforcing positive semidefiniteness and sparsification of the learned metric. They also highlight the applicability of their active learning approach to other metric learning paradigms and machine learning models like DNNs. The potential for using their method to guide data acquisition for other complex models is a significant avenue for future research.

Summary updated

Abstract

Clustering and classification critically rely on distance metrics that provide meaningful comparisons between data points. We present mixed-integer optimization approaches to find optimal distance metrics that generalize the Mahalanobis metric extensively studied in the literature. Additionally, we generalize and improve upon leading methods by removing reliance on pre-designated "target neighbors," "triplets," and "similarity pairs." Another salient feature of our method is its ability to enable active learning by recommending precise regions to sample after an optimal metric is computed to improve classification performance. This targeted acquisition can significantly reduce computational burden by ensuring training data completeness, representativeness, and economy. We demonstrate classification and computational performance of the algorithms through several simple and intuitive examples, followed by results on real image and medical datasets.
BibTeX
@misc{kumaran2018active,
  author = {Krishnan Kumaran and Dimitri Papageorgiou and Yutong Chang and Minhan Li and Martin Takác},
  title = {{Active Metric Learning for Supervised Classification}},
  year = {2018},
  eprint = {1803.10647},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.10647},
}
Figure