Linearly Unrecognizable Patterns

Linearly Unrecognizable Patterns

By Marvin Minsky and Seymour Papert
MIT – AIM 140

Reprinted from Proceedings of Symposia in Applied Mathematics, Volume 19
MATHEMATICAL ASPECTS OF COMPUTER SCIENCE
Copyright by the American Mathematical Society 1967
Printed in the U.S.A.

This work was supported in part by Project MAC, an M.I.T. research project sponsored by the Advanced Research Projects Agency, Department of Defense, under Office of Naval Research contracts Nonr-4102(01) and (02).

¹ We identify “property” (or “predicate”) with the characteristic function of the set of objects that have the property.

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

ϕ_pq(X) = 1  if p ∈ X and q ∈ X and midpoint(p, q) ∉ X
= 0  otherwise.

Then X is convex if and only if no ϕ_pq(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 ϕ_pq.¹ Thus, if ψ(X) means that “X is convex,” we have

ψ_convex(X) ⇔ ∑_{all (p, q)} ϕ_pq(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 ℱ a family of subsets of R. Using the letters X, Y, Z, for subsets of R it is natural to associate with ℱ a predicate ϕ_ℱ(X) which is TRUE if and only if X ∈ ℱ.

(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. We will usually use this only when there is a possibility of ambiguity, e.g., to distinguish between ⌈3 < 5⌉ = 1, which is true, and 3 < ⌈5 = 1⌉, which 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₁, …, 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(Φ),
ϕ ∈ Φ → |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₁ ∧ y₂ ∧ … ∧ y_k

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) = ⌈x ∈ X⌉. Then

ϕ_A = ⌈∑_{x ∈ A} ψ_x ≥ |A|⌉.

In particular the functions x and x̄ are of order 1. Similarly the functions x ∨ y, x ∧ y are of order 1. But the “exclusive or,” x ⊕ y and its complement, x ≡ y, are of order 2.

EXAMPLE (i). x₁ ∨ x₂ ∨ x₃ is of order 1:

⌈x₁ + x₂ + x₃ > 0⌉.

x₁ ∧ x₂ ∧ x₃ is also of order 1:

⌈x₁ + x₂ + x₃ > 2⌉.

x₁ x̄₂ = ⌈x₁ + (1/2 – x₂) > 1/2⌉ = ⌈x₁ – x₂ > 0⌉ is of order 1.

x₂ ∨ x̄₁ = ⌈x₂ + (1 – x₁) > 0⌉ = ⌈x₂ – x₁ > -1⌉ is of order 1.

EXAMPLE (ii). x₁ ⊕ x₂ is of order 2:

x₁ x̄₂ ∨ x̄₁ x₂ = ⌈x₁ – x₂ > 0⌉ ∨ ⌈x₂ – x₁ > 0⌉ which is also x₁ ≠ x₂;

x₁ x₂ ∨ x̄₁ x̄₂ = ⌈x₁ x₂ + (1 – x₁)(1 – x₂) > 0⌉ = ⌈2 x₁ x₂ – x₁ – x₂ > -1⌉ is of order 2. (Proof that it is not order 1 is in §II.)

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) ∑_{all} x_i + (-2) ∑_{i ≠ j} x_i x_j ≥ M²⌉.

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) + 1 – M² > 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. Q.E.D.

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}^{|R|} (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₁, …, 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. Hence, we can replace logical “∨” by arithmetic “+”. Furthermore, since numerically x̄_i = 1 – x_i, each ψ_i can be written in the form

ψ_i(X) = x_{i1} ··· x_{im} (1 – x_{i_{m+1}}) ··· (1 – x_{in}),

supposing that the negative terms are at the right. Multiplying this out, we obtain an expression of the form

ψ_i(X) = ∑ β_j Z_j

where Z_j is of the form x_{i1} ··· x_{im} x_{h1} ··· x_{hm} with {h₁, …, h_m} ⊂ {i_{m+1}, …, i_n}. But such Z_j are masks, so that ψ_i is a linear combination of masks. It follows immediately that ∑_{i ∈ I} ψ_i is itself a linear combination of masks

ψ = ∑ α_i Z_i

where each α_i is an integer and each Z_i a mask. Q.E.D.

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 “normal form.” We call it a “positive normal form.” To see the uniqueness, suppose that

ψ = ∑ α_i Z_i = ∑ β_i Z_i

and consider the difference

ϕ = (∑ α_i Z_i – ∑ β_i Z_i) = ∑ (α_i – β_i) Z_i = ∑ γ_i Z_i.

Now ϕ(X) must be identically zero. To see this, consider first any set X of one element {x_i}. Then

ϕ(X) = ϕ({x_i}) = γ_{{x_i}} x_i = γ_{{x_i}} · 1 = 0

so γ_{{x_i}} = 0. Next, consider any two-element X = {x_i, x_j}; then

ϕ({x_i, x_j}) = γ_{{x_i, x_j}} x_i x_j + γ_{{x_i}} x_i + γ_{{x_j}} x_j = γ_{{x_i, x_j}} · 1 = 0

so all two-element γ_{{x_i, x_j}} are zero. Similarly, by induction, all the γ’s can be seen to vanish.

The proof of the positive normal form theorem implies also the

THEOREM. ψ is of order k iff k is the smallest number for which there exists 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. This particular order-3 form appears later in a perceptron that recognizes convex figures.

Using this result we develop some more examples of the use of the concept of order.

THEOREM. If ψ₁ has order O₁ and ψ₂ has order O₂, then ψ₁ ⊕ ψ₂ and ψ₁ ≡ ψ₂ have order ≤ O₁ + O₂.

PROOF. The idea is to multiply together the positive mask representations ⌈(∑₁ ϕ – θ₁)(∑₂ ϕ – θ₂) > 0⌉ to get a positive form of order ≤ O₁ + O₂. (Use “>” for ≡ and “<” for ⊕.) This may not work in some cases where ∑₁ = θ₁ or ∑₂ = θ₂. In such cases, it is always possible to replace θ₁ and θ₂ by slightly different values, algebraically independent of the coefficients of ∑₁ and ∑₂, so that the predicates are unchanged but exact equality never holds.

Application.

EXAMPLE (vii). Since ψ^M(X) = ⌈⌈|X| ≥ M⌉ ≡ ⌈|X| ≤ M⌉⌉, we conclude that ψ^M has order 2, the result of Example (iii).

Question. What can be said about the orders of ⌈ψ₁ ∧ ψ₂⌉ and ⌈ψ₁ ∨ ψ₂⌉?

The answer to this question may be surprising, in view of the simple result of the previous theorem: it is shown in §IV that for any order n, there exists a pair of predicates ψ₁ and ψ₂ both of order 1 for which (ψ₁ ∧ ψ₂) and (ψ₁ ∨ ψ₂) have order n. In fact suppose that R = A ∪ B ∪ C where A, B, and C are large disjoint subsets of R. Then ψ₁ = ⌈|X ∩ A| > |X ∩ C|⌉ and ψ₂ = ⌈|X ∩ B| > |X ∩ C|⌉ each have order 1 because they are represented by

⌈∑_{x_i ∈ A} x_i – ∑_{x_i ∈ C} x_i > 0⌉  and  ⌈∑_{x_i ∈ B} x_i – ∑_{x_i ∈ C} x_i > 0⌉

but, as shown in §IV, (ψ₁ ∧ ψ₂) and (ψ₁ ∨ ψ₂) have high orders.

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 §V, is to establish a connection between the geometry of R and the question of when a geometric predicate can be a linear threshold function.

As an introduction to the methods introduced in this section we first consider a simple, almost trivial example. Suppose we wish to prove that the function x₁ x₂ ∨ x̄₁ x̄₂ is not of order 1. To do so we might try to deduce a contradiction from the hypothesis that numbers α, β and θ can be found for which

(1)    ψ(x₁, x₂) = x₁ x₂ ∨ x̄₁ x̄₂ = ⌈α x₁ + β x₂ > θ⌉.

We could proceed directly by writing down the conditions on α, β and θ:

x₁ = 0, x₂ = 0 ⇒ 0 > θ,
x₁ = 1, x₂ = 0 ⇒ α ≤ θ,
x₁ = 0, x₂ = 1 ⇒ β ≤ θ,
x₁ = 1, x₂ = 1 ⇒ α + β > θ.

In this simple case it is easy enough to deduce the contradiction.

But arguments of this sort are hard to generalize to more complex situations involving many variables. On the other hand the following argument, though it may be considered more complicated in itself, leads to elegant generalizations. First observe that the value of ψ is invariant under permutation of x₁ and x₂, that is,

ψ(x₁, x₂) = ψ(x₂, x₁).

Thus

α x₁ + β x₂ > θ,
α x₂ + β x₁ > θ
yields
((α + β)/2) x₁ + ((α + β)/2) x₂ > θ

by adding the inequalities. Similarly

α x₁ + β x₂ ≤ θ,
α x₂ + β x₁ ≤ θ
yields
((α + β)/2) x₁ + ((α + β)/2) x₂ ≤ θ.

It follows that if we write γ for (α + β)/2 then

ψ(x₁, x₂) = ⌈γ x₁ + γ x₂ > θ⌉;

i.e., we can assume that the coefficients of x₁ and x₂ in the linear representation of ψ are equal. It follows that

ψ(X) = ⌈γ |X| > θ⌉  or  ⌈γ |X| – θ > 0⌉

(if we assume that the space R has only the two points x₁ and x₂).

Now consider three values of X,

X₀ = ∅,         |X₀| = 0,  γ |X| – θ > 0,
X₁ = {x₁},      |X₁| = 1,  γ |X| – θ ≤ 0,
X₂ = {x₁, x₂},  |X₂| = 2,  γ |X| – θ > 0.

Since X₀ and X₂ satisfy ψ, and X₁ does not, the first-degree polynomial γ |X| – θ in |X| would have to change direction twice, from positive to negative and back to positive as |X| increases from 0 to 2. This is clearly impossible. Thus we learn something about ψ by averaging it over the permutations that leave it invariant. The method is similar to that used in Haar measure theory. In fact, for order 1, it is the same method.

The generalization of this procedure involves consideration of groups of permutations on the set R and functions invariant under these groups of permutations. In anticipation of application to geometrical problems, we recall the mathematical viewpoint from which every interesting geometrical property is an invariant of some natural transformation group.

Let G be a group of permutations of R; g ∈ G and X ⊂ R and define

X_g = {y | y = xg, x ∈ X}.
ψ^g(X) = ψ(X_g),
ψ ≡_G ϕ ⇔ (∃ g ∈ G)(ψ = ϕ^g).

Thus we define an equivalence relation of ψ’s with respect to a group G.

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 ∈ Φ.

(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:

Φ = Φ₁ ∪ ··· ∪ Φ_k

Now let ψ = ⌈∑_{ϕ ∈ Φ} α_ϕ ϕ(X) > 0⌉ be any linear representation of ψ and choose X such that ψ(X), i.e., ∑_{ϕ ∈ Φ} α_ϕ ϕ(X) > 0. Since ψ(X) = ψ(X_g), it follows that for each g ∈ G

∑_{ϕ ∈ Φ} α_ϕ ϕ(X_g) = ∑_{ϕ ∈ Φ} α_ϕ ϕ^g(X) > 0.

Since the sum of positive quantities is positive we can sum all such equations:

∑_{g ∈ G} ∑_{ϕ ∈ Φ} α_ϕ ϕ^g(X) > 0.

Since Φ = ⋃_{i=1}^k Φ_i, the expression on the left can be written:

∑_{g ∈ G} ∑_{i=1}^k ∑_{ϕ ∈ Φ_i} α_ϕ ϕ^g = ∑_{i=1}^k ∑_{g ∈ G} ∑_{ϕ ∈ Φ_i} α_ϕ ϕ^g.
∑_{i=1}^k ∑_{ϕ ∈ Φ_i} (∑_{g ∈ G} α_ϕ ϕ^g(X)) > 0.

Now observe that the set

Φ_i g = {ϕ g | ϕ ∈ Φ_i} = {ϕ | ϕ ∈ Φ_i} = Φ_i

because any g just permutes members of an equivalence class. Then also, Φ_i = Φ_i g⁻¹. Hence for any g,

∑_{ϕ ∈ Φ_i} α_ϕ ϕ^g = ∑_{ϕ ∈ Φ_i g⁻¹} α_ϕ ϕ^g = ∑_{ϕ ∈ Φ_i} α_{ϕ g} ϕ.

So

∑_g ∑_{ϕ ∈ Φ_i} α_ϕ ϕ^g = ∑_{ϕ ∈ Φ_i} α_{ϕ g⁻¹} ϕ = ∑_{ϕ ∈ Φ_i} (∑_g α_{ϕ g⁻¹}) ϕ.

Since as g runs over G, ϕ^g “covers” Φ_{E(ϕ)}, then ∑_{g ∈ G} α_{ϕ g⁻¹} has the same value for all equivalent ϕ’s, i.e., if ϕ ∈ Φ_i, ∑_{g ∈ G} α_{ϕ g⁻¹} depends only on i. Therefore we can denote ∑_{g ∈ G} α_{ϕ g⁻¹} by β_i, obtaining:

∑_{i=1}^k ∑_{ϕ ∈ Φ_i} β_i ϕ(X) > 0
or  ∑ β_{E(ϕ)} ϕ(X) > 0.

where E(ϕ) denotes “the equivalence class containing ϕ.”

A similar argument shows that if ∑ α_ϕ ϕ(X) < 0, then ∑ β_{E(ϕ)} ϕ(X) < 0. Thus ψ = ⌈∑ α_ϕ ϕ > 0⌉ = ⌈∑ β_{E(ϕ)} ϕ > 0⌉. We shall most often use this theorem in the following form:

COROLLARY 1. Any function ψ of order k has a linear representation

ψ = ⌈∑_Φ α_ϕ ϕ > 0⌉

where Φ is the set of masks of degree ≤ k and α_ϕ = α_{ϕ’} whenever S(ϕ) can be transformed into S(ϕ’) by an element of G.

PROOF. The corollary follows immediately from the theorem and the observation that, for masks, ϕ_A ≡_G ϕ_B if and only if A = B_g for some g ∈ G.

COROLLARY 2. Let Φ = Φ₁ ∪ ··· ∪ Φ_n be the decomposition of Φ into equivalence classes by the relation ≡_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)}|, i.e., N_i(X) is the number of ϕ’s of the i-th type, equivalent under the group, that “fit” the argument X.

