Connectionists: Stephen Hanson in conversation with Geoff Hinton

[Danko Nikolic]

Dear Barak,

Generalized XOR is defined in the manuscript, in the Supplementary
Materials. Here is a snapshot from a Figure that illustrates how to
construct it. Also the code for generating such training data is provided.

[image: image.png]

It is a hard problem to learn for a connectionist network. Perhaps all of
the computers in the world if worked together for 100 years could not learn
the problem with only 20 bits depth, provided that they used standard deep
learning techniques. And yet, it is trivially easy to create a solution for
an engineer who uses their human mind to understand(!) the problem.

Greetings,

Danko


Dr. Danko Nikolić
www.danko-nikolic.com
https://www.linkedin.com/in/danko-nikolic/
-- I wonder, how is the brain able to generate insight? --


On Mon, Jul 18, 2022 at 1:12 PM Barak A. Pearlmutter <barak at pearlmutter.net>
wrote:

> On Mon, 18 Jul 2022 at 08:28, Danko Nikolic <danko.nikolic at gmail.com>
> wrote:
> > In short, learning mechanisms cannot discover generalized XOR functions
> with simple connectivity -- only with complex connectivity. This problem
> results in exponential growth of needed resources as the number of bits in
> the generalized XOR increases.
>
> Assuming that "generalized XOR" means parity, this must rely on some
> unusual definitions which you should probably state in order to avoid
> confusion.
>
> Parity is a poster boy for an *easy* function to learn, albeit a
> nonlinear one. This is because in the (boolean) Fourier domain its
> spectrum consists of a single nonzero coefficient, and functions that
> are sparse in that domain are very easy to learn. See N. Linial, Y.
> Mansour, and N. Nisan, "Constant depth circuits, Fourier Transform and
> learnability", FOCS 1989, or Mansour, Y. (1994). Learning Boolean
> Functions via the Fourier Transform. Theoretical Advances in Neural
> Computation and Learning, 391–424. doi:10.1007/978-1-4615-2696-4_11
>
> --Barak Pearlmutter
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.srv.cs.cmu.edu/pipermail/connectionists/attachments/20220718/3de64244/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image.png
Type: image/png
Size: 71360 bytes
Desc: not available
URL: <http://mailman.srv.cs.cmu.edu/pipermail/connectionists/attachments/20220718/3de64244/attachment.png>