Binary Classification with Karmic, Threshold-Quasi-Concave Metrics
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationClassificationGeneral ClassificationSimilar Papers 제목 키워드 기반
Online Classification with Complex Metrics
We present a framework and analysis of consistent binary classification for complex and non-decomposable performance metrics such as the F-measure and the Jaccard measure. The proposed framework is general, as it applies…
Binary ClassificationClassificationGeneral ClassificationPrivate Learning and Sanitization: Pure vs. Approximate Differential Privacy
We compare the sample complexity of private learning [Kasiviswanathan et al. 2008] and sanitization~[Blum et al. 2008] under pure $\epsilon$-differential privacy [Dwork et al. TCC 2006] and approximate $(\epsilon,\delta)…
Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of $O(\xi^{-1} \log(1/\beta))$ (for generalization error $\xi$ with confidence $1-…
Learning TheoryBottleneck detection by slope difference distribution: a robust approach for separating overlapped cells
To separate the overlapped cells, a bottleneck detection approach is proposed in this paper. The cell image is segmented by slope difference distribution (SDD) threshold selection. For each segmented binary clump, its on…
validPreference Elicitation and Robust Optimization with Multi-Attribute Quasi-Concave Choice Functions
Decision maker's preferences are often captured by some choice functions which are used to rank prospects. In this paper, we consider ambiguity in choice functions over a multi-attribute prospect space. Our main result i…
Attribute