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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...