Information, Divergence and Risk for Binary Experiments

Mark D. Reid; Robert C. Williamson

Source-linked AI summary

Information, Divergence and Risk for Binary Experiments

Mark D. Reid, Robert C. Williamson

arXiv:0901.0356v1Jan 5, 2009stat.MLmath.ST

TL;DR

The paper addresses the fragmented treatment of divergences, risks, losses, scoring rules, ROC curves, and information in binary learning problems. It unifies them through integral and variational representations tied to cost-sensitive classification, deriving broader bounds and connections to established algorithms. The resulting framework identifies cost-weighted misclassification loss as a fundamental primitive and supports alternative divergence-estimation techniques.

Problem
Binary learning objects such as risk, divergence, information, loss, regret, ROC curves, and scoring rules lack a coherent framework explaining their relationships.
Method
The paper systematically studies integral and variational representations and decomposes binary experiments into primitive problems related to cost-sensitive classification.
Results
The framework unifies these objects, yields more general surrogate-loss bounds and Pinsker inequalities, and connects divergences with SVMs and MMD.
Takeaways & Limitations
Cost-weighted misclassification loss emerges as a fundamental primitive, while weight-function representations suggest empirical estimators for f-divergences and related quantities.
Takeaways & Limitations
AUC is not intrinsic because its integration implicitly uses an empirical weighting, and the scoring-rule results require conditions excluding meaningless or endpoint-divergent losses.

Abstract

from arXiv · show

We unify f-divergences, Bregman divergences, surrogate loss bounds (regret bounds), proper scoring rules, matching losses, cost curves, ROC-curves and information. We do this by systematically studying integral and variational representations of these objects and in so doing identify their primitives which all are related to cost-sensitive binary classification. As well as clarifying relationships between generative and discriminative views of learning, the new machinery leads to tight and more general surrogate loss bounds and generalised Pinsker inequalities relating f-divergences to variational divergence. The new viewpoint illuminates existing algorithms: it provides a new derivation of Support Vector Machines in terms of divergences and relates Maximum Mean Discrepancy to Fisher Linear Discriminants. It also suggests new techniques for estimating f-divergences.

1. Introduction

The paper seeks a coherent, composable framework for binary machine-learning problems by relating information, losses, risks, divergences, and related representations. It develops a pluralistic unification that transfers insights across problems and yields new bounds and connections.

Motivation: Binary experiments provide a common setting for studying learning objects determined by mixtures of two class distributions.These objects include risk, divergence, information, loss, regret, ROC curves, matching losses, and Bregman divergences.
Motivation: The paper addresses the lack of agreed language, composability, theoretical guarantees, and well-understood primitives for machine learning.Its longer-term aim is modular reuse with known costs when transferring solutions between problems.
Approach: It compares problems rather than algorithms, avoiding intrinsic limits caused by the absence of an agreed formal definition of algorithms.The proposed agenda studies relations among problem representations instead.
Contributions: Binary experiments are used to unify disparate concepts while simplifying and generalising surrogate-loss regret bounds and Pinsker inequalities.The proofs rely on decomposing problems into primitives.
Contributions: The paper links scoring rules, f-divergences, Bregman divergences, and regret, showing that choosing one determines corresponding choices among the others.Weight-function representations also suggest algorithms for empirically estimating these quantities.

2. Convex functions and their representations

The paper develops convex-function tools centered on integral representations, dual transformations, and Jensen gaps. These representations identify primitive functions and curvature weights that organize divergences, risks, information, and losses.

Dual transformations: The perspective transform Iφ is convex in both arguments and provides the basis for the f-divergences introduced later.It also defines the Csiszár dual, and the original function can be recovered as φ(s) = Iφ(s,1).
Dual transformations: The Legendre-Fenchel dual is convex, and for convex functions its bidual faithfully represents the original function.When derivatives exist, the conjugate is given by the Legendre transform.
Integral representations: Convex and concave functions are analyzed using generalized Taylor expansions and integral representations built from piece-wise linear terms.The paper considers both endpoint-based and unit-interval representations, including a kernel ψ(s,t).
Integral representations: Choquet representations express the nonlinear part of a convex function as a weighted integral of primitive piece-wise linear functions.For convex φ, the weights are given by the nonnegative curvature terms φ′′(t), while linear components do not affect the measures studied.
Jensen gaps: Because several divergences, information measures, and risks are Jensen gaps, their behavior is determined by the curvature weights φ′′.This makes convex functions equivalent for these measures when they share the same nonlinear part.

