Linear Combinations of Base Hypotheses
The capacity of L(B,T) is analyzed by counting dichotomies on a set C.
Why Combination Capacity Matters
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 VC-dimension of a hypothesis class measures the largest size of a set that the class can shatter. A set is shattered when the class can realize every possible binary labeling of that set.
The Two-Stage Construction
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.
Tracking the Construction on One Input
Suppose T base hypotheses are selected from B. What information is used to produce the final prediction for an input x?
Select: Choose h1 through hT from the base class B.
Evaluate: Apply every selected hypothesis to x, producing h1(x) through hT(x).
Combine: Treat those T outputs as one vector and apply a halfspace or linear predictor.
Predict: The linear predictor produces the final label for x.
L(B,T) uses T base hypotheses followed by a linear decision rule; it does not stop after selecting one member of B.
Counting Base Patterns on C
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 Two-Stage Counting Bound
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.
Following the Count Symbolically
Let C contain m points, let d equal VCdim(B), and let L(B,T) use T base hypotheses. Track the available choices without substituting numerical values.
Count one position: Sauer's Lemma gives at most (em/d)^d base patterns for one selected hypothesis position.
Fill T positions: Choosing a pattern independently for each of T positions gives at most (em/d)^(dT) pattern selections.
Apply the final rule: For each selection, the linear predictor contributes at most (em/T)^T dichotomies.
Compare with shattering: If C were shattered by L(B,T), the class would need to realize every binary labeling of C. Once m is sufficiently large, the counted upper bound prevents that.
The inability to realize all labelings for sufficiently large m yields an upper bound on VCdim(L(B,T)).
The proof counts two separate sources of variation: first, the T base-class patterns selected on C; second, the dichotomies produced by the final linear predictor on the resulting T-dimensional vectors.
From Counting to VC-Dimension
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.
Common Counting Mistakes
Counting hypotheses instead of dichotomies on C
The argument is about labelings produced on the selected finite set. Hypotheses that agree everywhere on C are indistinguishable for this count.
Fix:
Count distinct base patterns induced on C, using Sauer's Lemma.Stopping after counting the T base-pattern selections
The T selected patterns are still processed by a final halfspace or linear predictor, which contributes another bounded source of dichotomies.
Fix:
Include both stages: the T pattern choices and the predictor's at-most (em/T)^T dichotomies.Confusing the base class with the combined class
L(B,T) selects T hypotheses and then applies a linear decision rule to their outputs.
Fix:
Track the vector h1(x) through hT(x) before discussing the final prediction.Treating the approximate VC-dimension result as an exact equality
The source states an upper bound and notes that constants and logarithmic factors are suppressed.
Fix:
Describe it as an approximate upper-bound scaling statement.
When reconstructing the proof, write down the two stages separately. First ask how many patterns one base hypothesis can induce on C, then raise that count to account for T positions. Only after that should you count the dichotomies produced by the final linear predictor.
Practice and Takeaways
Explain why the proof counts patterns induced by B on C rather than counting hypotheses in B directly. Then describe the two factors that must be included after T base patterns have been selected.
Hints
- Focus on when two hypotheses are indistinguishable for the purpose of labeling C.
- Separate the number of possible T-pattern selections from the number of dichotomies produced by the final predictor.
- VC-dimension measures the capacity of a hypothesis class through shattering and realizable dichotomies. L(B,T) first selects T hypotheses from B, evaluates them to form a T-dimensional output vector, and applies a halfspace or linear predictor. Sauer's Lemma bounds the number of distinct patterns that one base hypothesis can induce on a set C. Repeating that choice for T positions and then counting the final predictor's dichotomies gives an upper bound on the capacity of L(B,T). The resulting VC-dimension scales approximately as VCdim(B) multiplied by T, with constants and logarithmic factors suppressed.
Key Takeaways
- VC-dimension measures how many points a hypothesis class can shatter.
- L(B,T) combines T hypotheses from B and applies a final linear predictor to their outputs.
- Sauer's Lemma bounds the number of distinct dichotomies that B can induce on a finite set C.
- The capacity bound counts both the T base-pattern selections and the final predictor's dichotomies.
- The resulting VC-dimension of L(B,T) is bounded approximately by VCdim(B) multiplied by T, up to constants and logarithmic factors.