From giles@research.nj.nec.com Sat Mar 2 06:41:29 1996 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sat, 2 Mar 96 06:41:22 -0600; AA17386 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sat, 2 Mar 96 06:41:20 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa27950; 1 Mar 96 2:42:59 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa27948; 1 Mar 96 2:25:46 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa13463; 1 Mar 96 2:25:32 EST Return-Path: Date: Thu, 29 Feb 96 10:03:15 EST From: Lee Giles Message-Id: <9602291503.AA29190@alta> To: Dave_Touretzky@cs.cmu.edu Subject: Re: shift invariance Cc: giles@research.nj.nec.com We and others [1, 2, 3, 4] showed that invariances, actually affine transformations, could directly be encoded into feedforward higher-order (sometimes called polynomial, sigma-pi, gated, ...) neural nets such that these networks are invariant to shift, scale, and rotation of individual patterns. As mentioned previously, similar invariant encodings can be had for associative memories in autonomous recurrent networks. Interestingly, this idea of encoding geometric invariances into neural networks is an old one [5]. [1] C.L. Giles, T. Maxwell, ``Learning, Invariance, and Generalization in High-Order Neural Networks'', Applied Optics, 26(23), p 4972, 1987. Reprinted in ``Artificial Neural Networks: Concepts and Theory,'' eds. P. Mehra and B. W. Wah, IEEE Computer Society Press, Los Alamitos, CA. 1992. [2] C.L. Giles, R.D. Griffin, T. Maxwell,``Encoding Geometric Invariances in Higher-Order Neural Networks'', Neural Information Processing Systems, Eds. D.Z. Anderson, Am. Inst. of Physics, N.Y., N.Y., p 301-309, 1988. [3] S.J. Perantonis, P.J.G. Lisboa, ``Translation, Rotation, and Scale Invariant Pattern Recognition by Higher-Order Neural Networks and Moment Classifiers'', IEEE Transactions on Neural Networks, 3(2), p 241, 1992. [4] L. Spirkovska, M.B. Reid,``Higher-Order Neural Networks Applied to 2D and 3D Object Recognition'', Machine Learning, 15(2), p. 169-200, 1994. [5] W. Pitts, W.S. McCulloch, ``How We Know Universals: The Perception of Auditory and Visual Forms'', Bulletin of Mathematical Biophysics, vol 9, p. 127, 1947. A bibtex entry for the above references can be found in: ftp://external.nj.nec.com/pub/giles/papers/high-order.bib -- C. Lee Giles / Computer Sciences / NEC Research Institute / 4 Independence Way / Princeton, NJ 08540, USA / 609-951-2642 / Fax 2482 www.neci.nj.nec.com/homepages/giles.html == From kzhang@cogsci.ucsd.edu Sat Mar 2 06:41:30 1996 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sat, 2 Mar 96 06:41:26 -0600; AA17397 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sat, 2 Mar 96 06:41:23 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id ab27961; 1 Mar 96 2:53:26 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa27954; 1 Mar 96 2:28:20 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa13480; 1 Mar 96 2:27:40 EST Received: from CS.CMU.EDU by B.GP.CS.CMU.EDU id aa25401; 1 Mar 96 1:50:29 EST Received: from mailbox.ucsd.edu by CS.CMU.EDU id aa16656; 1 Mar 96 1:49:53 EST Received: from cogsci.UCSD.EDU (cogsci.ucsd.edu [132.239.147.61]) by UCSD.EDU (8.6.12/8.6.9) with SMTP id WAA29564 for ; Thu, 29 Feb 1996 22:49:45 -0800 Received: by cogsci.UCSD.EDU (4.1/UCSDPSEUDO.4) id AA21976 for connectionists@cs.cmu.edu; Thu, 29 Feb 96 22:49:44 PST From: Kechen Zhang Message-Id: <9603010649.AA21976@cogsci.UCSD.EDU> Date: Thu, 29 Feb 1996 22:49:34 -0800 To: connectionists@cs.cmu.edu Subject: exact shift-invariance from position-independent weights Cc: kzhang@cogsci.ucsd.edu People often do not realize that it is actually possible to get shift-invariant responses from position-dependent weight patterns. The mechanism may seem counter-intuitive at the first sight, but the shift-invariance can be rigorously true. The story begins with the puzzling behaviors of the neurons in the visual area MST of macaque monkeys. For example, some neurons responded very well to a disk rotating clockwise on a screen no matter where the center of the disk was located. The same neurons would be inhibited if the disk rotated counterclockwise, once again, no matter where the disk was located on the screen. Of course, some other cells would prefer counterclockwise rotations to clockwise ones, also in a shift-invariant manner. (The same is true for many dilation/contraction neurons, and probably also for spiral neurons.) Recall that MST is just the next processing stage after area MT, where neurons respond typically to translational movements in a comparatively small region (receptive field). One might guess that some nonlinear, higher-order process is underlying the phenomenon. But brain has probably found a much simpler and more elegant solution. The plausible solution first emerged in a computer simulation experiment by Marty and Margaret Sereno. I helped to formalize their findings (hence this message). Poggio and colleagues independently arrived at similar conclusion via a different path. In short, rigorously shift-invariant responses can be obtained from a simple linear feedforward network whose weight pattern is not shift-invariant at all. The shift-invariance follows from what Poggio et al. called the Green theorems and we called the Gauss and Stokes theorems---all special cases of the general Stokes theorem, which can transform an integral along a closed curve into an integral over an area, and vice versa. Because the learned weight pattern (considered vector field) has a constant curl, the final response depend only on the area of that rotating disk. I think this is a nice example of a counter-intuitive neural mechanism for exact shift-invariance. References: [1] Sereno, M. I. and Sereno , M. E. (1991) Learning to see rotation and dilation with a Hebb rule. In: Advances in Neural Information Processing Systems, R. P. Lippman, J. Moody and D. S. Touretzky, eds. pp. 320-326. Morgan Kauffman, San Mateo, CA. [2] Zhang, K., Sereno, M. I. and Sereno , M. E. (1993) Emergence of position-independent detectors of sense of rotation and dilation with Hebbian learning: an analysis. Neural Computation 5: 597-612. [3] Poggio, T., Verri, A. and Torre, V. (1991) Green theorems and qualitative properties of optical flow. MIT A.I. Memo, no. 1289. -Kechen ________________________________________ Kechen Zhang Department of Cognitive Science University of California, San Diego La Jolla, CA 92093-0515 kzhang@cogsci.ucsd.edu ________________________________________ From horn@neuron.tau.ac.il Sat Mar 2 06:41:32 1996 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sat, 2 Mar 96 06:41:21 -0600; AA17384 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sat, 2 Mar 96 06:41:19 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa26996; 29 Feb 96 13:26:20 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa26994; 29 Feb 96 13:08:48 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa13074; 29 Feb 96 13:07:52 EST Received: from EDRC.CMU.EDU by B.GP.CS.CMU.EDU id aa12113; 29 Feb 96 11:28:24 EST Received: from neuron.tau.ac.il by EDRC.CMU.EDU id aa13955; 29 Feb 96 11:27:23 EST Return-Path: Date: Thu, 29 Feb 1996 18:26:51 +0200 (IST) From: david horn To: Connectionists@cs.cmu.edu Subject: preprint available Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Title: An Orientation Selective Neural Network and its Application to Cosmic Muon Identification Authors: Halina Abramowicz, David Horn, Ury Naftaly, Carmit Sahar--Pikielny School of Physics and Astronomy, Tel Aviv University Abstract: We propose a novel method for identification of a linear pattern of pixels on a two-dimensional grid. Following principles employed by the visual cortex, we employ orientation selective neurons in a neural network which performs this task. The method is then applied to a sample of data collected with the ZEUS detector at HERA in order to identify cosmic muons which leave a linear pattern of signals in the segmented uranium-scintillator calorimeter. A two dimensional representation of the relevant part of the detector is used. The results compared with a visual scan point to a very satisfactory cosmic muon identification. The algorithm performs well in the presence of noise and pixels with limited efficiency. Given its architecture, this system becomes a good candidate for fast pattern recognition in parallel processing devices. Paper can be retrieved from my home page: http://neuron.tau.ac.il/~horn/publications.html David Horn From tp-temp@ai.mit.edu Sat Mar 2 06:41:33 1996 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sat, 2 Mar 96 06:41:24 -0600; AA17388 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sat, 2 Mar 96 06:41:22 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa27961; 1 Mar 96 2:52:16 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa27952; 1 Mar 96 2:26:38 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa13472; 1 Mar 96 2:25:58 EST Received: from EDRC.CMU.EDU by B.GP.CS.CMU.EDU id aa21603; 29 Feb 96 20:37:55 EST Received: from ai.mit.edu by EDRC.CMU.EDU id aa16727; 29 Feb 96 20:37:43 EST Received: from corpus-callosum.ai.mit.edu (CORPUS-CALLOSUM.MIT.EDU) by life.ai.mit.edu (4.1/AI-4.10) for connectionists@cs.cmu.edu id AA06484; Thu, 29 Feb 96 20:37:38 EST From: Tomaso Poggio Received: by corpus-callosum.ai.mit.edu (4.1/AI-4.10) id AA00462; Thu, 29 Feb 96 20:37:36 EST Date: Thu, 29 Feb 96 20:37:36 EST Message-Id: <9603010137.AA00462@corpus-callosum.ai.mit.edu> To: CC:connectionists@cs.cmu.edu;@lucy.cs.wisc.edu Mmdf-Warning: Parse error in original version of preceding line at DST.BOLTZ.CS.CMU.EDU In-Reply-To: Lee Giles's message of Mon, 26 Feb 96 13:01:25 EST <9602261801.AA26373@alta> Subject: Shift Invariance A footnote to Lee Giles msg. Polynomial networks, analog perceptrons, Kolmogorov theorem and invariances were described in an old paper with Werner Reichardt. ``On the representation of multi-input systems: computational properties of polynomial algorithms,'' (T. Poggio and W. Reichardt). {\it Biol. Cyber.}, {\bf 37}, 167-186, 1980. From dwang@cis.ohio-state.edu Sat Mar 2 06:41:37 1996 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sat, 2 Mar 96 06:41:33 -0600; AA17418 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sat, 2 Mar 96 06:41:31 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa29121; 1 Mar 96 18:16:06 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa29119; 1 Mar 96 18:02:18 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa14462; 1 Mar 96 18:01:32 EST Received: from EDRC.CMU.EDU by B.GP.CS.CMU.EDU id aa09754; 1 Mar 96 17:56:32 EST Received: from news.cis.ohio-state.edu by EDRC.CMU.EDU id aa21940; 1 Mar 96 17:56:25 EST Received: from shirt.cis.ohio-state.edu (shirt.cis.ohio-state.edu [164.107.47.4]) by news.cis.ohio-state.edu (8.6.8.1/8.6.4) with ESMTP id RAA06767; Fri, 1 Mar 1996 17:56:15 -0500 From: DeLiang Wang Received: (dwang@localhost) by shirt.cis.ohio-state.edu (8.6.7/8.6.4) id RAA25712; Fri, 1 Mar 1996 17:56:14 -0500 Message-Id: <199603012256.RAA25712@shirt.cis.ohio-state.edu> Subject: Re: shift invariance To: Connectionists@cs.cmu.edu Date: Fri, 1 Mar 1996 17:56:13 -0500 (EST) Cc: jfeldman@ICSI.Berkeley.EDU, DeLiang Wang X-Mailer: ELM [version 2.4 PL22] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 1774 Jerry Feldman writes >2) Understanding how the visual system achieves shift invariance. > > This thread has been non-argumentative. The problem of invariances and >constancies in the visual system remains central in visual science. I can't >think of any useful message-sized summary, but this is an area where >connectionist models should play a crucial role in expressing and testing >theories. But, as several people have pointed out, we can't expect much from >tabula rasa learning. I'd like to know the evidence that the visual system achieves shift (translation) invariance (I'd appreciate references if any). It seems that the eye "focuses" on the object of interest first. In other words, the eye seems to shift with the object, not that the visual system is recognizing the object wherever it occurs on the retina. There seem to be problems with a system that DOES recognize an object no matter where it occurs, when the system faces more than an object as we confront all the time. > 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. Why does it pose a problem to the brain? Perhaps the brain is doing what's regarded as "preprocessing" (a black hole containing many "troubling" things). I do agree that there are limits to tabula rasa learning. The reason that we can learn things we do is, perhaps, critically linked to the prewiring of our brain. We know that we have a lot of difficulty in training a chimpanzee's brain to learn our language, let alone 3-layer perceptrons with backprop. DeLiang Wang From rolf@cs.rug.nl Sat Mar 2 06:41:38 1996 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sat, 2 Mar 96 06:41:32 -0600; AA17415 Message-Id: <9603021241.AA08956@lucy.cs.wisc.edu> Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sat, 2 Mar 96 06:41:29 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa28606; 1 Mar 96 10:11:39 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa28604; 1 Mar 96 9:58:56 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa14151; 1 Mar 96 9:58:12 EST Received: from RI.CMU.EDU by B.GP.CS.CMU.EDU id aa28248; 1 Mar 96 6:52:50 EST Received: from rug102.cs.rug.nl by RI.CMU.EDU id aa20463; 1 Mar 96 6:52:41 EST Received: by rug102.cs.rug.nl (1.37.109.11/16.2) id AA268501184; Fri, 1 Mar 1996 12:53:04 +0100 Date: Fri, 1 Mar 1996 12:53:04 +0100 From: rolf@cs.rug.nl To: Connectionists@cs.cmu.edu Subject: Learning shift invariance Dear connectionists, first of all, thanks to Laurenz Wiskott and Jerry Feldman for arranging the arguments and thus giving the discussion a proper fundament. My view on the matter is the following. The (to me) most interesting part is the generalizing ability which Laurenz has named 4b. I would define the challenge for a neural net to learn shift invariance as follows. There are N patterns and P positions. Beginning from tabula rasa, the network is presented ONE pattern in ALL possible positions to learn shift invariance. For practical reasons, more than one pattern may be required, but I would insist that shift invariance has to be learned from a small subset of the possible patterns. After having learned shift invariance that way the network should be able to learn new patterns at a SINGLE position and then recognize them in an invariant way in ANY position. Again, I would allow a small number of positions. I grant, that the network is NOW a structured one. That is what I would call a satisfactory solution to the problem of learning shift invariance. The network in Geoffrey Hinton's paper does a good job, but it fails to meet this requirement. His parameters are N=16, P=12. Every pattern is trained at 10 (random) positions. So the number of training examples is 0.83*P*N, the number of test examples to which the network generalizes is 0.17*P*N. This gets a little awkward for larger values of N and P. The task as outlined above would allow only s*(P+N-1) training examples, where s is the `small number'. Something like 3 should be appropriate, 1 desirable. Then the network should generalize and recognize all P*N examples correctly. Note that there is no objection to the choice of parameters in the paper but to the scaling behavior for larger parameters. The network must have seen the patterns in almost all possible positions to do the generalization. As far as I have followed the discussion the goal of an O(P+N) dependence of the training set size has not been reached yet. I see 3 possibilities for settling the issue. 1) Construct a network that solves the problem as outlined above. 2) Prove that it can not be done. 3) Prove (experimentally) that visual perception can not solve the problem. I am very interested in any progress in one of these directions, and I am looking forward to the further course of this discussion. Rolf +----------------------------------------------------------------------------+ | Rolf P. W"urtz | mailto: rolf@cs.rug.nl | URL: http://www.cs.rug.nl/~rolf/ | | Department of Computing Science, University of Groningen, The Netherlands | +----------------------------------------------------------------------------+ From joachim@fit.qut.edu.au Sat Mar 2 06:42:58 1996 Received: from lucy.cs.wisc.edu by sea.cs.wisc.edu; Sat, 2 Mar 96 06:42:00 -0600; AA17428 Received: from TELNET-1.SRV.CS.CMU.EDU by lucy.cs.wisc.edu; Sat, 2 Mar 96 06:41:27 -0600 Received: from TELNET-1.SRV.CS.CMU.EDU by telnet-1.srv.cs.CMU.EDU id aa28223; 1 Mar 96 5:01:34 EST Received: from DST.BOLTZ.CS.CMU.EDU by TELNET-1.SRV.CS.CMU.EDU id aa28221; 1 Mar 96 4:51:44 EST Received: from DST.BOLTZ.CS.CMU.EDU by DST.BOLTZ.CS.CMU.EDU id aa13668; 1 Mar 96 4:51:22 EST Received: from EDRC.CMU.EDU by B.GP.CS.CMU.EDU id aa25862; 1 Mar 96 2:58:16 EST Received: from ocean.fit.qut.edu.au by EDRC.CMU.EDU id aa18084; 1 Mar 96 2:57:45 EST Received: from aldebaran.fit.qut.edu.au (joachim@aldebaran.fit.qut.edu.au [131.181.2.29]) by ocean.fit.qut.edu.au (8.7.4/8.7.2) with ESMTP id RAA19057 for ; Fri, 1 Mar 1996 17:22:13 +1000 (EST) Received: (from joachim@localhost) by aldebaran.fit.qut.edu.au (8.7.4/8.7.3) id RAA18553; Fri, 1 Mar 1996 17:14:05 +1000 (EST) Date: Fri, 1 Mar 1996 17:14:05 +1000 (EST) From: Joachim Diederich Message-Id: <199603010714.RAA18553@aldebaran.fit.qut.edu.au> To: connectionists@cs.cmu.edu Subject: Postdoctoral Fellowships Cc: joachim@aldebaran.fit.qut.edu.au POSTDOCTORAL RESEARCH FELLOWSHIPS NEUROCOMPUTING RESEARCH CENTRE QUEENSLAND UNIVERSITY OF TECHNOLOGY BRISBANE, AUSTRALIA QUT-NRC invites applications from qualified academics for a limited number of QUT Postdoctoral Fellowships. These fellowships are available to researchers with less than five years full-time professional experience since being awarded their PhD. The duration of the fellowship is between nine months and two years. Applications from researchers with a background in Computational Learning Theory or Hybrid Artificial Intelligence/Neurocomputing Systems are especially welcomed. The salary is A$37,345 to A$40,087 pa, depending on qualifications and experience. Before submitting an application, intending applicants must contact the Neurocomputing Research Centre. Only applications strongly supported by a QUT research centre will be considered by the university. Applications should reach the Human Resources Director QUT Locked Bag 2 Red Hill QLD 4059 by Friday 29 March 1996. Please direct enquiries to: Prof Joachim Diederich Neurocomputing Research Centre Queensland University of Technology Box 2434 Brisbane Q 4001 AUSTRALIA Phone: +61 7 3864-2143 Fax: +61 7 3864-1801 e-mail: joachim@fit.qut.edu.au