dichotomy

Given a hypothesis $h:\mathcal{X}\to \{+1,-1\}$ and inputs ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_N$, the dichotomy generated by $h$ on those inputs is the tuple of labels $(h({\mathbf{x}}_1),\dots ,h({\mathbf{x}}_N))\in \{+1,-1{\}}^N$. The set of all dichotomies $\mathcal{H}({\mathbf{x}}_1,\dots ,{\mathbf{x}}_N)=\{(h({\mathbf{x}}_1),\dots ,h({\mathbf{x}}_N)):h\in \mathcal{H}\}$ replaces the infinite cardinality $|\mathcal{H}|$ with a finite count of at most $2^N$.

Definition

A hypothesis $h\in \mathcal{H}$ maps every point in $\mathcal{X}$ to $\{+1,-1\}$. The dichotomy of $h$ on a fixed set of $N$ inputs is what $h$ looks like restricted to those inputs:

$h({\mathbf{x}}_1,\dots ,{\mathbf{x}}_N)=(h({\mathbf{x}}_1),h({\mathbf{x}}_2),\dots ,h({\mathbf{x}}_N))\in \{+1,-1{\}}^N.$

Two different hypotheses can produce the same dichotomy: any two lines in ${\mathbb{R}}^2$ that label the same training points the same way are the same dichotomy even if they’re different decision boundaries. The dichotomy is a coarser equivalence class than the hypothesis itself.

The set of all dichotomies that $\mathcal{H}$ can implement on these inputs is

$\mathcal{H}({\mathbf{x}}_1,\dots ,{\mathbf{x}}_N)=\{(h({\mathbf{x}}_1),\dots ,h({\mathbf{x}}_N)):h\in \mathcal{H}\}.$

This set has size at most $2^N$ — the total number of binary labellings of $N$ points — and is finite even when $|\mathcal{H}|=\infty$.

Why It Matters

The generalisation bound from a union bound is

$\mathbb{P}[|E_{\text{in}}-E_{\text{out}}|>ϵ]\le 2M{e}^{-2{ϵ}^{2}N}$

where $M=|\mathcal{H}|$. For continuously-parameterised hypotheses (perceptrons, SVMs, neural networks), $M=\infty$ and the bound is vacuous.

The fix: most of the $M$ in the union bound is wasteful. If two hypotheses $h_1,h_2$ produce the same labelling on the training set, their bad events ${\mathcal{B}}_i=\{|E_{\text{in}}(h_i)-E_{\text{out}}(h_i)|>ϵ\}$ overlap massively — in the union bound we’re double-counting them.

Counting distinct dichotomies rather than distinct hypotheses gives a much smaller, finite quantity, and (with a more careful argument than the simple union bound) replaces $M$ in the generalisation bound. The maximum number of dichotomies over all possible input choices is the growth function $m_{\mathcal{H}}(N)$.

A Concrete Count

Take $\mathcal{H}=$ all lines in ${\mathbb{R}}^2$ (i.e., 2D perceptrons). Place $N=3$ inputs in general position. How many of the $2^3=8$ possible labellings can lines actually realise?

All 8: for any binary labelling of three non-collinear points, there’s a line that puts the $+1$ points on one side and $-1$ on the other. So $|\mathcal{H}({\mathbf{x}}_1,{\mathbf{x}}_2,{\mathbf{x}}_3)|=8$.

Now place $N=4$ points. Of the $2^4=16$ labellings, lines can realise only 14. The two unrealisable ones are the “XOR” labellings: $(+,-,-,+)$ and $(-,+,+,-)$ on a square — no line separates them. The infinite hypothesis set “all lines in ${\mathbb{R}}^2$” produces only 14 dichotomies on 4 points.

$N$	All possible labellings $2^N$	Lines in ${\mathbb{R}}^2$ realise
1	2	2
2	4	4
3	8	8
4	16	14

The structural restriction begins at $N=4$. This is the break-point behaviour that ultimately makes $m_{\mathcal{H}}(N)$ polynomial rather than exponential, and learning with infinite-$\mathcal{H}$ feasible.

Shattering

When $\mathcal{H}$ produces all $2^N$ possible dichotomies on a particular set of $N$ inputs, we say $\mathcal{H}$ shatters those inputs. Lines in ${\mathbb{R}}^2$ shatter any 3 non-collinear points, but cannot shatter any 4 points in general position. Convex sets in ${\mathbb{R}}^2$, on the other hand, shatter any number of points placed on a circle — so the dichotomy count stays at $2^N$ for all $N$.

Shattering is the strongest possible expressivity claim: there is no labelling we can’t fit. The largest $N$ for which $\mathcal{H}$ can shatter some set of $N$ inputs is the VC dimension of $\mathcal{H}$.

Related

• growth-function — $m_{\mathcal{H}}(N)=\max |\mathcal{H}({\mathbf{x}}_1,\dots ,{\mathbf{x}}_N)|$ over all input choices; replaces $M$ in the generalisation bound.
• vc-dimension — the largest $N$ for which some set of $N$ inputs is shattered.
• break-point — smallest $N$ at which shattering fails for every input set.
• generalization-bound — what the dichotomy-counting trick rescues.

Active Recall

Why isn't the size of $\mathcal{H}({\mathbf{x}}_1,\dots ,{\mathbf{x}}_N)$ always equal to $|\mathcal{H}|$, even when $\mathcal{H}$ is infinite?

Because many distinct hypotheses produce the same labelling on a fixed finite input set. Two slightly-rotated lines in ${\mathbb{R}}^2$ that happen to put the same training points on the same sides are different hypotheses but the same dichotomy. The dichotomy count collapses the equivalence class “labels the training set identically” — capped at $2^N$ regardless of how many distinct hypotheses exist.

Place 4 points at the corners of a square in ${\mathbb{R}}^2$. Which two of the 16 binary labellings can no linear classifier (perceptron in 2D) realise, and why?

The XOR-style labellings: $(+,-,-,+)$ on diagonally opposite corners, and the complement $(-,+,+,-)$. A line in ${\mathbb{R}}^2$ partitions the plane into two half-planes; to put diagonally-opposite corners on the same side and the other two opposite corners on the other side would require a non-linear boundary. So $|\mathcal{H}({\mathbf{x}}_1,\dots ,{\mathbf{x}}_4)|=14<16$, which is the source of the ${\mathbb{R}}^2$ perceptron’s break point at 4.

Why does counting dichotomies rather than hypotheses help us bound the probability of bad generalisation?

The naive union bound multiplies the per-hypothesis bad-event probability by $|\mathcal{H}|$, which is infinite for any continuously parameterised model. But “bad event for $h_1$” and “bad event for $h_2$” almost coincide when $h_1$ and $h_2$ produce the same labelling on the training set. A finer accounting collapses each equivalence class of identically-behaving hypotheses into a single dichotomy. There are at most $2^N$ dichotomies, and for “structured” $\mathcal{H}$ far fewer — often polynomial in $N$. The corrected union bound uses this dichotomy count rather than $|\mathcal{H}|$.