Self-adjusting multi-layer neural network architectures and methods therefor

[0002] This Application is a Continuation-In-Part of U.S. patent application Ser. No. 09/240,052, filed Jan. 29, 1999, now U.S. Pat. No. 6,490,571, which is a Continuation-In-Part of U.S. patent application Ser. No. 08/713,470, filed Sep. 13, 1996, now issued as U.S. Pat. No. 6,009,418, which claims the benefit of U.S. Provisional Patent Application Serial No. 60/016,707 filed May 2, 1996. The entire disclosures of these applications, including references incorporated therein, are incorporated herein by reference.

[0003] 1. Field of the Invention

[0004] The invention relates in general to the field of neural networks, and in particular to a neural network architecture and method which utilizes self-adjusting connections between nodes to process information.

[0005] 2. Related Art

[0006] Neural networks have been known and used in the prior art in computer applications which require complex and/or extensive processing. Such applications include, e.g., pattern recognition and image and voice processing. In these applications, neural networks have been known to provide greatly increased processing power and speed over conventional computer architectures. Several approaches to neural networking exist and can be distinguished from one another by their different architectures. Specifically, the approaches of the prior art can be distinguished by the numbers of layers and the interconnections within and between them, the learning rules applied to each node in the network, and whether or not the architecture is capable of supervised or unsupervised learning.

[0007] A neural network is said to be “supervised” if it requires a formal training phase where output values are “clamped” to a training set. In other words, such networks require a “teacher,” something not necessarily found in nature. Unsupervised networks are desirable precisely for this reason. They are capable of processing data without requiring a preset training set or discrete training phase. Biological neural networks are unsupervised, and any attempt to emulate them should aspire to this capability. Of the following approaches, the Boltzmann/Cauchy and Hidden Markov models are supervised networks and the remainder are unsupervised networks.

[0008] At least eight principal types of feedback systems, also called backpropagation models, have been identified in the prior art. The Additive Grossberg model uses one layer with lateral inhibitions. The learning rule is based on a sigmoid curve and updates using a steepest ascent calculation. The Shunting Grossberg is similar, with an added gain control feature to control learning rates. Adaptive Resonance Theory models use two layers, with on-center/off-surround lateral feedback and sigmoid learning curves. The Discrete Autocorrelator model uses a single layer, recurrent lateral feedback, and a step function learning curve. The Continuous Hopfield model uses a single layer, recurrent lateral feedback, and a sigmoid learning curve. Bi-Directional Associative Memory uses two layers, with each element in the first connected to each layer in the second, and a ramp learning curve. Adaptive Bi-Directional Associative Memory uses two layers, each element in the first connected to each in the second, and the Cohen-Grossberg memory function. This also exists in a competitive version. Finally, the Temporal Associative Memory uses two layers, with each element in the first connected to each element in the second, and an exponential step learning function.

[0009] At least eight principal types of feedforward systems have been identified. The Learning Matrix uses two layers, with each element in the first connected to each element in the second, and a modified step learning function. Drive-Reinforcement uses two layers, with each element in the first connected to each in the second, and a ramp learning function. The Sparse Distributed Memory model uses three layers, with random connections from the first to the second layer, and a step learning function. Linear Associative Memory models use two layers, with each element in the first layer connected to each element in the second, and a matrix outer product to calculate learning updates. The Optimal Linear Associative Memory model uses a single layer, with each element connected to each of the others, and a matrix pseudo-inverse learning function. Fuzzy Associative Memory uses two layers, with each element in the first connected to each element in the second, and a step learning function. This particular model can only store one pair of correlates at a time. The Learning Vector Quantizer uses two layers, with each element in the first connected to each in the second, negative lateral connections from each element in the second layer with all the others in the second layer, and positive feedback from each second layer element to itself. This model uses a modified step learning curve, which varies as the inverse of time. The Counterpropagation model uses three layers, with each element in the first connected to each in the second, each element in the second connected to each in the third, and negative lateral connections from each element in the second layer to each of the rest, with positive feedback from each element in the second layer to itself. This also uses a learning curve varying inversely with time.

[0010] Boltzmann/Cauchy models use random distributions for the learning curve. The use of random distributions to affect learning is advantageous because use of the distributions permits emulation of complex statistical ensembles. Thus, imposing the distributions imposes behavioral characteristics which arise from complex systems the model networks are intended to emulate. However, the Boltzmann/Cauchy networks are capable only of supervised learning. And, these models have proven to be undesirably slow in many applications.

[0011] Hidden Markov models rely on a hybrid architecture, generally of feedforward elements and a recurrent network sub-component, all in parallel. These typically have three layers, but certain embodiments have had as many as five. A fairly typical example employs three layers, a softmax learning rule (i.e., the Boltzmann distribution) and a gradient descent algorithm. Other examples use a three-layer hybrid architecture and a gamma memory function, rather than the usual mixed Gaussian. The gamma distribution is convenient in Bayesian analysis, also common to neural network research, and is the continuous version of the negative-binomial distribution. However, the underlying process for this model is a stationary one. That is, the probability distribution is the same at time t and time t+Δt for all Δt.

[0012] Studies of language change and studies of visual and acoustic processing in mammals have been used in the prior art to identify the mechanisms of neural processing for purposes of creating neural network architectures. For example, it has been noted that mammalian visual processing seems to be accomplished by feed-forward mechanisms which amplify successes. Such processing has been modeled by calculating Gaussian expectations and by using measures of mutual information in noisy networks. It has further been noted that such models provide self-organizing feature-detectors.