PROOF. ψ can be represented as

ψ = ⌈∑_{ϕ ∈ Φ} α_ϕ ϕ > 0⌉
= ⌈∑_i ∑_{ϕ ∈ Φ_i} α_i ϕ > 0⌉
= ⌈∑_i α_i ∑_{ϕ ∈ Φ_i} ϕ > 0⌉ = ⌈∑_i α_i N_i(X) > 0⌉.

COROLLARY 3. (THE TRIVIALITY OF INVARIANT PREDICATES OF ORDER 1). Let G be any transitive group of permutations on R (transitive means: for every pair p, q ∈ R there is g ∈ G such that pg = q). Then the only first-order predicates invariant under G are of the forms:

ψ(X) = ⌈|X| > m⌉
or  ψ(X) = ⌈|X| < m⌉, for some m.

PROOF. Since the group is transitive all the one-point predicates ϕ_{{p}} are equivalent. Thus we can assume that

ψ(X) = ⌈∑_{p ∈ X} α ϕ_{{p}} > θ⌉  (or with some other inequality sign)

i.e., the coefficient α is independent of p. But ∑_{p ∈ X} α ϕ_{{p}} > θ can be transformed into ∑_{p ∈ X} ϕ_{{p}} > θ/α (for α > 0; for α ≤ 0 a similar argument proves the corresponding assertion). But ∑_{p ∈ X} ϕ_{{p}} = |X|. Thus order-1 invariant predicates can do nothing more than define a count on the cardinality or “area” of figures. In fact, an order-1 predicate is a measure, and the order-1 invariant predicate is the Haar measure.

III. Applications of the group-invariance theorem.

The Parity Function.

In this section we develop in some detail the analysis of the particular predicate ψ_PAR defined by

ψ_PAR(X) = ⌈|X| is odd⌉.

Our interest in PAR is threefold: it is interesting in itself; it will be used for the analysis of other more important functions; and, especially, it illustrates our mathematical methods and the kind of question they enable us to discuss.

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.

Now suppose that ψ_PAR = ⌈∑ α_i ϕ_i > 0⌉ where the ϕ_i are masks with |S(ϕ_i)| ≤ K and the α_i depend only on the equivalence classes defined by G. Since masks with the same support are identical,

ϕ_i ≡_G ϕ_j ⇔ |S(ϕ_i)| = |S(ϕ_j)|.

Thus

ψ_PAR = ⌈∑_{j=0}^K (α_j ∑_{ϕ ∈ Φ_j} ϕ) > 0⌉

where Φ_j is the set of masks whose supports contain exactly j elements.

We now calculate for an arbitrary subset X of R,

C_j(X) = ∑_{ϕ ∈ Φ_j} ϕ(X).

Since ϕ(X) is 1 if S(ϕ) ⊂ X and 0 otherwise, C_j(X) is the number of subsets of X with j elements, i.e.,

C_j(X) = (|X| choose j)

which is a polynomial of degree j in |X|.

It follows that

ψ_PAR = ∑_{j=0}^K α_j C_j(X)

is a polynomial of degree K in |X|, say P(|X|).

Now consider a sequence

∅ = X₀ ⊂ X₁ ⊂ ··· ⊂ X_{|R|} = R

of |R| + 1 nested subsets of R, and the sequence of values

P(|X₀|) ≤ 0, P(|X₁|) > 0, P(|X₂|) ≤ 0, …, P(|X_{|R|}|).

This implies that P(|X|) changes direction |R| times as |X| increases from 0 to |R|. But since P is a polynomial of degree K, it follows that K = |R|. Q.E.D.

From this we obtain the

THEOREM. If ψ_PAR ∈ L(Φ) and if Φ contains only masks, then Φ contains all the masks.

PROOF. Suppose, if possible, that ψ_PAR ∈ L(Φ), that Φ contains only masks, and the mask whose support is A does not belong to Φ.

Let ψ_PAR = ⌈∑_{ϕ ∈ Φ} α_ϕ ϕ > 0⌉. Define, for any X, ψ^A(X) = ψ(X ∩ A). Clearly ψ_PAR^A, the parity function for subsets of A, is of order |A| by the previous theorem.

