Approximation of the optimal ROC curve and a tree-based ranking algorithm

We consider the extension of standard decision tree methods to the bipartite ranking problem. In ranking, the goal pursued is global: define an order on the whole input space in order to have positive instances on top with maximum probability. The most natural way of ordering all instances consists in projecting the input data x onto the real line using a real-valued scoring function s and the accuracy of the ordering induced by a candidate s is classically measured in terms of the AUC. In the paper, we discuss the design of tree-structured scoring functions obtained by maximizing the AUC criterion. In particular, the connection with recursive piecewise linear approximation of the optimal ROC curve both in the L ₁-sense and in the L _∈∞∈-sense is discussed.