[0013] Similarly, it has been noted in the prior art that acoustic processing in mammals, particularly bats, proceeds in parallel columns of neurons, where feed-forward mechanisms and the separation and convergence of the signal produce sophisticated, topically organized feature detectors.

[0014] The invention in its preferred embodiment provides a method and apparatus for using a neural network to process information wherein multiple nodes are arrayed in multiple layers for transforming input arrays from prior layers or the environment into output arrays for subsequent layers or output devices. Learning rules based for reinforcing successful matches to templates, and simultaneously suppressing unsuccessful matches, are applied. Interconnections between nodes are provided in a manner whereby the number and structure of the interconnections are self-adjusted by the learning rules during learning. At least one of the layers is used as a processing layer, and multiple lateral inputs to each node of each processing layer are used to retrieve information.

[0015] The invention provides rapid, unsupervised processing of complex data sets, such as imagery or continuous human speech, and a means to capture successful processing or pattern classification constellations for implementation in other networks. The invention includes application-specific self-adjusting multi-layer architectures that employ template-based learning rules to alter and annotate data arrays. Such application-specific architectures include a textual or oral language parser, a basic file searcher, an advanced file searcher, an advanced file searcher that can search for propositions, a translator, a basic “smart” scanner, an advanced “smart” scanner or oral parser, and a dialect parser for oral language. These applications have a number of common features. Inputs are delivered into a flexible number of channels, determined by the total number of scanned letters, input phonemes, words, or propositional values in the input sample. The arrays in each channel are then combined in patterns that depend on values derived from lookup tables or templates. Feedback from one or two layers higher in the central processing segment of the architecture further alters the arrays, where the learning rules reinforce template matches and also decrement failures to match. The lookup or template-matching steps also alter the arrays to prevent confusion of the data and to augment the information carried forward through the architecture. The output channels transform the arrays into final form as required, as well as reset the initial processing weights for the next processing cycle. These outputs take whatever format desired; they may be printed text, statistical information in digital or graphic form, oral outputs through speakers, data in a register, or inputs to other processing applications.

[0016] The foregoing and other objects, features, and advantages of the invention will be apparent from the following more particular description of preferred embodiments as illustrated in the accompanying drawings, in which reference characters refer to the same parts throughout the various views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating principles of the invention.

[0017] FIG. 1 illustrates a diagrammatic view of the self-adjusting layer architecture of the invention according to a preferred embodiment.

[0018] FIG. 1aillustrates a diagrammatic view of the self-adjusting layer architecture of the invention according to an embodiment wherein the invention is used to program a second neural network.

[0019] FIG. 2 illustrates a side view of a single channel.

[0020] FIG. 3 illustrates details of internal feedback in central processing layers.

[0021] FIG. 4 illustrates the effect of“leaky” processing.

[0022] FIG. 5 shows multiple “leaky” inputs merging at the central processing layers, and outputs proceeding to different implementation channels.

[0023] FIG. 6 depicts the front vowels for the participants in the Northern Cities Shift.

[0024] FIG. 7 illustrates the first three iterations in the generation of a Cantor set.

[0025] FIGS. 8-10 show graphical illustrations drawn from natural language studies.

[0026] FIG. 11 shows a schematic design for a textual or oral language parser.

[0027] FIG. 12 shows a schematic design for a basic file searcher.

[0028] FIG. 13 shows a schematic design for an advanced file searcher.

[0029] FIG. 14 shows a schematic design for an advanced file searcher that can search for propositions.

[0030] FIG. 15 shows a schematic design for a translator.

[0031] FIG. 16 shows a schematic design for a basic “smart” scanner.

[0032] FIG. 17 shows a schematic design for an advanced “smart” scanner or oral parser.

[0033] FIG. 18 shows a schematic design for a dialect parser for oral language.

[0034] By studying language acquisition and evolution, one can identify learning curves in language acquisition. These learning curves can be characterized by negative-binomial statistics. One can also identify patterns of change which can be explained by underlying attractors with fractal dimension. That is, the dimension of the sets is not the topological dimension—1 for a line, 2 for a plane, etc.—but a related measure of the size and complexity of the set, whose measure can be fractional.

[0035] The measures of these attractors are consistent with Cantor sets in three dimensions. In Cooper, “Linguistic Attractors: The Cognitive Dynamics of Language Acquisition and Change,” chapters 1-3, which is incorporated by reference herein, it is demonstrated that Cantor sets are sufficient (though not necessary) to establish a universal Turing machine. That is, they are sufficient to demonstrate an ability to compute any function. This reference also shows a correlate of these attractors with statistical patterns derived from children learning English, which provided the evidence for a learning process which converges on a negative-binomial distribution.

[0036] The self-adjusting layer architecture of the invention is motivated by the above and other considerations from human language acquisition and change, as well as by the general constraints posed by the structure of the human perceptive apparatus and systems for muscle control. It is based on multiple layers; with one or more layers devoted to processing input information transmitted along “leaky” channels; at least one processing layer; one or more layers devoted to processing outputs; feedback from the outputs back to the processing layer; and inputs from parallel channels, also to the processing layer. With the exception of the feedback loop and central processing layers, the network is feedforward. The learning rules reinforce successful matches to stored or learned patterns, again derived from considerations of human language acquisition.

[0037] The self-adjusting layer architecture of the invention according to a preferred embodiment is derived from a model of human speech acquisition based on random pattern matching. The requirement for negative reinforcement in human speech acquisition is controversial, but the consensus view seems to be that it is not required. A stochastic process relying on positive reinforcement which also yields the learning curves observed in human subjects as they learn to speak is consequently preferred for the matching process. Bose-Einstein statistics capture such a process, which can also be modeled as a Polya process that models sampling with replacement from sample populations. This process will also lead to a fractal pattern of synapse sequences corresponding to each learned pattern. Such a pattern is also to be expected from data on human language change.