3. Binary Experiments and Measures of Divergence

Binary experiments compare two distributions through statistical tests, likelihood ratios, classification rates, and divergences. The Neyman–Pearson lemma identifies the likelihood ratio as optimal, while f-divergences provide a broad framework for measuring distributional separation.

Binary experiments: A binary experiment consists of two probability measures P and Q over a common space, often representing positive and negative instances.Their separation quantifies how difficult it is to distinguish the distributions from samples drawn from their mixture.
Statistical tests: The likelihood ratio dP/dQ is the central statistic for preserving the distinction between P and Q.It maps observations from the instance space to the real line and underlies the optimal testing result.
Classification rates: A statistical test is a classifier assigning each instance to P or Q, with power equal to true positive rate and size equal to false positive rate.Thresholding a real-valued statistic generates a range of classification rates represented by an ROC curve.
Statistical tests: The Neyman–Pearson lemma shows that τ*(x) = dP/dQ(x) is uniformly most powerful for every threshold choice.Varying the threshold produces tests across sizes and yields a maximal ROC curve.
f-divergences: f-divergences measure separation between distributions through convex functions f satisfying f(1) = 0, with non-negativity following from Jensen gaps.The variational divergence uses f(t) = |t − 1|, is a true metric, and belongs to a primitive family from which other f-divergences can be built by weighted sums.

4. Risk and Statistical Information

The paper recasts binary experiments through generative class-conditional distributions and discriminative posteriors, linking risk, information, and divergences. Proper scoring rules yield concave Bayes risks and corresponding Bregman divergences, while f-divergences become interchangeable measures of task difficulty.

Generative and Discriminative Views: A binary experiment becomes a supervised task by mixing P and Q with prior π, pairing observations with positive and negative labels.The mixture reference measure is M = πP + (1 −π)Q.
Generative and Discriminative Views: The generative representation uses class-conditionals P and Q with prior π, whereas the discriminative representation uses observation distribution M and posterior η.Both decompositions are exact, and the paper translates between them using likelihood ratios and posterior probabilities.
Risk: Point-wise risk averages the loss under the conditional label probability, and full risk averages that quantity over observations distributed according to M.A task combines a loss with the binary distribution; its Bayes risk is the infimum of achievable full risk.
Proper Scoring Rules and Bregman Divergence: Proper scoring rules are exactly tied to concave point-wise Bayes risks, and negating such a risk produces the convex function underlying a Bregman divergence.The correspondence is bidirectional: concave Bayes risks induce proper scoring rules, while Bregman divergences yield proper scoring rules with Bayes risk equal to the negative generator.
Information and Divergence: Statistical information is a Bregman information and is nonnegative because its minimizer is the prior mean posterior, while Bregman divergence is nonnegative as regret.The paper also identifies log-loss with KL divergence, square loss with triangular discrimination, and 0-1 loss with V (P, Q).
Information and Divergence: For each prior π, f-divergences, statistical informations, and discriminative Bregman informations share a convex-function Jensen-gap representation and are bijectively related.The mapping λπ connects likelihood ratios with posterior probabilities.

5. Primitives and Weighted Integral Representations

The paper decomposes risks, divergences, and information measures into weighted integrals of primitive cost-sensitive classification objects. Their weight functions characterize behavior and expose correspondences, symmetry, convexity, and estimation issues.

Primitive Representations: Risks and f-divergences, including statistical and Bregman information, can be expressed as weighted integrals of primitive elements.For f-divergences and information, the weight function determines the measure’s behavior.
Primitive Representations: The weight functions of f-divergences and corresponding statistical information transform into one another for each prior π.This provides a direct translation between the two integral representations.
Integral Representations of f-divergences: The class of f-divergences is closed under linear combinations, extending from finite combinations to generalized weight functions.The result follows from convex combinations of the generating convex functions and the integral representations.
Integral Representations of f-divergences: Primitive f-divergences are generated by piecewise-linear hinge functions, and their weight function completely characterizes the behavior of the resulting divergence.Each generator has a single hinge, and affine translations do not change the f-divergence.
Integral Representations of f-divergences: Every convex f with f(1) = 0 admits a weighted representation over primitive f-divergences, with symmetry characterized by γ(π) = γ(1 −π).The primitive family is indexed by π ∈ (0, 1).
Proper Scoring Rules and Matching Losses: Proper scoring rules and their regrets admit weight-function representations, identifying Fisher-consistent probability-estimation losses with weighted primitive losses.The same weight function represents a loss’s risk, statistical information, and corresponding Bregman divergences.
Convexity, Matching Losses and Canonical Links: Canonical-link formulations make the corresponding Bregman divergence and loss convex in the hypothesis parameter.The paper expresses the estimator through an inverse link W^-1.
Estimation: KL divergence has weight γ(π) = 1/[π^2(1−π)^2], including a double pole at π = 0 that makes estimation difficult.The paper suggests avoiding endpoint regions and discusses KLε as a regularization example.

