Skip to main content
`Ctrl`+`K`

# Chapter 9: Minsky and Papert’s Analysis

## The Book That Changed AI History

In 1969, Marvin Minsky and Seymour Papert published Perceptrons: An Introduction to Computational Geometry, a rigorous mathematical analysis of what single-layer perceptrons can and cannot compute. The book’s impact was enormous and, in many ways, disproportionate to its actual claims. While the theorems were correct, their interpretation by the broader AI community led to a near-complete abandonment of neural network research for over a decade.

### The Authors

Marvin Minsky (1927–2016) was a co-founder of the MIT AI Lab, a pioneer in artificial intelligence, and one of the most influential figures in computer science. He had actually built one of the first neural network machines (SNARC) in 1951, but by the 1960s had become skeptical of the perceptron approach.

Seymour Papert (1928–2016) was a mathematician and computer scientist who had worked with Jean Piaget in Geneva before joining MIT. He brought a geometric and topological perspective to the analysis of perceptrons, which became the foundation of the book’s theoretical framework.

Together, they produced a masterpiece of mathematical analysis that was, unfortunately, read more for its conclusions than its nuances.

Danger

AI Winter context — After this book, skepticism toward neural networks grew and funding declined substantially for ~15 years. The downturn had multiple causes, but Perceptrons became a focal point for the skepticism.

The publication of Perceptrons in 1969 did not merely slow down neural network research — it nearly killed it. DARPA, the primary funder of AI research in the United States, redirected its resources almost entirely toward symbolic AI approaches (expert systems, logic programming, knowledge representation). Academic departments stopped hiring neural network researchers. Conference papers on the topic were rejected. Graduate students were actively discouraged from pursuing neural network dissertations. The field entered a period now called the first AI Winter, lasting roughly from 1969 to 1982.

Warning

What Minsky & Papert overstated — They proved limitations of single-layer perceptrons, but the public (and funders) interpreted this as limitations of ALL neural networks.

The mathematical results in Perceptrons apply strictly to single-layer perceptrons (or, more precisely, to perceptrons of bounded order). Minsky and Papert were aware that multi-layer networks could overcome many of these limitations, but they expressed strong skepticism about the trainability of such networks. The nuance was lost in translation: what reached funding agencies and the broader AI community was the simple message that “perceptrons don’t work.” This conflation of “single-layer perceptrons have provable limitations” with “neural networks are a dead end” was the most consequential misinterpretation in the history of AI.

Tip

What they actually proved vs. what people thought they proved:

What Minsky & Papert proved | What people believed
--- | ---
Single-layer perceptrons cannot compute XOR | Neural networks cannot compute XOR
PARITY requires examining all inputs simultaneously | Neural networks cannot learn complex patterns
Bounded-order perceptrons cannot detect connectedness | Neural networks are useless for vision
No known efficient learning algorithm for multi-layer nets (in 1969) | No learning algorithm exists for multi-layer nets

The left column consists of correct, important mathematical theorems. The right column consists of false conclusions that the community drew. The gap between the two cost the field over a decade of progress.

Show code cell source Hide code cell source

    import numpy as np
    import matplotlib.pyplot as plt
    from itertools import combinations

    plt.rcParams.update({
        'figure.figsize': (8, 6),
        'font.size': 12,
        'axes.grid': True,
        'grid.alpha': 0.3
    })

## 1. The Formal Framework

Minsky and Papert studied a generalized form of the perceptron that is more powerful than Rosenblatt’s original model.

### The Minsky-Papert Perceptron

Let \(R\) be a finite set (the retina — think of it as a set of pixel positions). An input is a subset \(X \subseteq R\) (the set of “active” pixels). The perceptron computes a predicate \(\psi\) on inputs:

\[\psi(X) = 1 \quad \text{iff} \quad \sum_{i} \alpha_i \varphi_i(X) > \theta\]

where:

- Each \(\varphi_i\) is a partial predicate that depends only on a bounded subset \(S_i \subseteq R\).

- Each \(\alpha_i \in \mathbb{R}\) is a weight.

- \(\theta \in \mathbb{R}\) is a threshold.

### Difference from Rosenblatt

In Rosenblatt’s perceptron, each \(\varphi_i\) examines a single input point: \(\varphi_i(X) = \mathbf{1}[r_i \in X]\). In the Minsky-Papert framework, each \(\varphi_i\) can be any Boolean function of the inputs within its receptive field \(S_i\). This makes the model strictly more powerful than Rosenblatt’s, so any limitation proved for this model applies a fortiori to the simpler version.

### Key Insight

The central question is: how large must the receptive fields \(S_i\) be to compute various predicates? If every predicate of interest requires looking at the entire retina, then the perceptron architecture provides no computational savings over a lookup table.

## 2. Order of a Perceptron

The order of a perceptron representation is the key complexity measure in Minsky and Papert’s analysis.

Definition. The order of a perceptron \(\psi\) is:

\[\text{ord}(\psi) = \min\{k : \text{there exists a representation with all } |S_i| \leq k\}\]

In other words, the order is the size of the largest receptive field needed by any partial predicate \(\varphi_i\).

### Examples

- Order 1 = classical Rosenblatt perceptron. Each \(\varphi_i\) looks at a single input.

