shift invariance and recurrent networks

[Dr. Stefan C. Kremer]

At 08:12 96-02-21 -0800, Jerry Feldman wrote:

> 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.

Recently, many recurrent connectionist networks have been applied to the
problem of grammatical induction (i.e. inducing a grammar, or equivalently
a finite state acceptor for a given set of example strings) [see, for
example: Giles (1990)].  These types of networks are capable of
learning many types of regular grammars (e.g. (0)*(101)(0)*).  Learning of
context-free grammars by connectionist networks has also been studied 
elsewhere [Das (1993)].

The resulting trained networks work only on the basis of local (both
spatially and temporally) interactions among neighbouring processing 
elements.  There are a variety of learning algorithms for these networks.
Some like backpropagation through time [Rumelhart, 1986] are spatially 
local, but temporally global, some like real-time recurrent learning 
[Williams, 1989] are temporally local and spatially global,
and some are both temporally and spatially local like Elman's truncated
gradient descent [Elman, 1990] and various locally recurrent networks
[Tsoi, 1994].

Don't these types of networks can handle shift invariance
problems using local processing?  (I'd agree that they're not biologically
plausible... ;) ).

> 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.

I'm not sure I understand this last part.  Are you saying that 
"preprocessing" and "weight sharing" can handle shift invariance
problems because they are a type of non-local processing?

        -Stefan

P.S.  Here's the refs:
@INPROCEEDINGS{giles90p,
	AUTHOR = "C.L. Giles and G.Z. Sun and H.H. Chen and Y.C. Lee and D.
				  Chen",
	TITLE = "Higher Order Recurrent Networks & Grammatical Inference",
	BOOKTITLE = "Advances in Neural Information Processing Systems~2",
	YEAR = "1990",
	EDITOR = "D.S. Touretzky",
	PUBLISHER = "Morgan Kaufmann Publishers",
	ADDRESS = "San Mateo, CA",
	PAGES = "380-387"}

@INPROCEEDINGS{das93p,
 	AUTHOR = "S. Das and  C.L. Giles and G.Z. Sun ",
	TITLE  = "Using Prior Knowledge in a NNPDA to Learn Context-Free
Languages",
	BOOKTITLE = "Advances in Neural Information Processing Systems 5",
	PUBLISHER = "Morgan Kaufmann Publishers",
	EDITOR = "S.J. Hanson and J.D. Cowan and C.L. Giles",
	PAGES = "65--72",
	ADDRESS = "San Mateo, CA"		
	YEAR = "1993"}

@BOOK{rumelhart86b1,
	EDITOR = "J. L. McClelland, D.E. Rumelhart and the P.D.P. Group (Eds.)",
	AUTHOR = "D. Rumberlhart, G. Hinton, R. Williams",
	TITLE = "Learning Internal Representation by Error Propagation",
	VOLUME = "1:  Foundations",
	BOOKTITLE = "Parallel Distributed Processing:  Explorations in the
Microstructure of Cognition",
	YEAR = "1986",
	PUBLISHER = "MIT Press",
	ADDRESS = "Cambridge, MA"}

@ARTICLE{williams89j1,
	AUTHOR = "R.J. Williams and D. Zipser",
	TITLE = "A Learning Algorithm for Continually Running Fully Recurrent
Neural Networks",
	JOURNAL = "Neural Computation",
	YEAR = "1989",
	VOLUME = "1",
	NUMBER = "2",
	PAGES = "270-280"}

@ARTICLE{elman90j,
	AUTHOR = "J.L. Elman",
	TITLE = "Finding Structure in Time",
	JOURNAL = "Cognitive Science",
	YEAR = "1990",
	VOLUME = "14",
	PAGES = "179-211"}

@ARTICLE{tsoi94j,
	AUTHOR = "A.C. Tsoi and A. Back",
	TITLE = "Locally Recurrent Globally Feedforward Networks, A Critical
Review of Architectures",
	JOURNAL = "IEEE Transactions on Neural Networks",
	VOLUME = "5",
	NUMBER = "2",
	PAGES = "229-239",
	YEAR = "1994"}
--
Dr. Stefan C. Kremer, Neural Network Research Scientist, 
Communications Research Centre, 3701 Carling Avenue, P.O. Box 11490, Station H
Ottawa, Ontario   K2H 8S2             # Tel: (613)990-8175  Fax: (613)990-8369
E-mail:  Stefan.Kremer at crc.doc.ca     # WWW: http://digame.dgcd.doc.ca/~kremer/