Learning layered ranking functions with structured support vector machines

The relationship between bipartite ranking algorithms, graph theory and ROC analysis has been formerly established with data sampled from two categories (i.e. classes). In this article, we discuss extensions for more general ranking models, with data sampled from, in general, r ordered categories. Similarly, such models can be visualized by means of a layered ranking graph in which each path in the graph corresponds to an r-tuple of correctly ranked objects with one object of each class. From an ROC analysis point of view, the fraction of correctly ranked r-tuples equals the volume under the ROC surface (VUS) for r ordered categories. Unlike the conventional kernel approach of minimizing the pairwise error, we try to optimize the fraction of correctly ranked r-tuples. A large number of constraints appear in the resulting quadratic program, but the optimal solution can be computed in O(n(3)) tune for samples of size n with structured support vector machines and graph-based techniques. Our approach can offer benefits for applications in various domains. On various synthetic and benchmark data sets, it outperforms the pairwise approach for balanced as well as unbalanced problems. In addition, scaling experiments confirm the theoretically derived time complexity. (C) 2008 Elsevier Ltd. All rights reserved