Measurable Prediction Functions

Why Measurability Matters for a Prediction Rule

A prediction rule assigns a response to each possible feature value. For example, a rule might map a patient's measured characteristics to a predicted outcome, or map an image to one of a finite set of labels. To use such a rule in probability, it must respect the measurable structure of the feature and response spaces. In particular, when the features are random, a measurable rule ensures that the predicted response is a random element whose events have well-defined probabilities.

Here we study a fixed, deterministic function from a feature space to a response space. The question is not whether the rule predicts accurately, but whether its inverse images of measurable response sets are measurable feature events. That condition is the basic mathematical requirement for a prediction function.

Definition: Let $(\mathcal X,\mathcal A)$ be a measurable feature space and $(\mathcal Y,\mathcal B)$ a measurable response space. A function $h:\mathcal X\to\mathcal Y$ is measurable if $$ h^{-1}(C)=\{x\in\mathcal X:h(x)\in C\}\in\mathcal A \quad\text{for every } C\in\mathcal B. $$ Such a function is called a measurable prediction function.

The inverse image $h^{-1}(C)$ is a set of feature values, not an inverse function: it collects every feature value whose prediction falls in $C$. Measurability asks whether each such set is an allowed event in the feature space. It is enough to check a collection of response sets that generates $\mathcal B$, provided the collection is a suitable generator, as the next result illustrates for real-valued predictions.

Real-Valued Predictions

For a real-valued response, the usual response space is $(\mathbb R,\mathcal B(\mathbb R))$, where $\mathcal B(\mathbb R)$ is the Borel sigma-algebra generated by open subsets of the real line. One convenient measurability test uses half-lines.

Theorem: A function $h:(\mathcal X,\mathcal A)\to(\mathbb R,\mathcal B(\mathbb R))$ is measurable if and only if $h^{-1}((-\infty,t])\in\mathcal A$ for every real $t$.

Proof. If $h$ is measurable, the condition follows because each $(-\infty,t]$ is Borel. Conversely, suppose all the indicated inverse images belong to $\mathcal A$. The family $\{(-\infty,t]:t\in\mathbb R\}$ generates $\mathcal B(\mathbb R)$. The collection of sets $C\subseteq\mathbb R$ for which $h^{-1}(C)\in\mathcal A$ is a sigma-algebra: inverse images preserve complements and countable unions. It contains the generating half-lines, so it contains the Borel sigma-algebra they generate. Thus $h^{-1}(C)\in\mathcal A$ for every Borel set $C$, which is precisely measurability. $\square$

This criterion is useful because prediction sets such as $\{x:h(x)\leq t\}$ are often easier to describe than the inverse image of an arbitrary Borel set. Equivalent generating tests can use open half-lines $(-\infty,t)$ instead; either convention works when used consistently.

Worked Example: A Linear Prediction on Euclidean Features

Let the feature space be $\mathbb R^2$ with its Borel sigma-algebra, and define the real-valued predictor $h(x_1,x_2)=0.5+2x_1-x_2$. Verify that $h$ is measurable.

For any real $t$, the inverse image of the half-line $(-\infty,t]$ is $$ \{(x_1,x_2):0.5+2x_1-x_2\leq t\} = \{(x_1,x_2):2x_1-x_2\leq t-0.5\}. $$ This is a closed half-space in $\mathbb R^2$, hence a Borel set. The half-line criterion therefore gives measurability of $h$.

For instance, the features $(1,0)$ produce the prediction $0.5+2(1)-0=2.5$, while $(0,1)$ produce $0.5+0-1=-0.5$. These values illustrate the rule; the half-space argument establishes measurability for every real threshold $t$.

More generally, if $h(x)=\beta_0+\sum_{j=1}^p\beta_jx_j$ on $\mathbb R^p$, with real coefficients, then $h$ is continuous in the usual Euclidean topology. Every continuous real-valued function on a topological space is Borel measurable: the inverse image of an open set is open, and therefore Borel. This familiar route is valid because the feature space has its usual Borel structure. If the feature space instead carries some other sigma-algebra, continuity alone does not establish measurability with respect to that sigma-algebra.

