Overview
This paper introduces a highly scalable approach to learning ranking functions. Instead of enforcing constraints on every individual pair of points across different ranks, the authors require that the convex hulls of different classes be separated. By applying Farkas' Lemma, they transform a computationally explosive $O(m^2)$ constraint problem into a lean, linear system. This method is orders of magnitude faster than traditional approaches and is capable of handling datasets with tens of thousands of samples without running out of memory.
The Problem: Quadratic Explosion in Ranking
In many machine learning tasks, the goal is not merely to classify an object (e.g., "is this a house or a car?") but to rank them (e.g., "which house is more expensive?"). This is known as ordinal regression or learning to rank.
The traditional approach to this problem involves creating constraints for every possible pair of samples where one should be ranked higher than the other. If you have $m$ training samples, the number of these constraints grows quadratically—$O(m^2)$. For a dataset of just 5,000 samples, this results in millions of constraints. This "quadratic explosion" makes standard ranking algorithms, like Ranking SVMs, agonizingly slow or physically impossible to run on modest hardware once the dataset grows beyond a few thousand points.
Methodology: Convex Hulls and Farkas' Lemma
The authors propose a "more stringent" but mathematically more tractable version of the ranking problem to bypass this quadratic explosion.
- Convex Hull Separation: Instead of enforcing that "every point in Class A must be ranked higher than every point in Class B," the algorithm dictates that "the entire convex hull of Class A must be ranked higher than the convex hull of Class B." A convex hull is essentially the smallest geometric "envelope" containing all points in a set.
- Farkas' Lemma: Because a convex hull contains an infinite number of points, the authors use Farkas' theorem of alternatives. This mathematical bridge allows them to swap an infinite set of constraints for a finite number of variables and linear equalities.
- Optimization: The resulting formulation looks very much like a Support Vector Machine (SVM) but with a significantly reduced number of slack variables. While traditional ranking SVMs might require $O(m^2)$ slack variables, this method only requires $O(m)$.
- Kernelization: The approach is not limited to linear rankings. By using the "kernel trick," the data can be projected into higher-dimensional spaces to find complex, non-linear ranking functions.
Order Graphs: Chain vs. Full
The authors experimented with different "order graphs" to define the relationships between ranks.
- A Full Graph enforces constraints between every possible rank combination (e.g., Rank 1 vs 2, 1 vs 3, 2 vs 3).
- A Chain Graph only enforces constraints between adjacent ranks (e.g., Rank 1 vs 2, 2 vs 3).
Surprisingly, the simpler Chain Graph often performed better and was more stable. This suggests that "over-constraining" the model with a Full Graph can lead to worse generalization.
Key Results: Speed and Accuracy
The authors evaluated their approach on nine publicly available benchmark datasets, primarily sourced from regression tasks and discretized into five ordinal bins. Datasets ranged from small sets of 74 samples to the massive CA Housing dataset with 20,640 samples, which served as the primary "stress test" for scalability.
- Speed: The proposed algorithm was several orders of magnitude faster than state-of-the-art methods like SVM-light and Informative Vector Machines (IVM), as seen in the logarithmic run time charts.
- Scalability: On the CA Housing dataset, both SVM-light and IVM either ran out of memory or failed to complete a single fold after 24 hours. The convex hull method handled it easily.
- Accuracy: Measured by the Generalized Wilcoxon-Mann-Whitney statistic (essentially the Area Under the ROC Curve for ranking), the proposed method was at least as accurate as, and often better than, the existing benchmarks.
Limitations and Future Work
- Order Graph Selection: While the paper demonstrates that the choice of order graph (Chain vs. Full) matters significantly, it does not provide a definitive heuristic for choosing the "optimal" graph for a novel dataset.
- Semi-Supervised Learning: Because the formulation is independent of the specific regularizer used, the authors note it could be extended to semi-supervised learning using graph-Laplacians to incorporate unlabeled data.
- Computational Geometry Overhead: While reducing slack variables to $O(m)$ is a massive win, the complexity of dealing with convex hulls in very high-dimensional feature spaces (via kernels) remains a potential area for further algorithmic optimization.
Summary updated