The risk of trivial solutions in bipartite top ranking

Aditya Krishna Menon

doi:10.1007/s10994-018-5759-4

The risk of trivial solutions in bipartite top ranking

Aditya Krishna Menon^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Given a sample of instances with binary labels, the bipartite top ranking problem is to produce a ranked list of instances whose head is dominated by positives. One popular existing approach to this problem is based on constructing surrogates to a performance measure known as the fraction of positives of the top (PTop). In this paper, we theoretically show that the measure and its surrogates have an undesirable property: for certain noisy distributions, it is optimal to trivially predict the same score for all instances. We propose a simple rectification which avoids such trivial solutions, while still focussing on the head of the ranked list and being as easy to optimise.

Original language	English
Pages (from-to)	627-658
Number of pages	32
Journal	Machine Learning
Volume	108
Issue number	4
DOIs	https://doi.org/10.1007/s10994-018-5759-4
Publication status	Published - 15 Apr 2019

Access to Document

10.1007/s10994-018-5759-4

Cite this

@article{8cf59b3503494f8f8045932dc4d63ba2,

title = "The risk of trivial solutions in bipartite top ranking",

abstract = "Given a sample of instances with binary labels, the bipartite top ranking problem is to produce a ranked list of instances whose head is dominated by positives. One popular existing approach to this problem is based on constructing surrogates to a performance measure known as the fraction of positives of the top (PTop). In this paper, we theoretically show that the measure and its surrogates have an undesirable property: for certain noisy distributions, it is optimal to trivially predict the same score for all instances. We propose a simple rectification which avoids such trivial solutions, while still focussing on the head of the ranked list and being as easy to optimise.",

keywords = "Bipartite ranking, Positives at the top, Top rank optimisation",

author = "Menon, \{Aditya Krishna\}",

note = "Publisher Copyright: {\textcopyright} 2018, The Author(s).",

year = "2019",

month = apr,

day = "15",

doi = "10.1007/s10994-018-5759-4",

language = "English",

volume = "108",

pages = "627--658",

journal = "Machine Learning",

issn = "0885-6125",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - The risk of trivial solutions in bipartite top ranking

AU - Menon, Aditya Krishna

PY - 2019/4/15

Y1 - 2019/4/15

N2 - Given a sample of instances with binary labels, the bipartite top ranking problem is to produce a ranked list of instances whose head is dominated by positives. One popular existing approach to this problem is based on constructing surrogates to a performance measure known as the fraction of positives of the top (PTop). In this paper, we theoretically show that the measure and its surrogates have an undesirable property: for certain noisy distributions, it is optimal to trivially predict the same score for all instances. We propose a simple rectification which avoids such trivial solutions, while still focussing on the head of the ranked list and being as easy to optimise.

AB - Given a sample of instances with binary labels, the bipartite top ranking problem is to produce a ranked list of instances whose head is dominated by positives. One popular existing approach to this problem is based on constructing surrogates to a performance measure known as the fraction of positives of the top (PTop). In this paper, we theoretically show that the measure and its surrogates have an undesirable property: for certain noisy distributions, it is optimal to trivially predict the same score for all instances. We propose a simple rectification which avoids such trivial solutions, while still focussing on the head of the ranked list and being as easy to optimise.

KW - Bipartite ranking

KW - Positives at the top

KW - Top rank optimisation

UR - https://www.scopus.com/pages/publications/85053236197

U2 - 10.1007/s10994-018-5759-4

DO - 10.1007/s10994-018-5759-4

M3 - Article

SN - 0885-6125

VL - 108

SP - 627

EP - 658

JO - Machine Learning

JF - Machine Learning

IS - 4

ER -

The risk of trivial solutions in bipartite top ranking

Abstract

Access to Document

Other files and links

Fingerprint

Cite this