Abstract

Direct optimization of ranking measures has become an important branch of learning to rank. Since ranking measures, such as NDCG and MAP, are difficult to optimize due to their discontinuity and indifferentiability, most direct optimization methods optimize a surrogate objective function instead. A critical issue then arises as to whether this alternative approach can really lead to the optimization of the original ranking measures. This paper is concerned with the formal analysis on this issue. Specifically, we propose the concept of "directness" to quantify the relationship between a surrogate objective function and the ranking measure. We show that the optimization of a surrogate objective function whose directness is large will lead to the effective optimization of the ranking measure. Then we analyze the directness of the surrogate objective functions in existing methods. Our theoretical results show that the directness of the surrogate objective functions in methods like SoftRank can be as large as possible, regardless of the data distribution, when some parameters are appropriately set. However, the directness of the surrogate objective functions in methods like SVM-NDCG cannot be arbitrarily large on certain distributions of data. As a result, the performance of SoftRank in terms of the ranking measures is theoretically guaranteed if one can effectively optimize its surrogate objective function, but there is no guarantee on the performance of SVM-NDCG. These theoretical findings have been verified by our experimental results on both synthetic and real datasets.

Paper Details