Distance Metric Learning with Application to Clustering with Side-Information

Eric P. XingAndrew Y. NgMichael I. JordanStuart J. Russell

article2002NeurIPS3,361 citations

Develops a convex optimization framework to learn Mahalanobis distance metrics from pairwise similarity constraints, guaranteeing global optimality and substantially improving clustering accuracy on multidimensional data.

Listen

Many machine learning and data analysis methods, including clustering and nearest-neighbor algorithms, depend on a distance metric that captures meaningful relationships in the data. When the default Euclidean metric produces clusters that do not align with a user’s intent, practitioners have had few systematic options beyond manual adjustment. The paper addresses this limitation by developing a method to learn a metric automatically from examples of similar (and, when available, dissimilar) pairs of points.

The work sets out to formulate metric learning as a convex optimization problem that finds a Mahalanobis distance respecting the supplied pairwise constraints, then to demonstrate that the resulting metric improves clustering accuracy on both synthetic and real data.

The approach begins with a convex program that minimizes distances between similar pairs while enforcing a lower bound on distances between dissimilar pairs and requiring the metric matrix to remain positive semi-definite. Efficient algorithms are derived for both diagonal and full matrices: Newton-Raphson for the diagonal case and projected gradient ascent for the full case. The method is evaluated on artificial data designed to expose limitations of Euclidean distance and on nine UCI data sets, where “little” and “much” side-information is generated by sampling pairs that share class labels. Performance is measured by clustering accuracy under four variants of K-means, with and without the learned metric and with and without instance-level constraints.

The learned metrics consistently raise clustering accuracy. On the UCI collections, K-means that uses either the diagonal or full learned metric outperforms standard K-means in nearly every data set; combining the metric with constrained K-means yields further gains, sometimes by large margins. Accuracy rises with the amount of side-information supplied, although the benefit saturates at different rates across data sets. Visualizations of the rescaled data confirm that similar points are drawn together while dissimilar points remain separated.

These results show that modest amounts of pairwise side-information can be turned into a reusable metric that generalizes to unseen points and improves downstream unsupervised tasks. The convex formulation guarantees that solutions are globally optimal and computationally tractable, removing the need for ad-hoc metric tweaking.

The principal limitations are dependence on the quality and quantity of side-information and the higher cost of the full-matrix procedure. Further gains are likely from integrating the metric-learning step with other algorithms that rely on distances, such as kernel methods or nearest-neighbor classifiers, and from testing on larger, higher-dimensional collections where the value of an automatically tuned metric may be even greater.

University of California Berkeley clustering methods k-means algorithm optimization Distance Metric Learning Similar Pair Convex Optimization

Xing et al (2002).pdf

Paper: A training algorithm for optimal margin classifiers, B. Boser et al. (1992). Understanding the foundational theory of maximal-margin hyperplanes and quadratic programming from support vector machines is essential before studying distance metric learning framed as convex optimization.

Paper: Distance Metric Learning for Large Margin Nearest Neighbor Classification, Kilian Q. Weinberger et al. (2005). This paper extends distance metric learning to large-margin nearest neighbor classification by casting the objective as a semidefinite program directly inspired by foundational metric learning principles.
Paper: Dimensionality Reduction by Learning an Invariant Mapping, Raia Hadsell et al. (2006). This work builds upon pairwise distance metric learning by introducing a siamese network architecture that learns nonlinear invariant mappings using a contrastive loss.

Cover for Distance Metric Learning with Application to Clustering with Side-Information

Abstract

Many algorithms rely critically on being given a good metric over their inputs. For instance, data can often be clustered in many “plausible” ways, and if a clustering algorithm such as K-means initially fails to find one that is meaningful to a user, the only recourse may be for the user to manually tweak the metric until sufficiently good clusters are found. For these and other applications requiring good metrics, it is desirable that we provide a more systematic way for users to indicate what they consider “similar.” For instance, we may ask them to provide examples. In this paper, we present an algorithm that, given examples of similar (and, if desired, dissimilar) pairs of points in ℝⁿ, learns a distance metric over ℝⁿ that respects these relationships. Our method is based on posing metric learning as a convex optimization problem, which allows us to give efficient, local-optima-free algorithms. We also demonstrate empirically that the learned metrics can be used to significantly improve clustering performance.

