Non-convex Regularizations for Feature Selection in Ranking With Sparse SVM

Léa Laporte, Rémi Flamary, Stéphane Canu, Sébastien Déjean, Josiane Mothe

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.

Taxonomy of feature selection approaches in ranking, highlighting the proposed embedded method.

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.

Comparison of regularization functions: the convex l1 penalty versus non-convex log, lp, and mcp penalties.

To optimize these non-convex objectives, the researchers employed two primary strategies:

  1. Accelerated Forward-Backward Splitting (FBS): A fast proximal gradient method for convex baselines.
  2. 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

BibTeX
@article{laporte2014non,
  author = {Léa Laporte and Rémi Flamary and Stéphane Canu and Sébastien Déjean and Josiane Mothe},
  title = {{Non-convex Regularizations for Feature Selection in Ranking With Sparse SVM}},
  journal = {IEEE Trans. Neural Networks Learn. Syst.},
  year = {2014},
  doi = {10.1109/tnnls.2013.2286696},
}
Figure