[0038] In the limit, Bose-Einstein systems or Polya processes converge to learning curves with negative-binomial distributions, but the fundamental process is a non-stationary one. As a further consequence, any model which relies on stationary processes (i.e., any Markov process, normal processes, Bernoulli processes, gamma processes, etc.) is only an approximation to this model, and accurate only in the limit as nodes approach infinity.

[0039] The architecture of the self-adjusting layer architecture at once mimics the input and output processing found in human perceptions and muscle control, and permits a variant of recurrent network architectures to learn in an unsupervised environment. Parallel “leaky” channels combine the strengths of Markov or other hybrid architectures with a more structured higher scale architecture. That is, major formations in the human brain most probably are joined on a large scale by pattern instructions, but internally by random connections. The multiple layers within a channel reflect the fact that the human nervous system does considerable processing before information is presented to the brain, and, again, considerable processing after leaving the brain before impulses arrive at the muscles. This not only contributes a time delay before feedback but also additional content to the commands to the muscles—commands which must have been learned.

[0040] FIG. 1 illustrates a diagrammatic view of the self-adjusting layer architecture of the invention according to a preferred embodiment. The diagram depicts typical elements in the network, but each layer in a channel could have many more than three elements per layer. These will be connected randomly to elements in the next layer, so it is not necessarily the case that each element in one layer is connected to each in the next. More than three layers may be necessary before arrival at the processing level, and more than three layers may be necessary before reaching the implementation layer (e.g., muscles).

[0041] In FIG. 1, information arrives from the left to a perceptual apparatus, which encodes the data, and passes it to the next layer. This flow continues to the processing layer, where inputs converge with inputs from parallel channels and output from a feedback loop connected to the primary channel.

[0042] The architecture uses feedforward nodes, randomly linked to higher levels within prescribed channels to process the inputs. Although not depicted, connections from each layer to the next are random: each node is not necessarily connected to each one in the layer above it. There is at least one central layer with lateral connections to other channels. This will be called the lateral processing layer.

[0043] Outputs proceed to the right, again with random feed-forward connections. Feedback from the output channels are merged with inputs to the lateral processing layer. This feedback is also merged with feedback from the lateral processing layer and from the initial output layer. This feedback is not depicted in FIG. 1, but is depicted by rings in FIGS. 2 and 3, discussed below. Outputs from other channels are also presented to the lateral processing layer.

[0044] Central processing is actually embedded between input and output channels, so that there is no discrete transition. A side view of a single channel is at FIG. 2, and details of internal feedback in the central processing layers is at FIG. 3. The rationale for these feedback and processing arrangements is set forth in the discussion of the learning rule for the network below.

[0045] The FIGS. depict a seven-layer architecture, but the actual number of layers would be dependent on input pre-processing, and output processing. This could require as few as one input layer or more than three feed-forward input layers, as well as at least one and possibly more than three feed-forward output layers in their respective channels. The essential result is, however, that structured data is presented to the central processing layers from input channels, and that outputs are further processed as required for final implementation. In natural language, for example, this would mean the network would take acoustic inputs, encode them in the input channels, process them in the central processing layers, and then process out-going motor signals in the necessary channels to a number of different muscle groups.

[0046] The three-layer central processing core of the architecture will produce the necessary computational characteristics.

[0047] It should be noted that in FIG. 2 the final input layer is also the first central processing layer. Similarly, the final processing layer is the initial feed-forward layer to output channels.

[0048] FIG. 3 shows the internal feedback within the central processing layers. External feedback from the beginning and the end of the output channels is merged with the inputs at the initial central processing/final input layer. Other channels feed into the lateral processing layer. Lateral connections in the central layer are crucial to a multi-channel architecture. An additional layer with lateral connections is optional, but makes processing of sequences easier for the network. Consequently, for language processing, where sequences must be processed with minimal load on memory, the additional lateral connections may be necessary.

[0049] In a complex organism, channels would be linked to specific perceptual organs and to output musculature keyed to specific behavior. Success is reinforced. This is a mild form of a competitive network, so that information will be organized topologically when processed, but the topology will not be strict. The random connections will make the upward flow of information within the channel “leaky.” The effect of“leaky” processing is diagramed in FIG. 4.

[0050] FIG. 5 shows multiple “leaky” inputs merging at the central processing layers, and outputs proceeding to different implementation channels. Processing in the central layers would be affected by the structure of lateral channels as well. These can be designed into the architecture, or evolve through the same rules as apply to the vertical channels.

[0051] Feedback can be processed by any of several expectation maximization schemes. Such schemes are described, e.g., in Linsker, “Neural Information Processing Systems5” Morgan Kaufmann Publishers, 1993, pages 953-960, the disclosure of which is incorporated herein by reference. However, any reinforcement over the critical threshold must update the successful interconnections according to Bose-Einstein statistics (originally, equiprobability assigned to different constellations of indistinguishable particles). This can be done as follows.

[0052] Begin with a Polya urn scheme, with m₀balls in the urn, m black and m₀−m red. For each drawing, replace each black ball with two black balls, and each red ball with two red balls (sampling with replacement). Then for n₀drawings, of which n balls were black, and n₀−n were red, we have the Polya distribution for the probability that the next ball will be black $f_p\left(n\right)=\frac{\left(\begin{array}{c}m+n-1\\ n\end{array}\right)\left(\begin{array}{c}{m}_0-m+n_0-n-1\\ n_0-n\end{array}\right)}{\left(\begin{array}{c}{m}_0+n_0-1\\ n_0\end{array}\right)}$

