REVIEW

Review of Neural Networks for Speech Recognition

Richard P. Lippmann^{∗}

MIT Lincoln Laboratory, Lexington, MA 02173, USA

The performance of current speech recogition systems is far below that of humans. Neural nets offer the potential of providing massive parallelism, adaptation, and new algorithmic approaches to problems in speech recognition. Initial studies have demonstrated that multilayer networks with time delays can provide excellent discrimination between small sets of pre-segmented difficult-to-discriminate words, consonants, and vowels. Performance for these small vocabularies has often exceeded that of more conventional approaches. Physiological front ends have provided improved recognition accuracy in noise and a cochlea filter-bank that could be used in these front ends has been implemented using micro-power analog VLSI techniques. Techniques have been developed to scale networks up in size to handle larger vocabularies, to reduce training time, and to train nets with recurrent connections. Multilayer perceptron classifiers are being integrated into conventional continuous-speech recognizers. Neural net architectures have been developed to perform the computations required by vector quantizers, static pattern classifiers, and the Viterbi decoding algorithm. Further work is necessary for large-vocabulary continuous-speech problems, to develop training algorithms that progressively build internal word models, and to develop compact VLSI neural net hardware.

1 State of the Art for Speech Recognition

Speech is the most natural form of human communication. Compact implementations of accurate, real-time speech recognizers would find widespread use in many applications including automatic transcription, simplified manmachine communication, and aids for the hearing impaired and physically disabled. Unfortunately, current speech recognizers perform poorly on talkerindependent continuous-speech recognition tasks that people perform without apparent difficulty. Although children learn to understand speech with little explicit supervision and adults take speech recognition ability for granted, it has proved to be a difficult task to duplicate with machines. As noted by Klatt (1986), this is due to variability and overlap of information in the acoustic signal, to the need for high computation rates (a human-like system must match inputs to 50,000 words in real time), to the multiplicity of analyses that must be performed (phonetic, phonemic, syntactic, semantic, and pragmatic), and to the lack of any comprehensive theory of speech recognition.

∗This work was sponsored by the Department of the Air Force. The views expressed are those of the author and do not reflect the official policy or position of the U.S. Government.

Neural Computation 1, 1–37 (1989) \begin{matrix}c \\ ◯ \end{matrix} 1989 Massachusetts Institute of Technology

The best existing speech recognizers perform well only in artificially constrained tasks. Performance is generally better when training data is provided for each talker, when words are spoken in isolation, when the vocabulary size is small, and when restrictive language models are used to constrain allowable word sequences. For example, talker-dependent isolated-word recognizers can be trained to recognize 105 words with 99% accuracy (Paul 1987). Large-vocabulary talker-dependent word recognition accuracy with sentence context can be as high as 95% for 20,000 words from sentences in office memos spoken with pauses between words (Averbuch et al. 1987).

Accuracy for a difficult 997-word talker-independent continuousspeech task using a strong language model (an average of only 20 different words possible after any other word) can be as high as 96% (Lee and Hon 1988). This word accuracy score translates to an unacceptable sentence accuracy of roughly 50%. In addition, the word accuracy of this high-performance recognizer when tested with no grammar model is typically below 70% correct. Results such as these illustrate the poor low-level acoustic-phonetic matching provided by current recognizers. These recognizers depend heavily on constraining grammars to achieve good performance. Humans do not suffer from this problem. We can recognize clearly spoken but contextually inappropriate words in anomalous sentences such as “John drank the guitar” almost perfectly (Marslen-Wilson 1987).

The current best performing speech recognition algorithms use Hidden Markov Model (HMM) techniques. Good introductions to these techniques and to digital signal processing of speech are available in (Lee and Hon 1988; Parsons 1986; Rabiner and Juang 1986; Rabiner and Schafer 1978). The HMM approach provides a framework which includes an efficient decoding algorithm for use in recognition (the Viterbi algorithm) and an automatic supervised training algorithm (the forward-backward algorithm). New neuralnet approaches to speech recognition must have the potential to overcome the limitations of current HMM systems. These limitations include poor low-level and poor high-level modeling. Poor low-level acoustic-phonetic modeling leads to confusions between acoustically similar words while poor high-level speech understanding or semantic modeling restricts applications to simple situations where finite state or probabilistic grammars are acceptable. In addition, the first-order Markov assumption makes it difficult to model coarticulation directly and HMM training algorithms can not currently learn the topological structure of word and sub-word models. Finally, HMM theory does not specify the structure of implementation hardware. It is likely that high computation and memory requirements of current algo-

Figure 1: Block diagram of an isolated word recognizer.

rithms will require new approaches to parallel hardware design to produce compact, large-vocabulary, continuous-speech recognizers.

2 The Potential of Neural Nets

Neural nets for speech recognition have been explored as part of the recent resurgence of interest in this area. Research has focused on evaluating new neural net pattern classification and training algorithms using real speech data and on determining whether parallel neural net architectures can be designed which perform the computations required by important speech recognition algorithms. Most work has focused on isolated-word recognition.

A block diagram of a simple isolated word recognizer is shown in figure 1. Speech is input to this recognizer and a word classification decision is output on the right. Three major operations are required. First, a preprocessor must extract important information from the speech waveform. In most recognizers, an input pattern containing spectral information from a frame of speech is extracted every 10 msec using Fast Fourier Transform (FFT) or Linear Predictive Coding (LPC) (Parsons 1986; Rabiner and Schafer 1978) techniques. Second, input patterns from the preprocessor must be compared to stored exemplar patterns in word models to compute local frame-to-frame distances. Local distances are used in a third step to time align input pattern sequences to stored exemplar pattern sequences that form word models and arrive at whole-word matching scores. Time alignment compensates for variations in talking rate and pronunciation. Once these operations have been performed, the selected word to output is that word with the highest whole-word matching score.

This paper reviews research on complete neural net recognizers and on neural nets that perform the above three operations. Auditory preprocessors that attempt to mimic cochlea and auditory nerve processing are first reviewed. Neural net structures that can compute local distance scores are then described. Classification results obtained using static speech patterns as inputs are then followed by results obtained with dynamic nets that allow continuous-time inputs. Techniques to integrate neural net and conventional approaches are then described followed by a brief review of psychological and physiological models of temporal pattern sequence recognition. The paper ends with a summary and suggestions for future research. Emphasis throughout is placed on studies that used large public-domain speech data bases or that first presented new approaches.

3 Auditory Preprocessors

A preprocessor extracts important parameters from the speech waveform to compress the amount of data that must be processed at higher levels and provide some invariance to changes in noise, talkers, and the acoustic environment. Most conventional preprocessors are only loosely modeled on the cochlea and perform simple types of filtering and data compression motivated by Fourier analysis and information theory. Recent physiological studies of cochlea and auditory nerve responses to complex stimuli have led to more complex physiological preprocessors designed to closely mimic many aspects of auditory nerve response characteristics. Five of these preprocessors and the VLSI cochlea filter listed in table 1 are reviewed in this section. Good reviews of many of these preprocessors and of response properties of the cochlea and auditory nerve can be found in (Greenberg 1988a; 1988b).

The five preprocessors in table 1 rely on periodicity or synchrony information in filter-bank outputs. Synchrony information is related to the short-term phase of a speech signal and can be obtained from the arrival times of nerve spikes on the auditory nerve. It could increase recognition performance by supplementing the spectral magnitude information used in current recognizers. Synchrony information is typically obtained by filtering the speech input using sharp bandpass filters with characteristics similar to those of the mechanical filters in the cochlea. The resulting filtered waveforms are then processed using various types of time domain analyses that could be performed using analog neural net circuitry.

Spectrograms created using physiological preprocessors for steady state vowels and other speech sounds illustrate an improvement in ability to visually identify vowel formants (resonant frequencies of the vocal tract) in noise (Deng and Geisler 1987; Ghitza 1988; Seneff 1988; Shamma 1988). Comparisons to more conventional front ends using existing speech recognizers have been performed by Beet (Beet et al. 1988), Ghitza (1988), and by Hunt and Lefèbvre (1988). These comparisons demonstrated significant performance improvements in noise (Ghitza 1988; Hunt and Lefèbvre 1988) and

Study  Processing  Comments
Deng and  Cross-Channel  Physiologically Plausible
Geisler (1987) Correlation  (Untested for Speech
of Neural Outputs  Recognition)

Ghitza (1988) Create Histogram  Improved Speech
of Time Intervals  Recognition In Noise

Between Threshold

Crossings of Filter Outputs

Hunt and  Periodicity and  Improved Speech
Lefèbvre  Onset Detection  Recognition In Noise and
(1988)  with Spectral Tilt

Lyon and Mead Tapped Transmission Implemented Using
(1988) Line Filter with Micropower VLSI
49 Outputs  Techniques

Seneff (1988)  Provides Periodicity Synchrony Spectrograms
and Spectral  Provide Enhanced Spectral
Magnitude Outputs Resolution (Untested for

Speech Recognition)

Shamma (1988) Lateral Inhibition  Physiologically Plausible
Across Cochlea  (Untested for Speech
Filter Outputs  Recognition)

Table 1: Recent Physiological Preprocessors.

with filtering that tilts the input spectrum up at high frequencies (Hunt and Lefèbvre 1988). Extensive comparisons have not, however, been made between physiological preprocessors and conventional preprocessors when the conventional preprocessors incorporate current noise and stress compensation techniques. Positive results from such comparisons and more detailed theoretical analyses would do much to foster the acceptance of these new and computationally intensive front ends.

Lyon and Mead (1988) describe a filter bank that could be used in a physiological preprocessor. This filter bank was carefully modeled after the cochlea, provides 49 analog outputs, and has been implemented using micropower analog VLSI CMOS processing. Extra circuitry would be required to provide synchrony or spectral magnitude information for a speech recognizer. This recent work demonstrates how preprocessors can be miniaturized using analog VLSI techniques. The success of this approach is beginning to demonstrate that ease of implementation using VLSI techniques may be more important when comparing alternative neural net approaches than computational requirements on serial Von Neuman machines.

4 Computing Local Distance Scores

Conventional speech recognizers compute local frame-to-frame distances by comparing each new input pattern (vector of parameters) provided by a preprocessor to stored reference patterns. Neural net architectures can compute local frame-to-frame distances using fine-grain parallelism for both continuousobservation and discrete-observation recognizers. New neural net algorithms can also perform vector quantization and reduce the dimensionality of input patterns.

Local distances for continuous-observation recognizers are functions related to log likelihoods of probability distributions. Simple log likelihood functions such as those required for independent Gaussian or binomial distributions can be calculated directly without training using single-layer nets with threshold-logic nonlinearities (Lippmann 1987; Lippmann et al. 1987). More complex likelihood functions can be computed using multilayer perceptrons (Cybenko 1988; Lapedes and Farber 1988; Lippmann et al. 1987), hierarchical nets that compute kernel functions (Albus 1981; Broomhead and Lowe 1988; Hanson and Burr 1987; Huang and Lippmann 1988; Moody 1988; Moody and Darken 1988), or high-order nets (Lee et al. 1986; Rumelhart et al. 1986a). Training to produce these complex functions is typically longest with multilayer perceptrons. These nets, however, often provide architectures with fewer nodes, simpler nodal processing elements, and fewer weights. They also may develop internal hidden abstractions in hidden layers that can be related to meaningful acoustic-phonetic speech characteristics such as formant transitions and that also could be applied to many different speech recognition tasks.

Discrete-observation recognizers first perform vector quantization and label each input with one particular symbol. Symbols are used to calculate local distances via look-up tables that contain symbol probabilities for each reference pattern. The look-up table calculation can be performed by simple single-layer perceptrons. The perceptron for any reference pattern must have as many inputs as there are symbols. Weights must equal symbol probabilities and all inputs must be equal to zero except for that corresponding to the current input symbol. Alternatively, a multilayer perceptron could be used to store probabilities for symbols that have been seen and interpolate between these probabilities for unseen symbols. The vector quantization operation can be performed using an architecture similar to that used by Kohonen’s feature-map net (Kohonen 1984). Inputs to the feature-map net feed an array of codebook nodes containing one node for each symbol. Components of the Euclidean distance between the input and the reference pattern represented by weights to each node are computed in each node. The codebook node with the smallest Euclidean distance to the input is selected using lateral inhibition or other maximum-picking techniques (Lippmann et al. 1987). This process guarantees that only one node with the minimum Euclidean distance to the input has a unity output as required. Weights used in this architecture can be calculated using the feature-map algorithm or any other standard vector quantization algorithm based on Euclidean distances such as k-means clustering (Duda and Hart 1973).

Kohonen’s feature-map vector quantizer is an alternative sequentiallytrained neural net algorithm. It has been tested successfully in an experimental speech recognizer (Kohonen 1988; Kohonen et al. 1984) but not evaluated with a large public speech data base. A version with a small number of nodes but including training logic has been implemented in VLSI (Mann et al. 1988). Experiments with a discrete-observation HMM recognizer (Mann et al. 1988) and with a template-based recognizer (Naylor and Li 1988) demonstrated that this algorithm provides performance similar to that provided by conventional clustering procedures such as k-means clustering (Duda and Hart 1973). The feature-map algorithm incrementally trains weights to a two-dimensional grid of nodes such that after training, nodes that are physically close in the grid correspond to input patterns that are close in Euclidean distance. One advantage of this topological organization is that averaging outputs of nodes that are physically close using nodes at higher levels corresponds to a probability smoothing technique often used in speech recognizers called Parzen smoothing (Duda and Hart 1973). This averaging can be performed by nodes with limited fan-in and short connections.

The auto-associative multilayer perceptron (Elman and Zipser 1987; Hinton 1987) is a neural net algorithm that reduces the dimensionality of continuousvalued inputs. It is a multilayer perceptron with the same number of input and output nodes and one or more layers of hidden nodes. This net is trained to reproduce the input at the output nodes through a small layer of hidden nodes. Outputs of hidden nodes after training can be used as reduced dimensional inputs for speech processing as described in (Elman and Zipser 1987; Fallside et al. 1988). Recent theoretical analyses have demonstrated that auto-associative networks are closedly related to a standard statistical technique called principal components analysis (Baldi and Hornik 1989; Bourlard and Kamp 1988). Auto-associative nets are thus not a new analytical tool but instead a technique to perform the processing required by principal components analysis.

5 Static Classification of Speech Segments

Many neural net classifiers have been applied to the problem of classifying static input patterns formed from a spectral analysis of pre-segmented words, phonemes, and vowels. Table 2 summarizes results of some representative studies. Introductions to many of the classifiers listed in this table and to neural net training algorithms are available in (Cowan and Sharp 1988; Hinton 1987; Lippmann et al. 1987). Unless otherwise noted, error rates in this and other tables refer to talker-dependent training and testing, multilayer perceptrons were trained using back-propagation (Rumelhart et al. 1986a), and systems were trained and tested on different data sets. The number of tokens in this and other tables refers to the total number of speech samples available for both training and testing and the label “multi-talker” refers to results obtained by testing and training using data from the same group of talkers. The label “talker-independent” refers to results obtained by training using one group of talkers and testing using a separate group with no common members.

Input patterns for studies in table 2 were applied at once as one whole static spectrographic (frequency versus time) pattern. Neural nets were static and didn’t include internal delays or recurrent connections that could take advantage of the temporal nature of the input for real-time processing. This approach might be difficult to incorporate in real-time speech recognizers because it would require long delays to perform segmentation and form the input patterns in an input storage buffer. It would also require accurate presegmentation of both testing and training data for good performance. This pre-segmentation was performed by hand in many studies.

Multilayer perceptrons and hierarchical nets such as the feature-map classifier and Kohonen’s learning vector quantizer (LVQ) have been used to classify static patterns. Excellent talker-dependent recognition accuracy near that of experimental HMM and commercial recognizers has been provided by multilayer perceptrons using small sets of words and digits. Hierarchical nets have provided performance similar to that of multilayer perceptrons but with greatly reduced training times and typically more connection weights and nodes.

5.1 Multilayer Perceptrons. Multilayer perceptron classifiers have been applied to speech problems more often than any other neural net classifier. A simple example from Huang and Lippmann (1988) presented in figure 2 illustrates how these nets can form complex decision regions with speech data. Input data obtained by Peterson and Barney (1952) consisted of the first two formants from vowels spoken by men, women, and children. Decision regions shown in the right side of figure 2 were formed by the two-layer perceptron with 50 hidden nodes trained using back-propagation shown on the left. Training required more than 50,000 trials. Decision region boundaries are near those that are typically drawn by hand to separate vowel regions and the performance of this net is near that provided by commonly used

Speech

Study  Network  Materials  Error Rate
Elman and Multilayer  1 Talker, CV’s Cons. - 5%
Zipser  Perceptron  /b,d,g/ /i,a,u/ Vowels - 0.5%
(1987)  (MLP)  505 Tokens

16 × 20 Inputs

Huang and MLP, Feature  67 Talkers  Gaussian,
Lippmann, Map Classifier  10 Vowels  FMC, MLP ≈ 20%
(1988)  (FMC)  671 Tokens  FMC Trains Fastest

2 Inputs

Kammerer MLP  11 Talkers  Talker Dep. - 0.4%
and Kupper 16 × 16 Inputs  20 Words  Talker Indep. - 2.7%
(1988)  5720 Tokens

Kohonen  Learning Vector Labeled  Gaussian - 12.9%
(1988)  Quantizer (LVQ) Finish Speech kNN - 12.0%
15 Inputs  3010 Tokens  LVQ - 10.9%

Lippmann MLP  16 Talkers  Gaussian - 8.7%
and Gold  11 × 2 Inputs  7 Digits  kNN - 6%
(1987)  2,912 Tokens MLP - 7.6%

Peeling  MLP  40 Talkers  Talker Dep. - 0.3%
and Moore 19 × 60 Inputs  10 Digits  Multi Talker - 1.9%
(1987)  16,000 Tokens

Table 2: Recognition of Speech Patterns Using Static Neural Nets.

conventional k-nearest neighbor (kNN) and Gaussian classifiers (Duda and Hart 1973).

A more complex experiment was performed by Elman and Zipser (1987) using spectrographic-like inputs. Input patterns formed from 16 filter-bank outputs sampled 20 times over a time window of 64 msec were fed to nets with one hidden layer and 2 to 6 hidden nodes. The analysis time window was centered by hand on the consonant voicing onset. Networks were trained to recognize consonants or vowels in consonant-vowel (CV) syllables composed of the consonants /b,d,g/ and the vowels /i,a,u/. Error rates were roughly 5% for consonant recognition and 0.5% for vowel recognition. An analysis indicated that hidden nodes often become feature detectors and differentiate between important subsets of sound types such as consonants versus vowels. This study demonstrated the importance of choosing a good data representation for speech and of normalizing speech inputs. It also raised the important question of training time because many experiments on this small data base required more than 100,000 training trials.

Lippmann and Gold (1987) performed another early study to compare multilayer perceptrons and conventional classifiers on a digit classification task. This study was motivated by single-talker results obtained by Burr (1988a). Inputs were 22 cepstral parameters from two speech frames located automatically by finding the maximum-energy frame for each digit. One- to three-layer nets with from 16 to 256 nodes in each hidden layer were evaluated using digits from the Texas Instruments (TI) 20-Word Speech Data Base (Doddington and Schalk 1981). Multilayer perceptron classifiers outperformed a Gaussian but not a kNN classifier. Hidden layers were required for good performance. A single-layer perceptron provided poor performance, much longer training times, and sometimes never converged during training. Most rapid training (less than 1000 trials) was provided by all three-layer perceptrons. These results demonstrate that the simple hyperplane decision regions provided by single-layer perceptrons are sometimes not sufficient and that rapid training and good performance can be obtained by tailoring the size of a net for a specific problem. The digit data used in these experiments was also used to test a multilayer perceptron chip implemented in VLSI (Raffel et al. 1987). This chip performed as well as computer simulations when down-loaded with weights from those simulations.

Figure 2: Decision regions formed by a 2-layer perceptron using back-propagation training and vowel formant data.

Kammerer and Kupper obtained surprisingly good recognition results for words from the TI 20-word data base (Kammerer and Kupper 1988). A single-layer perceptron with spectrogram-like input patterns performed slightly better than a DTW template-based recognizer. Words were first time normalized to provide 16 input frames with 16 2-bit spectral coefficients per frame. Expanding the training corpus by temporally distorting training tokens reduced the error slightly and best performance was provided by single and not multilayer perceptrons. Talker-dependent error rates were 0.4% (14/3520) for the single-layer perceptron and 0.7% (25/3520) for the DTW recognizer. These error rates are better than all but one of the commercial recognizers evaluated in (Doddington and Schalk 1981) and demonstrate good performance for a single-layer perceptron without hidden nodes. Talkerindependent performance was evaluated by leaving out the training data for each talker, one at a time, and testing using that talker’s test data. Average talker-independent error rates were 2.7% (155/5720) for the single-layer perceptron and 2.5% (145/5720) for the DTW recognizer. Training time was 6 to 25 minutes per talker on an array processor for the talker-dependent studies and 5 to 9 hours for the talker-independent studies.

Peeling and Moore (1987) obtained extremely good recognition results for digit classification. A multilayer perceptron with one hidden layer and 50 hidden nodes provided best performance. Its talker-dependent performance was low and near that provided by an advanced HMM recognizer. Spectrogramlike input patterns were generated using a 19-channel filter-bank analyzer with 20 msec frames. Nets could accommodate 60 input frames (1.2 seconds) which was enough for the longest duration word. Shorter words were padded with zeros and positioned randomly in the 60 frame input buffer. Nets were trained using different numbers of layers and hidden units and speech data from the RSRE 40-speaker digit data base. Multi-talker experiments explored performance when recognizers were tested and trained using data from all talkers. Error rates were near zero for talker-dependent experiments 0.25% (5/2000) and low for multi-talker experiments 1.9% (78/4000). Error rates on an advanced HMM recognizer under the same conditions were 0.2% (4/2000) and 0.6% (25/4000) respectively. The computation required for recognition using multilayer perceptrons was typically more than five times less than that required for the HMM recognizer.

The good small-vocabulary word recognition results obtained by both Kammerer and Kupper (1988) and Peeling and Moore (1987) suggest that back-propagation can develop internal feature detectors to extract important invariant acoustic events. These results must be compared to those of other experiments which attempted to classify digits without time alignment. Burton, Shore, and Buck (Burton et al. 1985; Shore and Burton 1983) demonstrated that talker-dependent error rates using the TI 20-Word Data Base can be as low as 0.3% (8/2560) for digits and 0.8% (40/5120) for all words using simple vector-quantization recognizers that do not perform time alignment. These results suggest that digit recognition is a relatively simple task where dynamic time alignment is not necessary and talker-dependent ac-

Figure 3: Block diagram of the hierarchical feature-map classifier.

curacy remains high even when temporal information is discarded. The good performance of multilayer perceptrons is thus not surprising. These studies and the multilayer perceptron studies do, however, suggest designs for implementing computationally-efficient real-time digit and small-vocabulary recognizers using analog neural-net VLSI processing.

5.2 Hierarchical Neural Nets that Compute Kernel Functions. Hierarchical neural net classifiers which use hidden nodes that compute kernel functions have also been used to classify speech patterns. These nets have the advantage of rapid training and the ability to use combined supervised/unsupervised training data.

Huang and Lippmann (1988) described a net called a feature-map classifier and evaluated the performance of this net on the vowel data plotted in figure 2 and on difficult artificial problems. A block diagram of the featuremap classifier is shown in figure. 3. Intermediate codebook nodes in this net compute kernel functions related to the Euclidean distance between the input and cluster centers represented by these nodes. The lower feature map net is first trained without supervision to form a vector quantizer and the upper perceptron-like layer is then trained with supervision using a modified version of the LMS algorithm. This classifier was compared to the multilayer perceptron shown in figure 2 and to a kNN classifier. All classifiers provided an error rate of roughly 20%. The 2-layer perceptron, however, required more than 50,000 supervised training trials for convergence. The feature map classifier reduced the amount of supervised training required by three orders of magnitude to fewer than 50 trials. Similar results were obtained with artificial problems.

Kohonen and co-workers (Kohonen et al. 1988) compared a neural-net classifier called a learning vector quantizer (LVQ) to Bayesian and kNN classifiers. The structure of the learning vector quantizer is similar to that of the feature-map classifier shown in figure 3. Training differs from that used with the feature-map classifier in that a third stage of supervised training is added which adjusts weights to intermediate codebook nodes when a classification error occurs. Adjustments alter decision region boundaries slightly but maintain the same number of codebook nodes.

Bayesian, kNN and LVQ classifiers were used to classify 15-channel speech spectra manually extracted from stationary regions of Finnish speech waveforms. All classifiers were tested and trained with separate sets of 1550 singleframe patterns that were divided into 18 phoneme classes (Kohonen et al. 1988). A version of the LVQ classifier with 117 codebook nodes provided the lowest error rate of 10.9% averaging over results where training and testing data sets are interchanged. The Bayesian classifier and kNN classifiers had slightly higher error rates of 12.9% and 12.0% respectively. Training time for the LVQ classifier was roughly 10 minutes on an IBM PC/AT. These results and those of Huang and Lippmann (1988) demonstrate that neural nets that use kernel functions can provide excellent performance on speech tasks using practical amounts of training time. Other experiments on artificial problems described in (Kohonen et al. 1988) illustrate trade-offs in training time. Boltzmann machines provided near optimal performance on these problems followed by the LVQ classifier and multilayer perceptrons. Training times were 5 hours on an array processor for the Boltzmann machine, 1 hour on a Masscomp MC 5600 for the multilayer perceptron, and roughly 20 minutes on the Masscomp for the LVQ classifier.

Two recent studies (Niranjan and Fallside 1988; Bridle 1988) have begun to explore a hierarchical net where nodes in a hidden layer compute kernel functions called radial basis functions (Broomhead and Lowe 1988). These nets are similar to previous classifiers that use the method of potential functions (Duda and Hart 1973). They have an advantage over multilayer perceptrons in that once the locations of the kernel functions are established, weights to the output nodes are determined uniquely by solving a least squares problem using matrix-based approaches. Initial results with small amounts of speech data consisting of vowels (Niranjan and Fallside 1988) and words (Bridle 1988) have been encouraging. Further work must explore techniques to assign the locations of kernel functions and adjust scale factors that determine the range of influence of each kernel function.

6 Dynamic Classification of Speech Segments

New dynamic neural net classifiers that incorporate short delays, temporal integration, or recurrent connections have been developed specifically for speech recognition. Spectral inputs for these classifiers are applied to input nodes sequentially, one frame at a time. These classifiers could thus be integrated into real time speech recognizers more easily than static nets because accurate pre-segmentation is typically not required for good performance and only short delays are used.

Both multilayer nets with delays and nets with recurrent connections have been used to classify acoustically similar words, consonants, and vowels. Excellent performance has been obtained using time delay nets in many studies including those by Lang and Hinton (1988) and by Waibel et al. (1987; 1988). Performance for small vocabularies often slightly exceeded that provided by high-performance experimental HMM recognizers. Techniques have also been developed to scale nets up for larger vocabularies and to speed up training times both for feed-forward and recurrent nets. Rapid training has been demonstrated using a hierarchical learning vector quantizer with delays and good performance but extremely long training times has been provided by Boltzmann machines.

6.1 Time-Delay Multilayer Perceptrons. Some of the most promising neural-net recognition results have been obtained using multilayer perceptrons with delays and some form of temporal integration in output nodes (Lang and Hinton 1988; Waibel et al. 1987; Waibel et al. 1988). Table 3 summarizes results of six representative studies.

Early results on consonant and vowel recognition were obtained by Waibel and co-workers (Waibel et al. 1987) using the multilayer perceptron with time delays shown in figure 4. The boxes labeled τ in this figure represent fixed delays. Spectral coefficients from 10 msec speech frames (16 per frame) are input on the lower left. The three boxes on the bottom thus represent an input buffer containing a context of three frames. Outputs of the nodes in these boxes (16×3 spectral coefficients) feed 8 hidden nodes in the first layer. Outputs from these nodes are buffered across the five boxes in the first hidden layer to form a context of five frames. Outputs from these boxes (8 × 5 node outputs) feed three hidden nodes in the second hidden layer. Outputs from these three nodes are integrated over time in a final output node.

In initial experiments (Waibel et al. 1987), the time-delay net from figure 4 was trained using back-propagation to recognize the voiced stops /b,d,g/. Separate testing and training sets of 2000 voiced stops spoken by three talkers were excised manually from a corpus of 5260 Japanese words. Excised portions sampled the consonants in varying phonetic contexts and contained 15 frames (150 msec) centered by hand around the vowel onset. The neural net classifier provided an error rate of 1.5% compared to an error rate 6.5% provided by a simple discrete-observation HMM recognizer. Training the time-delay net took several days on a four-processor Alliant computer. More recent work (Waibel et al. 1988) has led to techniques that merge smaller nets designed to recognize small sets of consonants and vowels into large nets which can recognize all consonants at once. These techniques greatly reduce training time, improve performance and are a practical approach to the scaling problem. Experiments resulted in low error rates of 1.4% for the consonants /b,d,g,p,t,k/ and 1.4% for the vowels /i,a,u,e,o/. The largest net designed from smaller subnets provided a talker-dependent error rate for one talker of 4.1% for 18 consonants. An advanced discrete-observation

Speech

Study  Network  Materials  Error Rate
Lang and  Time Delay  100 Talkers  Multi Talker - 7.8%
Hinton  MLP  “B,D,E,V”
(1988)  16 Inputs  768 Tokens

Unnikrishnan, Time Concen- 1 Talker  0.7%
Hopfield, and tration Net  Digits
Tank (1988)  32 Inputs  432 Tokens

Waibel et al. Time Delay  3 Japanese  /b,d,g/ - 1.5%
(1987)  MLP  Talkers, /b,d,g/,
16 Inputs  Many Contexts

> 4, 000 Tokens

Waibel, Sawai, Time Delay  1 Japanese  /b,d,g,p,t,k/ - 1.4%
and Shikano  MLP  Talker, 18 Cons.,
(1988)  16 Inputs  5 Vowels  18 Cons. - 4.1%
> 10, 000 Tokens 5 Vowels - 1.4%

Watrous  Temporal Flow 1 Talker  /b,d,g/ - 0.8%
(1988)  Structured  Phonemes, Words rapid/rabid - 0.8%
MLP  > 2, 000 Tokens
16 Inputs  /i,a,u/ - 0.0%

McDermott  Time Delay  3 Japanese  /b,d,g/ - 1.7%
and Katagiri LVQ  Talkers, /b,d,g/
(1988)  16 Inputs  > 4, 000 Tokens

Table 3: Recognition of Speech Using Time-Delay Neural Nets.

HMM recognizer provided an error rate of 7.3% on this task. These two studies demonstrate that good performance can be provided by time-delay nets when the network structure is tailored to a specific problem. They also demonstrate how small nets can be scaled up to solve large classification problems without scaling up training times substantially.

Lang and Hinton (1988) describe an extensive series of experiments that led to a similar high-performance time-delay net. This net was designed to classify four acoustically similar isolated words “B”, “D”, “E”, and “V” that are the most confusable subset from the spoken alphabet. A multi-talker recognizer for 100 male talkers was first trained and tested using pre-segmented 144 msec speech samples taken from around the vowel onset in these words. A technique called multi-resolution training was developed to shorten training time. This involved training nets with smaller numbers of hidden nodes, splitting weight values to hidden nodes to create larger desired nets, and then re-training the larger nets. A multiresolution trained net provided an error rate of 8.6%. This result, however, required careful pre-segmentation of each word. Pre-segmentation was not required by another net which allowed continuous speech input and classified the input as that word corresponding to the output node whose output value reached the highest level. Training used simple automatic energy-based segmentation techniques to extract 216 msecs of speech from around the vowel onset in each word. This resulted in

Figure 4: A time-delay multilayer perceptron.

an error rate of 9.5%. Outputs were then trained to be high and correct for the 216 msec speech segments as before, but also low for counter-example inputs selected randomly from the left-over background noise and vowel segments. Inclusion of counter-examples reduced the error rate to 7.8%. This performance compares favorably with the 11% error rate estimated for an enhanced HMM recognizer on this data base and based on performance with the complete E-set (Bahl et al. 1988; Lang and Hinton 1988).

Watrous (1988) also explored multilayer perceptron classifiers with time delays that extended earlier exploratory work on nets with recurrent connections (Watrous and Shastri 1987). These multilayer nets differed from those described above in that recurrent connections were provided on output nodes, target outputs were Gaussian-shaped pulses, and delays and the network structure were carefully adjusted by hand to extract important speech features for each classification task. Networks were tested using hand-segmented speech and isolated words from one talker. Good discrimination was obtained for many different recognition tasks. For example, the error rate was 0.8% for the consonants /b,d,g/, 0.8% for the word pair “rapid/rabid,” and 0.0% for the vowels /i,a,u/. Watrous has also explored the use of gradient methods of nonlinear optimization to decrease training time (Watrous 1986).

Rossen et al. (1988) recently described another time delay classifier. It uses more complex input data representations than the time-delay nets described above and a brain-state-in-a-box neural net classifier to integrate information over time from lower-level networks. Good classification performance was obtained for six stop consonants and three vowels. Notable features of this work are training to reject noise inputs as in (Lang and Hinton 1988) and the use of modular techniques to build large nets from smaller trained modules as in (Waibel et al. 1988). Other recent work demonstrating good phoneme and syllable classification using structured multilayer perceptron nets with delays is described in (Harrison and Fallside 1988; Homma et al. 1988; Irino and Kawahara 1988; Kamm et al. 1988; Leung and Zue 1988).

Unnikrishnan, Hopfield, and Tank (1988) obtained low error rates on digit classification using a time-concentration neural net that does not use only simple delays. This net, described in (Tank and Hopfield 1987), uses variable length delay lines designed to disperse impulsive inputs such that longer delays result in more dispersion. Impulsive inputs to these delay lines are formed by enhancing spectral peaks in the outputs of 32 bandpass filters. Outputs of delay lines are multiplied by weights and summed to form separate matched filters for each word. These matched filters concentrate energy in time and produce a large output pulse at the end of the correct word. Limited evaluations reported in (Unnikrishnan et al. 1988) for digit strings from one talker demonstrated good performance using a modified form of back-propagation training. A prototype version of this recognizer using discrete analog electronic devices was also constructed (Tank and Hopfield 1987). Tests performed by Gold with a large speech data base and a hierarchical version of the time concentration net that included both allophone and word models yielded performance that was no better than that of an existing HMM recognizer (Gold 1988).

