Binary classification with karmic, threshold-quasi-concave metrics

Bowei Yan, Oluwasanmi Oluseye Koyejo, Kai Zhong, Pradeep Ravikumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Complex performance measures, beyond the popular measure of accuracy, are increasingly being used in the context of binary classification. These complex performance measures are typically not even decomposable, that is, the loss evaluated on a batch of samples cannot typically be expressed as a sum or average of losses evaluated at individual samples, which in turn requires new theoretical and methodological developments beyond standard treatments of supervised learning. In this paper, we advance this understanding of binary classification for complex performance measures by identifying two key properties: a so-called Karmic property, and a more technical threshold-quasiconcavity property, which we show is milder than existing structural assumptions imposed on performance measures. Under these properties, we show that the Bayes optimal classifier is a threshold function of the conditional probability of positive class. We then leverage this result to come up with a computationally practical plug-in classifier, via a novel threshold estimator, and further, provide a novel statistical analysis of classification error with respect to complex performance measures.

Original languageEnglish (US)
Title of host publication35th International Conference on Machine Learning, ICML 2018
EditorsJennifer Dy, Andreas Krause
PublisherInternational Machine Learning Society (IMLS)
Pages8792-8804
Number of pages13
ISBN (Electronic)9781510867963
StatePublished - Jan 1 2018
Event35th International Conference on Machine Learning, ICML 2018 - Stockholm, Sweden
Duration: Jul 10 2018Jul 15 2018

Publication series

Name35th International Conference on Machine Learning, ICML 2018
Volume12

Other

Other35th International Conference on Machine Learning, ICML 2018
CountrySweden
CityStockholm
Period7/10/187/15/18

Fingerprint

Classifiers
Supervised learning
Statistical methods

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Human-Computer Interaction
  • Software

Cite this

Yan, B., Koyejo, O. O., Zhong, K., & Ravikumar, P. (2018). Binary classification with karmic, threshold-quasi-concave metrics. In J. Dy, & A. Krause (Eds.), 35th International Conference on Machine Learning, ICML 2018 (pp. 8792-8804). (35th International Conference on Machine Learning, ICML 2018; Vol. 12). International Machine Learning Society (IMLS).

Binary classification with karmic, threshold-quasi-concave metrics. / Yan, Bowei; Koyejo, Oluwasanmi Oluseye; Zhong, Kai; Ravikumar, Pradeep.

35th International Conference on Machine Learning, ICML 2018. ed. / Jennifer Dy; Andreas Krause. International Machine Learning Society (IMLS), 2018. p. 8792-8804 (35th International Conference on Machine Learning, ICML 2018; Vol. 12).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Yan, B, Koyejo, OO, Zhong, K & Ravikumar, P 2018, Binary classification with karmic, threshold-quasi-concave metrics. in J Dy & A Krause (eds), 35th International Conference on Machine Learning, ICML 2018. 35th International Conference on Machine Learning, ICML 2018, vol. 12, International Machine Learning Society (IMLS), pp. 8792-8804, 35th International Conference on Machine Learning, ICML 2018, Stockholm, Sweden, 7/10/18.
Yan B, Koyejo OO, Zhong K, Ravikumar P. Binary classification with karmic, threshold-quasi-concave metrics. In Dy J, Krause A, editors, 35th International Conference on Machine Learning, ICML 2018. International Machine Learning Society (IMLS). 2018. p. 8792-8804. (35th International Conference on Machine Learning, ICML 2018).
Yan, Bowei ; Koyejo, Oluwasanmi Oluseye ; Zhong, Kai ; Ravikumar, Pradeep. / Binary classification with karmic, threshold-quasi-concave metrics. 35th International Conference on Machine Learning, ICML 2018. editor / Jennifer Dy ; Andreas Krause. International Machine Learning Society (IMLS), 2018. pp. 8792-8804 (35th International Conference on Machine Learning, ICML 2018).
@inproceedings{079dbe765f4a439e82225a4eccf86740,
title = "Binary classification with karmic, threshold-quasi-concave metrics",
abstract = "Complex performance measures, beyond the popular measure of accuracy, are increasingly being used in the context of binary classification. These complex performance measures are typically not even decomposable, that is, the loss evaluated on a batch of samples cannot typically be expressed as a sum or average of losses evaluated at individual samples, which in turn requires new theoretical and methodological developments beyond standard treatments of supervised learning. In this paper, we advance this understanding of binary classification for complex performance measures by identifying two key properties: a so-called Karmic property, and a more technical threshold-quasiconcavity property, which we show is milder than existing structural assumptions imposed on performance measures. Under these properties, we show that the Bayes optimal classifier is a threshold function of the conditional probability of positive class. We then leverage this result to come up with a computationally practical plug-in classifier, via a novel threshold estimator, and further, provide a novel statistical analysis of classification error with respect to complex performance measures.",
author = "Bowei Yan and Koyejo, {Oluwasanmi Oluseye} and Kai Zhong and Pradeep Ravikumar",
year = "2018",
month = "1",
day = "1",
language = "English (US)",
series = "35th International Conference on Machine Learning, ICML 2018",
publisher = "International Machine Learning Society (IMLS)",
pages = "8792--8804",
editor = "Jennifer Dy and Andreas Krause",
booktitle = "35th International Conference on Machine Learning, ICML 2018",

}

TY - GEN

T1 - Binary classification with karmic, threshold-quasi-concave metrics

AU - Yan, Bowei

AU - Koyejo, Oluwasanmi Oluseye

AU - Zhong, Kai

AU - Ravikumar, Pradeep

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Complex performance measures, beyond the popular measure of accuracy, are increasingly being used in the context of binary classification. These complex performance measures are typically not even decomposable, that is, the loss evaluated on a batch of samples cannot typically be expressed as a sum or average of losses evaluated at individual samples, which in turn requires new theoretical and methodological developments beyond standard treatments of supervised learning. In this paper, we advance this understanding of binary classification for complex performance measures by identifying two key properties: a so-called Karmic property, and a more technical threshold-quasiconcavity property, which we show is milder than existing structural assumptions imposed on performance measures. Under these properties, we show that the Bayes optimal classifier is a threshold function of the conditional probability of positive class. We then leverage this result to come up with a computationally practical plug-in classifier, via a novel threshold estimator, and further, provide a novel statistical analysis of classification error with respect to complex performance measures.

AB - Complex performance measures, beyond the popular measure of accuracy, are increasingly being used in the context of binary classification. These complex performance measures are typically not even decomposable, that is, the loss evaluated on a batch of samples cannot typically be expressed as a sum or average of losses evaluated at individual samples, which in turn requires new theoretical and methodological developments beyond standard treatments of supervised learning. In this paper, we advance this understanding of binary classification for complex performance measures by identifying two key properties: a so-called Karmic property, and a more technical threshold-quasiconcavity property, which we show is milder than existing structural assumptions imposed on performance measures. Under these properties, we show that the Bayes optimal classifier is a threshold function of the conditional probability of positive class. We then leverage this result to come up with a computationally practical plug-in classifier, via a novel threshold estimator, and further, provide a novel statistical analysis of classification error with respect to complex performance measures.

UR - http://www.scopus.com/inward/record.url?scp=85057309063&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057309063&partnerID=8YFLogxK

M3 - Conference contribution

T3 - 35th International Conference on Machine Learning, ICML 2018

SP - 8792

EP - 8804

BT - 35th International Conference on Machine Learning, ICML 2018

A2 - Dy, Jennifer

A2 - Krause, Andreas

PB - International Machine Learning Society (IMLS)

ER -