Result: Every affine function $h:\mathbb R^p\to\mathbb R$, $h(x)=\beta_0+\beta^\top x$, is measurable when $\mathbb R^p$ and $\mathbb R$ carry their Borel sigma-algebras.

Proof. For any $t\in\mathbb R$, the set $h^{-1}((-\infty,t])$ is $$ \left\{x\in\mathbb R^p:\sum_{j=1}^p\beta_jx_j\leq t-\beta_0\right\}. $$ The expression on the left of the inequality is a continuous linear function of $x$. Its inverse image of the closed set $(-\infty,t-\beta_0]$ is closed, hence Borel. The half-line criterion proves that $h$ is measurable. $\square$

Threshold Rules

A threshold rule assigns a label according to whether a real-valued score is above or below a cutoff. Give the finite label set $\{0,1\}$ its discrete sigma-algebra, which contains every subset. If the score $g:\mathcal X\to\mathbb R$ is measurable and $c\in\mathbb R$, the rule $h(x)=\mathbf 1\{g(x)>c\}$ is measurable. Its label-1 region is $g^{-1}((c,\infty))$, a measurable set because $(c,\infty)$ is Borel and $g$ is measurable; its label-0 region is the complement, also measurable. These two regions are all that must be checked for a binary response.

Worked Example: A Threshold Applied to a Linear Score

For $x=(x_1,x_2)\in\mathbb R^2$, define $g(x)=2x_1-x_2$, and predict label 1 when $g(x)>1$, label 0 otherwise. Check the rule and classify two feature values.

The region for label 1 is $$ \{x:2x_1-x_2>1\}, $$ an open half-space, so it is Borel. The region for label 0 is its complement $\{x:2x_1-x_2\leq1\}$, which is also Borel. Since every subset of $\{0,1\}$ is measurable, these preimages establish that the classifier is measurable.

At $x=(1,0)$, the score is $2(1)-0=2>1$, so the prediction is 1. At $x=(0,0)$, the score is $0$, which is not greater than 1, so the prediction is 0. The strict inequality also specifies exactly how the boundary is handled: points satisfying $2x_1-x_2=1$ receive label 0.

The same argument works for a threshold on any measurable real-valued score, not just a linear score. For the rule $h(x)=\mathbf 1\{g(x)\geq c\}$, the positive region is $g^{-1}([c,\infty))$, again measurable. The choice between $>$ and $\geq$ changes the boundary assignment, but not the measurability argument.

Classifiers With Finitely Many Labels

Suppose the response space is a finite set $\mathcal Y=\{y_1,\ldots,y_K\}$ equipped with its discrete sigma-algebra. A classifier is measurable exactly when each label's decision region is measurable. This gives a direct way to verify finite-label rules without checking every subset of labels separately.

Theorem: Let $\mathcal Y=\{y_1,\ldots,y_K\}$ have the discrete sigma-algebra. A function $h:\mathcal X\to\mathcal Y$ is measurable if and only if each fiber $h^{-1}(\{y_k\})$ belongs to $\mathcal A$, for $k=1,\ldots,K$.

Proof. If $h$ is measurable, each singleton $\{y_k\}$ is measurable in the discrete sigma-algebra, so its inverse image is in $\mathcal A$. Conversely, assume every fiber is in $\mathcal A$. Any subset $C\subseteq\mathcal Y$ is a finite union of singletons, and $$ h^{-1}(C)=\bigcup_{y_k\in C}h^{-1}(\{y_k\}). $$ A finite union of sets in $\mathcal A$ belongs to $\mathcal A$. Thus every measurable response set has a measurable inverse image, and $h$ is measurable. $\square$

Worked Example: A Three-Label Classifier With Decision Regions

Let $\mathcal X=\mathbb R^2$, with its Borel sigma-algebra, and $\mathcal Y=\{A,B,C\}$, with its discrete sigma-algebra. Define a classifier by the following ordered rule: predict $A$ if $x_1<0$; otherwise predict $B$ if $x_2\geq0$; otherwise predict $C$. Find its three fibers and verify measurability.

