PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiclass Classification Calibration Functions

Bernardo Ávila Pires, Csaba Szepesvári

arXiv:1609.06385v1stat.MLcs.LG

TL;DR

Multiclass calibration functions can convert surrogate-risk bounds into true-risk bounds, but existing abstract techniques make deriving them for each loss laborious. The paper reduces that work to binary-like functions and a small set of loss-specific conditions, recovering and refining prior results while deriving functions for additional losses. The approach also yields improved risk calibration guarantees under the Mammen-Tsybakov noise condition.

  • Problem

    Existing multiclass calibration-function techniques are abstract enough that deriving functions for individual surrogate losses requires substantial case-by-case effort.

    Source: §1 · p. 2

  • Method

    The paper reduces multiclass calibration functions to binary-like functions by checking a small set of conditions for a chosen surrogate loss.

    Source: §4 · p. 18, §6 · p. 34

  • Results

    The analysis recovers and refines existing results for one-versus-all and variants of LLLW, derives novel results including for logistic regression, and generalizes improved risk calibration under the Mammen-Tsybakov noise condition.

    Source: §6 · pp. 34–35

  • Takeaways & Limitations

    The streamlined derivation offers a path to obtaining calibration-function results for other loss families proposed in the future.

    Source: §6 · p. 35

    The stated calibration-function theorem lacks elegant H-excess true-risk bounds when the Bayes-optimal classifier cannot be represented in the hypothesis class.

    Source: §2 · p. 8

Abstract

from arXiv · show

In this paper we refine the process of computing calibration functions for a number of multiclass classification surrogate losses. Calibration functions are a powerful tool for easily converting bounds for the surrogate risk (which can be computed through well-known methods) into bounds for the true risk, the probability of making a mistake. They are particularly suitable in non-parametric settings, where the approximation error can be controlled, and provide tighter bounds than the common technique of upper-bounding the 0-1 loss by the surrogate loss. The abstract nature of the more sophisticated existing calibration function results requires calibration functions to be explicitly derived on a case-by-case basis, requiring repeated efforts whenever bounds for a new surrogate loss are required. We devise a streamlined analysis that simplifies the process of deriving calibration functions for a large number of surrogate losses that have been proposed in the literature. The effort of deriving calibration functions is then surmised in verifying, for a chosen surrogate loss, a small number of conditions that we introduce. As case studies, we recover existing calibration functions for the well-known loss of Lee et al. (2004), and also provide novel calibration functions for well-known losses, including the one-versus-all loss and the logistic regression loss, plus a number of other losses that have been shown to be classification-calibrated in the past, but for which no calibration function had been derived.

1 Introduction

The paper targets the repeated, case-by-case effort required to derive multiclass calibration functions for converting surrogate-risk bounds into true-risk bounds. It streamlines that derivation by reducing multiclass calibration functions to binary-like functions and checking a small set of conditions for specific losses.

1 Introduction

  • The analysis reduces multiclass calibration functions to binary-like functions that are easier to compute for particular surrogate losses.When the proposed conditions hold, the resulting function is essentially a binary-loss calibration function.Source: §1 · p. 2
  • Under the Mammen-Tsybakov noise condition, the reduction also generalizes improved calibration guarantees from binary to multiclass classification.The stated improvement concerns risk, not pointwise risk.Source: §1 · p. 2
  • The approach refines Ávila Pires et al. (2013) for ordinary cost-insensitive classification, rather than their cost-sensitive setting.The paper also describes its analysis as a generalization of their work on losses introduced by Lee et al. (2004).Source: §1 · pp. 2–3
  • The framework recovers cost-insensitive calibration functions for Lee et al. (2004) and gives novel functions for logistic regression, one-versus-all, and other background-discrimination losses.The paper also says verifying an additional condition for some decoupled losses is no harder than deriving a related binary calibration function.Source: §1 · p. 3
  • The analysis does not cover losses proposed by Weston and Watkins (1998), Zou et al. (2006), or Beijbom et al. (2014), for which the authors believe a different analysis is required.The authors identify broad applicability to losses with similar structure, but not these three proposals.Source: §1 · p. 3

