Dichotomies of Hypothesis Classes

Why Combined Classes Need Counting

A learning method can build one hypothesis by combining several simpler hypotheses. The combined class may then produce more labelings than the base class can produce by itself. The key question is therefore a capacity question: on a fixed set of examples, how many different binary labelings can the entire combined class produce?

A dichotomy is one binary labeling of a fixed set of points produced by a hypothesis class. VC-dimension 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. Thus, VC-dimension does not merely ask whether a class can label some examples; it asks how large a set can support all possible labelings.

The Two Stages of L(B,T)

The class L(B,T) is constructed in two stages. First, select T hypotheses from the base class B. Denote them by h1 through hT. For an input x, these hypotheses produce T values: h1(x) through hT(x). These values form a T-dimensional output vector.

Second, apply a halfspace hypothesis, also described as a linear predictor, to that output vector. The final prediction is therefore not the output of one base hypothesis alone. It is the result of selecting T base hypotheses and then applying a linear decision rule to their outputs.

Counting Base-Class Dichotomies

To analyze the capacity of L(B,T), fix a set C containing m points. Ask first how many different labelings the base class B can create on C. Let d denote the VC-dimension of B. Sauer's Lemma gives an upper bound: B can induce at most (em/d) raised to the power d different dichotomies on C.

This bound counts patterns rather than individual hypotheses. That distinction matters. If two hypotheses in B produce the same labeling on C, they are indistinguishable for the purpose of counting what can happen on C. The proof therefore does not need to count every member of B separately; it only needs to count the distinct patterns visible on C.

Combining T Pattern Choices

Once the available base-class patterns on C have been counted, repeat the choice T times. Each of the T positions is filled by one pattern that B can produce on C. Since one position has at most (em/d) raised to the power d choices, all T positions together have at most (em/d) raised to the power dT choices.

These T selected patterns determine the T-dimensional output vector for every point in C. The final linear predictor then operates on those vectors. The proof states that this final predictor can produce at most (em/T) raised to the power T dichotomies on the resulting output vectors.

From Counting to a VC Bound

The proof now assumes that C is shattered by L(B,T). If C has m points and is shattered, L(B,T) must realize every binary labeling of C. The required number of labelings is therefore the number of all binary labelings of an m-point set.

The counting argument gives an upper bound on how many dichotomies L(B,T) can actually produce: the choices of T base patterns contribute the first factor, and the final linear predictor contributes the second factor. Once m becomes sufficiently large, this upper bound is too small to support every labeling of C. At that point, C cannot be shattered.

Writing d for VCdim(B), the counting argument yields the stated upper bound that VCdim(L(B,T)) is approximately d multiplied by T, with constants and logarithmic factors hidden by the tilde notation. This is an upper bound, not a claim that every such class always achieves exactly that dimension.

Common Counting Mistakes

• Treating L(B,T) as if it selected only one hypothesis from B.

  L(B,T) selects T base hypotheses and then applies a linear predictor to their joint output vector.

  Fix: Count the available pattern choices for all T positions, then count the dichotomies produced by the final predictor.

• Counting hypotheses instead of distinct labelings on C.

  For the fixed set C, hypotheses with identical labelings are indistinguishable in the dichotomy count.

  Fix: Count distinct patterns induced on C and use Sauer's Lemma to bound that number.

• Using Sauer's Lemma as a count for the entire class L(B,T).

  Sauer's Lemma controls the patterns contributed by B. The T-fold selection and the final linear predictor are additional stages.

  Fix: Use Sauer's Lemma for one base position, raise the resulting count to account for T positions, and then include the final predictor's bound.

• Confusing a large number of possible labelings with shattering.

  Shattering requires every binary labeling of C, not merely many labelings.

  Fix: Compare the number of labelings required for shattering with the upper bound on labelings the class can produce.

Check Your Reasoning

Summary

1. VC-dimension measures the largest size of a set that a hypothesis class can shatter.
2. L(B,T) selects T hypotheses from B, forms their output vector on each input, and applies a halfspace or linear predictor.
3. Sauer's Lemma bounds the number of distinct dichotomies that B can induce on an m-point set C by at most (em/d)^d, where d is VCdim(B).
4. For T selected base positions, the base-pattern count is bounded by (em/d)^(dT), and the final predictor contributes an additional bounded number of dichotomies.
5. Comparing the resulting upper bound with the number of labelings required for shattering gives VCdim(L(B,T)) approximately equal to dT, up to constants and logarithmic factors.