6. Graphical Representations

The paper uses ROC and risk diagrams to connect classifier performance, costs, priors, and divergences. These representations expose dualities between optimal tests, Bayes risk, and weighted areas under curves.

ROC Curves: ROC curves plot true-positive rates against false-positive rates as thresholds vary for a test statistic.The likelihood ratio provides an upper envelope, dominating every other ROC curve for a fixed binary experiment.
ROC Curves: The likelihood-ratio ROC curve dominates all other tests, while the dashed diagonal represents a random, uninformative test.For each false-positive rate, the likelihood-ratio test has the largest true-positive rate.
ROC Curves: Maximal AUC is not an f-divergence for all binary experiments, but it equals the variational divergence between P × Q and Q × P.The paper leaves investigation of related product-measure f-divergences for future work.
Risk Curves: Risk curves summarize an estimator’s risk across all costs for a fixed prior, or across all priors for a fixed cost.The diagrams compare the true posterior, an estimate, and the majority-class predictor.
Risk Curves: Weighted areas under risk curves recover full risk, regret, and statistical information through the corresponding loss weight function.The weighted area between an estimate and the true posterior gives regret, while the area between the prior tent and true-posterior curve gives statistical information.
Risk Curves: ROC and risk curves are dual: the maximal ROC curve for the likelihood ratio corresponds to the minimal Bayes risk curve.An explicit transformation maps between the two representations, with cost thresholds corresponding to test-statistic thresholds.

7. Bounding General Objects in Terms of Primitives

The paper derives tight bounds relating general divergences and regrets to primitive quantities such as variational divergence and cost-sensitive loss. These results include explicit, best-possible Pinsker bounds and surrogate-loss bounds.

General f-divergences and Bregman divergences are bounded in terms of primitive variational divergences and cost-sensitive regrets.The paper frames these inequalities as generalisations of classical Pinsker inequalities and surrogate-loss bounds.
A surrogate-loss bound asks how large Bw(η, ˆη) can be when Bc0(η, ˆη) = α, enabling simpler regret minimisation under one loss.The resulting bound quantifies the maximum price paid when replacing a target cost-sensitive loss with an easier surrogate.
The bounds in (73) and (74) are best possible, with tightness demonstrated by constructing distributions and conditional estimates attaining them.The construction uses arbitrary functions η(·) and ˆη(·) to realise the bound.
For arbitrary f-divergences, the paper gives bounds valid for all distributions P and Q, and they are tight when X contains a connected component.The construction is based on sampled values of the Bayes-risk curve and its piecewise-linear concave upper bound.
Theorem 28 states explicit bounds in terms of V(P,Q), including a best-possible improvement on the classical Pinsker inequality for KL(P,Q).The explicit optimal Pinsker representation coincides with Fedotov et al.’s implicit bound when the two are plotted.
The weighted-integral framework also suggests estimating f-divergences by estimating a sequence of Bayes-risk values at selected class priors.The sampled narrowband primitives provide the inputs for the theorem’s lower-bound construction.

8. Variational Representations

The paper shows that variational divergences and Bayes risks share equivalent optimisation structures, then extends variational representations to general f-divergences. This connects divergence estimation and learning procedures through admissible function classes and convex conjugates.

