Introduction
In Information Retrieval (IR), "Learning to Rank" (LTR) is essential for ordering documents by relevance. Modern ranking models often utilize thousands of features, ranging from simple word frequencies to complex PageRank scores. However, this high dimensionality introduces significant challenges: redundant features can lead to overfitting ("The Noise Problem"), and calculating numerous features per query increases latency ("The Efficiency Problem").
Feature selection aims to mitigate these issues. While standard methods often rely on the convex $\ell_1$ (Lasso) penalty, it frequently suffers from bias, shrinking important feature weights excessively. This paper proposes an embedded approach using non-convex regularizations to achieve superior sparsity without sacrificing ranking quality.
Methodology: Beyond Convexity
The authors extend the RankSVM framework, which treats ranking as a pairwise classification problem. The core innovation is the introduction of non-convex penalties—specifically the Log penalty, Minimax Concave Penalty (MCP), and the $\ell_p$ pseudo-norm ($p < 1$).
Unlike the linear growth of the $\ell_1$ penalty, these non-convex functions are "nearly unbiased." As shown in the figure below, they apply a steep penalty to small weights (inducing sparsity) but saturate or flatten for larger weights, allowing important features to retain their magnitude.
To optimize these non-convex objectives, the researchers employed two primary strategies:
- Accelerated Forward-Backward Splitting (FBS): A fast proximal gradient method for convex baselines.
- Reweighted $\ell_1$ Scheme: A Majorization-Minimization approach that solves a sequence of weighted $\ell_1$ problems, effectively finding solutions for the non-convex penalties using efficient convex optimization tools.
Experimental Evaluation
The framework was tested on nine benchmark datasets from the LETOR 3.0 and 4.0 corpora, including Ohsumed, Topic Distillation (TD), and Million Query (MQ) tracks. These datasets represent a diverse range of ranking tasks and feature distributions.
Key Results and Insights
- Unprecedented Sparsity: The non-convex models, particularly those using the log penalty, achieved up to a 6x reduction in the number of features compared to standard $\ell_1$ methods. For instance, on the MQ2008 dataset, the model maintained top-tier performance using only 9% of available features.
- Performance Parity: Despite the drastic reduction in features, ranking quality—measured by Mean Average Precision (MAP) and Normalized Discounted Cumulative Gain (NDCG)—remained statistically equivalent to state-of-the-art methods like FenchelRank and FSMRank.
- The Log Penalty Advantage: The log penalty consistently emerged as the most effective regularizer for balancing extreme sparsity with high accuracy.
Conclusion
This research demonstrates that non-convex regularizations can significantly enhance the efficiency and interpretability of ranking models. By aggressively pruning irrelevant features while preserving the signal of important ones, these methods offer a robust solution to the high-dimensionality challenges in modern search engines. Future work may explore automated hyperparameter tuning and the extension of this sparse framework to multitask learning environments.
Summary updated