- Order 2 = each partial predicate can look at pairs of inputs.

- Order \(k\) = each partial predicate can examine up to \(k\) inputs simultaneously.

- Order \(n\) (where \(n = |R|\)) = the perceptron can look at all inputs. This is equivalent to a threshold function of arbitrary Boolean features.

### The Hierarchy

Higher order means more power. An order-\(k\) perceptron can simulate any order-\((k-1)\) perceptron (by ignoring extra inputs in its receptive fields). The question is: which predicates require high order?

## 3. The Parity Theorem

This is the most important result in the book and the one most directly relevant to the XOR problem.

Theorem (Parity Theorem — Minsky & Papert, 1969)

The PARITY predicate on \(n\) bits requires order \(n\). That is, any perceptron computing PARITY must have at least one partial predicate that examines all \(n\) inputs.

Formally: \(\text{ord}(\text{PARITY}) = n\).

This means that no matter how cleverly you design the partial predicates, no matter how many of them you use, and no matter what weights you assign — if each partial predicate looks at fewer than \(n\) inputs, the perceptron cannot compute parity.

Proof

Let \(R = \{1, 2, \ldots, n\}\) be the set of input positions. For \(X \subseteq R\), define:

\[\text{PARITY}(X) = |X| \mod 2\]

Let \(P_0 = \{X \subseteq R : |X| \text{ is even}\}\) and \(P_1 = \{X \subseteq R : |X| \text{ is odd}\}\).

Note that \(|P_0| = |P_1| = 2^{n-1}\) (exactly half of all subsets have even size).

Suppose for contradiction that PARITY can be computed by a perceptron of order \(k < n\):

\[\text{PARITY}(X) = 1 \iff \sum_i \alpha_i \varphi_i(X) > \theta\]

where each \(\varphi_i\) depends only on \(S_i \subseteq R\) with \(|S_i| \leq k < n\).

Define the linear functional:

\[L(X) = \sum_i \alpha_i \varphi_i(X)\]

Key Lemma. For each partial predicate \(\varphi_i\) with \(|S_i| < n\), there exists a bit \(j_i \in R \setminus S_i\) (a bit not examined by \(\varphi_i\)). Consider the involution \(\tau_{j_i}: 2^R \to 2^R\) that flips bit \(j_i\):

\[\begin{split}\tau_{j_i}(X) = X \triangle \{j_i\} = \begin{cases} X \cup \{j_i\} & \text{if } j_i \notin X \\ X \setminus \{j_i\} & \text{if } j_i \in X \end{cases}\end{split}\]

This operation:

1. Toggles parity: \(\text{PARITY}(\tau_{j_i}(X)) = 1 - \text{PARITY}(X)\), so \(\tau_{j_i}\) maps \(P_0 \to P_1\) bijectively.

2. Preserves \(\varphi_i\): Since \(j_i \notin S_i\), the predicate \(\varphi_i\) cannot distinguish \(X\) from \(\tau_{j_i}(X)\), so \(\varphi_i(\tau_{j_i}(X)) = \varphi_i(X)\).

Using property 2, for each \(\varphi_i\):

\[\sum_{X \in P_0} \varphi_i(X) = \sum_{X \in P_0} \varphi_i(\tau_{j_i}(X)) = \sum_{Y \in P_1} \varphi_i(Y)\]

where the last step uses the bijection \(\tau_{j_i}: P_0 \to P_1\).

Therefore, by linearity:

\[\sum_{X \in P_0} L(X) = \sum_i \alpha_i \sum_{X \in P_0} \varphi_i(X) = \sum_i \alpha_i \sum_{Y \in P_1} \varphi_i(Y) = \sum_{Y \in P_1} L(Y)\]

But for PARITY to be correctly computed, we need:

- \(L(X) > \theta\) for all \(X \in P_1\) (odd parity classified as 1)

- \(L(X) \leq \theta\) for all \(X \in P_0\) (even parity classified as 0)

This gives:

\[\sum_{Y \in P_1} L(Y) > |P_1| \cdot \theta = 2^{n-1} \cdot \theta\]
\[\sum_{X \in P_0} L(X) \leq |P_0| \cdot \theta = 2^{n-1} \cdot \theta\]

So \(\sum_{Y \in P_1} L(Y) > \sum_{X \in P_0} L(X)\).

But we just showed \(\sum_{X \in P_0} L(X) = \sum_{Y \in P_1} L(Y)\).

