Source: Minsky, M., & Papert, S. (1967). Linearly Unrecognizable Patterns. In Mathematical Aspects of Computer Science (Vol. 19). American Mathematical Society.
Artificial Intelligence Memo No. 140
LINEARLY UNRECOGNIZABLE PATTERNS
Marvin Minsky and Seymour Papert
Massachusetts Institute of Technology, Cambridge, Massachusetts
Reprinted from Proceedings of Symposia in Applied Mathematics, Volume 19
Mathematical Aspects of Computer Science, American Mathematical Society, 1967
Introduction
The central theme of this study is the classification of certain geometrical properties according to the type of computation necessary to determine whether a given figure has them. Consider, for example, the following algorithm to determine whether a figure X is convex. For each pair of points (p, q) we define the function:
ϕ_{p,q}(X) = 1 if (p ∈ X and q ∈ X and midpoint(p, q) ∉ X)
ϕ_{p,q}(X) = 0 otherwise.
Then X is convex if and only if no ϕ_{p,q}(X) = 1 for any pair of points (p, q). This shows, in a sense we shall presently define more precisely, that the “global” property of convexity can be determined by a simple computation from the “local” properties ϕ_{p,q}. Thus, if ϕ_{convex}(X) means that “X is convex,” we have:
ϕ_{convex}(X) ⇔ ∑_{p,q} ϕ_{p,q}(X) < 1.
Now we generalize this. We say that a property Ψ is of order k if k is the smallest integer for which there exists a family Φ of predicates each of which depends only on a subset of k points of the figure X, and real numbers α_ϕ associated with each member of Φ such that:
Ψ(X) ⇔ (∑_{ϕ ∈ Φ} α_ϕ ϕ(X) > 0).
In this sense, we can assert that the order of ϕ_{convex} is at most 3. The determination of the orders of simple geometrical properties turns out to be far from trivial and presents many surprises. In fact, the greater part of the following analysis seems to be needed to prove that connectedness is not of any finite order, i.e.,
There is no k for which connectedness is of order k.
This remains true if we relax the definitions, as we shall, to make the sums finite by considering the plane as a fine-grained infinite chess-board, considering its squares to be points, and allowing only figures which contain each square entirely or not at all—that is, we will consider a discrete model of geometry.
Apart from the purely mathematical interest of the results that come from it, we consider the concept of finite order worthy of study for a number of reasons connected with the theories of computation and of pattern recognition. We shall briefly outline some of these reasons.
Motivation of This Study
(a) Local vs. global geometric properties. In problems of geometric pattern recognition, one is led to ask: to what extent can one use “local” properties—evidence obtained from looking at small portions of an object—as a basis for judgements about the “global” character of the object. For example, one can distinguish “line” drawings from other pictures on the basis of the existence of no interior points in the drawing—and this can be determined by a simple combination of evidence obtained from examining arbitrary small neighborhoods. On the other hand, one cannot obtain “local” evidence in favor of a drawing being “connected”—or so one might suspect—without having to combine such collections of evidence by a very complicated procedure.
Our first attempt to study this was based on the idea of diameter-restricted predicates, i.e., the restriction on the “local” properties is on the diameter of the set of points on which they depend rather than the number of points. The results of this study are summarized in §IX. However it soon became clear that the more interesting concept is order-restriction, and that the distinction we were seeking was not so much a question of geometry as a question about the theory of computation.
(b) Serial vs. parallel computation. What characterizes the extent to which an algorithm can have an essentially serial, as opposed to parallel, character? That is, to what degree can a computation be sped-up by doing several subcomputations at the same time? One would suspect, for example, that in many successive approximation computations there is little to be gained except, at great expense and redundancy, by parallel processing. We were led to suppose that the same is true for geometric connectedness recognition. One way to recognize that a set is disconnected (connected) is to find that there is a (no) curve dividing the set without intersecting it. One could therefore examine in parallel all possible separating curves, rather than serially trace through the paths within the set. But it would seem that the price of speeding-up the computation this way is superbly costly, and one looks for a way to get theoretical estimates of what is the exchange rate between the minimal serial and parallel amounts of computation. (The goal must be an exchange-cost curve.) One might hope that study of a particular problem, e.g., connectedness, would yield some insight into this general question of computation complexity for finite problems comparable with, say, that achieved in the theory of complexity of the recursive functions (Blum).
(c) Theory of perceptrons and linear separability. The pattern-recognition scheme known as the perceptron (Rosenblatt [6]) is known to be capable of learning to make any pattern discrimination which is within the scope of its potential ability—that is, if there is a set of parameter values that will suffice, it will find them. Thus, a good deal is known about this system’s learning ability, and therefore one is particularly interested to know what is the scope of potential ability. Curiously enough, there seems to be nothing in the large perceptron literature on this question, and the present paper seems to be the first to link the linear-separation problem with the geometric-property problem.
The perceptron (and its derivatives) are of considerable interest mathematically because they are perhaps the simplest nontrivial parallel machines. One therefore ought to understand them thoroughly—as a sort of “linear case” if one is to get any satisfactory theory of “higher-order” parallel computation schemes.
(d) Mathematical aspects. Linear separation computations have considerable mathematical significance in themselves. For example, if we ask for a maximum likelihood decision process based on Bayesian use of the results of statistically independent experiments, one obtains (Minsky and Selfridge [8]) a linear separation procedure. For another example, the generalization (in §I) of Boolean disjunctive normal form appears to yield surprising and fruitful results. Finally, the combination of group theory and linear inequalities seems to promise some new combinatorial techniques.
I. Theory of Linear Boolean Separation Functions
In this section we shall confine ourselves to the analysis of the linear representation of predicates defined on an abstract set R, without any additional mathematical structure. The theorems proved here will be applied in later sections to sets with geometrical or topological structures. When necessary for truth R must be taken as finite.
Our theory deals with predicates defined on subsets of a given base space which we shall consistently denote by R. We use the following notational conventions:
(i) Let R be an arbitrary set and F a family of subsets of R. Using the letters X, Y, Z for subsets of R it is natural to associate with F a predicate ϕ_F(X) which is TRUE if and only if X ∈ F.
(ii) We shall use the letters Φ and Ψ to denote predicates defined on the set of subsets of R. We shall use the notation Ψ(X) sometimes to mean the predicate whose value for a given X is TRUE or FALSE, sometimes to mean a binary set function whose value is 1 or 0. When we wish to employ the two senses in the same context we adapt the notation ⌈Ψ(X)⌉ for the binary function whose value is 1 if Ψ(X) is TRUE and 0 if Ψ(X) is FALSE.
(iii) Occasionally it will be convenient in examples to use the traditional representation of Ψ(X) as a function of n “Boolean variables” where n = |R|. If the elements of R are x_1, …, x_n it is traditional to think of a subset X of R as an assignation of the values 1 or 0 to x_i according to whether the point x_i is in X or not, i.e., x_i is used ambiguously to stand for the i-th point in the given enumeration of R, and for the set function ⌈x_i ∈ X⌉. This notation is particularly convenient when Φ is represented in the form of a standard Boolean function of two variables. Thus x_i ∨ x_j is a way of writing the set function ϕ(X) = ⌈x_i ∈ X or x_j ∈ X⌉.
(iv) We need to express the idea that a function may depend only on a subset of the points of R. We denote by S(ϕ) the smallest subset S of R with the property that, for any subset X, ϕ(X) = ϕ(X ∩ S). We call S(ϕ) the support of ϕ.
(v) Let Φ be a set of binary set-functions on R. We say that Ψ is a linear threshold function with respect to Φ if to each member ϕ of Φ there corresponds a real number α_ϕ such that, for some real number θ: Ψ(X) = ⌈∑_{ϕ ∈ Φ} α_ϕ ϕ(X) > θ⌉. This is often written more briefly as Ψ = ⌈∑ α_ϕ ϕ > θ⌉. We denote by L(Φ) the set of functions expressible in this way.
(vi) We now introduce the central concept of order. The order of Ψ is the smallest k for which there is a Φ satisfying Ψ ∈ L(Φ) and ϕ ∈ Φ ⇒ |S(ϕ)| ≤ k, where |S(ϕ)| is the cardinality of S(ϕ).
Functions of order 1 appear in the literature under the name of “linear threshold functions.” It should be noted that the order of a constant function is zero, hence the number θ in the definition of L(Φ) can be replaced by 0 (or any other number) without changing the definition of order. Note also that the definition is unchanged if we use “≥”, “≤”, or “<” instead of “>” (assuming, when necessary, that R is finite).
(vii) ϕ is called a mask if there is a set A such that ϕ(X) = ⌈X ⊃ A⌉. We denote this function by ϕ_A. In point-function notation a mask is a function of the form y_1 ∧ y_2 ∧ … ∧ y_l where {y_i} is the subset A of R. In particular constant functions are masks.
Linear Representation
PROPOSITION. All masks are of order 1.
PROOF. For each x ∈ A define ϕ_x(X) as ⌈x ∈ X⌉. Then ϕ_A = ⌈∑_{x ∈ A} ϕ_x ≥ |A|⌉. In particular the functions ϕ_x and ϕ_y are of order 1. Similarly the functions x ∨ y, x ∧ y, xy are of order 1. But the “exclusive or,” x ⊕ y, and its complement, x = y, are of order 2.
EXAMPLE (i). x_1 ∨ x_2 ∨ x_3 is of order 1: ⌈x_1 + x_2 + x_3 > 0⌉.
x_1 ∧ x_2 ∧ x_3 is also of order 1: ⌈x_1 + x_2 + x_3 > 2⌉.
x_1 x̄_2 = ⌈x_1 + (1 – x_2) > 1⌉ = ⌈x_1 – x_2 > 0⌉ is of order 1.
x_2 ∨ x̄_1 = ⌈x_2 + (1 – x_1) > 0⌉ = ⌈x_2 – x_1 > -1⌉ (which is also x_1 ⊃ x_2) is of order 1.
EXAMPLE (ii). x_1 = x_2, which is x_1 x_2 ∨ x̄_1 x̄_2 = ⌈x_1 x_2 + (1 – x_1)(1 – x_2) > 0⌉ = ⌈2x_1 x_2 – x_1 – x_2 > -1⌉, is of order 2.
EXAMPLE (iii). Let M be an integer 0 < M < |R|. Then the “counting function” Ψ^M(X) = ⌈|X| = M⌉, which recognizes when X contains exactly M points, is of order 2.
PROOF. Consider the representation Ψ^M(X) = ⌈(2M – 1) ∑_i x_i + (-2) ∑_{i < j} x_i x_j ≥ M^2⌉. For any figure X there will be |X| terms x_i with value 1, and |X|(|X| – 1)/2 terms x_i x_j with value 1. Then the predicate is equal to Ψ^M(X) = ⌈(2M – 1)|X| – |X|(|X| – 1) – M^2 ≥ 0⌉, and the only (integer) value of |X| for which this is true is |X| = M. Note that the linear form for the counting function does not contain R explicitly. Hence it works as well for an infinite space R.
EXAMPLE (iv). The functions ⌈|X| ≥ M⌉ and ⌈|X| ≤ M⌉ are of order 1 because they are represented by ⌈∑ x_i ≥ M⌉ and ⌈∑ x_i ≤ M⌉.
EXAMPLE (v). We can obtain an arbitrary function f(|X|) of the area of a figure from the predicates used in (iv) above by writing:
f(X) = f(0) + ∑_{k=1}^n (f(k) – f(k – 1)) · ⌈|X| ≥ k⌉.
The order of a function can be determined by examining its representation as a linear threshold with respect to sets of masks. To prove this we first show:
THEOREM (POSITIVE NORMAL FORM THEOREM). Every Ψ is a linear threshold function with respect to the set of all masks.
PROOF. The well-known disjunctive-normal-form theorem for Boolean functions tells us that any Boolean function Ψ(x_1, …, x_n) can be written in the form (DNF): Ψ(X) = ⋁_{i ∈ I} Ψ_i(X), where Ψ_i(X) = y_{i1} y_{i2} … y_{in}, where for each i and j, y_{ij} = x_j or y_{ij} = x̄_j. We can write this in linear form as Ψ(X) = ⌈∑_{i ∈ I} Ψ_i > 0⌉ because, for any X, at most one term of the DNF is nonzero. Furthermore, since numerically x̄_i = 1 – x_i, each Ψ_i can be written as x_{i1} … x_{im} (1 – x_{im+1}) … (1 – x_{in}). Multiplying this out, we obtain an expression of the form Ψ_i(X) = ∑ β_j Z_j, where Z_j is a mask. So Ψ_i is a linear combination of masks. It follows immediately that ∑_{i ∈ I} Ψ_i is itself a linear combination of masks: Ψ = ∑ α_i Z_i.
REMARK. The above construction shows not only that any Boolean function is “linear” in the set of masks in the “Ψ = ⌈∑ α_i ϕ_i > θ⌉” sense, but is also linear in a stronger “Ψ = ∑ α_i ϕ_i” sense. It is interesting that this form is unique, and is therefore entitled to be called a “positive normal form.”
THEOREM. Ψ is of order k iff k is the smallest number for which there exist a set of masks Φ satisfying ϕ ∈ Φ ⇒ |S(ϕ)| ≤ k and Ψ ∈ L(Φ).
EXAMPLE (vi). A “Boolean form” has order no higher than the degree in its disjunctive normal form. Thus ∑ α_{ijk} x_i x_j x̄_k = ∑ α_{ijk} x_i x_j – ∑ α_{ijk} x_i x_j x_k, so that the negations can be removed without raising order.
THEOREM. If Ψ_1 has order O_1 and Ψ_2 has order O_2, then Ψ_1 ⊕ Ψ_2 and Ψ_1 = Ψ_2 have order ≤ O_1 + O_2.
PROOF. The idea is to multiply together the positive mask representations ⌈(∑_1 ϕ – θ_1)(∑_2 ϕ – θ_2) > 0⌉ to get a positive form of order ≤ O_1 + O_2.
Question. What can be said about the orders of ⌈Ψ_1 ∧ Ψ_2⌉ and ⌈Ψ_1 ∨ Ψ_2⌉? The answer may be surprising: it is shown in §IV that for any order n, there exists a pair of predicates Ψ_1 and Ψ_2 both of order 1 for which (Ψ_1 ∧ Ψ_2) and (Ψ_1 ∨ Ψ_2) have order > n.
II. Group Theory of Linear Inequalities
In this section we consider linear threshold functions that are invariant under groups of permutations of the points of the base-space R. The purpose of this, realized finally in §VI, is to establish a connection between the geometry of R and the question of when a geometric predicate can be a linear threshold function.
THE GROUP INVARIANCE THEOREM. Let:
(i) G be a finite group of permutations of R;
(ii) Φ be a set of predicates on R closed under G, i.e., ϕ ∈ Φ, g ∈ G ⇒ ϕ^g ∈ Φ;
(iii) Ψ be in L(Φ) and invariant under G.
Then there exists a linear representation of Ψ, Ψ = ⌈∑_{ϕ ∈ Φ} β_ϕ ϕ > 0⌉, for which the coefficients β_ϕ depend only on the G-equivalence class of ϕ, i.e., ϕ =_G ϕ’ ⇒ β_ϕ = β_ϕ’.
PROOF. Divide Φ into equivalence classes by the relation =_G: Φ = Φ_1 ∪ … ∪ Φ_k. Now let Ψ = ⌈∑_{ϕ ∈ Φ} α_ϕ ϕ(X) > 0⌉ be any linear representation of Ψ and choose X such that Ψ(X) is true, i.e., ∑_{ϕ ∈ Φ} α_ϕ ϕ(X) > 0. Since Ψ(X) = Ψ(X_g), it follows that for each g ∈ G, ∑_{ϕ ∈ Φ} α_ϕ ϕ(X_g) = ∑_{ϕ ∈ Φ} α_ϕ ϕ^g(X) > 0. Summing over all g ∈ G yields ∑_{g ∈ G} ∑_{ϕ ∈ Φ} α_ϕ ϕ^g(X) > 0. Reordering the summation shows that the averaged coefficients β_i = ∑_{g ∈ G} α_{ϕ g^{-1}} depend only on the equivalence class i. Thus Ψ = ⌈∑_i β_i N_i(X) > 0⌉ where N_i(X) is the number of masks in class Φ_i satisfied by X.
COROLLARY 1. Any function Ψ of order k has a linear representation Ψ = ⌈∑_ϕ α_ϕ ϕ > 0⌉ where Φ is the set of masks of degrees ≤ k and α_ϕ = α_ϕ’ whenever S(ϕ) can be transformed into S(ϕ’) by an element of G.
COROLLARY 2. Let Φ = Φ_1 ∪ … ∪ Φ_n be the decomposition of Φ into equivalence classes by =_G. Then if Ψ is in L(Φ) and is closed under G, Ψ can be written in the form Ψ = ⌈∑ α_i N_i(X) > 0⌉ where N_i(X) = |{ϕ | ϕ ∈ Φ_i, ϕ(X) = 1}|.
COROLLARY 3 (THE TRIVIALITY OF INVARIANT PREDICATES OF ORDER 1). Let G be any transitive group of permutations on R. Then the only first-order predicates invariant under G are of the forms Ψ(X) = ⌈|X| > m⌉ or Ψ(X) = ⌈|X| < m⌉ for some m.
III. Applications of the Group-Invariance Theorem
The Parity Function
We develop in some detail the analysis of the particular predicate PAR defined by Ψ_{PAR}(X) = ⌈|X| is odd⌉.
THEOREM. Ψ_{PAR} is of order |R|. That is, to compute Ψ_{PAR} requires at least one predicate whose support covers the whole space R!
PROOF. Let G be the group of all permutations of R. Clearly PAR is invariant under G. Suppose that Ψ_{PAR} = ⌈∑ α_i ϕ_i > 0⌉ where the ϕ_i are masks with |S(ϕ_i)| ≤ K. Then Ψ_{PAR} = ⌈∑_{j=0}^K α_j C_j(X) > 0⌉ where C_j(X) = (|X| choose j) is the number of j-element subsets of X. The polynomial P(|X|) = ∑_{j=0}^K α_j (|X| choose j) must change sign |R| times as |X| goes from 0 to |R|. Since P is a polynomial of degree K, it follows that K = |R|.
THEOREM. If Ψ_{PAR} ∈ L(Φ) and if Φ contains only masks, then Φ contains all the masks.
COROLLARY 1. If Ψ_{PAR} ∈ L(Φ), then Φ must contain at least one ϕ for which |S(ϕ)| = |R|.
COROLLARY 2. Let Φ_A be the set of all Ψ_{PAR} for proper subsets A of R. Then Ψ_{PAR}^R ∉ L(Φ_A).
Coefficients of the Parity Function
THEOREM. For each M, (-1)^M α_{M+1} > 2^{M+1}.
This shows that it is impractical to use mask-like ϕ’s to recognize parity-like functions: even if one could afford the huge number of ϕ’s, one would have also to cope with huge ranges of their coefficients! The information capacity necessary to store the set {α_i} of coefficients is greater than that needed to store the entire set of patterns recognized by Ψ_{PAR}.
The “One-in-a-box” Theorem
THEOREM. Let A_1, …, A_m be disjoint subsets of R and define the predicate Ψ(X) = ⌈(∀ i)(|X ∩ A_i| > 0)⌉—i.e., there is at least one point of X in each A_i. Then if for all i, |A_i| = 4m^2, the order of Ψ is m.
COROLLARY. If R = A_1 ∪ A_2 ∪ … ∪ A_m, the order of Ψ is at least (|R|/4)^{1/3}.
IV. The AND-OR Theorem
We have already remarked that if R = A ∪ B ∪ C, the predicate Ψ_1(X) = ⌈|X ∩ A| > |X ∩ C|⌉ is of order 1, and stated that Ψ(X) = ⌈|X ∩ A| > |X ∩ C| ∧ |X ∩ B| > |X ∩ C|⌉ is not of bounded order as |R| becomes large. We formalize this as:
THEOREM (AND-OR THEOREM). If Ψ_k(X) is the predicate of the stated form for |R| = 3k, then the order of Ψ_k → ∞ as k → ∞.
V. The “Order-Limited” Perceptron
Now we consider the problem of computing the order of a number of interesting geometrical predicates. We divide the Euclidean plane E^2 into squares as an infinite chessboard. The set R is taken as the set of squares. A figure X of E^2 is identified with the set of squares of R it intersects.
We list some geometric predicates by order:
(a) k = 1: Under translation invariance, all coefficients are equal, so order-1 predicates can only define area threshold cuts: Ψ = ⌈|X| > A⌉ or Ψ = ⌈|X| < A⌉.
(b) k = 2: With masks of order 2, a figure is characterized by its “difference-vector spectrum.” Order-2 predicates cannot distinguish figures that share the same difference-vector spectrum.
(c) k = 3: The predicate Ψ_{CONVEX}(X) = ⌈X is a single, solid, convex figure⌉ is of order ≤ 3, because Ψ_{CONVEX}(X) = ⌈∑_{a,b,c} ⌈a ∈ X and b ∈ X and midpoint(a,b) ∉ X⌉ < 1⌉ is of order 3. Solid rectangles, hollow rectangles, and hollow squares can also be recognized with order 3.
(d) k = 4: Perimeters of complete circles can be recognized with order k = 4 using concyclic quadruples of points.
VI. Connectivity: A Geometric Property with Unbounded Order
Two points of R are adjacent if they are squares with a common edge. A figure is connected if, given any two points P_1, P_2 of the figure, we can find a path through adjacent squares from P_1 to P_2.
THEOREM. The predicate Ψ(X) = ⌈X is connected⌉ has arbitrarily large orders as R grows in size.
PROOF. By constructing a 2D array of (2m + 1) × 4m^2 squares where odd rows are fixed black and even rows require at least one black square each to connect the odd rows, connectivity on this figure reduces directly to the “One-in-a-Box” property, which requires order m. Thus connectivity has unbounded order.
Some Other Geometrical Predicates with Unbounded Order:
1. Symmetry: X is symmetric about some line in the plane.
2. “Twins”: X consists of two disjoint congruent subfigures.
3. Concentricity: X contains an interior hole.
Curiously enough, the predicate “X has a single connected component OR X contains a hole” has order 2, using the Euler relation (Holes = 1 + Edges – Vertices – Faces), even though each property separately has unbounded order.
VII. Connectivity and Serial Computation
While parallel recognition of connectivity requires unbounded order, serial computation of connectivity is remarkably efficient. We present a serial algorithm that tests connectivity by tracing boundary curves.
THEOREM. For any ε > 0, there is a 2-symbol Turing machine that can verify the connectivity of a figure X on any rectangular array R, using less than (2 + ε) log_2 |R| squares of tape.
THEOREM. For any ε > 0, there is a 2-symbol Turing machine that can verify the convexity of a figure X on any rectangular array R, using less than (1 + ε) log_2 |R| squares of tape.
VIII. Multi-Layer Perceptrons
Gamba Machines. Consider functions of the form ⌈∑_j β_j ⌈∑_i α_{ij} x_i > θ_j⌉ > θ⌉. Proposed by A. Gamba, this is an order-1 composition of order-1 perceptrons. While it neatly solves Parity and AND-OR functions, deeper geometric properties like connectivity still require an exponential number of terms approaching the number of simple closed curves in R.
IX. The Diameter-Limited Perceptron
In a diameter-limited perceptron, each ϕ_i can only see a region of diameter ≤ D.
• What it CAN recognize: Blank/black pictures, area threshold cuts, nonintersecting lines, single triangles, single rectangles, and absolute template-matching in a fixed position.
• What it CANNOT recognize: A figure containing exactly one single black point (cannot be recognized position-independently), bounded area segments (A_1 ≤ Area ≤ A_2), and connectivity.
References
1. W. W. Bledsoe and I. Browning, Pattern recognition and reading by machine, Proc. Eastern Joint Computer Conference, 1959.
2. A. Gamba, Optimum performance of learning machines, Proc. I.R.E. 49 (1961), 349.
3. N. Nilsson, Learning machines, McGraw-Hill, New York, 1965.
4. A. B. J. Novikoff, Integral geometry as a tool in pattern perception, Principles of Self-Organization, Pergamon, New York, 1961.
5. W. Pitts and W. S. McCulloch, How we know universals, Bull. Math. Biophys. 9 (1947), 127–147.
6. F. Rosenblatt, Principles of Neurodynamics, Spartan, Washington, D.C., 1962.
7. C. J. Zeeman, Topology of the brain, Topology of 3-Manifolds, Prentice-Hall, 1961.
8. M. Minsky and O. G. Selfridge, Learning in random nets, Proc. London Information Theory Sympos., Butterworth, London, 1961.