Adaptive partitioning schemes for bipartite ranking How to grow and prune a ranking tree - IMT - Institut Mines-Télécom Accéder directement au contenu
Article Dans Une Revue Machine Learning Année : 2010

Adaptive partitioning schemes for bipartite ranking How to grow and prune a ranking tree

Résumé

Recursive partitioning methods are among the most popular techniques in machine learning. It is the purpose of this paper to investigate how such an appealing methodology may be adapted to the bipartite ranking problem, in order to elaborate a global learning method. Following in the footsteps of the TreeRank approach developed in [1], we present tree-structured algorithms designed for learning to rank/order instances based on classification data. Crucial questions concerning practical implementation of the TreeRank algorithm, those related to the splitting rule and the choice of the ”right” size for the ranking tree namely, are tackled. From the angle embraced in this paper, splitting is viewed as a cost-sensitive classification task with data-dependent cost, so that, up to straightforward modifications, any classification algorithm may serve as a splitting rule. As for classification, we propose to implement a cost-complexity pruning method after the growing stage, in order to produce a ”right-sized” sub- ranking tree with large AUC. In particular, performance bounds are established for pruning schemes inspired by recent work on nonparametric model selection. It is also discussed how to interpret a ranking tree and various simulation studies are eventually presented for illustration purpose.
Fichier principal
Vignette du fichier
Opt_Pruning_Ranking_5.pdf (1.3 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00416054 , version 1 (11-09-2009)

Identifiants

Citer

Stéphan Clémençon, Marine Depecker, Nicolas Vayatis. Adaptive partitioning schemes for bipartite ranking How to grow and prune a ranking tree. Machine Learning, 2010, 83 (1), pp.31-69. ⟨10.1007/s10994-010-5190-y⟩. ⟨hal-00416054⟩
327 Consultations
95 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More