Adaptive affinity matrix for unsupervised metric learning

Yaoyi Li, Junxuan Chen, Yiru Zhao, Hongtao Lu

This paper, presented by researchers from Shanghai Jiao Tong University, introduces Adaptive Affinity Matrix (AdaAM), a novel framework for unsupervised metric learning that significantly improves how we represent relationships between data points for clustering.

TL;DR

AdaAM learns an optimized, low-rank affinity matrix by treating similarity learning as a spectral decomposition problem. By combining this learned global structure with local neighborhood information, it achieves state-of-the-art clustering accuracy—particularly on challenging datasets with varying illumination—while remaining computationally efficient.

What Problem Does This Paper Address?

Spectral clustering is a powerhouse in unsupervised learning, but it has three major "Achilles' heels":

  1. Out-of-sample extension: Traditional methods often only provide an embedding for the training data; they don't tell you how to handle a new data point without re-running the whole algorithm.
  2. Scalability: Complexity often scales poorly with the number of data points.
  3. Graph Robustness: The quality of clustering depends entirely on the "affinity graph" (the map of how similar points are). If your initial distance metric is noisy (e.g., two different faces look "close" because the lighting is similar), the clustering fails.

The authors aim to create a method that extracts more "adaptive" similarity information—meaning it learns the best way to measure similarity for a specific dataset—without the massive computational overhead of previous iterative approaches.

Methods

The core innovation of AdaAM is how it constructs the affinity matrix ($\Delta$).

  • Low-Rank Decomposition: Instead of using a standard heat kernel, the authors assume the ideal affinity matrix should be low-rank (reflecting the underlying cluster structure). They decompose the affinity matrix into a product of two identical low-rank matrices ($PP^T$).
  • Optimization via SVD: They reformulate the objective of "locality preserving" into a problem that can be solved using Singular Value Decomposition (SVD). This is much faster than the iterative optimization used in previous methods like PCAN.
  • Hybrid Approach: The final affinity matrix is a combination of this learned "intermediate" matrix and a standard $k$-Nearest Neighbor ($k$-NN) graph. This allows the model to capture both global structure and local nuances.
  • Metric Learning via LPP: To solve the out-of-sample problem, they apply Locality Preserving Projections (LPP) to their learned graph. This produces a linear transformation matrix ($A$) that can be applied to any new data point to project it into the learned metric space.
  • Sparsification: To prevent the matrix from becoming "too dense" and noisy, they implement a strategy to keep only the most significant similarity values, determined by a parameter $t$ that scales with the number of clusters.

Datasets

The authors evaluated AdaAM on five well-known image benchmarks:

  • UMIST: 575 images of 20 individuals (faces).
  • COIL20: 1,440 images of 20 objects.
  • USPS: 9,298 images of handwritten digits (16x16).
  • MNIST: 10,000 images of handwritten digits (28x28).
  • ExYaleB: 2,414 face images of 38 individuals under varying lighting conditions.

Key Insights and Ideas

  • The Power of Low-Rank Priors: By forcing the affinity matrix to be low-rank, the model inherently filters out "noise edges"—connections between points that are close in Euclidean space but belong to different classes.
  • Efficiency of "One-Shot" Learning: While the math allows for an iterative approach (alternating between updating the projection and the affinity matrix), the authors found that a single iteration provides nearly all the accuracy gains (see Fig. 1a). This makes it much faster than competing adaptive methods.
  • Robustness to Illumination: The most striking "aha moment" occurs with the ExYaleB dataset. Standard methods fail here because lighting changes create more variance than the actual differences between faces. AdaAM’s ability to learn a global structure allows it to see past these lighting "noises."

Key Results

  • Accuracy: AdaAM achieved the highest average and maximal accuracy across almost all datasets.
  • The ExYaleB Breakthrough: On the ExYaleB dataset, AdaAM achieved 54.36% average accuracy, while all other compared methods (including $k$-NN, DN, and PCAN) hovered around 23-26%. This represents a massive leap in handling complex, high-variance data.
  • Speed: In execution time tests on MNIST (Fig. 3), AdaAM was significantly faster than ClustRF-Bi and PCAN-kMeans, maintaining a complexity closer to simpler, non-adaptive methods like Cons-$k$NN.

Limitations and Future Work

  • Neighborhood Sensitivity: Like many graph-based methods, AdaAM's performance is sensitive to the choice of $k$ (neighborhood size). If $k$ is too small, the model lacks enough pairwise information to form a robust low-rank approximation.
  • Parameter Tuning: The sparsification strategy relies on a coefficient $\alpha$. While the authors suggest values (2.5 to 5), these were found via "rough parameter search," suggesting the need for a more automated way to determine optimal sparsification.
  • Linear Constraint: The method uses a linear projection (LPP). While efficient, it may not capture highly non-linear manifolds as well as deep learning-based unsupervised methods might.

Summary updated

Abstract

Spectral clustering is one of the most popular clustering approaches with the capability to handle some challenging clustering problems. Only a little work of spectral clustering focuses on the explicit linear map which can be viewed as the distance metric learning. In practice, the selection of the affinity matrix exhibits a tremendous impact on the unsupervised learning. In this paper, we propose a novel method, dubbed Adaptive Affinity Matrix (AdaAM), to learn an adaptive affinity matrix and derive a distance metric. We assume the affinity matrix to be positive semidefinite with ability to quantify the pairwise dissimilarity. Our method is based on posing the optimization of objective function as a spectral decomposition problem. The provided matrix can be regarded as the optimal representation of pairwise relationship on the manifold. Extensive experiments on a number of image data sets show the effectiveness and efficiency of AdaAM.
BibTeX
@inproceedings{li2016adaptive,
  author = {Yaoyi Li and Junxuan Chen and Yiru Zhao and Hongtao Lu},
  title = {{Adaptive affinity matrix for unsupervised metric learning}},
  booktitle = {ICME},
  year = {2016},
  url = {https://openreview.net/forum?id=WGxm5gQ4HJ},
}

Loading related content...

Figure