D. Cossock, and T. Zhang. Learning Theory, volume 4005 of Lecture Notes in Computer Science, Springer, Berlin / Heidelberg, (2006)
DOI: 10.1007/11776420_44
Abstract
We study the subset ranking problem, motivated by its important application in web-search. In this context, we consider the standard DCG criterion (discounted cumulated gain) that measures the quality of items near the top of the rank-list. Similar to error minimization for binary classification, the DCG criterion leads to a non-convex optimization problem that can be NP-hard. Therefore a computationally more tractable approach is needed. We present bounds that relate the approximate optimization of DCG to the approximate minimization of certain regression errors. These bounds justify the use of convex learning formulations for solving the subset ranking problem. The resulting estimation methods are not conventional, in that we focus on the estimation quality in the top-portion of the rank-list. We further investigate the generalization ability of these formulations. Under appropriate conditions, the consistency of the estimation schemes with respect to the DCG metric can be derived.
%0 Book Section
%1 cossock2006subset
%A Cossock, David
%A Zhang, Tong
%B Learning Theory
%C Berlin / Heidelberg
%D 2006
%E Lugosi, Gábor
%E Simon, Hans
%I Springer
%K learning-to-rank pointwise regression
%P 605-619
%R 10.1007/11776420_44
%T Subset Ranking Using Regression
%U http://dx.doi.org/10.1007/11776420_44
%V 4005
%X We study the subset ranking problem, motivated by its important application in web-search. In this context, we consider the standard DCG criterion (discounted cumulated gain) that measures the quality of items near the top of the rank-list. Similar to error minimization for binary classification, the DCG criterion leads to a non-convex optimization problem that can be NP-hard. Therefore a computationally more tractable approach is needed. We present bounds that relate the approximate optimization of DCG to the approximate minimization of certain regression errors. These bounds justify the use of convex learning formulations for solving the subset ranking problem. The resulting estimation methods are not conventional, in that we focus on the estimation quality in the top-portion of the rank-list. We further investigate the generalization ability of these formulations. Under appropriate conditions, the consistency of the estimation schemes with respect to the DCG metric can be derived.
%@ 978-3-540-35294-5
@incollection{cossock2006subset,
abstract = {We study the subset ranking problem, motivated by its important application in web-search. In this context, we consider the standard DCG criterion (discounted cumulated gain) that measures the quality of items near the top of the rank-list. Similar to error minimization for binary classification, the DCG criterion leads to a non-convex optimization problem that can be NP-hard. Therefore a computationally more tractable approach is needed. We present bounds that relate the approximate optimization of DCG to the approximate minimization of certain regression errors. These bounds justify the use of convex learning formulations for solving the subset ranking problem. The resulting estimation methods are not conventional, in that we focus on the estimation quality in the top-portion of the rank-list. We further investigate the generalization ability of these formulations. Under appropriate conditions, the consistency of the estimation schemes with respect to the DCG metric can be derived.},
added-at = {2011-10-17T15:07:44.000+0200},
address = {Berlin / Heidelberg},
affiliation = {Yahoo Inc., Santa Clara, CA USA},
author = {Cossock, David and Zhang, Tong},
biburl = {https://www.bibsonomy.org/bibtex/285b7a8b59ccdd94a8892eaf10081ab87/beate},
booktitle = {Learning Theory},
description = {SpringerLink - Export Citation},
doi = {10.1007/11776420_44},
editor = {Lugosi, Gábor and Simon, Hans},
interhash = {66a5bf9682800ff9f69aaa1ac94e6488},
intrahash = {85b7a8b59ccdd94a8892eaf10081ab87},
isbn = {978-3-540-35294-5},
keyword = {Computer Science},
keywords = {learning-to-rank pointwise regression},
pages = {605-619},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
timestamp = {2011-10-17T15:07:44.000+0200},
title = {Subset Ranking Using Regression},
url = {http://dx.doi.org/10.1007/11776420_44},
volume = 4005,
year = 2006
}