Now consider ϕ^A for ϕ ∈ Φ. If S(ϕ) ⊂ A, clearly ϕ^A = ϕ. If S(ϕ) is not a subset of A, ϕ^A is identically zero since

S(ϕ) ⊄ A ⇒ S(ϕ) ⊄ X ∩ A ⇒ ϕ(X ∩ A) = 0 ⇒ ϕ^A(X) = 0.

It follows that either S(ϕ^A) is a proper subset of A or ϕ^A is identically zero. Let Φ^A be the set of masks in Φ whose supports are subsets of A. Then ψ_PAR^A = ⌈∑_{ϕ ∈ Φ^A} α_ϕ ϕ > 0⌉. But for all ϕ ∈ Φ^A, |S(ϕ)| < |A|. It would follow that the order of ψ_PAR^A is less than |A|, which is a contradiction. Thus the hypotheses are impossible and the theorem follows. Q.E.D.

COROLLARY 1. If ψ_PAR ∈ L(Φ), then Φ must contain at least one ϕ for which |S(ϕ)| = |R|.

The following theorem, also immediate from the above is of interest to students of threshold logic:

COROLLARY 2. Let Φ be the set of all ψ_PAR^A for proper subsets A of R. Then ψ_PAR ∉ L(Φ).

Coefficients of the Parity Function.

Suppose that we have a ⌈∑ α_i ϕ_i > 0⌉ that recognizes Parity(|X|) with masks. Let us suppose that the recognition is reliable, e.g., that ∑ α_i ϕ_i > 2 for odd parity, and ∑ α_i ϕ_i < 0 for even parity. If we apply the full permutation group, we obtain the same reliable discrimination with a set of “average coefficients” α_i, all equal for ϕ’s of the same order. Then we obtain the inequalities

α₁ > 2
α₂ + 2 α₁ < 0
α₃ + 3 α₂ + 3 α₁ > 2
···
or  ∑_{i=1}^n (n choose i) α_i > 2  if n is odd,
< 0  if n is even.

Subtracting successive inequalities, define

D_n = ∑_{i=1}^{n+1} (n+1 choose i) α_i – ∑_{i=1}^n (n choose i) α_i
= α_{n+1} + ∑_{i=1}^n [(n+1 choose i) – (n choose i)] α_i
= α_{n+1} + ∑_{i=1}^n (n choose i-1) α_i
= ∑_{i=0}^n (n choose i) α_{i+1}

so that for all n,

(-1)^n D_n > 2  or  [(-1)^n D_n – 2] > 0.

Using these inequalities, we will obtain a bound on the coefficients |α_i|. We will sum the inequalities with certain positive weights; choose any M > 0, and consider

∑_{i=0}^M (M choose i) [(-1)^i D_i – 2] > 0.

Then

∑_{i=0}^M (M choose i) (-1)^i D_i > 2 ∑_{i=0}^M (M choose i) = 2^{M+1}.

The left-hand side is

∑_{i=0}^M ∑_{k=0}^i (-1)^i α_{k+1} (i choose k)(M choose i) = ∑_{k=0}^M ∑_{i=k}^M (-1)^i α_{k+1} (i choose k)(M choose i)
= ∑_{k=0}^M ∑_{i=k}^M (-1)^i α_{k+1} (i! / (k!(i-k)!)) (M! / (i!(M-i)!))
= ∑_{k=0}^M ∑_{i=k}^M (-1)^i α_{k+1} (M! / (k!(M-k)!)) ((M-k)! / ((i-k)!(M-i)!))
= ∑_{k=0}^M α_{k+1} (M choose k) (-1)^k ∑_{j=0}^{M-k} ((M-k)! / (j!(M-k-j)!)) (-1)^j
= ∑_{k=0}^M α_{k+1} (M choose k) (-1)^k (1 – 1)^{M-k}
= α_{M+1} (-1)^M

we have the

THEOREM. For each M,

(-1)^M α_{M+1} > 2^{M+1}.

These values hold for the average, so if the coefficients of each type are not equal, some must be even larger! 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!

REMARK. This has a practically fatal effect on the corresponding learning machines. At least 2^{|R|} instances of just the maximal pattern is required to “learn” the largest coefficient; actually the situation is far worse because of the unfavorable interactions with lower order coefficients. It follows, moreover that 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—that is, the even subsets of R. For, any uniform representation of the α’s must allow |R| bits for each, and since there are 2^{|R|} coefficients the total number of bits required is |R| · 2^{|R|}. On the other hand there are 2^{|R|-1} even subsets of R, each representable by an |R|-bit sequence, so that |R| · 2^{|R|-1} bits would suffice to represent the subsets.

It should also be noted that ψ_PAR is not very exceptional in this regard because the positive normal form theorem tells us that all possible 2^{2^{|R|}} Boolean functions can be so encoded as linear threshold functions in the set of all masks. Then, on the average, specification of the coefficients of each requires 2^{|R|} bits.

Another predicate of great interest is associated with the geometric property of “connectedness:” Its application and interpretation is deferred to §VI; the basic theorem is proved now.

The “One-in-a-box” Theorem.

THEOREM. Let A₁, …, 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², the order of ψ is ≥ m.

COROLLARY. If R = A₁ ∪ A₂ ∪ ··· ∪ A_m the order of ψ is at least the order of (|R|/4)^{1/3}.

PROOF. For each i = 1, …, m let G_i be the group of permutations of R which permutes the elements of A_i but do not affect the elements of the complement of A_i. Let G be the group generated by all elements of the G_i. Clearly ψ is invariant with respect to G. Let Φ be the set of masks of degree K or less. To determine the equivalence class of any ϕ ∈ Φ consider the ordered set of occupancy numbers

{|S(ϕ) ∩ A_i|}.

Then ϕ₁ ≡_G ϕ₂ if, for each i, |S(ϕ₁) ∩ A_i| = |S(ϕ₂) ∩ A_i|. Let Φ₁, Φ₂, …, Φ_M be the equivalence classes.

Now consider an arbitrary set X and an equivalence class Φ_j. We wish to calculate the number N_j(X) of members of Φ_j satisfied by X, i.e.,

N_j(X) = |{ϕ | ϕ ∈ Φ_j ∧ S(ϕ) ⊂ X}|.

A simple combinatorial argument shows that

N_j(X) = (|X ∩ A₁| choose |S(ϕ) ∩ A₁|) · (|X ∩ A₂| choose |S(ϕ) ∩ A₂|) ··· (|X ∩ A_m| choose |S(ϕ) ∩ A_m|)
where  (y choose n) = y(y – 1) ··· (y – n + 1) / n!

and ϕ is an arbitrary member of Φ_j. Since the numbers |S(ϕ) ∩ A_i| depend only on the classes Φ_j and add up to not more than K, it follows that N_j(X) can be written as a polynomial of degree K or less in the numbers x_i = |X ∩ A_i|:

N_j(X) = P_j(x₁, …, x_m).

Now let ψ = ⌈∑ α_ϕ ϕ > 0⌉ be a representation of ψ as a linear threshold function in the set of masks of degree less than or equal to K. By the argument which we have already used several times we can assume that α_ϕ depends only on the equivalence class of ϕ and write

∑ α_ϕ ϕ(X) = ∑_{j=1}^M β_j ∑_{ϕ ∈ Φ_j} ϕ(X) = ∑_{j=1}^M β_j N_j(X) = ∑_{j=1}^M β_j P_j(x₁, …, x_m)

which, as a sum of polynomials of degree at most K, is itself such a polynomial. Thus we can conclude that there exists a polynomial of degree at most K, Q(x₁, …, x_m), with the property that

ψ(X) = ⌈Q(x₁, …, x_m) > 0  with  x_i = |X ∩ A_i|⌉
i.e., that for all i, 0 ≤ x_i ≤ 4m²,
Q(x₁, …, x_m) > 0 ⇔ (∀ i)(x_i > 0).

In Q(x₁, …, x_m) make the formal substitution,

x_i = (t – (2i – 1))².

Then Q(x₁, …, x_m) becomes a polynomial of degree at most 2K in t. Now let t take on the values t = 0, 1, …, 2m. By property (4) Q must be positive for even t and negative or zero for odd t. By counting the number of changes of sign it is clear that 2K ≥ 2m i.e., K ≥ m. This completes the proof.

IV. The and/or theorem.

We have already remarked that if R = A ∪ B ∪ C the predicate

ψ₁(X) = ⌈|X ∩ A| > |X ∩ C|⌉  is of order 1,

and stated without proof that

ψ(X) = ⌈|X ∩ A| > |X ∩ C| ∧ |X ∩ B| > |X ∩ C|⌉

is not of bounded order as |R| becomes large. We shall now prove this assertion. We can assume without any loss of generality that |A| = |B| = |C| and our formal statement is that if ψ_k(X) is the predicate of the stated form for |R| = 3k, then the order of ψ_k → ∞ as k → ∞. The proof is similar to that used for the parity theorem. We shall assume that the order of ψ_k(X) is bounded by N for all k and derive the contradiction by showing that the associated polynomials would have to satisfy inconsistent conditions. The first step is to set up the associated polynomials for a fixed k.