The $A$ region is $$ h^{-1}(\{A\})=\{(x_1,x_2):x_1<0\}, $$ which is an open half-space. The $B$ region includes only points not already assigned to $A$, so $$ h^{-1}(\{B\})=\{(x_1,x_2):x_1\geq0,\ x_2\geq0\}. $$ This is an intersection of two closed half-spaces and is Borel. The remaining points have $x_1\geq0$ and $x_2<0$, giving $$ h^{-1}(\{C\})=\{(x_1,x_2):x_1\geq0,\ x_2<0\}. $$ This is also Borel. All three fibers are Borel, so the finite-label theorem proves that the classifier is measurable.

For example, $(-1,4)$ is assigned $A$, because its first coordinate is negative. The point $(2,0)$ is assigned $B$, because it was not assigned $A$ and its second coordinate is nonnegative. The point $(2,-1)$ is assigned $C$. The ordered definition makes the regions disjoint and covers the whole feature space.

Composition and the Probability Interpretation

Measurability is what allows a fixed prediction function to act on a random feature. If $X$ is a random element taking values in $\mathcal X$, then $h(X)$ is a random element in $\mathcal Y$ whenever $h$ is measurable. The reason is the composition rule below.

Proposition: If $X$ is a measurable map from a probability space $(\Omega,\mathcal F,P)$ to $(\mathcal X,\mathcal A)$, and $h:(\mathcal X,\mathcal A)\to(\mathcal Y,\mathcal B)$ is measurable, then $h\circ X:\Omega\to\mathcal Y$ is measurable.

Proof. For any $C\in\mathcal B$, the event that the composed prediction lies in $C$ is $$ (h\circ X)^{-1}(C)=X^{-1}(h^{-1}(C)). $$ Since $h$ is measurable, $h^{-1}(C)\in\mathcal A$. Since $X$ is measurable, the inverse image under $X$ of every set in $\mathcal A$ belongs to $\mathcal F$. Therefore $(h\circ X)^{-1}(C)\in\mathcal F$ for every $C\in\mathcal B$, proving measurability. $\square$

This statement concerns a fixed function $h$. A rule selected using observed data raises an additional measurability question because the rule itself then varies with the data. That is a distinct issue. Here the central check remains the same: identify measurable response sets and show that the prediction rule's inverse images are measurable feature sets.

Common Pitfall

A common mistake is to assume that a formula that looks ordinary, such as a linear expression or a threshold, is measurable under any possible sigma-algebras. The formula alone is not enough; measurability is defined relative to the sigma-algebras on both spaces. For example, let $\mathbb R$ have the trivial sigma-algebra $\{\varnothing,\mathbb R\}$ as its feature sigma-algebra, and the usual Borel sigma-algebra as its response sigma-algebra. The identity function $h(x)=x$ is continuous in the usual topology, but it is not measurable for these specified sigma-algebras: $h^{-1}((-\infty,0))=(-\infty,0)$, which is not in the trivial sigma-algebra.

The correction is to state the measurable structures before invoking a standard fact. Affine functions are Borel measurable on Euclidean spaces with their Borel sigma-algebras; threshold regions are measurable when their scores are measurable; and finite-label classifiers are measurable when their label fibers are measurable. These checks establish that the rule can be used as a random prediction, without making any claim about its predictive quality.

Key takeaway: A prediction function is measurable when every measurable response set has a measurable inverse image in feature space. For real-valued rules, test half-lines; for finite-label rules, test each label fiber.

Check Your Understanding

Use the stated sigma-algebras in each question.

State the definition of a measurable prediction function $h:\mathcal X\to\mathcal Y$ using inverse images.
Why is checking $h^{-1}((-\infty,t])$ for every real $t$ enough to establish measurability of a real-valued function?
For a measurable score $g$, explain why the rule that predicts 1 when $g(x)\geq c$ is measurable.
What sets must be checked to establish measurability of a classifier with a finite discrete label space?
Give the key reason that an affine function on Euclidean space is Borel measurable, and state which sigma-algebras this claim uses.