Abstract
Learning to Rank (LTR) is a fundamental task in Information Retrieval, often complicated by high-dimensional feature spaces containing redundant or noisy data. While convex $\ell_1$ regularization (Lasso) is commonly used for feature selection, it often introduces bias and fails to achieve optimal sparsity. This paper presents a framework for LTR that utilizes non-convex regularizations—specifically the Log penalty, Minimax Concave Penalty (MCP), and $\ell_p$ pseudo-norms—within a Sparse Support Vector Machine (SVM) architecture. By employing a reweighted $\ell_1$ optimization scheme, the proposed method achieves significant feature reduction (up to a factor of twelve) while maintaining or improving ranking accuracy across standard Letor benchmarks.
1. Introduction
In modern Information Retrieval (IR), the "Learning to Rank" (LTR) paradigm automates the construction of ranking functions by training on query-document pairs. However, as the number of available features grows, models increasingly suffer from the "curse of dimensionality." Many features are irrelevant or redundant, leading to overfitting and increased computational costs during inference.
Traditional approaches to feature selection often treat it as a preprocessing step or rely on convex $\ell_1$ regularization. While $\ell_1$ methods are computationally efficient, they are known to be biased, as they penalize all coefficients linearly regardless of their magnitude. This paper explores the integration of non-convex penalties directly into the SVM ranking objective to induce sharper sparsity and improve model interpretability without sacrificing predictive performance.
2. Methodology
The authors formulate the ranking problem as a pairwise classification task using a Sparse SVM. The core innovation lies in the application of a diverse suite of regularization terms.
2.1 Regularization Suite
The framework evaluates both convex and non-convex penalties:
- Convex: Standard $\ell_1$ (Lasso) and weighted $\ell_1$.
- Non-convex: The Log penalty, Minimax Concave Penalty (MCP), and the $\ell_p$ pseudo-norm ($0 < p < 1$).
These non-convex penalties are designed to more closely approximate the $\ell_0$ "norm," which counts the number of non-zero entries. Unlike the $\ell_1$ norm, non-convex penalties relax the penalty for larger coefficients, thereby reducing the bias inherent in Lasso and allowing the model to retain important features at their true scale.
2.2 Optimization Strategy
To address the challenges of non-convex optimization, the authors implement two distinct solvers:
- RankSVM-$\ell_1$: For convex objectives, an Accelerated Forward-Backward Splitting (FBS) algorithm (FISTA) is used to ensure fast convergence.
- Non-convex Solver: For non-convex objectives, a reweighted $\ell_1$ scheme based on Majorization-Minimization is employed. This approach iteratively solves a sequence of weighted convex problems, converging to a stationary point of the original non-convex objective. This makes the non-convex approach computationally tractable for practical IR applications.
3. Experimental Setup
The framework was rigorously tested on nine benchmark datasets from the Letor 3.0 and Letor 4.0 corpora, including Ohsumed, MQ2007, and MQ2008. These datasets represent a wide range of scales, from 50 to nearly 1,700 queries, providing a comprehensive evaluation of the model's ability to handle varying levels of sparsity and data density. Performance was measured using standard IR metrics: Mean Average Precision (MAP) and Normalized Discounted Cumulative Gain (NDCG).
4. Results and Discussion
The experimental results challenge the traditional assumption of a strict trade-off between model sparsity and ranking accuracy.
4.1 Sparsity and Accuracy
The most significant finding is the ability of non-convex penalties to drastically reduce the feature set. On average, non-convex methods selected only half as many features as their convex counterparts. In specific instances, such as the MQ datasets, the log penalty achieved a twelve-fold reduction in features compared to state-of-the-art competitors.
Crucially, this aggressive pruning did not degrade performance. The ranking quality (MAP and NDCG) remained statistically equivalent to or better than established embedded methods like FenchelRank and FSMRank.
4.2 Efficiency and Bias
By reducing the feature count by up to a factor of six compared to standard $\ell_1$ regularization, the resulting models are significantly more efficient for real-time ranking. The reduction in bias—achieved by not over-penalizing large, informative coefficients—allows the non-convex models to maintain high accuracy even with a minimal feature set.
5. Conclusion and Future Work
This research demonstrates that non-convex regularization is a powerful tool for feature selection in Learning to Rank. By integrating these penalties into a Sparse SVM framework, the authors show that it is possible to create highly sparse, interpretable, and accurate ranking models.
Future research directions include the fine-tuning of non-convex parameters ($\gamma$ and $\epsilon$) to further enhance performance and the optimization of iterative solvers for extremely large-scale datasets. Additionally, extending the framework to multitask learning could allow for shared feature selection across related ranking tasks, such as cross-lingual or cross-domain retrieval.
Summary updated