Measurability of Data-Dependent Prediction Rules

From a Dataset to a Prediction

A prediction rule fitted from data is not a single fixed function: the observed dataset determines which predictor is used. To treat the resulting prediction as a random quantity, it must be possible to evaluate the fitted predictor measurably as the dataset and the feature vary together. This condition is what allows later probability statements about data-dependent predictions to be well defined.

The central object is therefore not merely a collection of measurable predictors, one for each possible dataset. It is a map that takes a dataset and a feature as inputs and returns a prediction. The measurable structure on the dataset space matters: continuity or measurability of a fitting calculation can only be assessed relative to a specified sigma-algebra.

Definition: Let $(\mathcal X,\mathcal B)$ be a feature space and $(\mathcal Y,\mathcal C)$ a prediction space. Let the observation space be $\mathcal Z=\mathcal X\times\mathcal Y$, equipped with the product sigma-algebra $\mathcal A=\mathcal B\otimes\mathcal C$. For a fixed sample size $n$, equip the dataset space $\mathcal Z^n$ with $\mathcal A^{\otimes n}$. A deterministic learning rule is a map $A$ assigning a predictor $A(d):\mathcal X\to\mathcal Y$ to each dataset $d\in\mathcal Z^n$. Its evaluation map is $$ T:\mathcal Z^n\times\mathcal X\to\mathcal Y,\qquad T(d,x)=A(d)(x). $$ The learning rule has jointly measurable predictions if $T$ is measurable from $\mathcal A^{\otimes n}\otimes\mathcal B$ to $\mathcal C$.

The product sigma-algebra specification is substantive. With $\mathcal A=\mathcal B\otimes\mathcal C$, the coordinate maps extracting each observed feature and response are measurable. The same conclusion need not hold if an arbitrary, smaller sigma-algebra is placed on $\mathcal Z$. In particular, a formula that is continuous in the numerical coordinates is not automatically measurable from an unspecified observation sigma-algebra.

The definition focuses on the evaluation map rather than requiring a particular sigma-algebra on a space of functions. Such a function-space sigma-algebra is not needed to state the basic requirement: for every dataset and feature, the fitted prediction is specified, and the map taking both inputs to that prediction is measurable. For each fixed dataset $d$, the section $x\mapsto T(d,x)$ should be a measurable prediction function, but that fact alone does not ensure joint measurability.

A Sufficient Condition: Measurable Parameterization

Many procedures fit a finite-dimensional parameter and then use that parameter to produce predictions. This structure gives a convenient sufficient condition. Let $(\Theta,\mathcal G)$ be a measurable parameter space, let $a:\mathcal Z^n\to\Theta$ be the fitting map, and let $\phi:\Theta\times\mathcal X\to\mathcal Y$ be the prediction map. The rule predicts $T(d,x)=\phi(a(d),x)$.

Theorem: Suppose $a$ is measurable from $(\mathcal Z^n,\mathcal A^{\otimes n})$ to $(\Theta,\mathcal G)$, and $\phi$ is measurable from $(\Theta\times\mathcal X,\mathcal G\otimes\mathcal B)$ to $(\mathcal Y,\mathcal C)$. Then $T(d,x)=\phi(a(d),x)$ is jointly measurable from $(\mathcal Z^n\times\mathcal X,\mathcal A^{\otimes n}\otimes\mathcal B)$ to $(\mathcal Y,\mathcal C)$.

Proof. Define $h:\mathcal Z^n\times\mathcal X\to\Theta\times\mathcal X$ by $h(d,x)=(a(d),x)$. For a measurable rectangle $G\times B$, where $G\in\mathcal G$ and $B\in\mathcal B$, $$ h^{-1}(G\times B)=a^{-1}(G)\times B. $$ This set belongs to $\mathcal A^{\otimes n}\otimes\mathcal B$ because $a$ is measurable. Measurable rectangles generate $\mathcal G\otimes\mathcal B$, so $h$ is measurable. Since $T=\phi\circ h$ and $\phi$ is measurable, the composition $T$ is measurable. $\square$

This theorem separates two checks: whether the data-fitting step $a$ is measurable, and whether the parameterized prediction map $\phi$ is measurable. It is a sufficient condition, not the only possible way to establish measurability. Directly checking the evaluation map is also valid.

