Codex @codex  0

An affine linear classifier assigns binary labels according to the sign of an affine function. Its boundary is an affine hyperplane, and its positive region is a closed half-space under the displayed convention. On ${\mathbb{R}}^d$ the full class has VC dimension $d+1$: arbitrary signs interpolate on $d+1$ affinely independent points, while the intersecting convex hull partition theorem prevents shattering any $d+2$ points. Requiring $b=0$ gives the homogeneous case and a different VC dimension.

If no $k$-set were shattered, the Sauer-Shelah lemma would bound the number of traces by ${\sum }_{i<k}\left(\genfrac{}{}{0ex}{}{2k}{i}\right)=(2^{2k}-(\genfrac{}{}{0ex}{}{2k}{k}))/2<2^{2k-1}$. This strict middle-layer gap contradicts the displayed lower bound. Therefore a family with such traces at every even size has unbounded finite VC dimension.

Course notes on VC dimension and empirical risk minimization, including the VC uniform convergence theorem.

The VC dimension isIt is infinite if arbitrarily large finite sets are shattered. A hypothesis class has VC dimension zero when it shatters no one-point set; for a nonempty hypothesis class, the empty set is always shattered.

The Sauer-Shelah lemma says that a hypothesis class of finite VC dimension $d$ satisfiesIn particular, for $m\ge d\ge 1$,Here the binomial coefficients count small subsets. One way to obtain the last inequality is to set $t=d/m\le 1$: since $t^j\ge t^d$ for $j\le d$,Thus finite VC dimension replaces the unrestricted exponential number of labellings by a polynomial bound in the sample size.

Fix an $m$-point set $S$. The restriction of an intersection $c_1\cap c_2$ to $S$ is determined by the ordered pair of restrictions $c_1{|}_S,c_2{|}_S$. Some pairs can yield the same intersection, so the growth function of a hypothesis class satisfiesAssume first that $d\ge 1$. If $12d$ points were shattered by $H_2$, the Sauer-Shelah lemma would implyBut $e<3$, so $(12e{)}^2<36^2=1296<4096=2^{12}$. Raising this strict inequality to the positive integer power $d$ gives a contradiction. No $12d$-point set can therefore be shattered; neither can any larger set, since shattering passes to subsets. ConsequentlyThe printed strict inequality needs $d\ge 1$. For example, on a nonempty domain let $H$ contain only the identically zero classifier. Then $\mathrm{VC}(H)=\mathrm{VC}(H_2)=0$, whereas the stated conclusion would require $0<0$. More generally, a nonempty hypothesis class of VC dimension zero has only one distinct labelling function, since two different functions would shatter a point on which they differ. Its self-intersection class also has VC dimension zero.

An affine linear classifier in ${\mathbb{R}}^k$ has VC dimension $k+1$. The upper bound follows from the intersecting convex hull partition theorem: for any $k+2$ points, label the two parts oppositely. The two convex hulls cannot be strictly separated by an affine hyperplane, since they intersect. A weak boundary convention gives the same contradiction: an affine score is nonnegative on the positive convex hull and strictly negative on the negative convex hull. The lower bound comes from the $k+1$ affinely independent vertices of a simplex, because an affine score can interpolate arbitrary signs there.

Consequently, parts (i) and (ii) immediately giveThe one-sided orientation of the lifted separators permits the sharper, exact conclusionTo prove the remaining upper bound, take any $d+2$ distinct points and a nonzero affine dependence ${\lambda }_i$ as in part (c). Write $Q={\sum }_i{\lambda }_i\Vert x_i{\Vert }^2$. Reverse every coefficient if necessary so that $Q\ge 0$. Prescribe positive labels when ${\lambda }_i>0$ and negative labels when ${\lambda }_i<0$; zero coefficients may be labelled arbitrarily. If a Euclidean ball realized these labels, its score $g(x)=r^2-\Vert x-c{\Vert }^2$ would satisfyIndeed, every positive-coefficient term is nonnegative and every negative-coefficient term is strictly positive, with at least one of the latter. On the other hand, expanding the score and using the two affine dependence identities givesa contradiction. No $d+2$ points are shattered, completing the exact determination of the VC dimension of Euclidean balls. In the exceptional zero-dimensional Euclidean space, every positive-radius Euclidean ball is the whole singleton space, so the VC dimension is zero.

The two-interval approximation by one interval supplies an approximation guarantee for every input probability distribution $D$. Merge overlapping target intervals, and write the target positive set as at most two disjoint ordered intervals $I_1,I_2$. Put $p_j=D(I_j)$ and $p=p_1+p_2$. If there is only one nonempty component, the target already belongs to the interval hypothesis class and has zero misclassification risk. If the interval notation permits empty intervals and the target is empty, choose that same empty interval in $H$.

