Prediction problems, risks, and empirical minimization

A supervised prediction problem consists of nonempty measurable spaces $(\mathsf{X},{\mathrm{\Sigma }}_X)$ of instances, $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$ of labels, and $(\mathsf{A},{\mathrm{\Sigma }}_A)$ of prediction actions; the product measurable space $(\mathsf{X}\times \mathsf{Y},{\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_Y)$; a probability measure $P$ on that product; a nonempty class $\mathcal{F}$ of measurable predictors $f:\mathsf{X}\to \mathsf{A}$; and a loss $\mathrm{\ell }:\mathsf{A}\times \mathsf{Y}\to [0,+\mathrm{\infty }]$ that is measurable with respect to ${\mathrm{\Sigma }}_A\otimes {\mathrm{\Sigma }}_Y$. The law $P$ need not be supported on a deterministic labeling function, and this definition imposes no assumption that sample observations be independent or share a common law.

Measurable spaces and measurable sets: a measurable space is a set with a specified sigma-algebra.

A measurable function between measurable spaces: a function is measurable when preimages of measurable sets are measurable.

The product sigma-algebra and its finite iterates: the product sigma-algebra is generated by measurable rectangles.

Probability measures and probability spaces: a probability measure has total mass one.

Loss functions and risk: a loss is nonnegative and measurable in the action variable; risk is an extended nonnegative integral.

The joint law $P$ can be used at a fixed member of a statistical experiment. If it is selected from a parametric family, this prediction definition makes no parameter-recovery claim, and the family of laws need not distinguish parameter labels.

Statistical experiments: an experiment is a measurable sample space with a parameter-indexed family of probability measures.

Parametric statistical models: the parameter-to-law map need not be injective.

For a supervised prediction problem with joint law $P$, the population risk of any measurable predictor $f:\mathsf{X}\to \mathsf{A}$ (in particular, every $f\in \mathcal{F}$) is the extended nonnegative integral $R_P(f):={\int }_{\mathsf{X}\times \mathsf{Y}}\mathrm{\ell }(f(x),y)P(d(x,y))\in [0,+\mathrm{\infty }]\mathrm{.}$ For an ordered sample $S=((x_1,y_1),\dots ,(x_m,y_m))$ of length $m\ge 1$, the empirical risk or training risk of any such $f$ is ${\widehat{R}}_S(f):=\frac{1}{m}{\sum }_{i=1}^m\mathrm{\ell }(f(x_i),y_i)\in [0,+\mathrm{\infty }]\mathrm{.}$ Neither definition assumes finite risk. The sum uses extended nonnegative arithmetic; since $m\ge 1$, any summand equal to $+\mathrm{\infty }$ makes the empirical risk $+\mathrm{\infty }$.

Supervised prediction problems: fixes the measurable spaces, joint law, predictor class and loss.

Expectation of a nonnegative or integrable random variable: the expectation of a nonnegative measurable function is its extended integral.

Fix a sample $S$ and a nonempty class $\mathcal{F}$ of predictors. Its empirical minimum is ${\widehat{R}}_S^{\ast }(\mathcal{F}):={\inf }_{f\in \mathcal{F}}{\widehat{R}}_S(f)\in [0,+\mathrm{\infty }]$. An exact empirical risk minimizer is a predictor $f\in \mathcal{F}$ with ${\widehat{R}}_S(f)={\widehat{R}}_S^{\ast }(\mathcal{F})$. If the infimum is finite but is not attained, no exact minimizer exists. If the infimum is $+\mathrm{\infty }$, nonemptiness implies that every member has infinite empirical risk and is an exact minimizer.

For finite $\eta \ge 0$, a predictor $f\in \mathcal{F}$ is an $\eta$-approximate empirical risk minimizer if either the empirical minimum is $+\mathrm{\infty }$ and $f$ is an exact minimizer, or the empirical minimum is finite and $f$ has finite empirical risk at most ${\widehat{R}}_S^{\ast }(\mathcal{F})+\eta$. The membership requirement $f\in \mathcal{F}$ applies in both branches. Thus the definition never forms $+\mathrm{\infty }+\eta$. When $\eta =0$ and the finite infimum is not attained, no such predictor exists.

For a fixed sample size $m$, a measurable prediction rule with class $\mathcal{F}$ is a jointly measurable evaluation map from the sample space $((\mathsf{X}\times \mathsf{Y}{)}^m,({\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_Y{)}^{\otimes m})$ and a new instance in $\mathsf{X}$ to $\mathsf{A}$, whose slice at each sample belongs to $\mathcal{F}$. It is an exact or approximate ERM rule when every slice satisfies the corresponding samplewise definition above. This definition asserts no existence of a measurable selector for an arbitrary class.

Supervised prediction problems: fixes the measurable observation and predictor spaces.

Population and empirical risk: defines the samplewise empirical risk being minimized.

In a supervised prediction problem, for every measurable predictor $f$, the function $(x,y)\mapsto \mathrm{\ell }(f(x),y)$ is measurable, so its population risk is a defined extended nonnegative integral. For every sample size $m\ge 1$, the empirical risk $S\mapsto {\widehat{R}}_S(f)$ is an extended nonnegative measurable function on the finite product sample space.

Assume the Axiom of Choice. Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$ and $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$ be standard Borel spaces, let $(\mathsf{A},{\mathrm{\Sigma }}_A)$ be a measurable action space, and let $P$ be a probability measure on $\mathsf{X}\times \mathsf{Y}$. Write $P_X$ and $P_Y$ for its coordinate marginals. There are regular conditional probability kernels $Q(y,dx)$ for $X$ given $Y$ and $K(x,dy)$ for $Y$ given $X$, with $P(C\times D)={\int }_{D}Q(y,C)P_Y(dy)={\int }_{C}K(x,D)P_X(dx)(C\in {\mathrm{\Sigma }}_X,D\in {\mathrm{\Sigma }}_Y)\mathrm{.}$ Let $\mathrm{\ell }:\mathsf{A}\times \mathsf{Y}\to [0,+\mathrm{\infty }]$ be measurable with respect to ${\mathrm{\Sigma }}_A\otimes {\mathrm{\Sigma }}_Y$ and define $q(x,a):={\int }_{\mathsf{Y}}\mathrm{\ell }(a,y)K(x,dy)$. If a measurable predictor $f^{\ast }:\mathsf{X}\to \mathsf{A}$ has a measurable set $E\in {\mathrm{\Sigma }}_X$ with $P_X(E)=1$ such that $q(x,f^{\ast }(x))\le q(x,a)$ for every $x\in E$ and every $a\in \mathsf{A}$, then $R_P(f^{\ast })\le R_P(g)$ for every measurable predictor $g:\mathsf{X}\to \mathsf{A}$. All risks may be $+\mathrm{\infty }$.

Standard Borel spaces: a standard Borel space is measurably isomorphic to a Polish space.

Regular conditional distribution: a regular conditional distribution is an everywhere probability kernel satisfying the conditional-event integral identities.

The product sigma-algebra and its finite iterates: product sigma-algebras are generated by measurable rectangles.

The Axiom of Choice: AC asserts that every family of nonempty sets has a choice function.

Assume the Axiom of Choice. Let $(\mathsf{X},{\mathrm{\Sigma }}_X)$ be a nonempty measurable space, let $(\mathsf{Y},{\mathrm{\Sigma }}_Y)$ be a nonempty standard Borel space, and let $P$ be a probability measure on $(\mathsf{X}\times \mathsf{Y},{\mathrm{\Sigma }}_X\otimes {\mathrm{\Sigma }}_Y)$. Put $P_X(C)=P(C\times \mathsf{Y})$. There exists an everywhere probability kernel $K:(\mathsf{X},{\mathrm{\Sigma }}_X)\to (\mathsf{Y},{\mathrm{\Sigma }}_Y)$ such that

$P(C\times A)={\int }_{C}K(x,A)P_X(dx)(C\in {\mathrm{\Sigma }}_X,A\in {\mathrm{\Sigma }}_Y)\mathrm{.}$

No standard-Borel, countable-generation, or completeness hypothesis is imposed on the instance space.

The Axiom of Choice

Standard Borel spaces

Measure kernel and probability kernel

Existence of regular conditional distributions for standard borel targets

Kallenberg, Foundations of Modern Probability, 2nd ed., Theorem 6.3

Let $\mathcal{M}$ be the class of all measurable predictors from $\mathsf{X}$ to $\mathsf{A}$. The class Bayes risk is $R_P^{\ast }(\mathcal{F}):={\inf }_{f\in \mathcal{F}}{R}_P(f)$, and the unrestricted Bayes risk is $R_P^{\ast }:={\inf }_{g\in \mathcal{M}}{R}_P(g)$. A class Bayes predictor is a member of $\mathcal{F}$ attaining the first infimum; an unrestricted Bayes predictor, also called a Bayes predictor, is a member of $\mathcal{M}$ attaining the second. No attainment is asserted. If an infimum is $+\mathrm{\infty }$, every member of its nonempty class has infinite risk and attains that extended infimum, but no finite excess risk results.

For $f\in \mathcal{F}$ with both terms finite, its class excess risk is $R_P(f)-R_P^{\ast }(\mathcal{F})$. For a measurable predictor $g\in \mathcal{M}$ with both terms finite, its unrestricted excess risk is $R_P(g)-R_P^{\ast }$. These differences are left undefined if either risk is infinite.

Write $P_X(C):=P(C\times \mathsf{Y})$ for the instance marginal. If a regular conditional label law $K(x,dy)$ given $x$ is supplied, its conditional risk is $q(x,a):={\int }_{\mathsf{Y}}\mathrm{\ell }(a,y)K(x,dy)$. This function is measurable when the loss is product-measurable. A conditional Bayes rule is a measurable predictor that attains ${\inf }_{a\in \mathsf{A}}q(x,a)$ on one measurable set of full $P_X$-measure. Such a kernel exists under AC whenever the label space is standard Borel, even if the instance space is an arbitrary measurable space; if the label space is an arbitrary measurable space, no conditional law or measurable minimizer is asserted. When both instance and label spaces are standard Borel and AC holds, the conditional Bayes theorem shows that any such rule is an unrestricted Bayes predictor.

Supervised prediction problems: fixes the measurable instance, label and action spaces, joint law, predictor class and loss.

Population and empirical risk: defines $R_P(f)$ as the extended nonnegative population risk.

Standard Borel spaces: a standard Borel space is measurably isomorphic to a Polish space.

Regular conditional distribution: a regular conditional distribution is an everywhere probability kernel satisfying the conditional-event integral identities.

The Axiom of Choice: AC asserts that every family of nonempty sets has a choice function.

A standard-Borel label has a conditional kernel over an arbitrary measurable instance space: under AC, a joint law with standard Borel label space admits an everywhere label-given-instance probability kernel even for an arbitrary measurable instance space.

Measurability of integration against a kernel: integration of a nonnegative product-measurable function against a probability kernel is measurable.

A conditional Bayes rule minimizes population risk: under standard-Borel and AC hypotheses, a measurable conditional minimizer is globally risk-minimizing.

Kallenberg, Foundations of Modern Probability, 2nd ed., Theorem 6.3: a Borel target admits a conditional-distribution kernel from any measurable conditioning space.

Given a sample $S$ of length $m\ge 1$, an ordered finite nonempty list of measurable predictors $(f_1,\dots ,f_n)$, and a finite tolerance $\eta \ge 0$, compute $r_j:={\widehat{R}}_S(f_j)$ for each $j\in \{1,\dots ,n\}$. If every $r_j=+\mathrm{\infty }$, return index $1$. Otherwise set $r_{\ast }:={\min }_{1\le j\le n}{r}_j$ and return the least index $j$ for which $r_j<+\mathrm{\infty }$ and $r_j\le r_{\ast }+\eta$. The output index denotes the selected predictor from the supplied list. When $\eta =0$, the output is a first exact minimizer, including the all-infinite case. The algorithm evaluates only a finite number of empirical risks and makes no population-risk guarantee.

Supervised prediction problems: fixes the measurable observation and predictor spaces.

Population and empirical risk: defines each empirical risk evaluated by the procedure.

Empirical risk minimizers: defines exact and approximate ERM, including the all-infinite branch.

Population and empirical risks are measurable: the sample objective for each listed predictor is measurable.

Fix a positive sample size $m$, a nonempty predictor class $\mathcal{F}$, and a finite tolerance $\eta \ge 0$. The input includes a supplied jointly measurable evaluation map $A_{\eta }:(\mathsf{X}\times \mathsf{Y}{)}^m\times \mathsf{X}\to \mathsf{A}$ such that every sample slice $A_{\eta }(S,\cdot )$ belongs to $\mathcal{F}$. For each sample $S$, require that the slice is an exact empirical risk minimizer if ${\widehat{R}}_S^{\ast }(\mathcal{F})=+\mathrm{\infty }$, and otherwise has finite empirical risk at most ${\widehat{R}}_S^{\ast }(\mathcal{F})+\eta$. The procedure returns the predictor $A_{\eta }(S,\cdot )$ on input $S$. Its selector is an explicit input; this procedure asserts no existence or construction of such a selector for an arbitrary class. In particular, $\eta =0$ requires attainment whenever the empirical minimum is finite.

Supervised prediction problems: fixes the measurable sample and predictor spaces.

Population and empirical risk: defines the sample objective.

Empirical risk minimizers: defines exact and approximate ERM without forming $+\mathrm{\infty }+\eta$.

Population and empirical risks are measurable: establishes measurability of the sample objective for a fixed predictor.

For a sample of positive length, a finite ordered nonempty list of measurable predictors, and finite tolerance $\eta \ge 0$, let $J(S)$ be the index returned by the finite-list empirical-risk algorithm. Then $J$ is measurable into the finite index set with its discrete sigma-algebra, the evaluation map $(S,x)\mapsto f_{J(S)}(x)$ is jointly measurable, and the returned predictor is an $\eta$-approximate empirical risk minimizer as defined in the algorithm's input conditions. When $\eta =0$, it is an exact minimizer.