Training Sequences and Hypothesis Selection

A learning rule A can receive a training sequence S containing m examples even when its returned hypothesis is determined by only k of those examples. Theorem 30.2 studies this situation by separating the examples that determine the hypothesis from the examples that do not. This separation lets the proof analyze how a small defining subset relates to the rest of the training sequence.

The mapping B is the bridge between the selected examples and the hypothesis. For a selected index choice I, the proof writes the associated hypothesis as h_I = B(z_i1, ..., z_ik). The important structural point is that the hypothesis is tied to the k examples identified by the indices in I, rather than being described only as a function of the entire sequence.

Once k examples have been identified as the examples used by B, the remaining examples are collected in V. Thus, V represents the unselected part of the training sequence. The theorem gives this unselected set a central role because the proof does not study only the examples that define the hypothesis; it also tracks what remains after that selection.

The proof does not begin by fixing one particular selection of k examples. Instead, for every index choice I in [m]^k, it defines h_I = B(z_i1, ..., z_ik). Each possible index choice therefore creates a corresponding hypothesis expression that the proof may need to control.

This enumeration is necessary because the proof must account for the combinatorial number of possible selections. A statement established for one index choice is not automatically a statement about every choice. The union bound supplies the step that combines the probability statements for the separate choices.

The proof introduces δ′ by multiplying the per-index-choice parameter δ by the number of possible k-example selections, written as (m choose k). After the union-bound step, the proof obtains a probability statement of at least 1 − δ′. The multiplication records the cost of controlling all the index choices together rather than just one choice.

The proof includes the requirement m ≥ 2k as part of the probability-bound derivation. In terms of the sequence split, the selected part contains k examples and the unselected part contains the remaining m − k examples. The condition identifies the regime in which the proof carries out its bound using the relationship between these two parts.

The central lesson is structural. A hypothesis determined by a small subset of a training sequence can be analyzed by separating the defining examples from the unselected examples, considering every relevant index choice, and controlling those choices with a union bound. The factor (m choose k) explains why the proof changes δ to δ′.