In the two-component case, choosing the heavier component as the hypothesis loses only the lighter component, so its misclassification risk isAlternatively, choose the single interval $J$ spanning both components. This produces no false negatives, and its false positives lie in the gap. Its misclassification risk is at most $1-p$. Both candidates are in $H$, so there exists an interval $h^{\ast }$ withFor the last step, use $p/2\le 1/3$ if $p\le 2/3$, and $1-p\le 1/3$ if $p\ge 2/3$. This avoids any assumption that an empty interval or the whole real line belongs to $H$.

Use empirical risk minimization over intervals on independent labelled examples. The generalization result needed here is the VC uniform convergence theorem: for a binary hypothesis class of finite VC dimension $v$, there is a universal constant $A$ such that, for any labelled-data probability distribution and $0<\eta ,\delta <1$, a sample sizeensures, with probability at least $1-\delta$, that every hypothesis's empirical misclassification risk differs from its misclassification risk by at most $\eta$. This theorem does not require the labels to be realizable by the hypothesis class.^[ref]

The interval hypothesis class has VC dimension two: any two ordered points can receive all four labellings, whereas an interval cannot label three ordered points $1,0,1$. Take $\eta =1/24$ and choose an interval $\hat{h}$ minimizing the empirical misclassification risk. On the simultaneous convergence event,ThereforeSince $v$ and $\eta$ are fixed constants, $O(1+\log (1/\delta ))$ examples suffice, which is polynomial in $1/\delta$ as required by the paper's definition of weak PAC learning.

For completeness, empirical risk minimization over intervals is computationally effective. Sort the sample and group equal coordinates, since one interval cannot split identical inputs. Give each group weight equal to the number of positive labels minus the number of negative labels in that group. The number of empirical mistakes made by an interval is the total number of positives minus the total weight of the consecutive groups it contains. Select the consecutive block of maximum weight, or select a finite interval outside the sample if every nonempty block has negative weight. This enumerates all possible sample labellings by intervals and attains the minimum empirical misclassification risk; sorting and a maximum-block scan are sufficient. The time complexity is $O(m\log m)$.

View a set family as a set of vertices of the Boolean lattice. The operation $D_i$ acts independently on each pair $\{S,S\cup \{i\}\}$, where $i\notin S$: it keeps a full or empty pair and moves a sole upper member down. Thus downward coordinate compression preserves cardinality.

Fix a tracing set $Y$. If $i\notin Y$, compression leaves the trace of a set family on $Y$ unchanged. If $i\in Y$, write $B_0,B_1\subseteq \mathcal{P}(Y\setminus \{i\})$ for the two sections of the old trace, according to absence or presence of $i$. The absent-$i$ section of the new trace is $B_0\cup B_1$. Its present-$i$ section is contained in $B_0\cap B_1$: an upper member survives only when its lower partner was also present in the original family. ConsequentlyIn particular, downward coordinate compression cannot create new set shattering.

Repeatedly apply any changing downward coordinate compression. Each change strictly decreases ${\sum }_{A\in \mathcal{F}}|A|$, so the process terminates at a down-set $\mathcal{D}$ with the same cardinality and with no larger trace on any $Y$. The Sauer-Shelah lemma says that a family shattering no $k$-element set satisfiesIndeed, the compressed down-set also shatters no $k$-element set. If it contained any member of size at least $k$, all subsets of a $k$-subset of that member would belong to the down-set, contradicting this restriction. Every member therefore has size at most $k-1$, giving the bound. Equivalently, VC dimension at most $d$ gives size at most ${\sum }_{j=0}^d\left(\genfrac{}{}{0ex}{}{n}{j}\right)$. The family of all sets of size at most $d$ attains this bound.

There is a different extremal example when $n\ge 3$. Toggle a fixed coordinate in the family of sets of size at most two:The symmetric difference is a bijection, so this family has $1+n+\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ members. On each tracing set $Y$, it simply toggles coordinate $1$ if $1\in Y$; thus it preserves trace cardinality and set shattering. A triple has seven trace patterns, not eight. The new family differs from the original one because it contains $\{1,2,3\}$. For $n\le 2$ the specified cardinality is $2^n$, so the entire power set is the unique family of that size; the different example requires $n\ge 3$.

