Timezone: »

 
Poster
$H$-Consistency Bounds for Pairwise Misranking Loss Surrogates
Anqi Mao · Mehryar Mohri · Yutao Zhong

Wed Jul 26 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #330
in Poster Session 4 »
We present a detailed study of *$H$-consistency bounds* for score-based ranking. These are upper bounds on the target loss estimation error of a predictor in a hypothesis set $H$, expressed in terms of the surrogate loss estimation error of that predictor. We will show that both in the *general pairwise ranking* scenario and in the *bipartite ranking* scenario, there are no meaningful $H$-consistency bounds for most hypothesis sets used in practice including the family of linear models and that of the neural networks, which satisfy the equicontinuous property with respect to the input. To come up with ranking surrogate losses with theoretical guarantees, we show that a natural solution consists of resorting to a *pairwise abstention loss* in the general pairwise ranking scenario, and similarly, a *bipartite abstention loss* in the bipartite ranking scenario, to abstain from making predictions at some limited cost $c$. For surrogate losses of these abstention loss functions, we give a series of $H$-consistency bounds for both the family of linear functions and that of neural networks with one hidden-layer. Our experimental results illustrate the effectiveness of ranking with abstention.
[ PDF] 

Author Information

Anqi Mao (Courant Institute of Mathematical Sciences, NYU)
Mehryar Mohri (Google Research and Courant Institute of Mathematical Sciences)
Yutao Zhong (Courant Institute of Mathematical Sciences, NYU)

More from the Same Authors