# Did Minsky and Papert know that multi-layer perceptrons could solve XOR?

In their famous book entitled Perceptrons: An Introduction to Computational Geometry, Minsky and Papert show that a perceptron can't solve the XOR problem. This contributed to the first AI winter, resulting in funding cuts for neural networks. However, now we know that a multilayer perceptron can solve the XOR problem easily.

Backprop wasn't known at the time, but did they know about manually building multilayer perceptrons? Did Minsky & Papert know that multilayer perceptrons could solve XOR at the time they wrote the book, albeit not knowing how to train it?

There does not appear to be a historical consensus on this.

The Wikipedia page on the Perceptrons book (which does not come down on either side) gives an argument that the ability of MLPs to compute any Boolean function was widely known at the time (at the very least to McCulloch and Pitts).

However, this page gives an account by someone present at the MIT AI lab in 1974, claiming that this was not common knowledge there, alluding to documentation in "Artificial Intelligence Progress Report: Research at the Laboratory in Vision, Language, and other problems of Intelligence" (p31-32) which is claimed to support this.

In section 13.2 Other Multilayer Machines (pp. 231-232) of the book Perceptrons: An Introduction to Computational Geometry (expanded edition, third printing, 1988) Minsky and Papert actually talk about their knowledge of or opinions about the capabilities of what they call the multilayered machines (i.e. perceptrons with many layers or MLPs).

Have you considered "perceptrons" with many layers?

Well, we have considered Gamba machines, which could be described as "two layers of perceptron". We have not found (by thinking or by studying the literature) any other really interesting class of multilayered machine, at least none whose principles seem to have a signiﬁcant relation to those of the perceptron. To see the force of this qualiﬁcation it is worth pondering the fact, trivial in itself, that a universal computer could be built entirely out of linear threshold modules. This does not in any sense reduce the theory of computation and programming to the theory of perceptrons. Some philosophers might like to express the relevant general principle by saying that the computer is so much more than the sum of its parts that the computer scientist can aﬁord to ignore the nature of the components and consider only their connectivity. More concretely, we would call the student's attention to the following considerations:

1. Multilayer machines with loops clearly open all the questions of the general theory of automata.

2. A system with no loops but with an order restriction at each layer can compute only predicates of ﬁnite order.

3. On the other hand, if there is no restriction except for the absence of loops, the monster of vacuous generality once more raises its head.

The problem of extension is not merely technical. It is also strategic. The perceptron has shown itself worthy of study despite (and even because of!) its severe limitations, It has many features to attract attention: its linearity; its intriguing learning theorem; its clear paradigmatic simplicity as a kind of parallel computation. There is no reason to suppose that any of these virtues carry over to the many-layered version. Nevertheless, we consider it to be an important research problem to elucidate (or reject) our intuitive judgment that the extension is sterile. Perhaps some powerful convergence theorem will be discovered, or some profound reason for the failure to produce an interesting "learning theorem" for the multilayered machine will be found.

Backprop wasn't known at the time, but did they know about manually building multilayer perceptrons?

Yes. They say that Gamba machines could be described as a 2-layer perceptron. For reproducibility, here's the definition of the Gamba machine (section 13.1 Gamba Perceptrons and other Multilayer Linear Machines)

\begin{align} \psi &= \left[\sum_{i} \alpha_{i}\left[\sum_{j} \beta_{i j} x_{j}>\theta_{i}\right]>\theta\right] \\ &= \left[\sum_{i} \alpha_{i} \varphi_{i} >\theta \right] \end{align} See also sections 12.4.4. Layer-Machines.

Did Minsky & Papert know that multilayer perceptrons could solve XOR at the time they wrote the book, albeit not knowing how to train it?

So, according to the first excerpt, their intuition was the virtues of perceptrons would not carry over to MLPs, but they acknowledge that more research was needed to reject or support this hypothesis.

However, in section 13.0 Introduction of the same book, they write

We believe (but cannot prove) that the deeper limitations extend also to the variant of the perceptron proposed by A. Gamba.

So, they believed that the Gamba machine would not have been able to solve the XOR problem.

However, in the first excerpt, they say that a Turing machine could be built entirely out of linear threshold modules, which seems to be inconsistent with the second excerpt, but that's not really the case because they are not saying how to build a Turing machine out of the linear threshold modules but that just the specific Gamba machine would have the same limitations of the perceptron.

Whether Minsky knew or not, it was definitely known to Rosenblatt, as he published those results in his really pioneering report - Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms, published in 1961.

A large majority of academic and industry experts are simply unaware of the "depth" of Rosenblatt's publication on perceptrons, where he not only proved that 3-layer perceptrons (which he called elementary) are universal (check theorem 1 in section 5.2), but where he also provided results on convergence (check theorem 4 in section 5.5) and a statistical mechanics analysis of their generalization capabilities (check chapter 6 for the foundational theory, and figure 13 and 14 for an application of it, following the analysis in section 7.1.2).

It is simply unfortunate that Rosenblatt accidentally died soon after Minsky and Papert's not-so-pioneering 1969 book was published. I believe its misleading influence has regressed AI research for several decades.

If only Rosenblatt lived longer and made his presence stronger in academia, we would not be handing out Turing awards in AI to those who on critical scrutiny are objectively undeserving of it.

• Hello. Welcome to AI SE. It may be a good idea to provide the name of the 1962 book by Rosenblatt that you're talking about. It would be very nice if you also specify the sections where he proves "that 3-layer perceptrons (which he called elementary) are universal, but where he also provided results on convergence and a statistical mechanics analysis of their generalization capabilities", as you claim.
– nbro
Oct 7 '21 at 14:59
• Thank you, I have edited my post with extra information. I wrongly referred to it as the 1962 book, but it is actually a report published on March 15, 1961. I do not know in which year this was unclassified.
– Cel
Oct 10 '21 at 22:33
• Thanks for your last edit. It may also be a good idea to remove your last paragraph, as it is controversial and not very related to the specific question on the original post. Please, make also sure that the links to the specific section of the report that I added are correct.
– nbro
Oct 11 '21 at 8:27