Rémi Flamary

Site web professionel

RankSVM avec régularization non-convexe

%%% \def\w{\mathbf{w}} %%%

Description

Cette toolbox est une implémentation d'un solveur RankSVM avec régularization non-convexe Le code a été utilisé pour les expérimentations numériques du papier

L. Laporte, R. Flamary, S. Canu, S. Déjean, J. Mothe, Nonconvex Regularizations for Feature Selection in Ranking With Sparse SVM, Neural Networks and Learning Systems, IEEE Transactions on, Vol. 25, N. 6, pp 1118-1130, 2014.
Abstract: Feature selection in learning to rank has recently emerged as a crucial issue. Whereas several preprocessing approaches have been proposed, only a few works have been focused on integrating the feature selection into the learning process. In this work, we propose a general framework for feature selection in learning to rank using SVM with a sparse regularization term. We investigate both classical convex regularizations such as l1 or weighted l1 and non-convex regularization terms such as log penalty, Minimax Concave Penalty (MCP) or lp pseudo norm with p lower than 1. Two algorithms are proposed, first an accelerated proximal approach for solving the convex problems, second a reweighted l1 scheme to address the non-convex regularizations. We conduct intensive experiments on nine datasets from Letor 3.0 and Letor 4.0 corpora. Numerical results show that the use of non-convex regularizations we propose leads to more sparsity in the resulting models while prediction performance is preserved. The number of features is decreased by up to a factor of six compared to the l1 regularization. In addition, the software is publicly available on the web.
BibTeX:
@article{tnnls2014,
author = { Laporte, L. and Flamary, R. and Canu, S. and Déjean, S. and Mothe, J.},
title = {Nonconvex Regularizations for Feature Selection in Ranking With Sparse SVM},
journal = { Neural Networks and Learning Systems, IEEE Transactions on},
volume = {25},
number = {6},
pages = {1118-1130},
editor = {},
year = {2014}
} 

Solver

On fournit un solveur générique permétant de résoudre le problème d'optimisation:

%% \begin{equation*} \min_{\w} \sum_{i=1}^{n} \max(0,1-(\mathbf{x}_i^T\w))^2 + \Omega(\w) \end{equation*} %%

où $\Omega(\w)$ peut être :

  • Norme l1 : $\Omega(\w)=\sum_i |w_i|$
  • Pseudo-norme lp avec $ 0<p < 1$ : $ \Omega(\w)=\sum_i |w_i|^p $
  • Pénalité log : $ \Omega(\w)=\sum_i \log(\epsilon+|w_i|) $
  • MCP. : $\Omega(\w)=\left\{\begin{array}{ll}\lambda |w_j|-|w_j|^2/2\gamma & \mbox{ if } |w_j| \leq \gamma\lambda \\ \gamma\lambda^2/2 & \mbox{ if } |w_j| > \gamma\lambda \end{array}\right.$

Cette toolbox tourne sur Matlab/Octave. L'algorithm utilisé pour résoudre le problème d'optimisation est décrit ici et l'algorithme pour résoudre le sous-problème d'optimisation est décrit dzns le papier FISTA. La toolbox contient également le code du papier FSMrank tel que fournit par les auteurs.

Si vous utilisez ce code dans vos travaux veuillez citer Non-convex Regularizations for Feature Selection in Ranking with Sparse SVM.

Téléchargement

Version courante : 1.0

Téléchargement :

Installation

Version rapide:

  • Extraire les fichiers zip
  • Ajouter tous les dossiers et sous-dossiers au path matlab/octave.
  • Points d'entrée:
    • test_letor_ranksvmnc.m : Boucle de tests des différents régularization sur le jeux de données Letor
    • letor_FSMRank.m : Comparaison avec optimisation l1 rapide.
    • ncsvmclassNob.m : Solveur pour SVMRank non-convexe.