\[\boxed{\text{Contradiction. Therefore } \text{ord}(\text{PARITY}) = n. \quad \blacksquare}\]
Show code cell source Hide code cell source

    # Demonstration: the parity symmetry argument
    # For n=4, show that flipping any bit preserves partial predicate sums

    n = 4
    all_subsets = []
    for i in range(2**n):
        subset = set()
        for bit in range(n):
            if i & (1 << bit):
                subset.add(bit)
        all_subsets.append(frozenset(subset))

    P0 = [X for X in all_subsets if len(X) % 2 == 0]  # even parity
    P1 = [X for X in all_subsets if len(X) % 2 == 1]  # odd parity

    print(f"n = {n}")
    print(f"Total subsets: {len(all_subsets)}")
    print(f"|P0| (even parity) = {len(P0)}")
    print(f"|P1| (odd parity) = {len(P1)}")

    # Define a partial predicate on S = {0, 1} (order 2 < n=4)
    S = frozenset({0, 1})

    def phi(X, S):
        """A partial predicate: returns 1 if X intersects S in exactly 1 element."""
        return int(len(X & S) == 1)

    sum_P0 = sum(phi(X, S) for X in P0)
    sum_P1 = sum(phi(X, S) for X in P1)

    print(f"\nPartial predicate phi on S = {set(S)}: 'exactly one element of S is in X'")
    print(f"Sum over P0: {sum_P0}")
    print(f"Sum over P1: {sum_P1}")
    print(f"Equal? {sum_P0 == sum_P1}  (as predicted by the theorem)")

    # Verify for multiple partial predicates
    print("\nVerification for all order-2 partial predicates on pairs:")
    for pair in combinations(range(n), 2):
        S_test = frozenset(pair)
        # Try different predicates on this pair
        for name, pred in [
            ("both in X", lambda X, S: int(S.issubset(X))),
            ("at least one in X", lambda X, S: int(len(X & S) >= 1)),
            ("exactly one in X", lambda X, S: int(len(X & S) == 1)),
            ("neither in X", lambda X, S: int(len(X & S) == 0))
        ]:
            s0 = sum(pred(X, S_test) for X in P0)
            s1 = sum(pred(X, S_test) for X in P1)
            assert s0 == s1, f"FAILED for {set(S_test)}, {name}"

    print("All partial predicates of order 2 have equal sums over P0 and P1.")
    print("No linear combination can distinguish the two classes!")

    n = 4
    Total subsets: 16
    |P0| (even parity) = 8
    |P1| (odd parity) = 8

    Partial predicate phi on S = {0, 1}: 'exactly one element of S is in X'
    Sum over P0: 4
    Sum over P1: 4
    Equal? True  (as predicted by the theorem)

    Verification for all order-2 partial predicates on pairs:
    All partial predicates of order 2 have equal sums over P0 and P1.
    No linear combination can distinguish the two classes!

## 3a. Visualizing Why Parity Requires All Inputs

The parity function has a unique structure: knowing any proper subset of the inputs tells you nothing about the output. Flipping any single unobserved bit toggles the parity. This is what makes it maximally hard for a bounded-order perceptron.

Show code cell source Hide code cell source

    import numpy as np
    import matplotlib.pyplot as plt

    # Visualization: Parity function showing why it requires examining ALL inputs
    # For each subset of inputs observed, show that both parities are equally likely

    fig, axes = plt.subplots(1, 3, figsize=(18, 5))

    n = 4
    all_inputs = np.array([[int(b) for b in format(i, f'0{n}b')] for i in range(2**n)])
    parities = np.sum(all_inputs, axis=1) % 2

    # Panel 1: Observing 1 bit
    ax = axes[0]
    observed_bit = 0
    for val in [0, 1]:
        mask = all_inputs[:, observed_bit] == val
        p_even = np.sum(parities[mask] == 0)
        p_odd = np.sum(parities[mask] == 1)
        x_pos = [val - 0.15, val + 0.15]
        bars = ax.bar(x_pos, [p_even, p_odd], width=0.25,
                      color=['blue', 'red'], alpha=0.7,
                      edgecolor='black', linewidth=1.5)
        ax.text(val - 0.15, p_even + 0.2, str(p_even), ha='center', fontsize=11, fontweight='bold')
        ax.text(val + 0.15, p_odd + 0.2, str(p_odd), ha='center', fontsize=11, fontweight='bold')

    ax.set_xticks([0, 1])
    ax.set_xticklabels(['$x_1=0$', '$x_1=1$'], fontsize=12)
    ax.set_ylabel('Count', fontsize=12)
    ax.set_title('Observe 1 bit: $x_1$\nParity is 50/50', fontsize=13)
    ax.legend(['Even parity', 'Odd parity'], fontsize=10)
    ax.set_ylim(0, 6)
    ax.grid(True, alpha=0.3)

    # Panel 2: Observing 2 bits
    ax = axes[1]
    positions = []
    labels = []
    for v1 in [0, 1]:
        for v2 in [0, 1]:
            mask = (all_inputs[:, 0] == v1) & (all_inputs[:, 1] == v2)
            p_even = np.sum(parities[mask] == 0)
            p_odd = np.sum(parities[mask] == 1)
            pos = v1 * 2 + v2
            x_pos = [pos - 0.15, pos + 0.15]
            ax.bar(x_pos, [p_even, p_odd], width=0.25,
                   color=['blue', 'red'], alpha=0.7,
                   edgecolor='black', linewidth=1.5)
            ax.text(pos - 0.15, p_even + 0.1, str(p_even), ha='center', fontsize=10, fontweight='bold')
            ax.text(pos + 0.15, p_odd + 0.1, str(p_odd), ha='center', fontsize=10, fontweight='bold')
            labels.append(f'({v1},{v2})')

    ax.set_xticks(range(4))
    ax.set_xticklabels(labels, fontsize=11)
    ax.set_xlabel('$(x_1, x_2)$', fontsize=12)
    ax.set_ylabel('Count', fontsize=12)
    ax.set_title('Observe 2 bits: $x_1, x_2$\nStill 50/50!', fontsize=13)
    ax.set_ylim(0, 4)
    ax.grid(True, alpha=0.3)

    # Panel 3: Observing 3 bits
    ax = axes[2]
    labels3 = []
    for v1 in [0, 1]:
        for v2 in [0, 1]:
            for v3 in [0, 1]:
                mask = (all_inputs[:, 0] == v1) & (all_inputs[:, 1] == v2) & (all_inputs[:, 2] == v3)
                p_even = np.sum(parities[mask] == 0)
                p_odd = np.sum(parities[mask] == 1)
                pos = v1 * 4 + v2 * 2 + v3
                x_pos = [pos - 0.15, pos + 0.15]
                ax.bar(x_pos, [p_even, p_odd], width=0.25,
                       color=['blue', 'red'], alpha=0.7,
                       edgecolor='black', linewidth=1.5)
                ax.text(pos - 0.15, p_even + 0.05, str(p_even), ha='center', fontsize=9, fontweight='bold')
                ax.text(pos + 0.15, p_odd + 0.05, str(p_odd), ha='center', fontsize=9, fontweight='bold')
                labels3.append(f'{v1}{v2}{v3}')

    ax.set_xticks(range(8))
    ax.set_xticklabels(labels3, fontsize=9)
    ax.set_xlabel('$(x_1, x_2, x_3)$', fontsize=12)
    ax.set_ylabel('Count', fontsize=12)
    ax.set_title('Observe 3 of 4 bits\nSTILL 50/50!', fontsize=13)
    ax.set_ylim(0, 2.5)
    ax.grid(True, alpha=0.3)

    plt.suptitle('Parity on 4 bits: Observing any proper subset of inputs gives NO information\n'
                 'Blue = even parity, Red = odd parity --- always balanced until you see ALL bits',
                 fontsize=14, y=1.06)
    plt.tight_layout()
    plt.show()

    print("Key insight: No matter how many bits you observe (up to n-1),")
    print("the remaining unseen bit can always flip the parity.")
    print("This is why the Parity Theorem requires order n.")

    Key insight: No matter how many bits you observe (up to n-1),
    the remaining unseen bit can always flip the parity.
    This is why the Parity Theorem requires order n.