[0053] This is also the Bose-Einstein distribution for m₀cells (neurons/synapses) and n₀particles (inputs), with a constellation of m cells (neurons/synapses) with a total of n indistinguishable particles (successes). A constellation of m cells with a total of n indistinguishable balls for n₀→∞, m₀→∞, such that n₀/m₀=p, p finite is then $f_{B-E}\left(m,n\right)=f_P\left(n\right)\to \left(\begin{array}{c}m+n-1\\ n\end{array}\right)\frac{p_n}{{\left(1+p\right)}^{m+n}}$

[0054] This is a special case of the negative-binomial distribution, as required from learning curve data on human speech acquisition.

[0055] The network requirement is then n₀reinforced pathways across m₀synapses, both large, with n₀/m₀=p. When the Polya process has the substitution factor c≧0, the transition probability from E_n(n black) to E_n+1(n+1 black) is $\frac{m+\mathrm{nc}}{m_0+n_{0}c}=\frac{r+n\gamma }{1+n_0\gamma }\mathrm{for}r=\frac{m}{m_0};\gamma =\frac{c}{m_0}$

[0056] This leads to a special form for a rule to update synaptic weights. In general, Hebbian learning rules are expressed in the form

[0057] Δw_kj(n)=F(y_k(n), x_j(n))

[0058] for synaptic weights from j to k, where F is a function of pre- and post-synaptic activity. Frequently, models use the following special case

[0059] Δw_kj(n)=ηy_k(n)x_j(n)

[0060] where η is a positive learning rate parameter. To avoid saturation of the weights, this is often modified by the addition of a forgetting factor:

[0061] Δw_kj(n)=ηy_k(n)x_j(n)−αy_k(n)w_kj(n)

[0062] The rule has also been expressed in terms of the covariance between pre- and post-synaptic activities:

[0063] Δw_k(n)=ηE[(y_k(n)−{overscore (y)}_k(x_j(n)−{overscore (x)}_j)]

[0064] where E is the expectation for the activity.

[0065] The update rule for the self-adjusting layer architecture uses the learning rate parameter in a very different way. The form of the rule with a decay rate (to avoid saturation of the weights) is $\Delta w_{\mathrm{kj}}\left(n\right)=\left(\frac{r\pm \eta }{s+\eta +\delta \left(t\right)}\right)y_k\left(n\right)x_j\left(n\right)$

[0066] ηpositive; δ(t)≧0 and monotone increasing

[0067] where r/s is the synaptic weight at epoch n−1, and |r/s|≦1. Here r is increased for excitation, and decreased for inhibition. It only changes when there is activity at the synapse. The decay rate δ(t) varies with time, and does not depend on synaptic activity. The cumulative update across all inputs j would then take the form $\left(\frac{r+\alpha \left(n\right)-\beta \left(n\right)}{s+\eta \left(n\right)+\delta \left(t\right)}\right)$

[0068] where α(n)+β(n)=η(n), all positive

[0069] where α(n) and β(n) count the numbers of excitatory and inhibitory inputs, respectively.

[0070] We can apply the Cohen-Grossberg theorem to this rule immediately to demonstrate that the Self-adjusting layer architecture rule is capable of content-addressable memory. That is, any input of a portion of the memory can function to recall the rest. Briefly, the theorem states that for the class of neural networks described by the following system of coupled nonlinear differential equations: $\begin{array}{cc}\frac{d}{dt}{u}_j=a_j\left(u_j\right)\lfloor b_j\left(u_j\right)-\sum _{i=1}^N{c}_{\mathrm{ji}}{\phi }_i\left(u_i\right)\rfloor ,j=1,\dots ,i& \left(1\right)\end{array}$

[0071] the class of neural networks admits a Liapunov function, defined as $\begin{array}{cc}E=\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{c}_{\mathrm{ji}}{\phi }_i\left(u_i\right){\phi }_j\left(u_j\right)-\sum _{j=1}^N{\int }_0^{u_j}{b}_j\left(\lambda \right){\phi }_j^{\prime }\left(\lambda \right)d& \left(2\right)\end{array}$

[0072] where ${\phi }^{\prime }\left(\lambda \right)=\frac{d}{d\lambda }\left({\phi }_j\left(\lambda \right)\right)$

[0073] When the synaptic weights of the network are “symmetric”:

[0074] C_ij=C_ji

[0075] the function A_j,(u_j) satisfies the condition for “nonnegativity”:

[0076] a_j(u_j)≧0

[0077] and the nonlinear input-output function φ_j(u_j) satisfies the condition for “monotonicity”: $\frac{dE}{dt}\le 0\mathrm{for}{u}_j\ne 0\mathrm{and}\mathrm{all}j$

[0078] then the Liapunov function E of the system defined by Eq. (2) satisfies the condition and the system is globally asymptotically stable. That is, the system will be capable of content addressable memory.

[0079] Applying the Cohen-Grossberg theorem to the self-adjusting layer architecture, we note immediately that pre- and post-synaptic weights are identical, and thus, use symmetric weights between nodes. Then, if we set a_j(u_j)=1, it remains to show that the function φ′(u_j)≧0. This is the case for α(n)≧β(n) and δ(t) sufficiently small. Thus, we have monotonicity, and the self-adjusting layer architecture is capable of content addressable memory. It is also capable of the other attributes necessary for computation.

[0080] The learning rule for the self-adjusting layer architecture naturally leads to negative-binomial learning curves for the network—comparable to curves observed in humans acquiring natural language. This is an emergent property of the rule and need not be imposed by a structured learning regime as in the Boltzmann and Cauchy networks. The rule will lead to clusters of nodes in each layer associated with each successful multi-channel pattern. This is an important characteristic which will permit the network to function as a Turing machine. This can be demonstrated by considering these clusters of favored nodes as attractors. Their measurement is consistent with natural language in humans, and indicative of structured sets capable of computation. For example, the most useful measure we can apply to phonological attractors is Hausdorff dimension, which permits us to classify them as fractal sets. To make this application, we must establish a measure over our phase space. This is simple enough for formant frequencies, and can be extended to axes that code for other relevant factors, such as source, city, generation, gender, and conditioning environment. Using the usual Euclidean metric, we can establish a “distance” and can measure a “diameter.” Then, we can say the following.

[0081] The diameter of a set U is |U|=sup{|x−y|: x,yεU}. For E⊂∪U_iand 0<|U_i|≦δ for each I, {U_i} is a δ-cover of E. For δ>0, s≧0, $H_{\delta }^s\left(E\right)=\inf \sum _{i=1}^{\infty }{\left|U_i\right|}^s$

[0082] where the infimum is over all countable δ-covers {U_i} of E. H_δ^sis an outer measure on semantic space. The Hausdorff s-dimensional outer measure of E is $H^s\left(E\right)=\underset{\delta \to 0}{\lim }{H}_{\delta }^s\left(E\right)=\underset{\delta \to 0}{\sup }{H}_{\delta }^s\left(E\right)$

[0083] This limit may be infinite, since H_δ^sincreases as δ decreases. H^s(E) is a metric outer measure since it satisfies a triangle inequality. The restriction of H^sto the σ-field of H^s-measurable sets is called Hausdorff s-dimensional measure.

[0084] For any E, H^s(E) is non-increasing as s increases from 0 to ∞. For s<t,

[0085] H_δ^s(E)≧δ^s−tH_δ^t(E)

[0086] This implies that if H^t(E) is positive, H^s(E) is infinite, which further implies that there is a unique value, dim E, called the Hausdorff dimension of E, such that

[0087] H^s(E)=∞ if 0≦s≦dim E; H^s(E)=0 if dim E<s<∞

[0088] Ascribing probabilities to phonological attractors is therefore meaningful. We can ascribe fractal dimension to them as well.

[0089] Unfortunately, direct calculation of the Hausdorff dimension is often intractable. It can be approximated with another function, called the correlation function C(r), for varying distances r, which is given by $C\left(r\right)=\frac{1}{N^2}\sum _{i,j}\theta \left(r-\left|X_i-X_j\right|\right)$

[0090] Where N is the number of data points, r is the distance used to probe the structure of the attractor, X_iand X_jare pairs of points, and θ is the Heaviside function, where θ(x)=1 for x>0 and θ(x)=0 otherwise.

[0091] We estimate the dimension of the attractor by taking the slope of the linear portions of the curves. Since generally InC(r)˜dln(r), the slope will converge to d when the space is saturated. That is, the minimum number of variables to describe the manifold in n-space occupied by an attractor will be d.

[0092] FIG. 6 depicts the front vowels for the participants in the Northern Cities Shift. In the figure, the monophthongs, /i/, /e/, and particularly /æ/, show substantial linear segments. These are all participants in the chain shifts revealed in a detailed study of dialect change among the white populations of cities ranging from upstate New York across Minnesota, while the diphthongs generally have not. The diphthong signature on this chart is typical of sounds which are generally stable. The front monophthongs have dimensions ranging from 1.4 to 1.6.

[0093] It will now be shown that the structure of these set hierarchies allows the communication and processing of information. To see this, consider phonological attractors, which required several axes apiece to describe them fully, with each projection on each axis with dimension less than one. With fractal attractors, the projection on almost all dimensions in semantic space will in fact be zero. For those dimensions along which the dimension is greater than zero and less than one, it is possible to construct a fractal set, called a cascade, which has the characteristics of a Turing machine.

[0094] A simple example of such a cascade, used by Mandelbrot as a simple model for random errors in data transmission, is the Cantor set. This set consists of residues of the unit interval [0,1] from which the middle third is subtracted, and then the operation is applied to each successive residue ad infinitum. The resulting set has dimension s=0.6309 . . . and H^s(E)=1.

[0095] Instead of this simple set, we can construct a more involved set, which I will call a Gödel cascade, based on a generalized Cantor set. Specifically, we can define a finite union of closed intervals of the unit interval E₀, E₀⊃E₁⊃E₂. . . . For each interval I of E_j, we specify E_j+1∩I by selecting an integer m>2 and letting the subintervals J₁, J₂, . . . , J_mbe equally spaced, with lengths given by ${\left|J_i\right|}^s=\frac{1}{m}{\left|I\right|}^s$

[0096] Then

[0097] m|J_i|+(m−1)d=|I|(1≦i≦m)

[0098] where d is the spacing between two consecutive intervals J_i. The value for m may vary over different intervals i in E_j. The resulting set has dimension s and H^s(E)=1.

[0099] Now, following Martin Davis in the study of recursive operations and computability, if we associate each of a set of symbols with a different odd integer, we can construct the unique Gödel number for any expression $r=\prod _{k=1}^n{\mathrm{Pr}\left(k\right)}^{a_k}$

[0100] where r is the Gödel number, a_kis the integer for the kth symbol and Pr(k) is the kth prime number.

[0101] To create a cascade analog to this procedure, if we set m=2 and

[0102] d⁻¹=Pr(k)^a

[0103] in the construction of a cascade we can then in principle recover a unique set of residues for any expression by measuring the gaps between the residues. For the expression illustrated in FIG. 7, extended to n symbols, the expression can be recovered in reverse order by comparing the first gap to the residue one level up, the second gap to the residue two levels up, and so on to the 2ⁿth gap to the residue n+1 levels up.

[0104] This is merely the simplest procedure yielding this result. For equally spaced J_m, for example, we can also set w=2m−1 such that

[0105] w=Pr(k)^a

[0106] The expression can then be recovered from the ratio between each i and J_iderived from it. Alternatively, if we let m stand for w, the expression would be recoverable by counting the J_i. Clearly, since Gödel expressions can model any proposition in any formal system, cascades can, too. Other, more efficient cascades are n₀doubt possible as well.

[0107] A collection of such cascades would be a means to encode a collection of expressions, and hence would constitute a Turing machine.

[0108] Since Gödel numbering is not the only means to reduce expressions to integers, this demonstration is only good in principle, but it shows that fractal dimensions make sense. They provide a sufficient (although not necessary) condition for the full gamut of cognitive functions.

[0109] The generalized Cantor set from which the Gödel architecture and learning algorithm adds structured feedback, which allows correlations without a supervised learning situation, and a non-stationary update rule, which will yield the necessary fractal set components to match observations, since activation patterns in the central processing nodes will produce two dimensional Cantor sets (with fractal dimension less than 2, and generally greater than 1 for high information sets). These sets can then be combined. With a recursive learning algorithm and the processing layers seeking local mutual information maxima, we have the three components necessary for a Turing machine: recursion, composition, and minimalization. Davis also demonstrated that the minimalization operation need be performed only once, which means that the lateral processing layer is sufficient to make the overall architecture function.

[0110] It is probably significant to note that PET scans of humans show dimensions generally between 1 and 2, as we would expect from this architecture.

[0111] FIG. 7 illustrates the first three iterations in the generation of a Cantor set. Cantor sets are formed by the iterated concentration of the set members into increasingly small subsets of the unit segment [0,1]. In the classical Cantor set, the middle third of the segment is removed at each iteration; that is, the middle third of the segment [0,1], then the middle third of the remaining two pieces, then the middle third of the remaining four pieces, and so on. In a generalized Cantor set, the size of the piece removed is variable. The capability to reconstruct the size of the removed pieces by examination of the residues provides the computational capacity for such sets.

[0112] FIGS. 8-10 are drawn from natural language studies, and show similar dimensions at all levels of abstraction. FIG. 8 shows the back vowels from the same Northern Cities Vowel Shift study as FIG. 6; FIG. 9 shows case (i.e., nominative, genitive, dative, accusative) in Old English; and, FIG. 10 shows mood (indicative, subjunctive, imperative, and infinitive) in Old High German. The correlation signatures are all similar, and the underlying dimension is nearly the same as well for the high content sets: approximately 1.2 for the Old English dative, and 1.4 for the Old High German subjunctive.

[0113] The present invention can be practiced using digital network emulation software on a general purpose computer, or using special-purpose neural networking hardware, or some combination thereof. As the learning rule depends on probability distributions, digital implementation can calculate the distributions directly, or they can model the process as one of synapse pathway recruitment. In the latter case, since synapses cannot increase without bound, the population of synapses must be renormalized at each step. This is most easily accomplished with a uniform decay rate in the strength of connections.

[0114] Similarly, hardware or software/hardware simulations are possible with quantum devices based on particles obeying Bose-Einstein statistics. This population of particles includes photons, and therefore laser devices, but n₀particles subject to Pauli exclusion, such as electrons.

[0115] A preferred implementation of the invention is by means of digital emulation of a network, with the program specifying a series of lattices, each node incorporating the update formula, and each node on a given lattice mapped to nodes on the next lattice by a random, Gaussian distribution. Feedback may similarly require a Gaussian connection between the feedback source and the target processing layer. For single or small numbers of parallel channels, the model can be implemented on a standard Intel-based platform, e.g., one having a Pentium processor running at 100 MHz, or on a Macintosh platform with similar computational power. Larger emulations may require a workstation-class computer.

[0116] Implementation of the invention is also possible by use of a specialized chip, where the internal circuits respond according to the update rule.

[0117] The fact that the network generates Bose-Einstein statistics, and does not need to have them imposed by program, means that hardware implementations are also possible using components exhibiting quantum behaviors, such as lattices of atoms which respond to given frequencies. Bose-Einstein statistics, for example, describe the Einstein radiation mechanism, where the critical parameters are the absorption and spontaneous emission of photons. For this reason, Bose-Einstein statistics underlie physical devices such as lasers, which could thus be adapted to implementation of this type of network.

[0118] The learning rules are based on a Polya process, which reinforces success. This is a non-stationary process which induces Bose-Einstein statistics when conducted across large numbers of synapses over many iterations. In the limit, as the iterations approach infinity, the resulting distribution converges to a negative-binomial distribution. The rules themselves may be implemented in three different variants: 1) a basic synapse model; 2) a competitive-learning version focused on neurons rather than synapses; and 3) a hybrid feedforward/back-propagation version in which feedback weights can employ a variety of maximization schemes. The network can run in synchronous mode for all three versions by setting a common clock for the network, with each epoch updated simultaneously across the network. The network can also run in asynchronous mode by setting a non-zero epoch time for each node, but updating weights only for the nodes involved when one fires. Since the asynchronous mode only uses local interactions, some optimization schemes in the hybrid version would not run in this mode.

