Pairwise Constraints & Metric Learning

A label answers “what class is this?” Pairwise supervision answers a narrower question: “should these two examples be treated as the same kind?” or “must they be distinguished?” This can be cheaper to obtain, and it can express a user's intended notion of similarity even when globally named classes are unavailable.

The constraint vocabulary #

If the statements are treated as exact equivalence information, must-link is symmetric and transitively closes: $a\sim b$ and $b\sim c$ imply $a\sim c$. A cannot-link between any members of two must-link components then applies to the components. This graph preprocessing can expose contradictions before optimization.

Real judgments are often noisy, contextual, or probabilistic. Then hard transitive closure can amplify one error across an entire component. A soft loss with confidence weights is safer when annotators disagree or “similar” depends on context.

Three distinct ways to use a pair #

These routes answer different questions. A constrained k-means result may satisfy known pairs without learning a useful distance for unseen data. A learned metric may improve neighbourhoods without guaranteeing every training constraint. A pairwise classifier can predict whether two items match while never producing a globally consistent partition.

Mahalanobis learning is linear representation learning #

A common family learns

$$d_A(x_i,x_j)=\sqrt{(x_i-x_j)^\top A(x_i-x_j)},\qquad A\succeq0.$$

Positive semidefiniteness makes distances real and gives $A=L^\top L$, so

$$d_A(x_i,x_j)=\lVert Lx_i-Lx_j\rVert_2.$$

The matrix can rescale coordinates, rotate correlated directions, and collapse irrelevant directions. A diagonal $A$ only reweights features; a full $A$ learns interactions but has many more parameters and needs stronger regularization.

Xing and colleagues formulate one early convex version: minimize total squared distance over similar pairs while forcing dissimilar pairs to retain aggregate separation, subject to $A\succeq0$. Convexity removes local optima for that objective, not statistical error: biased pairs, weak features, or a mismatched linear geometry still produce a poor model.

Margin losses use pairs without explicit distance fitting #

Pairwise constraints can also enter a discriminative classifier. Nguyen and Caruana's PCSVM augments a multiclass margin formulation with same-class and different-class pair terms. The durable idea is broader than that particular solver: partial relation labels can constrain a decision function even when an absolute label is missing.

Modern contrastive losses use a related pattern—pull positive pairs together and push negatives apart—but the source of a “positive,” the margin, normalization, and sampling distribution define the actual learning problem. Augmented views of one image, two records judged equivalent by a person, and two observations sharing a class label are not interchangeable evidence.

Constraint collection is part of the model #

Uniformly sampling all pairs is rarely sensible. With many classes, almost every random pair is negative, so a model can appear accurate by learning little. Useful policies include sampling uncertain neighbours, balancing same and different judgments, covering disconnected regions, and querying pairs whose answer would merge or separate large constraint components.

The protocol must record:

• who or what generated each judgment and under which definition of similarity;
• confidence, disagreement, and whether abstention was allowed;
• how pairs were sampled and whether the learner influenced later queries;
• whether duplicated entities or derived pairs cross data partitions.

Failure modes #

Other common failures are:

• inconsistent closure: a cannot-link occurs inside a must-link component;
• hub domination: one frequently paired example determines much of the loss;
• easy-negative inflation: evaluation contains mostly obviously different pairs;
• transductive overclaim: constraints improve one fixed clustering, but no rule was learned for new points;
• geometry mismatch: a global linear transform cannot express context-dependent similarity;
• constraint satisfaction as quality: obeying supplied pairs says nothing about unconstrained regions or downstream utility.

Evaluation must match the route #

For constrained clustering, report pair satisfaction alongside an external clustering measure on held-out labels and stability across constraint samples. For a learned metric, evaluate retrieval, k-nearest-neighbour, or clustering performance on unseen entities—not only training loss. For pair classification, report class-balanced metrics and calibrate the operating threshold. In every case, compare against the same downstream algorithm with the original metric so the contribution of pair supervision is identifiable.