## 4. The Group Invariance Theorem

This is the deepest and most technically sophisticated result in Minsky and Papert’s book.

### Setting

Let \(G\) be a group acting on the retina \(R\) (e.g., the group of translations, rotations, or reflections of a grid). The action extends to subsets: for \(g \in G\) and \(X \subseteq R\), define \(g(X) = \{g(r) : r \in X\}\).

A predicate \(\psi\) is \(G\)-invariant if \(\psi(g(X)) = \psi(X)\) for all \(g \in G\) and \(X \subseteq R\).

Theorem (Group Invariance Theorem)

If \(G\) acts transitively on \(R\) (meaning for any \(r_1, r_2 \in R\), there exists \(g \in G\) with \(g(r_1) = r_2\)), then any \(G\)-invariant predicate computable by a bounded-order perceptron depends only on \(|X|\) (the number of active points).

Consequence: Many interesting visual predicates (e.g., “is there a vertical line in the image?”) are invariant under translations. The theorem says that if a perceptron has bounded order and computes such a predicate, it can only depend on the total number of active pixels — a very crude statistic. This means that most geometrically interesting predicates cannot be computed by bounded-order perceptrons.

Proof

Proof Sketch.

1. Symmetrization: For any partial predicate \(\varphi\) on \(S \subseteq R\), define its symmetrization:

\[\bar{\varphi}(X) = \frac{1}{|G|} \sum_{g \in G} \varphi(g^{-1}(X))\]

2. Because the perceptron computes a \(G\)-invariant function and \(G\) acts transitively, the symmetrized predicates suffice.

3. Orbit counting: By transitivity, symmetrized predicates are strongly constrained: the group action forces bounded-order partial predicates to lose access to fine-grained geometric structure.

The key insight is that symmetry under a transitive group severely restricts what a bounded-order perceptron can distinguish — it can only access coarse statistics of the input, not detailed spatial structure. The formal details depend on the specific setup of orbits and receptive fields. \(\blacksquare\)

## 5. Connectedness

The connectedness predicate is perhaps the most visually compelling example of a function that perceptrons cannot compute.

### The Problem

Consider an \(N \times N\) grid of pixels. Given a set \(X\) of active pixels, determine whether the active pixels form a connected figure (i.e., any two active pixels can be joined by a path through adjacent active pixels).

### Theorem

Theorem (Minsky and Papert). Connectedness cannot be computed by diameter-limited perceptrons with uniformly bounded local receptive fields. On larger grids, the required receptive-field size must grow with the geometric size of the image; the exact lower bound depends on the formal setup.

### Proof Sketch

The key idea is to construct two figures that are identical within any local neighborhood but differ globally in connectedness:

1. Figure A (connected): A spiral or long winding path that passes through many regions of the grid.

2. Figure B (disconnected): The same path, broken at a single point far from any local neighborhood being examined.

Any partial predicate with receptive field smaller than the distance between the endpoints cannot distinguish these two figures. Therefore, no bounded-order perceptron can compute connectedness.

### Intuition

Connectedness is inherently a global property. To determine whether two distant pixels are connected, you must trace a path between them, which may require examining the entire image. No collection of local observations can reliably determine global connectivity.