Under symmetry and sign-closure assumptions on R, constrained Bayes risk and variational divergence satisfy the theorem’s stated equivalence for every class prior π.The assumptions ensure the supremum can be represented using ±1-valued classifiers.
The variational representation reveals that the optimisation in Bayes risk is mirrored by a supremum over witness functions in variational divergence.The arg min is the hypothesis, while the arg max is the witness.
For 0-1 loss, the classical relation at π = 1/2 is L0−1(1/2, P, Q) = 1/2 − 1/4V(P, Q).The sign-closure requirement is tied to 0-1 loss and can be removed by considering linear loss instead.
With symmetric R contained in [−a,a]^X, the predictor attaining linear Bayes risk also attains the supremum defining variational divergence.This correspondence supports learning-theoretic interpretations of the variational representation.
For RKHS unit balls, the framework connects empirical estimators to the ν-Support Vector Machine and Maximum Mean Discrepancy.The RKHS representation uses feature maps and positive-definite kernels.
General f-divergence variational representations follow by substituting the Legendre-Fenchel representation of a convex generator into the divergence definition.The resulting formulations use function classes and convex conjugates, with alternative definitions related to extended infimal convolution.

9. Conclusions

The paper connects information, risk, regret, divergences, scoring rules, and classification through binary experiments, yielding unified representations and broader bounds. It also derives connections involving support vector machines and Maximum Mean Discrepancy while advancing a broader program of organizing machine-learning problems by their relationships.

Information, uncertainty, Bayes risk, regret, and f-divergences are translated between perspectives in supervised binary class probability estimation.
Integral representations connect risk curves, cost curves, ROC curves, variational divergences, risks, and regrets.
Surrogate regret bounds become more general and simpler, while generalized Pinsker inequalities relate Kullback–Leibler divergence to variational divergence.
A new derivation expresses support vector machines in terms of divergences and relates Maximum Mean Discrepancy to Fisher Linear Discriminants.
The results highlight cost-weighted misclassification loss as fundamental to the objects studied in binary experiments.
The paper is a first step toward understanding machine learning through relationships between problems rather than focusing primarily on solutions.

Appendix A. Proofs

The appendix derives an integral representation by expanding φ around 1 and using an integration-by-parts identity. The resulting kernel is expressed through a minimum involving s and t.

Integration by parts applied to tφ′′(t) produces an identity used to derive integral representations of binary class probability-estimation losses.
Substitution into the Taylor expansion of φ(s) about 1 yields the next form of the representation.
The kernel is defined as ψ(s, t) := min{(1 −t)s, (1 −s)t}.
Expanding the Jensen gap with the definition of ψ completes the corresponding algebraic representation.

A.3 Proof of Theorem 9

The proof establishes the theorem by verifying convexity and normalization for fπ, then substituting its representation into the f-divergence and statistical-information definitions.

The proof first checks that the constructed function is convex and satisfies fπ(1) = 0.
Convexity follows from the concavity of L and the convexity-preserving perspective transform, followed by composition with an affine function.
Substituting the resulting expression into the f-divergence definition uses dM = πdP + (1 −π)dQ and η = πdP/dM.
The forward direction and converse statement then follow from the derived expressions and the earlier discussion of the relevant representation.

A.4 Proof of part 5 of Theorem 33

The proof establishes convexity of an extended infimal convolution and applies perspective-function and Fenchel-duality arguments to the theorem’s fifth part.

A lemma states that the extended infimal convolution of convex, lower-bounded functions is convex in x.
When K(x, y) = g(x−y), the extended construction reduces to standard infimal convolution, whose convexity follows from marginalization of a jointly convex function.
For convex f and g, f□g is convex because it is represented through a perspective function and the lemma.
The fifth theorem part uses the conjugate identity h∗(s) = tφ(s/t) for h := tφ and Fenchel duality.
Swapping supremum and integration requires the cited theorem from Rockafellar and Wets.
The relation f,g(p, q) = qh(p/q) follows from h := f□g and the preceding representation.

A.5 Pinsker Theorems

The paper reduces Pinsker-bound optimization to admissible concave, piecewise-linear risk curves and derives explicit optimal bounds, including symmetric and asymmetric divergences.

Optimization construction: The optimal φ is obtained from the relation φ(π) = π ∧(1 −π) − ψ(P,Q)(π), equivalently from the Bayes-risk representation.Under the stated assumption on X, every admissible φ is realizable as a Bayes risk function for some (P, Q), establishing tightness.
Optimization construction: The optimization can be restricted to piecewise-linear concave ψ functions satisfying the endpoint and interpolation constraints.The resulting ψ connects (0, 0), the constrained points, and (1, 0).
The n = 1 case: For n = 1, the admissible risk curves are parameterized by a piecewise-linear ψ passing through (π1, ψ1), with slope a constrained to [−2ψ1, 2ψ1].For variational divergence, π1 = 1/2, making the divergence symmetric.
Explicit bounds: The theorem gives the first explicit representation of the optimal Pinsker bound, and its implicit and explicit forms coincide when plotted.The resulting bounds include a range for symmetric variational divergences and specialized formulas for several f-divergences.
Explicit bounds: The derived bounds specialize to concrete inequalities, including Ψ(P, Q) ≥ 8V^2/(4−V^2) and χ2(P, Q) ≥ 1{V < 1}V^2 + 1{V ≥ 1}V(2−V).For the KL case, the bound is expressed through a minimization over the admissible parameter range; the bound behaves like V^2 for small V.

