Binary Classification with Karmic, Threshold-Quasi-Concave Metrics

Bowei Yan, Sanmi Koyejo, Kai Zhong, Pradeep Ravikumar
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:5531-5540, 2018.

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-quasi-concavity 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v80-yan18b, title = {Binary Classification with Karmic, Threshold-Quasi-Concave Metrics}, author = {Yan, Bowei and Koyejo, Sanmi and Zhong, Kai and Ravikumar, Pradeep}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {5531--5540}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/yan18b/yan18b.pdf}, url = {https://proceedings.mlr.press/v80/yan18b.html}, 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-quasi-concavity 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.} }
Endnote
%0 Conference Paper %T Binary Classification with Karmic, Threshold-Quasi-Concave Metrics %A Bowei Yan %A Sanmi Koyejo %A Kai Zhong %A Pradeep Ravikumar %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-yan18b %I PMLR %P 5531--5540 %U https://proceedings.mlr.press/v80/yan18b.html %V 80 %X 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-quasi-concavity 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.
APA
Yan, B., Koyejo, S., Zhong, K. & Ravikumar, P.. (2018). Binary Classification with Karmic, Threshold-Quasi-Concave Metrics. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:5531-5540 Available from https://proceedings.mlr.press/v80/yan18b.html.

Related Material