Training Sequences and Hypothesis Selection

One Sequence, Two Roles

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.

Tracing the Unselected Set

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.

Why Every Index Choice Matters

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.

From δ to δ′

δ′ = (m choose k) × δ

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 Size Condition m ≥ 2k

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.

Mistakes in Reading the Proof

• Treating the hypothesis as determined by all m examples simply because A receives m examples.

  Theorem 30.2 specifically studies the case in which the returned hypothesis is determined by only k of the m examples.

  Fix: Separate the k examples used by B from the remaining examples collected in V.

• Ignoring V after identifying the selected examples.

  The unselected examples form V, which is central to the theorem's stated condition and the proof's separation of the sequence.

  Fix: Track both the selected examples and the unselected set V.

• Applying δ only once without accounting for possible index choices.

  The proof defines h_I for possible index choices and combines the corresponding probability statements with a union bound.

  Fix: Use δ′ = (m choose k) × δ for the parameter after this bookkeeping step.

• Claiming that the numerical δ′ calculation proves the theorem's performance condition.

  The calculation evaluates only the probability parameter after the union-bound step; it does not supply the omitted performance condition.

  Fix: State precisely what has been calculated: the probability parameter and the associated level 1 − δ′.

Proof Structure at a Glance

1. Start with a training sequence S containing m examples.
2. Identify k examples whose indices determine the hypothesis through B.
3. Collect the remaining m − k examples in V.
4. For every possible index choice I, define h_I = B(z_i1, ..., z_ik).
5. Use a union bound to combine the probability statements for the possible choices.
6. Replace δ with δ′ = (m choose k) × δ, yielding a stated probability of at least 1 − δ′.
7. Use the requirement m ≥ 2k as part of the probability-bound derivation.

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 δ′.