{'fraction_non_alphanumeric': 0.040300099803833846, 'fraction_numerical': 0.011907629831021786, 'mean_word_length': 4.17506678539626, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Consistency and Finite Sample Behavior of Binary Class Probability Estimation

In this work we investigate to which extent one can recover class probabilities within the empirical risk minimization (ERM) paradigm. The main aim of our paper is to extend existing results and emphasize the tight relations between empirical risk minimization and class probability estimation. Based on existing literature on excess risk bounds and proper scoring rules, we derive a class probability estimator based on empirical risk minimization. We then derive fairly general conditions under which this estimator will converge, in the L1-norm and in probability, to the true class probabilities. Our main contribution is to present a way to derive finite sample L1-convergence rates of this estimator for different surrogate loss functions. We also study in detail which commonly used loss functions are suitable for this estimation problem and finally discuss the setting of model-misspecification as well as a possible extension to asymmetric loss functions.


Introduction
In binary classification problems we try to predict a label y ∈ {−1, 1} = Y based on an input feature vector x ∈ X . Since optimizing for the classification accuracy is often computationally too complex, one typically measures performance through a surrogate loss function. Such methods are designed to achieve good classification performance, but often we are also interested in the classifier's confidence or a class probability estimate as such. We may, for instance, not only want to classify a tumor as benign or malignant, but also know an estimated probability that the predicted label is wrong. Also various methods in active or semi-supervised learning rely on such class probability estimates. In active learning they are, for instance, used in uncertainty based rules Lewis and Catlett (1994); Roy and McCallum (2001) while in semi-supervised learning they can be used for performing entropy regularization Grandvalet and Bengio (2005).
In this paper we derive necessary and sufficient conditions under which classifiers, obtained through the minimization of an empirical loss function, allow us to estimate the class probability in a consistent way. More precisely, we present a general way to derive finite sample bounds based on those conditions. While the use of class probability estimates, as argued before, finds a broad audience, the necessary tools to understand the behavior, especially the literature on proper scoring rules, is not that broadly known. So next to our contribution on finite sample behavior for class probability estimation we present a condensed introduction to this, in our opinion, underappreciated field.
A proper scoring rule is essentially a loss function that can measure the class probability point-wise. We investigate in which circumstances those loss functions make use of this potential and lift this point-wise property to the complete space. Next to proper scoring rules we use excess risk bounds to come to our results. Excess risk bounds are essentially inequalities that quantify how much an empirical risk minimizer is off from the true risk.
Combining those two areas, our main contributions are the following. Based on the existing literature, we define in Section 4, Equation (8), a probability estimateη derived from an empirical risk minimizer. Based on this we analyze in Section 5 to which extent commonly used loss functions are suitable for the task of class probability estimation. Following this and the analysis thereafter, we argue in Section 6.5 that the squared loss is, in view of this paper, not arXiv:1908.11823v1 [cs.LG] 30 Aug 2019 a particular good choice. In Section 6 we derive conditions that ensure that the estimatorη converges in probability towards the true posterior. In the same section we present a general way to analyze the finite sample behavior of the convergence rate for different loss functions. The idea is to bound the L 1 -distance between the estimated and the true class probability by the excess risk and then use bounds on the excess risk together with the properties of proper scoring rules to show convergence. In the same section we discuss the behavior of the estimator when it is misspecified. In this case one can in general not recover the true class probabilities, but instead find the best approximation with respect to a Bregman divergence. In Section 7 we conclude and discuss our analysis. In particular we discuss how one can extend this work to asymmetric loss functions and analyze their convergence behavior per class label. The following two sections start with related work and some preliminaries.

Related Work
The starting point of our analysis follows closely the notation and concepts as described by Buja et al. (2005) and Williamson (2010, 2011). While Buja et al. (2005) and Reid and Williamson (2010) deal with the inherent structure of proper scoring rules, Reid and Williamson (2011) make connections between the expected loss in prediction problems and divergence measures of two distributions. In contrast to that we investigate under which circumstances proper scoring rules can make use of their full potential in order to estimate class probabilities. Telgarsky et al. (2015) perform an analysis similar to ours as they also investigate convergence properties of a class probability estimator, their start and end point are very different though. While we start with theory from proper scoring rules, their paper directly starts with the class probability estimator as found in Zhang (2004). The problem is that the estimator in Zhang (2004) only appears as a side remark, and it is unclear to which extent this is the best, only or even the correct choice. This paper contributes to close this gap and answers those questions. They show that the estimator converges to a unique class probability model. In relation to this one can view this paper as an investigation of this unique class probability model and we give necessary and sufficient conditions that lead to convergence to the true class probabilities. Note also that their paper uses convex methods, while our work in comparison draws from the theory of proper scoring rules. Agarwal and Agarwal (2015) look at the problem in a more general fashion. They connect different surrogate loss functions to certain statistics of the class probability distribution, e.g. the mean, while we focus on the estimation of the full class probability distribution. This allows us to come to more specific results, such as finite sample behavior.
The probability estimator we use also appears in Agarwal (2014) where it is used to derive excess risk bounds, referred to as surrogate risk bounds, for bipartite ranking. The methods used are very similar in the sense that these are also based on proper scoring rules. The difference is again the focus, and even more so the conditions used. They introduce the notion of strongly proper scoring rules which directly allows one to bound the L 2 -norm, and thus the L 1 -norm, of the estimator in terms of the excess risk. We show that convergence can be achieved already under milder conditions. We then use the concept of modulus of continuity, of which strongly proper scoring rules are a particular case, to analyze the rate of convergence.

Preliminaries
We work in the classical statistical learning setup for binary classification. We assume that we observe a finite i.i.d. sample (x i , y i ) 1≤i≤n drawn from a distribution P on X × Y. Here X denotes a feature space and Y = {−1, 1} denotes a binary response variable. We then decide upon a hypothesis class F such that every f ∈ F is a map f : X → V for some space V. Given the space V we call any function l : {−1, 1} × V → [0, ∞) a loss function. The interpretation of the loss function is that we incur the penalty l(y, v) when we predicted a value v while we actually observed the label y. Our goal is then to find a predictor f n ∈ F based on the finite sample such that E[l(Y, f n (X)] is small, where X × Y is a random variable distributed according to P . In other words, we want to find an estimator f n that approximates the true risk minimizer f 0 well in terms of the expected loss, where (1) The estimator f n is often chosen to be the empirical risk minimizer As we show in this paper, finding such an f n implicitly means to find a good estimate for p(y | x) := P (Y = y | X = x) in many settings. Since we regularly deal with p(y | x) and related quantities we introduce the following notation.
To start with, we define η(x) := P (Y = 1 | X = x). Depending on the context we drop the feature x and think of η ∈ [0, 1] as a scalar. Accepting the small risk of overloading the notation we sometimes also think of η as a Bernoulli distribution with outcomes in Y and parameter η, as in the following definition. We define the point-wise conditional risk as the optimal point-wise conditional risk as and we denote by v * (η) the set of values that optimize the point-wise conditional risk v * (η) := arg min v∈V L(η, v).
Finally we define the conditional excess risk as

Proper Scoring Rules
If we chose V = [0, 1], we say that l : {−1, 1} × V → R is a CPE loss, where CPE stands for class probability estimation. The name stems from the fact that if V = [0, 1] it is already normalized to a value that can be interpreted as a probability. If l is a CPE loss we call it a proper scoring rule or proper loss if η ∈ v * (η) and we call it a strictly proper scoring rule or strictly proper loss if v * (η) = {η}. In other words, l is a proper scoring rule if η is a minimizer of L(η, ·) and this is strict if η is the only minimizer. In case l is strict we drop the set notation of v * , so that v * (η) = η.

Link Functions
As we will see later strictly proper CPE losses are well suited for class probability estimation. In general, however, we cannot expect that V = [0, 1], but we may still want to use the corresponding loss function for class probability estimation. To do that we will use the concept of link functions Buja et al. (2005); Reid and Williamson (2010). A link function is a map ψ : [0, 1] → V, so a function that indeed links the values from V to something that can be interpreted as a probability. Combining such a link function with a loss l : We call the combination of a loss and a link function (l, ψ) a (strictly) proper composite loss if l ψ is (strictly) proper as a CPE loss.
To distinguish between the losses l and l ψ we subscript the quantities (2)-(5) with a ψ if we talk about l ψ instead of l. For example we define L ψ (η, q) := L(η, ψ(q)) for q ∈ [0, 1] and in the same way we define v * ψ (η), L * ψ (η) and ∆L ψ (η, q). Note that if (l, ψ) is a strictly proper composite loss, we know that v * ψ (η) are single element sets, but the same does not need to hold for v * (η).

Degenerate Link Functions
To ask a composite loss (l, ψ) to be proper is not a strong requirement, one can check that choosing ψ as constant function already fulfills this. This is because a composite loss (l, ψ) is proper, iff the true posterior η is a minimizer of the conditional risk L ψ (η, ·), i.e. η ∈ v * ψ (η). If ψ is constant, then so is the conditional risk L ψ (η, ·) and then every value is a minimizer, so in particular η is a minimizer. We want to avoid this degenerate behavior for the task of probability estimation and will ask ψ to cover enough of V in the following sense. We call a composite loss (l, ψ) This does not directly exclude constant link functions for example, but consider the following. If ψ is constant and non-degenerate, then there is a single v = Im ψ such that v ∈ v * (η) for all η. Thus v would always minimize the loss, and we would, irrespectively of the input, always predict v. This is of course a property that no reasonable loss function should carry.

Behavior of Proper Composite Losses
For our convergence results we will need a loss function to be a strictly proper CPE loss. In this section we investigate how to characterize those loss functions.
We start by investigating proper CPE loss functions. Our first lemma states that the link functions that turns the loss l into a proper composite loss is already defined by the behavior of v * . Lemma 1. Let l : {−1, 1} × V → [0, ∞) be a loss function and ψ be a link function. The composite loss function (l, ψ) is then proper and non-degenerate if and only if ψ ∈ v * , meaning that ψ(η) ∈ v * (η) for all η ∈ [0, 1].
. This is the case if and only if L(η, ψ(η)) = min defined as the set of minimizers of L(η, ·). The non-degenerate follows directly by definition.
This lemma gives thus necessary and sufficient condition on our link ψ to lead to a proper loss function. The result is very similar to Corollary 12 and 14 found in Reid and Williamson (2010). Their corollaries state necessary and sufficient conditions on the link function, using the assumption that the loss has differentiable partial losses, which is an assumption we don't require.
In Section 6.2 we show that strictly proper losses, together with some additional assumptions, lead to consistent class probability estimates. So it is useful to know how to characterize those functions. The following lemma shows that a link function that turns a loss into strictly proper and non-degenerate CPE loss can be characterized again by the behavior of v * .
So if (l, ψ) is a strictly proper composite loss it will fulfill some sort of injectivity condition on the sets v * (η). With this we will be able to define an inverse ψ −1 on those sets, and this will be essentially our class probability estimator. With Lemma 2 we can connect every v ∈ V to a unique η v by the unique relation Note that we know from Lemma 2 that for strict properness it is sufficient for (l, ψ) that the disjoint property (7) only holds on Im ψ, the image of ψ. This is merely a technicality and we will assume from now on that every strictly proper composite loss will satisfy (7). The covering property (6)  If we assume, however, that the regularity properties (6) and (7) hold for a strictly proper non-degenerate composite loss (l, ψ) we can extend the domain of ψ −1 from Im ψ to the whole of V, see also Figure 1 and the examples in Table 2. Figure 1: The way we generally think of the mapping ψ, ψ −1 and the sets v * if (l, ψ) is non-degenerate and strictly proper. In those cases we can extend ψ −1 to the sets v * . This is well defined as the sets v * (η v ) and v * (η w ) have empty intersection for different η v , η w ∈ [0, 1]. Note that Lemma 2 guarantees that ψ(η v ) ∈ v * (η v ).
Definition 1. Let (l, ψ) be a strictly proper, non-degenerate composite loss and assume that v * disjointly covers V. We define, by abuse of notation, the inverse link function ψ −1 : The requirements from the previous definition is what we consider the archetype of a composite loss that is suitable for probability estimation, although not all of the requirements are necessary. This motivates the following definition.
Definition 2. We call a composite loss (l, ψ) a natural CPE loss if ψ is non-degenerate, v * fulfills the disjoint cover property (6) and (7) and (l, ψ) is strictly proper.
We now have all the necessary work done to make the following observation.
The corollary tells us that we can optimize our loss function over V to get v * (η) and then map this back with the inverse link ψ −1 to restore the class probability η. For this we once more refer to Figure 1. Remember that the set v * (η v ) is the set of all v ∈ V that minimize the loss if the true posterior probability was η v . If we use a natural CPE loss (l, ψ) we know then that ψ −1 maps all those points back to η v .
Given a predictor f : X → V this motivates to define an estimator of η(x) aŝ In Section 6 we give conditions under whichη(x) converges in probability towards η(x) when using an empirical risk minimizer f n as a prediction rule. More formally; Given any > 0 we show that under certain conditionŝ η n (x) := ψ −1 (f n (x)) satisfies where the probability is measured with respect to P . In the next section, however, we want to investigate first v * and v * −1 for some commonly used loss functions.

Analysis of Loss Functions
We now give examples of some commonly used loss functions and analyze whether they are strictly proper or not, with the aid of Lemma 2. In Table 1 we summarize the loss functions we consider and a link function that turns the loss function into a strictly proper composite loss, if possible. Table 2 shows the corresponding functions v * and v * −1 . That the link functions indeed fulfills the requirements can be checked with Lemma 2 . The behavior of the squared and squared hinge loss seems to be very similar. In Section 6.5, however, we point out an important difference. Loss Function l(y, v) ψ(η) As already noted by Buja et al. (2005), also Table 2 shows that the hinge loss is not suitable for class probability estimation. We observe that the intersections of v * (η) for different η ∈ [0, 1] are not disjoint. By Lemma 2 we can conclude that there is no link ψ such that (l, ψ) is strictly proper. One way to fix this, proposed by Duin and Tax (1998) and similar by Platt (1999), is to fit a logistic regressor on top of the support vector machine. Bartlett and Tewari (2004) investigate the behavior of the hinge loss deeper by connecting the class probability estimation task to the sparseness of the predictor. The hinge loss is of course classification calibrated (essentially meaning that we find point-wise the correct label with it), so between our considered surrogate losses it is the only one that really directly solves the classification problem without implicitly estimating the class probability.

Convergence of the Estimator
We now prove that the estimatorη(x) as defined in Equation (8) converges in probability and in the L 1 -norm to the true class probability η whenever we use an empirical risk minimizer, for which we have excess risk bounds, as a prediction rule.

Using the True Risk Minimizer for Estimation
Before we can investigate under which conditions an empirical risk minimizer can (asymptotically) retrieve η(x) we need to investigate under which conditions the true risk minimizer can retrieve it. In this subsection we formulate a theorem that gives necessary and sufficient conditions for that. Not surprisingly we basically require that our hypothesis class is rich enough so as to contain the class probability distribution already. Bartlett et al. (2006) and similar works often avoid problems caused by restricted classes by assuming from the beginning that the hypothesis class consists of all measurable functions. This theorem relaxes this assumption for the purpose of class probability estimation.
In this setting we assume that we use a hypothesis class F where f ∈ F are functions f : X → V. If we want to do class probability estimation we rescale those functions by composing them with the inverse link ψ For the other direction assume that η ∈ ψ −1 (F). First observe that Since (l, ψ) is a natural CPE loss we know that η(x) is the unique minimizer of L(η(x), ψ(·)). Since f 0 (X) is a minimizer of E X,Y [l(Y, ·)] = E[L(η(X), ·)] it follows that f 0 = ψ(η) almost surely. As (l, ψ) is regular, the inverse ψ −1 is well-defined and thus ψ −1 (f 0 ) = η.
Following Theorem 1 we need to assume that our hypothesis class is flexible enough for consistent class probability estimation. We formulate this assumption as follows.

Using the Empirical Risk Minimizer for Estimation
In the previous section we considered the possibility of retrieving class probability estimates with the true risk minimizer.
To move on to empirical risk minimizers we need the notion of excess risk bounds.
Definition 3. Let f n : X → R be any estimator of f 0 ∈ F. We call an excess risk bound for f n if B F (n) → 0 for n → ∞ and Excess risk bounds are typically in the order of comp(F ) n γ , where γ ∈ [0.5, 1] and comp(F) is a notion of model complexity. Common measures for the model complexity are the VC dimension Vapnik (1998), Rademacher complexity Bartlett et al. (2005) or -cover Benedek and Itai (1991). The existence of excess risk bounds is tied to the finiteness of any of those complexity notions. A lot of efforts in this line of research are made to find relations between the exponent γ and the statistical learning problem given by F, the loss l and the underlying distribution P . Conditions that ensure γ > 1 2 are often called easiness conditions, such as the Tsybakov condition Tsybakov (2004) or the Bernstein condition Audibert (2004). Intuitively those conditions often state that the variance of our estimator gets smaller the closer we are to the optimal solution. For a in-depth discussion and some recent results we refer to the work of Grünwald and Mehta (2016).
The map L 0 ψ (η, ·) captures the behavior of the loss when η is the true class probability and we predict a class probability less than η. Similarly L 1 ψ (η, ·) captures the behavior when we predict a class probability bigger than η, see also Figure  2. In Corollary 3, further below, we draw a connection between δ( ) and the modulus of continuity of the inverse functions of L 1 ψ (η, ·) and L 0 ψ (η, ·). The function δ( ) plays an important role in the convergence rate of the estimator η(x) as described in the next theorem. Theorem 2. Let (l, ψ) be a natural CPE loss and assume Assumption A holds. Furthermore let B F (n) be an excess risk bound for f n and assume that L ψ (η, ·) is strictly convex with η as its minimizer. Then there exists a mapping δ( ) : [0, 1] → R such that forη n (x) := ψ −1 (f n (x)) we have that Proof. Using Lemma 3 for the first inequality, Markov's Inequality for the second and the excess risk bound for the third inequality it follows that P (|η(X) −η n (X)| > ) ≤ P (∆L ψ (η(X),η n (X)) > δ)  This theorem gives us directly the earlier claimed asymptotic convergence result.
We do not have to restrict ourselves to asymptotic results though. Theorem 2 can also be used to derive rate of convergences as we will see in Subsection 6.4. But before that we briefly want to address the case of misspecification, i.e. the case when Assumption A does not hold.

Misspecification
The case of misspecification can be dealt with once we assume that L * ψ has a gradient. If this holds then Reid and Williamson (2010) show the identity ∆L ψ (η,η) = D −L * ψ (η,η) where D −L * ψ (η,η) is the with −L * ψ associated Bregman divergence between η andη. Excess risk bounds on ∆L ψ (η,η) translate then into bounds on the Bregman divergence between η andη and asymptotically we approach the best class probability estimate in terms of this divergence.

Rate of Convergence
For the rate of convergence it is crucial to investigate the function δ( ) from Inequality (14). One way to analyze this is to study the modulus of continuity of the inverse functions of L 0 ψ (η, ·) and L 1 ψ (η, ·): Definition 4. Let ω : [0, ∞] → [0, ∞] be a monotonically increasing function. Let I ⊂ R be an interval. A function g : I → R admits ω as a modulus of continuity at x ∈ I if and only if for all y ∈ I.
This is exactly the Implication (12).
Note that it follows from the proof that finding a modulus of continuity ω for L 0 ψ −1 (η, ·) and L 1 ψ −1 (η, ·) can be done by showing the bound |η − η| ≤ ω(∆L ψ (η,η)). We will use that in the following examples, where we analyze δ( ) for the squared (hinge) loss and the logistic loss. We show that those loss functions lead to a modulus of continuity given by the square root times a constant. Agarwal (2014) calls loss functions that admit this modulus of continuity strongly-proper loss functions. The following analysis can thus be found there in more detail and for a few more examples. We will use for simplicity versions of the losses that do not need a link function, and are already CPE losses, the results are summarized in Table 2.

Squared Loss vs Squared Hinge Loss
In this section we will subscript previously defined entities with S and SH for the squared and square hinge loss respectively. When using squared loss vs the squared hinge loss for class probability estimation there is one big difference in the inverse of the link function, namely its domain. The inverse link function is a map ψ −1 S : V → [0, 1]. If we use the square loss we implicitly chose V = [−1, 1] since this is the range of ψ S . The range of ψ SH on the other hand is V = R. That means that if we want to use the squared loss for class probability estimation we really have to parametrize our prediction functions f : X → [−1, 1], a simple linear model for example would usually not fit this assumption as the range of those models can be outside of [−1, 1]. For the squared hinge loss on the other hand we can allow for functions f : X → R. Sugiyama (2010) proposes to just truncate the inverse link for the squared loss, so using the same inverse link as for the squared hinge loss. This is fine as long as our hypothesis class is flexible enough, but leads to problems if that is not the case as the following example shows.
Assume we are given three one dimensional data points x 1 = −1, x 2 = 0, x 3 = 3 together with their true class probabilities η(x 1 ) = 0, η(x 2 ) = 1/3, η(x 3 ) = 1. We want to learn this classification with linear models, which are two-dimensional after including a bias term. That means that F = {f : X → R | ∃w 1 , w 2 ∈ R : f (x) = w 1 x + w 2 }. One can check that in case of the squared hinge loss function we can recover the true class probabilities with the linear function given by (w 1 , w 2 ) = (2, − 1 4 ). By Theorem 1 we know then that a optimal solution f 0 is also able to recover the true class probabilities.
The squared loss has after truncating the following problem. Although the linear function (w 1 , w 2 ) = (2, − 1 4 ) is part of ψ −1 S (F), after truncating, it will not be found back as an optimal solution f 0 . One can instead check that for the given example the true risk minimizer is given by f 0 = ( 19 39 , − 17 39 ). And this hypothesis does not recover the true class probabilities. This might appear as a contradiction to Theorem 1. But the problem arises because we use a different link function than the one associated to the square loss.

Discussion and Conclusion
The starting point of this paper is the question if one can retrieve consistently a class probability estimate based on ERM in a consistent way. To answer this question we draw from earlier work on proper scoring rules and excess risk bounds. Lemmas 1 and 2, our first results, characterize strictly proper composite loss functions in terms of their link function. Based on those lemmas, we subsequently derive necessary and sufficient conditions for retrieving the true class probability with ERM as formulated in Theorem 1. Next to some regularity conditions on the loss function, we show that to retrieve the true probabilities we essentially need that they are already part of our hypothesis class F, which, in a way, is not surprising.
In Section 6 we use the results from the previous sections and theory about excess risk bounds to state our main consistency and finite sample size results. We show that consistency arises whenever we use strictly proper (composite) loss functions, our hypothesis class is flexible enough, and we have excess risk bounds. This is the case, for example, whenever one of the complexity notions mentioned in Section 6 is finite. We then discuss the relation between the finite sample size behavior of the excess risk bound and the probability estimate and examine this relation for two example loss functions.
In Lemma 3 we introduce fairly general conditions under which a composite loss function (l, ψ) leads to a consistent class probability estimator. In particular we have a condition on the conditional risk L ψ (η, ·). (See also Figure 2.) Based on that we derive in Corollary 3 conditions which allow us to analyze the convergence rate for different loss functions. In the corollary we don't distinguish between L 0 ψ (η, ·) and L 1 ψ (η, ·), which leads to the same convergence rate for predicting values left and right from η. But the modulus of continuity for those two functions can be really different, especially when using asymmetric proper scoring rules Winkler (1994). We believe that by analyzing L 0 ψ (η, ·) and L 1 ψ (η, ·) individually one can extend our work to analyze the convergence behavior of asymmetric scoring rules in more detail.
As stated from the outset, one of our main goals is to emphasize the tight relationships between empirical risk minimization and class probability estimation in a distilled and compact version. The concepts of link functions and the relation between them and empirical risk minimization do not get the attention they deserve and are thus reinvented from time to time. Many of those concepts appear for example in the analysis of Zhang (2004) without any explicit reference to proper scoring rules.