6.2 Hierarchical Nets that Compute Kernel Functions. McDermott and Katagiri (1988) used Kohonen’s LVQ classifier on the same /b,d,g/ speech data base used by Waibel et al. (1987). They were able to obtain an error rate of 1.7% which is not statistically different from the 1.5% error rate obtained by Waibel et al. using the time-delay net shown in figure 4 (Waibel et al. 1987). Inputs for the LVQ classifier consisted of a 7-frame window of 16 filterbank outputs. The nearest of 150 codebook nodes were determined as the 15-frame speech samples were passed through this 7-frame window. The normalized distances between nearest nodes and 112-element input patterns were integrated over time and used to classify speech inputs. The error rate without the final stage of LVQ training was high (7.3%). It dropped to 1.7% after LVQ training was complete. This result demonstrates that nets with kernel functions and delays can perform as well as multilayer perceptrons with delays. These nets train faster but require more computation and memory during use. In this application, for example, the LVQ classifier required 17,000 weights which was more than 30 times as many required for the time-delay net used in (Waibel et al. 1987). If memory is not an important limitation, rapid search techniques such as hashing and k-d trees described in (Omohundro 1987) can be applied to the LVQ classifier to greatly reduce the time required to find nearest-neighbors. This would make the differences in computation time between these alternative approaches small on existing serial Von Neuman computers.

6.3 Nets with Recurrent Connections. Nets with recurrent connections have not been used as extensively for speech recognition problems as feed-forward nets because they are more difficult to train, analyze, and design. Table 4 summarizes results of three representative studies. Initial work explored the use of recurrent Boltzmann machines. These nets typically provided good performance on small problems but required extremely long training times. More recent studies have focused on modified backpropagation training algorithms described in (Almeida 1987; Jordan 1986; Pineda 1987; Rohwer and Forrest 1987; Rumelhart et al. 1986a; Watrous 1988) that can be used with recurrent nets and time varying inputs.

Prager, Harrison, and Fallside (Prager et al. 1986) performed one of the first experiments to evaluate the use of Boltzmann machines for speech recognition. At the time this study was performed, the Boltzmann machine training algorithm described in (Ackley et al. 1985) was the only well-known technique that could be used to train nets with recurrent connections. This training algorithm is computationally intensive because simulated annealing procedures (Kirkpatrick et al. 1983) are used to perform a probabilistic search of connection weights. Binary input and output data representations were developed to apply Boltzmann machines to an 11-vowel recognition task. One successful net used 2048 input bits to represent 128 spectral values and 8 output bits to specify the vowel. Nets typically contained 40 hidden nodes and 7320 links. Training used 264 tokens from 6 talkers and required 6 to 15 hours of processing on a high-speed array processor. The resulting multitalker error rate was 15%.

Prager, Harrison, and Fallside (Prager et al. 1986) also explored the use of a Boltzmann machine recognizer inspired by single-order Markov Model approaches to speech recognition. A block diagram of this recurrent net is presented in figure 5. The output of this net is delayed and fed back to the input to “carry” nodes that provide information about the prior state. This net was trained to identify words in two sentences spoken by one talker. Training time required 4 to 5 days of processing on a VAX 11/750 computer and performance was nearly perfect on the training sentences. Other recent work on Boltzmann machines (Bengio and De Mori 1988; Kohonen et al. 1988; Prager and Fallside 1987) demonstrates that good performance can be provided at the expense of excessive training time. Preliminary work on analog VLSI implementations of the training algorithm required by Boltzmann machines has demonstrated practical learning times for small hardware networks (Alspector and Allen 1987).

Many types of recurrent nets have been proposed that can be trained with modified forms of back-propagation. Jordan (1986) appears to have been the first to study nets with recurrent connections from output to input nodes as in figure 5. He used these nets to produce pattern sequences. Bourlard and Wellekens (1988) recently proved that such nets could be used to calculate local probabilities required in HMM recognizers and Robinson and

Speech

Study  Network  Materials  Error Rate
Anderson,  Recurrent Net 20 Talkers, CV’s Talker Indep. - 13.1%
Merrill, and 36 Inputs /b,d,g,p,t,k/, /a/
Port (1988)  561 Tokens

Prager,  Boltzmann  6 Talkers  Multi Talker - 15%
Harrison, and Machine  11 Vowels
Fallside (1986) 2048 Inputs  264 Tokens

Robinson and Recurrent Net 7 Talkers  Multi Talker - 30.8%
Fallside  20 Inputs  27 Phonemes
(1988b)  558 Sentences  Talker Dep. - 22.7%

Table 4: Recognition of Speech Using Recurrent Neural Nets.

Figure 5: A recurrent neural net classifier.

Fallside (1988a) pointed out the relationship between these nets and state space equations used in classical control theory. Nets with recurrent selflooping connections on hidden and output nodes were studied by Watrous and Shastri (1987) for a speech recognition application. Nets with recurrent connections from hidden nodes to input nodes were studied by Elman (1988) and by Servan-Schreiber, Cleeremans, and McClelland (1988) for natural language applications.

Two recent studies have explored recurrent nets similar to the net shown in figure 5 when trained with modified forms of back-propagation. Robinson and Fallside (1988b) used such a net to label speech frames with one of 27 phoneme labels using hand-marked testing and training data. Training used an algorithm suggested by Rumelhart et al. (1986a) that, in effect, replicates the net at every time step during training. Talker-dependent error rates were 22.7% for the recurrent net and 26.0% for a simple feed-forward net with delays between input nodes to provide input context. Multi-talker error rates were 30.8% for the recurrent net and 40.8% for the feed-forward net. A 64 processor array of transputers provided practical training times in these experiments.

Anderson, Merrill, and Port (1988) also explored recurrent nets similar to the net in figure 5. Stimuli were CV syllables formed from six stop consonants and the vowel /a/ that were hand segmented to contain 120 msecs of speech around the vowel onset. Nets were trained on data from 10 talkers, tested on data from 10 other talkers, and contained from one to two hidden layers with different numbers of hidden nodes. Best performance (an error rate of 13.1%) was provided by a net with two hidden layers.

7 Integrating Neural Net and Conventional Approaches

Researchers are beginning to combine conventional HMM and DTW speech recognition algorithms with neural net classification algorithms and also to design neural net architectures that perform computations required by important speech recognition algorithms. This may lead to improved recognition accuracy and also to new designs for compact real-time hardware. Combining the good discrimination of neural net classifiers with the automatic scoring and training algorithms used in HMM recognizers could lead to rapid advances by building on existing high-performance recognizers. Studies that have combined neural net and conventional approaches to speech recognition are listed in table 5. Many (Bourlard and Wellekens 1987; Burr 1988b; Huang et al. 1988; Sakoe and Iso 1987) integrate multilayer perceptron classifiers with conventional DTW and HMM recognizers and one (Lippmann and Gold 1987) provides a neural-net architecture that could be used to implement an HMM Viterbi decoder. One study (Bourlard and Wellekens 1987) demonstrated how a multilayer perceptron could be integrated into a DTW continuous-speech recognizer to improve recognition performance.

7.1 Integrating Multilayer Perceptron Classifiers with DTW and HMM Recognizers. At least three groups have proposed recognizers where multilayer perceptrons compute distance scores used in DTW or HMM recognizers (Bourlard and Wellekens 1987; Burr 1988a; Sakoe and Iso 1987). Bourlard and Wellekens (1987) demonstrated how the multilayer perceptron shown in figure 6 could be used to calculate allophone distance scores required for phoneme and word recognition in a DTW discrete-observation recognizer. One net had inputs from 15 frames of speech centered on the current frame, 50 hidden nodes, and 26 output nodes. Outputs corresponded to allophones in a 10-digit German vocabulary. Inputs were from 60 binary variables per frame. One input bit was on in each frame to specify the codebook entry that represented that frame. The multilayer perceptron was trained using hand-labeled training data to provide a high output only for that output node corresponding to the current input allophone. Recognition then used dynamic time warping with local distances equal to values from output nodes. This provides good discrimination from the neural net and integration over time from the DTW algorithm. Perfect recognition performance was provided for recognition of 100 tokens from one talker.

Bourlard and Wellekens (1987) also used a multilayer perceptron with contextual input and DTW to recognize words from a more difficult 919-word talker-dependent continuous-speech task. The net covered an input context of 9 frames, used one of 132 vectors to quantize each frame, had 50 or 200 hidden nodes, and had 50 output nodes corresponding to 50 German phonemes.

Study  Approach  Comments
Bourlard and MLP Provides Allophone Good Performance on
Wellekens  Distance Scores  918-Word, Talker-
(1987)  for DTW Recognizer  Dependent, Contin-

uous-Speech Task

Burr (1988a) MLP Classifier After  Tested on Single-
Energy-Based DTW  Talker E-Set

Huang and  Second-Stage MLP  Improved Performance
Lippmann  Discrimination After  for “B,D,G” from TI
(1988)  HMM Recognizer  Alpha-Digit Data Base

Lippmann  “Viterbi-Net” Neural  Same Good Perform-
and Gold  Net Architecture for  ance on Large Data
(1987)  HMM Viterbi Decoder  Base as Robust HMM

Recognizer

Sakoe and  MLP Provides Distance No Hand Labeling
Iso (1987) Scores for DTW Required, Untested

Recognizer

Table 5: Studies Combining Neural Net and Conventional Approaches.

This net was trained using 100 hand-segmented sentences and tested on 188 other sentences containing roughly 7300 phonemes. The phoneme error rate was 41.6% with 50 hidden nodes and 37% with 200 hidden nodes. These error rates were both lower than the 47.5% error rate provided by a simple discrete-observation HMM recognizer with duration modeling and one probability histogram per phoneme. Bourlard and Wellekens suggested that performance could be improved and the need for hand-segmented training data could be eliminated by embedding multilayer perceptron back-propagation training in an iterative Viterbi-like training loop. This loop could progressively improve segmentation for DTW or HMM recognizers. Iterative Viterbi training was not performed because the simpler single-pass training required roughly 200 hours on a SUN-3 workstation. As noted above, Bourlard and Wellekens (1988) also recently proved that recurrent neural nets could calculate local probabilities required in HMM recognizers.

Sakoe and Iso (1987) suggested a recognition structure similar to that of Bourlard and Wellekens (1987) where a multilayer perceptron with delays between input nodes computes local distance scores. They, however, do not require output nodes of the multilayer perceptron to represent sub-word units such as phonemes. Instead, a training algorithm is described that is similar to the iterative Viterbi-like training loop suggested by Bourlard and Wellekens (1987) but for continuous input parameters. No results were presented for this approach.

Burr (1988a) gave results for a recognizer where words were first aligned based on energy information to provide a fixed 20 input frames of spectral information. These inputs were fed to nine outputs representing members of the E-set (“B,C,D,E,G,P,T,V,Z”). This recognizer was trained and tested using 180 tokens from one talker. Results were nearly perfect when the initial parts of these words were oversampled.

Huang and Lippmann demonstrated how a second-stage of analysis using a multilayer perceptron could decrease the error rate of an HMM recognizer (Huang and Lippmann 1988). The Viterbi backtraces from an HMM recognizer were used to segment input speech frames and average HMM log probability scores for segments were provided as inputs to single- and multilayer perceptrons. Performance was evaluated using the letters “B,D,G” spoken by the 16 talkers in the TI alpha-digit data base. Ten training tokens per letter were used to train the HMM and neural net recognizer for each talker and the 16 other tokens were used for testing. Best performance was provided by a single-layer perceptron which almost halved the error rate.

Figure 6: A feed-forward multilayer perceptron that was used to compute allophone distance scores for a DTW recognizer.

Figure 7: A recurrent neural net called a Viterbi net that performs the calculations required in an HMM Viterbi decoder.

The error rate dropped from 7.2% errors with the HMM recognizer alone to 3.8% errors with the neural net postprocessor.

7.2 A Neural Net Architecture to Implement a Viterbi Decoder. Lippmann and Gold (1987) described a neural-net architecture called a Viterbi net that could be used to implement the Viterbi decoder used in many continuous observation HMM recognizers using analog VLSI techniques. This net is shown in figure 7. Nodes represented by open triangles correspond to nodes in a left-to-right HMM word model. Each of these triangles represents a threshold-logic node followed by a fixed delay. Small subnets in the upper part of the figure select the maximum of two inputs as described in (Lippmann et al. 1987) and subnets in the lower part sum all inputs. A temporal sequence of input vectors is presented at the input and the output is proportional to the log probability calculated by a Viterbi decoder. The structure of the Viterbi net illustrates how neural net components can be integrated to design a complex net which performs the calculations required by an important conventional algorithm.

The Viterbi net differs from the Viterbi decoding algorithm normally implemented in software and was thus evaluated using 4000 word tokens from the 9-talker 35-word Lincoln Stress-Style speech data base. Connection strengths in Viterbi nets with 15 internal nodes (one node per HMM model state) were adjusted based on parameter estimates obtained from the forward-backward algorithm. Inputs consisted of 12 mel cepstra and 13 differential mel cepstra that were updated every 10 msec. Performance was good and almost identical to that of current Robust HMM isolated-word recognizers (Lippmann and Gold 1987). The error rate was 0.56% or only 23 out of 4095 tokens wrong. One advantage an analog implementation of this net would have over digital approaches is that the frame rate could be increased to provide improved temporal resolution without requiring higher clock rates.

8 Other Nets for Pattern Sequence Recognition

In addition to the neural net models described above, other nets motivated primarily by psychological and physiological findings and by past work on associative memories have been proposed for speech recognition and pattern sequence recognition. Although some of these nets represent new approaches to the problem of pattern sequence recognition, few have been integrated into speech recognizers and none have been evaluated using large speech data bases.

8.1 Psychological Neural Net Models of Speech Perception. Three neural net models have been proposed which are primarily psychological models of speech perception (Elman and McClelland 1986; MacKay 1987; Marslen-Wilson 1987; Rumelhart et al. 1986b). The COHORT model developed by Marslen-Wilson (1987) assumes a left-to-right real-time acoustic phonetic analysis of speech as in current recognizers. It accounts for many psychophysical results in speech recognition such as the existence of a time when a word becomes unambiguously recognized (recognition point), the word frequency effect, and recognition of contextually inappropriate words. This model, however, is descriptive and is not expressed as a computational model.

Hand crafted versions of the TRACE and Interactive Activation models developed by Elman, McClelland, Rumelhart, and co-workers were tested with small speech data bases (Elman and McClelland 1986; Rumelhart et al. 1986b). These models are based on neuron-like nodes, include both feedforward and feed-back connections, use nodes with multiplicative operations, and emphasizes the benefits that can be obtained by using co-articulation information to aid in word recognition. These models are impractical because the problems of time alignment and training are not addressed and the entire network must be copied on every new time step. The Node Structure Theory developed by MacKay (1987) is a qualitative neural theory of speech recognition and production. It is similar in many ways to the above models, but considers problems related to talking rate, stuttering, internal speech, and rhythm.

8.2 Physiological Models For Temporal Pattern Recognition. Neural net approaches motivated primarily by physiological and behavioral results have also been proposed to perform some component of the time alignment task (Cohen et al. 1987; Dehaene et al. 1987; Wong and Chen 1986). Wong and Chen (1986) and Dehaene et al. (1987) describe similar models that have been tested with a small amount of speech data. These models include neurons with shunting or multiplicative nodes similar to those that have been proposed in the retina to compute direction of motion (Poggio and Koch 1987). Three neurons can be grouped to form a “synaptic triad” that can be used to recognize two component pattern sequences. This triad will have a strong output only if the modulator input goes “high” and then, a short time later, the primary input goes “high.”

Synaptic triads can be arranged in sequences and in hierarchies to recognize features, allophones and words (Wong and Chen 1986). In limited tests, hand crafted networks could recognize a small set of words spoken by one talker (Wong and Chen 1986). More interesting is a proposed technique for training such networks without supervision (Dehaene et al. 1987). If effective, this could make use of the large amount of unlabeled speech data that is available and lead to automatic creation of sub-word models. Further elaboration is necessary to describe how networks with synaptic triads could be trained and used in a recognizer.

Cohen and Grossberg proposed a network called a masking field that has

Figure 8: A model called a masking field that can be used to detect pattern sequences.

not yet been tested with speech input (Cohen and Grossberg 1987). This network is shown in figure 8. Inputs are applied to the bottom subnet which is similar to a feature map net (Kohonen et al. 1984). Typically, only one node in this subnet has a “high” output at any time. Subnet node outputs feed short-term storage nodes whose outputs decay slowly over time. Different input pattern sequences thus lead to different amplitude patterns in short term storage. For example the input C-A-T sampled at the end of the word will yield an intensity pattern in short-term storage with node C low, node A intermediate, and node T high. The input T-A-C will yield a pattern with node C high, node A intermediate, and node T low. These intensity patterns are weighted and fed to nodes in a masking field with weights adjusted to detect different patterns. The masking field is designed such that all nodes compete to be active and nodes representing longer patterns inhibit nodes representing shorter patterns. This approach can recognize short isolated pattern sequences but has difficulty recognizing patterns with repeated sub-sequences because nodes in short-term storage corresponding to those sub-sequences can become saturated. Further elaboration is necessary to describe how masking fields should be integrated into a full recognizer. Other recent studies (Jordan 1986; Stornetta et al. 1988; Tattersall et al. 1988) have also proposed using slowly-decaying nodes as short-term storage to provide history useful for pattern recognition and pattern sequence generation.

8.3 Sequential Associative Memories. A final approach to pattern sequence recognition is to build a sequential associative memory for pattern sequences as described in (Amit 1988; Buhmann and Schulten 1988; Hecht-Nielsen 1987; Kleinfield 1986; Sompolinsky and Kanter 1986). These nets extend past work on associative memories by Hopfield and Little (Hopfield 1982; Little 1974) to the case where pattern sequences instead of static patterns can be restored. Recognition in this approach corresponds to the net settling into a desired sequence of stable states, one after the other, when driven by an input temporal pattern sequence.

Dynamic associative memory models developed by Amit, Kleinfield, Sompolinsky, and Kanter (Amit 1988; Kleinfield 1986; Sompolinsky and Kanter 1986) use long and short delays on links to generate and recognize pattern sequences. Links with short delays mutually excite a small set of nodes to produce stable states. Links with long delays excite nodes in the next expected stable state. Transitions between states thus occur at predetermined times that depend on the delays in the links. A net developed by Buhmann and Schulten (1988) uses probabilistic nodes to produce sequencing behavior similar to that produced by a Markov chain. Transitions in this net occur stochastically but at some average rate. A final net described by Hecht-Nielsen (1987) is a modified version of Grossberg’s avalanche net (Grossberg 1988). The input to this net is similar in structure to Kohonen’s feature map. It differs in that nodes have different rise and fall time constants and overall network activity is controlled such that only the outputs of a few nodes are “high” at any time.

A few relatively small simulations have been performed to explore the behavior of the sequential associative memories. Simulations have demonstrated that these nets can complete pattern sequences given the first element of a sequence (Buhmann and Schulten 1988) and also perform such functions as counting the number of input patterns presented to a net (Amit 1988). Although this approach is theoretically very interesting and may be a good model of some neural processing, no tests have been performed with speech data. In addition, further work is necessary to develop training procedures and useful decoding strategies that could be applied in a complete speech recognizer.

9 Summary of Past Research

The performance of current speech recognizers is far below that of humans. Neural nets offer the potential of providing massive parallelism, adaptation, and new algorithmic approaches to speech recognition problems. Researchers are investigating:

1. New physiological-based front ends,

2. Neural net classifiers for static speech input patterns,

3. Neural nets designed specifically to classify temporal pattern sequences,

4. Combined recognizers that integrate neural net and conventional recognition approaches,

5. Neural net architectures that implement conventional algorithms, and

6. VLSI hardware neural nets that implement both neural net and conventional algorithms.

Physiological front ends have provided improved recognition accuracy in noise (Ghitza 1988; Hunt and Lefèbvre 1988) and a cochlea filter-bank that could be used in these front ends has been implemented using micro-power VLSI techniques (Lyon and Mead 1988). Many nets can compute the complex likelihood functions required by continuous-distribution recognizers and perform the vector quantization required by discrete-observation recognizers. Kohonen’s feature map algorithm (Kohonen et al. 1984) has been used successfully to vector quantize speech and preliminary VLSI hardware versions of this net have been built (Mann et al. 1988).

Multilayer perceptron networks with delays have provided excellent discrimination between small sets of difficult-to-discriminate speech inputs (Kammerer and Kupper 1988; Lang and Hinton 1988; Peeling and Moore 1987; Waibel et al. 1987; Waibel et al. 1988; Watrous 1988). Good discrimination was provided for a set of 18 consonants in varying phonetic contexts (Waibel et al. 1988), similar E-set words such as “B,D,E,V” (Lang and Hinton 1988), and digits and words from small-vocabularies (Kammerer and Kupper 1988; Peeling and Moore 1987; Watrous 1988). In some cases performance was similar to or slightly better than that provided by a more conventional HMM or DTW recognizer (Kammerer and Kupper 1988; Lang and Hinton 1988; Peeling and Moore 1987; Waibel et al. 1987; 1988). In almost all cases, a neural net approach performed as well as or slightly better than conventional approaches but provided a parallel architecture that could be used for implementation and a computationally simple and incremental training algorithm.

Approaches to the problem of scaling a network up in size to discriminate between members of a large set have been proposed and demonstrated (Waibel et al. 1988). For example, a net that classifies 18 consonants accurately was constructed from subnets trained to discriminate between smaller subsets of these consonants. Algorithms that use combined unsupervised/supervised training and provide high performance and extremely rapid training have also been demonstrated (Huang and Lippmann 1988; Kohonen et al. 1988). New training algorithms are under development (Almeida 1987; Jordan 1986; Pineda 1987; Rohwer and Forrest 1987; Watrous 1988) that can be used with recurrent networks.

Preliminary studies have explored recognizers that combine conventional and neural net approaches. Promising continuous-speech recognition results have been obtained by integrating multilayer perceptrons into a DTW recognizer (Bourlard and Wellekens 1987) and a multilayer perceptron post processor has improved the performance of an isolated-word HMM recognizer (Huang et al. 1988). Neural net architectures have also been designed for important conventional algorithms. For example, recurrent neural net architectures have been developed to implement the Viterbi decoding algorithm used in many HMM speech recognizers (Lippmann and Gold 1987) and also to compute local probabilities required in discrete-observation HMM recognizers (Bourlard and Wellekens 1988).

Many new neural net models have been proposed for recognizing temporal pattern sequences. Some are based on physiological data and attempt to model the behavior of biological nets (Dehaene et al. 1987; Cohen et al. 1987; Wong and Chen 1986) while others attempt to extend existing auto-associative networks to temporal problems (Amit 1988; Buhmann and Schulten 1988; Kleinfield 1986; Sompolinsky and Kanter 1986). New learning algorithms and net architectures will, however, be required to provide the real-time response and automatic learning of internal word and phrase models required for high-performance continuous speech recognition. This is still a major unsolved important problem in the field of neural nets.

10 Suggestions for Future Work

Further work should emphasize networks that provide rapid response and could be used with real-time speech input. They must include internal mechanisms to distinguish speech from background noise and to determine when a word has been presented. They also must operate with continuous acoustic input and not require hand marking of test speech data, long internal delays, or duplication of the network for new inputs.

Short-term research should focus on a task that current recognizers perform poorly on such as accurate recognition of difficult sets of isolated words. Such a task wouldn’t require excessive computation resources or extremely large data bases. A potential initial problem is talker-independent recognition of difficult E-set words or phonemes as in (Lang and Hinton 1988; Waibel et al. 1988). Techniques developed using small difficult vocabularies should be extended to larger vocabularies and continuous speech as soon as feasible. Efforts should focus on: developing training algorithms to construct sub-word and word models automatically without excessive supervision, developing better front-end acoustic-phonetic feature extraction, improving low-level acoustic/phonetic discrimination, integrating temporal sequence information over time, and developing more rapid training techniques. Researchers should continue integrating neural net approaches to classification with conventional approaches to training and scoring. Longerterm research on continuous-speech recognition must address the problems of developing high-level speech-understanding systems that can learn and use internal models of the world. These systems must be able to learn and use syntactic, semantic, and pragmatic constraints.

Efforts on building neural net VLSI hardware for speech recognition should also continue. The development of compact real-time speech recognizers is a major goal of neural net research. Parallel neural-net architectures should be designed to perform the computations required by successful algorithms and then these architectures should be implemented and tested. Recent developments in analog VLSI neural nets suggest that this approach has the potential to provide the high computation rates required for both front-end acoustic analysis and high-level pattern matching.

All future work should take advantage of the many speech data bases that currently exist and use results obtained with experimental HMM and DTW recognizers with these data bases as benchmarks. Descriptions of some common data bases and comments on their availability are in (Pallett 1986; Price et al. 1988). Detailed evaluations using large speech data bases are necessary to guide research and permit comparisons between alternative approaches. Results obtained on a few locally-recorded speech samples are often misleading and are not informative to other researchers.

Research should also build on the current state of knowledge in neural networks, pattern classification theory, statistics, and conventional HMM and DTW approaches to speech recognition. Researchers should become familiar with these areas and not duplicate existing work. Introductions to current HMM and DTW approaches are available in (Dixon and Martin 1979; Lee and Hon 1988; Parsons 1986; Rabiner and Juang 1986; Rabiner et al. 1978) and introductions to statistics and pattern classification are available in many books including (Duda and Hart 1973; Fukunaga 1972; Nilsson 1965).

Acknowledgments

I would like to thank members of Royal Signals and Radar Establishment including John Bridle and Roger Moore for discussions regarding the material in this paper. I would also like to thank Bill Huang and Ben Gold for interesting discussions and Carolyn for her patience.

References

Ackley, D.H., G.E. Hinton, and T.J. Sejnowski. 1985. A Learning Algorithm for

Boltzmann Machines. Cognitive Science 9, 147–160. Albus, J.S. 1981. Brain, Behavior, and Robotics. BYTE Books. Almeida, L.B. 1987. A Learning Rule for Asynchronous Perceptrons with Feedback

in a Combinatorial Environment. In: 1st International Conference on Neural Networks. IEEE, II–609.

Alspector, J. and R.B. Allen. 1987. A Neuromorphic VLSI Learning System. In: Advanced Research in VLSI: Proceedings of the 1987 Stanford Conference, ed. P Losleben, 313–349. Cambridge: MIT Press.

Amit, D.J. 1988. Neural Networks for Counting Chimes. Proceedings National

Academy of Science, USA 85, 2141–2145. Anderson, S., J. Merrill, and R. Port. 1988. Dynamic Speech Categorization With

Recurrent Networks. Technical Report 258, Department of Linguistics and Department of Computer Science, Indiana University.

Averbuch, A., L. Bahl, and R. Bakis. 1987. Experiments with the Tangora 20,000 Word Speech Recognizer. In: Proceedings IEEE International Conference on Acoustics Speech and Signal Processing, Dallax, TX, 701–704.

Bahl, L.R., P.F. Brown, P.V. De Souza, and R.L. Mercer. 1988. Modeling Acoustic Sequences of Continuous Parameters. In: Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing, New York, NY, 40– 43.

Baldi, P. and K. Hornik. 1988. Neural Networks and Principal Component Analysis: Learning from Examples Without Local Minima. Neural Networks 2, 53–58.

Beet, S.W., H.E.G. Powrie, R.K. Moore, and M.J. Tomlinson. 1988. Improved Speech Recognition Using a Reduced Auditory Representation. In: Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing, New York, NY, 75–78.

Bengio, Y. and R. De Mori. 1988. Use of Neural Networks for the Recognition of Place of Articulation. In: Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing, New York, NY, 103–106.

Bourlard, H. and Y. Kamp. 1988. Auto-Association by Multilayer Perceptrons

and Singular Value Decomposition. Biological Cybernetics 59, 291–294. Bourlard, H. and C.J. Wellekens. 1988. Links Between Markov Models and Mul-

tilayer Perceptrons. Technical Report Manuscript M-263, Phillips Research Laboratory, Brussels, Belgium.

. 1987. Speech Pattern Discrimination and Multilayer Perceptrons. Technical Report Manuscript M-211, Phillips Research Laboratory, Brussels, Belgium. Scheduled to appear in the December issue of Computer, Speech and Language.

Bridle, J. 1988. Neural Network Experience at the RSRE Speech Research Unit. ATR Workshop on Neural Networks and Parallel Distributed Processing, Osaka, Japan.

Broomhead, D.S. and D. Lowe. 1988. Radial Basis Functions, multi-variable functional interpolation and adaptive networks. Technical Report RSRE Memorandum No. 4148, Royal Speech and Radar Establishment, Malvern, Worcester, Great Britain.

Buhmann, J. and K. Schulten. 1988. Noise-Driven Temporal Association in Neural

Networks. Europhysics Letters 4, 1205–1209. Burr, D.J. 1988a. Experiments on Neural Net Recognition of Spoken and Written

Text. In: IEEE Transactions on Acoustics, Speech and Signal Processing, 36, 1162–1168.

. 1988b. Speech Recognition Experiments with Perceptrons. In: Neural Information Processing Systems, ed. D. Anderson, 144–153. New York: American Institute of Physics.

Burton, D.K., J.E. Shore, and J.T. Buck. 1985. Isolated-Word Speech Recognition Using Multisection Vector Quantization Codebooks. In: IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-33, 837–849.

Cohen, M. and S. Grossberg. 1987. Masking fields: A Massively Parallel Neural Architecture for learning, recognizing, and predicting multiple groupings of patterned data. Applied Optics 26, 1866–1891.

Cohen, M.A., S. Grossberg, and D. Stork. 1987. Recent Developments in a Neural Model of Real-Time Speech Analysis and Synthesis. In: 1st International Conference on Neural Networks, IEEE.

Cowan, J.D. and D.H. Sharp. 1988. Neural Nets and Artificial Intelligence.

Daedalus 117, 85–121. Cybenko, G. 1988. Continuous Valued Neural Networks with Two Hidden Lay-

ers are Sufficient. Technical Report, Department of Computer Science, Tufts University.

Dehaene, S., J. Changeux, and J. Nadal. 1987. Neural Networks that Learn Temporal Sequences by Selection. Proceedings National Academy Science, USA, Biophysics 84, 2727–2713.

Deng, Li and C. Daniel Geisler. 1987. A Composite Auditory Model for Processing

Speech Sounds. Journal of the Acoustical Society of America 82:6, 2001–2012. Dixon, N.R. and T.B. Martin. 1979. Automatic Speech and Speaker Recognition.

New York: IEEE Press. Doddington, G.R. and T.B. Schalk. 1981. Speech Recognition: Turning Theory

into Practice. IEEE Spectrum, 26–32. Duda, R.O. and P.E. Hart. 1973. Pattern Classification and Scene Analysis. New

York: John-Wiley & Sons. Elman, J.L. 1988. Finding Structure in Time. CRL Technical Report 8801, Uni-

versity of California, San Diego, CA. Elman, J.L. and J.L. McClelland. 1986. Exploiting Lawful Variability in the Speech Wave. In: Invariance and Variability in Speech Processes, eds. J.S. Perkell and D.H. Klatt. New Jersey: Lawrence Erlbaum.

Elman, J.L. and D. Zipser. 1987. Learning the Hidden Structure of Speech. ICS Report 8701, Institute for Cognitive Science, University of California, San Diego, La Jolla, CA.

Fallside, F., T.D. Harrison, R.W. Prager, and A.J.R. Robinson. 1988. A Comparison of Three Connectionist Models for Phoneme Recognition in Continuous Speech. ATR Workshop on Neural Networks and Parallel Distributed Processing, Osaka, Japan.

Fukunaga, K. 1972. Introduction to Statistical Pattern Recognition. New York:

Academic Press. Ghitza, O. 1988. Auditory Neural Feedback as a Basis for Speech Processing. In:

Proceedings IEEE International Conference on Acoustics Speech and Signal Processing, New York, NY, 91–94.

Gold, B. 1988. A Neural Network for Isolated Word Recognition. In: Proceedings IEEE International Conference on Acoustics Speech and Signal Processing, New York, NY, 44–47.

Greenberg, S. 1988a. The Ear as a Speech Analyzer. Journal of Phonetics 16,

139–149.

. 1988b. Special Issue on “Representation of Speech in the Auditory Periphery.” Journal of Phonetics 16.

Grossberg, S. 1988. Nonlinear Neural Networks: Principles, Mechanisms, and

Architectures. Neural Networks 1, 17–61. Hanson, S.J. and D.J. Burr. 1987. Knowledge Representation in Connectionist

Networks. Technical Report, Bell Communications Research, Morristown, New Jersey.

Harrison, T.D. and F. Fallside. 1988. A Connectionist Structure for Phoneme Recognition. Technical Report CUED/F-INFENG/TR.15, Cambridge University Engineering Department.

Hecht-Nielsen, R. 1987. Nearest Matched Filter Classification of Spatiotemporal

Patterns. Applied Optics 26, 1892–1899. Hinton, G.E. 1987. Connectionist Learning Procedures. Technical Report CMU-

CS-87-115, Carnegie Mellon University, Computer Science Department. Homma, T., L.E. Atlas, and R.J. Marks. 1988. An Artificial Neural Network for

Spatio-Temporal Bipolar Patterns: Application to Phoneme Classification. In: Neural Information Processing Systems, ed. D. Anderson, 31–40. New York: American Institute of Physics.

Hopfield, J.J. 1982. Neural Networks and Physical Systems with Emergent Collective Computational Abilities. Proceedings of the National Academy of Sciences, USA 79, 2554–2558.

Huang, W.M. and R.P. Lippmann. 1988. Neural Net and Traditional Classifiers. In: Neural Information Processing Systems, ed. D. Anderson, 387–396. New York: American Institute of Physics.

Huang, W.M., R.P. Lippmann, T. Nguyen. 1988. Neural Nets for Speech Recog-

nition. In: Conference of the Acoustical Society of America, Seattle WA. Hunt, M.J. and C. Lefèbvre. 1988. Speaker Dependent and Independent Speech

Recognition Experiments With an Auditory Model. In: Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing 1, New York, 215–218.

Irino, T. and H. Kawahara. 1988. A Study on the Speaker Independent Feature Extraction of Japanese Vowels by Neural Networks. ATR Workshop on Neural Networks and Parallel Distributed Processing, Osaka, Japan.

Jordan, M.I. 1986. Serial Order: A Parallel Distributed Processing Approach. In-

stitute for Cognitive Science Report 8604, University of California, San Diego. Kamm, C., T. Landauer, and S. Singhal. 1988. Training an Adaptive Network to

Spot Demisyllables in Continuous Speech. ATR Workshop on Neural Networks and Parallel Distributed Processing, Osaka, Japan.

Kammerer, B. and W. Kupper. 1988. Experiments for Isolated-Word Recognition with Single and Multi-Layer Perceptrons, Abstracts of 1st Annual INNS Meeting, Boston. Neural Networks 1, 302.

Kirkpatrick, S., C.D. Gelatt, and M.P. Vecchi. 1983. Optimization by Simulated

Annealing. Science 229, 671–679. Klatt, K.H. 1986. The Problem of Variability In Speech Recognition and Models

of Speech Perception. In: Invariance and Variability in Speech Processes, eds. J.S. Perkell and D.H. Klatt, 300-324. New Jersey: Lawrence Erlbaum.

Kleinfield, D. 1986. Sequential State Generation by Model Neural Networks. Pro-