We do this by choosing the group which permutes within the sets A, B, C. The equivalence classes of masks are then characterized by three numbers, i.e., |A ∩ S(ϕ)|, |B ∩ S(ϕ)| and |C ∩ S(ϕ)|. The number N_ϕ(X) of masks in this equivalence class satisfied by a given set X is

N_ϕ(X) = (|A ∩ X| choose |A ∩ S(ϕ)|) × (|B ∩ X| choose |B ∩ S(ϕ)|) × (|C ∩ X| choose |C ∩ S(ϕ)|).

If |S(ϕ)| ≤ N this is clearly a polynomial of degree at most N in the three numbers

x = |A ∩ X|,  y = |B ∩ X|,  z = |C ∩ X|.

The group invariance theorem says that if

ψ_k = ⌈∑_{ϕ ∈ Φ} γ_ϕ ϕ > 0⌉

where Φ is the set of masks with |S(ϕ)| ≤ N then

ψ_k(X) = ⌈∑ α_i N_i(X) > 0⌉

where i runs over the set of equivalence classes of Φ. But ∑ α_i N_i(X) is a polynomial of degree at most N in x, y and z. Call it P_k(x, y, z).

Now, by definition, for possible values of x, y, z (i.e., nonnegative integers ≤ k), P_k(x, y, z) > 0 if and only if x > z and y > z. We shall show, through a series of lemmas, that this cannot be true for all k. The technical details of these lemmas are not essential for the subsequent sections.

LEMMA 1. Let P_k(x, y, z) be an infinite sequence of polynomials of fixed degree n, with the property that for all positive integers x, y, z less than k,

(A)    x > z  and  y > z ⇒ P_k(x, y, z) ≥ 0,
       x ≤ z  or   y ≤ z ⇒ P_k(x, y, z) ≤ 0.

Then there exists a nonzero polynomial P(x, y, z) of the same degree n with the property that the implications (A) hold for all positive integral values of x, y, z. This follows from the following compactness argument: Write

P_k(x, y, z) = ∑_{i=1}^r C_{k,i} m_i(x, y, z)

where m_i(x, y, z) is an enumeration of the monomials in variables x, y and z. We can assume ∑ C_{k,i}² = 1 since the hypotheses remain true if P_k is divided by ∑ C_{k,i}². Now the bounded sequence C_{1,1}, C_{2,1}, …, C_{k,1}, … must contain an infinite convergent subsequence S₁ of the integers for which {C_{k,1} | k ∈ S₁} converges to a limit, say C₁.

Now consider {C_{k,2} | k ∈ S₁}. There must be an infinite subsequence of S₁, say S₂, on which this converges to a limit, say C₂. Continuing in this way we find a subsequence S = S_r of the integers and a set of numbers C₁, …, C_r such that {C_{k,i} | k ∈ S} converges to C_i for all i ≤ r. But then, for k ∈ S, P_k(x, y, z) converges to the polynomial P(x, y, z) = ∑_{i=1}^r C_i m_i(x, y, z) for all x, y, z.

To see that P(x, y, z) has the required properties, choose any positive integers x₀, y₀, z₀. For values of k smaller than the largest of these numbers, nothing can be said about P_k(x₀, y₀, z₀). But for all sufficiently large k, P_k(x₀, y₀, z₀) must be nonnegative if x₀ > z₀ and y₀ > z₀ (and nonpositive if x₀ ≤ z₀ or y₀ ≤ z₀). It follows immediately that P(x₀, y₀, z₀) is nonnegative (nonpositive) under the same conditions. To see that P is nonzero note that ∑ C_i² = 1.

LEMMA 2. If a polynomial f(α, β) satisfies the following conditions for all integral values of α and β, then it is identically zero:

(B)    α > 0  and  β > 0 ⇒ f(α, β) ≥ 0
(C)    α ≤ 0  or   β ≤ 0 ⇒ f(α, β) ≤ 0.

PROOF. Suppose that a polynomial of degree N, f(α, β), satisfies the conditions (B) and (C) and is not identically zero. Without loss of generality we can suppose that

f(α, β) = α^N g(β) + r(α, β)

where g(β) is not identically zero and r(α, β) has degree less than N in α.

For any β for which g(β) ≠ 0, there is an α₀ > 0 such that

|α₀^N g(β)| > |r(α₀, β)|.

Thus f(α₀, β) has the same sign as α₀^N g(β), i.e., as g(β) since α₀^N is positive. It follows from (B) and (C) that

(D)    β > 0 ⇒ g(β) ≥ 0,
       β < 0 ⇒ g(β) ≤ 0.

(The conditions (D) hold for all β: if g(β) ≠ 0 by preceding argument; if g(β) = 0, tautologously.) We now derive a contradiction by considering separately two cases:

(a) N even. Since g(β) is not identically zero, there is some β₀ > 0 for which g(β₀) ≠ 0. By (D), g(β₀) > 0. Thus α^N g(β₀) > 0 so that for a sufficiently large negative α₀,

α₀^N g(β₀) + r(α₀, β₀) > 0

i.e., f(α₀, β₀) > 0. But we are free to choose a negative value of α, i.e., we can find α₀, β₀ such that α₀ < 0 and f(α₀, β₀) > 0, which contradicts (C).

(b) N odd. Choose β₀ < 0 for which g(β₀) ≠ 0; then g(β₀) < 0, by (D). Choose negative α₀ as before. Then α₀^N g(β₀) > 0 so f(α₀, β₀) > 0, again contradicting (C). Q.E.D.

LEMMA 3. No nonzero polynomial P(x, y, z) can satisfy the following conditions for all positive integral values of x, y, z:

x > z  and  y > z ⇒ P(x, y, z) ≥ 0
x ≤ z  or   y ≤ z ⇒ P(x, y, z) ≤ 0.

PROOF. Suppose that P(x, y, z) has these properties. Define Q(α, β, z) = P(z + α, z + β, z). Let M be the highest power of z in Q so that

Q(α, β, z) = z^M f(α, β) + R(α, β, z)

where R is of degree less than M in z.

Now choose any α₀ and β₀ for which f(α₀, β₀) ≠ 0. For sufficiently large z, say z₀:

(a) z₀ + α₀ > 0 and z₀ + β₀ > 0
(b) |z₀^M f(α₀, β₀)| > |R(α₀, β₀, z₀)|.

It follows that

f(α₀, β₀) ≥ 0 ⇔ Q(α₀, β₀, z₀) ≥ 0 ⇔ P(z₀ + α₀, z₀ + β₀, z₀) ≥ 0.

Thus

α₀ > 0  and  β₀ > 0 ⇒ z₀ + α₀ > z₀  and  z₀ + β₀ > z₀
⇒ P(z₀ + α₀, z₀ + β₀, z₀) ≥ 0 ⇒ f(α₀, β₀) ≥ 0

and similarly α₀ < 0 or β₀ < 0 ⇒ f(α₀, β₀) ≤ 0. But this is true for all α₀, β₀. Thus by the previous lemma, f(α, β) = 0. It follows that P(x, y, z) is of degree zero in z, which is only possible if it is identically zero. Q.E.D.

This concludes the proof of the AND-OR theorem. It is clear that the reason the theorem is true has to do with the algebraic geometry of the “occupancy” polynomials. If it were not for the constraints concerning integer values of the variables, the theorem would be an immediate consequence of Bezout’s theorem.

V. The “order-limited” perceptron.

The Order of Some Geometrical Predicates.

Now we consider the problem of computing the order of a number of interesting geometrical predicates. As a first step, we have to provide the underlying space R with the topological and metric properties necessary for defining geometrical figures; this was not necessary in the case of predicates like Parity and others related to counting, for these are not really geometric in character.

The simplest procedure that is rigorous enough yet not too mathematically fussy seems to be to divide the Euclidean plane, E², into squares as an infinite chess board. The set R is then taken as the set of squares. A figure X of E² is then identified with that set of elements of R—i.e., that collection of squares that contain at least one point of X. Thus to any subset X of E² corresponds the subset X̂ of R defined by

X̂ = {x ∈ R | x ∩ X ≠ ∅}.

Now, although X and X̂ are logically distinct no serious confusion can arise if we identify them, and we shall do so from now on. Thus we refer to certain subsets of R as “circles,” “triangles,” etc., meaning that they can be obtained from real circles and triangles by the map X → X̂. Of course, this means that near the “limits of resolution” one begins to obtain apparent errors of classification because of the finite “mesh” of R. Thus a small circle will not look very round.

When it is necessary to distinguish between X and X̂ we will say that two figures X, X’ of E² are in the same R-tolerance class if X̂ = X̂’. In this we follow the general mathematical approach proposed by E. C. Zeeman for treating this kind of problem. To avoid inessential questions of how the group-invariance theorem applies to infinite groups, assume below when necessary that R has the toroidal topology.

We begin by listing some geometric predicates of rather small order.

(a) k = 1. When we say “geometric property” we mean something that is at least invariant under translation, usually also invariant under rotation, and often invariant under dilatation. The first two invariances combine to define the “congruence” group of transformations and all three the “similarity” group. For k = 1, just the translation group suffices for the Group Invariance Theorem to tell us that all coefficients are equal, hence the only patterns that can be of order 1 are those defined by a single cut in the cardinality or area of the set:

ψ = ⌈|X| > A⌉  or  ψ = ⌈|X| < A⌉.

Note: If translation invariance is not required, then order-1 can compute other properties, i.e., concerning moments about particular points or axes. However these are not “geometric.”