Topics

clustering methods k-means algorithm optimization optimization problems adaptive algorithms user information

Keywords

Distance Metric Learning Similar Pair Convex Optimization Mahalanobis Distance K-means Constrained K-means Side Information UCI Dataset Gradient Ascent Iterative Projection

1 Introduction
2 Learning Distance Metrics
2.1 The case of diagonal $A$
2.2 The case of full $A$
Iterate
Iterate
3 Experiments and Examples
3.1 Examples of learned distance metrics
3.2 Application to clustering
4 Conclusions
References

Knowls

Knowl 1 — Convex Formulation for Distance Metric Learning with Side Information
model/method
Given a collection of data points $\{x_i\}_{i=1}^m ⊂ \mathbb{R}^n$ , a set of similar pairs $\mathcal{S} = \{(x_i, x_j) : x_i \text{ and } x_j \text{ are similar}\}$ , and a set of dissimilar pairs $\mathcal{D} = \{(x_i, x_j) : x_i \text{ and } x_j \text{ are dissimilar}\}$ (or all pairs not in $\mathcal{S}$ ), distance metric learning seeks a positive semi-definite matrix $A \in \mathbb{R}^{n \times n}$ ( $A \succeq 0$ ) parameterizing the Mahalanobis distance metric:

$d_A(x, y) = \|x - y\|_A = \sqrt{(x - y)^T A (x - y)}$

The matrix $A$ is learned by solving the constrained optimization problem:

$\min_A \sum_{(x_i, x_j) \in \mathcal{S}} \|x_i - x_j\|_A^2$

$\text{subject to } \sum_{(x_i, x_j) \in \mathcal{D}} \|x_i - x_j\|_A \ge 1$

$A \succeq 0$

The objective function is linear in the parameters of $A$ , the dissimilarity constraint $\sum_{(x_i, x_j) \in \mathcal{D}} \|x_i - x_j\|_A \ge 1$ defines a convex feasible set, and the set of positive semi-definite matrices $A \succeq 0$ is a convex cone. Consequently, the optimization problem is convex and free of local optima.
Knowl 2 — Diagonal Distance Metric Learning via Newton-Raphson Optimization
algorithm
When the distance metric matrix is restricted to be diagonal, $A = \text{diag}(A_{11}, A_{22}, \dots, A_{nn})$ with $A_{ii} \ge 0$ , minimizing the squared distance between similar pairs subject to the unsquared distance constraint on dissimilar pairs is equivalent (up to a positive scalar multiple) to minimizing the objective function:

$g(A_{11}, \dots, A_{nn}) = \sum_{(x_i, x_j) \in \mathcal{S}} \|x_i - x_j\|_A^2 - \log \left( \sum_{(x_i, x_j) \in \mathcal{D}} \|x_i - x_j\|_A \right)$

subject to $A_{ii} \ge 0$ for all $i \in \{1, \dots, n\}$ . The problem is solved via the Newton-Raphson method with a line-search step size.
Input: Similar pairs $\mathcal{S}$ , dissimilar pairs $\mathcal{D}$ , data points $\{x_i\}_{i=1}^m \subset \mathbb{R}^n$
Output: Diagonal positive semi-definite matrix $A = \text{diag}(A_{11}, \dots, A_{nn})$
Initialize $A_{kk} > 0$ for $k = 1, \dots, n$
repeat
    Compute gradient $\nabla g(A)$ and Hessian $H = \nabla^2 g(A)$
    Compute Newton step direction $\Delta A = - H^{-1} \nabla g(A)$
    Find step-size $\alpha > 0$ via line-search to maximize descent subject to $A_{kk} + \alpha \Delta A_{kk} \ge 0$ for all $k$
    Update $A \leftarrow A + \alpha \Delta A$
until convergence of $A$
return $A$
Knowl 3 — Full Distance Metric Learning via Projected Gradient Ascent
algorithm
To learn a full positive semi-definite matrix $A \in \mathbb{R}^{n \times n}$ , the metric learning problem is formulated in the equivalent dual form:

$\max_A g(A) = \sum_{(x_i, x_j) \in \mathcal{D}} \|x_i - x_j\|_A$

$\text{subject to } f(A) = \sum_{(x_i, x_j) \in \mathcal{S}} \|x_i - x_j\|_A^2 \le 1$

$A \succeq 0$

The algorithm alternates between taking gradient ascent steps on $g(A)$ orthogonalized with respect to $\nabla_A f(A)$ and applying iterative projections onto the constraint sets $C_1 = \{A : f(A) \le 1\}$ and $C_2 = \{A : A \succeq 0\}$ .
Input: Similar pairs $\mathcal{S}$ , dissimilar pairs $\mathcal{D}$ , step-size $\alpha > 0$
Output: Positive semi-definite metric matrix $A \in \mathbb{R}^{n \times n}$
Initialize $A \succeq 0$ satisfying $f(A) \le 1$
repeat
    Compute $\nabla_A g(A)$ and $\nabla_A f(A)$
    Compute projected gradient $(\nabla_A g(A))_{\perp \nabla_A f}$ orthogonal to $\nabla_A f(A)$
    Update $A \leftarrow A + \alpha (\nabla_A g(A))_{\perp \nabla_A f}$
    repeat
        Project onto $C_1$ : $A \leftarrow \arg\min_{A' \in C_1} \|A' - A\|_F^2$
        Project onto $C_2$ :
            Compute eigendecomposition $A = X \Lambda X^T$ with $\Lambda = \text{diag}(\lambda_1, \dots, \lambda_n)$
            Set $\Lambda' = \text{diag}(\max(0, \lambda_1), \dots, \max(0, \lambda_n))$
             $A \leftarrow X \Lambda' X^T$
    until $A$ converges
until overall convergence
return $A$
Projection onto $C_1$ requires solving a sparse system of linear equations in $O(n^2)$ time. Projection onto $C_2$ is performed via the spectral decomposition of $A$ and thresholding eigenvalues at zero.
Knowl 4 — Degeneracy of Quadratic Dissimilarity Constraints in Metric Learning
theoretical result
In metric learning under similarity set $\mathcal{S}$ and dissimilarity set $\mathcal{D}$ , enforcing a squared distance constraint on dissimilar pairs:

$\sum_{(x_i, x_j) \in \mathcal{D}} \|x_i - x_j\|_A^2 \ge 1$

instead of the unsquared constraint $\sum_{(x_i, x_j) \in \mathcal{D}} \|x_i - x_j\|_A \ge 1$ , causes the optimal positive semi-definite matrix $A$ to always have rank 1.

Maximizing the ratio of squared distances corresponds to maximizing the Rayleigh quotient:

$\frac{\sum_{(x_i, x_j) \in \mathcal{D}} \|x_i - x_j\|_A^2}{\sum_{(x_i, x_j) \in \mathcal{S}} \|x_i - x_j\|_A^2} = \frac{\text{trace}(A M_\mathcal{D})}{\text{trace}(A M_\mathcal{S})} = \frac{\sum_{k=1}^n a_k^T M_\mathcal{D} a_k}{\sum_{k=1}^n a_k^T M_\mathcal{S} a_k}$

where $M_\mathcal{D} = \sum_{(x_i, x_j) \in \mathcal{D}} (x_i - x_j)(x_i - x_j)^T$ , $M_\mathcal{S} = \sum_{(x_i, x_j) \in \mathcal{S}} (x_i - x_j)(x_i - x_j)^T$ , and $A = \sum_{k=1}^n a_k a_k^T$ . The optimum is attained by choosing $a_1$ as the principal generalized eigenvector of $M_\mathcal{D} a_1 = \lambda M_\mathcal{S} a_1$ and setting $a_2 = \dots = a_n = 0$ , which collapses the entire dataset onto a single one-dimensional line.
Knowl 5 — Data Rescaling Interpretation of Mahalanobis Metric Learning
definition
Learning a Mahalanobis distance metric $d_A(x, y) = \sqrt{(x - y)^T A (x - y)}$ with a positive semi-definite matrix $A \succeq 0$ is mathematically equivalent to applying a linear map to the data:

$x \mapsto A^{1/2} x$

and measuring standard Euclidean distances between the transformed points:

$\|A^{1/2} x - A^{1/2} y\|_2 = \sqrt{(x - y)^T A^{1/2} A^{1/2} (x - y)} = \sqrt{(x - y)^T A (x - y)} = d_A(x, y)$

When $A = \text{diag}(A_{11}, \dots, A_{nn})$ is diagonal, each feature axis $k$ is scaled by $\sqrt{A_{kk}}$ , weighting feature dimensions independently. When $A$ is a general full matrix, the transformation corresponds to combined scaling and rotation across dimensions.
Knowl 6 — Clustering with Side-Information Framework
model/method
Pairwise similarity side-information $\mathcal{S}$ is incorporated into clustering via four comparative algorithmic variants:
1. K-means: Standard K-means using default Euclidean distance $\|x_i - \mu_k\|_2^2$ between data points $x_i$ and cluster centroids $\mu_k$ , ignoring $\mathcal{S}$ .
2. Constrained K-means (C-Kmeans): K-means with hard constraints where all points belonging to the same connected component $C$ of the graph formed by edges $\mathcal{S}$ are assigned to the identical cluster centroid $\mu_k$ that minimizes $\sum_{x_i \in C} \|x_i - \mu_k\|_2^2$ .
3. K-means + metric: K-means with distortion computed using the learned Mahalanobis distance $\|x_i - \mu_k\|_A^2 = (x_i - \mu_k)^T A (x_i - \mu_k)$ .
4. Constrained K-means + metric: Constrained K-means using both the connected component constraints from $\mathcal{S}$ and the learned Mahalanobis metric $A$ to compute centroid distances.
Knowl 7 — Pairwise Clustering Accuracy Metric for Clustering Evaluation
definition
Let $\hat{c}_i \in \{1, \dots, K\}$ denote the cluster assignment assigned to point $x_i$ ( $i = 1, \dots, m$ ) by a clustering algorithm, and let $c_i$ denote the true class label. In the 2-cluster setting, clustering performance is evaluated by pairwise accuracy:

$\text{Accuracy} = \frac{\sum_{i > j} \mathbf{1}\{\mathbf{1}\{c_i = c_j\} = \mathbf{1}\{\hat{c}_i = \hat{c}_j\}\}}{0.5 m (m - 1)}$

where $\mathbf{1}\{\cdot\}$ is the indicator function. This metric represents the probability that a randomly drawn pair $(x_i, x_j)$ agrees on whether the points belong to the same cluster or different clusters.

For datasets with more than 2 clusters ( $K > 2$ ), to prevent inflated accuracy scores due to the predominance of dissimilar pairs, pairs $(x_i, x_j)$ are sampled such that same-cluster pairs (according to $c$ ) and different-cluster pairs each receive equal total probability weight ( $0.5$ ).
Knowl 8 — Empirical Clustering Performance on Benchmark Datasets
empirical result
The metric learning clustering framework was evaluated on 9 UCI benchmark datasets (Boston housing, Ionosphere, Iris plants, Wine, Balance, Breast cancer, Soybean, Protein, Diabetes) under two side-information regimes: "little" side-information (where the number of connected components $K_c \approx 0.9 N$ ) and "much" side-information ( $K_c \approx 0.7 N$ ).

Results demonstrated:
- Clustering with a learned metric (diagonal or full $A$ ) consistently improved accuracy over naive K-means across almost all datasets.
- Combining Constrained K-means with a learned metric (C-Kmeans + metric) outperformed Constrained K-means alone across most datasets, often by a large margin.
- Increasing side-information from "little" to "much" consistently led to higher clustering accuracy across all metric variants.
- On datasets with correlated features (e.g., Wine), full metric learning achieved superior performance rapidly with minimal constraints; on high-dimensional or complex datasets (e.g., Protein), full metric learning yielded smaller improvements over diagonal metric learning.

Coverage note — Visual synthetic data plots (Figures 2, 3, 4, 5) and dataset-specific numerical tables (which appear only as bar charts in Figure 6 and curves in Figure 7) were omitted as individual knowls and are fully covered by the empirical result and data transformation knowls.

References

1.C. Atkeson, A. Moore, and S. Schaal. Locally weighted learning. AI Review, 1996.
2.T. Cox and M. Cox. Multidimensional Scaling. Chapman & Hall, London, 1994.
3.C. Domeniconi and D. Gunopulos. Adaptive nearest neighbor classification using support vector machines. In Advances in Neural Information Processing Systems 14. MIT Press, 2002.
4.G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins Univ. Press, 1996.
5.T. Hastie and R. Tibshirani. Discriminant adaptive nearest neighbor classification. IEEE Transactions on Pattern Analysis and Machine Learning, 18:607–616, 1996.
6.T.S. Jaakkola and D. Haussler. Exploiting generative models in discriminaive classifi er. In Proc. of Tenth Conference on Advances in Neural Information Processing Systems, 1999.
7.I.T. Jolliffe. Principal Component Analysis. Springer-Verlag, New York, 1989.
8.R. Rockafellar. Convex Analysis. Princeton Univ. Press, 1970.
9.S.T. Roweis and L.K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science 290: 2323-2326.
10.B. Scholkopf and A. Smola. Learning with Kernels. In Press, 2001.
11.N. Tishby, F. Pereira, and W. Bialek. The information bottleneck method. In Proc. of the 37th Allerton Conference on Communication, Control and Computing, 1999.
12.K. Wagstaff, C. Cardie, S. Rogers, and S. Schroedl. Constrained k-means clustering with background knowledge. In Proc. 18th International Conference on Machine Learning, 2001.

Citation

MLA

Xing, E., et al. “Distance Metric Learning with Application to Clustering with Side-Information”. Advances in Neural Information Processing Systems, vol. 15, 2002, https://proceedings.neurips.cc/paper_files/paper/2002/file/c3e4035af2a1cde9f21e1ae1951ac80b-Paper.pdf.

APA

Xing, E., Jordan, M., Russell, S. J., & Ng, A. (2002). Distance Metric Learning with Application to Clustering with Side-Information. Advances in Neural Information Processing Systems, 15. https://proceedings.neurips.cc/paper_files/paper/2002/file/c3e4035af2a1cde9f21e1ae1951ac80b-Paper.pdf

Chicago

Xing, E., M. Jordan, S. J. Russell, and A. Ng. 2002. “Distance Metric Learning with Application to Clustering with Side-Information”. Advances in Neural Information Processing Systems 15. https://proceedings.neurips.cc/paper_files/paper/2002/file/c3e4035af2a1cde9f21e1ae1951ac80b-Paper.pdf.

Harvard

Xing, E. et al. (2002) “Distance Metric Learning with Application to Clustering with Side-Information”, Advances in Neural Information Processing Systems. Curran Associates, Inc. Available at: https://proceedings.neurips.cc/paper_files/paper/2002/file/c3e4035af2a1cde9f21e1ae1951ac80b-Paper.pdf.

Vancouver

1. Xing E, Jordan M, Russell SJ, Ng A (2002) Distance Metric Learning with Application to Clustering with Side-Information. Advances in Neural Information Processing Systems 15:

BibTeX

@inproceedings{xing2002distance,
  title = {Distance Metric Learning with Application to Clustering with Side-Information},
  author = {Xing, Eric and Jordan, Michael and Russell, Stuart J. and Ng, Andrew},
  year = {2002},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {15},
  url = {https://proceedings.neurips.cc/paper_files/paper/2002/file/c3e4035af2a1cde9f21e1ae1951ac80b-Paper.pdf}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Distance Metric Learning with Application to Clustering with Side-Information

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Convex Formulation for Distance Metric Learning with Side Information

Knowl 2 — Diagonal Distance Metric Learning via Newton-Raphson Optimization

Knowl 3 — Full Distance Metric Learning via Projected Gradient Ascent

Knowl 4 — Degeneracy of Quadratic Dissimilarity Constraints in Metric Learning

Knowl 5 — Data Rescaling Interpretation of Mahalanobis Metric Learning

Knowl 6 — Clustering with Side-Information Framework

Knowl 7 — Pairwise Clustering Accuracy Metric for Clustering Evaluation

Knowl 8 — Empirical Clustering Performance on Benchmark Datasets

References

Citation

BibTeX

Access the Paper