On the Consistency of Ranking Algorithms
John Duchi, Lester Mackey and Michael Jordan
EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2010-56
May 9, 2010
http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-56.pdf
We present a theoretical analysis of supervised ranking, providing necessary and sufficient conditions for the asymptotic consistency of algorithms based on minimizing a surrogate loss function. We show that many commonly used surrogate losses are inconsistent; surprisingly, we show inconsistency even in low-noise settings. We present a new value-regularized linear loss, establish its consistency under reasonable assumptions on noise, and show that it outperforms conventional ranking losses in a collaborative filtering experiment.
BibTeX citation:
@techreport{Duchi:EECS-2010-56,
Author = {Duchi, John and Mackey, Lester and Jordan, Michael},
Title = {On the Consistency of Ranking Algorithms},
Institution = {EECS Department, University of California, Berkeley},
Year = {2010},
Month = {May},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-56.html},
Number = {UCB/EECS-2010-56},
Abstract = {We present a theoretical analysis of supervised ranking, providing necessary and sufficient conditions for the asymptotic consistency of algorithms based on minimizing a surrogate loss function. We show that many commonly used surrogate losses are inconsistent; surprisingly, we show inconsistency even in low-noise settings. We present a new value-regularized linear loss, establish its consistency under reasonable assumptions on noise, and show that it outperforms conventional ranking losses in a collaborative filtering experiment.}
}
EndNote citation:
%0 Report %A Duchi, John %A Mackey, Lester %A Jordan, Michael %T On the Consistency of Ranking Algorithms %I EECS Department, University of California, Berkeley %D 2010 %8 May 9 %@ UCB/EECS-2010-56 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-56.html %F Duchi:EECS-2010-56