ceedings National Academy Science, USA, Biophysics 83, 9469–9473. Kohonen, T. 1988. An Introduction to Neural Computing. Neural Networks 1,

3–16. Kohonen, T. 1984. Self-Organization and Associative Memory. Berlin: Springer-

Verlag. Kohonen, T., G. Barna, and R. Chrisley. 1988. Statistical Pattern Recognition

with Neural Networks: Benchmarking Studies. In: IEEE Annual International Conference on Neural Networks, San Diego, July.

Kohonen, T., K. Makisara, and T. Saramaki. 1984. Phonotopic Maps — Insightful Representation of Phonological Features for Speech Recognition. In: IEEE Proceedings of the 7th International Conference on Pattern Recognition.

Lang, K.J. and G.E. Hinton. 1988. The Development of the Time-Delay Neural Network Architecture for Speech Recognition. Technical Report CMU-CS-88-152, Carnegie-Mellon University.

Lapedes, A. and R. Farber. 1988. How Neural Nets Work. In: Neural Information Processing Systems, ed. D. Anderson, 442–456. New York: American Institute of Physics.

Lee, Kai-Fu and Hsiao-Wuen Hon. 1988. Large-Vocabulary Speaker-Independent Continuous Speech Recognition Using HMM. In: Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing 1, 123–126.

Lee, Y.C., G. Doolen, H.H. Chen, G.Z. Sun, T. Maxwell, H.Y. Lee, C.L. Giles. 1986. Machine Learning Using a Higher Order Correlation Network. Physica D, 276–306.

Leung, H.C. and V.W. Zue. 1988. Some Phonetic Recognition Experiments Using Artificial Neural Nets. In: Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing 1.

Lippmann, R.P., B. Gold, and M.L. Malpass. 1987. A Comparison of Hamming and Hopfield Neural Nets for Pattern Classification. Technical Report TR-769, MIT Lincoln Lab.

Lippmann, R.P. 1987. An Introduction to Computing with Neural Nets. IEEE

ASSP Magazine 4:2, 4–22. Lippmann, R.P. and Ben Gold. 1987. Neural Classifiers Useful for Speech Recog-

nition. In: 1st International Conference on Neural Networks, IEEE, IV–417. Little, W.A. 1974. The Existence of Persistent States in the Brain. Mathematical

Biosciences 19, 101–120. Lyon, R.F. and C. Mead. 1988. An Analog Electronic Cochlea. IEEE Transactions

on Acoustics, Speech and Signal Processing 36, 1119–1134. MacKay, D.G. 1987. The Organization of Perception and Action, New York:

Springer Verlag. Mann, J., J. Raffel, R. Lippmann, and B. Berger. 1988. A Self-Organizing Neural

Net Chip. Neural Networks for Computing Conference, Snowbird, Utah. Marslen-Wilson, W.D. 1987. Functional Parallelism in Spoken Word-Recognition.

In: Spoken Word Recognition, eds. U.H. Frauenfelder and L.K. Tyler. Cambridge, MA: MIT Press.

McDermott, E. and S. Katagiri. 1988. Phoneme Recognition Using Kohonen’s Learning Vector Quantization. ATR Workshop on Neural Networks and Parallel Distributed Processing, Osaka, Japan.

Moody, J. 1988. Speedy Alternatives to Back Propagation. Neural Networks for

Computing Conference, Snowbird, Utah. Moody, J. and C. Darken. 1988. Learning with Localized Receptive Fields. Techni-

cal Report YALEU/DCS/RR-649, Yale Computer Science Department, New Haven, CT.

Naylor, J. and K.P. Li. 1988. Analysis of a Neural Network Algorithm for Vector Quantization of Speech Parameters, Abstracts of 1st Annual INNS Meeting, Boston. Neural Networks 1, 310.

Nilsson, Nils J. 1965. Learning Machines. New York: McGraw Hill. Niranjan, M. and F. Fallside. 1988. Neural Networks and Radial Basis Functions

in Classifying Static Speech Patterns. Technical Report CUED/F-INFENG/TR 22, Cambridge University Engineering Department.

Omohundro, S.M. 1987. Efficient Algorithms with Neural Network Behavior.

Complex Systems 1, 273–347. Pallett, D.S. 1986. A PCM/VCR Speech Database Exchange Format. In: Pro-

ceedings IEEE International Conference on Acoustics, Speech and Signal Processing, Tokyo, Japan, 317–320.

Parsons, T. 1986. Voice and Speech Processing. New York: McGraw-Hill. Paul, D.B. 1987. A Speaker-Stress Resistant HMM Isolated Word Recognizer.

ICASSP 87, 713–716. Peeling, S.M. and R.K. Moore. 1987. Experiments in Isolated Digit Recognition

Using the Multi-Layer Perceptron. Technical Report 4073, Royal Speech and Radar Establishment, Malvern, Worcester, Great Britain.

Peterson, Gordon E. and Harold L. Barney. 1952. Control Methods Used in a Study of Vowels. The Journal of the Acoustical Society of America 24:2, 175–84.

Pineda, F.J. 1987. Generalization of Back-Propagation to Recurrent Neural Net-

works. Physical Review Letters 59, 2229–2232. Poggio, T. and C. Koch. 1987. Synapses that Compute Motion. Scientific Amer-

ican 256, 46–52. Prager, R.W. and F. Fallside. 1987. A Comparison of the Boltzmann Machine

and the Back Propagation Network as Recognizers of Static Speech Patterns. Computer Speech and Language 2, 179–183.

Prager, R.W., T.D. Harrison, and F. Fallside. 1986. Boltzmann Machines for

Speech Recognition. Computer Speech and Language 1, 2–27. Price, P., W.M. Fisher, J. Bernstein, D.S. Pallett. 1988. The DARPA 1000-

Word Resource Management Database for Continuous Speech Recognition. In: Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing, New York 1, 651–654.

Rabiner, L.R. and B.H. Juang. 1986. An Introduction to Hidden Markov Models.

IEEE ASSP Magazine 3:1, 4–16. Rabiner, Lawrence R. and Ronald W. Schafer. 1978. Digital Processing of Speech.

New Jersey: Prentice-Hall. Raffel, J., J. Mann, R. Berger, A. Soares, and S. Gilbert. 1987. A Generic Architec-

ture for Wafer-Scale Neuromorphic Systems. In: 1st International Conference on Neural Networks, IEEE.

Robinson, A.J. and F. Fallside. 1988a. A Dynamic Connectionist Model for

Phoneme Recognition. nEuro ’88, Paris, France.

. 1988b. Static and Dynamic Error Propagation Networks with Application to Speech Coding. In: Neural Information Processing Systems, ed. D. Anderson, 632–641. New York: American Institute of Physics.

Rohwer, R. and B. Forrest. 1987. Training Time-Dependencies in Neural Net-

works. In: 1st International Conference on Neural Networks, IEEE, II–701. Rossen, M.L., L.T. Niles, G.N. Tajchman, M.A. Bush, J.A. Anderson, and S.E.

Blumstein. 1988. A Connectionist Model for Consonant-vowel Syllable Recognition. In: Proceedings IEEE International Conference on Acoustics, Speech and Signal Processing, New York, NY, 59–66.

Rumelhart, D.E., G.E. Hinton, and R.J. Williams. 1986a. Interactive Processes in Speech Perception: The TRACE Model. In: Parallel Distributed Processing: Vol. 2, Psychological and Biological Models, eds. D.E. Rumelhart and J.L. McClelland. Cambridge, MA: MIT Press.

. 1986b. Learning Internal Representations by Error Propagation. In: Parallel Distributed Processing: Vol. 1, Foundations. Cambridge, MA: MIT Press.

Sakoe, H. and K. Iso. 1987. Dynamic Neural Network — A New Speech Recognition Model Based on Dynamic Programming and Neural Network. IEICE Technical Report 87, NEC Corporation.

Seneff, S. 1988. A Joint Synchrony/Mean-Rate Model of Auditory Speech Pro-

cessing. Journal of Phonetics 16, 55–76. Servan-Schreiber, D., A. Cleeremans, and J.L. McClellan. 1988. Encoding Sequen-

tial Structure in Simple Recurrent Networks. Technical Report CMU-CS-88-183, Carnegie Mellon University.

Shamma, S. 1988. The Acoustic Features of Speech Sounds in a Model of Auditory

Processing: Vowels and Voiceless Fricatives. Journal of Phonetics 16, 77–91. Shore, J.E. and D.K. Burton. 1983. Discrete Utterance Speech Recognition With-

out Time Alignment. IEEE Transactions on Information Theory IT-29, 473– 491.

Sompolinsky, H. and I. Kanter. 1986. Temporal Association in Asymmetrical

Neural Networks. Physical Review Letters 57, 2861–2864. Stornetta, W.S., T. Hogg, and B.A. Huberman. 1988. A Dynamical Approach

to Temporal Pattern Processing. In: Neural Information Processing Systems, ed. D. Anderson, 750–759. New York: American Institute of Physics.

Tank, D. and J.J. Hopfield. 1987. Concentrating Information in Time: Analog Neural Networks with Applications to Speech Recognition Problems. In: 1st International Conference on Neural Networks, IEEE.

Tattersall, G.D., P.W. Linford, and R. Linggard. 1988. Neural Arrays for Speech

Recognition. British Telecommunications Technology Journal 6, 140–163. Unnikrishnan, K.P., J.J. Hopfield, and D.W. Tank. 1988. Learning Time-delayed

Connections in a Speech Recognition Circuit. Neural Networks for Computing Conference, Snowbird, Utah.

Waibel, Alex, T. Hanazawa, G. Hinton, K. Shikano, and K. Lang. 1987. Phoneme Recognition Using Time-Delay Neural Networks. Technical Report TR-1-006, ATR Interpreting Telephony Research Laboratories, Japan. Scheduled to appear in March 1989 issue of IEEE Transactions on Acoustics Speech and Signal Processing.

Waibel, Alex, H. Sawai, and K. Shikano. 1988. Modularity and Scaling in Large Phonemic Neural Nets. Technical Report TR-I-0034, ATR Interpreting Telephony Research Laboratories, Japan.

Watrous, R.L. 1988. Speech Recognition Using Connectionist Networks. Ph.D

thesis, University of Pennsylvania.

. 1986. Learning Algorithms for Connectionist Networks: Applied Gradient Methods of Nonlinear Optimization. Technical Report MS-CIS-87-51, Linc Lab 72, University of Pennsylvania.

Watrous, R.L. and Lokendra Shastri. 1987. Learning Phonetic Features using Connectionist Networks: An Experiment in Speech Recognition. In: 1st International Conference on Neural Networks, IEEE, IV–381.

Wong, M.K. and H.W. Chen. 1986. Toward a Massively Parallel System for Word Recognition. In: Proceedings IEEE International Conference on Acoustics Speech and Signal Processing, 37.4.1–37.4.4.

Received 10 November; accepted 14 November 1988.

Communicated by Richard Lippmann

Modular Construction of Time-Delay Neural Networks for Speech Recognition

Alex Waibel

Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA and ATR Interpreting Telephony Research Laboratories, Twin 21 MiD Tower, Osaka, 540, Japan

Several strategies are described that overcome limitations of basic network models as steps towards the design of large connectionist speech recognition systems. The two major areas of concern are the problem of time and the problem of scaling. Speech signals continuously vary over time and encode and transmit enormous amounts of human knowledge. To decode these signals, neural networks must be able to use appropriate representations of time and it must be possible to extend these nets to almost arbitrary sizes and complexity within finite resources. The problem of time is addressed by the development of a Time-Delay Neural Network, the problem of scaling by Modularity and Incremental Design of large nets based on smaller subcomponent nets. It is shown that small networks trained to perform limited tasks develop time invariant, hidden abstractions that can subsequently be exploited to train larger, more complex nets efficiently. Using these techniques, phoneme recognition networks of increasing complexity can be constructed that all achieve superior recognition performance.

1 Introduction

Numerous studies have recently demonstrated powerful pattern recognition capabilities emerging from connectionist models or “artificial neural networks” (Rumelhart and McClelland 1986; Lippmann 1987). Most are trained on mere presentations of suitable sets of input/output training data pairs. Most commonly these networks learn to perform tasks by effective use of hidden units as intermediate abstractions or decisions in an attempt to create complex, non-linear, decision functions. While these properties are indeed elegant and useful, they are, in their most simple form, not easily applicable to decoding human speech.

2 Temporal Processing

One problem in speech recognition is the problem of time. A human speech signal is produced by moving the articulators towards target positions that characterize a particular sound. Since these articulatory motions are subject to physical constraints, they commonly don’t reach clean identifiable phonetic targets and hence describe trajectories or signatures rather than a sequence of well defined phonetic units. Properly representing and capturing the dynamic motion of such signatures, rather than trying to classify momentary snapshots of sounds, must therefore be a goal for suitable models of speech.

Another consequence of the dynamic nature of speech is the general absence of any unambiguous acoustic cue that indicates when a particular sound occurs. As a solution to this problem, segmentation algorithms have been proposed that presegment the signal before classification is carried out. Segmentation, however, is an errorful classification problem in itself and, when in error, sets up subsequent recognition procedures for recognition failure. To overcome this problem, a suitable model of speech should instead simply scan the input for useful acoustic clues and base its overall decision on the sequence and co-occurrence of a sufficient set of detected lower level clues. This then presumes the existence of translation invariant feature detectors, i.e., detectors that recognize an acoustic event independent of its precise location in time.

A “Time Delay Neural Network” (TDNN) (Lang 1987; Waibel et al. 1987) possesses both of these properties. It consists of TDNN-units that, in addition to computing the weighted sum of their current input features, also consider the history of these features. This is done by introducing varying delays on each of the inputs and processing (weighting) each of these delayed versions of a feature with a separate weight. In this fashion each unit can learn the dynamic properties of a set of moving inputs. The second property, “translation invariance” is implemented by TDNN-units that scan an input token over time, in search of important local acoustic clues, instead of applying one large network to the entire input pattern. Translation invariant learning in these units is achieved by forcing the network to develop useful hidden units regardless of position in the utterance. In our implementation this was done by linking the weights of time shifted instantiations of the net during a scan through the input token (thus removing relative timing information). Figure 1 illustrates a TDNN trained to perform the discrimination task between the voiced stop consonants /b, d, g/ (Waibel et al. 1987) for a more detailed description of its operation).

The three-category TDNN shown here (Fig. 1) has been evaluated over a large number of phonetic tokens (/b,d,g/). These tokens were generated by extracting the 150 msec intervals around pertinent phonemes from a phonetically handlabeled, large vocabulary database of isolated Japanese utterances (Waibel et al. 1987). While isolated pronunciation provided relatively well articulated tokens, the data nevertheless included significant variabil-

Figure 1: The TDNN architecture (input: “BA”). Eight hidden units in hidden layer 1 are fully interconnected with a set of 16 spectral coefficients and two delayed versions illustrated by the window over 48 input units. Each of these eight units in hidden layer 1 produces patterns of activation as the window moves through input speech. A five frame window scanning these activation patterns over time then activates each of three units in hidden layer 2. These activations over time in turn are then integrated into one single output decision. Note that the final decision is based on the combined acoustic evidence, independent of where in the given input interval (15 frames or 150 msecs) the /b, d or g/ actually occurred.

ity due to different phonetic contexts (e.g., “DO” vs. “DI”) and position in the utterance. Recognition experiments with three different male speakers showed that discrimination scores between 97.5% and 99.1% could be obtained.^{1} These scores compare favorably with those obtained using several standard implementations of Hidden Markov Model speech recognition algorithms (Waibel et al. 1987).

To understand the operation of the TDNNs, the weights and activation patterns of trained /b,d,g/-nets have been extensively evaluated (Waibel et al. 1987). Several interesting properties were observed:

1. The TDNNs developed linguistically plausible features in the hidden units, such as movement detectors for first and second formants, segment boundary detectors, etc.

2. The TDNN has developed alternate internal representations that can link quite different acoustic realizations to the same higher level concept (here: phoneme). This is possible due to the multilayer arrangement used.

3. The hidden units fire in synchrony with detected lower layer events. These units therefore operate independent of precise time alignment or segmentation and could lead to translation invariant phoneme recognition.

Our results suggest that the TDNN has most of the desirable properties needed for robust speech recognition performance.

3 The Problem of Scaling

Encouraged by the good performance and the desirable properties of the model, we wanted to extend TDNNs to the design of large scale connectionist speech recognition systems. Some simple preliminary considerations, however, raise serious questions about the extendibility of connectionist design: Is it feasible, within limited resources and time, to build and train ever larger neural networks? Is it possible to add new knowledge to existing networks? With speech being one of the most complex and all encompassing human cognitive abilities, this question of scaling must be addressed.

As a first step, let us consider the problem of extending the scope of our networks from tackling the three category task of all voiced stops (/b,d,g/) to the task of dealing with all stop consonants (/b,d,g,p,t,k/). The first row in table 1 shows the recognition scores of two individually trained three category nets, one trained on the voiced stop consonant discrimination task (/b,d,g/) and the other on the voiceless stop consonant discrimination task (/p,t,k/). A naive attempt of combining these two nets by simply choosing the maximally activated output unit from these two separately trained nets

1All recognition scores in this paper were obtained from evaluation on test data that was not included in training.

Method  bdg  ptk bdgptk
Individual TDNNs  98.3% 98.7%
TDNN: Max. Activation  60.5%
Retrain BDGPTK  98.3%
Retrain Combined Higher Layers  98.1%
Retrain with V/UV-units  98.4%
Retrain with Glue  98.4%
All-net Fine Tuning  98.6%

Table 1: From /b,d,g/ to /b,d,g,p,t,k/; Modular Scaling Methods.

resulted in failure as seen by the low recognition score (60.5%) in the second row. This is to be expected, since neither network was trained using other phonetic categories, and independent output decisions minimize the error for only small subsets of the task. A larger network (/b,d,g,p,t,k/-net) with six output units was therefore trained. Twenty hidden units (instead of eight) were used in Hidden layer 1 and six in hidden layer 2. Good performance could now be achieved (98.3%), but significantly more processing had to be expended to train this larger net. While task size was only doubled, the number of connections to be trained actually tripled. To make matters worse, more training data is generally needed to achieve good generalization in larger networks and the search complexity in a higher dimensional weight space increases dramatically as well. Even without increasing the number of training tokens in proportion to the number of connections, the complete /b,d,g,p,t,k/-net training run still required 18 days on a 4-processor Alliant supermini and had to be restarted several times before an acceptable solution had been found. The original /b,d,g/-net, by comparison, took only three days. It is clear that learning time increases more than linearly with task size, not to mention practical limitations such as available training data and computational capabilities. In summary, the dilemma between performance and resource limitations must be addressed if Neural Networks are to be applied to large real world tasks.

Our proposed solutions are based on three observations:

1. Networks trained to perform a smaller task may not produce outputs that are useful for solving a more complex task, but the knowledge and internal abstractions developed in the process may indeed be valuable.

2. Learning complex concepts in (developmental) stages based on previously learned knowledge is a plausible model of human learning and should be applied in connectionist systems.

3. To increase competence, connectionist learning strategies should build on existing distributed knowledge rather than trying to undo, ignore or relearn such knowledge.

Four experiments have been performed:

1. The previously learned hidden abstractions from the first layer of a /b,d,g/-net and a /p,t,k/-net were frozen by keeping their connections to the input fixed. Only connections from these two hidden layers 1 to a combined hidden layer 2 and to the output layer were retrained. While only modest (a few hours of) additional training was necessary at the higher layers, the recognition performance (98.1%) was found to be

Figure 2: Combination of a /b,d,g/-net and a /p,t,k/-net using 4 additional units in hidden layer 1 as free “Connectionist Glue.”

almost as good as for the monolithically trained /b,d,g,p,t,k/-net (see table 1). The small difference in performance might have been caused by the absence of features needed to merge the two subnets (here, for example, the voicing feature distinguishing voiced from voiceless stops).

2. Hidden features from hidden layer 1 are fixed as in the previous experiment, but four additional class-distinctive features are incorporated at the first hidden layer. These four units were excised from a net that was exclusively trained to perform voiced/unvoiced discrimination. The voiced/unvoiced net could be trained in little more than one day and combination training at the higher layers was accomplished in a few hours. A high recognition rate of 98.4% was achieved.

3. The hidden units from hidden layer 1 are fixed as before, and four additional free units are incorporated. These free units are called connectionist glue, since they are intended to fit or glue together two distinct, previously trained nets. This network is shown in figure 2. The four glue units can be seen to have free connections to the input that are trained along with the higher layer combinations. In this fashion they can discover additional features that are needed to accurately perform the larger task. In addition to training the original /b,d,g/- and /p,t,k/-nets, combination training using glue units was accomplished in two days. The resulting net achieved a recognition rate of 98.4%.

4. All-net fine tuning was performed on the previous network. Here, all connections of the entire net were freed once again for several hours of learning to perform small additional weight adjustments. While each of these learning iterations was indeed very slow, only few iterations were needed to fine tune the entire network for best performance of 98.6%.

Only modest additional training beyond that required to train the subcomponent nets was necessary in these experiments. Performance, however, was as good or better than that provided by a monolithically trained net and as high as the performance of the original smaller subcomponent nets.

4 Conclusion

We have described connectionist networks with delays that can represent the dynamic nature of speech and demonstrated techniques to scale these networks up in size for increasingly large recognition tasks. Our results suggest that it is possible to train larger neural nets in a modular, incremental fashion from smaller subcomponent nets without loss in recognition performance. These techniques have been applied successfully to the design of neural networks capable of discriminating all consonants in spoken isolated utterances (Waibel et al. 1988). With recognition rates of 96%, these nets were found to compare very favorably (Waibel et al. 1988) with competing recognition techniques in use today.

Acknowledgments

The author would like to acknowledge his collaborators: Toshiyuki Hanazawa, Geoffrey Hinton, Kevin Lang, Hidefumi Sawai, and Kiyohiro Shikano, for their contributions to the work described in this paper. This research would also not have been possible without the enthusiastic support of Akira Kurematsu, President of ATR Interpreting Telephony Research Laboratories.

References

Lang, K. 1987. Connectionist Speech Recognition. Ph.D thesis proposal, Carnegie

Mellon University. Lippmann, R.P. 1987. An Introduction to Computing with Neural Nets. IEEE

ASSP Magazine, 4–22. Rumelhart, D.E. and J.L. McClelland. 1986. Parallel Distributed Processing;

Explorations in the Microstructure of Cognition. Cambridge, MA: MIT Press. Waibel, A., T. Hanazawa, G. Hinton, K. Shikano, and K. Lang. 1987. Phoneme

Recognition Using Time-Delay Neural Networks. Technical Report TR-1-0006, ART Interpreting Telephony Research Laboratories. Also scheduled to appear in IEEE Transactions on Acoustics, Speech and Signal Processing, March 1989.

Waibel, A., H. Sawai, and K. Shikano. 1988. Modularity and Scaling in Large Phonemic Neural Networks. Technical Report TR-I-0034, ATR Interpreting Telephony Research Laboratories; IEEE Transactions on Acoustics, Speech and Signal Processing, to appear.

Received 6 November; accepted 8 December 1988.

Communicated by Carver Mead

Criteria for Robust Stability In A Class Of Lateral Inhibition Networks Coupled Through Resistive Grids

John L. Wyatt, Jr. David L. Standley

Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139, USA

In the analog VLSI implementation of neural systems, it is sometimes convenient to build lateral inhibition networks by using a locally connected on-chip resistive grid to interconnect active elements. A serious problem of unwanted spontaneous oscillation often arises with these circuits and renders them unusable in practice. This paper reports on criteria that guarantee these and certain other systems will be stable, even though the values of designed elements in the resistive grid may be imprecise and the location and values of parasitic elements may be unknown. The method is based on a rigorous, somewhat novel mathematical analysis using Tellegen’s theorem (Penfield et al. 1970) from electrical circuits and the idea of a Popov multiplier (Vidyasagar 1978; Desoer and Vidyasagar 1975) from control theory. The criteria are local in that no overall analysis of the interconnected system is required for their use, empirical in that they involve only measurable frequency response data on the individual cells, and robust in that they are insensitive to network topology and to unmodelled parasitic resistances and capacitances in the interconnect network. Certain results are robust in the additional sense that specified nonlinear elements in the grid do not affect the stability criteria. The results are designed to be applicable, with further development, to complex and incompletely modelled living neural systems.

1 Introduction

In the VLSI implementation of lateral inhibition and certain other types of networks, active cells are locally interconnected through an on-chip resistive grid. Linear resistors fabricated in, e.g., polysilicon, could yield a very compact realization, and nonlinear resistive grids, made from MOS transistors, have been found useful for image segmentation (Hutchinson et al. 1988). Networks of this type can be divided into two classes: feedback systems and feedforward-only systems. In the feedforward case one set of amplifiers imposes signal voltages or currents on the grid and another set reads out the resulting response for subsequent processing, while the same amplifiers both “write to” the grid and “read from” it in a feedback arrangement. Feedforward networks of this type are inherently stable, but feedback networks need not be.

A practical example is one of Mahowald and Mead’s retina chips (Mead and Mahowald 1988; Mead 1988) that achieve edge enhancement by means of lateral inhibition through a resistive grid. Figure 1a shows a single cell in an earlier version of this chip, and figure 1b illustrates the network of interconnected cells. Experiment has shown that the individual cells in this system are open-circuit stable and remain stable when the output of amplifier #2 is connected to a voltage source through a resistor, but the interconnected system oscillates so badly that the earlier design is scarcely usable^{1} (Mahowald and Mead 1988). Such oscillations can readily occur in most resistive grid circuits with active elements and feedback, even when each individual cell is quite stable. Analysis of the conditions of instability by conventional methods appears hopeless, since the number of simultaneously active feedback loops is enormous.

This paper reports a practical design approach that rigorously guarantees such a system will be stable if the active cells meet certain criteria. The work begins with the naivé observation that the system would be stable if we could design each individual cell so that, although internally active, it acts like a passive system as seen from the resistive grid. The design goal in that case would be that each cell’s output impedance should be a positive-real (Vidyasagar 1978; Desoer and Vidyasagar 1975; Anderson and Vongpanitlerd 1973) function. This is sometimes possible in practice; we will show that the original network in figure 1a would satisfy this condition in the absence of certain parasitic elements. Furthermore, it is a condition one can verify experimentally by frequency-response measurements.

It is obvious that a collection of cells that appear passive at their terminals will form a stable system when interconnected through a passive medium such as a resistive grid, and that the stability of such a system is robust to perturbations by passive parasitic elements in the network. The work reported here goes beyond that observation to provide (i) a demonstration that the passivity or positive-real condition is much stronger than we actually need and that weaker conditions, more easily achieved in practice, suffice to guarantee robust stability of the linear active network model, and (ii) an extension of the analysis to the nonlinear domain that furthermore rules out sustained large-signal oscillations under certain conditions. A key feature of the integrated circuit environment that makes these results applicable is the almost total absence of on-chip inductance. While the cells can appear

1The later design reported in (Mead and Mahowald 1988) avoids stability problems altogether, at a small cost in performance, by redesigning the circuits to passively sense the grid voltage in a “feedforward” style as described above.

Figure 1: (a) This photoreceptor and signal processor circuit, using two MOS amplifiers, realizes spatial lateral inhibition and temporal sharpening by communicating with similar cells through a resistive grid. The resistors will often be nonlinear by design. (b) Interconnection of cells through a hexagonal resistive grid. Cells are drawn as 2-terminal elements with the power supply and signal output lines suppressed. The voltage on the capacitor in any given cell is affected both by the local light intensity incident on that cell and by the capacitor voltages on neighboring cells of identical design. The necessary ingredients for instability — active elements and signal feedback — are both present in this system. (c) Grid resistors with a nonlinear characteristic of the form i = tanh(v) can be useful in image segmentation (Hutchinson et al. 1988).

inductive, as in figure 3c, the absence of inductance in our grid models makes these theorems possible.

Note that these results do not apply directly to networks created by interconnecting neuron-like elements, as conventionally described in the literature on artificial neural systems. The “neurons” in, e.g., a Hopfield network (Hopfield 1984) are unilateral 2-port elements in which the input and output are both voltage signals. The input voltage uniquely and instantaneously determines the output voltage of such a neuron model, but the output can only affect the input via the resistive grid. In contrast, the cells in our system are 1-port electrical elements (temporarily ignoring the optical input channel) in which the port voltage and port current are the two relevant signals, and each signal affects the other through the cell’s internal dynamics (modeled as a Thevénin equivalent impedance) as well as through the grid’s response.

It is apparent that uncontrolled spontaneous oscillation is a potential problem in living neural systems, which typically also consist of active elements arranged in feedback loops. Biological systems have surely solved the same problem we attack in this paper. It is reasonable to believe that stability has strongly constrained the set of network configurations nature has produced. Whatever Nature’s solutions may be, we suspect they have at least three features in common with the ones proposed here: (1) robustness in the face of wide component variation and the presence of parasitic network elements, (2) reliance on empirical data rather than anything we would recognize as a theory or analytic method, (3) stability strategies based on predominantly local information available to each network element.

Several reports on this work have appeared and will appear in (Wyatt and Standley 1988; Standley 1989; Standley and Wyatt 1989; 1988a; 1988b) during its development; a longer tutorial exposition will be given in the second printing of (Mead 1988).

2 The Linear Theory

2.1 Terminology. The output impedance of a linear system is a measure of the voltage response due to a change in output current while the input (light intensity in this case) is held constant. This standard electrical engineering concept will play a key role here. Figure 2a illustrates one experimental method for measuring the output impedance, and figure 2b is a standard graphical representation of an impedance, known as a Nyquist diagram. Similar plots have been used in experimental physiology (Cole 1932).

In the context of this work, an impedance is said to be positive-real (Vidyasagar 1978, Desoer and Vidyasagar 1975, Anderson and Vongpanitlerd 1973) if it is stable (i.e., has no poles or zeroes in the right-half plane) and its Nyquist diagram lies entirely in the right-half plane (i.e., in the language of complex numbers, Re{Z(iω)} ≥ 0 for all purely sinusoidal frequencies ω). Figure 2a is an example, while the system represented in figure 4 is stable but not positive-real.

Figure 2: (a) Simplified experimental measurement of the output impedance of a cell. A sinusoidal current i = Acos(ωt) is injected into the output and the voltage response v = Bcos(ωt + ϕ) is measured. The impedance, which has magnitude B/A and phase ϕ, is typically treated as a complex number Z(iω) that depends on the frequency ω. (b) Example of the Nyquist diagram of an impedance. This is a plot in the complex plane of the value of the impedance, measured or calculated at purely sinusoidal frequencies, ranging from zero upward toward infinity. It is not essential to think of Nyquist diagrams as representing complex numbers: they are simply polar plots in which radius represents impedance magnitude and angle to the horizontal axis represents phase. The diagram shown here is the Nyquist plot of the positive-real impedance in equation (2.1).

Figure 3: (a) Elementary model for an MOS amplifier. These amplifiers have a relatively high output resistance, which is determined by a bias setting (not shown). (b) Linearity allows this simplification of the network topology for the circuit in figure 1a without loss of information relevant to stability. The capacitor in figure 1a has been absorbed into the output capacitance of amp #2. (c) Passive network realization of the output impedance given in equation (2.1) for the network in (b).

A deep link between positive-real functions, physical networks and passivity is established by the classical result in linear circuit theory which states that H(s) is positive-real if and only if it is possible to synthesize a 2-terminal network of positive linear resistors, capacitors, inductors and ideal transform-

Figure 4: Nyquist diagram of an impedance that satisfies the Popov criterion, defined as follows. A linear impedance Z(s) satisfies the Popov criterion if (1 + τs)Z(s) is positive-real for some τ > 0. The “Popov multiplier” (1 + τs) modifies the Nyquist diagram by stretching and rotating it counterclockwise for ω > 0. The impedance plotted here is active and thus is not positive-real, but the rotation due to the (1 + τs) term can make it positive-real for an appropriate value of τ. The Popov criterion is a condition on the linear elements that is weaker than passivity: active elements satisfying this criterion are shown to pose no danger of instability even when nonlinear resistors and capacitors are present in the grid.

ers that has H(s) as its driving-point impedance (Anderson and Vongpanitlerd 1973).

This work was originally motivated by the following linear analysis of a model for the circuit in figure 1a. For an initial approximation to the output impedance of the cell we use the elementary model shown in figure 3a for the amplifiers and simplify the circuit topology within a single cell as shown in figure 3b.

Straightforward calculations show that the output impedance is given by

Z^{−1}(s) = [g_{m_{2}} + R_{o_{2}}^{−1} + sC_{o_{2}}] + \frac{g_{m_{1}}g_{m_{2}}R_{o_{1}}}{(1 + sR_{o_{1}}C_{o_{1}})}. (2.1)

This is a positive-real impedance that could be realized by a passive network of the form shown in figure 3c, where

R_{1} = (g_{m_{2}} + R_{o_{2}}^{−1})^{−1}, R_{2} = (g_{m_{1}}g_{m_{2}}R_{o_{1}})^{−1}, and L = C_{o_{1}}/g_{m_{1}}g_{m_{2}} . (2.2)

Of course this model is oversimplified, since the circuit does oscillate. Transistor parasitics and layout parasitics cause the output impedance of the individual active cells to deviate from the form given in equations (2.1) and (2.2), and any very accurate model will necessarily be quite high order. The following theorem shows how far one can relax the positive-real condition and still guarantee that the entire network is robustly stable. It obviously applies to a much wider range of linear networks than has been discussed here.

A linear network is said to be stable if for any initial condition the transient response converges asymptotically to a constant.

Theorem 1. Consider the class of linear networks of arbitrary topology, consisting of any number of positive 2-terminal resistors and capacitors and of N lumped linear impedances Z_{n}(s), n = 1, 2, …, N, that are open- and short-circuit stable in isolation, i.e., that have no poles or zeroes in the closed right-half plane. Every such network is stable if at each frequency ω ≥ 0 there exists a phase angle θ(ω) such that 0 ≥ θ(ω) ≥ −90^{∘} and |^{}Z̸_{n}(iω)−θ(iω)| < 90^{∘}, n = 1, 2, …, N.

An equivalent statement of this last condition is that the Nyquist plot of each cell’s output impedance for ω ≥ 0 never intersects the 2nd quadrant of the complex plane (figure 4 is an example), and that no two cells’ output impedance phase angles can ever differ by as much as 180^{∘}. If all the active cells are designed identically and fabricated on the same chip, their phase angles should track fairly closely in practice, and thus this second condition is a natural one.

The theorem is intuitively reasonable and serves as a practical design goal. The assumptions guarantee that the cells cannot resonate with one another at any purely sinusoidal frequency s = jω since their phase angles can never differ by as much as 180^{∘}, and they can never resonate with the resistors and capacitors since they can never appear simultaneously active and inductive at any sinusoidal frequency. A more advanced argument (Standley and Wyatt 1989) shows that exponentially growing instabilities are also ruled out.

3 Stability Result for Networks with Nonlinear Resistors and Capacitors

