Connectionists: Stephen Hanson in conversation with Geoff Hinton

[Barak A. Pearlmutter]

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