2 Preliminaries

The preliminaries frame classification as minimizing expected misclassification risk, while motivating convex surrogate losses as a tractable alternative for empirical risk minimization. They then explain how surrogate-risk bounds can yield true-risk bounds, with calibration functions offering tighter conversion and specific limits in parametric settings.

2 Preliminaries

  • Because empirical 0-1 risk minimization can be computationally hard for some hypothesis classes, the paper considers minimizing convex surrogate risk and converting resulting bounds to true-risk bounds.A hypothesis class and loss are chosen so that empirical surrogate-risk minimization can be done efficiently.Source: §2 · pp. 4, 6
  • Scores are mapped to predicted classes by a maximum selector, and composing a score function with it can represent any classifier.The surrogate loss takes a real-valued score vector and a class as input, unlike the 0-1 loss on a predicted class and true class.Source: §2 · pp. 3, 5
  • The conversion framework assumes a high-probability surrogate-risk bound for the learning algorithm; available surrogate-risk methods can supply such bounds.The text also allows replacing the high-probability assumption with an expectation bound to obtain an expectation bound for true risk.Source: §2 · pp. 6–7
  • Simply upper-bounding the 0-1 loss by the surrogate loss can yield loose true-risk bounds, as illustrated by a factor-of-two hinge-loss example.Even a surrogate-risk bound tending to zero does not guarantee an optimal classifier from that bound alone in the example.Source: §2 · p. 7
  • A calibration function converts excess surrogate-risk rates into excess true-risk rates, and its existence is equivalent to calibration or Fisher consistency.Calibration functions can therefore provide tighter guarantees than direct loss upper-bounding.Source: §2 · pp. 7–8
  • The stated calibration-function theorem lacks elegant H-excess true-risk bounds when the Bayes-optimal classifier is unavailable within the hypothesis class.The paper leaves H-calibration functions for the parametric setting as future work and notes that its bounds remain informative in non-parametric settings when approximation error is controlled or zero.Source: §2 · p. 8

3 The calibration toolset

Section 3 reviews calibration functions and their use in risk bounds for binary and multiclass losses, including reductions and calibration conditions. It also extends fast-rate results to multiclass classification under a convex, non-decreasing calibration function, a condition met by the authors’ functions.

3.1 The maximum calibration function

  • The maximum calibration function δmax bounds every calibration function from above and is itself a calibration function exactly when it is positive for every ε > 0.Any positive lower bound on δmax is also a calibration function.Source: §3.1 · pp. 9–10

3.2 From δmax to risk bounds

  • A positive lower bound on δmax can yield risk bounds by taking expectations with p = PY|X, provided the required infimum is bounded.The guarantee is vacuous unless the calibration lower bound is positive for every ε > 0 and every p.Source: §3.2 · pp. 10–11

3.3 Calibration functions in binary classification

  • For binary labels with S = S0 and L(y, s) = ϕ(−sy), if convex, lower-bounded ϕ satisfies ∂ϕ(0) ⊂ [0, ∞), δbinary is a calibration function iff ϕ has a unique positive derivative at zero.On S = [−1, 1], the losses for ϕ(t) = |1 + t| and ϕ(t) = (1 + t)+ are identical; ϕ(t) = (1 + t)2 and ϕ(t) = ((1 + t)+)2 share the same δbinary.Source: §3.3 · pp. 11–12

3.4 Calibration functions and multiclass classification

  • Multiclass losses that reduce to binary margin losses can nevertheless have substantially different calibration behavior in the multiclass setting.The section also presents LZhang as a flexible family that includes several losses through different choices of score space and functions.Source: §3.4 · p. 13

3.4.1 Calibration

  • For the surveyed convex losses, ϕ′(0) > 0 is necessary for calibration, while further consistency conditions vary by loss.For example, LLLW is consistent when ϕ is differentiable; the one-versus-all loss is a special case of LZhang and is calibrated under similar conditions.Source: §3.4.1 · pp. 14–15

