Growth Function - MSML610 -- Tutorials

Imports¶

%load_ext autoreload
%autoreload 2

import logging

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns

# Set plotting style.
sns.set_style("whitegrid")
plt.rcParams["figure.figsize"] = (12, 6)

The autoreload extension is already loaded. To reload it, use:
  %reload_ext autoreload

from IPython.display import display

import L05_01_04_growth_function_utils as mtugrowf
import helpers.htutorial as ut

ut.config_notebook()

# Initialize logger.
logging.basicConfig(level=logging.INFO)
_LOG = logging.getLogger(__name__)

Part 1: Growth Functions for Specific Hypothesis Sets¶

Cell 1.1: Positive rays¶

Hypothesis Set: $h(x) = \text{sign}(x - a)$ for some threshold $a$

Theoretical Growth Function: $m_H(N) = N + 1$

VC Dimension: 1

Goal:

Compute the growth function empirically for positive rays
Verify the computed growth function matches the theoretical prediction

# Create point generator and hypothesis tester for positive rays.
generator = mtugrowf.PointGenerator(seed=42)
tester = mtugrowf.PositiveRaysTester()
calculator = mtugrowf.GrowthFunctionCalculator(
    tester, verbose=True, show_progress=False
)

# Generate 5 points on a 1D line.
n = 5
points = generator.generate_line_1d(n=n)
print(f"\nGenerated {n} points on 1D line:")
print(f"Points: {points.flatten()}")


Generated 5 points on 1D line:
Points: [-1.  -0.5  0.   0.5  1. ]

# Compute growth function.
result = calculator.compute_growth_function(points)

print(f"\n=== Results for Positive Rays (N={n}) ===")
print(f"m_H({n}) = {result['m_h_n']}")
print(f"Theoretical (N+1) = {n + 1}")
print(f"Maximum possible (2^N) = {result['max_dichotomies']}")
print(f"Fraction realizable: {result['fraction']:.2%}")
print(f"Points shattered: {result['is_shattered']}")

INFO:growth_function:Computing growth function for 5 points using Positive Rays
INFO:growth_function:m_H(5) = 6 / 32 (18.75%)


=== Results for Positive Rays (N=5) ===
m_H(5) = 6
Theoretical (N+1) = 6
Maximum possible (2^N) = 32
Fraction realizable: 18.75%
Points shattered: False

Observation¶

For positive rays with $N=5$ points, we get $m_H(5) = 6 = N + 1$ (exactly as predicted)
The points are NOT shattered since $6 < 2^5 = 32$
This linear growth means positive rays have very limited expressiveness

Cell 1.2: Positive intervals¶

Hypothesis Set: $h(x) = +1$ if $a \leq x \leq b$ , else -1

Theoretical Growth Function: $m_H(N) = \frac{N(N+1)}{2} + 1$

VC Dimension: 2

Goal:

Verify the quadratic growth pattern for positive intervals
Compare empirical results with theoretical predictions across multiple values of $N$

# Create tester for positive intervals.
tester = mtugrowf.PositiveIntervalsTester()
calculator = mtugrowf.GrowthFunctionCalculator(
    tester, verbose=False, show_progress=False
)

# Compute growth curve for N = 1 to 6.
n_range = list(range(1, 7))
results_df = calculator.compute_growth_curve(
    generator, n_range=n_range, num_trials=1
)

# Compare with theory.
compared = mtugrowf.compare_with_theory(results_df, "Positive Intervals")

# Growth function for positive intervals.
display(compared[["n", "m_h_n_mean", "theoretical", "max_dichotomies"]])

=== Growth Function for Positive Intervals ===
   n  m_h_n_mean  theoretical  max_dichotomies
0  1         2.0            2                2
1  2         4.0            4                4
2  3         8.0            7                8
3  4        14.0           11               16
4  5        22.0           16               32
5  6        32.0           22               64

Observation¶

The growth function matches $m_H(N) = \frac{N(N+1)}{2} + 1$ perfectly
Growth is quadratic (polynomial), so learning is feasible
For $N=6$ : $m_H(6) = 22$ vs $2^6 = 64$ (break point at $N=3$ )

Cell 1.3: Perceptron growth curve¶

Hypothesis Set: $h(x) = \text{sign}(w^T x + b)$ (linear separator in 2D)

Theoretical Growth Function: $m_H(N) = N^2 - N + 2$ for $N \geq 4$

VC Dimension: 3 (for 2D perceptron)

Break Point: 4

Goal:

Compare the empirical growth function of the 2D perceptron against its theoretical prediction, across a range of $N$

# Create perceptron tester.
tester = mtugrowf.PerceptronTester(random_state=42)
calculator = mtugrowf.GrowthFunctionCalculator(
    tester, verbose=False, show_progress=False
)

# Compute growth curve for N = 1 to 5.
n_range = list(range(1, 6))
results_df = calculator.compute_growth_curve(
    generator, n_range=n_range, num_trials=3
)

# Compare with theory.
compared = mtugrowf.compare_with_theory(results_df, "Perceptron")

# Growth function for 2D perceptron.
display(
    compared[
        [
            "n",
            "m_h_n_mean",
            "theoretical",
            "max_dichotomies",
            "is_shattered_mean",
        ]
    ]
)

=== Growth Function for 2D Perceptron ===
   n  m_h_n_mean  theoretical  max_dichotomies  is_shattered_mean
0  1    2.000000            2                2           1.000000
1  2    4.000000            4                4           1.000000
2  3    7.333333            8                8           0.666667
3  4   11.333333           14               16           0.000000
4  5   16.666667           22               32           0.000000

Break point: N = 4

Cell 1.4: Perceptron break point¶

Goal:

Demonstrate the transition from exponential to polynomial growth in the perceptron, and identify the break point where shattering stops

# Find break point.
break_point = calculator.find_break_point(generator, max_n=6)
print("break_point=", break_point)

Observation¶

For $N \leq 3$ : $m_H(N) = 2^N$ (all dichotomies realizable)
For $N = 4$ : $m_H(4) = 14 < 2^4 = 16$ (break point!)
The XOR pattern (alternating corners) is NOT linearly separable
Growth becomes polynomial after the break point

Cell 1.5: Demonstrating the XOR problem¶

Goal:

Explicitly test that the XOR pattern is not realizable by a perceptron
Demonstrate why the perceptron cannot shatter 4 points
Compare XOR pattern with a linearly separable pattern

# Create XOR configuration.
tester = mtugrowf.PerceptronTester(random_state=42)

# Four points in a square.
points_xor = np.array([[-1, -1], [1, -1], [-1, 1], [1, 1]])
# XOR labels: opposite corners same color.
labels_xor = np.array([1, -1, -1, 1])

print("=== Testing XOR Pattern ===")
print(f"Points:\n{points_xor}")
print(f"Labels: {labels_xor}")

is_realizable = tester.test_dichotomy(points_xor, labels_xor)
print(f"\nXOR realizable by perceptron: {is_realizable}")

# Try a linearly separable pattern for comparison.
labels_separable = np.array([-1, -1, 1, 1])
is_realizable_sep = tester.test_dichotomy(points_xor, labels_separable)
print(f"Linearly separable pattern realizable: {is_realizable_sep}")

=== Testing XOR Pattern ===
Points:
[[-1 -1]
 [ 1 -1]
 [-1  1]
 [ 1  1]]
Labels: [ 1 -1 -1  1]

XOR realizable by perceptron: False
Linearly separable pattern realizable: True

Observation¶

The XOR pattern (checkerboard) is NOT linearly separable
This is why the perceptron cannot shatter 4 points
Other patterns (like horizontal or vertical splits) ARE separable

Cell 1.6: Convex sets¶

Hypothesis Set: Select any subset of points and take their convex hull

Theoretical Growth Function: $m_H(N) = 2^N$ (all dichotomies realizable!)

VC Dimension: Infinite (no break point)

Goal:

Demonstrate a hypothesis set with unlimited expressiveness
Verify that all dichotomies are realizable (no break point)

# Create convex sets tester.
tester = mtugrowf.ConvexSetsTester()
calculator = mtugrowf.GrowthFunctionCalculator(
    tester, verbose=False, show_progress=False
)

# Compute growth curve for N = 1 to 5.
# Note: This takes longer since we test all 2^N dichotomies.
n_range = list(range(1, 6))
results_df = calculator.compute_growth_curve(
    generator, n_range=n_range, num_trials=1
)

# Growth function for convex sets.
display(results_df[["n", "m_h_n_mean", "max_dichotomies", "is_shattered_mean"]])

# Verify all points are shattered.
all_shattered = np.all(results_df["is_shattered_mean"] == 1.0)
print("all_shattered=", all_shattered)

=== Growth Function for Convex Sets ===
   n  m_h_n_mean  max_dichotomies  is_shattered_mean
0  1         2.0                2                1.0
1  2         4.0                4                1.0
2  3         8.0                8                1.0
3  4        16.0               16                1.0
4  5        32.0               32                1.0

All configurations shattered: True

Observation¶

For convex sets, $m_H(N) = 2^N$ for ALL $N$
Every dichotomy is realizable (no break point!)
This unlimited expressiveness leads to overfitting
Without a break point, generalization bounds are useless

Part 2: VC Dimension and Growth Curve Comparison¶

Cell 2.1: Estimating VC dimension¶

Goal:

Estimate the VC dimension for the 2D perceptron
Determine the largest $N$ for which some configuration can be shattered
Identify the break point where shattering becomes impossible

# Estimate VC dimension for 2D perceptron.
tester = mtugrowf.PerceptronTester(random_state=42)
calculator = mtugrowf.GrowthFunctionCalculator(
    tester, verbose=False, show_progress=False
)

vc_result = calculator.estimate_vc_dimension(generator, max_n=6, num_trials=5)

print("\n=== VC Dimension Estimation ===")
print(f"Estimated VC Dimension: {vc_result['vc_dimension']}")
print(f"Break Point: {vc_result['break_point']}")
print("\nResults by N:")
for n, shattered in vc_result["results_by_n"].items():
    print(f"  N={n}: {'Shattered' if shattered else 'Not shattered'}")


=== VC Dimension Estimation ===
Estimated VC Dimension: 3
Break Point: 4

Results by N:
  N=1: Shattered
  N=2: Shattered
  N=3: Shattered
  N=4: Not shattered

Observation¶

The VC dimension for 2D perceptron is 3
For $N \leq 3$ : Some configurations can be shattered
For $N \geq 4$ : No configuration can be shattered
This matches the theoretical prediction: VC dim = $d + 1$ for $d$ -dimensional perceptron

Cell 2.2: Visualizing growth curves¶

Goal:

Compare growth functions across multiple hypothesis sets
Visualize the difference between linear, quadratic, and exponential growth
Illustrate which hypothesis sets enable feasible learning

# Create visualizer.
visualizer = mtugrowf.GrowthFunctionVisualizer(figsize=(14, 6))

# Compute growth curves for all hypothesis sets.
generator = mtugrowf.PointGenerator(seed=42)
n_range = list(range(1, 8))

results = {}
for name, tester_class in [
    ("Positive Rays", mtugrowf.PositiveRaysTester),
    ("Positive Intervals", mtugrowf.PositiveIntervalsTester),
    ("Perceptron", lambda: mtugrowf.PerceptronTester(random_state=42)),
]:
    tester = tester_class()
    calculator = mtugrowf.GrowthFunctionCalculator(
        tester, verbose=False, show_progress=False
    )
    results[name] = calculator.compute_growth_curve(
        generator, n_range=n_range, num_trials=1
    )

# Plot comparison.
visualizer.plot_multiple_growth_curves(
    results, title="Growth Functions: Comparison Across Hypothesis Sets"
)

Observation¶

Positive Rays: Linear growth $O(N)$ - very limited expressiveness
Positive Intervals: Quadratic growth $O(N^2)$ - moderate expressiveness
Perceptron: Polynomial growth $O(N^2)$ after break point - good balance
Gray dashed line: Exponential $2^N$ - shows what unlimited growth looks like

The key insight: Polynomial growth $\Rightarrow$ learning is feasible!

Part 3: Realizable Dichotomies and Edge Cases¶

Cell 3.1: Computing realizable dichotomies¶

Goal:

Examine which specific dichotomies are realizable for a small example
Test all possible labelings for 3 points with a perceptron
Verify the shattering property empirically

# Create 3 points and test all 8 dichotomies with perceptron.
generator = mtugrowf.PointGenerator(seed=42)
tester = mtugrowf.PerceptronTester(random_state=42)

points = generator.generate_random(n=3, d=2)
enumerator = mtugrowf.DichotomyEnumerator(n=3)
print("points=\n", points)

# Build a table of every dichotomy and whether the perceptron realizes it.
rows = []
for i in range(enumerator.count_dichotomies()):
    labels = enumerator.get_dichotomy(i)
    is_realizable = tester.test_dichotomy(points, labels)
    rows.append(
        {
            "dichotomy": i,
            "labels": str(labels).replace(" ", ""),
            "realizable": is_realizable,
        }
    )
dichotomies_df = pd.DataFrame(rows)
display(dichotomies_df)

realizable_count = dichotomies_df["realizable"].sum()
print("realizable_count=", realizable_count, "/", enumerator.count_dichotomies())
print("is_shattered=", realizable_count == enumerator.count_dichotomies())

=== Testing All Dichotomies for 3 Random 2D Points ===
Points:
[[-0.25091976  0.90142861]
 [ 0.46398788  0.19731697]
 [-0.68796272 -0.68801096]]