The previous results for linear networks can afford some limited insight into the behavior of nonlinear networks. If a linearized model is stable, then the equilibrium point of the original nonlinear network must be locally stable. But the result in this section, in contrast, applies to the full nonlinear circuit model and allows one to conclude that in certain circumstances the network cannot oscillate or otherwise fail to converge even if the initial state is arbitrarily far from the equilibrium point. Figure 4 introduces the Popov criterion, which is the basis of the following theorem. This is the first nonlinear result of its type that requires no assumptions on the network topology.

Theorem 2. Consider any network consisting of nonlinear resistors and capacitors and linear active cells with output impedances Z_{n}(s), n = 1, 2, …, N. Suppose

(a) the nonlinear resistor and capacitor characteristics, i_{j} = g_{j}(v_{j}) and q_{k} = h_{k}(v_{k}), respectively, are monotone increasing continuously differentiable functions, and

(b) the impedances Z_{n}(s) all satisfy the Popov criterion for some common value of τ > 0.

Then the network is stable in the sense that, for any initial condition at t = 0,

∫_{0}^{∞}[ ∑_{all resistors and capacitors} i_{k}^{2}(t) ]dt < ∞  (3.1)

Acknowledgments

We sincerely thank Professor Carver Mead of Cal Tech for encouraging this work, which was supported by Defense Advanced Research Projects Agency (DARPA) Contract No. N00014-87-K-0825 and National Science Foundation (NSF) Contract No. MIP-8814612.

References

Anderson, B.D.O. and S. Vongpanitlerd. 1973. Network Analysis and Synthesis

— A Modern Systems Theory Approach, Englewood Cliffs, NJ: Prentice-Hall. Cole, K.S. 1932. Electric Phase Angle of Cell Membranes. J. General Physiology

15:6, 641–649. Desoer, C. and M. Vidyasagar. 1975. Feedback Systems: Input-Output Properties.

New York: Academic Press. Hopfield, J.J. 1984. Neurons with Graded Response have Collective Computational

Properties Like Those of Two-state Neurons. Proc. Nat’l. Acad. Sci. 81, 3088–3092.

Hutchinson, J., C. Koch, J. Luo, and C. Mead. 1988. Computing Motion Using

Analog and Binary Resistive Networks. Computer 21:3, 52–64. Mahowald, M.A. and C.A. Mead. 1988. Personal communication. Mead, C.A. 1988. Analog VLSI and Neural Systems. Addison-Wesley. Mead, C.A. and M.A. Mahowald. 1988. A Silicon Model of Early Visual Process-

ing. Neural Networks 1:1, 91–97.

Penfield, P., Jr., R. Spence, and S. Duinker. 1970. Tellegen’s Theorem and Elec-

trical Networks. Cambridge, MA: MIT Press. Standley, D.L. 1989. Design Criteria Extensions for Stable Lateral Inhibition

Networks in the Presence of Circuit Parasitics. Proc. 1989 IEEE Int. Symp. on Circuits and Systems, Portland, OR.

Standley, D.L. and J.L. Wyatt, Jr. 1989. Stability Criterion for Lateral Inhibition Networks that is Robust in the Presence of Integrated Circuit Parasitics. IEEE Trans. Circuits and Systems, to appear.

. 1988a. Stability Theorem for Lateral Inhibition Networks that is Robust in the Presence of Circuit Parasitics. Proc. IEEE Int. Conf. on Neural Networks I, San Diego, CA, 27–36.

. 1988b. Circuit Design Criteria for Stability in a Class of Lateral Inhibition Neural Networks. Proc. IEEE Conf. on Decision and Control, Austin, TX, 328–333.

Vidyasagar, M. 1978. Nonlinear Systems Analysis. Englewood Cliffs, NJ: Prentice-

Hall. Wyatt, J.L., Jr. and D.L. Standley. 1988. A Method for the Design of Stable

Lateral Inhibition Networks that is Robust in the Presence of Circuit Parasitics. In: Neural Information Processing Systems, ed. D. Anderson, American Institute of Physics, New York, 860–867.

Received 30 September; accepted 13 October 1988.

Communicated by David Mumford

Two Stages of Curve Detection Suggest Two Styles of Visual Computation

Steven W. Zucker^{†} Allan Dobbins Lee Iverson

Computer Vision and Robotics Laboratory, McGill Research Centre for Intelligent Machines, McGill University, Montréal, Québec, Canada

The problem of detecting curves in visual images arises in both computer vision and biological visual systems. Our approach integrates constraints from these two sources and suggests that there are two different stages to curve detection, the first resulting in a local description, and the second in a global one. Each stage involves a different style of computation: in the first stage, hypotheses are represented explicitly and coarsely in a fixed, preconfigured architecture; in the second stage, hypotheses are represented implicitly and more finely in a dynamically-constructed architecture. We also show how these stages could be related to physiology, specifying the earlier parts in a relatively fine-grained fashion and the later ones more coarsely.

1 Introduction

An extensive mythology has developed around curve detection. In extrapolating from orientation-selective neurons in the visual cortex (Hubel and Wiesel 1962), it is now widely held that curve detection is simply a matter of “integrating” the responses of these cells. More specifically, the mythology holds that this integration process is global, that the initial estimates are local, and that the relationship between them will become clear as a more detailed understanding of cortical circuitry is uncovered. However, this mythical process of “integration” has turned out to be elusive, the search for it has led, instead, to a series of dilemmas, and the quantity of physiological data is exploding. It is rarely clear how new details of cortical circuitry relate to different components of the curve detection problem.

We believe that this situation is typical of vision in general, and amounts to ascribing too little function to the earlier stages, and too much to the later ones. For curve detection, virtually all of the complexity is delegated to the process of “integration,” so it is not surprising that successful approaches have remained elusive. Part of the problem is that models of integrative processes have been rich in selected detail, but poor in abstract function. In the sense that it is often useful to see the forest before the trees, we submit that solutions will likely be found by considering both coarse-grained and fine-grained models, and that such models will suggest a partitioning of function whose abstraction varies with granularity. To make this point concretely, we here outline a coarse-grained solution to the curve detection problem from a computational perspective, and sketch how it could map onto physiology. The sketch is coarse enough to serve as an organizational framework, but fine enough to suggest particular physiological constraints. One of these comprises our first, coarse-grain prediction: curve detection naturally decomposes into two stages, the first in which a local description is computed, and the second in which a global description is computed. These computations are sufficiently different that we are lead to hypothesize two different styles of visual computation.

†Senior Fellow, Canadian Institute for Advanced Research.

Neural Computation 1, 56–69 (1989) \begin{matrix}c \\ ◯ \end{matrix} 1989 Massachusetts Institute of Technology

2 The Dilemma of Curve Detection

The initial measurement of orientation information is broadly tuned, which suggests the averaging necessary to counteract retinal (sensor) sampling, quantization, and noise. However, the end result of curve detection is unexpectedly precise: corners can be distinguished from arcs of high curvature, and nearby curves can be distinguished from one another to a hyperaccurate level, even though they might pass through the same receptive field.

An analogous dilemma exists for computer vision systems, even with the spectacular numerical precision of which computers are capable: quantization and noise imply smoothing, but smoothing blurs corners, endpoints, and nearby curves into confusion (Zucker 1986). At the foundation is a chickenand-egg problem: if the points through which the curve passed, together with the locations of discontinuities, were known, then the actual properties of the curve could be inferred. But initially they are not known, so any smoothing inherent in the inference process is potentially dangerous.

3 Two Stages of Curve Detection

We have discovered a computational solution to this dilemma, which involves decomposing the full problem into two stages, each of which has a rather different character. In the first stage, the local properties of the curve are computed: its trace (the set of retinotopic points through which the curve passes), its tangent (or orientation at those points), and its curvature. In the second stage, these properties are refined to create a global model of the curve. This much — proceeding from local to global — is standard; the style of the computations is not. The key to the first stage is to infer the local properties coarsely — not in fine detail — but without sacrificing reliability or robustness. Coarseness is here related to quantization, which must limit error propagation without blurring over corners. Observe that this is precisely what is lacking in the standard myth, where errors (e.g., about placing discontinuities) can have far reaching consequences. The result is a style of computation in which the different (quantized) possibilities are made explicit, and arranged in a fixed, preconfigured computational architecture that imposes no a priori ordering over them. Each distinct hypothesis, say rough orientation and curvature at every position, forms a unit in a fixed network that strongly resembles neural-network-style models. Reliability and robustness are then maintained by the network; hence the local description is not computed locally! A mapping onto orientation hypercolumns will be discussed shortly.

The second stage embodies a rather different style of computation. Now the possibilities no longer need be general, but are constrained to be in the range dictated by the first stage. Thus the architecture can be tailored to each problem—that is, constructed adaptively rather than preconfigured— and variables can be represented implicitly. With these highly focused resources, the key limitation on precision is implementation, and it need not be hampered by uncontrolled error propagation. From the outside, this constructive style of computation holds certain key properties in common with later visual areas, such as V4 and IT, where receptive field structure has been shown to vary with problem constraints (e.g., Maunsell and Newsome 1987; Moran and Desimone 1985).

4 The Model of Curve Detection

In physiological terms, neurons are said to be orientation selective if they respond differentially to stimulus (edge or line) orientation. We take this operational statement one step further by defining orientation selection to be the inference of a local description of the curve everywhere along it, and postulate orientation selection as the goal of our first stage. In the second stage, global curves are inferred through this local description. The various stages of our process are shown in figure 1, and expanded below.

4.1 Stage 1: Inferring the Tangent Field. Formally orientation selection amounts to inferring the trace of the curve, or the set of points (in the image) through which the curve passes, its (approximate) tangent and curvature at those points, and their discontinuities (Zucker 1986). We refer to such information as the tangent field, and note that, since the initial measurements are discrete, this will impose constraints on the (inferred) tangents, curvatures, and discontinuities (Parent and Zucker 1985).

This first stage of orientation selection is in turn modeled as a two step process:

Step 1.1. Initial Measurement of the local fit at each point to estimate orientation and curvature. These estimates derive from a model of simple cell receptive fields instantiated at multiple scales and orientations at each image position. However, these local measurements are inherently inaccurate (e.g., broadly tuned), so we require:

Step 1.2. Interpretation into an explicit distributed representation of tangent and curvature by establishing consistency between the local measurements. This is accomplished by modifying them according to their geometric relationships with nearby estimates.

4.2 Stage 2: Inferring a Covering of the Curve. Since the tangent is the first derivative of a curve (with respect to arc length), the global curve can be recovered as an integral through the tangent field. Such a view typically leads to sequential recovery algorithms (e.g., Kass and Witkin 1987). But these algorithms require global parameters, starting points, and some amount of topological structure (i.e., which tangent point follows which); in short, they are biologically implausible. In contrast, we propose a novel approach in which a collection of short, dynamically modifiable curves (“snakes” in computer vision; see Montanari 1971; Kass et al. 1988) move in parallel.

The key idea behind our approach is to recover the global curve by computing a covering of it; i.e., a set of objects whose union is equivalent to the original curve. The elements of the covering are unit-length dynamic splines, initially equivalent to the elements of the tangent field, but which then evolve according to a potential distribution constructed from the tangent field. The evolution takes two forms: (i) a migration in position to achieve smooth coverings; and (ii) a “growth” to triple their initial length. Furthermore, since the splines are initially independent, it is not known which should be grouped into the covering of each distinct global curve. For graphical purposes we represent this by creating each one with a different “color,” and include a second process which converts overlapping splines to the same color. In the end, then, the cover is given by a collection of overlapping splines, or short “snakes,” each of which is the same color.

Again, there are two conceptually distinct steps to Stage 2 of the algorithm (David and Zucker 1989):

Step 2.1. Constructing the Potential Distribution from the discrete tangent field. Each entry in the tangent field actually represents a discretization of the many possible curves in the world that could project onto that particular (tangent, curvature) hypothesis. Now these pieces must be put together, so consider a measure (or envelope) over all of these possible curves. Assuming the curves are continuous but not necessarily differentiable everywhere, each contribution to the potential can be modeled as a Gaussian (the Wiener measure) oriented in the direction of the tangent field entry. The full potential distribution is their pointwise sum; see figure 3.

Step 2.2. Spline Dynamics The discrete entities in the tangent field are converted into unit splines initialized in the valleys of the potential distribution. They evolve according to a variational scheme that depends on spline properties (tension and rigidity) as well as the global potential.

5 Implementing the Model

Each stage of the model has different implementation requirements. To differentiate between smooth curves, curves with corners, crossing curves and branching curves, it is necessary to represent each possible tangent (orientation) and curvature value at every possible position. Smooth curves are then represented as a single (tangent, curvature) hypothesis at each (retinotopic) trace point, corners as multiple tangents at a single point, and bifurcations as a single tangent but multiple curvatures at a single point. Orientation hypercolumns in the visual cortex are thus a natural representational substrate, with explicit representation of each possible orientation and curvature at each position. This leads to a new observation regarding discontinuities: explicit neurons to represent them are unnecessary, and leads to our first physiological prediction:

Prediction 1. Crossings, corners, and bifurcations are represented at the early processing stages by multiple neurons firing within a “hypercolumn.”

5.1 Stage 1, Step 1: Intra-Columnar Initial Measurements. We first seek a physiologically plausible mechanism for measuring orientation and curvature. Observe that an orientation-selective cortical neuron carries information about the tangent to curves as they pass through its receptive field, and an ensemble of such cells of different size carries information about how orientation is changing over it. Such differences are related to curvature (or deviation from straightness), and adding appropriate rectification leads to a model of endstopped neurons (Dobbins et al. 1987; cf. Hubel and Wiesel 1965). This model exhibits curvature-selective response at the preferred orientation, as do endstopped neurons. Thus

Prediction 2. Endstopped neurons carry the quantized representation of orientation and (non-zero) curvature at each position.

By varying the components one obtains cells selective for different ranges and signs of curvature.

Thus the initial measurements can be built up by intra-columnar local circuits, with the match to each (quantized) orientation and curvature represented explicitly as, say, firing rate in endstopped neurons. However, these measurements of orientation and curvature are broadly tuned; nearby curves are blurred together and multiple possibilities arise at many positions. Introducing further non-linearities into the initial measurements eliminates some

Figure 1: An illustration of the different stages of curve detection. In (a) we show a section of a fingerprint image; note the smooth curves and discontinuities around the “Y” in the center. (b) Graphical illustration of the initial information, or those orientation/curvature hypotheses resulting from convolutions above the noise level. (c) The discrete tangent field resulting from the relaxation process after 2 iterations; note that most of the spurious initial responses have been eliminated.

(d) Final snake positions, or coverings of the global curves. (e) The potential distribution constructed from the entries in the tangent field.

spurious responses (Zucker et al. 1988), but the broadly-tuned smearing remains. We thus seek an abstract principle by which these broadly tuned responses can be refined into crisper distributions.

5.2 Stage 1, Step 2: Inter-Columnar Iterative Refinement. Again curvature enters the model, but now as a way of expressing the relationship between nearby tangent (orientation) hypotheses. Consider an arc of a curve, and observe that tangents to this arc must conform to certain position and orientation constraints for a given amount of curvature; we refer to such constraints geometrically as co-circularity (Fig. 2a). Discretizing all continuous curves in the world that project into the columnar space of coarse (orientation, curvature) hypotheses partitions these curves into equivalence classes, examples of which are shown in figure 2b (Parent and Zucker 1985; Zucker et al. 1988). Interpreting the (orientation, curvature) hypotheses as endstopped neurons, such co-circularly-consistent relationships are what is to be expected of the firing pattern between endstopped neurons in nearby orientation hypercolumns given such a curve as stimulus. Turning this around, when such intercolumnar patterns arise from the initial measurements, a curve from one of the equivalence classes is to be expected.

Such inter-columnar interactions can be viewed physiologically as excitatory and inhibitory projections between endstopped cells at nearby positions (adjacent hypercolumns), and can be used as follows. Since curvature is a relationship between tangents at nearby positions, two tangents should support one another if and only if they agree under a curvature hypothesis, and cocircularity provides the measure of such support. In addition, two tangents that disagree with the curvature estimate should detract support from one another. Relaxation labeling provides a formal mechanism for defining such support, and for specifying how to use it (Hummel and Zucker 1983). Mathematically it amounts to gradient descent; physiologically it can be viewed as a mechanism for specifying how the response of neighboring neurons will interact. In summary:

Prediction 3. Inter-columnar interactions exist between curvature consistent (co-circular) tangent hypotheses.

Given interaction, the next question relates to precision. Earlier we hypothesized that this first stage was coarse. Both computational experiments (Zucker et al. 1988), psychophysics (Link and Zucker 1988), and the range of receptive field sizes in striate cortex (Dobbins et al. 1988) provide independent evidence about the quantization of curvature:

Prediction 4. The initial representation of curvature in the visual cortex is quantized into 5 ± 2 distinct classes; namely, straight, curved to the left a small amount, curved to the left a large amount, and similarly to the right.

Figure 2: (a) The geometric relationships necessary for defining the compatibilities between two label pairs at points i and j. (b) Compatibilities between coarse (orientation, curvature) hypotheses at nearby positions. 8 distinct orientations and 7 curvatures were represented, and 3 examples are shown. (top) The labels which give positive (left) and negative (right) support for a diagonal orientation that curves slightly left; (middle) positive and negative support for a straight curvature class; (bottom) positive and negative support for the maximum curvature class. The magnitude of the interactions varies as well, roughly as a Gaussian superimposed on these diagrams. The values were obtained by numerically solving a 6-dimensional closest point problem (Zucker et al. 1988). Physiologically these projective fields represent inter-columnar interactions. Multiplied by the original tangent receptive fields, they represent the units for building the potential distribution that guides Stage 2.

Relaxation processes can be realized iteratively, and computational experiments suggest that about 3 interations suffice (Zucker et al. 1988). At this time we can only speculate how these iterations relate to physiology, but perhaps the first iteration is carried out by a recurrent network within V1, and the subsequent iterations through the feed-forward and -back projections to extrastriate cortex (e.g., V2 or V4 in monkey). There is no doubt, however, that interactions beyond the classical receptive field abound (Allman et al. 1985).

The advantage of this style of “coarse modeling” is that a number of testable physiological hypotheses do emerge, and we are now beginning to explore them. The requirement of initial curvature estimates led to the connection with endstopping, and the current model suggests roles for intercolumnar interactions. In particular, we predict that they should be a function of position and orientation, a prediction for which some support exists (e.g. Nelson and Frost 1985) in the zero-curvature case; experiments with curved stimuli remain to be done.

5.3 Stage 2: Potential Distributions and Evolving Spline Covers. The tangent field serves as a coarse model for the curve, represented locally. The next task is to infer a smooth, global curve running through it. We perform this inference in a rather different kind of architecture, one that involves potential distributions constructed specifically for each instance. It proceeds as follows.

The potential distribution is created by adding together contributions from each element in the tangent field; see figure 3. Changing the representation from the tangent field to the potential distribution changes what is explicit and what is implicit in the representation. In Stage 1 there were discrete coarse entities; now there are smooth valleys that surround each of the global curves, with a separation between them. The “jaggies” imposed by the initial image sampling have been eliminated, and interpolation to sub-pixel resolution is viable.

To recover the curves through the valleys, imagine creating, at each tangent field entry, a small spline of unit length oriented according to the tangent and curvature estimates (Fig. 4). By construction, we know that this spline will be born in a valley of the tangent field potential distribution, so they are then permitted to migrate to both smooth out the curve and to find the true local minima. But the inference of a cover for the global curves requires that the splines overlap, so that each point on every curve is covered by at least one spline. We therefore let the splines extend in length while they migrate in position, until they each reach a prescribed length. The covering is thus composed of these extensible splines which have grown in the valleys of the tangent field potential. Their specific dynamics and properties are described more fully in (David and Zucker 1989).

It is difficult to interpret these ideas physiologically within the classical view of neurons, in which inputs are summed and transformed into an output train of action potentials. Dendrites simply support passive diffusion of

Figure 3: Illustration of how a potential distribution is constructed from tangent field entries. (a) A small number of tangents, showing the individual contributions from each one. (b) As more tangents are included, long “valleys” begin to form when the individual entries are added together. (c) The complete tangent field and potential distribution as shown in figure 1. Physiologically one might think of such potentials as being mapped onto neuronal membranes. Not shown is the possible effect of attention in gating the tangent field contributions, the smallest unit for which could correspond to a tangent field entry.

depolarization. Recently, however, a richer view of neuronal processing has emerged, with a variety of evidence pointing to active dendritic computation and dendro-dendritic interaction (Schmitt and Worden 1979). Active conductances in dendrites functionally modify the geometry, and dendro-dendritic interactions suggest that the output transformation is not uniquely mediated by the axon. Taken together, these facts imply that patterns of activity can be sustained in the dendritic arbor, and that this membrane could be the substrate of the above potential distribution computations. For this to be feasible, however, we require

Prediction 5. The mapping of the potential distribution onto the neuronal membrane implies that the retinotopic coordinates are similarly mapped (at least in open neighborhoods) onto the membrane.

The large constructed potential distributions may bear some resemblance to the large receptive fields observed in areas V4 and IT (Maunsell and Newsome 1987). While any such relationship is clearly speculative at this time, it should be noted that they have two key similarities: (i) extremely large receptive fields (potential distributions) have been created, but they maintain about the same orientation selectivity as in V1 (Desimone et al. 1985); (ii) their structure can change. We have stressed how structure is controlled by upward flowing information, but it should be modifiable by “top-down” attentional influences as well (Maunsell and Newsome 1987; Moran and Desimone 1985). Attention could easily “gate” the tangent field entries at the creation of the potential, which leads to:

Prediction 6. There exists a smallest scale of attentional control, and it corresponds (in size) to the scale of the unit potential contributions.

6 Conclusions

This paper is both constructive and speculative. On the constructive side, we have outlined a computational solution to the curve detection problem that fills the wide gulf between initial broad measurements of orientation and precise final descriptions of global curve structure. Much of the mythology that has developed around curve detection is due, we believe, to ascribing too little function to the first (measurement) stage, and too much function to the second (integration) stage. Our solution was to interpose a stable description—the tangent field—between the stages, to represent the local properties of curves (and their discontinuities). Three points emerged: (i) represent the local structure coarsely, not in fine detail; so that (ii) the different possibilities can be represented explicitly and (iii) do not assume that local properties must be computed purely locally. Once the tangent field was in place, the task for the second, global stage could then be posed, and led to the introduction of the mathematical notion of a cover to suggest parallel (and hence at least not biologically implausible) mechanisms for recovering global information. Finally, we introduced the notion of a potential distribution as the representation for mediating the local to global transition between the two stages.

The paper has also been speculative. Problems in vision are complex, and computational modeling can certainly help in understanding them. But in our view computational modeling cannot proceed without direct constraints from the biology, and modeling — like curve detection — should involve both coarse-grained and finer-grained theories. We attempted to illustrate how such constraints could be abstracted by speculating how our model could

Figure 4: Illustration of the splines in motion. Initially, each spline is born at a tangent field location, with unit length. Then, according to the potential distribution shown in figure 1e, the splines migrate in position (to find minima in the distribution) and in length, so that they overlap and fill in short gaps. At convergence, the length of each spline has tripled. Not shown is the fact that each spline is born with a different “color,” and that, as they overlap, the colors equilibrate to a unique value for the entire covering of each global curve. Also, those splines that migrate to positions unsupported by the potential distribution are eliminated at convergence. (a) Initial distribution; (b) and (c) intermediate iterations; (d) final convergence. Physiologically one might think of the spline computations as being supported by localized dendric or dendro-dendritic interactions.

map onto physiology. While much clearly remains to be done, the role for curvature at several levels now seems evident. That such roles for curvature would have emerged from more traditional neural network modeling seems doubtful.

Two different styles of computation emerged in the two stages of curve detection. Although we stressed their differences in the paper, in closing we should like to stress their similarities. Both stages enjoy formulations as variational problems, and recognizing the hierarchy of visual processing, we cannot help but postulate that the second, fine stage of curve detection may well be the first, coarse stage of shape description. The fine splines then become the coarse units of shape.

Acknowledgments

This research was sponsored by NSERC grant A4470. We thank R. Milson and especially C. David for their contributions to the second stage of this project.

References

Allman, J., F. Miezin, and McGuinness. 1985. Stimulus Specific Responses from Beyond the Classical Receptive Field: Neurophysiological Mechanisms for Local-global Comparisons in Visual Neurons. Annual Rev. Neurosci. 8, 407–430.

David, C. and S.W. Zucker. 1989. Potentials, Valleys, and Dynamic Global Coverings. Technical Report 89-1, McGill Research Center for Intelligent Machines, McGill University, Montreal.

Desimone, R., S. Schein, J. Moran, and L. Ungerleider. 1985. Contour, Color, and

Shape Analysis Beyond the Striate Cortex. Vision Research 25, 441–452. Dobbins, A., S.W. Zucker, and M.S. Cynader. 1987. Endstopping in the Visual

Cortex as a Substrate for Calculating Curvature. Nature 329, 438–441.

. 1988. Endstopping and Curvature. Technical Report 88-3, McGill Research Center for Intelligent Machines, McGill University, Montreal.

Hubel, D.H. and T.N. Wiesel. 1962. Receptive Fields, Binocular Interaction and Functional Architecture in the Cat’s Visual Cortex. J. Physiol. (London) 160, 106–154.

. 1965. Receptive Fields and Functional Architecture in Two Non-striate Visual Areas (18 and 19) of the Cat. J. Neurophysiol. 28, 229–89.

Hummel, R. and S.W. Zucker. 1983. On the Foundations of Relaxation Labeling Processes. IEEE Transactions on Pattern Analysis and Machine Intelligence 5, 267–287.

Kass, M., A. Witkin, and D. Terzopoulos. 1988. SNAKES: Active Contour Mod-

els. Int. J. Computer Vision 1, 321–332. Kass, M. and A. Witkin. 1987. Analyzing Oriented Patterns. Computer Vision

Graphics and Information Processing 37, 362–385. Link, N. and S.W. Zucker. 1988. Corner Detection in Curvilinear Dot Grouping.

Biological Cybernetics 59, 247–256. Maunsell, J. and W. Newsome. 1987. Visual Processing in Monkey Extrastriate

Cortex. Ann. Rev. Neuroscience 10, 363–401. Montanari, U. 1971. On the Optimum Detection of Curves in Noisy Pictures.

CACM 14, 335–345. Moran, J. and R. Desimone. 1985. Selective Attention Gates Visual Processing in

the Extriastriate Cortex. Science 229, 782–784.

Nelson, J.J. and B.J. Frost. 1985. Intracortical Facilitation among Co-oriented, Co-axially Aligned Simple Cells in Cat Striate Cortex. Exp. Br. Res. 61, 54–61.

Parent, P. and S.W. Zucker. 1985. Trace Inference, Curvature Consistency, and Curve Detection. CVaRL Technical Report CIM-86-3, McGill University. IEEE Transactions on Pattern Analysis and Machine Intelligence, in press.

Schmitt, F. and F. Worden. 1979. The Neurosciences: Fourth Study Program,

Cambridge, MA: MIT Press. Zucker, S.W. 1986. The Computational Connection in Vision: Early Orientation

Selection. Behaviour Research Methods, Instruments, and Computers 18, 608– 617.

Zucker, S.W., C. David, A. Dobbins, and L. Iverson. 1988. The Organization of Curve Detection: Coarse Tangent Fields and Fine Spline Coverings. Proc. 2^{nd} Int. Conf. on Computer Vision, Tarpon Springs, Florida.

Received 14 October; accepted 23 October 1988.

Communicated by Dana Ballard

Part Segmentation for Object Recognition

Alex Pentland

Vision Sciences Group, The Media Lab, Massachusetts Institute of Technology, Room E15-410, 20 Ames Street, Cambridge, MA 02139, USA

Visual object recognition is a difficult problem that has been solved by biological visual systems. An approach to object recognition is described in which the image is segmented into parts using two simple, biologically-plausible mechanisms: a filtering operation to produce a large set of potential object “parts,” followed by a new type of network that searches among these part hypotheses to produce the simplest, most likely description of the image’s part structure.

1 Introduction

In order to recognize objects one must be able to compute a stable, canonical representation that can be used to index into memory (Binford 1971; Marr and Nishihara 1978; Hoffman and Richards 1985). The most widely accepted theory on how people recognize objects seems to be that they first segment the object into its component parts and then recognition occurs by using this part description to classify the object, perhaps by use of an associative network.

Despite the importance of object recognition, most vision research — and especially neural network research — has been aimed at understanding early visual processing. In part this focus on early vision is because the uniform, parallel operations typical of early vision are easily mapped onto neural networks, and are more easily understood than the nonhomogeneous, nonlinear processing required to segment an object into parts and then recognize it. As a consequence, the process of object recognition is little understood.

The goal of this research is to automatically recover accurate part descriptions for object recognition. I have approached this objective by developing a system that segments an imaged object into convex parts using a neural network that is similar to that described by Hopfield and Tank (Hopfield and Tank 1985), but which uses a temporally-decaying feedback loop to achieve considerably better performance. For the sake of efficiency and simplicity I have used silhouettes, obtained from grey-scale images by intensity, motion, and texture thresholding, rather than operating on the grey-scale images directly.

Figure 1: (a) Two-dimensional binary patterns used to segment silhouettes into parts. (b) Spatial structure of a receptive field corresponding to one of these binary patterns.

2 A Computational Theory of Segmentation

Many machine vision systems employ matched filters to find particular 2-D shapes in an image, typically using a multiresolution approach that allows efficient search over a wide range of scales. Thus, in machine vision, a natural way to locate the parts of a silhouetted object is to make filter patterns that cover the spectrum of possible 2-D part-shapes (as is shown in figure 1(a)), match these 2-D patterns against the silhouette, and then pick the best matching filter. If the match is sufficiently good, then we register the detection of a part whose shape is roughly that of the best-matching filter.

A biological version of this approach might use many hypercolumns each containing receptive fields with excitatory regions shaped as in figure 1. The cell with the best-matching excitatory field would be selected by introducing strong lateral inhibition within the hypercolumn in order to suppress all but the best-responding cells. This arrangement of receptive fields and within-hypercolumn inhibition produces receptive fields with oriented, center-surround spatial structure, such as is shown in figure 1(b).

The major problem with such a filtering/receptive field approach is that all such techniques incorporate a noise threshold that balances the number of false detections against the number of missed targets. Thus we will either miss many of the object’s parts because they don’t quite fit any of our 2-D patterns, or we will have a large number of false detections.

This false-alarm versus miss problem occurs in almost every image processing domain, and there are only two general approaches to overcoming the problem. The first is to improve the discriminating power of the filter so as to improve the false-alarm/miss tradeoff. The success of this approach depends upon precise characterization of the target and so is not applicable to this problem.

In the second approach, each non-zero response of a filter/receptive field is considered as an hypothesis about the object’s part structure rather than being considered as a detection. One therefore uses a very low threshold to obtain a large number of hypotheses, and then searches through them to find the “real” detections. This approach depends upon having some method of measuring the likelihood of a set of hypotheses, i.e., of measuring how good a particular segmentation into parts is as an explanation of the image data. It is this second, “best explanation” approach that I have adopted in this paper.

2.1 Global Optimization: The Likelihood Principle and Occam’s Razor. The notion that vision problems can be solved by optimizing some “goodness of fit” measure is perhaps the most powerful paradigm found in current computational research (Hopfield and Tank 1985; Ballard et al. 1983; Hummel and Zucker 1983; Poggio et al. 1985). Although heuristic measures are sometimes employed, the most attractive schemes have been based on the likelihood principle (the scientific principle that the most likely hypothesis is the best one), i.e., they have posed the problem in terms of an a priori model with unknown parameter values, and then searched for the parameter settings that maximize the likelihood of the model given the image data.

Recently it has been proven (Rissanen 1983) that one method of finding this maximum likelihood estimate is by use of the formal, informationtheoretic version of Occam’s Razor: the scientific principle that the simplest hypothesis is the best one. In information theory the simplicity or complexity of a description is measured by the number of bits (binary digits) needed to encode both the description and remaining residual noise. This new result tells us that both the likelihood principle and Occam’s Razor agree that the best description of image data is the one that provides the bitwise shortest encoding.

This method of finding the maximum likelihood estimate is particularly useful in vision problems because it gives us a simple way to produce maximum likelihood estimates using image models that are too complex for direct optimization (Leclerc 1988). In particular, to find the maximum likelihood estimate of an object’s part structure one needs only to find the shortest description of the image data in terms of parts.

2.2 A Computational Procedure. How can the shortest/most likely image description be computed? Let {H} be a set of n part hypotheses h_{i} produced by our filters/receptive fields, and let {H^{∗}} be a subset of {H} containing m hypotheses. The particular elements which comprise {H^{∗}} can be indicated by a vector x⃗ consisting of n − m zeros and m ones, with a one in slot i indicating that hypothesis h_{i} is an element of {H^{∗}}.

The presence of part hypothesis h_{i} in the set {H} indicates that a particular pattern from among those illustrated in figure 1(a) has at least a minimal correspondence to the image data at some particular image location. Let us designate the number of image pixels at which h_{i} and the image agree (have the same value) by a_{ii}, and the number of image pixels at which h_{i} and the image disagree (have different values) by e_{ii}. Then h_{i} provides an encoding of the image which saves S(h_{i}) bits as compared to simple pixel-by-pixel description of the image pixel values. The amount of this savings, in bits, is:

S(h_{i}) = k_{1}a_{ii} − k_{2}e_{ii} − k_{3}. (2.1)

where k_{1} is the average number of bits needed to specify a single image pixel value, k_{2} is the average number of bits needed to specify that a particular pixel is erroneously encoded by h_{i}, and k_{3} is the cost of specifying h_{i} itself. The ratio between k_{1} and k_{2} is our a priori estimate of the signal to noise ratio, including both image noise and noise from quantization of the set of 2-D shape patterns. The parameter k_{3} is equal to the minus log of the probability of a particular part hypothesis. By default we make k_{3} equal for all h_{i}; however, we can easily incorporate a priori knowledge about the likelihood of each h_{i} by setting k_{3} to the minus log probability associated with each h_{i}.

Equation 2.1 allows us to find the single hypothesis which provides the best image description by simply maximizing S(h_{i}) over all the hypotheses h_{i}. To find the overall maximum-likelihood/simplest description, however, we must search from among the power set of {H} to find that subset {H^{∗}} which maximizes S(x⃗). Thus we must be able to account for interactions between the various h_{i} in {H^{∗}}.

Let a_{ij} be the number of image pixels at which h_{i}, h_{j}, and the image all agree, and e_{ij} be number of image pixels at which both h_{i} and h_{j} disagree with the image. We then define a matrix A with values a_{ii} on the diagonal, and values −1/2a_{ij} for i ≠ j, and similarly a matrix E with values e_{ii} on the diagonal, and values −1/2e_{ij} for i ≠ j. Ignoring points where three or more h_{i} overlap, the savings generated by encoding the image data using {H^{∗}} (as specified by the vector x⃗) is simply

