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:
- 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.
- 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