shift invariance

[Jerry Feldman]

 Shift invariance is the ability  of a neural system to recognize a pattern
independent of where appears on the retina. It is generally understood that
this property can not be learned by neural network methods, but I have
not seen a published proof. A "local" learning rule is one that updates the
input weights of a unit as a function of the unit's own activity and some
performance measure for the network on the training example. All biologically
plausible learning rules, as well as all backprop variants, are local in this
sense.

 It is easy to show that no local rule can learn shift invariance.  Consider
learning binary strings with one occurrence of the sequence 101 and
otherwise all zeros. First consider length 5; there are only 3 positive
examples:

		10100	01010	00101

Suppose that the training data does not include the middle
example. The two positive training examples have no 1's in common with the
withheld example. There will be no positive examples with a 1 in position 2 or
4 and many negative examples. Thus there is no correlation between a 1 in
position 2 or 4 and a good example so no local training rule will learn the
correct classification. A similar argument extends to binary strings of
arbitrary length so an arbitrarily small fraction of the training data can be
omitted and still no local updating rules will suffice to learn shift
invariance.

 The one dimensional case of shift invariance can be handled by treating
each string as a sequence and learning a finite-state acceptor. But the
methods that work for this are not local or biologically plausible and
don't extend to two dimensions.

 The unlearnability of shift invarince is not a problem in practice because
people use preprocessing, weight sharing or other techniques to get shift
invariance where it is known to be needed. However, it does pose a problem for
the brain and for theories that are overly dependent on learning.