Dichotomies and Growth Functions

Why Count Prediction Patterns?

A binary hypothesis class can contain many prediction rules, but on a particular finite sample some rules may make exactly the same predictions. For questions about how flexibly the class can label data, the relevant count is therefore not simply the number of rules: it is the number of distinct binary prediction patterns the rules produce on the sample.

This count is a basic combinatorial summary of a class. It helps describe how much variation the class can express across samples, which is useful when studying generalization. The key is to keep two questions separate: how many patterns occur on one specified sample, and what is the largest such count over all samples of a fixed size?

Dichotomies on a Fixed Sample

Definition: Let \(X\) be an input space and let \(\mathcal{H}\) be a nonempty class of binary functions \(h:X\to\{0,1\}\). For an ordered finite sample \(S=(x_1,\ldots,x_n)\), a dichotomy realized by \(\mathcal{H}\) on \(S\) is a vector \((h(x_1),\ldots,h(x_n))\in\{0,1\}^n\) for some \(h\in\mathcal{H}\). The set of all such vectors is the trace of \(\mathcal{H}\) on \(S\).

The ordering in \(S\) gives the coordinates of each prediction vector. Changing the order of the sample only permutes those coordinates, so it does not change how many distinct dichotomies are realized. The definition allows repeated inputs: a sample is a sequence, not necessarily a set of distinct points.

Worked Example: Counting Patterns With a Repeated Input

Let \(X=\{A,B,C\}\), and consider three hypotheses with values \(h_0=(0,0,0)\), \(h_1=(1,1,1)\), and \(h_2=(1,0,1)\), where the coordinates correspond to \(A,B,C\). Count their distinct dichotomies on \(S=(C,A,C)\).

For \(h_0\), each sampled point has label 0, so the prediction vector is \((0,0,0)\). For \(h_1\), each has label 1, giving \((1,1,1)\). For \(h_2\), both \(C\) and \(A\) have label 1, so it also gives \((1,1,1)\). Thus the set of realized dichotomies is \(\{(0,0,0),(1,1,1)\}\), with cardinality 2.

There are three hypotheses but only two distinct patterns on this sample. The repeated occurrence of \(C\) also forces the first and third coordinates of every realized vector to agree.

Proposition: If \(x_i=x_j\) for two positions in a sample, then every dichotomy on that sample has equal entries in positions \(i\) and \(j\).

Proof. For any \(h\in\mathcal{H}\), equality of the inputs implies \(h(x_i)=h(x_j)\), since \(h\) is a function. This holds for every hypothesis in the class, so every realized prediction vector has equal entries in those two positions. \(\square\)

The Growth Function

Definition: For a nonempty binary class \(\mathcal{H}\), its growth function at sample size \(n\) is \(\Pi_{\mathcal{H}}(n)\), the maximum number of distinct dichotomies it can realize on any ordered sample of \(n\) points from \(X\): \[ \Pi_{\mathcal{H}}(n) = \sup_{x_1,\ldots,x_n\in X} \left| \left\{ (h(x_1),\ldots,h(x_n)):h\in\mathcal{H} \right\} \right|. \] For \(n=0\), the only prediction vector is the empty vector, so \(\Pi_{\mathcal{H}}(0)=1\).

For each fixed sample of size \(n\), there can be at most \(2^n\) binary vectors. The growth function asks how many distinct vectors the class can attain on its most favorable sample of that size. It is therefore a worst-case count, not the number of patterns on a particular dataset.

Because the possible counts for a fixed \(n\) are integers between 1 and \(2^n\), the supremum in the definition is attained whenever there is at least one sample of size \(n\). Repeated points are allowed, but they may reduce the count on a given sample by imposing coordinate equalities.

Threshold Classifiers on the Real Line

Theorem: Let \(X=\mathbb{R}\) and let \(\mathcal{H}\) be the class of threshold classifiers \(h_t(x)=\mathbf{1}\{x\ge t\}\), for \(t\in\mathbb{R}\). Then \(\Pi_{\mathcal{H}}(n)=n+1\) for every integer \(n\ge 0\).

Proof. For \(n=0\), the result is the convention \(\Pi_{\mathcal{H}}(0)=1\). Now take \(n\ge1\). On any sample, let its distinct input values, in increasing order, be \(z_1<\cdots<z_m\), where \(m\le n\). A threshold labels all values below \(t\) as 0 and all values at least \(t\) as 1. As \(t\) moves from left to right, the label pattern can change only when it passes one of the \(m\) distinct sample values. Thus there are at most \(m+1\le n+1\) patterns on this sample.

For the matching lower bound, choose a sample of \(n\) distinct points \(x_1<\cdots<x_n\). Taking \(t\le x_1\) gives the all-one vector, and taking \(t>x_n\) gives the all-zero vector. For each \(k=1,\ldots,n-1\), choosing \(x_k<t\le x_{k+1}\) gives \(k\) zeros followed by \(n-k\) ones. These are \(n+1\) distinct patterns in total, so the maximum is at least \(n+1\). Combining the upper and lower bounds proves the result. \(\square\)

Worked Example: Thresholds on Four Ordered Observations

