Linear Combinations of Base Hypotheses

A learning method may build one final hypothesis by combining several simpler hypotheses. The combined class can be more expressive than the original base class, so analyzing only one base hypothesis does not reveal the full capacity of the method. The relevant question is how many different binary labelings the combined class can produce on a finite set of examples. VC-dimension measures this capacity through shattering and the number of realizable dichotomies.

The class L(B,T) is formed in two stages. First, select T hypotheses h1 through hT from the base class B. For an input x, these hypotheses produce a T-dimensional vector of values: h1(x) through hT(x). Second, apply a halfspace hypothesis, also called a linear predictor in the proof, to that vector. The final prediction therefore depends on both the selected base hypotheses and the rule that combines their outputs.

To bound the VC-dimension of L(B,T), begin with a finite set C containing m points that is assumed to be shattered by L(B,T). The first counting stage ignores the final linear predictor and asks how many different binary labelings the base class B can create on C. These labelings are called dichotomies. Two hypotheses that agree on every point in C contribute the same dichotomy, so they can be treated as one pattern for this count.

Let d denote VCdim(B). Sauer's Lemma bounds the number of distinct dichotomies that B can induce on C by at most (em/d) raised to the power d. The important role of this result is that it counts observable patterns on C rather than individual hypotheses in B. Even if many hypotheses exist, hypotheses with the same labeling on C do not create additional possibilities for the current counting argument.

The second counting stage fills each of the T positions with one available base-class pattern. If one position has at most (em/d) raised to the power d possible patterns, then all T positions have at most (em/d) raised to the power dT possible pattern selections. This accounts for the choices of the T base hypotheses as they appear on C.

After the T base patterns have been selected, the final linear predictor receives T-dimensional output vectors. The proof states that this predictor can produce at most (em/T) raised to the power T dichotomies on those vectors. The full count therefore combines the number of T-pattern selections with the number of labelings available from the final predictor.

The proof begins by assuming that C is shattered by L(B,T). Shattering a set of m points requires the class to realize every binary labeling of that set. The two-stage count supplies an upper bound on how many dichotomies L(B,T) can produce. When m becomes sufficiently large, that upper bound is too small to include all labelings of C. Therefore C cannot remain shattered beyond that point.

Translating the restriction on m into a VC-dimension statement gives the stated upper bound: VCdim of L(B,T) is at most approximately VCdim(B) multiplied by T. The tilde notation in the source indicates that constants and logarithmic factors are being suppressed. The result expresses the main scaling idea: using T base hypotheses increases capacity in proportion to the base capacity times the number of selected hypotheses, subject to the suppressed factors in the bound.