Source Summary: Minsky & Papert — Perceptrons
Full title: Perceptrons: An Introduction to Computational Geometry
Authors: Marvin L. Minsky, Seymour A. Papert
Affiliation: MIT
Venue: MIT Press (1969); Expanded edition 1988; Reissue with new foreword by Léon Bottou 2017
PDF: papers/minsky-1969-perceptrons-an-introduction-to-computational.pdf
Contributions
- Formal limits of perceptrons — rigorous proofs of what single-layer perceptrons cannot compute.
- XOR and parity — demonstrated that certain simple predicates (parity, connectedness) require unbounded resources in a perceptron.
- Order of predicates — introduced the concept of “order” to characterize computational power; higher-order predicates require exponentially more perceptron units.
- Mathematical rigor in ML — argued that connectionist research needed formal theory, not just empirical tinkering.
Methodology
The Perceptron Model
A perceptron computes:
output = sign(Σ wᵢ φᵢ(x) − θ)
where φᵢ are predicates (local feature detectors) and wᵢ are learned weights.
A diameter-limited perceptron: each φᵢ can only observe a bounded region of the input (at most d pixels).
Key theorems
XOR / parity: A single-layer perceptron cannot compute the parity function on n inputs unless it has exponentially many units. More precisely:
- Any perceptron computing parity of n inputs of order ≤ k requires Ω(n^(k/2)) units
Connectedness: Whether a binary image contains a connected figure cannot be computed by any finite-order diameter-limited perceptron — requires a global predicate that looks at arbitrarily large regions.
Geometric predicates: One-in-a-box, symmetry, and many other natural geometric predicates fall outside low-order perceptrons.
The order concept
A predicate is order k if it can be expressed using logical combinations over groups of at most k input units. Higher order = more global context needed. Perceptrons are limited to computing order-1 or order-2 predicates efficiently.
Historical context
The book was written in response to Rosenblatt’s Perceptron (1958), which generated widespread optimism that simple learning machines would soon replicate human cognition. Minsky and Papert argued this optimism was premature:
- Rosenblatt’s perceptron convergence theorem only guarantees learning when the target function is linearly separable
- Many natural classification tasks are not linearly separable
- The research community was investing in connectionism without adequate theoretical grounding
The 1988 prologue
The expanded edition added a prologue acknowledging the backpropagation revival (1986). Minsky and Papert maintained their position: multi-layer networks lacked adequate theory and relied on hill-climbing with no convergence guarantees.
Léon Bottou’s 2017 foreword
Argues the eventual success of deep learning (especially post-2012 ImageNet) does not contradict Minsky and Papert’s theoretical analysis — it vindicates the learning approach while showing that scale and data can overcome the lack of theory.
Limitations of the analysis
- Focuses exclusively on single-layer perceptrons; Minsky and Papert did not prove limits for multi-layer networks
- The book’s negative results do not apply to modern deep learning architectures
- Critics argued the publication chilled funding for neural network research during the 1970s (“AI winter”)
Key References
- Rosenblatt 1958 — The Perceptron: A Probabilistic Model for Information Storage
- McCulloch & Pitts 1943 — Foundational neuron model
- Vapnik & Chervonenkis 1971 — VC theory (developed independently, related ideas)
- Rumelhart, Hinton, Williams 1986 — Backpropagation (multi-layer, addressed Minsky-Papert limits)