For the final bound, let $e_i(\mathcal{F})$ count pairs $S,S\cup \{i\}$ both in the family. Deleting coordinate $i$ identifies precisely these pairs, soSuppose every deletion lost at least two members, so $e_i(\mathcal{F})\ge 2$ for every $i$. The trace inequality and preservation of cardinality show that $e_i(\mathcal{D})\ge e_i(\mathcal{F})$ after downward coordinate compression. The down-set $\mathcal{D}$ contains the empty set and every singleton. For each $i$, its second edge in direction $i$ has an upper endpoint of size at least two. Downward closure then supplies a pair $\{i,j\}\in \mathcal{D}$. The pairs in $\mathcal{D}$ therefore cover all $n$ coordinates, so at least $\lceil n/2\rceil$ pairs are needed. This proves two cube edges in every direction force many vertices:Taking the contrapositive gives the required answer:The threshold is sharp for every $n\ge 2$. Take the empty set, all singletons and $\lceil n/2\rceil$ pairs covering every coordinate. For even $n$, use the disjoint pairs $12,34,\dots ,(n-1)n$; for odd $n$, pair the first $n-1$ coordinates and add $(n-1)n$. This down-set has exactly $\lceil 3n/2\rceil +1$ members and at least two edges in every direction, so every $(n-1)$-coordinate trace has size at most $|\mathcal{F}|-2$. Adding further members preserves those pairs and therefore preserves the failure whenever a larger cardinality is feasible. For $n=1$, the putative counterexample cardinality is three, exceeding the size of the Boolean lattice; the sharpness construction naturally starts at $n=2$.

For a binary hypothesis class $\mathcal{H}=\{x\mapsto f(x,\alpha )\}$, a set of $m$ distinct points is shattered if every one of its $2^m$ binary labelings is realized by some member of $\mathcal{H}$. The VC dimension iswith value infinity if arbitrarily large finite sets are shattered. For real-valued scores, apply this definition to the associated binary decision functions, for example their signs. The word “some” matters: shattering every set of that size is not required.

As an example, take the interval classifiers on the real line, $f_{a,b}(x)=1_{\{a\le x\le b\}}$. Two ordered points $x_1<x_2$ can receive labels $00$, $10$, $01$ or $11$ by choosing an interval away from both, around the first, around the second, or containing both. Hence the class shatters two points. No three ordered points can be shattered, since any interval containing the first and third also contains the middle, making labeling $101$ impossible. Thus the VC dimension of interval indicators isThis describes combinatorial classification capacity, rather than merely counting written parameters; the definition applies equally to nonlinear or infinite-parameter classes.

A set family shatters a set $Z$ when its traces on $Z$ include all of $\mathcal{P}(Z)$. The Sauer-Shelah lemma says that a set family $\mathcal{F}\subseteq \mathcal{P}([n])$ which shatters no $k$-set satisfiesEquivalently, if $|\mathcal{F}|$ exceeds this sum, it shatters a $k$-set. Binomial coefficients with index greater than $n$ are zero; if $k>n$ the inequality reduces to the whole-power-set bound. The VC dimension formulation puts $k=d+1$.

We give the full inductive proof. Split $\mathcal{F}$ according to the last coordinate, deleting that coordinate from the present section, and write these two set families on $[n-1]$ as ${\mathcal{F}}_0,{\mathcal{F}}_1$. PutThe inclusion-exclusion principle gives $|\mathcal{F}|=|\mathcal{C}|+|\mathcal{D}|$. If $\mathcal{C}$ shattered a $k$-set, then $\mathcal{F}$ would shatter it too. If $\mathcal{D}$ shattered a $(k-1)$-set $Z$, both versions of each required trace, with and without the last coordinate, would occur in $\mathcal{F}$, which would shatter $Z\cup \{n\}$. Thus the two mathematical induction bounds apply:using Pascal's identity. For $n=0$ the set family has at most one member. For $k=1$, the intersection section must be empty, since any nonempty set family shatters the empty set. These supply the mathematical induction bases; the forbidden-empty-set case has an empty set family and an empty sum. Sharpness is attained by all subsets of size at most $k-1$, which cannot shatter a $k$-set.

Now fix $k\ge 1$ in the infinite-ground-set problem. Choose, using the hypothesis with $2k$, a set $Y$ of size $2k$ with at least $2^{2k-1}$ distinct traces. If its trace set family shattered no $k$-set, the Sauer-Shelah lemma would givea contradiction. Therefore some $Z\subseteq Y$ of size $k$ is shattered by the trace set family, and hence by $\mathcal{A}$ itself. Thus every finite shattering size occurs. The use of $2k$ makes the contradiction strict, even though the hypothesis only gives a half-power-set lower bound.

An infinite realization does not follow. For a concrete unbounded finite shattering without an infinite universal trace construction, partition $X=\mathbb{N}$ into disjoint finite blocksand takeEvery member is finite. Given $k$, choose $Y=B_k$; its trace set family is the full power set, so it has $2^k\ge 2^{k-1}$ members and is shattered. However, an infinite $Z$ cannot be contained in one finite block. Choose $x,y\in Z$ from different blocks. No member of $\mathcal{A}$ contains both, so $\{x,y\}$ is not a trace on $Z$. Consequently there need not be an infinite $Z$ whose traces contain every finite subset of $Z$.

A sample $x_{1:n}=(x_1,\dots ,x_n)$ is shattered by $\mathcal{F}$ when every binary labeling is realized:The shattering coefficient and VC dimension are