(b) k = 2. For k = 2 things are more complicated. As shown in §I it is possible to make a double cut in the area of the set, hence we can do the counting trick, and recognize those figures whose areas are

ψ = ⌈A₁ < |X| < A₂⌉.

(In fact, in general we can always find a function of order k that recognizes the sets satisfied by any k inequalities concerning their cardinality.) Now consider only the group of translations and masks of order 2. Then two masks x₁ x₂ and x₁’ x₂’ are equivalent if and only if the difference vectors x₁ – x₂ and x₁’ – x₂’ are equal. Then, with respect to the translation group, a figure is completely characterized (up to k = 2) by its “difference-vector spectrum,” defined as the sequence of the numbers of pairs of points separated by each possible directed distance.

Pairs of figures that have the same difference-vector spectra are indistinguishable to any order-2 predicate that is translation invariant.

If we add the requirement of invariance under rotation, spectra classify together all differences of the same length, whatever their orientation.

An interesting pair of figures rotationally distinct, but still indistinguishable for k = 2, is a pair which have the same direction-independent distance-between-point-pair statistics. There is an interesting theoretical direction here, but we will not stop to look into it. Many interesting proposals for pattern recognition machines are related to the theory of these geometric spectra. The classic paper of Bledsoe and Browning [1] is related to this, as is the work on “integral geometry” of Novikoff [4].

Note that we did not allow reflections, yet reflectionally opposite figures are confused! One should be cautious about using “intuition” here. The theory of rotational invariance requires careful attention to the effect of the discrete retinal approximation, but can presumably be made consistent by application of Zeeman’s methods; for the dilatation “group,” there are serious difficulties.

(c) k = 3. As k increases, the class of realizable discriminations grows, and our detailed understanding wanes. It is interesting to discover that the predicate

ψ(X) = ⌈X is a single, solid, convex figure⌉

is of order ≤ 3 as noted in the Introduction, because

ψ_CONVEX(X) = ⌈∑_{a,b ∈ R} ⌈a ∈ X  and  b ∈ X  and  midpoint(a,b) ∉ X⌉ < 1⌉

is of order 3. Presumably this predicate cannot be realized with order 2.

It is not difficult to show that the set of solid rectangles (with axes parallel to the mesh of R) can be recognized by a predicate of order 3. This is true also for the set of hollow rectangles (with borders one square thick). It is much more difficult to show, but true, that the set of hollow squares has order three. Intuitively one might suppose that at least order 4 is required to insure equality of side lengths.

Another example of a predicate that can be realized with k = 3, for any n, is:

ψ(X) = ⌈the points of X are collinear, and broken into not more than n segments⌉.

(d) k = 4. Using the fact that any three points determine a circle, we can make a perceptron with masks of order k = 4 for the following predicate:

ψ(X) = ⌈X is the perimeter of a complete circle⌉.

PROOF. Define, for all concvclic quadruples of points in R a, b, c, d:

ϕ_{abcd}(X) = ⌈a ∈ X  and  b ∈ X  and  c ∈ X  and  d ∉ X⌉

and then realize ψ as

ψ = ⌈∑_{a,b,c,d} ϕ_{abcd} < 1⌉.

Many other curious and interesting predicates can be shown by similar arguments to have small orders. One should be careful not to conclude that this means that there are practical consequences of this, unless one is prepared to face the fact that:

(a) large numbers of ϕ’s are required, of the order of |R|^k for the examples given above.

(b) the threshold conditions are sharp, so that engineering considerations may cause difficulties in realizing the linear summation, especially if there is any problem of noise. Even with simple square root noise, for k = 4 or larger, the noise grows faster than the retinal size.

(c) a very slight change in the pattern-definition destroys the recognizability.

An alternative method is to integrate the curvature of line elements. This leads to interesting questions about the precision of global functions that can be approximated by summation of local elements with a given precision. Curvature requires order 4, in a sense. The predicate defined here admits a few uninteresting exceptions.

Furthermore, in most cases there will be more efficient machines, for the same amount of hardware, to realize these rather simply-defined patterns. Low-order recognition has often the character of a “trick,” and one cannot generalize freely. The AND-OR order theorem tells us that some simple relations between simple properties of figures can be prohibitively hard to recognize.

VI. Connectivity: A geometric property with unbounded order.

We define connectedness as follows:

Two points of R are adjacent if they are squares (in the map F → F̂) with a common edge. A figure is connected if, given any two points P₁, P₂ of the figure, we can find a path through adjacent squares from P₁ to P₂.

THEOREM. The predicate

ψ(X) = ⌈X is connected⌉

has arbitrarily large orders as |R| grows in size.

PROOF. Suppose that ψ(X) could have order < m. Consider an array of (2m + 1) × 4m² adjacent squares of R arranged in 2m + 1 rows of 4m² squares each. Let G₀ be the set of array points whose row indices are odd (rows B₁, B₃, …, B_{2m+1}), and let G₁ be the remaining squares of the array (rows B₂, B₄, …, B_{2m}). Let ℱ be the family of figures obtained from the figure G₀ by adding subsets of G₁. It is clear that if F ∈ ℱ it is of the form G₀ ∨ F₁, where F₁ ⊂ G₁. Now F will be connected if and only if its F₁ contains at least one square from each even row; that is, if the set F₁ satisfies the “one-in-a-box” condition (see end of §III). The theorem then follows from the One-in-a-Box Theorem.

To see the details of how the One-in-a-Box Theorem is applied, if it is not already clear, consider the figures of family ℱ as a subset of all possible figures on R. Clearly, if we had an order-k predicate that could recognize connectivity on R, we could have one that worked on ℱ; namely the same predicate with constant zero inputs to all variables not in the small array. And since all points of the odd rows have always value 1 for figures in ℱ, this in turn means that we could have an order-k predicate to decide the one-in-a-box property on set G₁; namely the same predicate further restricted to having constant one inputs to the points in G₀. Thus each Boolean function of the original predicate is replaced by the function obtained by fixing some of its variables to zero and one; this operation can never increase the order of a function. But since this last predicate cannot exist, neither can the first.

An Example. Consider the special case for k = 2, and the equivalent one-in-a-box problem for a G₁ space in which m = 3 and there are just 4 squares in each row. Now consider a ψ of degree 2; we will show that it cannot characterize the connectedness of pictures of this kind. Suppose that ψ = ⌈∑ α_i ϕ_i > θ⌉ and consider the equivalent form, symmetrized under the full group of permutations that interchange the rows and permute within rows. Then there are just three equivalence-classes of masks of degree ≤ 2, namely:

single points:   ϕ_i^1 = x_i
point-pairs:     ϕ_{ij}^{11} = x_i x_j  (x_i and x_j in same row),
point-pairs:     ϕ_{ij}^{12} = x_i x_j  (x_i and x_j in different rows);

Note that this is not the same group used in proving the general theorem.

hence any order-2 predicate must have the form

(1)    ψ = α₁ N^1(X) + α_{11} N^{11}(X) + α_{12} N^{12}(X) > θ

where N^1, N^{11}, and N^{12} are the numbers of point sets of the respective types in the figure X.

Now consider two figures X₁ and X₂ where in each case one counts:

N^1 = 6,  N^{11} = 6,  N^{12} = 9;

hence the form (1) has the same value for both figures. But X₁ is connected while X₂ is not! Note that here m = 3 so that we obtain a contradiction with |A_i| = 4, while the general proof required |A_i| = 4m² = 36. It is known also that if k = 6, we can get a similar result with |A_i| = 16.

The case of k = 2, m = 3, |A_i| = 3 is of order 2, since one can in fact express the connectivity predicate for that space as

ψ = ⌈N^{11}(X) + N^{12}(X) – 2 N^1(X) > 4⌉.

Cut-wise Connectivity.

It should be observed that the proof of the previous theorem applies not only to a property of connectivity in its classical sense but to the stronger predicate defined by:

A figure X is “cutwise disconnected” if there is a straight line L such that: X does not intersect L and does not lie entirely to one side of L.

The general connectivity definition would have “curve” for L instead of “straight line,” and one would expect that this would require a higher order for its realization.

Relations Between Perceptrons.

The study of the order of predicates is often facilitated by the reduction of a given predicate to another simpler one. Although we do not have a satisfactory theory of any class of reductions, or even a clear enough insight into the nature of the relations which might play a role analogous to “homomorphism,” “quotient” and so on in more developed areas of mathematics, the following examples are useful in particular applications and indicate an interesting area for future research.

(a) Let us say that a perceptron system, P, is defined by the basic set R and a set Φ of predicates on subsets of R. A second perceptron system, P’, is a subperceptron system of P if the basic set R’ is a subset of R and if its set of predicates is that obtained by relativising the members of Φ to R’, i.e., all predicates ϕ’ ∈ Φ’ satisfy

X ⊂ R’ ⇒ ϕ'(X) = ϕ(X)  for some ϕ ∈ Φ

and all predicates ϕ’ satisfying this condition are in Φ’. Clearly the order of any predicate of the form ψ’ for P’ is at most that of ψ for P.

(b) Isomorphism must be given the following natural sense: Let P be defined by R and Φ and P’ by R’ and Φ’. Then an isomorphism, f, is an isomorphic map f: R → R’ of the sets R with the property that for each ϕ ∈ Φ there is exactly one ϕ’ ∈ Φ’ satisfying ϕ(X) = ϕ'(f(X)) (where f(X) = {p ∈ R’ | ∃ q ∈ X: f(q) = p}).