S(x⃗) = k_{1}x⃗Ax^{T} − k_{2}x⃗Ex^{T} − k_{3}x⃗x^{T} . (2.2)

Equation 2.2 can easily be extended to include overlaps between three or more parts by adding in additional terms that express these higher-order overlaps. However, these higher-order overlaps are expensive to calculate. Moreover, such high-order overlaps seem to be infrequent in real imagery. I have chosen, therefore, to assume that in the final solution that there are a negligible number of image points covered by three or more h_{i}. Note that we are not assuming that this is true of the entire set {H}, where such high-order overlaps will be common. The important consequence of this assumption is that the maximum of the savings function S(x⃗) over all x⃗ is also the maximum of equation 2.2.

The solution to equation 2.2 is straightforward when the matrix Q

Q = k_{1}A − k_{2}E − k_{3}I (2.3)

is positive (or negative) definite. Unfortunately, this is not the case in this problem. As a consequence, relaxation techniques (Hummel and Zucker 1983) such as the Hopfield-Tank network (Hopfield and Tank 1985) give a very poor solution.

I have therefore devised a new method of solution (and corresponding network) which can provide a good solution to equation 2.2. This new technique is a type of continuation method: one first picks a problem related to the original problem that can be solved, and then iteratively solves a series of problems that are progressively closer to the original problem, each time using the last solution as the starting point for the next iteration.

In the problem at hand, Q is easily solved when k_{3} is large enough, as then Q is diagonally dominant and thus negative definite. Therefore, I can obtain a globally good solution by first solving using a large k_{3}, and then — using that answer as starting point — progressively resolve using smaller and smaller values of k_{3} until the desired solution is obtained. Because k_{3} is the cost of adding a model to our description, the effect of this continuation technique is to solve for the largest, most prominent parts first, and then to progressively add in smaller and smaller parts until the entire figure is accounted for.

The neural network interpretation of this solution method is a Hopfield-Tank network placed in a feedback loop where the diagonal weights are initially quite large and decay over time until they finally reach the desired values. In each “time step” the Hopfield-Tank network stabilizes, the diagonal weights are reduced, and the network outputs are fed back into the inputs. When the diagonal weights reach their final values, the desired outputs are obtained.

It can be shown that for many well-behaved problems (for example, when the largest eigenvalues are all of one sign, with opposite-signed eigenvalues of much smaller magnitude) this feedback technique will produce an answer that is on average substantially better than that obtained by Hopfield-Tank or relaxation methods. As with relaxation techniques (Hummel and Zucker 1983), this feedback method can be applied to problems with asymmetric weights.

A biological equivalent of our solution method is to use a set of hypercolumns (each containing cells with the excitatory subfields illustrated in figure 1) that are tied together by a Hopfield-Tank network augmented by a time-decaying feedback loop. The action of this network is to suppress activity in all but a small subset of the hypercolumns. After this network has stabilized, each of the remaining active cells correspond exactly to one part of the imaged object. The characteristics of that cell’s excitatory subfield correspond to the shape of the imaged part.

3 Segmentation Examples

This technique has been tested on over two hundred synthetic images, with widely varying noise levels (Pentland 1988). In these tests the number of visible parts was correctly determined 85–95% of the time (depending on noise level), with largely obscured or very small parts accounting for almost all of the errors. Estimates of part shape were similarly accurate. The following three examples illustrate this segmentation performance.

The first example uses synthetic range data with a dynamic range of 4 bits. In this example, only 72 2-D shape patterns were employed in order to illustrate the effects of coarse quantization in both orientation and size. The intent of this example is to demonstrate that a high-quality segmentation into parts can be achieved despite coarse quantization in both orientation, size, and range values, and despite wide variation in the weights. In the remaining examples, the 2-D shape patterns shown in figure 1(a) were employed.

Figure 2(a) shows an intensity image of a CAD model; synthetic range data from this model is shown in figure 2(b). These range data were histogrammed and automatically thresholded, producing the silhouette shown in figure 2(c).

Figure 2(d) shows the operation of our new solution method. The parameter k_{3} is initially set to a large value, thus making equation 2.2 diagonally dominant. In this first step only the very largest parts are recovered, as is shown in the first frame of figure 2(d). The parameter k_{3} is then progressively reduced and the equation resolved, allowing smaller and smaller parts to be recovered. This is shown in the remaining frames of figure 2(d). This solution method therefore constructs a scale hierarchy of object parts, with the largest and most visible at the top of the hierarchy and the smallest parts on the bottom. This scale hierarchy can be useful in matching and recognition processes.

The final segmentation for this figure is shown in figure 2(e); here 3-D volumetric models have been substituted for their corresponding^{1} 2-D shapes in order to better illustrate how the silhouette was segmented into parts. The z dimension of these 3-D models is arbitrarily set equal to the smaller of the x and y dimensions. It can be seen that, apart from coarse quantization in orientation and size, the part segmentation is a good one.

1That is, for each 2-D pattern we substituted a 3-D CAD model whose outline corresponds exactly to the 2-D shape pattern.

Figure 2: (a) Intensity image of a CAD model. (b) Range image of this model.

(c) Silhouette of the range data. (d) This sequence of images illustrates how our continuation method constructs a scale-space description of part structure, first recovering only large, important parts and then recovering progressively smaller part structure. (e) Final segmentation into parts obtained using only very coarsely quantized 2-D patterns; 3-D models corresponding to recovered parts are used to illustrate the recovered structure. (f) Segmentations for a 5 : 1 ratio of the parameters k_{i}, showing that the segmentation is stable.

One important question is the stability of segmentation with respect to the parameters k_{i}. Figure 2(f) shows the results of varying the ratio of parameters k_{1}, k_{2}, and k_{3} over a range of 5 : 1. It can be seen that the part segmentation is stable, although as the relative cost of each model increases (the final value of k_{3} becomes large) small details (such as the feet) disappear.

The second example of segmenting a silhouette into parts uses a real image of a person, shown in figure 3(a). A silhouette was produced by automatic thresholding of a fractal measure of texture smoothness; this silhouette is shown in figure 3(b). The resulting segmentation into parts is shown in figure 3(c).

An example of segmenting a more complex silhouette into parts uses the Rites of Spring, a drawing by Picasso, shown in figure 3(c). The area within the box was digitized and the intensity thresholded to produce a coarse silhouette, as shown in figure 3(d). The automatic segmentation is shown in figure 3(e). It is surprising that such a good segmentation can be produced from this hand-drawn, coarsely digitized image (note that very small details, e.g., the goat’s horns, were missed because they were smaller than any of the 2-D patterns).

Figure 3: (a) Image of a person. (b) Silhouette produced by thresholding a fractal texture measure. (c) Automatic segmentation into parts. (d) The Rites of Spring, by Picasso. (e) Digitized version. (f) The automatic segmentation into parts.

4 Summary

I have described a method for segmenting 2-D images into their component parts, a critical stage of processing in many theories of object recognition. This method uses two stages: a detection stage which uses matched filters to extract hypotheses about part structure, and an optimization stage, where all hypotheses about the object’s part structure are combined into a globally optimum (i.e., simplest, most likely) explanation of the image data. The first stage is implemented by local competition among the filters illustrated in figure 1(a), and the second stage is implemented by a new type of neural network that gives substantially better answers than previously suggested optimization networks. This new network may be described as a relaxation or Hopfield-Tank network augmented by time-decaying feedback. For additional details the reader is referred to reference (Pentland 1988).

Acknowledgments

This research was made possible in part by National Science Foundation, Grant No. IRI-8719920. I wish to especially thank Yvan Leclerc for his comments, and for reviving my interest in minimal length encoding.

References

Ballard, D.H., G.E. Hinton, and T.J. Sejnowski. 1983. Parallel Visual Computa-

tion. Nature 306, 21–26. Binford, T.O. 1971. Visual Perception by Computer. Proceeding of the IEEE

Conference on Systems and Control, Miami. Hoffman, D. and W. Richards. 1985. Parts of Recognition. In: From Pixels to

Predicates, ed. A. Pentland. New Jersey: Ablex Publishing Co. Hopfield, J.J. and D.W. Tank. 1985. Neural Computation of Decisions in Opti-

mization Problems. Biological Cybernetics 52, 141–152. Hummel, R.A. and S.W. Zucker. 1983. On the Foundations of Relaxation Labeling

Processes. IEEE Transactions on Pattern Analysis and Machine Intelligence 5:3, 267–287.

Leclerc, Y. 1988. Construction Simple Stable Descriptions for Image Partitioning. Proc. DARPA Image Understanding Workshop, April 6–8, Boston, MA, 365– 382.

Marr, D. and K. Nishihara. 1978. Representation and Recognition of the Spatial Organization of Three-dimensional Shapes. Proceedings of the Royal Society– London B 200, 269–94

Pentland, A. 1988. Automatic Recovery of Deformable Part Models. Massachusetts

Institute of Technology Media Lab Vision Sciences Technical Report 104. Poggio, T., V. Torre, and C. Koch. 1985. Computational Vision and Regulariza-

tion Theory. Nature 317, 314–319. Rissanen, J. 1983. Minimum-length Description Principle. Encyclopedia of Statis-

tical Sciences 5, 523–527. New York: Wiley.

Part Segmentation for Object Recognition 79

Received 23 September; accepted 8 November 1988.

Communicated by Richard Andersen

Computing Optical Flow in the Primate Visual System

H. Taichi Wang Bimal Mathur

Science Center, Rockwell International, Thousand Oaks, CA 91360, USA

Christof Koch

Computation and Neural Systems Program, Divisions of Biology and Engineering and Applied Sciences, 216-76, California Institute of Technology, Pasadena, CA 91125, USA

Computing motion on the basis of the time-varying image intensity is a difficult problem for both artificial and biological vision systems. We show how gradient models, a well known class of motion algorithms, can be implemented within the magnocellular pathway of the primate’s visual system. Our cooperative algorithm computes optical flow in two steps. In the first stage, assumed to be located in primary visual cortex, local motion is measured while spatial integration occurs in the second stage, assumed to be located in the middle temporal area (MT). The final optical flow is extracted in this second stage using population coding, such that the velocity is represented by the vector sum of neurons coding for motion in different directions. Our theory, relating the single-cell to the perceptual level, accounts for a number of psychophysical and electrophysiological observations and illusions.

1 Introduction

In recent years, a number of theories have been advanced at both the computational and the psychophysical level, explaining aspects of biological motion perception (for a review see Ullman 1981; Nakayama 1985; Hildreth and Koch 1987). One class of motion algorithms exploit the relation between the spatial and the temporal intensity change at a particular point (Fenneman and Thompson 1979; Horn and Schunck 1981; Marr and Ullman 1981; Hildreth 1984). In this article we address in detail how these algorithms can be mapped onto neurons in striate and extrastriate primate cortex (Ballard et al. 1983).

Our neuronal implementation is derived from the most common version of the gradient algorithm, proposed within the framework of machine vision (Horn and Schunck 1981). Due to the “aperture” problem inherent in their definition of optical flow, only the component of motion along the local spatial brightness gradient can be recovered. In their formulation, optical flow is then computed by minimizing a two-part quadratic variational functional. The first term forces the final optical flow to be compatible with the locally measured motion component (“constraint line term”), while the second term imposes the constraint that the final flow field should be as smooth as possible. Such as “smoothness” or “continuity” constraint is common to most early vision algorithms.

2 A Neural Network Implementation

Commensurate with this method, and in agreement with psychophysical results (e.g. Welch 1989), our network extracts the optical flow in two stages (Fig. 1). In a preliminary stage, the time-varying image I(i, j) is projected onto the retina and relayed to cortex via two neuronal pathways providing information as to the spatial location of image features (S neurons) and temporal changes in these features (T neurons): S(i, j) = ∇^{2}G ∗ I(i, j) and T (i, j) = ∂(∇^{2}G ∗ I(i, j))/∂t, where ∗ is the convolution operator and G the 2-D Gaussian filter (Enroth-Cugell and Robson 1966; Marr and Hildreth 1980; Marr and Ullman 1981). In the first processing stage, the local motion information is represented using a set of n ON-OFF orientation- and direction-selective cells U, each with preferred direction indicated by the unit vector Θ_{k}:

U(i, j, k) = \frac{−T (i, j)∇_{k}S(i, j)}{|∇S(i, j)|^{2} + ϵ} (2.1)

where ϵ is a constant and ∇_{k} is the spatial derivative along the direction Θ_{k}. This derivative is approximated by projecting the convolved image S(i, j) onto a “simple” type receptive field, consisting of a 1 by 7 pixel positive (ON) subfield adjacent to a 1 by 7 pixel negative (OFF) subfield. The cell U responds optimally if a bar or grating oriented at right angles to Θ_{k} moves in direction Θ_{k}. Note that U is proportional to the product of a transient cell (T) with a sustained simple cell with an odd-symmetric receptive field, with an output proportional to the magnitude of local component velocity (as long as |∇_{k}S(i, j)| > ϵ). At each location i, j, n such neurons code for motion in n directions. Equation (2.1) differs from the standard gradient model in which U = −T/∇_{k}S, by including a gain control term, ϵ, such that U does not diverge if the stimulus contrast decreases to zero. ϵ is set to a fixed fraction of the square of the maximal magnitude of the gradient ∇S for all values of i, j. Our gradient-like scheme can be approximated for small enough values of the local contrast (i.e. if |∇S(i, j)|^{2} < ϵ), by −T (i, j)∇_{k}S(i, j). Under this condition, our model can be considered a second-order model, similar to the correlation or spatio-temporal energy models (Hassenstein and Reichardt 1956; Poggio and Reichardt 1973; Adelson and Bergen 1985; Watson and Ahumada 1985). We also require a set of n ON-OFF orientation- but not direction-selective neurons E, with E(i, j, k) = |∇_{k}S(i, j)|, where the absolute value ensures that these neurons only respond to the magnitude of the spatial gradient, but not to its sign.

We assume that the final optical flow field is computed in a second stage, using a population coding scheme such that the velocity is represented within a set of n′ neurons V at location i, j, each with preferred direction Θ_{k} with V(i, j) = ∑_{k=1}^{n′} V (i, j, k)Θ_{k}. Note that the response of any individual cell V (i, j, k) is not the projection of the velocity field V(i, j) onto Θ_{k}. For any given visual stimulus, the state of the V neurons is determined by minimizing the neuronal equivalent of the above mentioned variational functional. The first term, enforcing the constraint that the final optical flow should be compatible with the measured data, has the form:

L_{0} = ∑_{i,j,k}[∑_{k′} V (i, j, k′) cos(k′ − k) − U(i, j, k)]^{2}E^{2}(i, j, k), (2.2)

where cos(k′ − k) is a shorthand for the cos of the angle between Θ_{k′} and Θ_{k}. The term E^{2}(i, j, k) ensures that the local motion components U(i, j, k) only have an influence when there is an appropriate oriented local pattern; thus E^{2} prevents velocity terms incompatible with the measured data from contributing significantly to L_{0}. In order to sharpen the orientation tuning of E, we square the output of E (the orientation tuning curve of E has a half-width of about 60^{o}).

The smoothness term, minimizing the square of the first derivative of the optical flow (Horn and Schunck 1981) takes the following form:

L_{1} = ∑_{i,j,k,k′}[4V (i, j, k) − V (i − 1, j, k) − V (i + 1, j, k)  (2.3)
− V (i, j − 1, k) − V (i, j + 1, k)] × cos(k′ − k)V (i, j, k′).

Our algorithm computes the state of the V neurons that minimizes L_{0} + λL_{1} (λ is a free parameter, usually set at 10). We can always find this state by evolving V (i, j, k) on the basis of the steepest descent rule: ∂V/∂t = −∂(L_{0}+λL_{1})/∂V. Since the variational functional is quadratic in V, the right hand side in the above differential equation is linear in V. Conceptually, we can think of the coefficients of this linear equation as synaptic weights, while the left hand side can be interpreted as a capacitive term, determining the dynamics of our model neurons. In other words, the state of the V neurons evolve by summating the synaptic contribution from E, U and neighboring V neurons and updating its state accordingly. Thus, the system “relaxes” into its final and unique state. To mimic neuronal responses more accurately, the output of our model neurons S, T, E, U, and V is set to zero if the net input is negative.

Figure 1: Computing motion in neuronal networks. (a) Schematic representation of our model. The image I is projected onto the rectangular 64 by 64 retina and sent to the first processing stage via the S and T channels. A set of n = 16 ON-OFF orientation- (E) and direction-selective (U) cells code local motion in 16 different directions Θ_{k}. These cells are most likely located in layers 4Cα and 4B of V1. Neurons with overlapping receptive field positions i, j but different preferred directions Θ_{k} are arranged here in 16 parallel planes. The ON subfield of one such U cell is shown in Fig. 4a. The output of both E and U cells is relayed to a second set of 64 by 64 by 16 V cells where the final optical flow is represented via population coding V(i, j) = ∑_{k=1}^{n′} V (i, j, k)Θ_{k}, with n′ = 16. Each cell V (i, j, k) in this second stage receives input from cells E and U at location i, j as well as from neighboring neurons at different spatial locations. We assume that the V units correspond to a subpopulation of MT cells. (b) Polar plot of the median neuron (solid line) in MT of the owl monkey in response to a field of random dots moving in different directions (Baker et al. 1981). The tuning curve of one of our model V cells in response to a moving bar is superimposed (dashed line). Figure courtesy of J. Allman and S. Petersen.

3 Physiology and Psychophysics

Since the magnocellular pathway in primates is the one processing motion information (Livingstone and Hubel 1988; DeYoe and Van Essen 1988) we assume that the U and E neurons would be located in layers 4Cα and 4B of V1 (see also Hawken et al. 1988) and the V neurons in area MT, which contains a very high fraction of direction- and speed-tuned neurons (Allman and Kass 1971; Maunsell and Van Essen 1983). All 2n neurons U and E with receptive field centers at location i, j then project to the n′ MT cells V in an excitatory or inhibitory (via interneurons) manner, depending on whether the angle between the preferred direction of motion of the pre- and post-synaptic neuron is smaller or larger than |90^{o}|.^{1} Anatomically, we then predict that each MT cell receives input from V1 (or V2) cells located in all different orientation-columns. The smoothness constraint of equation (3) results in massive interconnections among neighboring V cells (Fig. 1a).

Our model can explain a number of perceptual phenomena. When two identical square gratings, oriented at a fixed angle to each other, are moved perpendicular to their orientation (Fig. 2a), human observers see the resulting plaid pattern move coherently in the direction given by the intersection of their local constraint lines (“velocity constraint combination rule”; in the case of two gratings moving at right angle at the same velocity, the resultant is the diagonal; Adelson and Movshon 1982). The response of our network to such an experiment is illustrated in figure 2: the U cells only respond to the local component of motion (component selectivity; Fig. 2b), while the V cells respond to the global motion (Fig. 2c), as can be seen by computing the vector sum over all V cells at every location (pattern selectivity; Fig. 2d). About 30% of all MT cells do respond in this manner, signaling the motion of the coherently moving plaid pattern (Movshon et al. 1985). In fact, under the conditions of rigid motion in the plane observed in Adelson and Movshon’s experiments, both their “velocity space combination rule” and the “smoothness” constraint converge to the solution perceived by human observers (for more results see Wang et al. 1989). Given the way the response of the U neurons vary with visual contrast (equation 2.1), our model predicts that if the two gratings making up the plaid pattern differ in contrast, the final pattern velocity will be biased in the direction of the component velocity of the grating with the larger contrast. Recent psychophysical experiments support this conjecture (Stone et al. 1988). It should be noted that the optical flow field is not represented explicitly within neurons in the second stage, but only implicitly, via vector addition.

Our algorithm reproduces both “motion capture” (Ramachandran and Anstis 1983; see Wang et al. 1989) and “motion coherence” (Williams and Sekuler 1984), as illustrated in figure 3. As demonstrated previously, these phenomena can be explained, at least qualitatively, by a smoothness or local

1The appropriate weight of the synaptic connection between U and V is cos(k − k′)U(k′)E^{2}(k′). Various biophysical mechanisms can implement the required multiplicative interaction as well as the synaptic power law (Koch and Poggio 1987).

Figure 2: (a) Two gratings moving towards the lower right (one at −26^{o} and one at −64^{o}), the first moving at twice the speed of the latter. The amplitude of the composite is the sum of the amplitude of the individual bars. The neuronal responses of a 12 by 12 pixel patch (outlined in (a)) is shown in the next three subpanels. (b) Response of the U neurons to this stimulus. The half wave rectified output of all 16 cells at each location is plotted in a radial coordinate system at each location as long as the response is significantly different from zero. (c) The output of the V cells using the same needle diagram representation after the network converged. (d) The resulting optical flow field, extracted from (c) via population coding, corresponding to a coherent plaid moving towards the right, similar to the perception of human observers (Adelson and Movshon 1982) as well as to the response of a subset of MT neurons in the macaque (Movshon et al. 1985). The final optical flow is within 5% of the correct flow field.

Figure 3: (a) In “motion coherence,” a cloud of dots is perceived to move in the direction of their common motion component. In this sequence, all dots have an upward velocity component, while their horizontal velocity component is random.

(b) The final velocity field only shows the motion component common to all dots. Humans observe the same phenomena (Williams and Sekuler 1984). (c) In γmotion, a dark stimulus flashed onto a homogenously lit background appears to expand (Lindemann 1922; Kofka, 1931). It will disappear with a motion of contraction. (d) Our algorithm perceives a similar expansion when a disk appears. The contour of the stimulus is projected onto the final optical flow.

rigidity constraint (Yuille and Grzywacz 1988; Bülthoff et al. 1989). Finally, γ motion, a visual illusion first reported by the Gestalt psychologists (Lindemann 1922; Kofka 1931; for a related illusion in man and fly see Bülthoff and Götz 1979), is also mimicked by our algorithm. This illusion arises from the initial velocity measurement stage and does not rely on the smoothness constraint.

Cells in area MT respond well not only to motion of a bar or grating but also to a moving random dot pattern (Albright 1984; Allman et al. 1985). Similarly, our algorithm detects a random-dot figure moving over a stationary random-dot background, as long as the spatial displacement between two consecutive frames is not too large (Fig. 4). An interesting distinction arises between direction-selective cells in V1 and MT. While the optimal orientation in V1 cells is always perpendicular to their optimal direction, this is only true for about 60% of MT cells (type I cells; Albright 1984; Rodman and Albright 1988). 30% of MT cells respond strongly to flashed bars oriented parallel to the cells’ preferred direction of motion (type II cells). If we identify our V cells with this MT subpopulation, we predict that type II cells should respond to an extended bar (or grating) moving parallel to its edge (Fig. 4).

4 Discontinuities in the Optical Flow

The major drawback of all motion algorithms is the degree of smoothness required, smearing out any discontinuities in the optical flow field, such as those arising along occluding objects or along a figure-ground boundary. It has been shown previously how this can be dealt with by introducing the concept of line processes which explicitly code for the presence of discontinuities in the motion field (Hutchinson et al. 1988; see also Poggio et al. 1988). If the spatial gradient of the optical flow between two neighboring points is larger than some threshold, the flow field “is broken”; that is the process or “neuron” coding for a motion discontinuity at that location is switched on and no smoothing occurs. If little spatial variation exists, the discontinuity remains off. The performance of the original version of the Horn and Schunck version is greatly improved using this idea (Hutchinson et al. 1988). Perceptually, it is known that the visual system uses motion to segment different parts of visual scenes (Baker and Braddick 1982; van Doorn and Koenderink 1983; Hildreth 1984). But what about the possible cellular correlate of line processes? Allman and colleagues (Allman et al. 1985) first described cells in area MT in the owl monkey whose “true” receptive field extended well beyond the classical receptive field as mapped with bar or spot stimuli. About half of all MT cells have an antagonistic direction-selective surround, such that the response of the cell to motion of a random dot display or an edge within the center of the receptive field can be modified by moving a stimulus within a very large surrounding region. The response depends on the difference in speed and direction of motion between the center and the surround, and is maximal if the surround moves at the same speed as the stimulus in the center but in the opposite direction. Thus, tantalizing hints exist as to the possible neuronal basis of motion discontinuities.

Recently, two variations of Horn and Schunck’s (1981) original algorithm have been proposed, based on computational considerations (Uras et al. 1988; Yuille and Grzywacz 1988). Both algorithms can be mapped onto the neuronal network we have proposed, with minimal changes either in the U stage

Figure 4: (a) A dark bar (outlined) is moved parallel to its orientation towards the right. Due to the aperture problem, those U neurons whose receptive field only “see” the straight elongated edges of the bar — and not the leading or trailing edges — will fail to respond to this moving stimulus, since motion remains invisible on the basis of purely local information. The ON subfield of the receptive field of a vertically oriented U cell is superimposed onto the image. (b) It is only after information has been integrated, following the smoothing process inherent in the second stage of our algorithm, that the V neurons respond to this motion. The type II cells of Albright (1984) in MT should respond to this stimulus. (c) Response of our algorithm to a random-dot figure-ground stimulus. The central 10 by 10 pixel square moved by 1 pixel toward the left. (d) Final optical flow after smoothing. The V cells detect the figure, similar to cells in MT. The contour of the translated square is projected onto the final optical flow.

(Uras et al. 1988) or by increasing the connectivity among more distant V cells (Yuille and Grzywacz 1988). It remains an open challenge to provide both psychophysical and electrophysiological evidence to evaluate the validity of these and similar schemes (e.g. Nakayama and Silverman 1988). We are currently trying to extend our model to account for the intriguing phenomena of “motion transparency,” such as when two fields of random dots moving in opposite directions are perceived to form the 3-D motion field associated with a transparent and rotating cylinder (Siegel and Andersen 1988).

Acknowledgments

We thank John Allman, David Van Essen, and Alan Yuille for many fruitful discussions and Andrew Hsu for computing the figure-ground response. Support for this research came from NSF grant EET-8700064, ONR Young Investigator Award and NSF Presidential Young Investigator Award to C.K.

References

Adelson, E.H. and J.R. Bergen. 1985. Spatio-temporal Energy Models for the

Perception of Motion. J. Opt. Soc. Am. A 2, 284–299. Adelson, E.H. and J.A. Movshon. 1982. Phenomenal Coherence of Moving Visual

Patterns. Nature 200, 523–525. Albright, T.L. 1984. Direction and Orientation Selectivity of Neurons in Visual

Area MT of the Macaque. J. Neurophysiol. 52, 1106-1130. Allman, J.M. and J.H. Kass. 1971. Representation of the Visual Field in the

Caudal Third of the Middle Temporal Gyrus of the Owl Monkey (Aotus trivirgatus). Brain Res. 31, 85–105.

Allman, J., F. Miezin, and E. McGuinness. 1985. Direction- and Velocity-specific Responses from Beyond the Classical Receptive Field in the Middle Temporal Area (MT). Perception 14, 105–126.

Ballard, D.H., G.E. Hinton, and T.J. Sejnowski. 1983. Parallel Visual Computa-

tion. Nature 306, 21–26. Baker, C.L. and O.J. Braddick. 1982. Does Segregation of Differently Moving

Areas Depend on Relative or Absolute Displacement. Vision Res. 7, 851–856. Baker, J.F., S.E. Petersen, W.T. Newsome, and J.M. Allman. 1981. Visual Re-

sponse Properties of Neurons in Four Extrastriate Visual Areas of the Owl Monkey (Aotus trivirgatus): A Quantitative Comparison of Medial, Dorsomedial, Dorsolateral, and Middle Temporal Areas. J. Neurophysiol. 45, 397–416.

Bülthoff, H.H., J.J. Little, and T. Poggio. 1989. Parallel Computation of Motion:

Computation, Psychophysics and Physiology. Nature, in press. Bülthoff, H.H. and K.G. Götz. 1979. Analogous Motion Illusion in Man and Fly.

Nature 278, 636–638. DeYoe, E.A. and D.C. Van Essen. 1988. Concurrent Processing Streams in Mon-

key Visual Cortex. Trends Neurosci. 11, 219–226. Enroth-Cugell, C. and J.G. Robson. 1966. The Contrast Sensitivity of Retinal

Ganglion Cells of the Cat. J. Physiol. (Lond.) 187, 517–552.

Fennema, C.L. and W.B. Thompson. 1979. Velocity Determination in Scenes Containing Several Moving Objects. Comput. Graph. Image Proc. 9, 301– 315.

Hassenstein, B. and W. Reichardt. 1956. Systemtheoretische Analyse der Zeit-, Reihenfolgen- und Vorzeichenauswertung bei der Bewegungsperzeption des Rüsselkäfers Chlorophanus. Z. Naturforschung 11b, 513–524.

Hildreth, E.C. 1984. The Measurement of Visual Motion. Cambridge, MA: MIT

Press. Hildreth, E.C. and C. Koch. 1987. The Analysis of Visual Motion. Ann. Rev.

Neurosci. 10, 477–53 Horn, B.K.P. and B.G. Schunck. 1981. Determining Optical Flow. Artif. Intell.

17, 185–20 Hutchinson, J., C. Koch, J. Luo, and C. Mead. 1988. Computing Motion using

Analog and Binary Resistive Networks. IEEE Computer 21, 52–61. Koch, C. and T. Poggio. 1987. Biophysics of Computation. In: Synaptic Function,

eds. G.M. Edelman, W.E. Gall, and W.M. Cowan, 637–698. New York: John Wiley.

Kofka, K. 1931. In: Handbuch der normalen und pathologischen Physiologie 12,

eds. A. Bethe et al. Berlin: Springer. Lindemann, E. 1922. Experimentelle Untersuchungen über das Enstehen und

Vergehen von Gestalten. Psych. Forsch. 2, 5–60. Livingstone, M. and D. Hubel. 1988. Segregation of Form, Color, Movement, and

Depth: Anatomy, Physiology and Perception. Science 240, 740–749. Marr, D. and E.C. Hildreth. 1980. Theory of Edge Detection. Proc. R. Soc.

Lond. B 297, 181–217. Marr, D. and S. Ullman. 1981. Directional Selectivity and its Use in Early Visual

Processing. Proc. R. Soc. Lond. B 211, 151–180. Maunsell, J.H.R. and D. Van Essen. 1983b. Functional Properties of Neurons in

Middle Temporal Visual Area of the Macaque Monkey. II. Binocular Interactions and Sensitivity to Binocular Disparity. J. Neurophysiol. 49, 1148–1167.

Movshon, J.A., E.H. Adelson, M.S. Gizzi, and W.T. Newsome. 1985. The Analysis of Moving Visual Patterns. In: Exp. Brain Res. Suppl. II: Pattern Recognition Mechanisms, eds. C. Chagas, R. Gattass, and C. Gross, 117-151. Heidelberg: Springer.

Nakayama, K. 1985. Biological Motion Processing: A Review. Vision Res. 25,

625–660. Nakayama, K. and G.H. Silverman. 1988. The Aperture Problem—II. Spatial

Integration of Velocity Information along Contours. Vision Res. 28, 747–75 Poggio, T., E.B. Gamble, and J.J. Little. 1988. Parallel Integration of Visual

Modules. Science 242 337–340. Poggio, T. and W. Reichardt. 1973. Considerations on Models of Movement

Detection. Kybernetik 13, 223–227. Ramachandran, V.S. and S.M. Anstis. 1983. Displacement Threshold for Coherent

Apparent Motion Motion in Random-dot Patterns. Vision Res. 12, 1719– 1724.

Rodman, H. and T. Albright. 1989. Single-unit Analysis of Pattern-motion Selective Properties in the Middle Temporal Area (MT). Exp. Brain Res., in press.

Siegel, R.M. and R.A. Andersen. 1988. Perception of Three Dimensional Structure

from Motion in Monkey and Man. Nature 331, 259–261. Stone, L.S., J.B. Mulligan, and A.B. Watson. 1988. Neural Determination of

the Direction of Motion: Contrast Affects the Perceived Direction of Motion. Neurosci. Abstr. 14, 502.5.

Ullman, S. 1981. Analysis of Visual Motion by Biological and Computer Systems.

IEEE Computer 14, 57–69. Uras, S., F. Girosi, A. Verri, and V. Torre. 1988. A Computational Approach to

Motion Perception. Biol. Cybern. 60, 79–87. van Doorn, A.J. and J.J. Koenderink. 1983. Detectability of Velocity Gradients

in Moving Random-dot Patterns. Vision Res. 23, 799–804. Wang, H.T., B. Mathur, A. Hsu, and C. Koch. 1989. Computing Optical Flow in

the Primate Visual System: Linking Computational Theory with Perception and Physiology. In: The Computing Neurone, eds. R. Durbin, C. Miall, and G. Mitchinson. Reading: Addison-Wesley. In press.

Watson, A.B. and A.J. Ahumada. 1985. Model of Human Visual-motion Sensing.

J. Opt. Soc. Am. A 2, 322–341. Welch, L. 1989. The Perception of Moving Plaids Reveals Two Motion Processing

Stages. Nature, in press. Williams, D. and R. Sekuler. 1984. Coherent Global Motion Percepts from

Stochastic Local Motions. Vision Res. 24, 55–62. Yuille, A.L. and N.M. Grzywacz. 1988. A Computational Theory for the Percep-

tion of Coherent Visual Motion. Nature 333, 71–73.

Received 28 October; accepted 6 December 1988.

A Multiple-Map Model for Pattern Classification

Alan Rojer Eric Schwartz

Computational Neuroscience Laboratory, New York University Medical Center, Courant Institute of Mathematical Sciences, New York University, New York, NY 10016, USA

A characteristic feature of vertebrate sensory cortex (and midbrain) is the existence of multiple two-dimensional map representations. Some workers have considered single-map classification (e.g. Kohonen 1984) but little work has focused on the use of multiple maps. We have constructed a multiple-map classifier, which permits abstraction of the computational properties of a multiplemap architecture. We identify three problems which characterize a multiple-map classifier: classification in two dimensions, mapping from high dimensions to two dimensions, and combination of multiple maps. We demonstrate component solutions to each of the problems, using Parzen-window density estimation in two dimensions, a generalized Fisher discriminant function for dimensionality reduction, and split/merge methods to construct a “tree of maps” for the multiple-map representation. The combination of components is modular and each component could be improved or replaced without affecting the other components. The classifier training procedure requires time linear in the number of training examples; classification time is independent of the number of training examples and requires constant space. Performance of this classifier on Fisher’s iris data, Gaussian clusters on a fivedimensional simplex, and digitized speech data is comparable to competing algorithms, such as nearest-neighbor, back-propagation and Gaussian classifiers. This work provides an example of the computational utility of multiple-map representations for classification. It is one step towards the goal of understanding why brain areas such as visual cortex utilize multiple map-like representations of the world.

1 Introduction

One of the most prominent features of the vertebrate sensory system is the use of multiple two-dimensional maps to represent the world. The observational data base for cortical maps is excellent, and this area represents one of the better-understood aspects of large-scale brain architecture. Recently, through the use of a system for computer-aided neuroanatomy, we have been able to obtain high-precision reconstructions of primary visual cortex map and column architectures, have constructed accurate models of both columnar and topographic architecture of primary visual cortex, and have suggested several computational algorithms which are contingent on the specific forms of column and map architecture which occur in this first visual area of monkey cortex (Schwartz et al. 1988). We expect to be able to extend these methods and ideas to other cortical areas. There is thus good progress in the areas of measuring, modeling, and computing with single-map representations. However, the problem of how to make use of multiple maps has been little explored.

Other workers have considered the application of single-map representations to classification. Kohonen (1984) has developed an algorithm for representing a feature space in a map; this algorithm constructs a space-variant representation, in rough analogy to the space-variant nature of primate visual cortex. However, this work does not provide a computational model for computing with multiple maps.

We believe that a classifier utilizing a multiple-map architecture must incorporate the following modules:

An efficient algorithm for classification in two dimensions.

A projection of high dimensional data into a two-dimensional representation.

An algorithm for combining multiple two-dimensional representations.

Our strategy in this work has been to use simple components to construct our multiple-map classifier. In particular, we were seeking algorithms which require one pass through the data and which are not sensitive to convergence issues (e.g. local minima in an energy function). We are interested in the overall properties of the classifier, and we are trying to deemphasize the role of the individual components, which are modular and hence subject to improvement or replacement.

2 Classification in Two Dimensions

We assume that the items, or instances, we wish to classify are represented as vectors x ∈ R^{d}, where each component of x is a feature measurement. Each instance belongs to a class k. We also have a training set, a set of instances of known class (training examples). We refer to the set of training examples in class k as X_{k}. Our problem is to construct a set of discriminant functions f_{k} : R^{d} → R, k = 1, …, c. An arbitrary instance x is assigned to the class k for which f_{k}(x) is maximal.

Because the instances are represented as vectors, we can refer to the distance between an instance and a training example as ∥x−x′∥. We compute discriminant functions

f_{k}(x) = \frac{1}{N} ∑_{x′∈X_{k}} g(∥x − x′∥), (2.1)

where g(r) is some function which decreases as r increases. If we let g be a probability density (i.e. nonnegative and integrating to one over its support) this is the Parzen-window estimate (Parzen 1962) for the a posteriori density; i.e. f_{k}(x) ≈ p(k|x). Since this is the same term which is maximized in the Bayes classifier, our classifier performance approaches the Bayesian limit as the approximation above approaches the actual probability density. This algorithm is related to the nearest-neighbor classifier. Its principal novelty is to use maps to store f_{k}(x). Then, given the training examples, we can compute f_{k}(x) by convolution in one pass.

For illustration, see figure 1. We depict a two-class, one-dimensional classifier. The “map” is simply a segment of the real line. The training examples are shown on the x-axis as boxes. The weighting function g(x) is a Gaussian function. The individual convolutions g(x) ∗ δ(x − x′) are shown as dotted lines. The class-specific density estimates, which are also the discriminant functions, are shown as a solid and broken line, respectively.

We consider a two-dimensional, three-class problem in figure 2 and figure 3. The weighting function is a circular two-dimensional Gaussian function. The instances have been drawn from prespecified two-dimensional multivariate normal distributions; this permits construction of a Bayes classifier to determine minimal error rate. In figure 2, we show a comparison between the Parzen-window density estimates f_{k}(x) and the actual probability density functions for each class. In figure 3, the classifier is compared to a Bayesian classifier. The visual comparison indicates that the classifier is capturing much of the character of the Bayesian classifier. When the classifier was trained on 400 samples from each class, and tested on 300 (different) instances, its error rate was 16.0%, which may be compared to 14.4% for the Bayesian classifier.

One important issue in the application of this method is the choice of the weighting function (or kernel). We have typically used Gaussian kernels, in which case we need to choose the kernel variance σ^{2} (or covariance matrix Σ_{m} in higher dimensions). This is a difficult problem in general; we have used heuristic algorithms. For example, if we desire an isotropic kernel, we might use σ = N^{−1/m}\sqrt{λ_{1}}, where λ_{1} is the largest eigenvalue of the covariance matrix resulting from the projection of the data into an m-dimensional map. The factor N^{−1/m} arises from the heuristic decision to give each training instance an equal amount of map volume; since the kernel is m-dimensional, the volume scales as σ^{m}. More generally, we could use Σ_{m} = \frac{1}{N} P Σ, where P is the projection into the map (see below). In experimental studies, we have found that the performance of the classifier is insensitive to small changes in the kernel size or shape.

Figure 1: A one-dimensional two-class classifier. Class 0 instances are shown as solid boxes; class 1 instances are shown as open boxes. The estimated a posteriori density p(k|x) (here, for one-dimensional x) is shown as a solid line for class 0, and a broken line for class 1. The Parzen-window function g(∥x − x′∥) for each paradigm x′ is shown as a dotted line. The classifier operates by choosing the class for which the estimated a posteriori density is maximized. Thus, samples drawn with feature measurements below 0.7 would be assigned to class 0. Samples drawn with x > 0.7 would be assigned to class 1.

Figure 2: Comparison of actual binormal density against estimated density f_{k}(x) computed by our classifier. Here a higher density corresponds to a darker region of the plot. The top row shows density plots for three binormal distributions in R^{2}. The bottom row shows the estimates f_{k}(x) computed by the classifier for 400 samples drawn from each of these three distributions. The weighting function used is a circular Gaussian with a variance approximately 1/60 the width of the figure.

3 From d Dimensions to Two Dimensions

In the previous section, we showed that the performance (as measured by error rate) approaches that of the Bayesian classifier for two-dimensional data drawn from Gaussian distributions. Actually there is nothing in our

Figure 3: Comparison of decision regions computed by our classifier against decision regions of a hypothetical Bayes classifier which had complete knowledge of the underlying class distributions. Regions in the Bayes classifier are clipped due to round-off.

derivation which restricts us to two dimensions; a d-dimensional classifier is defined as above, except that the density estimate p_{k}(x) will require a d-dimensional map. In practice we limit ourselves to two dimensions for three reasons. First, our original motivation is to understand the functional utility of laminar structures such as neocortex for pattern classification in the brain. Second, two-dimensional maps can be processed by conventional image processing software and hardware, and the user of the classifier gets the benefit of visual displays of the intermediate structures in the classifier (e.g. p_{k}(x) and the computed partition). Finally, the number of bins required to store the maps p_{k}(x) grows exponentially with the dimensionality d, and thus favors small d.

Restriction to two dimensions introduces an interesting aspect to the classification problem. Although our original data is in d dimensions, i.e. the data is composed of d measurements, we must somehow extract only two measurements or combinations of measurements with which to construct our classifier. The classification problem then spawns a problem of feature derivation. We can formulate the dimensionality reduction problem as construction of a function P : R^{d} → R^{2} which maps d-dimensional instances to two-dimensional map positions. The two dimensions of the map constitute the two derived features. We need to specify what kind of function P we will allow. To date, we have only considered linear projections, but nonlinear functions could also be used (e.g. Kohonen’s self-organizing feature map; Kohonen 1984).

We apply the generalized Fisher discriminant which was first introduced for a projection to R (Fisher 1936) and later generalized to a domain of arbitrary dimensionality (Bryan 1951). A discussion of the technique may be found in (Duda and Hart 1973). The two vectors which comprise P turn out to be the eigenvectors associated with the two largest eigenvalues in the generalized eigenvalue system

S_{b}u = λS_{w}u, (3.1)

where S_{w} is the “within-class” scatter matrix, given by

S_{w} = ∑_{k∈Ω} \frac{1}{N_{k}} ∑_{x′∈X_{k}}(x′ − \overline{x}_{k})(x′ − \overline{x}_{k})^{T} (3.2)

with \overline{x}_{k} the class mean and N_{k} the number of training examples representing class k, and S_{b} is the “between-class” scatter matrix, given by

S_{b} = \frac{1}{N} ∑_{k∈Ω} N_{k}(\overline{x}_{k} − \overline{x})(\overline{x}_{k} − \overline{x})^{T} (3.3)

Here, \overline{x} is the mean over all the training examples. In practice, we have found that S_{w} is nonsingular, so the system can be reduced to a standard eigenvalue problem

S_{w}^{−1}S_{b}u = λu. (3.4)

The extraction of the principal eigenvalue and its eigenvector are realizable using a typical Hebb synapse model with a fixed-length weight vector (Oja 1982).

The performance of the discriminant can be observed with Fisher’s classical iris data. This data describes a four-dimensional, three-class problem. Figure 4 depicts the classifier constructed from the projection of the iris

Figure 4: Iris classifier constructed from 100 training points drawn from the iris data (shaded background). Projection of four-dimensional iris data points into the two-dimensional subspace which maximizes the ratio of between-class variance to within-class variance (foreground data points).

data into the two-dimensional subspace which maximizes the ratio described above. The classes can be seen to be fairly well separated. The classifier was tested by splitting the 150 instances into a 100-instance training set and a 50-instance test set. After training on the 100 instances, the classifier achieved 98% correct classification on the 50 instances in the test set. By comparison, the nearest-neighbor classifier operating on the same training and test sets achieved 98% correct classification, the Gaussian classifier achieved 94% correct classification, and a multilayer perceptron trained using back-propagation^{1} achieved 96% correct classification.

4 Using Multiple Maps: A Tree of Maps

The previous example showed that for a relatively easy four-dimensional three-class problem, the generalized Fisher discriminant analysis was adequate to obtain a map which permitted good classifier performance. But in general, the discriminant analysis does not yield enough separation. For example, consider a regular five-dimensional simplex; this is a set of six equidistant points on the unit sphere in R^{5}. Locate a spherical multivariate normal distribution at each vertex of the simplex. This is a point swarm whose density declines as exp(−r^{2}), where r is the distance from the vertex. We construct the classifier by utilizing discriminant analysis to find a projection P : R^{5} → R^{2}. With 600 training points and 300 test points, the error rate is 36%.

Fortunately, we are not confined to one map. One method of using multiple maps utilizes a split/merge technique to reduce one many-class problem to several problems, each with fewer classes. We merge the original base classes into superclasses, each of which is represented by the union of training examples from its underlying base classes. We then apply discriminant analysis to the newly formed superclasses. If we can achieve an adequate separation, we proceed as above with a separate map for each superclass. If necessary, we can again perform merges among the elements of a superclass, until we have divided each superclass into component base classes.

The consequence of this approach is to create a tree of maps. From the root of the tree, we project instances into a superclass. If the superclass is a base class, we assign that class to the instance. Otherwise, the instance is assigned to a superclass, which has its own map. We project the instance into that map, and continue as above, until the instance lands in a region assigned to a base class. In the training phase, we construct a classifier in R^{2} for each internal node in the tree to classify instances into one of the superclasses for that node.

1A multilayer perceptron with 4 hidden units was trained using back-propagation (Rumelhart et al. 1986) with 5000 iterations through the training set, with ε = 0.02 and α = 0.

We can illustrate this algorithm with the simplex data. We partition the classes so that three maps are used to classify. In the first map, we merge classes 2–5 into a superclass, letting classes 0 and 1 remain as base classes. In the second map, we will resolve the superclass composed of classes 2–5 into classes 2 and 3 and a superclass formed of 4 and 5. Finally, in the third map, we will resolve the superclass formed from 4 and 5 above into component base classes. The error rate of the three-map classifier is found to be 4.7%, a dramatic improvement over the single-map classifier (36% error rate). This may be compared to error rates of 2%, 6% and 2.7% respectively for the Gaussian, nearest-neighbor and multilayer perceptron classifiers.^{2} We have also applied our classifier to real-world data which consisted of 22 cepstral parameters from digitized speech.^{3} Each of 16 data sets represented one speaker; seven classes (monosyllabic words) were present in each data set. Each set consisted of 70 training instances and 112 test instances. The results are summarized:

Nearest- Multilayer
Classifier: Multiple-map Gaussian^{4} neighbor perceptron^{5}

Average error

rate(%):  6.5  6.0  5.9  6.3
Range (%):  1.8–12.5  3.6–10.7 1.8–15.2 1.8–11.6

from which it may be seen that all four classifiers under consideration had closely comparable performance.

5 Automatic Generation of the Map Tree

In the preceding examples of multiple map usage, we interactively chose a map tree. In this section we explore a simple approach to automatic generation of the map tree. This is a clustering problem; we want to group classes into superclasses which in some way reflect the natural similarity between classes.

2A multilayer perceptron with 7 hidden units was trained using back-propagation (Rumelhart et al. 1986) with 5000 iterations through the training set, with ε = 0.02 and α = 0.

3We are grateful to R. Lippmann of MIT Lincoln Laboratory for providing this data.

4Covariance matrix estimates were obtained by pooling data from all 16 speakers for each class.

5Multilayer perceptrons for each speaker used 15 hidden units.

We introduce the distance matrix A for the classes. For any interclass distance measure dist(i, j), A_{ij} = A_{ji} = dist(i, j). We use a very simple tree generation algorithm. We treat A as a graph with each class represented by a node, and each edge weighted according to interclass distance. We then compute the minimal spanning tree. We form superclasses by recursively removing the largest edge in the tree, yielding two subtrees, each of which forms a superclass. We can use a variety of interclass distance measures; we have experimented with distances between class means, overlap of the one-dimensional Fisher discriminant projections, and overlap of the two-dimensional Fisher discriminant projections.

6 Discussion

Our classifier is inspired by the prevalence of maps in the vertebrate brain. Its components are two-dimensional map units which implement Parzenwindow density estimation, a dimensionality reduction methodology, and a scheme for decomposing a problem so that it can be solved by a system of maps. The training and running costs are favorably low. It admits an easy formal description. The intermediate results of classifier construction, e.g. the density estimates p_{k}(x) and the partition computed by the classifier, are easily observed by a human user. This allows insight into the structure of the data that is hard to gain from other algorithms. Many of the operations can be implemented with conventional image processing operations (and thus can take advantage of special-purpose image processing hardware). The error rate is comparable to popular parametric, nonparametric, and neural network classifiers.

Only a few other workers have considered the role of maps in pattern classification. In particular, Kohonen (1984) has considered iterative algorithms for “self-organizing feature maps.” We wish to distinguish his work from ours. In our classifier, the map function comprises a linear projection of a data instance to determine a position in the map followed by a reference to that position. Kohonen maps an instance via a distance computation at each node of his map, followed by a winner-take-all cycle to obtain the nearestneighbor to the instance among all the map nodes. The projection we use is computed with one pass through the training set to compute second-order statistics, which are diagonalized in a step which has a cost related only to the dimensionality of the data, but not the number of samples. Kohonen uses a very large number of iterations through the training set. Most importantly, we emphasize the use of multiple maps, which is not considered in (Kohonen 1984). We could use a Kohonen-type feature map as a module in our classifier (replacing the Fisher discriminant analysis) although we would then sacrifice these advantages.

Tree classifiers have been considered at length in Breiman et al. (1984). There are similarities between their classifiers and ours at classification time, although the training algorithms are quite distinct. The principal difference in classifier operation is that we use two-dimensional density estimation at each node, while they use one-dimensional linear discriminants. Their discriminant is typically a threshold comparison of one feature value, although they also describe an iterative technique for obtaining a discriminant from a linear combination of a subset of the feature variables. There are much larger differences in the classifier training algorithms; we present an example of a simple heuristic for generating map trees (based on minimal spanning trees) whereas they examine a large set of possible splits in the data to generate trees. We wish to emphasize that our tree classifier is one possible technique for utilizing multiple maps; examination of alternative approaches is an important research problem.

Perceptual (and probably cognitive) functions of the brain are mediated by laminar cortical systems. Three carefully investigated systems (monkey vision, bat echolocation, and auditory localization in the owl) are committed to multiple two-dimensional spatial maps. The present paper describes the first attempt to construct a pattern classification system which has high performance and which is based on a multiple parallel map-like representation of feature vectors. The algorithms described in this paper allow us to begin to investigate the pattern classification and perceptual performance of such map-based architectures.

Acknowledgments

Supported by AFOSR-88-0275.

References

Breiman, L., J.H. Freedman, R.A. Olshen, and C.J. Stone. 1984. Classification

and Regression Trees. Bellmont, CA: Wadsworth. Bryan, J.G. 1951. The Generalized Discriminant Function: Mathematical Foun-

dation and Computation Routine. Harvard Educ. Rev. 21, 90–95. Duda, R.O. and P.E. Hart. 1973. Pattern Classification and Scene Analysis. New

York: Wiley. Fisher, R.A. 1936. The Use of Multiple Discriminant Measurements in Taxonomic

Problems. Ann. Eugenics 7, 179-188. Kohonen, T. 1984. Self-organization and Associative Memory. New York: Springer-

Verlag. Oja, E. 1982. A Simplified Neuron Model as a Principal Component Analyzer. J.

Math. Biol. 15, 267–273. Parzen, E. 1962. On Estimation of a Probability Density Function and Mode.

Ann. Math. Stat 33, 1065–1076. Rumelhart, D.E., G.E. Hinton, and R.J. Williams. 1986. Learning Representations

by Back-propagating Errors. Nature 323, 533–536.

Schwartz, E.L., B. Merker, E. Wolfson, and A. Shaw. 1988. Computational Neuroscience: Applications of Computer Graphics and Image Processing to Two and Three Dimensional Modeling of the Functional Architecture of Visual Cortex. IEEE Computer Graphics and Applications July 1988, 13–28.

Received 1 October; accepted 18 November 1988.

Communicated by David A. Robinson

A Control Systems Model of Smooth Pursuit Eye Movements with Realistic Emergent Properties

R. J. Krauzlis S. G. Lisberger

Department of Physiology and Neuroscience Graduate Program, University of California, San Francisco, CA 94143, USA

Visual tracking of objects in a noisy environment is a difficult problem that has been solved by the primate oculomotor system, but remains unsolved in robotics. In primates, smooth pursuit eye movements match eye motion to target motion to keep the eye pointed at smoothly moving targets. We have used computer models as a tool to investigate possible computational strategies underlying this behavior. Here, we present a model based upon behavioral data from monkeys. The model emphasizes the variety of visual signals available for pursuit and, in particular, includes a sensitivity to the acceleration of retinal images. The model was designed to replicate the initial eye velocity response observed during pursuit of different target motions. The strength of the model is that it also exhibits a number of emergent properties that are seen in the behavior of both humans and monkeys. This suggests that the elements in the model capture important aspects of the mechanism of visual tracking by the primate smooth pursuit system.

1 Introduction

Computer models have advanced our understanding of eye movements by providing a framework in which to test ideas suggested by behavioral and physiological studies. Our knowledge of the smooth pursuit system is at a stage where such models are especially useful. We know that pursuit eye movements are a response to visual motion and that they are used by primates to stabilize the retinal image of small moving targets. Lesion and electrophysiological studies have identified several cortical and subcortical sites that are involved in pursuit (see Lisberger et al. 1987 for review), but the precise relationship between the visual motion signals recorded at these sites and those used by pursuit remain unclear.

We present a model that was designed to replicate the monkey’s initial eye velocity response as a function of time for different pursuit target motions. The model emphasizes the variety of visual signals available for pursuit and minimizes the computations done by motor pathways. The structure of the model is based upon behavioral experiments which have characterized how different aspects of visual motion act to initiate pursuit. In monkeys, the pursuit system responds not only to the velocity of retinal images, but also to smooth accelerations and to the abrupt accelerations that accompany the onset of target motion (Krauzlis and Lisberger 1987; Lisberger and Westbrook 1985). Therefore, the model includes three parallel pathways that are sensitive to these three aspects of visual motion.

2 Structure of the Model

Our model is drawn in figure 1. Within each pathway, a time-delayed signal related to the motion of retinal images (Ṫ − Ė, called retinal “slip”) is processed by a nonlinear gain element derived from our behavioral experiments and a filter. The first pathway is sensitive to slip velocity (ė) and its gain is linear. The second and third pathways are both sensitive to slip acceleration (ë), but in different ways. The impulse acceleration pathway is sensitive to the large accelerations that accompany step changes in target velocity, but has a dead zone in the gain element that renders it insensitive to smaller accelerations. The smooth acceleration pathway is sensitive to gradual changes in image velocity. The outputs of the gain elements in each pathway are low pass filtered to produce three signals with different dynamics (Ë′v, Ë′i, Ë′a) that are then summed and integrated to give a command for eye velocity (Ė′). The integrator makes our model reproduce the fact that the pursuit system interprets visual inputs as commands for eye accelerations (Lisberger et al. 1981). Eye velocity (Ë) is obtained by passing the eye velocity command through a low pass filter that represents the eye muscles and orbital tissues.

The behavior of the model was refined by matching its performance under open-loop conditions to that of the monkey. We removed visual feedback by setting the value of feedback gain to zero, and compared the model’s output to averages of the monkey’s eye velocity in behavioral trials where visual feedback was electronically eliminated for 200 ms (methods in Morris and Lisberger 1987). First, we stimulated the model with steps in target velocity, which activate the slip velocity and impulse acceleration pathways. We adjusted the filters in these pathways to obtain the fit in figure 2A, where the rising phase of the model’s output (dotted lines) matches the rising phase of the monkey’s eye velocity (solid lines) during the open-loop portion of the monkey’s response. Then, we stimulated the model with steps in target acceleration, which activates the slip velocity and smooth acceleration pathways, and adjusted the filter in the smooth acceleration pathway (Fig. 2B).

3 Emergent Properties of the Model

We tested the model by restoring visual feedback and providing steps of target velocity in closed-loop conditions. Figure 2C shows that the model matches the rising phase of the monkey’s response and makes a realistic transition into steady-state tracking. Like the monkey, it reaches steadystate velocity at later times for higher target speeds. The contribution of each pathway to the initiation of pursuit can be assessed by setting its gain to zero, effectively “lesioning” that limb of the model. When the slip impulse acceleration pathway is lesioned, the rising phase is delayed and more sluggish, but the transition to steady-state tracking is unchanged (Fig. 2D, open arrow). This pathway contributes exclusively to the initial 25–50 ms of the response to steps in target velocity and allows the model to reproduce the

Figure 1: Model of smooth pursuit eye movement system. Boxes contain transfer functions expressed in Laplace notation. Abbreviations: Ṫ, target velocity; ė, slip velocity; ë, slip acceleration; Ë′v, output of slip velocity pathway; Ë′i, output of slip impulse acceleration pathway; Ë′a, output of slip acceleration pathway; Ë′, eye acceleration command; Ė′, eye velocity command; Ė, eye velocity. Parameters used: t = .065; T_{v} = 0.030; T_{i} = 0.020; T_{a} = 0.010; T_{p} = 0.015. Functions for gain elements: Slip velocity pathway: y = ax; a = 8.3. Slip impulse acceleration pathway: for x > c, y = a log(bx + 1); a = 17500, b = .00015, c = 3000. Slip smooth acceleration pathway: for d > x > e, y = a log(bx + 1); for x < e, y = (cx^{2})a log(bx + 1); a = 28, b = .1, c = .0016, d = 500, e = 18.5. Equations given for impulse and smooth acceleration pathways apply for x > 0. For x < 0, equivalent odd functions are used.

Figure 2: Comparison of the eye velocity output from the model and the monkey. In all panels, dotted lines show the model’s output and solid lines show the monkey’s eye velocity. A: Steps in target velocity of 5, 15, and 25 d/s under open-loop conditions. The monkey’s open-loop response lasts for the first 200 ms of his response. B: Steps in target acceleration of 45, 64, and 120 d/s^{2} under open-loop conditions. C: Steps in target velocity of 5, 15, and 25 d/s under closed-loop conditions. D: Effect of lesioning either acceleration pathway on the model’s response to a step in target velocity of 20 d/s. Open arrow, model’s response when gain in slip impulse acceleration pathway is set to zero. Closed arrow, model’s response when gain in slip smooth acceleration pathway is set to zero.

observation that the earliest component of the pursuit response is sensitive to target direction, but relatively insensitive to target speed (Lisberger and Westbrook 1985). When the smooth acceleration pathway is eliminated, the rising phase is unchanged, but there is a large overshoot in the transition to steady-state tracking (Fig. 2D, filled arrow). Thus, the smooth acceleration pathway normally decelerates the eye as eye velocity approaches target velocity. This is an emergent property of the model, since this pathway was tuned by adjusting its contribution to the acceleration of the eye as shown in figure 2B.

The model rings at a relatively high frequency, 5 Hz, in response to steps in target velocity (solid lines in figure 3A). Similar oscillations are seen in the behavior of both humans and monkeys (Goldreich and Lisberger 1987; Robinson et al. 1986). If the model is driven at this resonant frequency, the output lags target velocity by 180 degrees (Fig. 3B, filled arrow), an effect that is also seen in the monkey’s behavior (Goldreich and Lisberger 1987). The high frequency properties of the model depend upon the presence of the smooth acceleration pathway. If this pathway is eliminated, the spontaneous oscillations still occur, but now at only 1.6 Hz (Fig. 3A, open arrow), and the phase lag in the response to sinusoidal inputs increases (Fig. 3B, open arrow).

4 Discussion

An important property of our model is that it allows independent control over the initiation and maintenance phases of pursuit. The rising phase is determined mainly by the slip velocity and impulse acceleration pathways. The steady-state behavior is determined primarily by the smooth acceleration pathway. Since the differentiator in the smooth acceleration pathway introduces a phase lead, the steady-state behavior of the model has a higher frequency response than the rising phase. The exact frequency of ringing depends upon the total delay around the smooth acceleration pathway. For example, if the delay in the visual input is increased by 30 ms, the model will ring at 3.8 Hz, similar to what is normally observed in humans (Robinson et al. 1986) or in monkeys when the delay in visual feedback is increased (Goldreich and Lisberger 1987). The amount of ringing depends upon the gain element in the smooth acceleration pathway. Lowering the gain dampens or eliminates the ringing, increasing the gain produces persistent ringing. Such variations are also seen on individual trials in the monkey’s behavior.

The strength of our model is that it uses open-loop behavioral data to embody the pursuit system’s sensitivity to different aspects of visual motion. Although it was designed to replicate the dynamics of the initiation of pursuit, the model also serendipitously solves a problem noted by Robinson (Robinson et al. 1986), namely, that the rising phase of pursuit is sluggish compared to the frequency of its ringing. The emergence of realistic steady-state properties in the model indicates that the visual elements in its pathways capture important aspects of signal processing within the smooth pursuit system. Our model does not include a sensitivity to position errors, which can affect steady-state tracking in monkeys (Morris and Lisberger 1987). It also does not include the topographic organization of the visual system and therefore cannot reproduce the retinotopic deficits in the initiation of pursuit or the directional deficits in the maintenance of pursuit which are seen after lesions of cortical areas MT and MST (Dursteler et al. 1987; Newsome et al. 1985). However, it should be possible to embed the dynamics of our model within a topographic structure that would account for these effects.

Acknowledgments

This research was supported by NIH Grants EY03878 and EY07058.

References

Dursteler, M.R., R.H. Wurtz, and W.T. Newsome. 1987. Directional Pursuit Deficits Following Lesions of the Foveal Representation within the Superior Temporal Sulcus of the Macaque Monkey. J. Neurophysiol 57, 1262–1287.

Goldreich, D. and S.G. Lisberger. 1987. Evidence that Visual Inputs Drive Oscil-

Figure 3: Ringing and frequency response of the model. A: Solid lines, model’s closed-loop response to steps in target velocity of 10 and 20 d/s, viewed on larger time scale than in figure 2C. Dotted line, model’s response to step in target velocity of 10 d/s when gain in smooth acceleration pathway is set to zero. B: Driving the model with sine wave target velocity at 5.0 Hz under closed-loop conditions. Filled arrow, the intact model’s response lags target motion by 180 degrees. Open arrow, model’s response when gain in smooth acceleration pathway is set to zero. Phase lag is now 325 degrees. lations in Eye Velocity during Smooth Pursuit Eye Movements in the Monkey. Soc. Neurosci. Abstr. 13, 170.

Krauzlis, R.J. and S.G. Lisberger. 1987. Smooth Pursuit Eye Movements are Not

Driven Simply by Target Velocity. Soc. Neurosci. Abstr. 13, 170. Lisberger, S.G., C. Evinger, G.W. Johanson, and A.F. Fuchs. 1981. Relationship

between Eye Acceleration and Retinal Image Velocity during Foveal Smooth Pursuit Eye Movements in Man and Monkey. J. Neurophysiol. 46, 229–249.

Lisberger, S.G., E.J. Morris, and L. Tychsen. 1987. Visual Motion Processing and Sensory-motor Integration for Smooth Pursuit Eye Movements. Ann. Rev. Neurosci. 10, 97–129.

Lisberger, S.G. and L.E. Westbrook. 1985. Properties of Visual Inputs that Initiate Horizontal Smooth Pursuit Eye Movements in Monkeys. J. Neurosci. 5, 1662–1673.

Morris, E.J. and S.G. Lisberger. 1987. Different Responses to Small Visual Errors during Initiation and Maintenance of Smooth-pursuit Eye Movements in Monkeys. J. Neurophysiol. 58, 1351–1369.

Newsome, W.T., R.H. Wurtz, M.R. Dursteler, and A. Mikami. 1985. Deficits in Visual Motion Processing Following Ibotenic Acid Lesions of the Middle Temporal Area of the Macaque Monkey. J. Neurosci. 5, 825–840.

Robinson, D.A., J.L. Gordon, and S.E. Gordon. 1986. A Model of the Smooth Pursuit Eye Movement System. Biol. Cybern. 55, 43–57.

Received 15 August; accepted 1 October 1988.

Communicated by Patricia Churchland

The Brain Binds Entities and Events by Multiregional Activation from Convergence Zones

Antonio R. Damasio

Department of Neurology, Division of Behavioral Neurology and Cognitive Neuroscience, University of Iowa College of Medicine, Iowa City, IA, USA

The experience of reality, in both perception and recall, is spatially and temporally coherent and “in-register.” Features are bound in entities, and entities are bound in events. The properties of these entities and events, however, are represented in many different regions of the brain that are widely separated. The degree of neural parcellation is even greater when we consider that the perception of most entities and events also requires a motor interaction on the part of the perceiver (such as eye movements and hand movements) and often includes a recordable modification of the perceiver’s somatic state. The question of how the brain achieves integration starting with the bits and pieces it has to work with, is the binding problem. Here we propose a new solution for this problem, at the level of neural systems that integrate functional regions of the telencephalon.

1 Introduction

Data from cognitive psychology, neurophysiology, and neuroanatomy indicate unequivocally that the properties of objects and events that we perceive through various sensory channels engage geographically separate sensory regions of the brain (Posner 1980; Van Essen and Maunsell 1983; Damasio 1985; Livingstone and Hubel 1988). The need to “bind” together the fragmentary representations of visual information has been noted by Treisman and Gelade (1980), Crick (1984), and others, but clearly the problem is a much broader one and includes the need to integrate both the sensory and motor components in both perception and recall, at all scales and at all levels. This broader concept of binding is closer to that of Sejnowski (1986).

The traditional and by now untenable solution to the binding problem has been that the components provided by different sensory portals end up being displayed together in so-called multimodal cortices, where the most detailed and integrated representations of reality are achieved. This intuitively reasonable view suggests that perception depends on a unidirectional process which provides a gradual refinement of signal extraction along a cascade aimed towards integrative cortices in anterior temporal and anterior frontal regions. Some of the most influential accounts for the neural basis of cognition in the post-war period as well as major discoveries of neurophysiology and neuroanatomy over the past two decades, have seemed compatible with this view. After all, anatomical projections do radiate from primary sensory cortices toward structures in the hippocampus and prefrontal cortices via a multi-stage sequence (Pandya and Kuypers 1969; Jones and Powell 1970; Nauta 1971; Van Hoesen 1982), and the farther away neurons are from primary sensory cortices, the larger their receptive fields become, and the less unimodal their responses are (Desimone and Ungerleider 1989). However, there are several lines of evidence on the basis of which this traditional solution can be rejected.

2 Experimental Evidence

Evidence from Experimental Neuroanatomy: The notion that integration of perceptual or recalled components depends on a single neural meeting ground calls for the identification of a neuroanatomical site that would receive projections from all neural regions involved in the processing of entities and events as they occur in experience. Despite considerable exploration no such region has yet been found. The anterior temporal cortices and the hippocampus do receive projections from multiple sensory areas, but not from motor regions (Van Hoesen 1982). The anterior frontal cortices, the most frequently mentioned candidates for ultimate integration, are even less suited for that role. The sensory and motor streams that reach them remain segregated in different regions (Goldman-Rakic 1988). In other words, there seems to be no structural foundation to support the intuition that temporal and spatial integration occur at a single site.

Advances in experimental neuroanatomy have added a new element to neuroanatomical reasoning about this problem: at every stage of the chain of forward cortical projections, there exist prominent projections back to the originating sites. Moreover, the systems are just as rich in multi-stage, reciprocating feedback projections as they are in feedforward projections (Van Hoesen 1982; Van Essen 1985; Livingstone and Hubel 1987). The neuroanatomical networks revealed by these studies allow for both forward convergence of some parallel processing streams, and for the flow of signaling back to points of origin. In the proposal we will describe below, such networks operate as coherent phase-locked loops in which patterns of neural activity in “higher” areas can trigger, enhance, or suppress patterns of activity in “lower” areas.

Evidence from Experimental Neuropsychology in Humans with Focal Cerebral Lesions: If temporal and frontal integrative cortices were the substrate for the integration of neural activity on which binding depends, the bilateral destruction of those cortices in humans should: (a) preclude the perception of reality as a coherent multimodal experience and reduce experience

Figure 1: Fundamental divisions of human cerebral cortex depicted in a simplified diagram of the external and internal views of the left hemisphere. The motor and premotor cortices include cytoarchitectonic fields 4, 6, and 8. The early and intermediate sensory cortirces include the primary visual, auditory, and somatosensory regions (respectively fields 17, 41/42, and 3/1/2), and the surrounding association cortices (fields 18/19, 7, 39, 22, 40, 5). The temporal “integrative” cortices include fields 37, 36, 35, 20, 21, 38, and 28, i.e., neocortical as well as limbic and paralimbic areas. The frontal “integrative” cortices include fields 44, 45, 46, 9, 10, 11, 12, 13, and 25, i.e., prefrontal neocortices as well as limbic.

to disjointed, modal tracks of sensory or motor processing; (b) reduce the integration of even such modal track processing; and (c) disable memory for any form of past integrated experience and interfere with all levels and types of memory. However, the results of bilateral destruction of the anterior temporal lobes, as well as bilateral destruction of prefrontal cortices, falsify these predictions (see Fig. 1).

Coherent perceptual experience is not altered by bilateral damage to the anterior temporal regions, nor does such damage disturb perceptual quality (see Corkin 1984; Damasio et al. 1985; Damasio et al. 1987). Our patient Boswell is a case in point. His extensive, bilateral damage in anterior temporal cortices and hippocampus, disables his memory for unique autobiographical events, but not his ability to perceive the world around in fully integrated fashion and to recall and recognize the entities and events that he encounters or participates in, at non-unique level. His binding ability breaks down at the level of unique events, when the integration of extremely complex combinatorial arrangement of entities is required.

Bilateral lesions in prefrontal cortices, especially when restricted to the orbitofrontal sector, are also compatible with normal perception and even with normal memory for most entities and events except for those that pertain to the domain of social knowledge (Eslinger and Damasio 1985; Damasio and Tranel 1988).

Finally, it is damage to certain sectors of sensory association cortices that can affect both the quality of some aspects of perception within the modality served by those cortices, and recognition and recall. Depending on precisely which region of visual cortex is affected, lesions in early visual association cortices can disrupt perception of shape, or color, or texture, or stereopsis, or spatial placement of the physical components of a stimulus (Damasio 1985; Damasio et al. 1989). A patient may lose the ability to perceive color and yet perceive shape, depth and motion normally. More importantly, damage within some sectors of modal association cortices can disturb recall and recognition of stimuli presented through that modality, even when basic perceptual processing is not compromised. For instance, patients may become unable to recognize familiar faces that they perceive flawlessly (although, intriguingly, they can discriminate familiar from unfamiliar faces at covert level; Tranel and Damasio 1985; 1988).

The key point is that damage in a posterior and unimodal association cortex can disrupt recall and recognition at virtually every level of the binding chain, from the entity-categorical level to the event-unique level. It can preclude the kind of integrated experience usually attributed to the anterior cortices.

3 A New View on the Binding Problem

The evidence then indicates: (a) that substantial binding, relative to entities or parts thereof, occurs in unimodal cortices and can support recall and recognition at the level of categories; (b) that recall and recognition at category level, are generally not impaired by damage confined to anterior integrative cortices, i.e., knowledge recalled at categoric levels depends largely on posterior sensory cortices and interconnected motor cortices; (c) that recall and recognition of knowledge at the level of unique entities or events, requires both anterior and posterior sensory cortices, i.e., a more complex network is needed to map uniqueness; anterior integrative structures alone are not sufficient to record and reconstruct unique knowledge.

The implication is that the early and intermediate posterior sensory cortices contain fragmentary records of featural components which can be reactivated, on the basis of appropriate combinatorial arrangements (by fragmentary featural components we mean “parts of entities,” at a multiplicity of scales, most notably at feature level, e.g., color, movement, texture, shape and parts thereof). They also contain records of the combinatorial arrangement of features that defined entities (“local” or “entity” binding), but do not contain records of the spatial and temporal relationships assumed by varied entities within an event (“non-local” or “event binding”). The latter records, the complex combinatorial codes needed for event recall, are inscribed in anterior cortices. In this perspective the posterior cortices contain the fragments with which any experience of entities or events can potentially be re-enacted, but only contain the binding mechanism to re-enact knowledge relative to entities. Posterior cortices require binding mechanisms in anterior structures in order to guide the pattern of multiregional activations necessary to reconstitute an event.

Thus posterior cortices contain both basic fragments and local binding records and are essential for recreating any past experience. Anterior cortices contain non-local or event-binding records and are only crucial for reconstitution of contextually more complex events.

Perhaps the most important distinction between this perspective and the traditional view, is that higher-order anterior cortices are seen as repositories of combinatorial codes for inscriptions that lie elsewhere and can be reconstructed elsewhere, rather than being the storage site for the more refined “multimodal” representations of experiences. Although anterior cortices receive multimodal projections we conceptualize the records they harbor as amodal.

If parts of the representation of an entity are distributed over distant regions of the brain, then mechanisms must be available to bind together the fragments. A proposal for a new solution to the binding problem (Damasio 1989) is illustrated in figure 2 and presented in outline as follows:

1. The neural activity prompted by perceiving the various physical properties of any entity, occurs in fragmented fashion and in geographically separate regions located in early sensory cortices and in motor cortices. So-called “integrative” cortices do not contain such fragmentary inscriptions.

2. The integration of multiple aspects of external and internal reality in perceptual or recalled experiences, depends on the phase-locked coactivation of geographically separate sites of neural activity within the above mentioned sensory and motor cortices, rather than on a transfer and spatial integration of different representations towards anterior higher-order cortices. Consciousness of those co-activations depends on their being attended to, i.e., on simultaneous enhancement of a pertinent set of activity against background activity.

3. The patterns of neural activity that correspond to distinct physical properties of entities are recorded in the same neural ensembles in which they occur during perception, but the combinatorial arrangements (binding codes) that describe their pertinent linkages in entities and in events (their spatial and temporal coincidences), are stored in separate neural ensembles called convergence zones.

4. Convergence zones trigger and synchronize neural activity patterns corresponding to topographically organized fragment representations of physical structure, that were pertinently associated in experience, on

Figure 2: Simplified diagram of some aspects of the proposed neural architecture. V, SS, and A depict early and intermediate sensory cortices in visual, somatosensory, and auditory modalities. In each of those sensory sectors, separate functional regions are represented by open and filled dots. Note feedforward projections (black lines) from those regions toward several orders of convergence zones (CZ1, CZ2, CZn), and note also feedback projections from each CZ level toward originating regions (red lines). H depicts hippocampal system, one of the structures where signals related to a large number of activity sites can converge. Note outputs of H toward last station of feedforward convergence zones (CZn) and toward noncortical neural stations (NC) in basal forebrain, brain stem, and neurotransmitter nuclei. Feedforward and feedback pathways should not be seen as rigid channels. They are conceived as facilitated lines which become active when concurrent firing in early cortices or CZs takes place. Furthermore, those pathways terminate over neuron ensembles, in distributed fashion, rather than on specific single neurons.

the basis of similarity, spatial placement, temporal sequence, or temporal coincidence, or combinations thereof. The triggering and synchronization depends on feedback projections from the convergence zone to multiple cortical regions where fragment records can be activated.

5. Convergence zones are located throughout the telencephalon, at multiple neural levels, in association cortices of different orders, limbic cortices and subcortical limbic nuclei, and non-limbic subcortical nuclei such as the basal ganglia.

6. The geographic location of convergence zones for different entities varies among individuals but is not random. It is constrained by the subject matter of the recorded material (its domain), and by contextual complexity of events (the number of component entities that interact in an event and the relations they adopt), and by the anatomical design of the system. Convergence zones that bind features into entities are located earlier in the processing streams, and convergence zones that bind entities into progressively more complex events are gradually placed more anteriorly in the processing streams.

7. The representations inscribed in the above architecture, both those that preserve topographic/topologic relationships and those that code for combinatorial arrangements, are committed to populations of neuron ensembles and their synapses, in distributed form.

8. The co-occurrence of activities in multiple sites that is necessary for binding conjunctions, is achieved by recurrent feedback interactions.

Thus, we propose that the processing does not proceed in a single direction but rather through temporally coherent phase-locking amongst multiple regions. Although the convergence zones that realize the more encompassing integration are placed more anteriorly, it is activity in the more posterior cortical regions that is more directly related to conscious experience.

By means of feedback, convergence zones repeatedly return processing to earlier cortices where activity can proceed again towards the same or other convergence zones. Integration takes place when activations occur within the same time window, in earlier cortices. There is no need to postulate a “final” and single integration area. This model accommodates the segregation of neural processing streams that neuroanatomical and neurophysiological data continue to reveal so consistently, and is compatible with the increase in receptive fields of neurons that occurs in cerebral cortex, in the posterioranterior direction. It accords with the proposal that fewer and fewer neurons placed anteriorly in the system are projected on by structures upstream and thus subtend a broader compass of feed-forwarding regions. Broad receptive field neurons serve as pivots for reciprocating feedback projections rather than as accumulators of the knowledge inscribed at earlier levels. They are intermediaries in a continuous process that centers on early cortices.

4 Conclusions

The problem of how the brain copes with the fragmentary representations of information is central to our understanding of brain function. It is not enough for the brain to analyze the world into its components parts: the brain must bind together those parts that make whole entities and events, both for recognition and recall. Consciousness must necessarily be based on the mechanisms that perform the binding. The hypothesis suggested here is that the binding occurs in multiple regions that are linked together through activation zones; that these regions communicate through feedback pathways to earlier stages of cortical processing where the parts are represented; and that the neural correlates of consciousness should be sought in the phaselocked signals that are used to communicate between these activation zones.

Several questions are raised by this new view. For instance, what is the precise nature of the feedback signals that provide temporally coherent phase-locking among multiple regions? How large are the convergence zones in different parts of the brain? How are the decisions made to store an aspect of experience in a particular zone? There are several possible approaches to test the hypothesis proposed here. One approach is to develop new techniques for recording from many neurons simultaneously in communicating brain regions. Another relies on neuropsychological experiments in neurological patients with small focal lesions in key areas of putative networks dedicated to specific cognitive processes. Finally, modeling studies should illuminate the collective properties of convergence zones and provide us with the intuition we need to sharpen our questions.

Acknowledgments

Supported by NINCDS Grant PO1 NS19632.

References

Corkin, S. 1984. Lasting Consequences of Bilateral Medial Temporal Lobectomy: Clinical Course and Experimental Findings in HM. Seminars in Neurology 4, 249–259.

Crick, F. 1984. Function of the Thalamic Reticular Complex: The Searchlight

Hypothesis. Proc. Natl. Acad. Sci. USA 81, 4586–4590. Damasio, A. 1989. Multiregional Retroactivation: A Systems Level Model for

Some Neural Substrates of Cognition. Cognition, in press.

. 1985. Disorders of Complex Visual Processing. In: Principles of Behavioral Neurology, ed. M.M. Mesulam, Contemporary Neurology Series, 259–288. Philadelphia: F.A. Davis.

Damasio, A., P. Eslinger, H. Damasio, G.W. Van Hoesen, and S. Cornell. 1985. Multimodal Amnesic Syndrome Following Bilateral Temporal and Basal Forebrain Damage. Archives of Neurology 42, 252–259.

Damasio, A., H. Damasio, D. Tranel, K. Welsh, and J. Brandt. 1987. Additional Neural and Cognitive Evidence in Patient DRB. Society for Neuroscience 13, 1452.

Damasio, A. and D. Tranel. 1988. Domain-specific Amnesia for Social Knowledge.

Society for Neuroscience 14, 1289. Damasio, A.R., H. Damasio, and D. Tranel. 1989. Impairments of Visual Recog-

nition as Clues to the Processes of Memory. In: Signal and Sense: Local and Global Order in Perceptual Maps, eds. G. Edelman, E. Gall, and M. Cowan, Neuroscience Institute Monograph. Wiley and Sons.

Desimone, R. and L. Ungerleider. 1989. Neural Mechanisms of Visual Processing in Monkeys. In: Handbook of Neuropsychology, Disorders of Visual Processing, ed. A. Damasio, in press.

Eslinger, P. and A. Damasio. 1985. Severe Disturbance of Higher Cognition after

Bilateral Frontal Lobe Ablation. Neurology 35, 1731–1741. Goldman-Rakic, P.S. 1988. Topography of Cognition: Parallel Distributed Net-

works in Primate Association Cortex. In: Annual Review of Neuroscience II, Annual Reviews Inc., Palo Alto, CA, 137–156.

Jones, E.G. and T.P.S. Powell. 1970. An Anatomical Study of Converging Sensory

Pathways within the Cerebral Cortex of the Monkey. Brain 93, 793–820. Livingstone, M. and D. Hubel. 1988. Segregation of Form, Color, Movement, and

Depth: Anatomy, Physiology, and Perception. Science 240, 740–749.

. 1987. Connections between Layer 4B of Area 17 and Thick Cytochrome Oxidase Stripes of Area 18 in the Squirrel Monkey. Journal of Neuroscience 7, 3371–3377.

Nauta, W.J.H. 1971. The Problem of the Frontal Lobe: A Reinterpretation.

J. Psychiat. Res. 8, 167–187. Pandya, D.N. and H.G.J.M. Kuypers. 1969. Cortico-cortical Connections in the

Rhesus Monkey. Brain Res. 13, 13–36. Posner, M.I. 1980. Orienting of Attention. Quarterly Journal of Experimental

Psychology 32, 3–25. Sejnowski, T.J. 1986. Open Questions about Computation in Cerebral Cortex. In:

Parallel Distributed Processing, eds. J.L. McClelland and D.E. Rummelhart, 372–389. Cambridge: MIT Press.

Tranel, D. and A. Damasio. 1988. Nonconscious Face Recognition in Patients

with Face Agnosia. Behavioral Brain Research 30, 235–249.

. 1985. Knowledge without Awareness: An Autonomic Index of Facial Recognition by Prosopagnosics. Science 228:21, 1453–1454.

Treisman, A. and G. Gelade. 1980. A Feature-integration Theory of Attention.

Cognitive Neuropsychology 12, 97–136. Van Essen, D.C. 1985. Functional Organization of Primate Visual Cortex. In:

Cerebral Cortex, eds. A. Peters and E.G. Jones, 259–329. Plenum Publishing. Van Essen, D.C. and J.H.R. Maunsell. 1983. Hierarchical Organization and Func-

tional Streams in the Visual Cortex. Trends in Neuroscience 6, 370–375. Van Hoesen, G.W. 1982. The Primate Parahippocampal Gyrus: New Insights

Regarding its Cortical Connections. Trends in Neurosciences 5, 345–350.

Received 18 November; accepted 25 November 1988.

Communicated by David Touretzky

Product Units: A Computationally Powerful and Biologically Plausible Extension to Backpropagation Networks

Richard Durbin David E. Rumelhart

Department of Psychology, Stanford University, Stanford, CA 94305, USA

We introduce a new form of computational unit for feedforward learning networks of the backpropagation type. Instead of calculating a weighted sum this unit calculates a weighted product, where each input is raised to a power determined by a variable weight. Such a unit can learn an arbitrary polynomial term, which would then feed into higher level standard summing units. We show how learning operates with product units, provide examples to show their efficiency for various types of problems, and argue that they naturally extend the family of theoretical feedforward net structures. There is a plausible neurobiological interpretation for one interesting configuration of product and summing units.

1 Introduction

The success of multilayer networks based on generalized linear threshold units depends on the fact that many real-world problems can be well modeled by discriminations based on linear combinations of the input variables. What about problems for which this is not so? It is clear that for some tasks higher order combinations of some of the inputs, or ratios of inputs, may be appropriate to help form a good representation for solving the problem (for example cross-correlation terms can give translational invariance). This observation led to the proposal of “sigma-pi units” which apply a weight not only to each input, but also to all second and possibly higher order products of inputs (Rumelhart, Hinton, and McClelland; Maxwell et al. 1987). The weighted sum of all these terms is then passed through a non-linear thresholding function. The problem with sigma-pi units is that the number of terms, and therefore weights, increases very rapidly with the number of inputs, and becomes unacceptably large for use in many situations. Normally only one or a few of the non-linear terms are relevant. We therefore propose a different type of unit, which represents a single higher order term, but learns which one to represent. The output of this unit, which we will call a product unit, is

y = Π_{i=1}^{N}x_{i}^{p_{i}} (1.1)

Figure 1: Two suggested forms of possible network incorporating product units. Product units are shown with a Π and summing units with a Σ. (a) Each summing unit gets direct connections from the input units, and also from a group of dedicated product units. (b) There are alternating layers of product and summing units, finishing with a summing unit. The output of all our summing units was squashed using the standard logistic function, 1/(1 + e^{−x}); no non-linear function was applied to the output from product units.

We will treat the p_{i} in the same way as variable weights, training them by gradient descent on the output sum square error. In fact such units provide much more generality than just allowing polynomial terms, since the p_{i} can take fractional and negative values, permitting ratios. However, simple products can still be represented by setting the p_{i} to zero or one. Related types of units were previously considered by Hanson and Burr (1987).

There are various ways in which product units could be used in a network. One way is for a few of them to be made available as inputs to a standard thresholded summing unit in addition to the original raw inputs, so that the output can now consider some polynomial terms (Fig. 1a). This approach has a direct neurobiological interpretation (see the discussion). Alternatively there could be a whole hidden layer of product units feeding into a subsequent layer of summing units (Fig. 1b). We do not envision product units replacing summing units altogether; the attractions are rather in mixing them, particularly in alternating layers so that we can form weighted sums of arbitrary products. This is analogous to alternating disjunctive and conjunctive layers in general forms for logical functions.

2 Theory

In order to discuss the equations governing learning in product units it is convenient to rewrite equation 1 in terms of exponentials and logarithms.

y = e^{Π_{i=1}^{n}p_{i} log_{e} x_{i}} (2.1)

In this form we can see that a product unit acts like a summing unit whose inputs are preprocessed by taking logarithms, and whose output is passed through an exponential, rather than a squashing function. If x_{i} is negative then log_{e} x_{i} = log_{e} |x_{i}| + iπ, which is complex, and so equation (2.1) becomes

y = e^{∑ p_{i} log |x_{i}|}(cos π ∑_{i|x_{i}<0} p_{i} + i sin π ∑_{i|x_{i}<0} p_{i}) (2.2)

We want to be able to consider negative inputs because the non-linear characteristics of product units, which we want to use computationally, are centered on the origin. There are two main alternatives to dealing with the resulting complex-valued expressions. One is to handle the whole network in the complex domain, and at the end fit the real component to the data (either ignoring the complex component or fitting it to 0). The other is to keep the system in the real domain by ignoring the imaginary component of the output from each product unit, restricting us to real-valued weights. For most problems the latter seems preferable. In the case where all the exponents p_{i} are integral, as with a true polynomial term, then the approximation of ignoring the imaginary component is exact. Given this, it can be viewed that we are extending the space of polynomial terms to fractional exponents in a well behaved fashion, so as to permit smooth learning of the exponents. Additionally, in simulations we seem to gain nothing for the added complexity of working in the complex domain (it doubles the number of equations and weight variables). On the other hand, for some physical problems it may be appropriate to consider complex-valued networks.

In order to train the weights by gradient descent we need to be able to calculate two sets of derivatives for each unit. First we need the derivative of the output y with respect to each weight p_{i} so as to be able to update the weights. Second we need the derivative with respect to each input x_{i} so as to be able to propagate the error back to previous layers using the chain rule. Let us set I_{i} equal to 1 if x_{i} is negative, otherwise 0, and define U, V by

U = ∑_{i=1}^{N} p_{i} log_{e} |x_{i}| V = ∑_{i=1}^{N} p_{i}I_{i}

Then the equations we need for the real-valued version are

y = e^{U} cos πV  (2.3)
\frac{dy}{dp_{i}} = log_{e} |x_{i}|e^{U} cos πV − I_{i}πe^{U} sin πV
\frac{dy}{dx_{i}} = |x_{i}|^{−1} p_{i}e^{U} cos πV

It is possible to add an extra constant input to a product unit, corresponding to the bias for a summing unit. In this case the appropriate constant is -1, since a positive value would simply multiply the output by a scalar, which is irrelevant when there is a variable multiplicative weight from the output to a higher level summing unit. Although this multiplicative bias is often eventually redundant, we have found it to be important during the learning process for some tasks, such as the symmetry task (see below and Fig. 2).

Figure 2: Examples of product unit networks that solve “hard” binary problems. In each case there is a standard thresholded summing output unit (Σ) and one or more “hidden” product units (Π). The weight values are shown by each arrow, and there is also a constant bias value shown inside each unit’s circle. Product unit biases can be considered to have constant −1 input (see text). In each case the network was found by training from data. (a) Parity. The output is 1 if an even number of inputs is on, 0 if an odd number is on. (b) Symmetry. The output is 1 if the input pattern is mirror symmetric (as shown here), 0 otherwise. For summing unit network solutions to the symmetry and parity problems see (Rumelhart, Hinton, and Williams). (c) Multiplexer. Here the values of the two lefthand input units encode in binary fashion which of the four right hand inputs is transmitted to the output. Examples are shown. Where there is a dot the value of the input unit (1 or −1) is irrelevant. An “x” stands for either 1 or −1.

One property that we have lost with product units is that they are vulnerable to translation and rotation of the input space, in the sense that a learnable problem may no longer be learnable after translation. Summing units with a threshold are not vulnerable to such transformations. If desired, we can regain translational invulnerability by introducing new parameters μ_{i} to allow an explicit change of origin. This would replace x_{i} by (x_{i} − μ_{i}) in all the above equations. We can once again learn the μ_{i} by gradient descent. With the μ_{i} present a product unit can approximate a linear threshold unit arbitrarily closely, by working on only a small region of the exponential function. Alternatively, we can notice that rotational and translational vulnerability of single product units is in part compensated for if a number of them are being used in parallel, which will often be the case. This is because a single product transforms to a set of products in a rotated and translated space. In any case, there may be some benefit to the asymmetry of a product unit’s capabilities under affine transformation of the input space. For non-geometric sets of input variables this type of extra computational power may well be useful.

3 Results

Many of the problems that are studied using networks use Boolean input. For product units it is best to use Boolean values −1 and 1, in which case the exponential terms in equations (3) disappear, and the units behave like cosine summing units with 1 and 0 inputs. Examples of the use of product units for learning Boolean functions are provided by networks that learn the parity and symmetry functions. These functions are hard to learn using summing units: the parity function requires as many hidden units as inputs, while symmetry requires 2 hidden units, but often gets stuck in a local minimum unless more are given. Both functions are learned rapidly using a

Figure 3: Performance on a task with real-valued input: learning a circular domain. In each case the network and a plot of its response function over the range −2.0 to 2.0 are shown. A variety of local minima were found using two product unit networks (which in theory could solve the problem exactly), whereas there was only one solution found using two summing units. Although non-optimal, the product unit solutions were always better than the summing units solutions. (a) The ideal product unit network, used to generate the data. (b) An example of a good empirical solution with product units (2% misclassified, MSE 0.03). (c) An example of a poor product unit local minimum (13% misclassified, MSE 0.10).

(d) The solution essentially always obtained with two summing hidden units (38% misclassified, MSE 0.24).

single product hidden unit (Fig. 2 a,b). A good example of a problem that multilayer nets with product units find good solutions for is the multiplexing task shown in figure 2c. Here two of the inputs code which of the four remaining inputs to output. This task has a biological interpretation as an attentional mechanism, and is therefore relevant for computational models of sensory information processing. Indeed, the neurobiological interpretation of just the type of hybrid net used here (see below) suggests a substrate and mechanism for attentional processes in the brain.

We can measure the informational capacity of a unit by the number of random Boolean patterns that it can learn (more precisely, the number at which the probability of storing them all perfectly drops to a half; Mitchison and Durbin 1989). For a single summing unit with N inputs the capacity can be shown theoretically to be 2N (Cover 1965). The empirical capacity of a single product unit is significantly higher than this at around 3N (table 1). The relative improvement is maintained in a comparison of multilayer networks with product hidden units compared with ones consisting purely of summing units (table 1), indicating that product units cooperate well with summing units.

We can also consider the performance of product units when the inputs x_{i} are real valued. An example is the ability of a network with two product hidden units to learn to respond to a circular region around the origin. In fact it appears that there are many local minima for this problem, and although the network occasionally finds the “correct” solution (Fig. 3a), it more often finds other solutions such as those shown in figure 3b,c. However these solutions are not bad: the average mean square error (MSE) for product unit networks is 0.09 (average of 10) with 88% correct data classification (whether the output is the correct side of 0.5) whereas the best corresponding summing unit network gives an MSE of 0.24, and only 62% correct classification.

Product unit Summing unit
Structure M  percentage  percentage
6 1  12  92  18
18  49  3
20  28  1
12 1  24  100  29
36  66  0
40  20  0
6 2 1  24  100  2
36  82  0
40  58  0
6 2 1  24  100  0
fixed  36  45  0
output 40  14  0

Table 1: Results on storage of random data. The number of successful storage attempts in 100 trials is shown in the last two columns for various net structures and numbers of vectors, M. Storage is termed successful if all input vectors produce output on the correct side of 0.5. Input vectors were random, x_{i} = −1 or 1, and output values for each vector were random 0 or 1. The “6 1” and “12 1” nets had a single learning unit with 6 or 12 inputs. For these comparisons the output of a product unit was passed through the standard summing unit squashing function, e^{x}/(1 + e^{x}). The single summing units do not attain the M=2N theoretical limit (Cover 1965), presumably because the squashing function output creates local minima not present for a simple perceptron. The “6 2 1” nets had 2 hidden units (either product or summing) and one summing output unit, which was trainable for the first set of results, and fixed with all weights equal for the second set. These results indicate that storage capacity for product units is at least 3 bits per weight, as opposed to no more than 2 bits per weight for summing units, and that fixed output units do not drastically reduce computational power in multilayer networks.

4 Discussion

We have proposed a new type of computational unit to be used in layered networks along with standard thresholded summing units. The underlying idea behind this unit is that it can learn to represent any generalized polynomial term in the inputs. It can therefore help to form a better representation of the data in cases where higher order combinations of the inputs are significant. Unlike sigma-pi units, which to some extent perform the same task, product units do not increase the number of free parameters, since there is only one weight per input, as with summing units. Although we have been unable to prove that product units are guaranteed to learn a learnable task, as can be shown for a single simplified summing unit (Rosenblatt 1962), we have shown that product units can be trained efficiently using gradient descent, and allow much simpler solutions of various standard learning problems. In addition, as isolated units they have a higher empirical learning capacity than summing units, and they act efficiently to create a hidden layer representation for an output summing unit (table 1).

There is a natural neurobiological interpretation for this type of combination of product and summing units in terms of a single neuron. Local regions of dendritic arbor could act as product units whose outputs are summed at the soma. Equation (2.1) shows that a product unit acts like a summing unit with an exponential output function, whose inputs are preprocessed by passing them through a log function. Both these transfer functions are realistic. When there are voltage sensitive dendritic channels, such as NMDA receptors, the post-synaptic voltage response is qualitatively exponential around a critical voltage level (Collingridge and Bliss 1987); an effect that will be influenced by other local input apart from the specific input at the synapse. Presynaptically, there are saturation effects giving an approximately logarithmic form to the voltage dependency of transmitter release. In fact just these features have been presented as problems with the standard thresholded summing model of neurons. Standard summing inputs could still be made using neurotransmitters that do not stimulate voltage sensitive channels. As far as learning in the biological model is concerned, it is acceptable that the second layer summing weights, corresponding to the degree of influence of dendritic regions at the soma, are not very variable. Systems with fixed summing output layers are nearly as computationally powerful as fully variable ones, both in theory (Mitchison and Durbin 1989), and simulations (table 1). Learning at the input synapses is still essentially Hebbian (equation 2.2b), with an additional term when the input x_{i} is negative. Although the periodic form of this term appears unbiological, some type of additional term is not unreasonable for inhibitory input, which may well have different learning characteristics. Alternatively, it might be that the learning model only applies to excitatory input. Further consideration of this neurobiological model is required, but it seems likely that this approach will lead to a plausible new computational model of a neuron that is potentially much more powerful than the standard McCulloch-Pitts model.

One possible criticism of introducing a new type of unit is that it is trivially going to improve the representational capabilities of the networks: one can always improve a fit to data by making a model more complex, and this is rarely worth the price of throwing away elegance. The defence to this must be that the extension is in some sense natural, which we believe that it is. Product units provide the continuous analogy to general Boolean conjunctions in the same way that summing units are continuous analogs of Boolean disjunctions (although both continuous forms are much more powerful, sufficiently so that either can represent any arbitrary disjunction or conjunction on Boolean input). In fact many of the proofs of capabilities of networks to perform general tasks rely on the “abuse” of thresholded summing units to perform multiplicative or conjunctive tasks, often in alternating layers with units being used in an additive or disjunctive fashion. Such proofs will be much simpler for networks with both product and summing units, indicating that such networks are more appropriate for finding simple models of general data. It might be argued that in opening up such generality the special properties of learning networks will be lost, because they no longer provide strong constraints on the type of model that is created. We feel that this misses the point. The real justification for layered network models appears when a number of different output functions are fit to some set of data. By using a layered model the fit of each function influences and constrains the fit of all the others. If there is some underlying natural representation this will be modeled by the intermediate layers, since it will be appropriate for all the output functions. This cross-constraining of learning is not easily available in many other systems, which therefore miss out on a vast amount of data that is relevant, although indirectly so. Product units provide a natural extension of the use of summing units in this framework.

Acknowledgments

R.M.D is a Lucille P. Markey Visiting Fellow at Stanford University. We thank T.J. Sejnowski for pointing out the neurobiological interpretation.

References

Collingridge, G.L. and T.V.P. Bliss. 1987. NMDA receptors — their role in long-

term potentiation. Trends Neurosci. 10, 288–293. Cover, T. 1965. Geometrical and Statistical Properties of Systems of Linear

Inequalities with Applications in Pattern Recognition. IEEE Trans. Elect. Comp. 14, 326–334.

Hanson, S.J. and D.J. Burr. 1987. Knowledge Representation in Connectionist

Networks. Technical Report Bell Communication Research, Morristown, NJ. Maxwell, T., C.G. Giles, and Y.C. Lee. 1987. Generalization in Neural Networks,

the Contiguity Problem. In: Proceedings IEEE First International Conference on Neural Networks 2, 41–45.

Mitchison, G.J. and R.M. Durbin. 1988. Bounds on the Learning Capacity of

Some Multilayer Networks. Biological Cybernetics, in press. Rosenblatt, F. 1962. Principles of Neurodynamics. New York: Spartan. Rumelhart, D.E., G.E. Hinton, and J.L. McClelland. 1986. A General Framework

for Parallel Distributed Processing. In: Parallel Distributed Processing 1, 45–76. Cambridge, MA, and London: MIT Press.

Rumelhart, D.E., G.E. Hinton, and R.J. Williams. 1986. Learning Internal Representations by Error Propagation. In: Parallel Distributed Processing 1, 318–362. Cambridge, MA, and London: MIT Press.

128 Richard Durbin and David E. Rumelhart

Received 11 November; accepted 17 December 1988.

Communicated by Scott Kirkpatrick

Deterministic Boltzmann Learning Performs Steepest Descent in Weight-Space

Geoffrey E. Hinton

Department of Computer Science, University of Toronto, 10 King’s College Road, Toronto M5S 1A4, Canada

The Boltzmann machine learning procedure has been successfully applied in deterministic networks of analog units that use a mean field approximation to efficiently simulate a truly stochastic system (Peterson and Anderson 1987). This type of “deterministic Boltzmann machine” (DBM) learns much faster than the equivalent “stochastic Boltzmann machine” (SBM), but since the learning procedure for DBM’s is only based on an analogy with SBM’s, there is no existing proof that it performs gradient descent in any function, and it has only been justified by simulations. By using the appropriate interpretation for the way in which a DBM represents the probability of an output vector given an input vector, it is shown that the DBM performs steepest descent in the same function as the original SBM, except at rare discontinuities. A very simple way of forcing the weights to become symmetrical is also described, and this makes the DBM more biologically plausible than back-propagation (Werbos 1974; Parker 1985; Rumelhart et al. 1986).

1 Introduction

The promising results obtained by Peterson and Anderson (Peterson and Anderson 1987) using a DBM are hard to assess because they present no mathematical guarantee that the learning does gradient descent in any error function (except in the limiting case of a very large net with small random weights). It is quite conceivable that in a DBM the computed gradient might have a small systematic difference from the true gradient of the normal performance measure for each training case, and when these slightly incorrect gradients are added together over many cases their resultant might bear little relation to the resultant of the true case-wise gradients (see Fig. 1).

2 The Learning Procedure for Stochastic Boltzmann Machines

A Boltzmann machine (Hinton and Sejnowski 1986) is a network of symmetrically connected binary units that asynchronously update their states according to a stochastic decision rule. The units have states of 1 or 0 and the probability that unit i adopts the state 1 is given by

p_{i} = σ(\frac{1}{T} ∑_{j} s_{j}w_{ij}) (2.1)

where s_{j} is the state of the j^{th} unit, w_{ij} is the weight on the connection between the j^{th} and the i^{th} unit, T is the “temperature” and σ is a smooth non-linear function defined as

σ(x) = \frac{1}{1 + e^{−x}} (2.2)

If the binary states of units are updated asynchronously and repeatedly using equation 2.1, the network will reach “thermal equilibrium” so that the relative probabilities of global configurations are determined by their energies according to the Boltzmann distribution:

\frac{P_{α}}{P_{β}} = \frac{e^{−E_{α}/T}}{e^{−E_{β}/T}} (2.3)

where P_{α} is the probability of a global configuration and E_{α} is its energy defined by

E_{α} = − ∑_{i<j} s_{i}^{α}s_{j}^{α}w_{ij} (2.4)

where s_{i}^{α} is the binary state of unit i in the α^{th} global configuration, and bias terms are ignored because they can always be treated as weights on connections from a permanently active unit.

At any given temperature, T, the Boltzmann distribution is the one that minimizes the Helmholtz free energy, F, of the distribution. F is defined by the equation

F = ⟨E⟩ − T H (2.5) where ⟨E⟩ is the expected value of the energy given the probability distribution over configurations and H is the entropy of the distribution. It can be shown that minima of F (which will be denoted by F^{∗}) satisfy the equation

[figure: a; b; a + b; â; b̂; â + b̂] Figure 1: The true gradients of the performance measure are a and b for two training cases. Even fairly accurate estimates, â and b̂, can have a resultant that points in a very different direction.

e^{−F^{∗}/T} = ∑_{α} e^{−E_{α}/T} (2.6)

In a stochastic Boltzmann machine, the probability of an output vector, O_{β}, given an input vector, I_{α} is represented by

P^{−}(O_{β}|I_{α}) = \frac{e^{−F_{αβ}^{∗}/T}}{e^{−F_{α}^{∗}/T}} (2.7)

where F_{αβ}^{∗} is the minimum free energy with I_{α} and O_{β} clamped, and F_{α}^{∗} is the minimum free energy with just I_{α} clamped. A very natural way to observe P^{−}(O_{β}|I_{α}) is to allow the network to reach thermal equilibrium with I_{α} clamped, and to observe the probability of O_{β}. The key to Boltzmann machine learning is the simple way in which a small change to a weight, w_{ij}, affects the free energy and hence the log probability of an output vector in a network at thermal equilibrium.

\frac{∂F^{∗}}{∂w_{ij}} = −⟨s_{i}s_{j}⟩ (2.8)

where ⟨s_{i}s_{j}⟩ is the expected value of s_{i}s_{j} in the minimum free energy distribution. The simple relationship between weight changes and log probabilities of output vectors makes it easy to teach the network an input-output mapping. The network is “shown” the mapping that it is required to perform by clamping an input vector on the input units and clamping the required output vector on the output units (with the appropriate conditional probability). It is then allowed to reach thermal equilibrium at T = 1, and at equilibrium each connection measures how often the units it connects are simultaneously active. This is repeated for all input-output pairs so that each connection can measure ⟨s_{i}s_{j}⟩^{+}, the expected probability, averaged over all cases, that unit i and unit j are simultaneously active at thermal equilibrium when the input and output vectors are both clamped. The network must also be run in just the same way but without clamping the output units to measure ⟨s_{i}s_{j}⟩^{−}, the expected probability that both units are active at thermal equilibrium when the output vector is determined by the network. Each weight is then updated by

Δw_{ij} = ϵ(⟨s_{i}s_{j}⟩^{+} − ⟨s_{i}s_{j}⟩^{−}) (2.9)

It follows from equation 2.7 and equation 2.8 that if ϵ is sufficiently small this performs steepest descent in an information theoretic measure, G, of the difference between the behavior of the output units when they are clamped and their behavior when they are not clamped.

G = ∑_{α,β} P^{+}(I_{α}, O_{β}) log \frac{P^{+}(O_{β} | I_{α})}{P^{−}(O_{β} | I_{α})} (2.10)

where I_{α} is a state vector over the input units, O_{β} is a state vector over the output units, P^{+} is a probability measured at thermal equilibrium when both the input and output units are clamped, and P^{−} is a probability measured when only the input units are clamped.

Stochastic Boltzmann machines learn slowly, partly because of the time required to reach thermal equilibrium and partly because the learning is driven by the difference between two noisy variables, so these variables must be sampled for a long time at thermal equilibrium to reduce the noise. If we could achieve the same simple relationships between log probabilities and weights in a deterministic system, learning would be much faster.

3 Mean field theory

Under certain conditions, a stochastic system can be approximated by a deterministic one by replacing the stochastic binary variables of equation 2.1 by deterministic real-valued variables that represent their mean values

p_{i} = σ(\frac{1}{T} ∑_{j} p_{j}w_{ij}) (3.1)

We could now perform discrete, asynchronous updates of the p_{i} using equation 3.1 or we could use a synchronous, discrete time approximation of the set of differential equations

\frac{dp_{i}}{dt} = −p_{i} + σ(\frac{1}{T} ∑_{j} p_{j}w_{ij}) (3.2)

We shall view the p_{i} as a representation of a probability distribution over all binary global configurations. Since many different distributions can give rise to the same mean values for the p_{i} we shall assume that the distribution being represented is the one that maximizes the entropy, subject to the constraints imposed on the mean values by the p_{i}. Equivalently, it is the distribution in which the p_{i} are treated as the mean values of independent stochastic binary variables. Using equation 2.5 we can calculate the free energy of the distribution represented by the state of a DBM (at T = 1).

F = − ∑_{i<j} p_{i}p_{j}w_{ij} + ∑_{i}[p_{i} log(p_{i}) + (1 − p_{i}) log(1 − p_{i})] (3.3)

Although the dynamics of the system defined by equation 3.2 do not consist in following the gradient of F, it can be shown that it always moves in a direction that has a positive cosine with the gradient of −F so it settles to one of the minima of F (Hopfield 1984).

Mean field systems are normally viewed as approximations to systems that really contain higher order statistics, but they can also be viewed as exact systems that are strongly limited in the probability distributions that they can represent because they use only N real values to represent distributions over 2^{N} binary states. Within the limits of their representational powers, they are an efficient way of manipulating these large but constrained probability distributions.

4 Deterministic Boltzmann machine learning

In a DBM, we shall define the representation of P^{−}(O_{β}|I_{α}) exactly as in equation 2.7, but now F_{αβ}^{∗} and F_{α}^{∗} will refer to the free energies of the particular minima that the network actually settles into. Unfortunately, in a DBM this representation is no longer equivalent to the obvious way of defining P^{−}(O_{β}|I_{α}) which is to clamp I_{α} on the input units, settle to a minimum of F_{α}, and interpret the values of the output units as a representation of a probability distribution over output vectors, using the maximum entropy assumption.

The reason for choosing the first definition rather than the second is this: Provided the stable states that the network settles to do not change radically when the weights are changed slightly, it can now be shown that the mean field version of the Boltzmann machine learning procedure changes each weight in proportion to the gradient of log P^{−}(O_{β}|I_{α}), which is exactly what is required to perform steepest descent in the performance measure G defined in equation 2.10.

When w_{ij} is incremented by an infinitessimal amount ϵp_{i}p_{j} two things happen to F^{∗} (see Fig. 2). First, the mean energy of the probability distribution represented by the state of the DBM is decreased by ϵp^{2}_{i}p^{2}_{j} and, to first order, the mean energy of all nearby states of the DBM is decreased by the same amount. Second, the values of the p_{i} at which F is minimized change slightly so the stable state moves slightly. But, to first order, this

Figure 2: The effect of a small weight increment on a free energy minimum. To first order, the difference in free energy between A and C is equal to the difference between A and B. At a minimum, small changes in the distribution (sideways movements) have negligible effects on free energy, even though they may have significant (and opposite) effects on the energy and the entropy terms.

[figure: C; B; A]

Figure 3: A small increase in the free energy of B can prevent a network from settling to the free energy minimum at C. So small changes in weights occasionally cause large changes in the final free energy.

movement of the minimum has no effect on the value of F because we are at a stable state in which ∂F/∂p_{i} = 0 for all i. Hence the effect of incrementing w_{ij} by ϵp_{i}p_{j} is simply to create a new, nearby stable state which, to first order, has a free energy that is ϵp_{i}^{2}p_{j}^{2} lower than the old stable state. So, assuming T = 1, if all weights are incremented by ϵp_{i}^{+}p_{j}^{+} in the stable state that has I_{α} and O_{β} clamped and are decremented by ϵp_{i}^{−}p_{j}^{−} in the stable state that has only I_{α} clamped we have, from equation 2.7

Δw_{ij} = ϵ(p_{i}^{+}p_{j}^{+} − p_{i}^{−}p_{j}^{−}) = ϵ\frac{∂ log P^{−}(O_{β}|I_{α})}{∂w_{ij}} (4.1)

This ensures that by making ϵ sufficiently small the learning procedure can be made to approximate steepest descent in G arbitrarily closely.

The derivation above is invalid if, with the same boundary conditions, a small change in the weights causes the network to settle to a stable state with a very different free energy. This can happen with energy landscapes like the one shown in figure 3. A small weight change caused by some other training case can cause a free energy barrier that prevents the network finding the deeper minimum. In simulations that repeatedly sweep through a fixed set of training cases, it is easy to avoid this phenomenon by always starting the network at the stable state that was found using the same boundary conditions on the previous sweep. This has the added advantage of eliminating almost all the computation required to settle on a stable state, and thus making a settling almost as fast as a forward pass of the back-propagation procedure.

Unfortunately, starting from the previous best state does not eliminate the possibility that a small free-energy barrier will disappear and a much better state will then be found when the network is running with the output units unclamped. This can greatly increase the denominator in equation 2.7 and thus greatly decrease the network’s representation of the probability of a correct output vector. It should also be noted that it is conceivable that, due to local minima in the free energy landscape, F_{α}^{∗} may actually be higher than F_{αβ}^{∗}, in which case the network’s representation of P^{−}(O_{β}|I_{α}) will exceed 1.

In practice this does not seem to be a problem, and DBM’s compare very favorably with back-propagation in learning speed.

5 Symmetry of the Weights

We have assumed that the weight of the connection from i to j is the same as the weight from j to i. If these weights are asymmetric, the learning procedure will automatically symmetrize them provided that, after each weight update, each weight is decayed slightly towards zero by an amount proportional to its magnitude. This favors “simple” networks that have small weights, and it also reduces the energy barriers that create local minima. Weight-decay always reduces the difference between w_{ij} and w_{ji}, and since the learning rule specifies weight changes that are exactly symmetrical in i and j, the two weights will always approach one another. Williams (1985) makes a similar argument about a different learning procedure. Thus the symmetry that is required to allow the network to compute its own error derivatives is easily achieved, whereas achieving symmetry between forward and backward weights in back-propagation networks requires much more complex schemes (Parker 1985).

6 Acknowledgments

I thank Christopher Longuet-Higgins, Conrad Galland, Scott Kirkpatrick, and Yann Le Cun for helpful comments. This research was supported by grants from the Ontario Information Technology Research Center, the National Science and Engineering Research Council of Canada, and DuPont. Geoffrey Hinton is a fellow of the Canadian Institute for Advanced Research.

References

Hinton, G.E. and T.J. Sejnowski. 1986. Learning and relearning in Boltzmann machines. In: Parallel Distributed Processing: Explorations in the Microstructure of Cognition, Volume 1: Foundations, eds. D.E. Rumelhart, J.L. McClelland, and the PDP group. Cambridge, MA: MIT Press.

Hopfield, J.J. 1984. Neurons with Graded Response Have Collective Computational Properties like Those of Two-state Neurons. Proceedings of the National Academy of Sciences U.S.A. 81, 3088–3092.

Parker, D.B. 1985. Learning-logic. Technical Report TR-47, Sloan School of Man-

agement, Massachusetts Institute of Technology, Cambridge, MA. Peterson, C. and J.R. Anderson. 1987. A Mean Field Theory Learning Algorithm

for Neural Networks. Complex Systems 1, 995–1019. Rumelhart, D.E., G.E. Hinton, and R.J. Williams. 1986. Learning Representations

by Back-propagating Errors. Nature 323, 533–536.

Werbos, P.J. 1974. Beyond Regression: New Tools for Prediction and Analysis in

the Behavioral Sciences. PhD Thesis, Harvard University, Cambridge, MA. Williams, R.J. 1985. Feature Discovery through Error-correction Learning. Tech-

nical Report ICS-8501, Institute for Cognitive Science, University of California, San Diego, La Jolla, CA.

Received 5 December; accepted 15 December 1988.

Communicated by Les Valiant

What Size Net Gives Valid Generalization?

Eric B. Baum^{∗}

Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA 91109, USA

David Haussler

Department of Computer and Information Sciences, University of California, Santa Cruz, CA 95064, USA

We address the question of when a network can be expected to generalize from m random training examples chosen from some arbitrary probability distribution, assuming that future test examples are drawn from the same distribution. Among our results are the following bounds on appropriate sample vs. network size. Assume 0 < ϵ ≤ 1/8. We show that if m ≥ O(\frac{W}{ϵ} log \frac{N}{ϵ}) random examples can be loaded on a feedforward network of linear threshold functions with N nodes and W weights, so that at least a fraction 1 − \frac{ϵ}{2} of the examples are correctly classified, then one has confidence approaching certainty that the network will correctly classify a fraction 1 − ϵ of future test examples drawn from the same distribution. Conversely, for fully-connected feedforward nets with one hidden layer, any learning algorithm using fewer than Ω(\frac{W}{ϵ}) random training examples will, for some distributions of examples consistent with an appropriate weight choice, fail at least some fixed fraction of the time to find a weight choice that will correctly classify more than a 1 − ϵ fraction of the future test examples.

1 Introduction

In the last few years, many diverse real-world problems have been attacked by back propagation. For example “expert systems” have been produced for mapping text to phonemes (Sejnowski and Rosenberg 1987), for determining the secondary structure of proteins (Qian and Sejnowski 1988), and for playing backgammon (Tesauro and Sejnowski 1988). In such problems, one starts with a training database, chooses (by making an educated guess) a network, and then uses back propagation to load as many of the training examples as possible onto the network. The hope is that the network so designed will generalize to predict correctly on future examples of the same problem. This hope is not always realized.

∗Current address: Department of Physics, Princeton University, Princeton, NJ 08540.

Neural Computation 1, 137–146 (1989) \begin{matrix}c \\ ◯ \end{matrix} 1989 Massachusetts Institute of Technology

We address the question of when valid generalization can be expected. Given a training database of m examples, what size net should we attempt to load these on? We will assume that the examples are drawn from some fixed but arbitrary probability distribution, that the learner is given some accuracy parameter ϵ, and that his goal is to produce with high probability a feedforward neural network that predicts correctly at least a fraction 1−ϵ of future examples drawn from the same distribution. These reasonable assumptions are suggested by the protocol proposed by Valiant for learning from examples (Valiant 1984). However, here we do not assume the existence of any “target function”; indeed the underlying process generating the examples may classify them in a stochastic manner, as in e.g. (Duda and Hart 1973).

Our treatment of the problem of valid generalization will be quite general in that the results we give will hold for arbitrary learning algorithms and not just for backpropagation. The results are based on the notion of capacity introduced by Cover (Cover 1965) and developed by Vapnik and Chervonenkis (Vapnik and Chervonekis 1971; Vapnik 1982). Recent overviews of this theory are given in (Devroye 1988; Blumer et al. 1987b; Pollard 1984), from the various perspectives of pattern recognition, Valiant’s computational learning theory, and pure probability theory, respectively. This theory generalizes the simpler counting arguments based on cardinality and entropy used in (Blumer et al. 1987a; Denker et al. 1987), in the latter case specifically to study the question of generalization in feedforward nets (see Vapnik 1982 or Blumer et al. 1987b).

The particular measures of capacity we use here are the maximum number of dichotomies that can be induced on m inputs, and the Vapnik-Chervonenkis (VC) Dimension, defined below. We give upper and lower bounds on these measures for classes of networks obtained by varying the weights in a fixed feedforward architecture. These results show that the VC dimension is closely related to the number of weights in the architecture, in analogy with the number of coefficients or “degrees of freedom” in regression models. One particular result, of some interest independent of its implications for learning, is a construction of a near minimal size net architecture capable of implementing all dichotomies on a randomly chosen set of points on the n-hypercube with high probability.

Applying these results, we address the question of when a network can be expected to generalize from m random training examples chosen from some arbitrary probability distribution, assuming that future test examples are drawn from the same distribution. Assume 0 < ϵ ≤ 1/8. We show that if m ≥ O(\frac{W}{ϵ} log \frac{N}{ϵ}) random examples can be loaded on a feedforward network of linear threshold functions with N nodes and W weights, so that at least a fraction 1 − \frac{ϵ}{2} of the examples are correctly classified, then one has confidence approaching certainty that the network will correctly classify a fraction 1 − ϵ of future test examples drawn from the same distribution. Conversely, for fully-connected feedforward nets with one hidden layer, any learning algorithm using fewer than Ω(\frac{W}{ϵ}) random training examples will, for some distributions of examples consistent with an appropriate weight choice, fail at least some fixed fraction of the time to find a weight choice that will correctly classify more than a 1 − ϵ fraction of the future test examples.

Ignoring the constant and logarithmic factors, these results suggest that the appropriate number of training examples is approximately the number of weights times the inverse^{1} of the accuracy parameter, ϵ. Thus, for example, if we desire an accuracy level of 90%, corresponding to ϵ = 0.1, we might guess that we would need about 10 times as many training examples as we have weights in the network. This is in fact the rule of thumb suggested by Widrow (1987), and appears to work fairly well in practice. At the end of Section 3, we briefly discuss why learning algorithms that try to minimize the number of non-zero weights in the network (Rumelhart 1987; Hinton 1987) may need fewer training examples.

2 Definitions

We use ln to denote the natural logarithm and log to denote the logarithm base 2. We define an example as a pair (x⃗, a), x⃗ ∈ ℜ^{n}, a ∈ {−1, +1}. We define a random sample as a sequence of examples drawn independently at random from some distribution D on ℜ^{n} × {−1, +1}. Let f be a function from ℜ^{n} into {−1, +1}. We define the error of f, with respect to D, as the probability a ≠ f(x⃗) for (x⃗, a) a random example.

Let F be a class of {−1, +1}-valued functions on ℜ^{n} and let S be a set of m points in ℜ^{n}. A dichotomy of S induced by f ∈ F is a partition of S into two disjoint subsets S^{+} and S^{−} such that f(x⃗) = +1 for x⃗ ∈ S^{+} and f(x⃗) = −1 for x⃗ ∈ S^{−}. By Δ_{F} (S) we denote the number of distinct dichotomies of S induced by functions f ∈ F, and by Δ_{F} (m) we denote the maximum of Δ_{F} (S) over all S ⊂ ℜ^{n} of cardinality m. We say S is shattered by F if Δ_{F} (S) = 2^{|S|}, i.e. all dichotomies of S can be induced by functions in F. The Vapnik-Chervonenkis (VC) dimension of F, denoted V Cdim(F), is the cardinality of the largest S ⊂ ℜ^{n} that is shattered by F, i.e. the largest m such that Δ_{F} (m) = 2^{m}.

A feedforward net with input from ℜ^{n} is a directed acyclic graph G with an ordered sequence of n source nodes (called inputs) and one sink (called the output). Nodes of G that are not source nodes are called computation nodes, nodes that are neither source nor sink nodes are called hidden nodes. With each computation node n_{i} there is associated a function f_{i} : ℜ^{indegree(n_{i})} → {−1, +1}, where indegree(n_{i}) is the number of incoming edges for node n_{i}. With the net itself there is associated a function f : ℜ^{n} → {−1, +1} defined by composing the f_{i}’s in the obvious way, assuming that component i of the input x⃗ is placed at the i^{th} input node.

1It should be noted that our bounds differ significantly from those given in (Devroye 1988) in that the latter exhibit a dependence on the inverse of ϵ^{2}. This is because we derive our results from Vapnik’s theorem on the uniform relative deviation of frequencies from their probabilities (Vapnik 1982; see Appendix A3 of Blumer et al. 1987b), giving sharper bounds as ϵ approaches 0.

A feedforward architecture is a class of feedforward nets all of which share the same underlying graph. Given a graph G we define a feedforward architecture by associating to each computation node n_{i} a class of functions F_{i} from ℜ^{indegree(n_{i})} to {−1, +1}. The resulting architecture consists of all feedforward nets obtained by choosing a particular function f_{i} from F_{i} for each computation node n_{i}. We will identify an architecture with the class of functions computed by the individual nets within the architecture when no confusion will arise.

3 Conditions Sufficient for Valid Generalization

Theorem 1. Let F be a feedforward architecture generated by an underlying graph G with N ≥ 2 computation nodes and F_{i} be the class of functions associated with computation node n_{i} of G, 1 ≤ i ≤ N. Let d = ∑_{i=1}^{N} V Cdim(F_{i}). Then Δ_{F} (m) ≤ ∏_{i=1}^{N} Δ_{F_{i}}(m) ≤ (Nem/d)^{d} for m ≥ d, where e is the base of the natural logarithm.

Proof. Assume G has n input nodes and that the computation nodes of G are ordered so that node n_{i} receives inputs only from input nodes and from computation nodes n_{j}, 1 ≤ j ≤ i − 1. Let S be a set of m points in ℜ^{n}. The dichotomy induced on S by the function in node n_{1} can be chosen in at most Δ_{F_{1}}(m) ways. This choice determines the input to node n_{2} for each of the m points in S. The dichotomy induced on these m inputs by the function in node n_{2} can be chosen in at most Δ_{F_{2}}(m) ways, etc. Any dichotomy of S induced by the whole network can be obtained by choosing dichotomies for each of the n_{i}’s in this manner, hence Δ_{F} (m) ≤ ∏_{i=1}^{N} Δ_{F_{i}}(m).

By a theorem of Sauer (1972), whenever V Cdim(F) = k < ∞, Δ_{F} (m) ≤ (em/k)^{k} for all m ≥ k (see also Blumer et al. 1987b). Let d_{i} = V Cdim(F_{i}), 1 ≤ i ≤ N. Thus d = ∑_{i=1}^{N} d_{i}. Then ∏_{i=1}^{N} Δ_{F_{i}}(m) ≤ ∏_{i=1}^{N}(em/d_{i})^{d_{i}} for m ≥ d. Using the fact that ∑_{i=1}^{N} −α_{i}logα_{i} ≤ logN whenever α_{i} > 0, 1 ≤ i ≤ N, and ∑_{i=1}^{N} α_{i} = 1, and setting α_{i} = d_{i}/d, it is easily verified that ∏_{i=1}^{N} d_{i}^{d_{i}} ≥ (d/N)^{d}. Hence ∏_{i=1}^{N}(em/d_{i})^{d_{i}} ≤ (Nem/d)^{d}.

Corollary 3. Let F be the class of all functions computed by feedforward nets defined on a fixed underlying graph G with E edges and N ≥ 2 computation nodes, each of which computes a linear threshold function. Let W = E + N (the total number of weights in the network, including one weight per edge and one threshold per computation node). Then Δ_{F} (m) ≤ (Nem/W)^{W} for all m ≥ W and V Cdim(F) ≤ 2W log(eN).

Proof. The first inequality follows directly from Theorem 1 using the fact that V Cdim(F) = k + 1 when F is the class of all linear threshold functions on ℜ^{k} (see e.g. Wenocur and Dudley 1981). For the second inequality, it is easily verified that for N ≥ 2 and m = 2W log(eN), (Nem/W)^{W} < 2^{m}. Hence this is an upper bound on V Cdim(F).

Using VC dimension bounds given in (Wenocur and Dudley 1981), related corollaries can be obtained for nets that use spherical and other types of polynomial threshold functions. These bounds can be used in the following.

Theorem 2. (Vapnik 1982) (see Blumer et al. 1987b; Theorem A3.3): Let F be a class of functions^{2} on ℜ^{n}, 0 < γ ≤ 1, 0 < ϵ, δ < 1. Let S be a random sequence of m examples drawn independently according to the distribution D. The probability that there exists a function in F that disagrees with at most a fraction (1 − γ)ϵ of the examples in S and yet has error greater than ϵ (w.r.t. D) is less than

8Δ_{F} (2m)e^{−γ^{2}ϵm/4}.

From Corollary 2 and Theorem 3, we get:

Corollary 4. Given a fixed graph G with E edges and N linear threshold units (i.e. W = E + N weights), fixed 0 < ϵ ≤ 1/2, and m random training examples, where

m ≥ \frac{32W}{ϵ} ln\frac{32N}{ϵ} ,

if one can find a choice of weights so that at least a fraction 1 − ϵ/2 of the m training examples are correctly loaded, then one has confidence at least 1 − 8e^{−1.5W} that the net will correctly classify all but a fraction ϵ of future examples drawn from the same distribution. For

m ≥ \frac{64W}{ϵ} ln\frac{64N}{ϵ} ,

the confidence is at least 1 − 8e^{−ϵm/32}.

Proof. Let γ = 1/2 and apply Theorem 3, using the bound on Δ_{F} (m) given in Corollary 2. This shows that the probability that there exists a choice of the weights that defines a function with error greater than ϵ that is consistent with at least a fraction 1 − ϵ/2 of the training examples is at most

8(2Nem/W)^{W} e^{−ϵm/16}.

When m = \frac{32W}{ϵ} ln\frac{32N}{ϵ}, this is 8(2e\frac{ϵ}{32N} ln\frac{32N}{ϵ})^{W}, which is less than 8e^{−1.5W} for N ≥ 2 and ϵ ≤ 1/2. When m ≥ \frac{64W}{ϵ} ln\frac{64N}{ϵ}, (2Nem/W)^{W} ≤ e^{ϵm/32}, so 8(2Nem/W)^{W} e^{−ϵm/16} ≤ 8e^{−ϵm/32}.

The constant 32 is likely an overestimate. No serious attempt has been made to minimize it. Further, we do not know if the log term is unavoidable. Nevertheless, even without these terms, for nets with many weights this may represent a considerable number of examples. Such nets are common in cases where the complexity of the rule being learned is not known in advance, so a large architecture is chosen in order to increase the chances that the rule can be represented. To counteract the concomitant increase in the size of the training sample needed, one method that has been explored is the use of learning algorithms that try to use as little of the architecture as possible to load the examples, e.g. by setting as many weights to zero as possible, and by removing as many nodes as possible (a node can be removed if all its incoming weights are zero.) (Rumelhart 1987; Hinton 1987). The following shows that the VC dimension of such a “reduced” architecture is not much larger than what one would get if one knew a priori what nodes and edges could be deleted.

2We assume some measurability conditions on the class F. See (Pollard 1984; Blumer et al. 1987b) for details.

Corollary 5. Let F be the class of all functions computed by linear threshold feedforward nets defined on a fixed underlying graph G with N′ ≥ 2 computation nodes and E′ ≥ N′ edges, such that at most E ≥ 2 edges have non-zero weights and at most N ≥ 2 nodes have at least one incoming edge with a non-zero weight. Let W = E + N. Then the conclusion of Corollary 4 holds for sample size

m ≥ \frac{32W}{ϵ} ln\frac{32NE′}{ϵ} .

Proof sketch. We can bound Δ_{F} (m) by considering the number of ways the N nodes and E edges that remain can be chosen from among those in the initial network. A crude upper bound is (N′)^{N}(E′)^{E}. Applying Corollary 2 to the remaining network gives Δ_{F} (m) ≤ (N′)^{N}(E′)^{E}(Nem/W)^{W}. This is at most (NE′em/W)^{W}. The rest of the analysis is similar to that in Corollary 4.

This indicates that minimizing non-zero weights may be a fruitful approach. Similar approaches in other learning contexts are discussed in (Haussler 1988) and (Littlestone 1988).

4 Conditions Necessary for Valid Generalization

The following general theorem gives a lower bound on the number of examples needed for distribution-free learning, regardless of the algorithm used.

Theorem 3. (Ehrenfeucht et al. 1987; see also Blumer et al. 1987b): Let F be a class of {−1, +1}-valued functions on ℜ^{n} with V Cdim(F) ≥ 2. Let A be any learning algorithm that takes as input a sequence of {−1, +1}-labeled examples over ℜ^{n} and produces as output a function from ℜ^{n} into {−1, +1}. Then for any 0 < ϵ ≤ 1/8, 0 < δ ≤ \frac{1}{100} and

m < max[\frac{1 − ϵ}{ϵ}ln\frac{1}{δ}, \frac{V Cdim(F) − 1}{32ϵ}],

there exists (1) a function f ∈ F, and (2) a distribution D on ℜ^{n} × {−1, +1} for which P rob((x⃗, a) : a ≠ f(x⃗)) = 0, such that given a random sample of size m chosen according to D, with probability at least δ, A produces a function with error greater than ϵ.

This theorem can be used to obtain a lower bound on the number of examples needed to train a net, assuming that the examples are drawn from the worst-case distribution that is consistent with some function realizable on that net. We need only obtain lower bounds on the VC dimension of the associated architecture. In this section we will specialize by considering only fully-connected networks of linear threshold units that have only one hidden layer. Thus each hidden node will have an incoming edge from each input node and an outgoing edge to the output node, and no other edges will be present. In (Baum 1988) a slicing construction is given that shows that a one hidden layer net of threshold units with n inputs and 2j hidden units can shatter an arbitrary set of 2jn vectors in general position in ℜ^{n}. A corollary of this result is:

Theorem 4. The class of one hidden layer linear threshold nets taking input from ℜ^{n} with k hidden units has VC dimension at least 2⌊\frac{k}{2}⌋n.

Note that for large k and n, 2⌊\frac{k}{2}⌋n is approximately equal to the total number W of weights in the network.

A special case of considerable interest occurs when the domain is restricted to the hypercube: {+1, −1}^{n}. Lemma 6 of (Littlestone 1988) shows that the class of Boolean functions on {+1, −1}^{n} represented by disjunctive normal form expressions with k terms, k < O(2^{n/2}/\sqrt{n}), where each term is the conjunction of n/2 literals, has VC dimension at least kn/4. Since these functions can be represented on a linear threshold net with one hidden layer of k units, this provides a lower bound on the VC dimension of this architecture. We also can use the slicing construction of (Baum 1988) to give a lower bound approaching kn/2. The actual result is somewhat stronger in that it shows that for large n a randomly chosen set of approximately kn/2 vectors is shattered with high probability.

Theorem 5. With probability approaching 1 exponentially in n, a set S of m ≤ 2^{n/3} vectors chosen randomly and uniformly from {+1, −1}^{n} can be shattered by the one hidden layer architecture with 2⌈m/⌊(n(1 − \frac{10}{ln n}))⌋⌉ linear threshold units in its hidden layer.

Proof sketch. With probability approaching 1 exponentially in n no pair of vectors in S are negations of each other. Assume n ≥ e^{10}. Let r = ⌊n(1 − \frac{10}{ln n})⌋. Divide S at random into ⌈m/r⌉ disjoint subsets S_{1}, …, S_{⌈m/r⌉} each containing no more than r vectors. We will describe a set T of ±1 vectors as sliceable if the vectors in T are linearly independent and the subspace they span over the reals does not contain any ±1 vector other than the vectors in T and their negations. In (Odlyzko 1988) it is shown, for large n, that any random set of r vectors has probability P = 4(_{3}^{r})(\frac{3}{4})^{n} + O((\frac{7}{10})^{n}) of not being sliceable. Thus the probability that some S_{i} is not sliceable is O(mn^{2}(\frac{3}{4})^{n}), which is exponentially small for m ≤ 2^{n/3}. Hence with probability approaching 1 exponentially in n, each S_{i} is sliceable, 1 ≤ i ≤ ⌈m/r⌉.

Consider any Boolean function f on S and let S_{i}^{+} = {x⃗ ∈ S_{i} : f(x⃗) = +1}, 1 ≤ i ≤ ⌈m/r⌉. If S_{i} is sliceable and no pair of vectors in S are negations of each other then we may pass a plane through the points in S_{i}^{+} that doesn’t contain any other points in S. Shifting this plane parallel to itself slightly we can construct two half spaces whose intersection forms a slice of ℜ^{n} containing S_{i}^{+} and no other points in S. Using threshold units at the hidden layer recognizing these two half spaces, with weights to the output unit +1 and −1 appropriately, the output unit receives input +2 for any point in the slice and 0 for any point not in the slice. Doing this for each S_{i}^{+} and thresholding at 1 implements the function f.

We can now apply Theorem 6 to show that any neural net learning algorithm using too few examples will be fooled by some reasonable distributions.

Corollary 6. For any learning algorithm training a net with k linear threshold functions in its hidden layer, and 0 < ϵ ≤ 1/8, if the algorithm uses (a) fewer than \frac{2⌊k/2⌋n−1}{32ϵ} examples to learn a function from ℜ^{n} to \{−1, +1\}, or (b) fewer than \frac{⌊n⌊k/2⌋(max(1/2,1−10/(ln n)))⌋−1}{32ϵ} examples to learn a function from {−1, +1}^{n} to {−1, +1}, for k ≤ O(2^{n/3}), then there exist distributions D for which (i) there exists a choice of weights such that the network exactly classifies its inputs according to D, but (ii) the learning algorithm will have probability at least .01 of finding a choice of weights which in fact has error greater than ϵ.

5 Conclusion

We have given theoretical lower and upper bounds on the sample size vs. net size needed such that valid generalization can be expected. The exact constants we have given in these formulae are still quite crude; it may be expected that the actual values are closer to 1. The logarithmic factor in Corollary 4 may also not be needed, at least for the types of distributions and architectures seen in practice. Widrow’s experience supports this conjecture (Widrow 1987). However, closing the theoretical gap between the O(\frac{W}{ϵ} log \frac{N}{ϵ}) upper bound and the Ω(\frac{W}{ϵ}) lower bound on the worst case sample size for architectures with one hidden layer of threshold units remains an interesting open problem. Also, apart from our upper bound, the case of multiple hidden layers is largely open. Finally, our bounds are obtained under the assumption that the node functions are linear threshold functions (or at least Boolean valued). We conjecture that similar bounds also hold for classes of real valued functions such as sigmoid functions, and hope shortly to establish this.

Acknowledgments

We would like to thank Ron Rivest for suggestions on improving the bounds given in Corollaries 4 and 5 in an earlier draft of this paper, and Nick Littlestone for many helpful comments. The research of E. Baum was performed by the Jet Propulsion Laboratory, California Institute of Technology, as part of its Innovative Space Technology Center, which is sponsored by the Strategic Defense Initiative Organization/Innovative Science and Technology through an agreement with the National Aeronautics and Space Administration (NASA). D. Haussler gratefully acknowledges the support of ONR grant N00014-86-K-0454. Part of this work was done while E. Baum was visiting UC Santa Cruz.

References

Baum, E.B. 1988. On the Capabilities of Multilayer Perceptrons. J. of Complexity,

in press. Blumer, A., A. Ehrenfeucht, D. Haussler, and M. Warmuth. 1987a. Occam’s

Razor. Inf. Proc. Let. 24, 377–380.

. 1987b. Learnability and the Vapnik-Chervonenkis Dimension. University of California–Santa Cruz Technical Report UCSC-CRL-87-20 and J. ACM, to appear.

Cover, T. 1965. Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications to Pattern Recognition. IEEE Trans. Elect. Comp. V14, 326–334.

Devroye, L. 1988. Automatic Pattern Recognition, a Study of the Probability of

Error. IEEE Trans. PAMI V10:N4, 530–543. Denker, J., D. Schwartz, B. Wittner, S. Solla, J. Hopfield, R. Howard, and L. Jackel.

1987. Automatic Learning, Rule Extraction, and Generalization. Complex Systems 1, 877–922.

Duda, R. and P. Hart. 1973. Pattern Classification and Scene Analysis. New

York: Wiley. Ehrenfeucht, A., D. Haussler, M. Kearns, and L. Valiant. 1987. A General

Lower Bound on the Number of Examples Needed for Learning. University of California–Santa Cruz Technical Report UCSC-CRL-87-26 and Information and Computation, to appear.

Haussler, D. 1988. Quantifying Inductive Bias: AI Learning Algorithms and

Valiant’s Learning Framework. Artificial Intelligence 36, 177–221. Hinton, G. 1987. Connectionist Learning Procedures. Artificial Intelligence, to

appear. Littlestone, N. 1988. Learning Quickly when Irrelevant Attributes Abound: a new

linear threshold algorithm. Machine Learning V2, 285–318. Odlyzko, A. 1988. On Subspaces Spanned by Random Selections of ±1 Vectors.

J. Comb. Th. A V47:N1, 124–133. Pollard, D. 1984. Convergence of stochastic processes. New York: Springer-Verlag. Qian, N. and T.J. Sejnowski. 1988. Predicting the Secondary Structure of Globular

Protein using Neural Networks. J. Molec. Biol. 202, 865–884. Rumelhart, D. 1987. Personal communication. Sauer, N. 1972. On the Density of Families of Sets. J. Comb. Th. A V13,

145–147. Sejnowski, T.J. and C.R. Rosenberg. 1987. NET Talk: a Parallel Network that

Learns to Read Aloud. Complex Systems 1, 145–168.

Tesauro, G. and T.J. Sejnowski. 1988. A ‘Neural’ Network that Learns to Play Backgammon. In: Neural Information Processing Systems, ed. D.Z. Anderson, AIP, NY, 794–803.

Valiant, L.G. 1984. A Theory of the Learnable. Comm. ACM V27 N11, 1134–

1142. Vapnik, V.N. and A.Ya. Chervonenkis. 1971. On the Uniform Convergence of

Relative Frequencies of Events to their Probabilities. Th. Prob. and its Applications V17:N2, 264–280.

Vapnik, V.N. 1982. Estimation of Dependences Based on Empirical Data. New

York: Springer Verlag. Wenocur, R.S. and R.M. Dudley. 1981. Some Special Vapnik-Chervonenkis Classes.

Discrete Math. V33, 313–318. Widrow, B. 1987. ADALINE and MADALINE – 1963, Plenary Speech, Vol I:

Proc. IEEE 1st Int. Conf. on Neural Networks, San Diego, CA, 143–158.

Received 5 September; accepted 26 September 1988.