Efficient Pairwise Difference Learning: A Comparative Study of Encoding Strategies and Training Pair Selection

Bernard Georges; Mohamed Karim Belaid; Manuel Rodrigues

cs.LGOct 15, 2026

Efficient Pairwise Difference Learning: A Comparative Study of Encoding Strategies and Training Pair Selection

Authors: Bernard Georges, Mohamed Karim Belaid, Manuel Rodrigues

Organizations: University of Minho, ALGORITMI CENTER LASI, Braga, Portugal · IDIADA Fahrzeugtechnik GmbH, Munich, Germany

Abstract

Pairwise Difference Learning for Classification (PDC) enhances supervised learning in low-data regimes by training a binary similarity classifier on pairs of instances rather than individual samples, effectively inflating the training set from $n$ to $O(n^2)$ examples. However, the PDC framework leaves critical implementation choices underspecified, particularly regarding input representation and pair selection strategies. This work systematically investigates these design decisions through extensive empirical evaluation. We compare four feature encoders (paired features, triplet with relative difference, absolute difference, and a novel triplet with absolute difference) alongside four pair selection strategies ranging from exhaustive to kernel-thinning-based schemes. Experiments across nearly 200 benchmark classification datasets using Decision Tree, Multilayer Perceptron, Gaussian Naive Bayes, and Support Vector Classifier as base models reveal that the proposed triplet with absolute difference encoder ( $φ_{\mathrm{3dabs}}$ ) achieves the highest average F1 scores. More notably, restricting training to upper-triangle pairs reduces computational time by approximately 40% with negligible accuracy loss. Kernel thinning-based selection provided no accuracy benefits while substantially increasing computational overhead. Overall, PDC configurations outperformed base models in 94% of tested cases, though no single configuration dominated universally, suggesting dataset-specific optimization remains an open challenge.

Figures & tables

Encoder	Output vector $\phi(x_{i},x_{j})$
$\phi_{\mathrm{2d}}(x_{i},x_{j})$	$(22,\;8,\;38,\;72)$
$\phi_{\mathrm{3drel}}(x_{i},x_{j})$	$(22,\;8,\;38,\;72,\;-16,\;-64)$
$\phi_{\mathrm{abs}}(x_{i},x_{j})$	$(16,\;64)$
$\phi_{\mathrm{3dabs}}(x_{i},x_{j})$	$(22,\;8,\;38,\;72,\;16,\;64)$

Table 1: Example of the four pair encoders on two Titanic passengers with features Age (years) and Fare (US$).