(c) P’ is obtained from P by a collapsing operation f, if f is a map from points of R’ to disjoint sets of R, i.e.,

p ∈ R’ ⇒ f(p) ⊂ R
p ≠ q ⇒ f(p) ∩ f(q) = ∅.

A predicate ψ’ on R’ is obtained from a predicate ψ on R by the collapsing map f if ψ'(X’) = ψ(f(X’)), for X’ ⊂ R’.

THEOREM (COLLAPSING THEOREM). If f is a collapsing map from R to R’ and ψ’ is obtained from a predicate ψ by f, then the order of ψ’ is not greater than that of ψ.

PROOF. Let ψ = ⌈∑ α_ϕ ϕ > 0⌉ where Φ is the set of masks of degree less than k on R. Now for any X’ ⊂ R’,

(1)    ψ'(X’) = ψ(f(X’)) = ⌈∑_ϕ α_ϕ ϕ(f(X’)) > 0⌉.

We next observe that (1) remains true if Φ is replaced by the set of masks Φ̃ for which S(ϕ) ⊂ f(R’), for if S(ϕ) ⊄ f(R’), ϕ(f(X’)) = 0 for all X’ ⊂ R’.

Now for ϕ ∈ Φ̃ we have

S(ϕ) ⊂ ⋃ {f(p) | p ∈ R’},
in fact  S(ϕ) ⊂ ⋃ {f(p) | f(p) ∩ S(ϕ) ≠ ∅}.

Thus,

X’ ⊃ {p | f(p) ∩ S(ϕ) ≠ ∅} ⇒ f(X’) ⊃ ⋃ {f(p) | f(p) ∩ S(ϕ) ≠ ∅} ⊃ S(ϕ)

i.e., X’ ⊃ {p | f(p) ∩ S(ϕ) ≠ ∅} ⇒ f(X’) ⊃ S(ϕ) ⇒ ϕ(f(X’)). On the other hand, if ϕ(f(X’)), i.e., f(X’) ⊃ S(ϕ), it follows that

f(p) ∩ S(ϕ) ≠ ∅ ⇒ p ∈ X’

since f(p) ∩ f(q) = ∅ for p ≠ q. Thus ϕ(f(X’)) = ⌈X’ ⊃ {p | f(p) ∩ S(ϕ) ≠ ∅}⌉. In other words ϕ(f(X’)) is a mask on R’ with support {p | f(p) ∩ S(ϕ) ≠ ∅}. But since the sets of the form f(p) are disjoint, for different p, it follows that

|{p | f(p) ∩ S(ϕ) ≠ ∅}| ≤ |S(ϕ)| < k.

Going back to Equation (1) we see, then, that ψ’ is represented as a linear function of masks of degree less than k. Q.E.D.

Huffman’s Construction for ψ_CON.

We shall illustrate the application of the preceding concept by giving an alternative proof that ψ_CON has no finite order, based on a construction suggested to us by D. Huffman.

The intuitive idea is to construct a switching network which will be connected if an even number of its n switches are in the “on” position. Thus the connectedness problem is reduced to the parity problem.

The interpretation of the symbols x_i and x̄_i is as follows: when x_i is in the “on” position contact is made whenever x_i appears, and broken whenever x̄_i appears; when x_i is in the “off” position contact is made where x̄_i appears and broken where x_i appears. It is easy to see that the whole net is connected in the electrical and topological sense if the number of switches in the “on” position is 0 or 2. The generalization to n is obvious:

(a) List the terms in the classical normal form for ψ_PAR. Considered as a point function, which in the case n even can be written:

ψ_PAR(x₁, …, x_n) = x̄₁ x̄₂ ··· x̄_n ∨ x₁ x₂ x̄₃ x̄₄ ··· x̄_n ∨ ··· ∨ x₁ x₂ ··· x_n

(b) Translate this Boolean expression into a switching net by interpreting conjunction as series coupling and disjunction as parallel coupling.

(c) Construct a perceptron which “looks at” the position of the switches.

The reductive argument, in intuitive form, is as follows: the Huffman switching net can be regarded as defining a class of geometric figures which are connected or not depending on the parity of a certain set, the set of switches in “on” position. We thus see how a perceptron for ψ_CON on one set, R, can be used as a perceptron for ψ_PAR on a second set R’. As a perceptron for ψ_PAR, it must be of order at least |R’|. Thus the order of ψ_CON must be of order |R’|. We shall use the collapsing theorem to formalize this argument. But before doing so we note that a certain price has been paid for its intuitive simplicity: the set R is much bigger than the set R’; in fact |R| must be of the order of magnitude of 2^{|R’|}, so that the best result to be obtained from the construction is that the order of ψ_CON must increase with |R| like log |R|. This gives a weaker bound, log |R| compared with |R|^{1/3}, if we wish to estimate the order.

Connectivity on a Toroidal Space R.

Our earliest attempts to prove that ψ_CONNECTED has unbounded order led to the following curious result: The predicate defined on a 2n × 6 toroidally connected space R has order 2n. The proof is by construction: consider the space in which the edges e, e and f, f are identified. Consider the family of subsets ℱ of R that satisfy the conditions:

(i) All the shaded points belong to each X ∈ ℱ.

(ii) For each X ∈ ℱ and each i, either both points marked a^{(i)} or both points b^{(i)} are in, but no other combinations are allowed.

Then it can be seen, for each X ∈ ℱ that X is either one connected figure or X divides into two separate connected figures. Which case actually occurs depends only on the parity of |{i | a^{(i)} ∈ X}|. Then using the Collapsing Theorem and the order(ψ_PAR) = |R| theorem, we find that ψ_CON has order |R|/12.

The idea of this proof came from the attempt to reduce connectivity to parity directly by representing a switching diagram where if an even number of switches are in the “down” position then a is connected to a’ and b to b’. If the number of down switches is odd, a is connected to b’ and a’ to b. This diagram can be drawn in the plane by bringing the vertical connections around the end; then one finds that the predicate “a is connected to a'” has for order some constant multiple of |R|. If we put the toroidal topology on R, the order becomes constant times |R|; this is also true for a 3-dimensional nontoroidal R. Because of these results, we conclude that the order ~|R|^{1/3} obtained for ψ_CONNECTED is too low.

ADDED IN PROOF: We have since shown that the order is at least ~|R|^{1/2} in the plane.

Some Other Geometrical Predicates.

A number of other important geometric predicates that almost certainly have unbounded orders are:

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⌉.

¹ But, if a particular axis line is chosen in advance, then only order 2 is required!

Curiously enough, the predicate

⌈X has a single connected component⌉ ∨ ⌈X contains a hole⌉

has order 2. This can be shown by a construction using the Euler relation, Holes = 1 – (Edges – Vertices + Faces), even though each separately has unbounded order.

VII. Connectivity and serial computation.

It seems intuitively clear that the reason that the abstract quality of connectivity cannot be captured by a machine of finite order is that it has an inherently serial character; one cannot conclude that a figure is connected by any simple order-independent combination of simple tests. The same is true for the much simpler property of parity. In the case of parity, there is a stark contrast between our “worst possible” result for finite-order machines (§III) and the following “best possible” result for the serial computation of parity. Let x₁, x₂, …, x_n be any enumeration of the points of R and consider the following algorithm for determining the parity of X:

START:  set i to 0
EVEN:   add 1 to i
        If i = |R| then STOP; parity is EVEN
        If x_i = 0, go to EVEN; otherwise go to ODD
ODD:    add 1 to i
        If i = |R| then STOP; parity is ODD
        If x_i = 0, go to ODD; otherwise go to EVEN

where “go to α” means continue the algorithm at the instruction whose name is α.

Now this program is “minimal” in two respects: first in the number of computation-steps per point, but more significant, in the fact that the program requires no temporary storage-place for partial information accumulated during the computation, other than that required for the enumeration variable i. (In a sense, the process requires one binary-digit of current information, but this can be absorbed as above into the algorithm-structure.)

This suggests that it might be illuminating to ask for connectivity: how much storage is required by the best serial algorithm? The answer, as shown below, is that it requires no more than about 2 times that for storing the enumeration variable alone! To study this problem it seems that the Turing machine framework is the simplest and most natural, because of its simple uniform way of handling information storage.

A Serial Algorithm for Connectivity.

Connectivity of a geometric figure X is characterized by the fact that between any pair (p, q) of points of X there is a path that lies entirely in X. An equivalent definition, using the enumeration x₁, …, x_{|R|} of the points of R is: X is connected if and only if for each point x_i after the first point in X, there is a path to some x_j ∈ X for which i > j. (Proof: by recursion, then, each point of X is connected to the first point in X.) Using this definition of connectivity we can describe a beautiful algorithm to test whether X is connected. We will consider only figures that are “reasonably regular”—to be precise, we suppose that X is bounded by a number of oriented, simple, closed curves so that for each point x_i on a boundary there is defined a unique “next point” x_i* on that boundary. We choose x_i* to be the boundary point to the left of x_i when facing the complement of X. We will also assume that points x_i and x_{i+1} that are consecutive in the enumeration are adjacent in R. Finally, we will assume that X does not touch the edges of the space R.

