PaperlayerView exact revision on arXiv

Source-linked AI summary

Composite Binary Losses

Mark D. Reid, Robert C. Williamson

arXiv:0912.3301v1stat.ML

TL;DR

The paper asks how binary losses for classification and probability estimation can be understood beyond symmetric margin losses. It develops characterisations of composite losses, surrogate quality, and convexity, and reports that all convex proper losses are non-robust to misclassification noise. The paper also identifies settings where convex surrogate losses are incommensurable.

  • Problem

    Prior work focused heavily on symmetric margin losses, leaving the general non-symmetric structure of composite losses and the choice of best surrogate loss to characterize.

  • Method

    The paper analyzes composite losses formed from proper losses and link functions, using partial losses, intrinsic parametrisations, calibration relationships, and link- and weight-function characterisations of convexity.

  • Results

    All convex proper losses are non-robust to misclassification noise, and some convex surrogate losses are incommensurable on particular problems.

  • Takeaways & Limitations

    Composite-loss analysis provides characterisations connecting margin losses, properness, classification calibration, convexity, surrogate comparison, and surrogate tuning.

  • Takeaways & Limitations

    The best-surrogate question is meaningful only when expectations over examples and a restricted hypothesis class H ⊊ [0, 1]^X are specified.

Abstract

from arXiv · show

We study losses for binary classification and class probability estimation and extend the understanding of them from margin losses to general composite losses which are the composition of a proper loss with a link function. We characterise when margin losses can be proper composite losses, explicitly show how to determine a symmetric loss in full from half of one of its partial losses, introduce an intrinsic parametrisation of composite binary losses and give a complete characterisation of the relationship between proper losses and ``classification calibrated'' losses. We also consider the question of the ``best'' surrogate binary loss. We introduce a precise notion of ``best'' and show there exist situations where two convex surrogate losses are incommensurable. We provide a complete explicit characterisation of the convexity of composite binary losses in terms of the link function and the weight function associated with the proper loss which make up the composite loss. This characterisation suggests new ways of ``surrogate tuning''. Finally, in an appendix we present some new algorithm-independent results on the relationship between properness, convexity and robustness to misclassification noise for binary losses and show that all convex proper losses are non-robust to misclassification noise.

1 Introduction

The paper extends binary-loss analysis from symmetric margin losses to general composite losses for classification and probability estimation. It develops characterisations linking properness, calibration, convexity, surrogate quality, and robustness.

  • Motivation: Composite binary losses combine a proper loss with a link function and support class probability estimation through probability-valued predictions.Proper losses are designed to minimize conditional risk at the true class probability, while link functions map predictor outputs into [0, 1].
  • Motivation: The paper targets the general non-symmetric setting, extending beyond margin losses that intrinsically treat positive and negative classes symmetrically.This addresses the stated importance of handling non-symmetric classification problems.
  • Core characterisations: It characterises proper composite losses through partial losses, introduces an intrinsic parametrisation, and relates properness to classification calibration.The analysis also covers margin losses and connects regret with Bregman divergences.
  • Convexity and tuning: It characterises proper-composite convexity using the link function and proper-loss weight function, motivating new approaches to surrogate tuning.The convexity characterisation is framed around the question of which surrogate loss is best.
  • Surrogate losses: The paper defines “best” surrogate losses and shows that some convex surrogate losses are incommensurable on particular problems.It also explicitly identifies a surrogate with the best surrogate regret bound in a certain sense.
  • Robustness: The appendix shows that all convex proper losses are non-robust to misclassification noise.This is presented as an algorithm-independent relationship among properness, convexity, and noise robustness.

2 Losses and Risks

This section establishes the basic objects used throughout the paper: binary losses, partial losses, experiments, conditional and full risks, and Bayes risks. It also introduces properness and the conditional Bayes-risk curve.

  • Losses: A binary loss assigns a nonnegative penalty to a prediction value when one of two possible labels is observed.The loss is represented by partial losses for the positive and negative labels.
  • Losses: Margin losses express loss as φ(yv), while class probability estimation losses use predictions in [0, 1] as direct probability estimates.Examples include 0-1, hinge, logistic, exponential, square, log, and cost-weighted misclassification losses.
  • Risks: An experiment is specified by the joint distribution P, or equivalently by the observation-conditional probability η and the marginal distribution M.The conditional probability is η(x) = Pr(Y = 1|X = x).
  • Risks: Conditional risk averages label-specific losses at a fixed class probability, while full risk averages point-wise risk over the marginal distribution of examples.The predictor in the full-risk setting is a function v: X → V.
  • Risks: The Bayes risk is the minimal achievable risk, and its conditional counterpart is the point-wise or conditional Bayes risk.The paper uses L(v, P) as shorthand for full risk under the corresponding experiment.
  • Properness: The conditional Bayes-risk curve, also called generalized entropy, is important because its curvature determines much of the structure of probability-estimation losses.This motivates studying the curve as a central object in loss analysis.