Take four distinct observations \(x_1<x_2<x_3<x_4\). The threshold class \(h_t(x)=\mathbf{1}\{x\ge t\}\) realizes the following patterns as \(t\) moves across the observations.

If \(t\le x_1\), the vector is \((1,1,1,1)\). If \(x_1<t\le x_2\), it is \((0,1,1,1)\). If \(x_2<t\le x_3\), it is \((0,0,1,1)\). If \(x_3<t\le x_4\), it is \((0,0,0,1)\). Finally, if \(t>x_4\), it is \((0,0,0,0)\).

These five vectors are distinct, and the theorem shows that no sample of four points can produce more. Hence \(\Pi_{\mathcal{H}}(4)=5\). The count is not \(2^4\): thresholds cannot produce arbitrary arrangements of zeros and ones, such as \((1,0,1,0)\).

Calculating Growth Functions for Finite Classes

For a finite class, the hypotheses can be listed and their prediction vectors compared on a sample. Different hypotheses may coincide on that sample, so an exact calculation must remove duplicate vectors. The next example shows why knowing only the class size and sample size need not determine the exact count.

Worked Example: A Four-Hypothesis Class on Three Inputs

Let \(X=\{a,b,c\}\), and define \(\mathcal{H}=\{h_0,h_a,h_b,h_c\}\). The function \(h_0\) is zero everywhere; \(h_a\) is 1 at \(a\) and 0 elsewhere; \(h_b\) is 1 at \(b\) and 0 elsewhere; \(h_c\) is 1 at \(c\) and 0 elsewhere. We calculate the growth function for every sample size.

For \(n=0\), the empty sample has one empty prediction vector, so \(\Pi_{\mathcal{H}}(0)=1\). For \(n=1\), choosing any one input yields both possible labels 0 and 1 among the hypotheses, hence \(\Pi_{\mathcal{H}}(1)=2\).

For \(n=2\), use the sample \((a,b)\). The four hypotheses give, respectively, \((0,0)\), \((1,0)\), \((0,1)\), and \((0,0)\). There are three distinct patterns. Any sample of size two either uses two distinct inputs, in which case the two singleton hypotheses associated with those inputs and the all-zero pattern give at most three patterns, or repeats one input, in which case only two patterns are possible. Thus \(\Pi_{\mathcal{H}}(2)=3\).

For \(n\ge3\), choose a sample whose first three entries are \(a,b,c\), filling any remaining entries by repetitions. On the first three coordinates the hypotheses give \(000,100,010,001\), respectively, so all four are distinct on the full sample as well. There cannot be more than four patterns because the class contains only four hypotheses. Therefore \(\Pi_{\mathcal{H}}(n)=4\) for every \(n\ge3\).

In summary, the values are 1 at \(n=0\), 2 at \(n=1\), 3 at \(n=2\), and 4 for \(n\ge3\). In particular, on two observations the class has four hypotheses but realizes only three dichotomies on the best possible sample.

Worked Example: Two Constant Classifiers

Let \(X\) be any nonempty input space and let \(\mathcal{H}\) consist of only the two constant functions \(h_0(x)=0\) and \(h_1(x)=1\). On every nonempty sample, \(h_0\) produces the all-zero vector and \(h_1\) the all-one vector. These are distinct, and there are no other hypotheses, so \(\Pi_{\mathcal{H}}(n)=2\) for every \(n\ge1\). By convention, \(\Pi_{\mathcal{H}}(0)=1\).

This count is unaffected by the sample values: the two rules always disagree at every coordinate. By contrast, in the four-hypothesis example, the exact count depended on how many different inputs the sample included.

Common Mistakes and Why the Count Matters

Counting hypotheses instead of dichotomies. Different hypotheses can produce the same vector on a sample. Compare prediction vectors and count each distinct vector once.
Treating a sample-specific count as the growth function. A growth function takes the largest count over all samples of the stated size. A sample with repeated inputs may realize fewer patterns than a sample of distinct inputs.
Assuming every binary pattern is attainable. There are \(2^n\) possible binary vectors of length \(n\), but a restricted class may realize only a small subset. Thresholds, for example, produce ordered patterns rather than arbitrary ones.
Assuming the number of hypotheses gives the exact count. A finite class can have hypotheses that agree on a sample. In the four-hypothesis example, four rules yield only three patterns when the sample is \((a,b)\).

The growth function packages a sample-wise counting question into a sequence indexed by sample size. Its value records the largest number of distinct labelings the class can produce, not how many hypotheses are written in its definition. This distinction is essential whenever a later argument needs to control the range of prediction patterns across samples.

Check Your Understanding

Answer each question by identifying the sample or class features that determine the count.

Why must the entries in positions \(i\) and \(j\) agree in every dichotomy if \(x_i=x_j\)?
For four distinct real inputs, how many patterns can the threshold class \(h_t(x)=\mathbf{1}\{x\ge t\}\) realize, and why can it not realize \((1,0,1,0)\)?
For the class with \(h_0,h_a,h_b,h_c\), list the distinct prediction vectors on the sample \((a,c)\).
Explain the difference between the number of hypotheses in a class and the number of dichotomies it realizes on a fixed sample.
Why does the definition of the growth function take a maximum over samples rather than use the count from one observed sample?