START:   Set i to 0 and go to SEARCH
SEARCH:  Add 1 to i. If i = |R|, Stop and print “X is NULL.”
         If x_i ∈ X then go to SCAN, otherwise go to SEARCH.
SCAN:    Add 1 to i. If i = |R|, Stop and print “X is connected.”
         If x_i ∉ X or x_{i-1} ∈ X go to SCAN, otherwise
         Set j to i and go to TRACE.
TRACE:   Set j to j*
         If j = i, Stop and print “X is disconnected.”
         If j > i, go to TRACE.
         If j < i, go to SCAN.

Notice that at any point in the computation, it is necessary to keep track of the indexes of just the two points x_i and x_j.

Analysis. SEARCH simply finds the first point of X in the enumeration of R. Once such a point of X is found, SCAN searches through all of R, eventually testing every point of X. The current point, x_i, of SCAN is tested as follows: If x_i is not in X, then no test is necessary and SCAN goes on to x_{i+1}. If the previous point x_{i-1} was in X (and, by induction, is presumed to have passed the test) then x_i, if in X, is connected to x_{i-1} by adjacency. Finally, if x_i ∈ X and x_{i-1} ∉ X, then x_i is on a boundary curve B. TRACE circumnavigates this boundary curve. Now if B is a boundary curve it is either (i) an exterior boundary of a previously encountered component of X, in which case some point of B must have been encountered before; or (ii) B is an interior boundary curve, in which case a point of B must have been encountered before reaching x_{i-1} which is inside B; or (iii) B is the exterior boundary curve of a never-before-encountered component of X, the only case in which TRACE will return to x_i without meeting an x_j for which j < i. Thus SCAN will run up to i = |R| if and only if X has a single nonempty connected component.

Note that we can count the number of components of X by introducing K, initially zero, and adding 1 to K each time TRACE reaches the i = j exit. Note also that the algorithm is quite efficient; the only points examined more than once are some of the boundary points, and none of them is examined more than three times.

The Turing Machine Version of the Connectivity Algorithm.

It is convenient to assume that R is a 2^n × 2^n square array. Let x₁, …, x_{|R|} be an enumeration of the points of R in the order:

1          2^n + 1          …   (2^n – 1)2^n + 1
2          2^n + 2          …   (2^n – 1)2^n + 2
…        …              …   …
2^n        2 · 2^n          …   2^n · 2^n

This choice of dimension and enumeration makes available a simple way to represent the situation to a Turing machine. The Turing machine must be able to specify a point x_i of R, find whether x_i ∈ X, and in case x_i is a boundary point of X, find the index of the “left neighbor” of x_i*. The Turing Machine tape will have the form:

I_x  |  I_y  |  J_x  |  J_y  |  K

where each section represents an interval of n squares. Then the intervals to the right of I_x and I_y can hold the x and y coordinates of a point of R.

We will suppose that the Turing machine is coupled with the outside world, i.e., the figure X, through an “oracle” that works as follows: certain internal states of the machine have the property that when entered, the resulting next state depends on whether the coordinates in the I (or J) intervals designate a point in X. It can be verified, though the details are tedious, that all the operations described in the algorithm can be performed by a fixed Turing machine that uses no tape squares other than those in these intervals. For example, “i = |R|” if and only if there are all ones following I_x and I_y. “Add 1 to i” is equivalent to: “start at I_y and move left, changing 1’s to 0’s until a 0 is encountered and changed to 1 or until I_x is met.” The only nontrivial operation is computing j* given j. But this requires only examining the neighbors of x_j, and that is done by adding ±1 to the J_x and J_y coordinates, and consulting the oracle.

Since the Turing machine can keep track of which interval it is in, we really need only one symbol for punctuation, so the Turing machine can be a 3-symbol machine. By using a block encoding, one can use a 2-symbol machine, and, omitting details, we obtain the result:

THEOREM. For any ϵ 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₂ |R| squares of tape.

For convexity there is a similar procedure that makes three tests:

i. X is not disconnected by any vertical line that does not intersect X.
ii. The intersection of X with any vertical line is a connected segment.
iii. The outer boundary of X does not change the sign of its curvature.

A detailed construction shows that each test requires only one index point, so that

THEOREM. For any ϵ 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₂ |R| squares of tape.

This last result is certainly minimal since log₂ |R| squares are needed just to indicate a point of R, and all points must be examined. We are quite sure that the connectivity algorithm is minimal, also, in its use of tape, but we have no proof. In fact, we do not know any method, in general, to show that an algorithm is minimal in storage, except when information-theoretic arguments can be used. Incidentally, it is not hard to show that |X| is prime requires no more than (2 + ϵ) log₂ |R| squares (and presumably needs more than (2 – ϵ) log₂ |R|).

We do not definitely know any geometric predicates that require higher orders of storage, but we suspect that in an appropriate sense, the topological equivalence of two figures (e.g., two components of X) requires something more like |R| than like log |R| squares. There are, of course, recursive function-theoretic predicates that require arbitrarily high, indeed noncomputable, orders of storage, but none of these is known to have straightforward geometric interpretations.

VIII. Multi-layer perceptrons.

We have found a number of limitations of perceptrons, as defined above, and we have suggested that these may point toward as yet unknown theorems about parallel machines in general. On the other hand one suspects that some, at least, of the results above are not so general, and might not survive minor relaxations of the definitions.

One direction of generalization that seems important is that of relaxing the constraint that the ϕ’s be simply weighted and added. We have not found any particularly enlightening generalization on the lowest level—e.g., of replacing addition by an arbitrary commutative operation. An easier direction is to consider compositions of perceptrons. The remainder of this section explores some kinds of composite perceptrons. Unfortunately we do not understand them very well, so this section is more concerned with problem-posing than with problem-solving.

Gamba Machines.

Consider functions of the form

⌈∑_j β_j ⌈∑_i α_{ij} x_i > θ_j⌉ > θ⌉.

This form was proposed and realized in a series of machines built by A. Gamba [2]. It is essentially an order-1 composition of order-1 perceptrons, and is of interest to us for a number of reasons:

(i) The parity problem is solved neatly by

⌈∑_{j=0}^{|R|} (-1)^j ⌈∑_{all i} x_i > j⌉ > 0⌉.

Thus only |R| functions are needed, each itself of order 1 in the {x_i}. In fact, any predicate f(|X|) that depends only on the area |X| can be realized as

f(|X|) = f(0) + ∑_{j=0}^{|R|} ⌈∑ x_i > j⌉ · (f(j + 1) – f(j)).

The problem that led to our formulation of the AND-OR theorem also is solved neatly:

⌈⌈∑_{x ∈ A} x – ∑_{x ∈ C} x > 0⌉ + ⌈∑_{x ∈ B} x – ∑_{x ∈ C} x > 0⌉ ≥ 2⌉

is 1 if and only if |X ∩ A| > |X ∩ C| and |X ∩ B| > |X ∩ C|. This might suggest that this class of machines might transcend the other kinds of limitations we have found for machines of finite-order.

We are quite certain that this impression is misleading: that the deeper geometric properties are still outside the reach of this kind of “2-layer” perceptron. The inclusion of AND and OR is due to the 2-layer construction; any Boolean function is obtainable, in such a manner, through its normal form, but for most functions there will still be too many terms for practical interest. ⌈|X ∩ A| > |X ∩ C|⌉ type of predicates are within reach because they are simple area functions and hence fit precisely the inner ∑ α_{ij} first-order predicate forms. In fact, any class ℱ of figures can be recognized by a Gamba-machine because

⌈∑_{X ∈ ℱ} ⌈∑_{x ∈ X} x_i ≥ |X|⌉ > 0⌉

realizes it. But, this general form requires a special “Gamba-mask” for each X ⊂ ℱ. Although the above examples show that in special cases more economical representations are possible, this is not true in general (as one can see by considering the number 2^{2^{|R|}} of possible functions); in particular we conjecture, for example, that for the Connectivity Predicate, the machine would require a number of masks of an order approaching the number of simple-closed-curves in R. Even for convexity, we doubt that that predicate can be realized with significantly fewer than the number of ϕ’s needed for the order-3 1-layer machine.

(ii) In spite of its apparent simplicity, analysis of the geometric predicate problem for Gamba machines appears to require methods quite different from those we have used. First, because of the arbitrary order 1 predicate permitted in the inner sum, the notion of order does not seem to apply, and theorems must concern restrictions on the numbers of terms. Second, we have not found a way to carry the group-averaging methods into the inner α_{ij} coefficients, so that we cannot use the techniques that come from the group-invariance theorem. It is difficult to see how to analyse other multi-layer and composite perceptrons until this simple case is better understood. How much weaker are the machines with α_{ij} > 0 or those with all θ_j = 0? We have no characterization of what they can do.

(iii) The Gamba machine is of considerable practical interest because of the possibility of realizing the inner, and even the outer, sums by inexpensive, highly parallel optical methods. Using coherent light and properly prepared photographic transparencies, one can realize each inner sum (even with complex coefficients!) with a picture p_j whose density at point x_i is α_{ij}. By shrewd optics, one can even do this (with fixed p_j) for all translations of the source pattern X. Because of these technological possibilities it is important to have a better theory; we expect that the result will be favorable to problems like recognition of printed characters, but still very poor for the more abstract properties like detection of connectivity, symmetry, topological equivalence, and the like.