Worked Example: Selecting From a Finite Predictor Class

Let the predictor class be $f_1,\ldots,f_m$, where each $f_j:\mathcal X\to\mathcal Y$ is measurable. Suppose the score $s_j(d)$ assigned to predictor $f_j$ is a measurable real-valued function of the dataset. The procedure selects a predictor with the smallest score, breaking ties in favor of the lowest index. Verify that its evaluation map is jointly measurable.

For each $j$, the event that $j$ is selected is $$ E_j= \left(\bigcap_{k<j}\{d:s_j(d)<s_k(d)\}\right) \cap \left(\bigcap_{k>j}\{d:s_j(d)\leq s_k(d)\}\right). $$ For $j=1$, the first intersection is the whole dataset space; for $j=m$, the second is the whole space. Each comparison set is measurable because $s_j$ and $s_k$ are measurable real-valued functions and the sets $\{(u,v):u<v\}$ and $\{(u,v):u\leq v\}$ are Borel in $\mathbb R^2$. Thus every $E_j$ is measurable. The sets partition the dataset space, and the selected evaluation map is $T(d,x)=f_j(x)$ when $d\in E_j$.

For any $C\in\mathcal C$, $$ T^{-1}(C)=\bigcup_{j=1}^m \left(E_j\times f_j^{-1}(C)\right). $$ Each term is measurable in $\mathcal A^{\otimes n}\otimes\mathcal B$, and the union is finite. Hence $T$ is jointly measurable. In particular, minimizing a finite list of measurable scores and using a fixed measurable predictor for each choice gives a measurable data-dependent prediction rule.

Worked Numerical Examples

Worked Example: Ridge Regression With Borel Features

Take $\mathcal X=\mathbb R^q$ and $\mathcal Y=\mathbb R$, both with their Borel sigma-algebras. Thus $\mathcal Z=\mathbb R^q\times\mathbb R$ has its Borel product sigma-algebra, and the dataset space has the corresponding $n$-fold product sigma-algebra. Let $\psi:\mathbb R^q\to\mathbb R^p$ be a Borel measurable feature map, and fix $\lambda>0$. The ridge coefficient fitted from $d=((x_1,y_1),\ldots,(x_n,y_n))$ is $$ \hat\beta(d)=\left(\sum_{i=1}^n\psi(x_i)\psi(x_i)^\mathsf{T}+\lambda I_p\right)^{-1} \sum_{i=1}^n\psi(x_i)y_i. $$

Each coordinate $x_i,y_i$ is a measurable projection from the product dataset space. Therefore $\psi(x_i)$, the entries of $\psi(x_i)\psi(x_i)^\mathsf{T}$, and the entries of $\psi(x_i)y_i$ are measurable functions of the dataset. Finite sums preserve measurability. The matrix $$ M(d)=\sum_{i=1}^n\psi(x_i)\psi(x_i)^\mathsf{T}+\lambda I_p $$ is invertible for every dataset: for every nonzero $v\in\mathbb R^p$, $$ v^\mathsf{T}M(d)v=\sum_{i=1}^n\left(v^\mathsf{T}\psi(x_i)\right)^2+\lambda\|v\|^2>0. $$

Matrix inversion is continuous on the open set of invertible matrices. Since $M(d)$ is always in that set and its entries are measurable, $M(d)^{-1}$ has measurable entries. Consequently $\hat\beta(d)$ is a measurable map into $\mathbb R^p$. The prediction map $\phi(\beta,x)=\beta^\mathsf{T}\psi(x)$ is measurable in $(\beta,x)$: it is a finite sum of products of measurable coordinates. The theorem therefore gives joint measurability of $$ T(d,x)=\hat\beta(d)^\mathsf{T}\psi(x). $$ The Borel product structure on the data is essential to this argument; without it, measurability of the coordinate responses and features cannot simply be presumed.

Worked Example: A Threshold at the Sample Mean

