From: sontag@control.rutgers.edu (Eduardo Sontag)
Newsgroups: comp.ai.neural-nets
Subject: Rosenblatt's book revisited
Date: 12 Oct 92 17:02:48 GMT
Organization: Rutgers Univ., New Brunswick, N.J.


Puzzled by statements often made about Rosenblatt's original work, including
those often seen in papers or grant proposals, which roughly state something
like "he didn't realize that some functions such as XOR can't be computed...
[until Minsky and Papert came along]...", I decided to take a quick look at
the source, the book "Principles of Neurodynamics" (1962).  The purpose of this
note is to try to clear some apparently popular missconceptions.

I found the book very difficult to read, as most mathematical statements are
sloppy, but I did take a quick look.  Some observations follow, which not
everyone may be familiar with.  (I apologize to all those who are well-aware
of these facts, but for them I have a question --see below.)

(1) The basic topic of the book are **not** what we call today (single layer)
perceptrons.  He was primarily interested in general feedforward
("series/parallel") as well as recurrent ("back coupled") nets, and many
architectures in between.

(2) Theorem 1 in page 100 states that every Boolean function can be
implemented by a 1 hidden layer net (of threshold devices; there are
differentiable activations later, but I couldn't understand what is being
proved for those).  The proof is the obvious one (DNF).  But he goes on to say
(page 101) that it is evident that if there are no hidden units, not every
function can be implemented (so much for his lack of knowledge of XOR...).
Moreover, there is plenty of discussion of capacity issues; see for instance
p.109, or pages 401-402.  I didn't check exactly what these results mean and
how the compare with Cover's and others.  But they surely seem to have the
right flavor.

(3) He also discusses the fact that every finite automaton can be simulated by
(recurrent) NN's, if delay lines are included (p.303), a fact that was of
course well-known at the time (see the _title_ of Kleene's foundational paper
on automata and regular languages!).

(3) The Perceptron Convergence Theorem is *not* all that this book is about.
Far from the case, he mentions it --including a footnote in p.111 downplaying a
proof by Papert which he claims is erroneous-- but in the context of 1-HL nets
in which one has frozen the input-to-hidden weights,

(4) Chapter 13 deals with modifiable input-to-hidden weights. He starts with
an argument showing that local techniques may get stuck in saddle points due
to symmetry (my wording, not his) and hence randomization in the initial
conditions and in the algorithm are needed for symmetry breaking.  In section
13.3, entitled "Backpropagation error correction procedure", he describes a
stochastic algorithm which, I would bet, could be interpreted as some sort of
simulated annealing version of standard gradient descent.
I am not clear about his notations, so my QUESTION to the experts is: has
anyone read all this carefully and decided what is going on there?  (There are
no "sigmoidals", but the update rule looks quite familiar..).  There are plenty
of experiments with his "BP" procedure.  For those that didn't read the book,
typically there are of the order of 10-20 inputs and 20-50 hidden units, it
would seem.  Number of training samples is about 400-500, it would seem from
graphs.

(5) There is considerable discussion about the merits of MORE than one hidden
layer.  He repeatedly makes the point that even though 1HL nets are "enough"
(in the Boolean case; he doesn't have the approximation theorems), 2 HL and
even deeper nets are far better are "generalization" as opposed to
"memorization".

Again, let me repeat that I looked at this VERY VERY quickly, and the above
comments may reflect missunderstandings.  I would be extremely interested in
receiving comments and in knowing if anyone has cleaned-up the material so that
it can be read efficiently.  (The beautiful work of Minsky and Papert pursued
a rather different direction, looking at issues of scalability vis a vis local
decisions.  The questions raised above are about other aspects of the work.)

Looking forward to comments (to this newsgroup),
-eduardo
-- 
Eduardo D. Sontag
Department of Mathematics
Rutgers Center for Systems and Control (SYCON)
Rutgers University
New Brunswick, NJ 08903, USA

(Phone: (908)932-3072; dept.: (908)932-2390, FAX: (908)932-5530)
sontag@hilbert.rutgers.edu
Newsgroups: comp.ai.neural-nets