3.4.2 Calibration functions

  • Zhang (2004) derives a calibration function for LRRKA from its optimal binary surrogate risk V, with strong concavity providing a sufficient condition.The paper identifies this result as a special case of its later Lemma 5.4.Source: §3.4.2 · pp. 15–16
  • For LLLW, Ávila Pires et al. (2013) give a calibration function depending on ε and p; the paper uses their analysis to motivate reducing multiclass calibration functions to binary ones.When the infimum over θ is attained at zero, their result generalizes the binary margin-loss result for hinge, exponential, and squared transformations.Source: §3.4.2 · p. 16
  • Theorem 3.11 extends the Mammen–Tsybakov noise-condition fast-rate result to multiclass classification, assuming a convex, non-decreasing calibration function.The authors state that their results lower-bound δ_max(ε) by δ_binary(ε), which is convex.Source: §3.4.2 · p. 16
  • Requiring δ to be non-decreasing imposes no real restriction, since any calibration function can be replaced by a non-decreasing one that is no worse.The replacement is ε ↦ sup_{ε′≤ε} δ(ε′), which is greater than or equal to δ.Source: §3.4.2 · p. 16
  • The proof adapts Bartlett et al. (2006)'s fast-rate argument to multiclass classification and applies the calibration guarantee contrapositively.Source: §3.4.2 · p. 17

4 Streamlining the derivation of calibration functions for multiclass classification

The section streamlines multiclass calibration analysis by reducing its bounds to binary calibration-like functions through conditions that can be checked for a chosen loss. The reduction does not establish that the binary function is maximal in the multiclass case; it does give a tight characterization when there are two classes.

4 Streamlining the derivation of calibration functions for multiclass classification

  • An adjustment function separates expected surrogate risk into an adjusted term and the adjustment, supporting reuse of results across related loss formulations.For example, LLLW can be written in the LZhang form with a specified ψ and score set S0.Source: §4 · pp. 18–19
  • Lemma 4.1 applies to multiclass losses when L satisfies Conditions 1–3, but does not necessarily imply δmax = δbinary for |Y| > 2, since the corresponding δmax terms need not match.Source: §4 · p. 19
  • Condition 1 restricts minimization to scores meeting two class constraints, and Condition 2 expresses the resulting lower bound through pseudo-risks.Condition 1 equates the infimum over the constrained score set with one over scores satisfying the two class-specific constraints.Source: §4 · p. 20
  • Conditions 3–4 lower-bound the binary-like function by a non-decreasing ζ of the probability gap, with Condition 4 taking ζ = δbinary.The monotonicity of ζ allows the gap bound to yield ζ(ε).Source: §4 · pp. 20–21
  • For |Y| = 2, δbinary is the largest calibration function, δmax, and positivity of δbinary for every ε > 0 characterizes calibration under the stated conditions.The section explicitly warns that this equality need not hold for more than two classes.Source: §4 · pp. 19, 21

5 Case studies

The case studies apply the paper’s streamlined calibration analysis to background discrimination, multiclass logistic regression, Lee et al. (2004), LLLW, hinge, and Liu losses. They derive calibration results under stated conditions and identify cases where technical conditions can be verified.

5.1 The background discrimination loss

  • For convex LZhang with F(t)=t, non-decreasing ψ, Assumption 2, and Condition 8, calibration is equivalent to δbinary(ε)>0 for all ε>0, with equality when |Y|=2.Condition 8 implies Condition 3 for the stated LZhang setting, and the analysis also recovers Theorem 3.9 for LRRKA.Source: §5.1 · pp. 25–27
  • Table 4 summarizes calibrated LZhang variants discussed by Zhang (2004) and whether, and under what conditions, they satisfy Condition 8.The table also includes the variant with ψ(t)=−t and ϕ(t)=(at+b)2 for a,b∈R.Source: §5.1 · p. 27, Table 4 · p. 27

5.2 Multiclass logistic regression

  • The logistic regression loss has equivalent coupled and decoupled formulations, and the paper derives its calibration function, with equality in the bound when |Y|=2.For the coupled form, risk minimizers eliminate the coupled part; the decoupled form uses S=∆|Y|.Source: §5.2 · pp. 28, 30