[0119] The rules for the basic synapse model can be programmed as follows:

[0120] a. Provide each neuron an address on a two-dimensional layer, similar to cells on a spreadsheet.

[0121] b. Specify the connections between each layer, again, similar to specifying connections between cells on multiple spreadsheets in a workbook.

[0122] c. For each neuron on layer j, we then have inputs from layer i and outputs to layer k.

[0123] d. For each synapse linking i to j:

[0124] If i fires, reset the original weight r/s to: $\frac{r+c}{s+c}\mathrm{for}\mathrm{excitation}$ $\frac{r-c}{s+c}\mathrm{for}\mathrm{inhibition}$

[0125] for learning constant c>0

[0126] For threshold θ_jfor the neuron, when $\sum _i{w}_{\mathrm{ji}}\ge {\theta }_j$

[0127] j fires

[0128] e. Calculate for all neurons on level j.

[0129] f. Repeat calculations for all neurons on level k.

[0130] g. Initial inputs to the first layer are measurements from the environment (signals from light sensors, low/high pass filters from sound equipment, etc.).

[0131] h. Final outputs are to devices connected to the environment (printers, muscles, speakers, etc.)

[0132] The rules for competitive learning are similar, but modified as follows:

[0133] a. Lateral connections (i.e., within the same layer) between neurons are specified as inhibitory.

