Randomized Learning Rules and Auxiliary Randomness

Why Add Randomness to a Learning Rule?

A learning procedure need not return the same prediction every time it sees the same training data. It may break ties at random, sample a model from a distribution, or deliberately randomize its predictions. To describe such a procedure, we must distinguish two sources of variation: the training data may change across samples, and the algorithm may use randomness even when the data are held fixed.

The distinction is easiest to formalize by introducing an auxiliary random variable \(U\). The observed dataset is denoted by \(D\), and the prediction input by \(x\). A randomized rule is then a function of all three: \(D\), \(U\), and \(x\). If \(U\) is held fixed, the rule is an ordinary prediction function of \(x\) for each fixed dataset.

For a precise setup, let \((\mathcal Z,\mathcal A)\) be the measurable space of one training observation, and let the dataset space be \(\mathcal D=\mathcal Z^n\) with its product sigma-algebra. Let \((\mathcal X,\mathcal B)\) be the feature space and \(\mathcal Y\) the prediction space. A randomized rule can be represented by a measurable map \(H:\mathcal D\times\mathcal U\times\mathcal X\to\mathcal Y\), where \((\mathcal U,\mathcal C)\) is the auxiliary-randomness space.

The joint measurability of \(H\) matters: it ensures that the output is a measurable function of the random inputs when \(D\), \(U\), or the query \(x\) varies. For every fixed \(d\in\mathcal D\) and \(u\in\mathcal U\), the section \(x\mapsto H(d,u,x)\) is measurable. Thus fixing the data and the random seed produces a valid prediction function.

Two Sources of Random Variation

In the usual sampling model, \(D\) is random because it is generated from the data distribution. The auxiliary variable \(U\) is introduced to represent the algorithm's own random choices. A common model takes \(U\) to be uniform on \([0,1)\) and independent of \(D\). Independence expresses the idea that, before the algorithm uses its random seed, that seed does not reveal information about the training sample.

This separation is a modeling choice, not a claim that every computer implementation literally draws a fresh independent number at every prediction. A pseudorandom seed can be represented abstractly by \(U\). If a procedure's random choices depend on the data, those choices can still be modeled by a map \(H(D,U,x)\); independence of the seed does not mean the resulting prediction is independent of \(D\).

A non-randomized learning rule is the special case in which \(H\) does not depend on \(U\). In a randomized rule, even with \(D=d\) fixed, varying \(U\) can change the prediction. Conversely, with \(U=u\) fixed, varying \(D\) can change it because the fitted procedure responds to the data.

Measurable Probabilities for Finite Predictions

A particularly transparent case is a classifier with finitely many possible outputs, \(\mathcal Y=\{1,\ldots,K\}\). For each class \(j\), specify the probability of predicting that class as a function \(q_j(d,x)\) of the dataset and input. These probabilities must be measurable and must form a probability vector at every \((d,x)\).

These probabilities can be implemented with one uniform auxiliary variable. Define the cumulative probabilities \(C_0(d,x)=0\) and \(C_j(d,x)=\sum_{r=1}^j q_r(d,x)\) for \(j=1,\ldots,K\). Since the probabilities sum to one, \(C_K(d,x)=1\). For \(u\in[0,1)\), choose the unique index \(j\) for which \(C_{j-1}(d,x)\leq u<C_j(d,x)\). If \(q_j(d,x)=0\), this interval is empty, so that class is never selected.

Proof of measurability. Each cumulative function \(C_j\) is measurable because it is a finite sum of measurable functions. The set on which the output equals \(j\) is \(\{(d,u,x):C_{j-1}(d,x)\leq u<C_j(d,x)\}\). The map \((d,u,x)\mapsto(C_{j-1}(d,x),u,C_j(d,x))\) is measurable, and the subset of triples \((a,u,b)\) satisfying \(a\leq u<b\) is Borel. Therefore each output set is measurable. Since the output space is finite, measurability of all these sets proves measurability of \(H\).

Proof of the probability statement. Fix \(d,x\). The values of \(u\) that produce class \(j\) form the interval \([C_{j-1}(d,x),C_j(d,x))\), whose length is \(C_j(d,x)-C_{j-1}(d,x)=q_j(d,x)\). A uniform random variable assigns an interval its length, so \(P(H(d,U,x)=j)=q_j(d,x)\). This proves both claims. \(\square\)

Separating Sampling Variability From Algorithmic Variability

The distinction can be quantified in a small example. Suppose \(D=(X_1,X_2)\), where \(X_1,X_2\) are independent Bernoulli random variables with success probability \(1/2\). The algorithm predicts class 1 with probability \(q(D)=0.2\) if both observations are zero, and with probability \(q(D)=0.8\) otherwise. Let \(A\) be the indicator that the randomized algorithm predicts class 1.

More generally, if \(D\) and a query \(X\) are random and \(U\) is independent of the pair \((D,X)\), the finite-class construction satisfies \(P(H(D,U,X)=j\mid D,X)=q_j(D,X)\) almost surely. One way to verify the statement is to multiply the indicator of the event \(H=j\) by any bounded measurable function \(g(D,X)\), then integrate first over the independent uniform variable \(U\). The interval calculation gives \(E[g(D,X)\mathbf 1\{H=j\}]=E[g(D,X)q_j(D,X)]\), which is the defining property of this conditional probability.

One Seed, Many Inputs

A rule \(H(d,u,x)\) may use the same value of \(u\) when evaluated at several inputs. In that case the predictions at those inputs can be dependent, even though each individual prediction has the specified class probabilities. For example, a shared uniform variable can place all inputs on the same side of a random threshold. If separate, independent randomization is intended for each prediction, the model must include separate auxiliary variables or an auxiliary random object that supplies them.

This distinction is important whenever the question concerns a collection of predictions rather than just the distribution at one input. The marginal probabilities \(q_j(d,x)\) specify the random output at each fixed input, but by themselves they do not specify how outputs at different inputs are jointly randomized.

Common Mistake

A common mistake is to say, “The prediction is random, so the dataset must be random too,” or to combine both sources into one vague notion of randomness. That loses the useful distinction between changing the sample and changing the algorithm's seed. The correction is to write the rule explicitly as \(H(D,U,x)\), state which variables are random, and specify their dependence. In the standard auxiliary-randomness setup, \(D\) is random under the sampling model and \(U\) is an additional random variable independent of \(D\).

A second related mistake is to specify class probabilities without checking measurability. Pointwise probabilities alone do not establish that the output is a valid measurable function of the data, seed, and input. In the finite-class construction, measurable probability functions give measurable cumulative cutpoints, and the interval events defining each output are measurable; this verifies the needed property rather than assuming it.