Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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.
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00416054
Contributor : Stephan Clémençon Connect in order to contact the contributor
Submitted on : Friday, September 11, 2009 - 5:09:20 PM
Last modification on : Thursday, April 15, 2021 - 3:31:56 AM
Long-term archiving on: : Tuesday, October 16, 2012 - 10:51:12 AM

File

Opt_Pruning_Ranking_5.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00416054, version 1

Citation

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, Springer Verlag, 2010, 83 (1), pp.31-69. ⟨hal-00416054⟩

Share

Metrics

Record views

322

Files downloads

82