1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

import numpy as np
from typing import Set, List, Tuple
 
def illustrate_shattering():
    """
    Illustrate the concept of shattering, which underlies VC dimension.
    
    A set S is 'shattered' by class H if every labeling of S is
    achievable by some hypothesis in H.
    
    VC dimension = size of largest shattered set
    """
    
    print("Shattering Illustration")
    print("=" * 60)
    
    # Example 1: Linear separators in R^2
    # Can shatter any 3 non-collinear points
    # Cannot shatter any 4 points (one configuration fails)
    # VC dimension = 3
    
    print("
1. Linear Separators in R^2:")
    print("   - 3 non-collinear points: ALL 8 labelings achievable ✓")
    print("   - 4 points (any config): Some labeling impossible ✗")
    print("   - VC dimension = 3")
    
    # Example 2: Axis-aligned rectangles in R^2
    # Can shatter 4 points (corners of a rectangle)
    # Cannot shatter 5 points
    # VC dimension = 4
    
    print("
2. Axis-Aligned Rectangles in R^2:")
    print("   - 4 points (rectangle corners): ALL 16 labelings ✓")
    print("   - 5 points: Configuration with center fails ✗")
    print("   - VC dimension = 4")
    
    # Example 3: Intervals on R
    # Can shatter 2 points (any pair)
    # Cannot shatter 3 points (endpoint labeling fails)
    # VC dimension = 2
    
    print("
3. Intervals on R:")
    print("   - 2 points: ALL 4 labelings (empty, left, right, both) ✓")
    print("   - 3 points: Labeling (1, 0, 1) impossible ✗")
    print("   - VC dimension = 2")
    
    # Example 4: All functions X → {0,1}
    # Can shatter ANY finite set
    # VC dimension = infinity
    # NOT PAC-learnable!
    
    print("
4. All Functions X → {0,1}:")
    print("   - Can shatter ANY finite set")
    print("   - VC dimension = ∞")
    print("   - NOT PAC-learnable!")
    
    print("
" + "=" * 60)
    print("Key Insight: Finite VC dimension ⟺ PAC-learnable")
 
 
def sample_complexity_from_vc(d: int, epsilon: float, delta: float) -> int:
    """
    Compute sample complexity from VC dimension.
    
    Fundamental theorem: m = O((d + log(1/δ)) / ε)
    
    More precise bound (realizable):
        m = O((d log(1/ε) + log(1/δ)) / ε)
    
    Agnostic bound:
        m = O((d + log(1/δ)) / ε²)
    """
    from math import log, ceil
    
    # Realizable case bound
    realizable = ceil((d * log(1/epsilon) + log(1/delta)) / epsilon)
    
    # Agnostic case bound
    agnostic = ceil((d + log(1/delta)) / (epsilon ** 2))
    
    return realizable, agnostic
 
 
def compare_complexity_bounds():
    """Compare sample complexity for different hypothesis classes."""
    
    print("
Sample Complexity Comparison (ε=0.05, δ=0.05)")
    print("-" * 60)
    
    cases = [
        ("Intervals on R", 2),
        ("Rectangles in R²", 4),
        ("Linear separators R²", 3),
        ("Linear separators R¹⁰", 11),
        ("Linear separators R¹⁰⁰", 101),
        ("Decision stumps (100 features)", 2),
    ]
    
    epsilon, delta = 0.05, 0.05
    
    for name, vc_dim in cases:
        real, agn = sample_complexity_from_vc(vc_dim, epsilon, delta)
        print(f"{name:30} (d={vc_dim:3}): "
              f"Realizable={real:>6,}, Agnostic={agn:>7,}")
 
illustrate_shattering()
compare_complexity_bounds()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

import numpy as np
from typing import Tuple, List
 
class RectangleLearner:
    """
    PAC learner for axis-aligned rectangles in R^2.
    
    Algorithm: Find the tightest rectangle containing all positive examples.
    This is the 'most specific' consistent hypothesis.
    
    Key insight: The learned rectangle is contained in the target rectangle.
    Errors occur only in the 'gap' between learned and target rectangles.
    """
    
    def __init__(self):
        self.rectangle = None  # (a, b, c, d)
    
    def learn(self, samples: List[Tuple[float, float, int]]) -> None:
        """Learn from labeled samples."""
        positives = [(x, y) for x, y, label in samples if label == 1]
        
        if not positives:
            # No positive examples: output empty rectangle
            self.rectangle = (float('inf'), float('-inf'), 
                             float('inf'), float('-inf'))
            return
        
        # Tightest rectangle containing all positives
        xs = [p[0] for p in positives]
        ys = [p[1] for p in positives]
        
        self.rectangle = (min(xs), max(xs), min(ys), max(ys))
    
    def predict(self, x: float, y: float) -> int:
        """Predict label for point (x, y)."""
        a, b, c, d = self.rectangle
        return int(a <= x <= b and c <= y <= d)
 
 
def analyze_rectangle_learning(m: int, epsilon: float, delta: float):
    """
    Analyze PAC learning for rectangles.
    
    Theorem: With m = O((4/ε) ln(4/δ)) samples, the learned rectangle
    has generalization error ≤ ε with probability ≥ 1-δ.
    
    Proof:
    1. True rectangle R* has probability 1 under D (for points with label 1)
    2. Learned rectangle R ⊆ R* (contained in true rectangle)
    3. Error region = R* \ R (points in true but not learned rectangle)
    4. Error region has 4 'strips' (one per side)
    5. Each strip has probability ≤ ε/4 of not being 'hit' by m samples
       if its probability mass > ε/4
    6. By union bound, probability all strips are small: ≥ 1-δ
    """
    np.random.seed(42)
    
    # True rectangle
    true_rect = (0.2, 0.8, 0.3, 0.7)  # [0.2, 0.8] × [0.3, 0.7]
    a_t, b_t, c_t, d_t = true_rect
    
    # Distribution: uniform over [0, 1]²
    def sample():
        x, y = np.random.uniform(0, 1, 2)
        label = int(a_t <= x <= b_t and c_t <= y <= d_t)
        return x, y, label
    
    # Generate training samples
    samples = [sample() for _ in range(m)]
    
    # Learn rectangle
    learner = RectangleLearner()
    learner.learn(samples)
    
    # Estimate generalization error
    n_test = 100000
    errors = 0
    for _ in range(n_test):
        x, y = np.random.uniform(0, 1, 2)
        true_label = int(a_t <= x <= b_t and c_t <= y <= d_t)
        pred_label = learner.predict(x, y)
        errors += (true_label != pred_label)
    
    gen_error = errors / n_test
    
    # Compare to theoretical bound
    # Required m for PAC: m ≥ (4/ε) ln(4/δ)
    theoretical_m = int(np.ceil((4/epsilon) * np.log(4/delta)))
    
    return {
        'samples': m,
        'gen_error': gen_error,
        'epsilon_target': epsilon,
        'theoretical_m': theoretical_m,
        'learned_rect': learner.rectangle,
        'true_rect': true_rect
    }
 
# Run experiment
result = analyze_rectangle_learning(m=200, epsilon=0.05, delta=0.05)
print(f"Samples: {result['samples']}")
print(f"Generalization error: {result['gen_error']:.4f}")
print(f"Target ε: {result['epsilon_target']}")
print(f"Theoretical m required: {result['theoretical_m']}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

"""
Illustrating the difference between proper and improper learning.
 
Proper learning: H = C (same hypothesis class as concept class)
Improper learning: H ⊃ C (broader hypothesis class)
 
Key insight: Improper learning can be easier!
"""
 
from typing import List, Tuple
import numpy as np
 
# Example: Learning conjunctions
 
class ProperConjunctionLearner:
    """
    Proper learner: outputs a conjunction from the class of conjunctions.
    
    This learner finds the most specific conjunction consistent with data.
    Efficient for conjunctions: O(mn) time.
    """
    
    def __init__(self, n: int):
        self.n = n
        self.literals = None  # Set of (variable, polarity) pairs
    
    def learn(self, samples: List[Tuple[np.ndarray, int]]):
        # Initialize with all possible literals
        self.literals = set()
        for i in range(self.n):
            self.literals.add((i, True))   # positive literal
            self.literals.add((i, False))  # negative literal
        
        # Remove literals inconsistent with positive examples
        for x, label in samples:
            if label == 1:
                for i in range(self.n):
                    if x[i] == 0:
                        self.literals.discard((i, True))
                    else:
                        self.literals.discard((i, False))
        
        return self.literals
 
 
class ImproperDNFLearner:
    """
    Improper learner: learns conjunctions but outputs DNF.
    
    This might seem wasteful, but for some classes (like 3-term DNF),
    improper learning with a larger class (3-CNF) is tractable
    while proper learning is NP-hard!
    """
    
    def __init__(self, n: int):
        self.n = n
        self.dnf_terms = []  # List of conjunctions
    
    def learn(self, samples: List[Tuple[np.ndarray, int]]):
        # Simple strategy: memorize positive examples as terms
        # Each positive example becomes a term with full specification
        
        for x, label in samples:
            if label == 1:
                # Create a term that matches exactly this example
                term = []
                for i in range(self.n):
                    term.append((i, x[i] == 1))
                self.dnf_terms.append(term)
        
        return self.dnf_terms
    
    def predict(self, x: np.ndarray) -> int:
        # OR of all terms: positive if any term is satisfied
        for term in self.dnf_terms:
            satisfied = True
            for i, polarity in term:
                if polarity and x[i] != 1:
                    satisfied = False
                    break
                if not polarity and x[i] != 0:
                    satisfied = False
                    break
            if satisfied:
                return 1
        return 0
 
 
def compare_learning_strategies():
    """
    Compare proper and improper learning.
    
    For conjunctions: both work fine.
    For 3-DNF: proper is NP-hard, improper (via 3-CNF) is polynomial!
    """
    
    print("Learning Strategy Comparison")
    print("=" * 60)
    
    print("
1. Conjunctions:")
    print("   - Proper learning: O(mn) time, output is a conjunction")
    print("   - Improper learning: Also works, but unnecessary")
    print("   - In this case, proper is preferred (simpler hypothesis)")
    
    print("
2. 3-term DNF:")
    print("   - Proper learning: NP-hard (must find consistent 3-DNF)")
    print("   - Improper with 3-CNF: Polynomial time!")
    print("   - Key: DNF can be rewritten as CNF (De Morgan's laws)")
    print("   - Learning 3-CNF improperly learns 3-DNF efficiently")
    
    print("
3. Intersections of halfspaces:")
    print("   - Proper learning: Open problem for >2 halfspaces")
    print("   - Improper learning: Use neural nets (not well understood)")
    
    print("
" + "=" * 60)
    print("Takeaway: Improper learning broadens what's tractable!")
 
compare_learning_strategies()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

import numpy as np
from typing import List, Tuple, Callable
 
def demonstrate_no_free_lunch():
    """
    Demonstrate the No Free Lunch theorem: without assumptions,
    every learner is as good (or bad) as any other.
    """
    
    np.random.seed(42)
    n = 4  # Small dimension for illustration
    
    # All possible inputs
    X = [tuple(int(b) for b in format(i, f'0{n}b')) 
         for i in range(2**n)]
    
    # Generate random training sample
    m = 8  # Half the domain
    train_indices = np.random.choice(len(X), m, replace=False)
    train_X = [X[i] for i in train_indices]
    
    # Count how many consistent functions exist
    # (functions that agree on training data but vary on test data)
    
    test_indices = [i for i in range(len(X)) if i not in train_indices]
    n_test = len(test_indices)
    
    # Any labeling of training points is consistent with 2^(n_test) functions
    # (one for each possible labeling of test points)
    
    consistent_functions = 2 ** n_test
    
    print("No Free Lunch Demonstration")
    print("=" * 60)
    print(f"Input dimension: n = {n}")
    print(f"Total instances: |X| = {2**n}")
    print(f"Training samples: m = {m}")
    print(f"Unseen instances: 2^n - m = {2**n - m}")
    print(f"Functions consistent with training: 2^{n_test} = {consistent_functions}")
    print()
    print("For EACH possible labeling of training data,")
    print(f"there are {consistent_functions} functions that produce it.")
    print("Without assumptions, we can't distinguish between them!")
    print()
    print("Implication: For the class of ALL functions,")
    print("no learner can generalize better than random guessing.")
 
 
def demonstrate_shattering_infinite_vc():
    """
    Show that the class of all functions shatters any finite set.
    """
    
    print("
Infinite VC Dimension: Class of All Functions")
    print("=" * 60)
    
    # For any m points, we can realize all 2^m labelings
    for m in [1, 2, 3, 4, 5]:
        labelings = 2 ** m
        print(f"m = {m} points: {labelings:>4} possible labelings, ALL achievable")
    
    print()
    print("VC dimension = ∞ (can shatter any finite set)")
    print("⟹ NOT PAC-learnable (need VC dimension < ∞)")
 
 
def contrast_bounded_unbounded_trees():
    """
    Show the difference between bounded and unbounded decision trees.
    """
    
    print("
Bounded vs Unbounded Decision Trees")
    print("=" * 60)
    
    n = 10  # 10 Boolean variables
    
    # Unbounded trees: can represent all functions
    unbounded_vc = 2 ** n
    
    # Bounded trees: VC dimension depends on depth
    for depth in [1, 2, 3, 4, 5]:
        # VC dimension ≈ 2^d * log(n)
        bounded_vc = (2 ** depth) * np.log2(n)
        
        print(f"Depth = {depth}: VC ≈ {bounded_vc:.0f}")
    
    print(f"Unbounded: VC = {unbounded_vc} = 2^n (infinite growth)")
    print()
    print("Bounded depth trees: PAC-learnable")
    print("Unbounded depth trees: NOT PAC-learnable")
 
demonstrate_no_free_lunch()
demonstrate_shattering_infinite_vc()
contrast_bounded_unbounded_trees()