Note that the Gamba-machine can have order as large as |R| in the {x_i}. If the inner predicate threshold were removed then, because ∑_j β_j ∑_i α_{ij} x_i = ∑_i (∑_j β_j α_{ij}) x_i, one would have merely an order-1 function in the x_i.

IX. The diameter-limited perceptron.

In this section we discuss the power and limitations of the “diameter-limited” perceptrons: those in which each ϕ can see only a circumscribed portion of the retina R.

We consider a machine that sums the weighted evidence about a picture obtained by experiments ϕ, each of which report on the state of affairs within a circumscribed region, of diameter less than or equal to some length D. That is, Diameter(S(ϕ)) ≤ D. We will suppose that D is uniform over the ϕ’s of the machine (each actual region that affects a ϕ can be smaller, but not larger). We suppose also that in a practical sense D is small compared with the full dimensions of the space R. That is, D should be small enough that none of the ϕ’s can see the whole of an interesting figure (or else we would not have an effective limited diameter situation, and there would be no interesting theory) but D should be large enough that a ϕ has a chance to detect an interesting “local feature” of the figure.

We will consider first some things that a diameter-limited perceptron can recognize, and then some of the things it cannot.

(a) Blank picture, or black picture. A diameter-limited perceptron can tell when a picture is entirely black, or entirely white: suppose that the set of ϕ’s is chosen to cover the retina in regions, that may overlap, and that we define ϕ_i to be zero when all the points it can see are white, otherwise its value is 1. Then ∑ ϕ_i > 0 if the picture has one or more black points, and not if the picture is blank. Similarly, we could define the ϕ’s to be 1 when they see any white point, 0 otherwise, thus distinguishing the all-black picture from all others.

For later examples, it is important here to notice why these patterns can be recognized: it is not that any ϕ-unit can really say that there is strong evidence that the figure is all-white (although it has a slight correlation with this); but any ϕ can definitely say that it has conclusive evidence that the picture is not all white. Some interesting patterns have this character; that one can reject all pictures not in the class because each must have, somewhere or other, a local feature that is definitive and can be detected by what happens within a region of diameter D.

(b) Area cuts. We can distinguish, for any number S, the class of figures whose area is greater than S. To do this we define a ϕ_i for each point to be 1 if that point is black, 0 otherwise. Then ∑ x_i > S is a recognizer for the class in question. (One can do slightly better; if the ϕ’s look at regions of area A, then one can recognize this pattern by using only of the order of (|R| log A)/A units.)

(c) Nonintersecting lines. One can say that a pattern is composed of nonintersecting lines if, in each small region, the pattern is composed of separate line-segments, or blank. Then, if we make each ϕ have value zero when this condition is met, unity when it is not, then ∑ ϕ_i = 0 will accept all figures in the class and ∑ ϕ_i > 0 will reject all figures not in the class.

(d) Triangles. We can make a diameter-limited perceptron recognize the figures consisting of exactly one triangle (either solid or outline) by the following trick: We use two kinds of ϕ’s: the first has weight +1 if its field contains a vertex (two line segments meeting at an angle), otherwise its value is zero. The second kind, ϕ*, has value zero if its field is blank, or contains a line segment, solid black area, or a vertex, but has value +1 if the field contains anything else, including the end of a line segment. Provide enough of these ϕ’s so that the entire retina is covered, in nonoverlapping fashion, by both types. Finally assign weight 1 to the first type and a very large positive weight W to those of the second type. Then

∑ ϕ_i – W ∑ ϕ_i* < 4

will be a specific recognizer for triangles. (But also the null-picture is accepted.) Similarly, by requiring that the first kind of unit recognize right-angle vertices, the machine can be made to recognize the class of rectangles (setting the threshold to be < 5).

Note that this does not generalize to a very wide class of geometric recognition abilities. The triangle and rectangle cases are rather peculiar; the triangle because it is the simplest figure that has true vertices. The rectangle can be recognized because it has four equal angles; the system cannot be specialized to recognize, for example, exactly the squares. It is interesting, in view of the limitations we will establish shortly, to see why these patterns can be recognized by the diameter-limited machine; a rectangle is the only figure that has four or fewer right angles and no free line ends, etc.

(e) Absolute template-matching. Suppose that one wants the machine to recognize exactly a certain figure X₀ and no other. Then the diameter-limited machine can be made to do this by partitioning the retina into regions, and in each region a ϕ-function has a value 0 if that part of the retina is exactly matched to the corresponding part of X₀, otherwise the value is 1. Then

∑ ϕ_i < 1

if and only if the picture is exactly X₀.

Note, however, that this scheme works just on a particular object in a particular position. It cannot be generalized to recognize a particular object in any position (or even, in general, in two positions). In fact we show in the next section that even the simplest possible figure, namely one that consists of just one point, cannot be recognized independently of position!

(f) Convexity. The remarks in §V, Example c, footnote apply to the diameter limited case.

Limitations of Diameter-limited Perceptron.

Now we consider some of the basic limitations of the diameter-limited perceptron, by exhibiting and analysing some patterns they cannot recognize.

(g) The figure containing one single black point. This is the fundamental counter-example. We want a machine

∑ α_i ϕ_i > θ

to accept figures with area 1, but reject figures with area 0 or area greater than 1. Clearly this can be defined by two area cuts (i.e., area > 0 AND area < 2), but it cannot be realized by a linear threshold function with the area-restriction.

To see that this cannot be done, suppose that {α_i} and θ have been selected. Present first the blank picture, X₀. Then, defining f(X) = ∑ α_i ϕ_i(X) we have f(X₀) ≤ θ. Now present a figure, X₁, containing only one point, x₁. We must then have

f(X₁) > θ.

The change in the sum must be due to a change in the values of some of the ϕ’s. In fact, it must be due to changes only in ϕ’s for which x₁ ∈ S(ϕ), since nothing else in the picture has changed. In any case,

(1)    f(X₁) – f(X₀) > 0.

Now choose another point x₂ which is farther than D away from x₁. Then no S(ϕ) can contain both x₁ and x₂. For the figure X₂ containing only x₂ we must also have

(2)    f(X₂) = ∑ α_i ϕ_i ≥ θ.

Now consider the figure X₁₂ containing both x₁ and x₂. The addition, to X₂, of the point x₁ can affect only ϕ’s for which x₁ ∈ S(ϕ), and these are changed exactly as they are changed when the all-blank picture X₀ is changed to the picture X₁. Therefore

f(X₁₂) = f(X₂) + [f(X₁) – f(X₀)]

and by (1) and (2),

f(X₁₂) > θ.

but we require that

f(X₁₂) ≤ θ.

REMARK. Of course, this is the same phenomenon noted in the introduction to §II.

(h) Area segments. The diameter-limited perceptron cannot recognize the class of figures whose areas A lie between two bounds A₁ ≤ A ≤ A₂.

PROOF. This follows from the method of (g) above, which is a special case of this, with A₁ = 1 and A₂ = 1. But using the method of §I, Example (vii), this recognition is possible with order 2 if the diameter-limitation is relaxed.

(i) Connectedness. The diameter-limited perceptron cannot decide when the picture is a single, connected whole, as distinguished from two or more disconnected pieces.

PROOF. Consider the four pictures X₀₀, X₀₁, X₁₀, X₁₁ and suppose that the diameter D is small enough that no ϕ can bridge the separated components. Now figures X₀₁ and X₁₀ are connected, but X₀₀ and X₁₁ are disconnected. Suppose that there were a set of ϕ’s and α’s and θ such that

∑ α_i ϕ_i(X₀₀) < θ
∑ α_i ϕ_i(X₀₁) ≥ θ
∑ α_i ϕ_i(X₁₀) ≥ θ
∑ α_i ϕ_i(X₁₁) < θ

so that these four figures were correctly separated. But then, just as in the previous argument we would have for all ϕ_i:

ϕ_i(X₁₁) = ϕ_i(X₁₀) + ϕ_i(X₀₁) – ϕ_i(X₀₀)

because the two changing regions are more than D apart, hence

∑ α_i ϕ_i(X₁₁) ≥ θ + θ – θ = θ

contradicting the separation requirement.

Acknowledgement

We would like to thank many students and associates, particularly William Henneman, Dona Strauss and John White, for their contributions to this work.

BIBLIOGRAPHY

1. W. W. Bledsoe and I. Browning, Pattern recognition and reading by machine, Proc. Eastern Joint Computer Conference, 1959; reprint, Pattern recognition, Uhr, 1966.

2. A. Gamba, Optimum performance of learning machines, Proc. I.R.E. 49 (1961), 349; Further experiments with PAPA, Nuovo Cimento Suppl. Ser. X 20 (1961), 112-116.

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; reprinted in Embodiments of mind, M.I.T. Press, Cambridge, Mass., 1965.

6. F. Rosenblatt, Principles of neurodynamics, Spartan, Washington, D.C., 1962.

7. E. C. Zeeman, “Topology of the brain” in Topology of 3-manifolds, M. K. Fort, ed., Prentice-Hall, Englewood Cliffs, N. J., 1961.

8. M. Minsky and O. G. Selfridge, Learning in random nets, Proc. London Information Theory Sympos., Butterworth, London, 1961.

MASSACHUSETTS INSTITUTE OF TECHNOLOGY
CAMBRIDGE, MASSACHUSETTS