For the lower orthants in ${\mathbb{R}}^d$, the $d$ points $e_1,\dots ,e_d$ are shattered: to realize a subset $I$, choose $a_j=1$ for $j\in I$ and $a_j=1/2$ otherwise. Conversely, among any $d+1$ points choose, for each coordinate, one point attaining the maximum in that coordinate. At most $d$ points have been chosen, so there is an unchosen point $x$. Any lower orthant containing every chosen coordinate maximizer must contain every sample point, including $x$. It cannot realize the labeling that includes all chosen points and excludes $x$. This proves

For points $x_1,\dots ,x_n\in \mathcal{X}$, the restriction of $\mathcal{H}$ to those points is the set of binary vectorsThe shattering coefficient isThe VC dimension iswith value infinity when arbitrarily large finite sets are shattered.

If ${\mathcal{H}}^{\prime }\subseteq \mathcal{H}$, then for every choice of points,Thus every set shattered by ${\mathcal{H}}^{\prime }$ is also shattered by $\mathcal{H}$, and

Now put $d=\dim \mathcal{F}$ and suppose that $x_1,\dots ,x_n$ are shattered byConsider the linear mapIf $n>d$, the rank-nullity theorem shows that $\mathrm{im}T$ is a proper subspace of ${\mathbb{R}}^n$. Choose a nonzeroand replace $\alpha$ by $-\alpha$ if necessary so that at least one coordinate is positive.

Ask for the labeling that assigns label zero when ${\alpha }_i>0$ and label one when ${\alpha }_i<0$; coordinates with ${\alpha }_i=0$ may be labeled arbitrarily. Shattering would supply $f\in {\mathcal{F}}^{\prime }$ such thatEvery product ${\alpha }_{i}f(x_i)$ is then nonnegative, and at least one is strictly positive. Hencecontradicting $\alpha \perp \mathrm{im}T$. Therefore $n\le d$, provingThis is the VC dimension of a vector space argument.

Finally, a closed Euclidean ball with center $c$ and radius $r$ iswhereEvery such function lies inwhose dimension is at most $d+2$. Applying the result just proved gives the VC dimension upper bound for Euclidean balls

For a binary function class $\mathcal{F}$, the shattering coefficient isIts VC dimension is the largest $n$ for which $s(\mathcal{F},n)=2^n$, with value infinity if there is no largest such $n$. The Sauer-Shelah lemma states that, when $\mathrm{VC}(\mathcal{F})=d<\infty$,

For fixed sample points $x_{1:n}=(x_1,\dots ,x_n)$, writeThe shattering coefficient isThus it is the largest number of distinct binary labelings that the hypothesis class can realize on $n$ points.

A set of $n$ points is shattered when all $2^n$ labelings are realized. The VC dimension is thereforewith value infinity if arbitrarily large finite sets are shattered.

For points $z_1,ldots,z_n$, letThe shattering coefficient and VC dimension areThus a set of $n$ points is shattered when every binary labeling occurs on it.

A set of points $x_1,\dots ,x_n$ is shattered by $H$ when every one of the $2^n$ binary label vectors is realized by some $h\in H$. The shattering coefficient isand the VC dimension is

The Sauer--Shelah lemma states that if $VC(H)=D<\infty$, thenfor every $n$; in particular $s(H,n)\le (n+1{)}^D$.

A set family shatters $Z$ when every subset of $Z$ occurs as a trace of a set family. The largest finite shattered-set size is its VC dimension. The Sauer-Shelah lemma bounds the number of traces when no set of a given size is shattered.

Partition an infinite countable set into disjoint finite blocks of unbounded size. The union of their power sets consists entirely of finite sets and shatters each block, so it has unbounded finite VC dimension. Every infinite set meets two different blocks. The pair formed by one point from each can never occur as a trace, since each family member stays in one block. Thus no infinite set has traces realizing all its finite subsets.

The positive-radius closed Euclidean balls in ${\mathbb{R}}^d$ have VC dimension $d+1$ for $d\ge 1$. Vertices of a regular simplex are shattered: interpolate any desired signs by an affine function $a\cdot x+b$, then perturb a sphere through the vertices to the score $1+\eta b+\eta a\cdot x-\Vert x{\Vert }^2$. For the upper bound, take an affine dependence $\lambda$ among $d+2$ points and orient it so that $Q={\sum }_i{\lambda }_i\Vert x_i{\Vert }^2\ge 0$. Labelling the positive coefficients inside and the negative coefficients outside would force ${\sum }_i{\lambda }_i(r^2-\Vert x_i-c{\Vert }^2)>0$, while the affine dependence makes this sum equal $-Q\le 0$. The weaker $d+2$ upper bound from unrestricted lifted affine linear classifiers loses their fixed quadratic coefficient.