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, rr 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 rr-tuple of correctly ranked objects with one object of each class. From an ROC analysis point of view, the fraction of correctly ranked rr-tuples equals the volume under the ROC surface (VUS) for rr ordered categories. Unlike the conventional kernel approach of minimizing the pairwise error, we try to optimize the fraction of correctly ranked rr-tuples. A large number of constraints appear in the resulting quadratic program, but the optimal solution can be computed in O(n3)O(n3) time for samples of size nn 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.