ExampleConstruction: Literature-sourcedVerification: AI-adaptedPipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Affine halfspaces in real p-space have VC dimension p plus one

Example

Use local coordinates $x_{i} : = x (i - 1)$ on $R^{k}$ and write $e_{i}$ for the function that is one at $i - 1$ and zero elsewhere, for $1 \leq i \leq k$ . Thus these coordinates and unit vectors reindex the canonical indices $0, \dots, k - 1$ by $1, \dots, k$ .

Equip $R^{p}$ with its Euclidean Borel sigma-algebra. For an integer $p \geq 1$ , let $H_{p}$ consist of the classifiers on $R^{p}$ of the form $h_{w, b} (x) = 1$ if and only if $w \cdot x + b \geq 0$ , with $w \in R^{p}$ and $b \in R$ , where $w \cdot x : = \sum_{j = 1}^{p} w_{j} x_{j}$ . The sketch illustrates one labeling for $p = 2$ : the affine score $f (x_{1}, x_{2}) = 1 - 2 x_{1} - 2 x_{2}$ labels $0$ by $1$ and $e_{1}, e_{2}$ by $0$ . The proof below handles arbitrary $p$ and all labelings algebraically; it does not rely on the sketch.

Example references

Mohri et al., Example 3.12 and Theorem 3.13: affine hyperplanes in $R^{p}$ have VC dimension $p + 1$ .

Facts & Assumptions

Given: The class $H_{p}$ of affine halfspace classifiers described in the Example.

[F1]

A finite indexed tuple is shattered exactly when every binary labeling occurs. Indexed shattering and VC dimension of a binary class

[F2]

For $k = p$ and $k = p + 1$ , reindex the supplier's basis vectors by $i \mapsto i - 1$ , as in the Example. The resulting local vectors $e_{1}, \dots, e_{k}$ form a basis of $R^{k}$ and every vector is its coordinate linear combination. The standard list $e : n \to F^{n}$ with $e_{i} (i) = 1_{F}$ and $e_{i} (j) = 0_{F}$ for $j \neq i$ is an ordered basis of $F^{n}$ ; hence $\dim_{F} F^{n} = n$ , and $F^{0}$ is the zero space with basis $\emptyset$ and dimension $0$

[F3]

Every linearly independent subset of $R^{p + 1}$ has at most $p + 1$ elements, because the $p + 1$ standard coordinate vectors span that space. If $V$ has a spanning set with $n$ elements, then every linearly independent subset of $V$ is finite with at most $n$ elements; in particular $V$ has no linearly independent subset equinumerous with $N$

[F4]

A finite list is linearly independent exactly when it is injective and its image is a linearly independent subset. Finite sums re-indexed along an injection, with a zero term deleted, and concatenated; and the closure properties of linear independence: an independent list is injective and never $0_{V}$ , its sublists are independent, a list is independent exactly when it is injective with linearly independent image, and every subset of a linearly independent set is linearly independent

[F5]

A finite list is linearly dependent exactly when it has a scalar relation equal to zero with at least one nonzero coefficient. Linear independence: a finite list $v : n \to V$ is independent when $\sum_{i < n} λ_{i} v_{i} = 0_{V}$ forces every $λ_{i} = 0_{F}$ , and a subset $S \subseteq V$ is independent when every injective finite list into $S$ is independent

Verification

1.1F1F2givenconstruct

The $p + 1$ points $0, e_{1}, \dots, e_{p}$ are shattered. Given arbitrary labels $y_{0}, \dots, y_{p} \in {0, 1}$ , set $s_{i} = 2 y_{i} - 1$ , $b = s_{0}$ , and $w_{i} = s_{i} - s_{0}$ . The affine score $f (x) = w \cdot x + b$ then satisfies $f (0) = s_{0}$ and $f (e_{i}) = s_{i}$ ; since these values are $+ 1$ or $- 1$ , the rule $h (x) = 1 {f (x) \geq 0}$ realizes exactly the chosen labels. Thus the VC dimension is at least $p + 1$ .

1.2F1F3F4F5givenchooseconstructalgebra

Take any $p + 2$ indexed points $x_{1}, \dots, x_{p + 2} \in R^{p}$ . The augmented vectors $(x_{i}, 1) \in R^{p + 1}$ form a list of $p + 2$ vectors. If the list were linearly independent, [F4] would make its image a linearly independent set of $p + 2$ distinct vectors, contradicting [F3]. [F3, F4] Hence the list is dependent, and [F5] gives real coefficients $a_{i}$ , not all zero, with $\sum_{i} a_{i} (x_{i}, 1) = 0$ , equivalently $\sum_{i} a_{i} x_{i} = 0$ and $\sum_{i} a_{i} = 0$ . Both positive and negative coefficients occur. Label $x_{i}$ by $1$ when $a_{i} > 0$ and by $0$ when $a_{i} < 0$ (choose either label when $a_{i} = 0$ ). If an affine score $f (x) = w \cdot x + b$ realized this labeling, then $a_{i} f (x_{i}) \geq 0$ for every positive coefficient and $a_{i} f (x_{i}) > 0$ for every negative coefficient, because label $0$ means $f (x_{i}) < 0$ . Therefore $\sum_{i} a_{i} f (x_{i}) > 0$ , contradicting $\sum_{i} a_{i} f (x_{i}) = w \cdot \sum_{i} a_{i} x_{i} + b \sum_{i} a_{i} = 0$ . No $p + 2$ -tuple is shattered, so the VC dimension is at most $p + 1$ .

2.1step 1.1step 1.2∎

Steps 1.1 and 1.2 give matching lower and upper bounds, proving $VCdim (H_{p}) = p + 1$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

35 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., Example 3.12 and Theorem 3.13 (standard reference, not scraped)