45:"/_next/static/chunks/33yus346z0l_n.js" 46:"/_next/static/chunks/2j22cxchii_xx.js" 47:"/_next/static/chunks/0iv56yrji_20j.js" 48:"/_next/static/chunks/32izpn90gvm22.js" 49:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4a:"/_next/static/chunks/1z-pox7hqp2x3.js" 4b:"/_next/static/chunks/20w4eaqlekefm.js" 4c:"/_next/static/chunks/1tn-0fivsxsv1.js" 4d:"/_next/static/chunks/09nq57stwzkgf.js" 4e:"/_next/static/chunks/3m1xjj5kw5fie.js" 4f:"/_next/static/chunks/0gafyzg9j9yqj.js" 50:"/_next/static/chunks/3k2gyg36fnag_.js" 51:"/_next/static/chunks/3bgoyiso1rhn7.js" 52:"/_next/static/chunks/3cstd6xzfli_o.js" 53:"/_next/static/chunks/253gnmj0-cj17.js" 54:"/_next/static/chunks/0hlb44ca7-4a2.js" 55:"/_next/static/chunks/20329i6m_04t6.js" 56:"/_next/static/chunks/40mq7ggq-ozo4.js" 57:"/_next/static/chunks/082jo-0ajazgr.js" 58:"/_next/static/chunks/2ozcrjb_hh74t.js" 59:"/_next/static/chunks/01a-3hvnqu8wl.js" 5a:"/_next/static/chunks/05i8en-x14ibi.js" 5b:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5c:"/_next/static/chunks/2k8pepwc4pxns.js" 5d:"/_next/static/chunks/0wa9m1-tphf9u.js" 5e:"/_next/static/chunks/30jdm3dwz834g.js" 5f:"/_next/static/chunks/0k9bl6dipnsvu.js" 60:"/_next/static/chunks/18ggtgz2yf759.js" 61:"/_next/static/chunks/0i3-eynrkvqi7.js" 62:I[593304,["$2a","$2b","$2c","$2d","$2e","$2f","$45","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61"],"OwnedHydration"] 63:T4d3,**Case 1: A Single Point** For any single point $\mathbf{x}_1$, linear classifiers can trivially shatter it: - Label +1: Use any line with $\mathbf{x}_1$ on the positive side - Label -1: Use any line with $\mathbf{x}_1$ on the negative side ✓ All $2^1 = 2$ dichotomies achievable. **Case 2: Two Points** For two distinct points $\{\mathbf{x}_1, \mathbf{x}_2\}$: - $(+1, +1)$: Draw a line with both points on the positive side - $(-1, -1)$: Draw a line with both points on the negative side - $(+1, -1)$: Draw a line separating them with $\mathbf{x}_1$ on the + side - $(-1, +1)$: Draw a line separating them with $\mathbf{x}_2$ on the + side ✓ All $2^2 = 4$ dichotomies achievable. **Case 3: Three Points** This is where geometry becomes critical. For three points $\{\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\}$: *If the points are collinear (lie on a line):* The labeling $(+1, -1, +1)$ cannot be achieved—a line cannot separate the middle point from both endpoints. ✗ Cannot shatter collinear points. *If the points form a triangle (general position):* All 8 dichotomies are achievable by appropriately orienting the separating line. ✓ Linear classifiers shatter any 3 points in general position in $\mathbb{R}^2$.64:T79f,import numpy as np from itertools import product from typing import List, Tuple, Callable def can_shatter_linear(points: np.ndarray) -> bool: """ Check if linear classifiers can shatter the given 2D points. Uses linear separability testing for each dichotomy. Args: points: Array of shape (n_points, 2) Returns: True if linear classifiers shatter this point set """ n = len(points) # Generate all 2^n possible labelings for labels in product([-1, 1], repeat=n): labels = np.array(labels) # Check if this labeling is linearly separable if not is_linearly_separable(points, labels): return False return True def is_linearly_separable(X: np.ndarray, y: np.ndarray) -> bool: """ Check if points X with labels y are linearly separable. Uses linear programming or perceptron convergence. """ from scipy.optimize import linprog n, d = X.shape # Formulate as LP: find w, b such that y_i(w·x_i + b) >= 1 # Variables: [w_1, w_2, ..., w_d, b] # Constraint: y_i * (sum_j w_j * x_ij + b) >= 1 # Rewrite: -y_i * sum_j w_j * x_ij - y_i * b <= -1 A_ub = np.zeros((n, d + 1)) for i in range(n): A_ub[i, :d] = -y[i] * X[i] A_ub[i, d] = -y[i] b_ub = -np.ones(n) c = np.zeros(d + 1) # We just need feasibility result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='highs') return result.success # Example: Test shattering for 3 points triangle = np.array([ [0.0, 0.0], [1.0, 0.0], [0.5, 1.0] ]) print(f"Can linear classifiers shatter 3 points in triangle? {can_shatter_linear(triangle)}") # Output: True # Example: Test with 4 points square = np.array([ [0.0, 0.0], [1.0, 0.0], [1.0, 1.0], [0.0, 1.0] ]) print(f"Can linear classifiers shatter 4 points in square? {can_shatter_linear(square)}") # Output: False43:["$","$L62",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792298948640,"state":{"data":{"json":{"id":"seed_a9019c835ffdeeabaad537588a984bc7","slug":"vc-dimension","category":"Statistical Learning Theory","topic":"VC Dimension","title":"VC Dimension and Model Complexity","description":"Master the Vapnik-Chervonenkis dimension—the fundamental measure of hypothesis class complexity that underlies generalization theory. Learn to compute VC dimension, derive generalization bounds, and apply structural risk minimization for principled model selection.","difficulty":"ADVANCED","estimatedMinutes":90,"pages":[{"id":"seed_837b0197b58f58800b6929d82917562c","title":"Shattering: The Foundation of VC Theory","order":0,"content":[{"id":"opening-hook","title":"The Expressiveness Question","content":[{"data":{"content":"In machine learning, we constantly face a fundamental tradeoff: **expressive models can fit training data perfectly but may fail to generalize, while simple models generalize well but may underfit**. To navigate this tradeoff rigorously, we need a precise mathematical measure of a hypothesis class's *expressive power*—its ability to represent arbitrary patterns.\n\nThe concept of **shattering** provides exactly this measure. It answers a seemingly simple but profound question: *Given a set of data points, can our hypothesis class realize every possible way of labeling those points?*\n\nThis question lies at the heart of statistical learning theory and leads directly to the celebrated **Vapnik-Chervonenkis (VC) dimension**, which quantifies hypothesis class complexity in a way that directly connects to generalization guarantees."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will deeply understand what it means for a hypothesis class to shatter a set of points. You'll develop geometric and combinatorial intuition for shattering, see concrete examples across different hypothesis classes, and understand why shattering is the key to measuring model complexity for generalization analysis.","variant":"info"},"type":"callout"}]},{"id":"dichotomy-concept","title":"Dichotomies: The Building Blocks of Shattering","content":[{"data":{"content":"Before defining shattering, we need the concept of a **dichotomy**. This fundamental notion captures how a hypothesis partitions a finite set of points into two classes.\n\n**Formal Definition:**\n\nLet $\\mathcal{H}$ be a hypothesis class consisting of functions $h: \\mathcal{X} \\to \\{-1, +1\\}$ mapping from some input space $\\mathcal{X}$ to binary labels. Given a finite set of points $S = \\{x_1, x_2, \\ldots, x_m\\} \\subset \\mathcal{X}$, each hypothesis $h \\in \\mathcal{H}$ induces a **labeling** or **dichotomy** of $S$:\n\n$$h|_S = (h(x_1), h(x_2), \\ldots, h(x_m)) \\in \\{-1, +1\\}^m$$\n\nThis is simply the vector of predictions that $h$ makes on the points in $S$. Different hypotheses in $\\mathcal{H}$ may induce the same dichotomy, or they may induce different dichotomies."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Intuition: Dichotomies as Colorings","content":"Think of a dichotomy as a way to 'color' the points in S with two colors (say, red and blue). Each hypothesis h assigns a color to each point. The question is: how many different colorings can our hypothesis class produce? If H can produce all possible colorings, it has maximum expressive power over S.","variant":"tip"},"type":"callout"},{"data":{"content":"**The Set of Achievable Dichotomies:**\n\nThe set of all dichotomies that $\\mathcal{H}$ can induce on $S$ is denoted:\n\n$$\\mathcal{H}(S) = \\{(h(x_1), \\ldots, h(x_m)) : h \\in \\mathcal{H}\\}$$\n\nThis is the **restriction** of $\\mathcal{H}$ to the set $S$. Note that $\\mathcal{H}(S) \\subseteq \\{-1, +1\\}^m$, meaning the number of achievable dichotomies satisfies:\n\n$$|\\mathcal{H}(S)| \\leq 2^m$$\n\nThe upper bound $2^m$ represents all possible binary labelings of $m$ points. A hypothesis class that achieves this upper bound for a particular set $S$ has complete expressive freedom over $S$—and this is precisely what shattering means."},"type":"text"},{"data":{"input":"Consider two points: $S = \\{1, 3\\}$. What dichotomies can $\\mathcal{H}_{\\text{thresh}}$ achieve?","title":"Example: Threshold Classifiers on the Real Line","output":"• $\\theta = 0$: Both points ≥ θ → $(+1, +1)$\n• $\\theta = 2$: Point 1 < θ, point 3 ≥ θ → $(-1, +1)$ \n• $\\theta = 4$: Both points < θ → $(-1, -1)$\n\nBut **no threshold can achieve** $(+1, -1)$ because threshold classifiers label all points above the threshold as +1 and all below as -1. They cannot label a smaller point as +1 and a larger point as -1.\n\nSo $|\\mathcal{H}_{\\text{thresh}}(S)| = 3 < 4 = 2^2$.","description":"Consider $\\mathcal{X} = \\mathbb{R}$ and the hypothesis class of threshold classifiers:\n\n$\\mathcal{H}_{\\text{thresh}} = \\{h_\\theta : \\theta \\in \\mathbb{R}\\}$ where $h_\\theta(x) = \\begin{cases} +1 & \\text{if } x \\geq \\theta \\\\ -1 & \\text{if } x < \\theta \\end{cases}$","explanation":"Threshold classifiers cannot shatter any set of 2 points because they impose a monotonic structure on the labeling."},"type":"example"}],"titleType":"number","titleNumber":1},{"id":"shattering-definition","title":"The Formal Definition of Shattering","content":[{"data":{"content":"We now present the central definition that underpins VC theory.\n\n**Definition (Shattering):**\n\nA hypothesis class $\\mathcal{H}$ **shatters** a finite set $S = \\{x_1, \\ldots, x_m\\} \\subset \\mathcal{X}$ if $\\mathcal{H}$ can realize every possible dichotomy of $S$. Formally:\n\n$$\\mathcal{H} \\text{ shatters } S \\iff |\\mathcal{H}(S)| = 2^m$$\n\nEquivalently, for every labeling $(y_1, \\ldots, y_m) \\in \\{-1, +1\\}^m$, there exists some $h \\in \\mathcal{H}$ such that:\n\n$$h(x_i) = y_i \\quad \\text{for all } i = 1, \\ldots, m$$"},"type":"text"},{"data":{"icon":"Info","title":"The Power of Shattering","content":"If H shatters S, then H can perfectly memorize any possible labeling of S, regardless of whether that labeling has any structure or pattern. This is both powerful (high expressiveness) and dangerous (potential for overfitting). Shattering captures the ability to fit arbitrary noise.","variant":"note"},"type":"callout"},{"data":{"content":"**Key Properties of Shattering:**\n\n1. **Set-dependent**: Whether $\\mathcal{H}$ shatters a set depends on *which* points are in the set, not just how many.\n\n2. **Subset monotonicity**: If $\\mathcal{H}$ shatters $S$, it also shatters every subset $S' \\subseteq S$. (Proof: Restricting dichotomies to a subset preserves all labelings.)\n\n3. **Existence vs. universality**: We only require *existence* of a shattered set of size $m$—there may be many sets of size $m$ that $\\mathcal{H}$ *cannot* shatter.\n\n4. **Location matters**: Two sets of the same size may have very different shatterability properties based on where the points are positioned."},"type":"text"},{"data":{"rows":[["1","2","Need both (+1) and (-1)","Any single point"],["2","4","Need all of (−−), (−+), (+−), (++)","Two distinct points"],["3","8","Need all 8 labelings","Three points in general position"],["4","16","Need all 16 labelings","Four points (often impossible)"],["m","2^m","Need all 2^m labelings","Exponentially harder"]],"caption":"Shattering Requirements for Different Set Sizes","headers":["Set Size m","Total Possible Dichotomies","Requirement to Shatter","Example (Points)"]},"type":"table"}],"titleType":"number","titleNumber":2},{"id":"geometric-intuition","title":"Geometric Intuition for Shattering","content":[{"data":{"content":"The most illuminating way to understand shattering is through geometric visualization. Consider the hypothesis class of **linear classifiers** (halfspaces) in $\\mathbb{R}^2$:\n\n$$\\mathcal{H}_{\\text{linear}} = \\{h_{\\mathbf{w},b} : \\mathbf{w} \\in \\mathbb{R}^2, b \\in \\mathbb{R}\\}$$\n\nwhere $h_{\\mathbf{w},b}(\\mathbf{x}) = \\text{sign}(\\mathbf{w}^\\top \\mathbf{x} + b)$.\n\nEach hypothesis corresponds to a line in $\\mathbb{R}^2$, with points on one side labeled +1 and points on the other labeled -1."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Visualizing Halfspaces","content":"Imagine a line sweeping through the plane. As you rotate and translate this line, you create different partitions of the plane. For a fixed set of points, each line orientation produces a dichotomy. The question is: can you achieve ALL possible dichotomies by appropriately positioning the line?","variant":"tip"},"type":"callout"},{"data":{"content":"$63"},"type":"text"},{"data":{"input":"Show that all 8 dichotomies are achievable with linear classifiers.","title":"Example: Shattering Three Points in the Plane","output":"• $(+,+,+)$: Line $y = -1$ (all above)\n• $(-,-,-)$: Line $y = 2$ (all below)\n• $(+,-,-)$: Line passing left of $\\mathbf{x}_1$, right of others\n• $(-,+,-)$: Line passing through region separating $\\mathbf{x}_2$\n• $(-,-,+)$: Horizontal line at $y = 0.5$ (only $\\mathbf{x}_3$ above)\n• $(+,+,-)$: Horizontal line at $y = 0.5$ (only $\\mathbf{x}_3$ below)\n• $(+,-,+)$: Line separating $\\mathbf{x}_2$ from $\\{\\mathbf{x}_1, \\mathbf{x}_3\\}$\n• $(-,+,+)$: Line separating $\\mathbf{x}_1$ from $\\{\\mathbf{x}_2, \\mathbf{x}_3\\}$","description":"Consider three points forming a triangle: $\\mathbf{x}_1 = (0,0)$, $\\mathbf{x}_2 = (1,0)$, $\\mathbf{x}_3 = (0.5, 1)$.","explanation":"For any triangle in the plane, every vertex can be isolated by an appropriate line, and every pair can be grouped together, enabling all 8 dichotomies."},"type":"example"},{"data":{"content":"**Case 4: Four Points**\n\nCan linear classifiers shatter *any* set of 4 points in $\\mathbb{R}^2$? The answer is **no**:\n\n*Convex hull argument:* Consider 4 points in general position forming a quadrilateral. Let's say they are the vertices of a convex quadrilateral. The diagonal labelings like $(+1, -1, +1, -1)$ (alternating around the quadrilateral) cannot be achieved by a single line.\n\n*One point inside:* If one point lies inside the convex hull of the other three, we cannot label it differently from all surrounding points.\n\nIn both cases, there exists at least one dichotomy that no linear classifier can achieve. Therefore:\n\n**Linear classifiers in $\\mathbb{R}^2$ cannot shatter any set of 4 points.**"},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Shattering Ceiling","content":"This illustrates a fundamental principle: every hypothesis class has a maximum set size it can shatter. For linear classifiers in ℝ², this maximum is 3. No matter how cleverly you position 4 points, a line cannot realize all 16 dichotomies. This maximum is exactly the VC dimension.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"shattering-examples","title":"Shattering Examples Across Hypothesis Classes","content":[{"data":{"content":"Let's systematically examine shattering behavior across different hypothesis classes to build intuition for how model structure affects expressive power."},"type":"text"},{"data":{"tabs":[{"id":"intervals","label":"Intervals on ℝ","content":[{"data":{"content":"**Interval Classifiers:**\n\n$\\mathcal{H}_{\\text{interval}} = \\{h_{a,b} : a \\leq b, a,b \\in \\mathbb{R}\\}$\n\nwhere $h_{a,b}(x) = +1$ if $x \\in [a,b]$ and $-1$ otherwise.\n\n**Analysis:**\n\n*Can we shatter 2 points?*\nYes! For $\\{x_1, x_2\\}$ with $x_1 < x_2$:\n- $(+,+)$: Interval $[x_1-\\epsilon, x_2+\\epsilon]$\n- $(-,-)$: Interval $[x_2+1, x_2+2]$ (disjoint from both)\n- $(+,-)$: Interval $[x_1-\\epsilon, x_1+\\epsilon]$ (contains only $x_1$)\n- $(-,+)$: Interval $[x_2-\\epsilon, x_2+\\epsilon]$ (contains only $x_2$)\n\n*Can we shatter 3 points?*\nNo! Consider $x_1 < x_2 < x_3$. The labeling $(+1, -1, +1)$ is impossible—an interval cannot contain $x_1$ and $x_3$ while excluding $x_2$.\n\n**Result:** Interval classifiers can shatter at most 2 points."},"type":"text"}],"titleIcon":"Target"},{"id":"rectangles","label":"Axis-Aligned Rectangles","content":[{"data":{"content":"**Axis-Aligned Rectangle Classifiers in $\\mathbb{R}^2$:**\n\n$\\mathcal{H}_{\\text{rect}} = \\{h_R : R = [a_1,b_1] \\times [a_2,b_2]\\}$\n\nwhere $h_R(\\mathbf{x}) = +1$ if $\\mathbf{x} \\in R$ and $-1$ otherwise.\n\n**Analysis:**\n\n*Can we shatter 4 points?*\nYes! Place four points at positions that can each be isolated:\n- $(1,0), (0,1), (-1,0), (0,-1)$\n\nAny subset can be captured by an appropriate rectangle.\n\n*Can we shatter 5 points?*\nNo! Consider 5 points where one lies in the convex hull of a subset. The diagonal configuration, or having a central point, prevents certain labelings.\n\n**Result:** Axis-aligned rectangles in $\\mathbb{R}^2$ have VC dimension 4."},"type":"text"}],"titleIcon":"Target"},{"id":"circles","label":"Circles in ℝ²","content":[{"data":{"content":"**Circle Classifiers (points inside labeled +1):**\n\n$\\mathcal{H}_{\\text{circle}} = \\{h_{c,r} : c \\in \\mathbb{R}^2, r > 0\\}$\n\nwhere $h_{c,r}(\\mathbf{x}) = +1$ if $\\|\\mathbf{x} - c\\| \\leq r$ and $-1$ otherwise.\n\n**Analysis:**\n\n*Can we shatter 3 points?*\nYes! For any 3 non-collinear points:\n- All combinations of 1, 2, or 3 points can be enclosed\n- Empty or all-exclusive uses a circle disjoint from all points\n\n*The geometric insight:*\nCircles have 3 degrees of freedom (center coordinates + radius), allowing them to match the 3-point shattering capability.\n\n**Result:** Circles in $\\mathbb{R}^2$ have VC dimension 3."},"type":"text"}],"titleIcon":"Target"},{"id":"sinusoids","label":"Sinusoidal Classifiers","content":[{"data":{"content":"**Sinusoidal Classifiers:**\n\n$\\mathcal{H}_{\\sin} = \\{h_\\omega : \\omega > 0\\}$\n\nwhere $h_\\omega(x) = \\text{sign}(\\sin(\\omega x))$.\n\n**A Surprising Result:**\n\nThis hypothesis class with a single parameter can shatter **arbitrarily large** finite sets!\n\n*Construction:* Given $m$ points $x_1 < x_2 < \\ldots < x_m$, for any labeling $(y_1, \\ldots, y_m)$, we can find $\\omega$ such that $\\sin(\\omega x_i)$ has the correct sign for each $i$.\n\nThe key is that as $\\omega \\to \\infty$, the sine function oscillates arbitrarily fast, passing through any desired sign pattern.\n\n**Result:** $\\mathcal{H}_{\\sin}$ has **infinite VC dimension** despite having only one parameter!\n\n*Implication:* Number of parameters is NOT a reliable measure of complexity."},"type":"text"}],"titleIcon":"Target"}],"defaultTab":"intervals"},"type":"tabs"},{"data":{"icon":"AlertCircle","title":"Parameters ≠ Complexity","content":"The sinusoidal example reveals a crucial insight: the number of parameters in a model does NOT determine its capacity to overfit. A single-parameter sinusoidal classifier has infinite VC dimension! This is why we need VC dimension rather than parameter counting to measure true model complexity.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"growth-function","title":"The Growth Function: Quantifying Expressiveness","content":[{"data":{"content":"While shattering is a binary concept (a set is either shattered or not), we often want to quantify *how many* dichotomies a hypothesis class can achieve. This leads to the **growth function** (also called the **shattering coefficient**).\n\n**Definition (Growth Function):**\n\nFor a hypothesis class $\\mathcal{H}$, the growth function $\\Pi_\\mathcal{H}: \\mathbb{N} \\to \\mathbb{N}$ is defined as:\n\n$$\\Pi_\\mathcal{H}(m) = \\max_{S \\subset \\mathcal{X}, |S| = m} |\\mathcal{H}(S)|$$\n\nThis is the maximum number of dichotomies that $\\mathcal{H}$ can induce on any set of $m$ points."},"type":"text"},{"data":{"content":"**Properties of the Growth Function:**\n\n1. **Upper bound**: $\\Pi_\\mathcal{H}(m) \\leq 2^m$ for all $m$\n\n2. **Monotonicity**: While $\\Pi_\\mathcal{H}(m)$ is non-decreasing, the *rate* of growth can vary\n\n3. **Shattering connection**: $\\mathcal{H}$ shatters some set of size $m$ if and only if $\\Pi_\\mathcal{H}(m) = 2^m$\n\n4. **VC dimension connection**: If $\\text{VCdim}(\\mathcal{H}) = d$, then:\n - $\\Pi_\\mathcal{H}(m) = 2^m$ for $m \\leq d$\n - $\\Pi_\\mathcal{H}(m) < 2^m$ for $m > d$"},"type":"text"},{"data":{"rows":[["Positive rays on ℝ","1","m + 1","Linear growth"],["Intervals on ℝ","2","m(m-1)/2 + m + 1 = O(m²)","Quadratic growth"],["Halfspaces in ℝ^d","d + 1","Σᵢ₌₀ᵈ C(m,i) = O(m^d)","Polynomial (degree d)"],["Finite class |H|=N","≤ log₂(N)","min(N, 2^m)","Bounded by class size"],["Sinusoids sin(ωx)","∞","2^m for all m","Exponential (maximal)"]],"caption":"Growth Functions for Different Hypothesis Classes","headers":["Hypothesis Class","VC Dimension","Growth Function Π(m)","Behavior"]},"type":"table"},{"data":{"icon":"Lightbulb","title":"The Sauer-Shelah Lemma","content":"A fundamental result (Sauer-Shelah Lemma) shows that once the VC dimension is finite (say d), the growth function is bounded by a polynomial: Π(m) ≤ Σᵢ₌₀ᵈ C(m,i) ≤ (em/d)^d. This polynomial bound is crucial for deriving generalization guarantees—it ensures that the hypothesis class cannot be too complex.","variant":"tip"},"type":"callout"},{"data":{"content":"**Why the Growth Function Matters:**\n\nThe growth function appears directly in generalization bounds. Roughly speaking, the sample complexity and generalization error depend on $\\Pi_\\mathcal{H}(m)$ or its logarithm. When $\\Pi_\\mathcal{H}(m)$ grows polynomially rather than exponentially, we can learn with polynomial sample complexity.\n\nThis is the key insight: **finite VC dimension implies polynomial growth, which implies learnability**."},"type":"text"}],"titleType":"number","titleNumber":5},{"id":"shattering-and-learning","title":"Why Shattering Matters for Learning","content":[{"data":{"content":"The concept of shattering might seem abstract, but it has profound implications for machine learning. Understanding shattering answers the fundamental question: *Why do some models generalize while others memorize?*\n\n**The Overfitting Connection:**\n\nIf $\\mathcal{H}$ can shatter a large set, it means $\\mathcal{H}$ can perfectly fit *any* labeling of that set—including completely random labels with no underlying pattern. This ability to fit noise is precisely what we mean by overfitting.\n\nConsider an extreme case: if $\\mathcal{H}$ shatters a training set of size $m$, then for any target function $f$ (even if $f$ generates labels randomly), there exists $h \\in \\mathcal{H}$ with zero training error. But such an $h$ has learned nothing—it has merely memorized."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Price of Shattering","content":"If your hypothesis class can shatter your training set, you can achieve zero training error on ANY labeling—including pure noise. This is not a feature; it's a liability. It means your training error tells you nothing about your test error.","variant":"warning"},"type":"callout"},{"data":{"content":"**The Generalization Intuition:**\n\nThe more points $\\mathcal{H}$ can shatter, the more freedom it has to fit arbitrary patterns. This freedom requires more data to distinguish genuine patterns from noise. The VC dimension quantifies this:\n\n- **If VCdim($\\mathcal{H}$) = d**, you need roughly $O(d)$ samples to learn reliably\n- **If VCdim($\\mathcal{H}$) = ∞**, no finite sample is sufficient for guaranteed generalization\n\nThis gives the first principled answer to 'how much data do I need?'—it depends on the VC dimension of your hypothesis class."},"type":"text"},{"data":{"left":[{"data":{"items":["Cannot shatter arbitrarily large sets","Growth function is polynomial","Generalization bounds exist","PAC-learnable with finite samples","Training error is meaningful signal"],"title":{"icon":"CheckCircle","text":"Finite VC Dimension (Good)","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Can shatter any finite set","Growth function is exponential","No uniform generalization guarantees","May require infinite samples","Training error can be misleading"],"title":{"icon":"XCircle","text":"Infinite VC Dimension (Risky)","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**The Fundamental Theorem Preview:**\n\nWe're building toward one of the deepest results in learning theory:\n\n**A hypothesis class $\\mathcal{H}$ is PAC-learnable if and only if VCdim($\\mathcal{H}$) is finite.**\n\nThis theorem (which we'll prove in later pages) shows that shattering—and its quantification via VC dimension—is not just one way to measure complexity, but *the* fundamental measure that determines learnability."},"type":"text"}],"titleType":"number","titleNumber":6},{"id":"computational-perspective","title":"Computational Considerations","content":[{"data":{"content":"While shattering is a theoretical concept, understanding its computational aspects helps bridge theory and practice.\n\n**Verifying Shattering:**\n\nGiven a specific set $S$ and hypothesis class $\\mathcal{H}$, how do we check if $\\mathcal{H}$ shatters $S$?\n\n*Naive approach:* Enumerate all $2^{|S|}$ labelings and verify each is realizable. This is exponential in $|S|$.\n\n*For structured $\\mathcal{H}$:* Often we can use geometric or algebraic arguments. For linear classifiers, this reduces to checking linear separability of various point subsets."},"type":"text"},{"data":{"fileName":"shattering_verification.py","languages":[{"code":"$64","name":"Python","value":"python"}],"showLineNumbers":true},"type":"code"},{"data":{"icon":"Info","title":"Complexity of Determining VC Dimension","content":"In general, computing the VC dimension of an arbitrary hypothesis class is computationally hard (coNP-complete for neural networks, for example). However, for well-structured classes like linear classifiers, kernel methods, and polynomial classifiers, the VC dimension can be computed or bounded analytically.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: The Power of Shattering","content":[{"data":{"content":"We've developed a deep understanding of shattering—the foundation for VC theory and generalization analysis."},"type":"text"},{"data":{"type":"ordered","items":["**Dichotomies** are the labelings a hypothesis class can induce on a finite point set. The set $\\mathcal{H}(S)$ captures all achievable labelings.","**Shattering** occurs when $\\mathcal{H}$ can realize all $2^m$ dichotomies of an $m$-point set—complete expressive freedom over that set.","**Geometry determines shattering.** Point positions matter: collinear points cannot be shattered by linear classifiers even though non-collinear points can.","**The growth function** $\\Pi_\\mathcal{H}(m)$ quantifies the maximum dichotomies as a function of set size.","**Parameters ≠ complexity.** Single-parameter sinusoids have infinite VC dimension; multi-parameter linear classifiers have finite VC dimension.","**Shattering connects to overfitting.** The ability to shatter large sets means the ability to memorize noise."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nWith shattering firmly understood, we're ready to define the **VC dimension** formally—the largest set size a hypothesis class can shatter. This single number summarizes the expressive power of a hypothesis class and directly determines sample complexity and generalization bounds."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand shattering—the core concept underlying VC theory. You can analyze whether a hypothesis class shatters a given point set, compute dichotomies, and understand why shattering ability determines a model's capacity to overfit. Next, we'll formalize the VC dimension and explore its properties.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_0322860aedd69fdb804fbe7aec5e68e3","title":"VC Dimension: Formal Definition and Properties","order":1,"content":null,"isLocked":true},{"id":"seed_15d60f4805b3fc39c9218948a64ceccc","title":"VC Dimension of Linear Classifiers","order":2,"content":null,"isLocked":true},{"id":"seed_47246e73be4769f88b5b1c581d4db307","title":"Generalization Bounds from VC Dimension","order":3,"content":null,"isLocked":true},{"id":"seed_34b2d48d22ea18b27e951e037b0ba7d3","title":"Structural Risk Minimization","order":4,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792298948639,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"vc-dimension"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"vc-dimension\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298948640,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792298948637,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_a9019c835ffdeeabaad537588a984bc7"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_a9019c835ffdeeabaad537588a984bc7\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298948640,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792298948637,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0322860aedd69fdb804fbe7aec5e68e3"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_0322860aedd69fdb804fbe7aec5e68e3\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298948640,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792298948637,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0322860aedd69fdb804fbe7aec5e68e3"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_0322860aedd69fdb804fbe7aec5e68e3\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298948640,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792298948637,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0322860aedd69fdb804fbe7aec5e68e3"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_0322860aedd69fdb804fbe7aec5e68e3\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792298948640,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_0322860aedd69fdb804fbe7aec5e68e3","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_0322860aedd69fdb804fbe7aec5e68e3\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@65"}]},"children":"$L66"}]