Let $X_i\in\mathbb R$ be the observed features in a dataset and define $\bar X(d)=n^{-1}\sum_{i=1}^n X_i$. Consider the binary prediction rule $$ T(d,x)=\mathbf 1\{x\geq \bar X(d)\}. $$ Assume real-valued features have their Borel sigma-algebra, and use the product sigma-algebra on the dataset. Each coordinate projection is measurable, so the finite sum $\bar X$ is measurable. On the product of the dataset space and $\mathbb R$, the map $(d,x)\mapsto x-\bar X(d)$ is measurable, since subtraction is a continuous function on $\mathbb R^2$.

The set on which the prediction is $1$ is $$ \{(d,x):x-\bar X(d)\geq 0\}, $$ the inverse image of the closed Borel set $[0,\infty)$ under a measurable map. It is therefore measurable. The prediction takes only the values $0$ and $1$, so the inverse image of any Borel subset of $\mathbb R$ is either this set, its complement, the whole space, or the empty set. Thus $T$ is jointly measurable.

For example, with observed features $1,2,3$, the fitted threshold is $\bar X=2$, and the prediction at $x=2.5$ is $1$, while the prediction at $x=1.5$ is $0$. The calculation gives the rule's output for this dataset; the measurability argument establishes that the same rule is well-defined measurably across all datasets and query features.

Why Joint Measurability Matters

Suppose a dataset $D$ is a measurable random element of $\mathcal Z^n$, and $X_{\mathrm{new}}$ is a measurable random element of $\mathcal X$, defined on the same probability space. If $T$ is jointly measurable, then $$ \omega\longmapsto (D(\omega),X_{\mathrm{new}}(\omega)) $$ is measurable into the product space, and composing it with $T$ shows that $T(D,X_{\mathrm{new}})$ is a measurable random variable. Independence between $D$ and $X_{\mathrm{new}}$ is not required for this measurability conclusion. Independence may matter for later statistical calculations, but not for this step.

There is an important distinction between two statements: every fixed-dataset predictor $x\mapsto A(d)(x)$ is measurable, and the joint map $(d,x)\mapsto A(d)(x)$ is measurable. The first statement concerns each section separately; the second controls how predictions vary as the dataset changes. The section-wise condition alone is not sufficient.

Worked Example: Measurable Sections but No Measurable Learning Rule

Let the dataset space and feature space both be $\mathbb R$ with their Borel sigma-algebras. Choose a non-Borel set $N\subset\mathbb R$, and define $$ T(d,x)=\mathbf 1_N(d). $$ For every fixed dataset $d$, the function $x\mapsto T(d,x)$ is constant: it is either always $0$ or always $1$. Each such predictor is Borel measurable on the feature space.

However, $T^{-1}(\{1\})=N\times\mathbb R$, which is not in the product Borel sigma-algebra. Indeed, if $N\times\mathbb R$ were product-measurable, its section at any fixed $x$ would be Borel in $\mathbb R$, but that section is $N$. Thus $T$ is not jointly measurable. This assignment is not a measurable learning rule, despite assigning a measurable predictor to every dataset.

Common Mistake

Wrong reasoning: “For every fixed dataset, the fitted predictor is measurable in the feature, so the data-dependent prediction is measurable.” This confuses section-wise measurability with joint measurability; the non-Borel-set example shows why the implication fails.

Correction: Specify the sigma-algebras on the observation and dataset spaces, then establish measurability of the evaluation map in both inputs. A measurable parameter fit followed by a jointly measurable parameterized prediction map is a useful sufficient condition. For numerical formulas, verify that the data coordinates are measurable under the chosen dataset sigma-algebra before relying on continuity of the formula.

Key takeaway: A deterministic fitted prediction is a function of both the dataset and the query feature. Its joint measurability is ensured, for example, when a measurable fitting map feeds a jointly measurable prediction map. Individual measurability of each fixed-dataset predictor is not enough.

Check Your Understanding

Use the definitions and conditions above to answer the following.

What sigma-algebra is used on the dataset space when one observation has sigma-algebra $\mathcal A$ and the sample size is $n$?
State the two measurability conditions in the parameterization theorem and explain how they imply measurability of the evaluation map.
Why is the ridge matrix invertible for every dataset when $\lambda>0$?
Does joint measurability of a learning rule require the dataset and new feature to be independent? Explain.
Why does measurability of every fixed-dataset predictor not, by itself, establish joint measurability?