Appendix C. Examples and Prior Work on Surrogate Loss Bounds

The appendix connects the paper’s surrogate-loss framework to prior regret-bound results and illustrates it with truncated quadratic loss, while noting the broader expressiveness of proper scoring rules.

Prior work and scope: Surrogate-loss bounds are situated within a growing literature on calibration, regret bounds, and proper scoring rules.The appendix specifically compares its results with work by Bartlett et al. and Steinwart and Christmann.
Prior work and scope: Margin losses cannot capture the richness of all possible proper scoring rules, even when generalized to uneven weights.Using the same φ function for both loss components remains less general than the paper’s proper-scoring-rule treatment.
Examples: The appendix states that its equations 130 and 131 match Bartlett et al.’s results after identifying B^1/2(η, ˆη) with the relevant ℓ1/2 loss measure.The comparison depends on the normalization convention used for the loss.
Examples: For truncated quadratic loss, the link function is ˆh(ˆη) = 2ˆη −1, the conditional risk is L(η) = 4η(1 −η), and the regret bound is B(η, ˆη) ≥ 4α^2.These results match the corresponding results of Bartlett et al. under the paper’s ℓ1/2 convention.

Appendix D. A Brief History of Pinsker Inequalties

The appendix reviews classical and later Pinsker inequalities, compares alternative approaches, and discusses convolution factorization examples and its unresolved inverse problem.

Pinsker inequalities: Classical Pinsker work established KL(P, Q) ≥ V^2/2, followed by polynomial and non-polynomial refinements involving higher powers or Vajda’s function.The historical sequence includes bounds with V^4, V^6, and additional higher-order terms.
Comparisons and conventions: Different divergence conventions require care because some references define variational divergence V with a factor-of-two difference.The appendix also notes bounds obtained under likelihood-ratio assumptions and summarizes inequalities for symmetric f-divergences.
Comparisons and conventions: Several authors derived general or specialized lower bounds for f-divergences in terms of V, but some results are difficult to evaluate explicitly or do not extend beyond n = 1.The appendix contrasts these approaches with the paper’s explicit and more general constructions.
Convolution factorization: The paper gives examples where f = g□g, including Pearson χ2 producing triangular discrimination under the convolution operation.The construction is computed by minimizing over an auxiliary positive variable.
Convolution factorization: The inverse factorization problem—recovering g from a given f such that f = g□g—remains unresolved, although several examples demonstrate existence.The appendix relates this question to convex composition and spectral factorization.

Appendix F. Empirical Estimators of VBH, 1 2(P, Q) and SVMs

The appendix derives empirical estimators and SVM variants from generalized variational divergence, showing links to kernel methods, sparsity control, and Fisher linear discriminants.

Empirical estimators: The appendix transfers distribution-level divergence–risk results to the empirical-sample setting, including implications for sample-based machine learning.It focuses on weighted empirical distributions rather than only the underlying distributions.
MMD and Fisher discriminants: With uniform weights, the biased MMD estimator corresponds to a Fisher linear discriminant in feature space when both within-class covariance matrices are identity.The equivalence follows because the constructed hypotheses are identical.
SVM derivation: Optimizing sample weights α minimizes J(α, x), maximizes the linear risk Llin, and yields the support vector machine.This is described as the most pessimistic weighting choice.
SVM derivation: Adding αi ≤ 1/(νm) makes ν control sparsity, and the resulting constrained formulation is equivalent to the ν-SVM algorithm.The constraints imply at least νm nonzero weights.
SVM derivation: The paper presents a simple, direct derivation of the SVM from generalized variational divergence rather than designing the algorithm solely through conventional kernel-classification routes.The appendix distinguishes this perspective from earlier kernel representations and classifiers.
MMD and Fisher discriminants: When the empirical distributions are close, the classifier based on the MMD witness has performance close to the worst possible.This places the resulting classification behavior in a regime distinct from the usual low-risk setting.