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