The accuracy of information retrieval systems is often measured using complex non-decomposable loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG). Given a set of positive (relevant) and negative (non-relevant) samples, the parameters of a retrieval system can be estimated using a rank SVM framework, which minimizes a regularized convex upper bound on the empirical loss. However, the high computational complexity of loss-augmented inference, which is required to learn a rank SVM, prohibits its use in large training datasets. To alleviate this defficiency, we present a novel quicksort avored algorithm for a large class of nondecomposable loss functions. We provide a complete characterization of the loss functions that are amenable to our algorithm. Furthermore, we prove that no comparison based algorithm can improve upon the computational complexity of our approach asymptotically. We demonstrate that it is possible to reduce the constant factors of the complexity by exploiting the special structure of the AP loss. Using the PASCAL VOC action recognition and object detection datasets, we show that our approach provides significantly better results than baseline methods that use a simpler decomposable loss in comparable runtime.

提出了一种新的 quicksort-flavored 算法，可以在大量训练数据集上优化非可分离损失函数。已证明，该方法适用于包括 AP 和 NDCG 基础上的损失函数，并且对于我们的方法渐近计算复杂度不能提高。我们展示了该方法在优化结构化铰链损失上的效果并且得到了比简单的可分离损失函数更好的结果，同时需要相当的训练时间。

基于排名的损失函数的高效优化