5.3 The loss of Lee et al. (2004)

  • In the cost-insensitive setting, the analysis refines Theorem 3.10 by verifying Condition 4 and providing a result for δmax independent of p.For presentation, it verifies Condition 2 via assumed Conditions 6 and 7 in a special case of Theorem 3.10.Source: §5.3 · p. 30
  • Condition 7 is established for ϕhinge, ϕexp, and ϕsquared, but its status for ϕlogit is unclear.The hinge case is proved; the exponential and squared cases are omitted as straightforward calculations.Source: §5.3 · p. 31
  • The authors conjecture that differentiability of ϕ on (tinf, −tinf) implies Condition 7, but report that they have not proved or disproved this.They suggest differentiability on the increasing part of ϕ, alongside convexity and ϕ′(0) > 0, may be a minimal requirement because adding kinks can yield non-calibrated losses.Source: §5.3 · p. 31
  • For convex, lower-bounded ϕ satisfying Condition 7, Theorem 5.19 gives a refined calibration result whose δmax and δbinary do not depend on p, with equality when |Y| = 2.The supplied passage omits the theorem’s formula, so the result is stated without specifying its calibration function.Source: §5.3 · p. 33
  • Theorem 5.19 and Lemma 5.18 also yield a result for LLiu because its δmax matches that of LLLW with ϕhinge.The binary-class case holds with equality.Source: §5.3 · p. 33

6 Conclusion

The paper reduces multiclass calibration-function derivation to checking conditions that yield binary-like bounds, then applies the analysis to multiple surrogate-loss families. It reports novel, recovered, and refined results, improved risk guarantees under the Mammen-Tsybakov noise condition, and remaining gaps in the analysis.

6 Conclusion

  • The strategy reduces lower-bounding multiclass δmax to binary-like δbinary functions and gives improved risk calibration guarantees under the Mammen-Tsybakov noise condition.The paper states that this generalizes Bartlett et al. (2006) to the multiclass case.Source: §6 · p. 34
  • The analysis covers decoupled LZhang variants, logistic regression, and LLiu, and recovers one-versus-all and some LLLW results.For LLLW, the results bound δmax(ε) rather than δmax(ε, p) and require weaker conditions.Source: §6 · pp. 34–35
  • The paper presents novel results for a large family of surrogate losses, including logistic regression, and recovers and refines existing results in a unified manner.The conclusion notes that logistic regression is frequently used in practice.Source: §6 · p. 35
  • The reduction covers most, but not all, multiclass surrogate losses: applying it to LWW and LBSKV requires further work on Condition 2.For LZZH, Condition 7 fails even in simple cases such as ϕexp, so minor adaptations of the LLLW results do not appear feasible.Source: §6 · p. 35
  • For some decoupled formulations discussed by Zhang (2004), Condition 8 fails; the paper calls for a relaxation or alternative proofs for Lemma 5.5.The authors also identify verification of Condition 2 for LZhang under suitable conditions on F as an open issue for other coupled formulations.Source: §6 · p. 35
  • The conclusion leaves scaling effects and extensions to simplex coding and other score transformations for future investigation.It specifically notes that scaling by c introduces a factor of c in the risk bound from Theorem 2.2.Source: §6 · pp. 35–36

A Proofs

The appendix presents omitted proofs and technical results, including a non-calibration example for 1/2-Kink and an explicit optimizer for a two-coordinate objective.

A Proofs

  • The appendix presents proofs omitted from the main text along with accessory technical results, beginning with two well-known facts.Source: A Proofs · p. 39
  • The appendix records reusable proof tools, including a convex subgradient lower bound and an infimum comparison using mappings between feasible sets.Source: A Proofs · p. 39
  • In a three-class, one-point scenario, 1/2-Kink is not classification-calibrated because a surrogate-risk minimizer does not uniquely align its maximum score with the uniquely most probable class.Source: A Proofs · p. 39
  • For the two-coordinate logarithmic objective, the minimizing score is s*=q=p1/(p1+p2).Source: A Proofs · p. 44
Loading 1609.06385v1…