Reproduce “Pairwise Supervision Can Provably Elicit a Decision Boundary” on OpenResearch

About this paper

Han Bao, Takuya Shimada, Liyuan Xu, Issei Sato, Masashi Sugiyama

CIPS learns a classifier from pairwise comparisons without class labels. It assigns each example a scalar score and predicts pair agreement from the product of scores, yielding a boundary whose pairwise error is tied to pointwise error up to label permutation. On codrna, CIPS reached 6.3% clustering error with 1,000 pairs, matching supervised learning; orientation requires an unequal, majority prior.

Key insights

• A product-type similarity learning objective can inherently elicit a binary decision boundary, directly translating pairwise relationships into classification separation.
• Under conditions where class priors are not equal and the majority class is known, correct class labels can be assigned using only pairwise supervision, with error probability decaying exponentially.
• The CIPS framework unifies various similarity learning methods by showing they can be interpreted as minimizing a pairwise surrogate risk, providing a consistent theoretical basis for their application to classification.

Summary by alphaXiv.