Mistake in DARPA NN Report

[alexis%yummy@gateway.mitre.org]

I just read the executive summary of the "DARPA Neural Network Study"
by MIT/Lincoln Labs which is really quite good (I would have prefered
less emphasis on computing power and more on say learning but ...).

Unfortunately they repeat a mistake in the intro about ability of feed-
forward networks.  In Figure 4-4 and the supporting text on p. 15 they
state that a net with 2 in and 1 out can partition the 2D input space
as such:

     One-Layer           ----- Two-Layer -----          Three-Layer
   ############     #######:::::::  ####::::::::::     ::::::::::::::
   ::##### A ##     ## A ##:: B ::  ######::: B ::     : B :###::::::
   ::::########     #######:::::::  ## A ###::::::     ::::######::::
   ::::::######     :::::::#######  ########::::::     :::### A ###::
   : B ::::####     :: B ::## A ##  #######:::::::     :::::######:::
   ::::::::::##     :::::::#######  ######::::::::     ::::::::::::::

Certainly a one-layer (i.e., Perceptron) can linearly partition, and
a three-layer (with enough nodes) can do anything, but otherwise the
figure is all wrong.  The "island" shown for a three-    ::::::::::::::
layer can easily be done by a two layer.  In our paper   :::########:::
"Geometric Analysis of Neural Network Capabilities"      :::##::::##:::
(ICNN87, VIII p385) we bother to take this to the        :::##:::::::::
extreme by doing something like the "C" (for convex)     :::##::::##:::
at left.  Actually any finite number of finitely         :::########:::
complex items can be done with a two-layer net.          ::::::::::::::

Far worse, the "four-quadrant" problem shown under       ######::::::
two-layers *CANNOT* be done with two layers.  There      ####::::::::
are few problems that can't be done with two layers,     ##::::::::::
but the easiest I know of is precisely that.  Assuming   ::::::::::##
thoses boundaries go on to +/- infinity this requires    ::::::::####
a three-layer net (if they only go a finite distance     ::::::######
you can do it with 2-layer if the inputs go to both
layers).  The report states that this is how an XOR is done with two 
layers, when in fact it is done by having a single "valley" (or equiv.
a "mountain" the other way) like the fig at left.

Just grumbling ....

alexis wieland
MITRE Corp.