[0134] b. Step d above is modified as follows:

[0135] If i fires, and if j fires, i.e., when $\sum _i{w}_{\mathrm{ji}}\ge {\theta }_j$

[0136] Then reset r/s as above.

[0137] In these rules, the feedback loops in the architecture are treated identically to the pathways from input to output. To employ alternate backpropagation maximization schemes, however, such as Linsker's “infomax,” the feedback loops can be treated differently, with the weights reset according to the maximization scheme. This makes the network a hybrid feedforward/backpropagation network. This approach is more expensive in memory, but potentially faster.

[0138] To model “forgetting,” which avoids saturation of the synaptic weights, any of these versions can be modified by introducing a decay factor. Since the decay factor is not related to activity, but simply to time, any synaptic junction that is inactive will eventually approach a connectivity of zero, for any non-zero decay rate. Decay at a synapse can then be modeled by: $w_{\mathrm{ji}}\left(t\right)=\frac{r+\alpha -\beta }{s+\eta +\delta \left(t\right)}$

[0139] for α+β=η all positive; δ(t)≧0 monotone increasing

[0140] where α is the number of excitations, and β is the number of inhibitions.

[0141] Other decay rates are possible. For example, the common form $w_{\mathrm{ji}}\left(t\right)=\frac{r+\alpha -\beta }{s+\eta }-\delta \left(t\right);\delta \left(t\right)\ge 0$ $e.g.\delta \left(t\right)=e^{-\mathrm{kt}}\left(\frac{r+\alpha -\beta }{s+\eta }\right)$

[0142] The decay can also consist of a simple instruction to reset to default values.

[0143] The architecture has three components: 1) an input component; 2) a processing component; and 3) an output component. It therefore has a minimum of three layers. When there are more than three layers, the components overlap. That is, the last input layer is also the first processing layer. Similarly, the last processing layer is also the first output layer.

[0144] The input component consists of one or more feedforward layers. The first layer takes its input from measurements of the environment as described above.

[0145] The processing layer consists of three or more layers. At least the middle layer has lateral connectivity within a given channel, and to other channels. Lateral connectivity within other layers of this component can be specified as desired. The layers also have internal feedback as indicated in the diagrams. Output feedback feeds to the first processing layer.

[0146] The output component has one or more feedforward layers, with final output to the environment as described above. Feedback from the final output goes to the first processing layer.

[0147] The architecture must have a channelized structure because the underlying Polya process converges to a stationary distribution as the number of actions goes to infinity. Hence the learning characteristics are maximized when the number of elements in each layer in a channel is the minimum necessary to process the data.

[0148] The “leaky” processing feature of the network can be induced by allowing random connections outside a given channel when the signal passes up the layers. This can be accomplished, for example, by employing a Gaussian distribution so that connections from one layer to the next are scattered around a mean corresponding to a direct vertical connection. The variance of the Gaussian distribution would determine how “leaky” the channel was.

[0149] Learning characteristics of the network are also affected by how channels are interconnected. If related data is processed in adjacent channels in the network, it would find the correlation much more quickly than if the channels were widely separated.

[0150] Consequently, the learning characteristics of the network are crucially linked to the size and interconnections of the channels. This is particularly so due to the simple nature of the learning rules.

[0151] The attractor concept underlying this design is also important because, as illustrated in FIG. 1a, successful combinations of weights and channels can be recorded and programmed in other networks as, for example, pattern classifiers or processors, so that the new networks need not be trained for that capability. In this way, recorded attractors can be used as a programming language for feedforward or hybrid neural networks. Specialized circuits or chips can also model the attractors.

[0152] The disclosed neural network architecture is particularly suited to neural network implementations which use specialized chips and very-large scale integrated (VLSI) circuit technology. In particular, floating gate transistor designs, such as that disclosed by Hasler, et al, in “Single Transistor Learning Synapses,” Advances in Neural Information Processing Systems 7”, MIT Press, the entire disclosure of which is incorporated herein by reference, can be applied at each node of the architecture of the invention. In such applications, the learning rules can be implemented by adding electrons (through injection) or removing electrons (through tunneling). On a larger scale, the architecture of the invention can be implemented using one or more Field Programmable Gate Array (FPGA) devices such as those disclosed by Martin Bolton in. “Programmable Arrays,” The Electrical Engineering Handbook, 2d ed, the entire disclosure of which is incorporated herein by reference. Moreover, the network architecture of the invention also lends itself toward designing such FPGA devices by modeling the connections and contents of the logic cells that drive them. The network architecture of the invention can be implemented using other programmable logic devices (PLDs) as well.