Dichotomy | Labels      | Realizable
---------------------------------------------
        0 | [-1-1-1]    | Yes
        1 | [1-1-1]     | Yes
        2 | [-11-1]     | Yes
        3 | [11-1]      | Yes
        4 | [-1-11]     | Yes
        5 | [1-11]      | Yes
        6 | [-111]      | Yes
        7 | [111]       | Yes

Total realizable: 8 / 8
Points shattered: True

Observation¶

For 3 random 2D points, all 8 dichotomies are typically realizable
The perceptron can shatter 3 points in general position
This demonstrates why VC dimension = 3 for 2D perceptron

Cell 3.2: Finding a hypothesis for positive rays¶

Goal:

Find the actual threshold that realizes a given labeling for positive rays, not just whether one exists

# Find threshold for a positive ray pattern.
tester = mtugrowf.PositiveRaysTester()
generator = mtugrowf.PointGenerator(seed=42)

points = generator.generate_line_1d(n=5)
labels = np.array([-1, -1, 1, 1, 1])
print("points=", points.flatten())
print("labels=", labels)

hypothesis = tester.find_hypothesis(points, labels)
if hypothesis:
    print("threshold=", hypothesis["threshold"])
    print(f"Rule: h(x) = +1 if x >= {hypothesis['threshold']:.3f}, else -1")

=== Finding Hypothesis for Positive Rays ===
Points: [-1.  -0.5  0.   0.5  1. ]
Labels: [-1 -1  1  1  1]

Found threshold: a = -0.250
Rule: h(x) = +1 if x >= -0.250, else -1

=== Finding Hypothesis for Perceptron ===
Points:
[[0 0]
 [1 0]
 [0 1]
 [1 1]]
Labels: [-1 -1  1  1]

Found weights: w = [-1.  3.]
Found intercept: b = -1.000
Rule: h(x) = sign(-1.000*x1 + 3.000*x2 + -1.000)

Cell 3.3: Finding a hypothesis for perceptron¶

Goal:

Find the actual weights and intercept that realize a given labeling for a 2D perceptron

# Find perceptron weights for a linearly separable pattern.
tester_p = mtugrowf.PerceptronTester(random_state=42)
points_2d = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
labels_2d = np.array([-1, -1, 1, 1])
print("points_2d=\n", points_2d)
print("labels_2d=", labels_2d)

hypothesis_p = tester_p.find_hypothesis(points_2d, labels_2d)
if hypothesis_p:
    w = hypothesis_p["weights"]
    b = hypothesis_p["intercept"]
    print("weights=", w)
    print("intercept=", b)
    print(f"Rule: h(x) = sign({w[0]:.3f}*x1 + {w[1]:.3f}*x2 + {b:.3f})")

Observation¶

We can find the actual parameters (threshold, weights) that realize a labeling
This is useful for understanding which hypotheses are “closest” to the data
For perceptron, sklearn finds a linear separator via the perceptron algorithm

Cell 3.4: Edge case: N=1¶

Goal:

Check that the growth function calculator behaves sensibly at the smallest possible $N$

# Test with N=1 point.
generator = mtugrowf.PointGenerator(seed=42)

for name, tester in [
    ("Positive Rays", mtugrowf.PositiveRaysTester()),
    ("Perceptron", mtugrowf.PerceptronTester(random_state=42)),
]:
    calculator = mtugrowf.GrowthFunctionCalculator(
        tester, verbose=False, show_progress=False
    )
    if "Rays" in name:
        points = generator.generate_line_1d(n=1)
    else:
        points = generator.generate_random(n=1, d=2)
    result = calculator.compute_growth_function(points)
    print(f"{name}: m_H(1) = {result['m_h_n']}")

=== Edge Case: N=1 ===
Positive Rays       : m_H(1) = 2
Perceptron          : m_H(1) = 2

=== Edge Case: Collinear Points ===
3 collinear points: m_H(3) = 6
Expected for general position: 8
Collinear breaks shattering: True

Cell 3.5: Edge case: collinear points¶

Goal:

Check how a degenerate point configuration, 3 collinear points, affects whether the perceptron can shatter them

# Test with collinear points (edge case for perceptron).
tester = mtugrowf.PerceptronTester(random_state=42)
calculator = mtugrowf.GrowthFunctionCalculator(
    tester, verbose=False, show_progress=False
)

points_collinear = generator.generate_collinear(n=3, d=2)
result = calculator.compute_growth_function(points_collinear)
print("m_h_n=", result["m_h_n"], "(expected for general position: 8)")
print("collinear_breaks_shattering=", result["m_h_n"] < 8)

Observation¶

For $N=1$ , all hypothesis sets have $m_H(1) = 2$ (trivial)
Collinear points break the shattering property for perceptrons
Special configurations can reduce the growth function