On Tree-based Methods for Similarity Learning

Stéphan Clémençon, Robin Vogel

Abstract

In many situations, the choice of an adequate similarity measure or metric on the feature space dramatically determines the performance of machine learning methods. Building automatically such measures is the specific purpose of metric/similarity learning. In Vogel et al. (2018), similarity learning is formulated as a pairwise bipartite ranking problem: ideally, the larger the probability that two observations in the feature space belong to the same class (or share the same label), the higher the similarity measure between them. From this perspective, the ROC curve is an appropriate performance criterion and it is the goal of this article to extend recursive tree-based ROC optimization techniques in order to propose efficient similarity learning algorithms. The validity of such iterative partitioning procedures in the pairwise setting is established by means of results pertaining to the theory of U-processes and from a practical angle, it is discussed at length how to implement them by means of splitting rules specifically tailored to the similarity learning task. Beyond these theoretical/methodological contributions, numerical experiments are displayed and provide strong empirical evidence of the performance of the algorithmic approaches we propose.

Introduction

In modern machine learning applications—ranging from biometric identification to recommendation engines—the ability to quantify the "similarity" between two objects is often more critical than simple classification. Traditionally, this challenge is addressed through metric learning, which seeks to find a distance function that brings similar items closer together. However, this paper proposes a paradigm shift: treating similarity learning as a pairwise bipartite ranking problem.

Under this framework, the goal is to produce a similarity score such that, for any given query, items sharing the same label are ranked higher than those with different labels. By framing the problem this way, the authors can leverage the Receiver Operating Characteristic (ROC) curve as a gold-standard performance metric, allowing for optimization at specific operating points—such as maximizing the True Positive Rate at very low False Positive Rates—which is essential for high-stakes applications like security screening.

Methodology: Similarity TreeRank

The authors extend the TreeRank algorithm, an iterative partitioning method originally designed for univariate ranking, to the domain of similarity. The primary challenge in this transition is that similarity functions must be inherently symmetric: $s(x, x') = s(x', x)$. A standard decision tree applied to pairs would not naturally respect this constraint, potentially treating the pair $(A, B)$ differently from $(B, A)$.

The Symmetric LeafRank Rule

To solve the symmetry problem, the authors introduce the Symmetric LeafRank splitting rule. Instead of partitioning the feature space $\mathcal{X}$ directly, the algorithm operates on the product space $\mathcal{X} \times \mathcal{X}$. They employ a mathematical projection technique using orthogonal transformations and absolute values to ensure the tree "sees" pairs symmetrically without the need to double the training data. This ensures that the resulting similarity measure is mathematically sound and computationally efficient.

Cost-Sensitive Recursive Partitioning

The algorithm grows trees by treating each node split as a cost-sensitive binary classification problem. This recursive approach allows the model to "zoom in" on specific regions of the ROC space. By iteratively refining the partitions, the algorithm builds a piecewise constant similarity function that optimizes the functional ROC curve directly, rather than just the Area Under the Curve (AUC).

Theoretical Foundations and U-Processes

One of the significant hurdles in similarity learning is that data points are not independent. If a dataset contains points $A, B,$ and $C$, the pair $(A, B)$ is inherently dependent on the pair $(A, C)$ because they share a common element. Standard learning theory, which assumes independent and identically distributed (i.i.d.) data, does not apply here.

The authors utilize the theory of $U$-processes to provide rigorous generalization bounds. They prove that the Similarity TreeRank algorithm achieves a universal logarithmic convergence rate in the sup-norm of the ROC space, specifically at a rate of $\exp(-\lambda \sqrt{\log n})$. This theoretical guarantee ensures that the similarity measures learned by the tree will generalize well to unseen data despite the complex dependencies between pairs.

Empirical Results

The proposed method was evaluated using both synthetic datasets and the MNIST handwritten digit dataset.

  • Synthetic Data: The algorithm successfully recovered "ground truth" similarity structures across various noise levels and class asymmetries, demonstrating its robustness as a ranking tool.
  • MNIST Performance: The authors implemented a Ranking Forest—an ensemble of similarity trees. In head-to-head comparisons, this forest significantly outperformed Large Margin Nearest Neighbor (LMNN), a popular linear metric learning baseline.
  • Comparison to Deep Learning: While the tree-based approach outperformed linear methods, it did not surpass specialized Neural Network encodings optimized with softmax cross-entropy. However, the authors highlight that the TreeRank approach offers greater interpretability and a direct optimization of the ranking objective, which neural networks often only approximate.

Conclusion and Future Work

This research establishes a robust theoretical and algorithmic framework for tree-based similarity learning. By treating similarity as a ranking problem and utilizing $U$-statistics to handle data dependencies, the authors have created a method that is both mathematically grounded and empirically effective.

Future work remains in addressing the computational complexity of operating on $n^2$ pairs, which remains a challenge for massive datasets. Additionally, the authors suggest that the "LeafRank" procedure within the nodes could be further enhanced by incorporating non-linear SVMs or deeper local trees to improve the granularity of the similarity scores.

Summary updated

Abstract

In many situations, the choice of an adequate similarity measure or metric on the feature space dramatically determines the performance of machine learning methods. Building automatically such measures is the specific purpose of metric/similarity learning. In Vogel et al. (2018), similarity learning is formulated as a pairwise bipartite ranking problem: ideally, the larger the probability that two observations in the feature space belong to the same class (or share the same label), the higher the similarity measure between them. From this perspective, the ROC curve is an appropriate performance criterion and it is the goal of this article to extend recursive tree-based ROC optimization techniques in order to propose efficient similarity learning algorithms. The validity of such iterative partitioning procedures in the pairwise setting is established by means of results pertaining to the theory of U-processes and from a practical angle, it is discussed at length how to implement them by means of splitting rules specifically tailored to the similarity learning task. Beyond these theoretical/methodological contributions, numerical experiments are displayed and provide strong empirical evidence of the performance of the algorithmic approaches we propose.
BibTeX
@inproceedings{clemencon2019tree,
  author = {Stéphan Clémençon and Robin Vogel},
  title = {{On Tree-based Methods for Similarity Learning}},
  booktitle = {LOD},
  year = {2019},
  url = {https://openreview.net/forum?id=1wATvZDPCIH},
}
Figure