3 Losses for Class Probability Estimation

This section characterises proper losses for class probability estimation through conditional risk, partial losses, Bayes-risk curvature, and weight functions. It also derives structural consequences for symmetric losses and their construction.

  • Proper, Fair, Definite and Regular Losses: Proper losses minimise conditional risk at the true class probability, with strict properness requiring a unique minimiser.The conditional risk is L(η, ˆη), and properness requires L(η)=L(η,η) for every η.
  • The Structure of Proper Losses: For differentiable proper losses, one partial loss determines the other, while symmetry makes the loss fully determined by half of one partial loss.Symmetry of the loss is equivalent to symmetry of its weight function or conditional Bayes risk.
  • The Structure of Proper Losses: Savage’s characterisation states that properness is equivalent to concavity of the point-wise Bayes risk together with a constraint on partial losses.Regularity extends this characterisation to the endpoints of the unit interval.
  • The Structure of Proper Losses: For proper losses, regret equals the Bregman divergence generated by the negative conditional Bayes risk.This connects excess conditional risk with a generalised distance induced by f = −L.
  • The Structure of Proper Losses: A proper loss can be represented using a nonnegative weight function w, which is the negative curvature of the conditional Bayes risk.Conversely, defining a loss from a suitable weight function yields a proper loss; strict properness requires non-zero weight mass on every open subset.

4 Composite Losses

Composite losses combine a class-probability loss with an invertible link, allowing predictions on an arbitrary scale to be interpreted as probabilities. The section characterises properness through the link, partial losses, and an intrinsic weight-like quantity.

  • Composite Losses: A composite loss is formed by composing a CPE loss with the inverse of an invertible link from probabilities to prediction values.The link maps the unit interval to a prediction range, while its inverse supplies probability interpretations for predictions.
  • Proper Composite Losses: Properness constrains the composite partial losses through a nonnegative weight function and the link’s derivative.Theorem 10 gives necessary and sufficient conditions when the link and partial losses are differentiable under a strictly monotone link.
  • Proper Composite Losses: The ratio ρ acts as a coordinate-free weight function for composite losses and is nonnegative under the proper-composite conditions.It incorporates the link while retaining the role of the proper loss’s weight function.
  • Proper Composite Losses: Once the weight function and link are fixed, the composite partial losses are determined up to an additive constant; alternatively, one partial loss and the link determine the other.For arbitrary partial losses, the corresponding reference link is the one that guarantees properness and calibration.
  • Margin Losses: For a margin loss, a suitable link gives consistent probability interpretations, whereas another link can make those interpretations inconsistent.The required link is symmetric, and for flat spots where φ′(v)=0 it may not be unique.
  • Margin Losses: As α approaches zero in the examined inverse-link family, probability estimates approach 1/2 for almost all finite predictions, explaining why hinge loss supports classification but not probability estimation.The limiting behaviour places estimates infinitesimally to either side of 1/2 except for very large prediction values.

5 Classification Calibration and Proper Losses

The section defines classification calibration for probability-estimation losses and establishes its exact relationship with strict properness, extending the result to composite losses and recovering the margin-loss condition.

  • Classification Calibration for CPE Losses: Classification calibration at c requires the conditional risk to be strictly lower than risks from predictions on the opposite side of c.The competing estimate may also equal c.
  • Classification Calibration for CPE Losses: Classification calibration at every c ∈ (0, 1) is equivalent to strict properness for CPE losses.
  • Classification Calibration for CPE Losses: For a proper loss with weight w, calibration at c holds exactly when w(c) ≠ 0.
  • Calibration for Composite Losses: For invertible differentiable links, a composite loss is calibrated at every c ∈ (0, 1) exactly when its associated proper loss is strictly proper.
  • Classification Calibration for CPE Losses: For differentiable partial losses, calibration at c is characterised by ℓ′_1(c) < 0 and cℓ′_1(c) + (1 − c)ℓ′_−1(c) = 0.
  • Calibration for Composite Losses: In the margin-loss special case, the general differentiable condition reduces to φ′(0) < 0, matching the earlier characterisation.

6 Convexity of Composite Losses