$D$	$\delta_{\blacksquare}(D)$	$\delta_{\mathord{\hbox to3.81pt{\vbox to3.81pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{\lx@inpgf@ignorespaces}}{{}{{}}{} {}{} {}{} {\lx@inpgf@ignorespaces}\lxSVG@fill\lxSVG@drawpath@unclipped{M 1.42 4.72 L 4.72 4.72 L 4.72 1.42 Z}{stroke:none} \lx@inpgf@ignorespaces {}{{}}{} {}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 4.72 L 4.72 0}{fill:none} \lx@inpgf@ignorespaces } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}(D)$	$\delta_{\mathord{\hbox to2.39pt{\vbox to2.39pt{\pgfpicture\makeatletter\hbox{\hskip-1.02426pt\lower 1.02426pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{\lx@inpgf@ignorespaces}} {}{{}}{} {}{} {}{} {\lx@inpgf@ignorespaces}\lxSVG@fill\lxSVG@drawpath@unclipped{M 1.42 4.72 L 4.72 4.72 L 4.72 1.42 Z}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}(D)$	, $m=1$
$\begin{bmatrix}\spadesuit\\[2.0pt] \heartsuit\\[2.0pt] \diamondsuit\\[2.0pt] \clubsuit\end{bmatrix}$	$\begin{bmatrix}\spadesuit\spadesuit&\spadesuit\heartsuit&\spadesuit\diamondsuit&\spadesuit\clubsuit\\ \heartsuit\spadesuit&\heartsuit\heartsuit&\heartsuit\diamondsuit&\heartsuit\clubsuit\\ \diamondsuit\spadesuit&\diamondsuit\heartsuit&\diamondsuit\diamondsuit&\diamondsuit\clubsuit\\ \clubsuit\spadesuit&\clubsuit\heartsuit&\clubsuit\diamondsuit&\clubsuit\clubsuit\end{bmatrix}$	$\begin{bmatrix}\spadesuit\spadesuit&\spadesuit\heartsuit&\spadesuit\diamondsuit&\spadesuit\clubsuit\\ &\heartsuit\heartsuit&\heartsuit\diamondsuit&\heartsuit\clubsuit\\ &&\diamondsuit\diamondsuit&\diamondsuit\clubsuit\\ &&&\clubsuit\clubsuit\end{bmatrix}$	$\begin{bmatrix}\phantom{\spadesuit\spadesuit}&\spadesuit\heartsuit&\spadesuit\diamondsuit&\spadesuit\clubsuit\\ &&\heartsuit\diamondsuit&\heartsuit\clubsuit\\ &&&\diamondsuit\clubsuit\\ &&&\end{bmatrix}$	$\begin{bmatrix}\spadesuit\spadesuit&\spadesuit\heartsuit&&\\ &&&\heartsuit\clubsuit\\ &&\diamondsuit\diamondsuit&\\ &&&\clubsuit\clubsuit\end{bmatrix}$

Table 2: Toy example of pair-selection patterns on

D=(\spadesuit,\heartsuit,\diamondsuit,\clubsuit)

. Each matrix entry denotes the ordered pair

(x_{i},x_{j})

; empty cells indicate discarded pairs. For

with

m=1

, an arbitrary half of the pairs are kept.

		$\phi_{\mathrm{3drel}}$	$\phi_{\mathrm{abs}}$	$\phi_{\mathrm{3dabs}}$
All Pairs ( $\boldsymbol{\delta_{\blacksquare}}$ )	$F_{1}$	0.804 $\pm$ 0.151	0.797 $\pm$ 0.154	0.810 $\pm$ 0.150
	Time [min]	81	68	81
UT w/ diagonal ( $\boldsymbol{\delta_{\mathord{\hbox to3.81pt{\vbox to3.81pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{\lx@inpgf@ignorespaces}}{{}{{}}{} {}{} {}{} {\lx@inpgf@ignorespaces}\lxSVG@fill\lxSVG@drawpath@unclipped{M 1.42 4.72 L 4.72 4.72 L 4.72 1.42 Z}{stroke:none} \lx@inpgf@ignorespaces {}{{}}{} {}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 4.72 L 4.72 0}{fill:none} \lx@inpgf@ignorespaces } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}}$ )	$F_{1}$	0.806 $\pm$ 0.148	0.796 $\pm$ 0.155	0.810 $\pm$ 0.148
	Time [min]	43	50	44
UT w/o diagonal ( $\boldsymbol{\delta_{\mathord{\hbox to2.39pt{\vbox to2.39pt{\pgfpicture\makeatletter\hbox{\hskip-1.02426pt\lower 1.02426pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{\lx@inpgf@ignorespaces}} {}{{}}{} {}{} {}{} {\lx@inpgf@ignorespaces}\lxSVG@fill\lxSVG@drawpath@unclipped{M 1.42 4.72 L 4.72 4.72 L 4.72 1.42 Z}{stroke:none} \lx@inpgf@ignorespaces \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}}$ )	$F_{1}$	0.806 $\pm$ 0.148	N/A	0.809 $\pm$ 0.147
	Time [min]	44	N/A	48

Table 3:

F_{1}

score Comparison of different input combinations

Figure 1: Histogram of the $F_{1}$ score difference of between a method and $\phi_{\mathrm{3drel}}$ 1 1 1 The notation for this figure is based on the original work with: $\phi_{1}=\phi_{\mathrm{abs}}$ , $\phi_{2}=\phi_{\mathrm{3dabs}}$ and $\delta_{0}=\boldsymbol{\delta_{\blacksquare}}$

	Baseline	Before Pairing (m=1)	After Pairing (m=1)	After Pairing (m=2)
Results (80 DS)	0.838	0.811	0.838	0.825
Time [min]	7	7	209	147

Table 4: Comparison of

F_{1}

and run time across Different Kernel Thinning Settings for 80 Datasets per experiment

Model (num of datasets)	No PDL	$\phi_{\mathrm{3drel}}\circ\boldsymbol{\delta_{\blacksquare}}$	$\phi_{\mathrm{3dabs}}\circ\boldsymbol{\delta_{\blacksquare}}$	$\phi_{\mathrm{3dabs}}\circ\boldsymbol{\delta_{\mathord{\hbox to3.81pt{\vbox to3.81pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} \lxSVG@begingroup@{stroke=#000000} \lxSVG@begingroup@{fill=#000000} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width=0.4pt} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin=1} {{\lx@inpgf@ignorespaces}}{{}{{}}{} {}{} {}{} {\lx@inpgf@ignorespaces}\lxSVG@fill\lxSVG@drawpath@unclipped{M 1.42 4.72 L 4.72 4.72 L 4.72 1.42 Z}{stroke:none} \lx@inpgf@ignorespaces {}{{}}{} {}{}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 4.72 L 4.72 0}{fill:none} \lx@inpgf@ignorespaces } \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}}}}$	$\phi_{\mathrm{2d}}\circ\boldsymbol{\delta_{\blacksquare}}$
MLP (187 DS)	0.759 $\pm$ 0.168	0.794 $\pm$ 0.168	0.810 $\pm$ 0.159	0.803 $\pm$ 0.162	0.794 $\pm$ 0.169
GaussianNB (195 DS)	0.727 $\pm$ 0.179	0.603 $\pm$ 0.230	0.691 $\pm$ 0.212	0.684 $\pm$ 0.215	0.327 $\pm$ 0.088
SVC (70 DS)	0.869 $\pm$ 0.152	0.871 $\pm$ 0.157	0.880 $\pm$ 0.141	0.880 $\pm$ 0.144	N/A
Decision Tree (195 DS)	0.782 $\pm$ 0.152	0.804 $\pm$ 0.151	0.810 $\pm$ 0.150	0.810 $\pm$ 0.148	N/A

Table 5:

F_{1}

score of every experiment done in the different models

Data-Efficient Learning

Data-efficient learning develops methods that achieve accurate, robust models with fewer labeled examples, training samples, or interactions.

See all 239 papers

Pairwise Difference Learning for Classification
Jun 28, 2024Mohamed Karim Belaid, Maximilian Rabus, Eyke HüllermeierClassification Meta-Learning
IDIADA Fahrzeugtechnik GmbH, Munich, Germany · Dr. Ing. h.c. F. Porsche AG Stuttgart, Germany · Ludwig-Maximilians-Universität Munich, Germany
Pairwise Learning Increases Data Efficiency in Deep Neural Networks
Oct 20, 2026Robert Bain, Marjan Rashidi, Elizabeth ChrastilData-Efficient Learning Small-Data Learning
Department of Neurobiology & Behavior, University of California, Irvine, Irvine, CA 92697, USA · Department of Cognitive Sciences, University of California, Irvine, Irvine, CA 92697, USA
Uncertainty Quantification in Pairwise Difference Learning for Classification
Oct 15, 2026Mohamed Karim Belaid, Maximilian Rabus, Eyke HüllermeierUncertainty Quantification Uncertainty Decomposition
IDIADA Fahrzeugtechnik GmbH, Munich, Germany. · Dr. Ing. h.c. F. Porsche AG, Stuttgart, Germany. · Institute of Informatics, University of Munich (LMU), Germany. +2

Jun 28, 2024J/K move · Enter open · S save

Pairwise Difference Learning for Classification

Mohamed Karim Belaid, Maximilian Rabus, Eyke Hüllermeier

IDIADA Fahrzeugtechnik GmbH, Munich, Germany · Dr. Ing. h.c. F. Porsche AG Stuttgart, Germany · Ludwig-Maximilians-Universität Munich, Germany

Classification Meta-Learning Supervised Learning Binary Classification

Open paper AskPDF arXiv

Pairwise difference learning (PDL) has recently been introduced as a new meta-learning technique for regression. Instead of learning a mapping from instances to outcomes in the standard way, the key idea is to learn a function that takes two instances as input and predicts the difference between the respective outcomes. Given a function of this kind, predictions for a query instance are derived from every training example and then averaged. This paper extends PDL toward the task of classification and proposes a meta-learning technique for inducing a PDL classifier by solving a suitably defined (binary) classification problem on a paired version of the original training data. We analyze the performance of the PDL classifier in a large-scale empirical study and find that it outperforms state-of-the-art methods in terms of prediction performance. Last but not least, we provide an easy-to-use and publicly available implementation of PDL in a Python package.

Abstract

Data-Efficient Learning

Explore similar work

Pairwise Difference Learning for Classification

Pairwise Learning Increases Data Efficiency in Deep Neural Networks

Uncertainty Quantification in Pairwise Difference Learning for Classification