On threshold-based classification rules

Abstract. Suppose we have n i.i.d. copies {(Xi, Yi), i = 1,..., n} of an example (X,Y), where X ∈ X is an instance and Y ∈ {−1, 1} is a label. A decision function (or classifier) f is a function f: X → [−1, 1]. Based on f, the example (X,Y) is misclassified if Y f(X) ≤ 0. In this paper, we first study the case X = R, and the simple decision functions ha(x) = 2l{x ≥ a} − 1 based on a threshold a ∈ R. We choose the threshold ân that minimizes the classification error in the sample, and derive its asymptotic distribution. We also show that, under monotonicity assumptions, ân is a nonparametric maximum likelihood estimator. Next, we consider more complicated classification rules based on averaging over a class of base classifiers. We allow that certain examples are not classified due to lack of evidence, and provide a uniform bound for the margin. Moreover, we illustrate that when using averaged classification rules, maximizing the number of examples with margin above a given value, can overcome the problem of overfitting. In our illustration, the classification problem then boils down to optimizing over certain threshold-based classifiers