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