[0153] FIGS. 11-18 show schematic diagrams illustrating the principles of application-specific self-adjusting, multi-channel, multi-layer architectures that employ non-stationary learning rules to create fractal dimensional data arrays for computation. In particular, the following applications are described: a textual or oral language parser (FIG. 11), a basic file searcher (FIG. 12), an advanced file searcher (FIG. 13), an advanced file searcher that can search for propositions (FIG. 14), a translator (FIG. 15), a basic “smart” scanner (FIG. 16), an advanced “smart” scanner or oral parser (FIG. 17), and a dialect parser for oral language (FIG. 18).

[0154] These applications have a number of common features. Inputs are delivered into a flexible number of channels, determined by the total number of scanned letters, input phonemes, words, or propositional values in the input sample. The arrays in each channel are then combined in patterns that depend on values derived from lookup tables or templates. Feedback from one or two layers higher in the central processing segment of the architecture further alters the arrays, where the learning rules reinforce template matches and also decrement failures to match. The lookup or template-matching steps also alter the arrays to prevent confusion of the data and to augment the information carried forward through the architecture. The output channels transform the arrays into final form as required, as well as reset the initial processing weights for the next processing cycle. These outputs take whatever format desired. For example, they may be printed text, statistical information in digital or graphic form, oral outputs through speakers, data in a register, or inputs to other processing applications.

[0155] Learning rules based on the Polya urn scheme described above would work in this architecture, as would any other convenient rules that reinforce success and suppress mismatches with templates. The effect of such rules is to merge and direct arrays into active channels, while reducing the activity in neighboring channels. The geometric pattern of this process parallels the iterative process used in constructing Cantor-like sets, and thereby creates data arrays across the layers of the architecture with fractal dimension. The actual content of the arrays can theoretically range from single digits to complex contents, as convenient. If restricted to a single bit of content per node, the information would be carried as combinations of active nodes and their geometric distribution, as in FIG. 7. With greater content, the physical distribution can be less important, and more content can be processed and stored at each node. In the applications in FIGS. 11-18, the input content is at least a byte per channel, and increases as the arrays are processed.

[0156] The parser in FIG. 11 receives oral or written input separated into words. Oral inputs received as features or formants would require the more complex architecture at FIG. 17. The words proceed to the next layer, where the network accesses a glossary or dictionary, which labels the words by type. Lateral feedback at this level would suppress impossible combinations. At the next layer, the network matches each adjacent pair of words to possible templates, such as Determiner+Noun. Feedback to the previous layer would suppress further impossible combinations, and reinforce matches. Lateral feedback would also do this. At the third processing layer, the network would access clausal templates against the remaining pairs of words, again suppressing impossibilities and reinforcing matches. This layer would be capable of checking for word-order clues. Feedback from this layer to the first processing layer can check for verb agreement and other such characteristics, thereby reducing the number of remaining options, and reinforcing the rest. At the fourth processing layer, the network accesses sentence templates, which allows it to check for textual relations to other sentences, and to correlate portions of compound, complex, conditional, and other sentence types. Finally, the network resets itself for the next sentence and produces propositional outputs and any desired statistical data. At this level, the parser would be capable of reducing the input text to its logical propositional components (e.g., ‘if a then b,’ ‘either a or b,’ ‘both a and b,’ ‘a but not b,’ etc.), as well as to basic syntactic components V(X, Y, Z)+A, where ‘V’ is the verbal component of each clause, ‘X’ the focus, ‘Y’ the target (if any), ‘Z’ the reference (if any), and ‘A’ is the set of all adjuncts appended to each clause.

[0157] The file searcher designs in FIGS. 12-14 are related to the parser in two ways. First, they share the architectural features mentioned above, with more and more layers added as more and more advanced features are added. Second, they rely on parser outputs as templates for the search. In FIG. 12, the basic search design relies on X- or V-template inputs from the parser. The X-template would produce a noun index related to the focus (typically the subject) noun phrases in a basic text, thereby creating relatively sophisticated search parameters simply by parsing a base document of interest. Similarly, the V-template would employ the verbs as the basis for search. The more advanced search architecture at FIG. 13 allows more processing of the searched files before employing the parser inputs. The searcher would then match X- or V-templates from the base document against comparable arrays in the searched files, thereby creating an index of matching clausal parameters, rather than simple nouns or verbs. The most sophisticated of these searchers is at FIG. 14, which would match entire propositional outputs from the base document and all searched files.

[0158] FIG. 15 applies this approach to language translation. It takes the propositional output from a parsed document (e.g., from FIG. 11) or a parsed oral expression (e.g., from FIG. 17) in one language. It then looks up the words for matches in a second language, adjusts the alternatives against clausal templates of the second language, and finally against full sentence templates. The output would be an expression in the second language with the same propositional content as the input expression.

[0159] FIG. 16 represents a “smart” scanner, which takes inputs from a scanning device, matches the scanned characters against stored font templates, and adjusts the results based on a subsequent retrieval of dictionary information. As with the searcher design, smart scanners can employ any of the lookup/template levels from the parser architecture to adjust the final estimate of what has been scanned.

[0160] The most sophisticated scanner is represented at FIG. 17, which brings sentence templates to bear before producing an output. This architecture would also work for oral input, with phoneme data rather than character data.

[0161] Finally, FIG. 18 shows a design to help calibrate verbal signals. It takes oral inputs as processed into features or formants, then adjusts those estimates for the phonemic environment, for the estimated age and gender of the speaker, and then for regional (dialect) effects. The final output is in standard phonemes, which can be employed by the advanced parser at FIG. 17.

[0162] While the invention has been particularly shown and described with reference to a preferred embodiment thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention.