On Tree-Based Methods for Similarity Learning

Stéphan Clémençon, Robin Vogel

TL;DR

This paper adapts the TreeRank algorithm—originally designed for ranking—to the domain of similarity learning. By introducing a novel "Symmetric LeafRank" splitting rule, the authors create a recursive, tree-based method that optimizes the entire ROC curve for pairwise comparisons while guaranteeing that the resulting similarity measures remain mathematically symmetric.

What Problem Does This Paper Address?

In many machine learning tasks, like biometric identification or recommendation systems, the goal isn't just to classify an object, but to determine how "similar" two objects are. Traditionally, this is framed as metric learning.

The authors argue that similarity learning is essentially a pairwise bipartite ranking problem: given a query, you want to rank all items in a database such that those sharing the same label as the query appear at the top. While many methods focus on optimizing the Area Under the Curve (AUC), real-world applications (like airport security) often require maximizing the True Positive Rate at a very specific, low False Positive Rate. Optimizing for these local points on an ROC curve is computationally difficult and often non-convex. This paper seeks an algorithmic way to optimize the functional ROC curve directly using decision trees.

Methods

The authors build upon TreeRank, an iterative partitioning algorithm. The core challenge in applying TreeRank to similarity is that similarity functions must be symmetric ($s(x, x') = s(x', x)$).

Key technical contributions include:

  • Symmetric LeafRank: A specialized splitting rule. Instead of splitting the feature space $\mathcal{X}$ directly, the algorithm operates on the product space $\mathcal{X} \times \mathcal{X}$. To maintain symmetry, they project pairs onto a subspace where the order of elements doesn't change the coordinates' absolute values.
  • Cost-Sensitive Recursive Partitioning: The algorithm grows a tree where each node split is treated as a cost-sensitive binary classification problem. This allows the tree to "zoom in" on regions of the ROC space that need the most optimization.
  • Theoretical Guarantees: Using the theory of $U$-processes (which handles dependencies between pairs of data points), the authors prove that their method achieves a "universal" logarithmic generalization rate bound in the sup-norm of the ROC space.

Datasets

The paper evaluates the approach using:

  1. Synthetic Data: Data generated from random trees of varying depths to test the algorithm's ability to recover "ground truth" similarity structures under different noise levels and class asymmetries.
  2. MNIST: The classic handwritten digit dataset. The authors used PCA to reduce the 784-dimensional images to 153 dimensions to manage memory requirements for baseline comparisons.

Key Insights and Ideas

  • Similarity as Ranking: The "aha moment" is treating similarity not as a distance to be minimized, but as a score used to rank pairs. This shifts the focus from geometry to order statistics.
  • The Symmetry Constraint: You can't just throw a standard decision tree at pairs of data; the tree would treat $(A, B)$ differently from $(B, A)$. The authors' mathematical trick (using orthogonal projections and absolute values) ensures the tree "sees" pairs symmetrically without doubling the training data.
  • Handling Dependencies: Most learning theory assumes data points are independent (i.i.d.). In similarity learning, if you have points $A, B,$ and $C$, the pair $(A, B)$ is not independent of $(A, C)$. The use of $U$-statistics is a rigorous way to prove the algorithm still works despite these inherent overlaps.

Key Results

  • Theoretical Robustness: The authors proved that the Similarity TreeRank algorithm converges to the optimal ROC curve at a rate of $\exp(-\lambda \sqrt{\log n})$.
  • MNIST Performance: In empirical tests on MNIST, the Ranking Forest (an ensemble of these similarity trees) significantly outperformed LMNN (Large Margin Nearest Neighbor), a widely used linear metric learning baseline.
  • Comparison to Deep Learning: While the tree-based method beat linear baselines, it still trailed behind a specialized Neural Network encoding (optimized with softmax cross-entropy). However, the authors note that their method is more interpretable and directly targets the ranking objective.

Limitations and Future Work

  • Computational Complexity: Operating on pairs ($n^2$ combinations) is inherently expensive. While the authors used a forest of 44 trees trained on $10^5$ pairs each, scaling to massive datasets remains a challenge.
  • Rate of Convergence: The proven logarithmic rate is theoretically "slow," though the authors argue this is a byproduct of the global nature of the similarity problem.
  • LeafRank Optimization: The authors suggest that the performance could be further improved by using more sophisticated "LeafRank" procedures (the internal classifiers used to split nodes), such as non-linear SVMs or deeper local trees.

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 [21], 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 $$\mathrm{ROC}$$ curve is an appropriate performance criterion and it is the goal of this article to extend recursive tree-based $$\mathrm{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},
}

Loading related content...

Figure