Show code cell source Hide code cell source

    # Visual demonstration: connected vs. disconnected figures
    # that look identical locally

    fig, axes = plt.subplots(1, 2, figsize=(14, 6))

    N = 15

    # Create a winding path
    def create_path(N):
        path = []
        # Horizontal across row 2
        for j in range(1, N-1):
            path.append((2, j))
        # Down right side
        for i in range(2, N-2):
            path.append((i, N-2))
        # Horizontal across near bottom
        for j in range(N-2, 0, -1):
            path.append((N-3, j))
        # Down left side
        for i in range(N-3, 5, -1):
            path.append((i, 1))
        # Horizontal in middle
        for j in range(1, N-3):
            path.append((6, j))
        # Down again
        for i in range(6, 10):
            path.append((i, N-4))
        return path

    path = create_path(N)

    # Connected version
    grid_connected = np.zeros((N, N))
    for (i, j) in path:
        if 0 <= i < N and 0 <= j < N:
            grid_connected[i, j] = 1

    # Disconnected version: break the path at one point
    grid_disconnected = grid_connected.copy()
    break_point = path[len(path) // 2]  # break in the middle
    grid_disconnected[break_point[0], break_point[1]] = 0

    ax1 = axes[0]
    ax1.imshow(grid_connected, cmap='Blues', interpolation='nearest')
    ax1.set_title('Connected Figure', fontsize=14)
    ax1.set_xticks(range(N))
    ax1.set_yticks(range(N))
    ax1.grid(True, alpha=0.3)

    ax2 = axes[1]
    ax2.imshow(grid_disconnected, cmap='Blues', interpolation='nearest')
    ax2.set_title('Disconnected Figure (one pixel removed)', fontsize=14)
    # Mark the break point
    ax2.plot(break_point[1], break_point[0], 'rx', markersize=15, markeredgewidth=3)
    ax2.annotate('Break here', (break_point[1], break_point[0]),
                 xytext=(break_point[1]+1.5, break_point[0]-1.5),
                 fontsize=11, color='red',
                 arrowprops=dict(arrowstyle='->', color='red'))
    ax2.set_xticks(range(N))
    ax2.set_yticks(range(N))
    ax2.grid(True, alpha=0.3)

    plt.suptitle('Connectedness: A single pixel change far from any local view\n'
                 'changes the global property. No local predicate can detect this.',
                 fontsize=13, y=1.02)
    plt.tight_layout()
    plt.show()

    print(f"Total active pixels (connected): {int(grid_connected.sum())}")
    print(f"Total active pixels (disconnected): {int(grid_disconnected.sum())}")
    print(f"Difference: just 1 pixel at position {break_point}")

    Total active pixels (connected): 54
    Total active pixels (disconnected): 53
    Difference: just 1 pixel at position (12, 8)

## 6. Order Results: Summary Table

The following table summarizes the key results from Minsky and Papert’s analysis. It shows the order (minimum receptive field size) required for various predicates.

Predicate | Order Required | Notes
--- | --- | ---
OR | 1 | \(w_i = 1\), \(\theta = 0.5\)
AND | 1 | \(w_i = 1\), \(\theta = n - 0.5\)
MAJORITY | 1 | \(w_i = 1\), \(\theta = n/2\)
PARITY | \(n\) | Must examine ALL inputs
Connectedness | \(\Omega(\sqrt{N})\) for \(N \times N\) grid | Inherently global
Convexity | \(\Omega(\sqrt{N})\) | Similar to connectedness
Euler number | \(O(1)\) | Surprisingly local!

### Key Observations

1. OR, AND, MAJORITY are all order 1: each partial predicate examines a single input. These are exactly the linearly separable functions.

2. PARITY is worst-case: it requires order \(n\) (the maximum possible). No local information helps at all.

3. Connectedness is between: it requires large but not maximal order. The \(\Omega(\sqrt{N})\) bound reflects the fact that you must “see across” the image.

4. Euler number (number of connected components minus number of holes) is surprisingly computable by a low-order perceptron, because it can be expressed as a sum of local contributions.

Show code cell source Hide code cell source

    # Demonstrate: OR, AND, MAJORITY are order-1 (linearly separable)
    # while PARITY is not

    n_bits = 4

    # Generate all 2^n binary inputs
    inputs = np.array([[int(b) for b in format(i, f'0{n_bits}b')] for i in range(2**n_bits)])

    # Define predicates
    def or_pred(x): return int(np.sum(x) >= 1)
    def and_pred(x): return int(np.sum(x) == n_bits)
    def majority_pred(x): return int(np.sum(x) > n_bits/2)
    def parity_pred(x): return int(np.sum(x) % 2 == 1)

    predicates = [
        ('OR', or_pred, 'sum >= 1'),
        ('AND', and_pred, f'sum = {n_bits}'),
        ('MAJORITY', majority_pred, f'sum > {n_bits}/2'),
        ('PARITY', parity_pred, 'sum mod 2')
    ]

    fig, axes = plt.subplots(1, 4, figsize=(18, 4))

    for idx, (name, pred, rule) in enumerate(predicates):
        ax = axes[idx]
        sums = np.sum(inputs, axis=1)
        outputs = np.array([pred(x) for x in inputs])

        # Plot: x-axis = sum of inputs, y-axis = output
        # Jitter for visibility
        np.random.seed(42)
        jitter = np.random.uniform(-0.1, 0.1, len(sums))
        colors = ['blue' if o == 0 else 'red' for o in outputs]

        ax.scatter(sums + jitter, outputs + jitter * 0.3, c=colors, s=60, alpha=0.7, edgecolors='black')
        ax.set_xlabel('Sum of inputs', fontsize=11)
        ax.set_ylabel('Output', fontsize=11)
        ax.set_title(f'{name}\n(Rule: {rule})', fontsize=12)
        ax.set_yticks([0, 1])
        ax.set_xticks(range(n_bits + 1))

        # Check if the predicate depends only on the sum (order 1)
        sum_consistent = True
        for s in range(n_bits + 1):
            mask = sums == s
            if mask.any():
                vals = outputs[mask]
                if len(set(vals)) > 1:
                    sum_consistent = False
                    break

        order_str = "Order 1" if sum_consistent else f"Order {n_bits}"
        color = 'green' if sum_consistent else 'red'
        ax.text(0.5, -0.2, order_str, transform=ax.transAxes, ha='center',
                fontsize=13, fontweight='bold', color=color)

    plt.suptitle(f'Predicates on {n_bits}-bit inputs: Order-1 predicates depend only on the sum',
                 fontsize=14, y=1.05)
    plt.tight_layout()
    plt.show()

    print("\nNotice: OR, AND, MAJORITY all produce consistent outputs for each sum value.")
    print("PARITY does not: inputs with the same sum can have different parity.")
    print("This is why PARITY requires order n --- the sum alone is not enough.")

    Notice: OR, AND, MAJORITY all produce consistent outputs for each sum value.
    PARITY does not: inputs with the same sum can have different parity.
    This is why PARITY requires order n --- the sum alone is not enough.

## 7. The AI Winter

The publication of Perceptrons in 1969 had consequences far beyond what a mathematics monograph normally achieves. It contributed to what is now called the first AI winter — a period of dramatically reduced funding, interest, and research activity in neural networks.

### The Impact

1. Funding dried up. Government agencies (especially DARPA in the US) shifted funding away from neural networks toward symbolic AI. The message — whether accurate or not — was that perceptrons were a dead end.

2. Careers were derailed. Researchers working on neural networks found it difficult to publish papers, get grants, or find academic positions. The field became unfashionable.

3. Research went underground. Neural network work did not stop entirely, but it moved to the margins of the field.

### Frank Rosenblatt’s Death

Frank Rosenblatt, the inventor of the perceptron, died in a boating accident on the Chesapeake Bay on July 11, 1971, at the age of 43. He did not live to see the vindication of his ideas. His death deprived the field of its most passionate advocate at precisely the moment when advocacy was most needed.

### What Survived

Despite the winter, several researchers continued important work on neural networks:

- Stephen Grossberg (1970s–): Developed Adaptive Resonance Theory (ART) and continued rigorous mathematical analysis of neural dynamics.

- Teuvo Kohonen (1970s–): Developed self-organizing maps for unsupervised learning.

- Shun-ichi Amari (1970s–): Developed mathematical foundations for neural learning in Japan.

- Kunihiko Fukushima (1980): Created the Neocognitron, a precursor to convolutional neural networks.

- Paul Werbos (1974): Described the backpropagation algorithm in his PhD thesis, though it went largely unnoticed until the 1980s.

These researchers kept the flame alive during the dark years, and their work provided crucial foundations for the renaissance that would come in the 1980s.

## 7a. Timeline of the AI Winter and Funding Impact

The following visualization shows the dramatic impact of Perceptrons on the trajectory of neural network research, from the optimistic early years through the winter and eventual revival.

Show code cell source Hide code cell source

    import numpy as np
    import matplotlib.pyplot as plt

    # Timeline of funding cuts and the AI Winter
    fig, (ax1, ax2) = plt.subplots(2, 1, figsize=(16, 10), gridspec_kw={'height_ratios': [2, 1]})

    # --- Top panel: Estimated relative funding for neural network research ---
    years = np.arange(1955, 1992)
    # Approximate relative funding curve (stylized)
    funding = np.zeros_like(years, dtype=float)
    for i, yr in enumerate(years):
        if yr < 1957:
            funding[i] = 10 + (yr - 1955) * 5
        elif yr < 1965:
            funding[i] = 20 + (yr - 1957) * 10  # Rapid growth
        elif yr < 1969:
            funding[i] = 100 - (yr - 1965) * 5  # Slight decline
        elif yr < 1970:
            funding[i] = 80 - 40  # Sharp cut after Perceptrons
        elif yr < 1982:
            funding[i] = max(5, 40 - (yr - 1970) * 3)  # Continued decline
        elif yr < 1986:
            funding[i] = 10 + (yr - 1982) * 5  # Slow recovery
        else:
            funding[i] = 30 + (yr - 1986) * 15  # Rapid recovery after backprop

    ax1.fill_between(years, 0, funding, alpha=0.3, color='steelblue')
    ax1.plot(years, funding, 'b-', linewidth=2)

    # Mark key events
    events_top = [
        (1957, 'Perceptron\ninvented', 'green'),
        (1969, 'Minsky-Papert\n"Perceptrons"', 'red'),
        (1971, 'Rosenblatt\ndeath', 'black'),
        (1974, 'Werbos\nbackprop\nthesis', 'orange'),
        (1982, 'Hopfield\nnetworks', 'blue'),
        (1986, 'Backprop\npublished\nin Nature', 'green'),
    ]

    for yr, label, color in events_top:
        idx = yr - 1955
        if 0 <= idx < len(funding):
            ax1.axvline(x=yr, color=color, linestyle='--', alpha=0.5, linewidth=1.5)
            ax1.annotate(label, (yr, funding[idx]),
                         xytext=(yr, funding[idx] + 15),
                         fontsize=9, ha='center', color=color, fontweight='bold',
                         arrowprops=dict(arrowstyle='->', color=color, linewidth=1.5))

    # Shade the AI Winter
    ax1.axvspan(1969, 1982, alpha=0.1, color='red', label='AI Winter (~1969-1982)')

    ax1.set_ylabel('Relative Funding Level\n(stylized)', fontsize=12)
    ax1.set_title('Neural Network Research Funding: The AI Winter', fontsize=14)
    ax1.legend(fontsize=11, loc='upper left')
    ax1.set_xlim(1955, 1991)
    ax1.set_ylim(0, 140)
    ax1.grid(True, alpha=0.3)

    # --- Bottom panel: Key publications and milestones ---
    milestones = [
        (1943, 'McCulloch-Pitts model'),
        (1949, 'Hebb\'s learning rule'),
        (1957, 'Rosenblatt: Perceptron'),
        (1958, 'Convergence Theorem'),
        (1960, 'ADALINE (Widrow)'),
        (1969, 'Perceptrons (book)'),
        (1971, 'Rosenblatt dies'),
        (1974, 'Werbos: backprop'),
        (1980, 'Neocognitron'),
        (1982, 'Hopfield networks'),
        (1985, 'Boltzmann machine'),
        (1986, 'Backprop in Nature'),
        (1988, 'Perceptrons epilogue'),
        (1989, 'Universal Approx. Thm'),
    ]

    for i, (yr, label) in enumerate(milestones):
        side = 1 if i % 2 == 0 else -1
        color = 'red' if 1969 <= yr <= 1982 else 'green' if yr >= 1982 else 'steelblue'
        ax2.plot(yr, 0, 'o', color=color, markersize=8, zorder=5)
        ax2.annotate(label, (yr, 0), xytext=(yr, side * 0.5),
                    fontsize=8, ha='center', va='center', color=color,
                    fontweight='bold',
                    arrowprops=dict(arrowstyle='-', color=color, linewidth=0.5))

    ax2.axhline(y=0, color='black', linewidth=2)
    ax2.axvspan(1969, 1982, alpha=0.1, color='red')
    ax2.set_xlim(1940, 1992)
    ax2.set_ylim(-1.2, 1.2)
    ax2.set_xlabel('Year', fontsize=12)
    ax2.set_title('Key Milestones in Neural Network History', fontsize=13)
    ax2.set_yticks([])
    ax2.grid(True, axis='x', alpha=0.3)

    plt.tight_layout()
    plt.show()

## 8. What Was Correct vs. What Was Overstated

With the benefit of hindsight, we can evaluate Minsky and Papert’s claims more carefully.

### What Was Correct

The mathematical theorems in the book are entirely correct. Single-layer perceptrons genuinely cannot compute XOR, PARITY, connectedness, or many other important functions. The proofs are rigorous and elegant. These results remain valid and important today.

### What Was Acknowledged but Dismissed

Minsky and Papert were well aware that multi-layer networks could overcome the limitations they proved. In the original 1969 edition, they wrote:

> “The perceptron has shown itself worthy of study despite (and even because of!) its severe limitations. It has many features to attract attention: its linearity; its intriguing learning theorem; its clear paradigmatic simplicity as a kind of parallel computation. There is no reason to suppose that any of these virtues carry over to the many-layered version.”

The key phrase is the last sentence: they acknowledged that multi-layer networks existed but expressed skepticism that the desirable properties (especially learnability) would carry over. This was a reasonable concern in 1969, when no efficient learning algorithm for multi-layer networks was known.

### The “No Learning Algorithm” Claim

The most consequential claim was that there was no known way to train multi-layer networks. This was:

- Technically true in 1969: no practical learning algorithm for multi-layer networks was widely known.

- Wrong in spirit: the backpropagation algorithm had been described in various forms (Kelley 1960, Bryson 1961, Dreyfus 1962), and Werbos would describe it explicitly for neural networks in 1974.

### The 1988 Epilogue

In the expanded 1988 edition, Minsky and Papert added a new chapter addressing the backpropagation revolution. They acknowledged the success of multi-layer networks but raised new concerns:

- Training time might be impractical for large networks.

- Local minima might prevent convergence.

- The representations learned might not generalize well.

Some of these concerns proved valid (training time is indeed a challenge), while others were overstated (local minima are less problematic than feared, and generalization has been remarkably successful).

Show code cell source Hide code cell source

    # Timeline visualization: The AI Winter and Recovery

    fig, ax = plt.subplots(figsize=(16, 6))

    # Timeline events
    events = [
        (1943, 'McCulloch-Pitts\nneuron model', 'green'),
        (1949, 'Hebb\'s\nlearning rule', 'green'),
        (1957, 'Rosenblatt\'s\nPerceptron', 'green'),
        (1958, 'Perceptron\nConvergence\nTheorem', 'green'),
        (1969, 'Minsky & Papert\n"Perceptrons"', 'red'),
        (1971, 'Rosenblatt\ndeath', 'black'),
        (1974, 'Werbos:\nbackprop\n(PhD thesis)', 'orange'),
        (1980, 'Fukushima:\nNeocognitron', 'orange'),
        (1982, 'Hopfield\nnetworks', 'blue'),
        (1986, 'Rumelhart et al.:\nbackprop\npublished', 'green'),
        (1988, 'Minsky-Papert\nepilogue', 'purple'),
        (1989, 'Universal\nApprox.\nTheorem', 'green'),
    ]

    # Draw timeline
    years = [e[0] for e in events]
    ax.plot([min(years)-2, max(years)+2], [0, 0], 'k-', linewidth=2)

    for i, (year, label, color) in enumerate(events):
        side = 1 if i % 2 == 0 else -1
        ax.plot(year, 0, 'o', color=color, markersize=10, zorder=5)
        ax.plot([year, year], [0, side * 0.5], '-', color=color, linewidth=1.5)
        ax.text(year, side * 0.6, label, ha='center', va='bottom' if side > 0 else 'top',
                fontsize=8.5, color=color, fontweight='bold')
        ax.text(year, side * 0.15, str(year), ha='center', va='center', fontsize=8, color='gray')

    # Shade the AI Winter
    ax.axvspan(1969, 1982, alpha=0.1, color='blue', label='AI Winter (approx. 1969-1982)')

    ax.set_xlim(1940, 1992)
    ax.set_ylim(-1.5, 1.5)
    ax.set_xlabel('Year', fontsize=12)
    ax.set_title('Timeline: The Rise, Fall, and Revival of Neural Networks', fontsize=14)
    ax.legend(loc='lower right', fontsize=11)
    ax.set_yticks([])
    ax.grid(True, axis='x', alpha=0.3)

    plt.tight_layout()
    plt.show()

## 9. Exercises

### Exercise 9.1: MAJORITY is Order 1

The MAJORITY predicate on \(n\) bits returns 1 if more than half the bits are 1:

\[\begin{split}\text{MAJORITY}(x_1, \ldots, x_n) = \begin{cases} 1 & \text{if } \sum_i x_i > n/2 \\ 0 & \text{otherwise} \end{cases}\end{split}\]

Explain why MAJORITY can be computed by an order-1 perceptron (i.e., a classical Rosenblatt perceptron). Give the explicit weights and threshold.

Hint: What are the partial predicates \(\varphi_i\) for an order-1 perceptron?

### Exercise 9.2: Connectedness Requires Global Information

Give an intuitive explanation (not a formal proof) of why determining whether a set of pixels forms a connected figure requires looking at the entire image. Use the following thought experiment:

Imagine you can only look at small patches of the image (say, \(3 \times 3\) regions). Construct two images that look identical in every \(3 \times 3\) patch but differ in connectivity. What property of the path forces you to look at a large region?

### Exercise 9.3: The 1988 Epilogue

In the 1988 expanded edition of Perceptrons, Minsky and Papert added a chapter responding to the backpropagation revolution. Consider the following questions:

1. What specific concerns did they raise about the scalability of backpropagation?

2. Which of these concerns have been validated by subsequent research, and which have been resolved?

3. In what sense was their original (1969) skepticism about multi-layer learning algorithms justified, and in what sense was it overstated?

Write a thoughtful 1-page response addressing these questions.

Show code cell source Hide code cell source

    # Space for Exercise 9.1: Verify that MAJORITY is order-1

    n = 5  # number of bits

    # Generate all 2^n inputs
    inputs = np.array([[int(b) for b in format(i, f'0{n}b')] for i in range(2**n)])

    # Order-1 perceptron for MAJORITY:
    # phi_i(X) = x_i (each partial predicate looks at one bit)
    # weights: alpha_i = 1 for all i
    # threshold: theta = n/2

    w = np.ones(n)  # all weights = 1
    theta = n / 2    # threshold

    print(f"MAJORITY on {n} bits:")
    print(f"Weights: {w}")
    print(f"Threshold: {theta}")
    print(f"Decision: output 1 iff w.x > theta, i.e., sum(x) > {theta}")
    print()

    correct = 0
    total = 0
    for x in inputs:
        pred = int(np.dot(w, x) > theta)
        true = int(np.sum(x) > n/2)
        if pred == true:
            correct += 1
        total += 1

    print(f"Accuracy: {correct}/{total} = {correct/total:.1%}")
    print("\nMAJORITY is correctly computed by an order-1 perceptron.")
    print("Each partial predicate examines exactly one input bit.")

    MAJORITY on 5 bits:
    Weights: [1. 1. 1. 1. 1.]
    Threshold: 2.5
    Decision: output 1 iff w.x > theta, i.e., sum(x) > 2.5

    Accuracy: 32/32 = 100.0%

    MAJORITY is correctly computed by an order-1 perceptron.
    Each partial predicate examines exactly one input bit.