The section characterises convexity and quasi-convexity of composite losses through the proper loss’s weight function and link, yielding tuning rules and canonical-link guarantees while identifying practical limits.

  • Convexity of Composite Losses: The intrinsic parametrisation combines the proper loss’s weight function w and link derivative ψ′, or equivalently their ratio ρ, to characterise composite-loss convexity.The characterisation supports choosing either w or ψ and solving for the compatible counterpart.
  • Convexity of Composite Losses: Convexity of each partial loss, every conditional risk, and empirical risk are equivalent for the loss classes considered.The equivalence follows because conditional risks and empirical risks are nonnegative weighted sums of partial losses, while singleton samples recover each partial loss.
  • Convexity of Composite Losses: Properness does not guarantee that empirical risk avoids local minima, because sums of quasi-convex functions need not be quasi-convex.
  • Convexity of Composite Losses: Proper composite losses with invertible differentiable links have conditional risks that are quasi-convex in the prediction value.
  • A Simpler Characterisation of Convex Composite Losses: For linear links, including the identity link, convexity holds exactly when w(x) ≤ 1/(1 − x) for all x ∈ (0, 1).
  • Canonical Links: A proper loss combined with its canonical link is always convex, regardless of the proper loss’s weight function.The canonical link is defined by ψ′(v) = w(v), which makes ρ equal to 1.
  • A Simpler Characterisation of Convex Composite Losses: The squared-loss weight w(c) = 1 lies within the allowable convexity region for the identity link.

7 Choosing a Surrogate Loss

The paper formalizes how to compare surrogate losses and shows that no universal best proper convex surrogate is established, with losses potentially preferred on different experiments. It also derives bounds relating the minimal convex proper loss to 0-1 regret.

  • Motivation: Because convex surrogates support tractable optimization while 0-1 loss is non-convex, the paper frames surrogate choice as a problem-dependent optimization question.The discussion motivates minimax formulations when a universal best surrogate does not exist.
  • Defining the best surrogate: Surrogate quality is defined through the reference-loss penalty incurred by hypotheses that minimize surrogate risk within a restricted class H.The penalty measures the minimum reference-loss risk achievable by an H-minimizer of the surrogate loss.
  • Defining the best surrogate: The best-surrogate question is meaningful only after averaging over X and restricting hypotheses to H, because all proper losses share the same conditional minimizer.Without restrictions, every proper loss recovers the true class probability conditionally.
  • Incommensurability: The paper conjectures that every proper convex loss is outperformed by another proper convex loss for some hypothesis class and experiment.A proof would require constructing experiments that reverse the surrogate ordering for each pair of losses.
  • The minimal loss: The minimal symmetric convex proper loss is obtained by minimizing the admissible weight function pointwise and yields an explicit inverted bound from its regret to 0-1 regret.The resulting bound is plotted in Figure 4, but the authors do not establish that this loss is universally best.

8 Conclusions

The conclusions consolidate the paper’s characterizations of composite binary losses and emphasize weight-function parametrization as a basis for surrogate tuning. They also retain open questions about whether the minimal loss has a stronger optimality property.

  • Contributions: The paper characterizes composite losses through their links to margin losses, properness, classification calibration, symmetry, convexity, and natural parametrizations.It also considers the problem of choosing a best surrogate loss.
  • Parametrization: The pair (w, ψ′) is presented as a natural intrinsic parametrization because both loss and link are represented through non-negative weight functions.The canonical link sets ψ′ equal to w.
  • Surrogate tuning: Surrogate tuning adapts the surrogate to the problem while retaining 0-1 loss as the target minimized for computational reasons.Low-dimensional parametrizations of admissible weight functions could let algorithms explore convex losses and evaluate resulting 0-1 risk.
  • Open questions: The authors conjecture that ℓminimal has a special property beyond pointwise weight minimization and the smallest normalized 0-1 regret bound.They suggest a possible weaker minimax optimality but leave its exact nature unresolved.
  • Open questions: The appendix example suggests that no convex proper weight function crosses over wminimal, distinguishing the minimal loss from the crossing behavior used to show incommensurability.This is presented as an author-supported observation about the constructed example.

A Example Showing Incommensurability of Two Proper Surrogate Losses

A simple construction compares two proper surrogate losses on two problems using a linear hypothesis class and identity link. The preferred surrogate reverses between the problems, demonstrating incommensurability.

  • Setup: The example uses X = [0, 1] with uniform M and two problems induced on this input space.The construction evaluates constrained surrogate optima under the same general setup.
  • Setup: The comparison uses a simple linear hypothesis class, identity link function, and two proper losses ℓ1 and ℓ2 specified by their weight functions.The corresponding conditional losses are calculated from these weight functions.
  • Results: For problem η1, surrogate ℓ2 yields a constrained Bayes-optimal hypothesis with lower 0-1 risk than the corresponding optimum for ℓ1.Thus ℓ2 is better than ℓ1 on η1 under the example’s constrained comparison.
  • Results: For problem η2, the ordering reverses: surrogate ℓ2 is worse than ℓ1.The same pair of losses therefore cannot be ranked universally under the constructed experiments.

B An Alternate View of Canonical Links

The appendix gives an alternate convex-duality view of canonical links and Bregman divergences. It shows that choosing the inverse link as W^-1 produces convex conditional loss and divergence expressions in the hypothesis parameter.

  • Motivation: The appendix uses convex duality to provide an alternate understanding of canonical links and an improved formulation of Bregman-divergence duality.The authors note that the duality result may be independently useful.
  • Convex duality: The Legendre-Fenchel dual φ⋆ is the convex function obtained from φ through the supremum of linear pairing minus φ.The appendix also identifies the differentiable case with the Legendre transform.
  • Bregman representation: The appendix parametrizes the weighted conditional loss and its regret using the convex function W associated with the weight function.This follows the standard Bregman-divergence parametrization by a convex function.
  • Bregman representation: Theorem 34 establishes the stated relationship for the Bregman divergence DW and its dual parametrization over x and y in [0, 1].The proof proceeds by substitutions involving W and its inverse.
  • Canonical-link convexity: When ψ^-1 = W^-1, the predicted probability is W^-1(hat h), and both DW(η, W^-1(hat h)) and LW(η, W^-1(hat h)) are convex in hat h.The convexity argument uses convexity of the Legendre-Fenchel dual together with a linear term.
  • Canonical-link convexity: The canonical link is identified with the link whose derivative equals the loss weight function, and its composite loss is convex.This connects the appendix’s dual formulation to the paper’s earlier canonical-link result.

C Convexity and Robustness

The appendix connects convexity and robustness to random class noise for binary losses. It shows how noise transforms conditional risk and concludes that strictly proper, hence convex proper, losses are non-robust.

  • Related results: Convex potential functions, including convex margin losses, have previously been shown non-robust to random class noise in boosting settings.The cited result concerns boosting algorithms and a specific learning task.
  • Non-convex alternatives: Non-convex margin losses were proposed as alternatives, with experimental evidence suggesting greater robustness to class noise than convex counterparts.RobustBoost is described as using parameterised non-convex surrogate losses that approximate 0-1 loss with more boosting iterations.
  • Noise transformation: Random class-flip noise transforms a composite loss into a corrupted loss and changes its conditional risk through the corrupted class probability.The corrupted probability is a convex combination of the original probability and its complement.
  • Robustness consequence: Strictly proper losses cannot remain proper after class-noise corruption because the noisy-risk minimiser differs from the original probability.The paper therefore suggests that strictly proper losses are not robust to any class noise.

C.1 Robustness implies Non-convexity

The paper defines pointwise robustness through overlap between clean and noisy conditional-risk minimisers, then characterises robustness for threshold losses and arbitrary proper losses. This yields the conclusion that every convex proper loss is non-robust to random class noise.

  • Definition: A loss is α-robust at η when clean and α-corrupted conditional risks share at least one minimiser.This definition concerns pointwise conditional-risk minimisation rather than a particular learning algorithm.
  • Threshold losses: 0-1 loss, equivalently ℓ_1/2, is α-robust for every η and α, whereas other thresholds have more limited robust regions.For c ≠ 1/2, the robust range excludes an interval determined by c and α.
  • Threshold losses: For threshold loss ℓ_c, robustness depends on whether η and its corrupted version ηα lie on the same side of c.The minimiser sets are disjoint when the two probabilities fall on opposite sides of the threshold.
  • Proper-loss characterisation: For a proper loss with weight function w, any threshold component with positive weight that is non-robust makes the full proper loss non-robust.The argument uses the intersection of minimiser sets in the integral representation of proper losses.
  • Main consequence: All convex proper losses are non-robust to random class noise for every nonzero noise level.Convex proper losses are strictly proper and therefore have weight functions non-zero across the interval, allowing the general theorem to apply.
  • Scope and comparison: The result is algorithm-independent but not directly comparable to boosting results because the robustness definitions and loss classes differ.The paper’s proper-loss focus excludes convex losses such as hinge loss covered by the cited boosting analysis.
  • Scope and comparison: Robustness does not imply convexity’s converse: some non-convex strictly proper losses are also non-robust under this definition.The paper notes that this qualifies arguments claiming robustness from non-convexity alone.
Loading 0912.3301v1…