Patent Publication Number: US-5426721-A

Title: Neural networks and methods for training neural networks

Description:
This invention pertains to novel neural networks, and to novel methods for training those neural networks. 
     A neural network is a set of computational units which are interconnected in a manner generally analogous to the interconnections of biological neurons. A circuit which resembles in some way the interconnections of biological neurons may be called a neural network. Each computational unit comprises a neuron, one or more inputs, one or more outputs, and means to transform the input signals into output signals. The interconnections between neurons are typically given different weights. An input for one neuron may be connected to an external input source, or to the output of another neuron. Typical uses for neural networks are to learn facts or patterns, and to show associative recall of the stored patterns. 
     A multilayered neural network has one or more layers of &#34;hidden&#34; neurons between the input layer of neurons and the output layer of neurons. Multilayered networks are attractive for many types of problems because such networks have non-linear capabilities. The seemingly simple &#34;Exclusive-Or&#34; problem is a canonical example of a nonlinear problem. 
     Neural networks must generally be &#34;trained&#34; for a particular task. In other words, the network must learn a set of interconnection weights which are appropriate for a specified problem. Finding generally effective training methods for multi-layered networks has remained a difficulty. The so-called &#34;back-propagation&#34; training method has often been used, but this iterative method can be slow to converge to a solution. Furthermore, it may not always find a solution if the iterative steps converge to a local minimum rather than to the desired global minimum. See, e.g., Rumelhart et al., &#34;Learning Internal Representations by Error Propagation&#34; in Rumelhart et al. (Eds.), Parallel Distributed Processing: Explorations in the Microstructure of Cognition. Vol. 1: Foundations, pp. 318-362 (1986); and see generally Lippmann, &#34;An Introduction to Computing with Neural Nets,&#34; IEEE ASSP Magazine, pp. 4-22 (April 1987). 
     Novel neural networks and novel methods for training those networks have been discovered. The novel networks are feedforward networks having at least three layers of binary neurons. The training method is easy to implement, converges rapidly, and is guaranteed to converge to a solution (provided only that the mapping is self-consistent). A novel network structure is used, in which each corner of the input vector hypercube may be considered separately. The problem of mapping may be reduced to a sum of corner classification sub-problems. Three highly efficient alternative training methods have also been discovered. 
     The novel methods are guaranteed to find a solution, and they provide an upper bound on the number of hidden neurons which are necessary for a specified mapping. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates an embodiment of a novel neural network architecture in accordance with the present invention. 
     FIG. 2 illustrates an embodiment of the present invention which maps the Exclusive-Or function for two variables. 
     FIG. 3 illustrates an embodiment of the present invention which maps a specified, arbitrary function. 
    
    
     A n-dimensional &#34;binary vector&#34; is an ordered set of n elements, where each of the elements has one of two possible values: 1 or 0, on or off, true or false, high or low, etc. For example, (0 1 1 0 1 0) is a 6-dimensional binary vector. Consider the mapping Y=f(X), where X and Y are n- and m-dimensional binary vectors, respectively. The ultimate goal is to implement the mapping Y=f(X) on a neural network. 
     Let the number of the sample vectors X used to train the network be k, so that we can write Y i  =f(X i ), i=1, . . . , k. A novel procedure is described below for realizing the mapping Y=f(X) with a 3-layered, &#34;feedforward&#34; network of binary neurons. (A &#34;feedforward&#34; network is one in which the flow of information from neuron to neuron is one-way; i.e., there is no feedback.) The three neuron layers are conventionally called the input neurons, the &#34;hidden&#34; neurons, and the output neurons. The input neurons distribute input data to the second layer, the &#34;hidden&#34; neurons. The hidden neurons perform intermediate calculations, whose results are distributed to the output neurons. The output neurons perform final calculations, and output the results. See, e.g., FIG. 1, illustrating an embodiment of the novel neural network architecture. In FIG. 1, note that each output neuron is associated with a distinct &#34;subset neural network&#34; of the overall neural network depicted. The numbers of input and the output neurons are n and m, respectively. 
     The output of a neuron is 1 if the weighted sum of the signals into the neuron is greater than the neuron&#39;s threshold T, and is 0 otherwise. The output o j  of neuron j may be written as: ##EQU1## where w ij  is the weight given to the ith input to the jth neuron. 
     For convenience only, we will typically add an extra constant value input to each neuron, so that the threshold for each neuron can be made equal to zero for simplicity. The weight given to this additional input can thus simulate any desired threshold value. Where a threshold is not otherwise specified, it will be assumed to be zero. The transformation Y i  =f(X i ), i=1, . . . , k may be written in the form of an array as follows: 
     
         ______________________________________                                    
Sample      Input        Output                                           
______________________________________                                    
1           x.sub.11 x.sub.12 . . . x.sub.1n                              
                          y.sub.11 . . . y.sub.1m                         
2           x.sub.21 x.sub.22 . . . x.sub.2n                              
                          y.sub.21 . . . y.sub.2m                         
.           .            .                                                
.           .            .                                                
.           .            .                                                
i           x.sub.i1 x.sub.i2 . . . x.sub.in                              
                          y.sub.i1 . . . y.sub.ij . . . y.sub.im          
.           .            .                                                
.           .            .                                                
.           .            .                                                
k           x.sub.k1 x.sub.k2 . . . x.sub.kn                              
                          y.sub.k1 . . . y.sub.km                         
______________________________________                                    
 
    
     This array format emphasizes that the outputs may also be written as a sequence of m, k-dimensional vectors W j  =(y 1j  y 2j  . . . y kj ). 
     The &#34;weight&#34; of a binary vector is defined to be the number of its elements having the value 1. The weight of Y i  will be denoted α i , and the weight of vector W j  =(y 1j  y 2j  . . . y kj ) will be denoted β j . 
     For purposes of illustration, consider the output y 1  =(y 11  y 21  . . . y k1 ). This output defines vector W 1 . It will now be shown how this output may be obtained with a 3-layered network. The other m - 1 outputs may be obtained in an analogous fashion. 
     The y 1  values for the k samples determine the W 1  vector. By definition, W 1  has exactly β 1  elements of value 1. Thus the vector W 1  can be written as a sum of β 1  different binary vectors, each of which contains a single 1, and whose other elements are all 0. This is an important step in the novel technique. The next step is to classify the input n-dimensional vectors that produce a 1 in the output. 
     A single neuron suffices to realize each of these β 1  vectors. This fact may be visualized by placing the input X i  vectors on the corners of an n-dimensional hypercube; each of these corners may be isolated with a single hyperplane. In other words, a total of β 1  neurons suffices to isolate the β 1  corners corresponding to the vector W 1 . These β 1  &#34;hidden&#34; neurons, connected to the n input lines through weights that define appropriate hyperplanes, produce a 1 output for the specified input vectors. Then the outputs of these neurons are processed through a logical-Or operation to give the correct response for the output layer neuron. Therefore, the hidden neuron outputs may each be fed to a single output neuron, through links each having a weight of 1. The threshold of an output neuron should be less than 1, and greater than or equal to 0 to ensure a 1 output for all the corners that were isolated by the β 1  hidden layer neurons. (Recall that a neuron produces an output of 1 only when the sum of the inputs exceeds its threshold.) Although a zero threshold may suffice, it is preferred to use a higher threshold, such as one about 1/β 1 , to allow for possible noise. 
     This procedure may be followed for each of the m output neurons. The corner classification procedure guarantees the realization of the mapping. 
     In some cases, some of the hidden neurons generated by this procedure may be redundant or duplicative; removing redundant neurons can increase efficiency. Consider the following function: ##EQU2## It has been found that the number of hidden neurons which are duplicative equals Σγ i . Thus the number of hidden neurons required to realize the mapping Y i  =f(X i ), i=1, 2, . . . , k is equal to Σβ i  -Σγ i . It also follows that the number of hidden neurons required to realize a mapping is at most k. Thus, while each output is associated with a &#34;subset neural network&#34; of the overall neural network, there may be overlap in the sense that a given &#34;subset neural network&#34; may feed to more than one output° 
     There are a number of ways to-construct a set of weights to isolate a corner of the n-dimensional input vector cube. One way is as follows: An initial set of weights is chosen, perhaps at random. Whenever the neuron makes a mistake with a given input, the weights are changed to make the mistake less likely; this process is iterated for all neurons and for all sample inputs. This application of the so-called &#34;perceptron&#34; method will converge in a finite number of steps. Let the inputs and the weights be represented by the vectors (x 1  x 2  . . . x n ) and (w 1  w 2  . . . w n ), respectively. An extra input x n+1  is assumed, having a constant value of 1, requiring the addition of an extra weight w n+1 . (Recall that the extra 1 input and the extra weight are used only to simulate the effect of the threshold, so that the actual threshold may be 0 in all cases if desired.) The perceptron method as applied to this problem may be stated as follows: 
     1. Start with any trial weight vector; the trial weight vector may be random, or may be the all-zero vector. 
     2. Feed a sample input vector to the network with the trial weight vector, and monitor an output neuron. 
     3. If the output is 0 when it should be 1, add the input vector to the trial weight vector. 
     4. If the output is 1 when it should be 0, subtract the input vector from the trial weight vector. 
     5. If the output is correct, leave the trial weight vector unchanged, and iterate steps 2-4 for all sample input vectors and all output neurons, until all outputs are correct for all sample inputs, at which point the now-converged trial weight vector may be considered the final weight vector. 
     A proof of these results is presented in Kak, &#34;On training feedforward neural networks,&#34; Pramana Journal of Physics vol. 40, no. 1, pp. 35-42 (1993), the entire disclosure of which is incorporated by reference. 
     Example 1: The Exclusive-Or Mapping 
     The Exclusive-Or mapping is not linearly separable, and has therefore often been used as a benchmark to test neural network training methods. The Exclusive-Or mapping for the two inputs x 1  and x 2  is illustrated below: 
     
         ______________________________________                                    
Sample      x.sub.1                                                       
                   x.sub.2    x.sub.3                                     
                                  Output                                  
______________________________________                                    
1           0     0           1   0                                       
2           0     1           1   1                                       
3           1     0           1   1                                       
4           1     1           1   0                                       
______________________________________                                    
 
    
     This table shows the extra input x 3  =1, used to allow the hidden layer neurons also to learn their thresholds. 
     For the Exclusive-Or mapping m=1, and Σβ i  =2. Thus two hidden layer neurons are needed for the mapping. The training method splits the output vector (0 1 1 0) into the sum of two component vectors, each having a single element of 1: (0 1 0 0) and (0 0 1 0). 
     The two input corners to be isolated are (0 1) and (1 0), because these inputs are the ones corresponding to a 1 output. The geometry of these two corners is such that the equations for the corresponding hyperplanes need not have constant terms. So for this example the weight component for x 3  turns out to be zero for each case, as we will see on the application of the corner classification algorithm. 
     The transformation to be realized for the first component output vector (0 1 0 0) is: 
     
         ______________________________________                                    
Sample      x.sub.1                                                       
                   x.sub.2    x.sub.3                                     
                                  Output                                  
______________________________________                                    
1           0     0           1   0                                       
2           0     1           1   1                                       
3           1     0           1   0                                       
4           1     1           1   0                                       
______________________________________                                    
 
    
     This transformation can be realized by the weights (-1 1 0), which may be obtained with the corner classification method described above. Starting with a zero trial weight vector (0 0 0), the sequence converges in two steps: 
     
         ______________________________________                                    
 0 0 0         (initial trial weights)                                    
 0 1 1         (first iteration)                                          
-1 1 0         (second, converged iteration)                              
______________________________________                                    
 
    
     The weights are obtained in 2 steps. (The calculations of the intermediate steps in the method are not shown, but may readily be followed by applying the 5-step method described above.) Note that these weights work because the threshold has been taken to be zero. 
     Now consider the second basis transformation: 
     
         ______________________________________                                    
Sample      x.sub.1                                                       
                   x.sub.2    x.sub.3                                     
                                  Output                                  
______________________________________                                    
1           0     0           1   0                                       
2           0     1           1   0                                       
3           1     0           1   1                                       
4           1     1           1   0                                       
______________________________________                                    
 
    
     Application of the same method gives the sequence: 
     
         ______________________________________                                    
0                0     0                                                  
1                0     1                                                  
0               -1     0                                                  
1               -1     1                                                  
0               -2     0                                                  
1               -2     1                                                  
1               -2     0                                                  
______________________________________                                    
 
    
     Six iterations were needed to obtain these weights. With the weights for the input layer, the design is now complete, because the weights in the output layer are all equal to 1. The threshold of the neuron in the output layer may be set to be 1/β 1  =0.5, or indeed any suitable non-negative value. 
     The resulting network to realize the Exclusive-Or mapping is illustrated in FIG. 2. The total number of iterative steps required was a mere 8. By contrast, it has been reported that 6,587 iterations were required to solve the same problem with the basic backpropagation algorithm (although modifications to the basic backpropagation algorithm might reduce the number of iterations required somewhat.) See Rumelhart et al., Parallel Distributed Processing, vol. 1, p. 332 (1986). The backpropagation algorithm encounters such difficulty because unlike the present invention, it does not take advantage of the structure of the training samples. 
     In other experiments done in our laboratory (data not shown), the novel feedforward method has exhibited a neural network training time about 50 times faster than that of the backpropagation method; it is expected that this training-time-differential factor will increase as the size of a problem increases. The greatly reduced training time required by the novel networks can be very important in addressing real-time or near-real-time neural network calculations. The generalization performance of the novel networks in the experiments was often as good as that of backpropagation-generated networks, but in some cases was slightly less. 
     EXAMPLE 2 
     Consider the mapping shown below, with x 5  as a constant input for training the neuron thresholds. 
     
         ______________________________________                                    
Sample    x.sub.1                                                         
                  x.sub.2                                                 
                         x.sub.3                                          
                              x.sub.4                                     
                                   x.sub.5                                
                                         y.sub.1                          
                                              y.sub.2                     
______________________________________                                    
1         0      1      1    1    1     1    0                            
2         1      0      1    1    1     1    1                            
3         1      0      0    0    1     0    1                            
4         0      1      1    0    1     0    0                            
5         1      1      0    0    1     0    0                            
______________________________________                                    
 
    
     By inspection, β 1  =2 and β 2  =2. An initial design would therefore require 2+2=4 hidden neurons. However, by inspection α 2  =2, meaning that the number of hidden neurons may be reduced by one. Thus three hidden neurons are needed. 
     The weights (-2 0 0 1 0) and (0 -2 0 1 0) were found to represent solutions for the output y 1 . (The starting weight vectors used were randomly chosen, and were not all 0.) Likewise, the weights (0 -2 0 1 0) and (1-2 -2 -2 0) are found to classify the corners for the output y 2 . Because two of these 4 hidden neurons are identical, one of them may be deleted. The final design is illustrated in FIG. 3. 
     A First Alternative Classification Method 
     Following is a description of an alternative method of isolating the corners of the n-dimensional input vector hypercube. 
     We wish to isolate the input vector X i  by a hidden neuron. The hidden neuron should produce a 1 corresponding to this input, and a 0 corresponding to all other inputs. This result can be achieved By using weights which are positively correlated with X i , and which are negatively correlated with all other input vectors. 
     Let the inputs (including an extra x n+1  =1 input for learning the thresholds) and the weights be represented by vectors X +  =(x 1  x 2  . . . x n  x n+1 ) and W +  =(w 1  w 2  . . . w n  w n  +1), respectively. (The &#34;+&#34; superscript signifies the addition of the extra (n+1)st term in each vector. ) First, we assign w n+1  =1 for the all-zero vector. The least integer value which w n+1  may assume is 1, because there are no non-zero values in this vector with which to establish a positive correlation. This choice then forces the w n+1  values for all other vectors to be either zero or negative. For the other cases we assign w n+1  =1-S i , where S i  is the weight of the sequence X i  ; this weighting ensures that sequences with lower weights are not classified. (Note that the weight of the all-zero sequence is 0; therefore, the w n+1  required to classify it is 1-0=1, consistent with the above result.) To establish negative correlation the weight w i  for an x i  =0 is taken to be -1. The resulting values of w n+1  become increasingly more negative for X i  &#39;s of larger weight, defining hyperplanes moving further away from the origin. 
     To summarize, the weights are as follows: ##EQU3## The value of w j  =1-S i  implies that the threshold of the hidden neuron to separate this sequence is S i  -1. 
     The weights established by this method are one possible set of solutions for the mapping problem, a set of weights which represents the smallest integer values which will solve the problem. 
     Example 3: The Exclusive-Or Mapping 
     
         ______________________________________                                    
Sample      x.sub.1                                                       
                   x.sub.2    x.sub.3                                     
                                  Output                                  
______________________________________                                    
1           0     0           1   0                                       
2           0     1           1   1                                       
3           1     0           1   1                                       
4           1     1           1   0                                       
______________________________________                                    
 
    
     As before, m=1 and Σβ i  =2, so 2 hidden neurons are needed. 
     Using our corner classification formula, the weight vectors corresponding to X 2  and X 3  with this method are readily seen to be (-1 1 0) and (1 -1 0) by inspection. The fact that w 3  is 0 in both cases means that the threshold of both hidden neurons is 0. 
     A Second Alternative Classification Method 
     A variation on the first alternative classification method can yield better generalization capabilities than the first alternative method, but still demonstrate rapid training times. The weights are initially assigned as in the first alternative method described above. Then the weights are randomly raised by an amount r j , without changing the threshold values: for each j=1, 2, . . . , n, w j  is raised by an amount r j  randomly chosen from the interval [0, R), R&lt;1. (For example, R may be taken to be 0.5.) 
     After adding these random factors, the weights are updated as described below. For each j=1, . . . , i-1, i+1, . . . , k, the indices of the remaining input vectors in the training set, one calculates the inner product S=X j+  ·W + . If S&gt;0, one does either of the following: 
     (a) Find an l such that X i   l  =0 and X j   l  =1; and update w l  to be w l  -S; or 
     (b) Find an l such that X i   l  =1 and X j   l  =0; and update w l  to be w l  +S; and also update W n+1  to be w a+  -S. 
     This procedure thus increases the correlation between w and X i , and reduces the correlation between w and the other input vectors in the training set. Note that, unlike the &#34;perceptron&#34; approach, this method requires only one pass through the input vectors of a training set to converge. 
     Example4, Using the Second Alternative Classification 
     This example is based on the problem of predicting a particular bond&#39;s interest rate for the next month, based on its monthly interest rate for each of the previous eight months. (Actual historical financial data were used, but are not shown here.) If the interest rate is represented by a three bit binary sequence, a 24-bit input vector will represent a bond&#39;s monthly interest rate for the eight preceding months, and a three-bit output will represent the predicted interest rate for the ninth month. 
     The training set consisted of 52 input-output pairs obtained from actual historical financial data. Table 1 shows a comparison of the time required to learn the 52 input-output pairs of the training set with the two &#34;generalizable&#34;  classification methods discussed thus far. Training time was measured by the number of times a weight vector was updated, and by the number of passes made through the input vectors of the training set. Note that the number of passes required by the one-pass classification scheme equals the number of hidden neurons in the network. 
     
                       TABLE 1                                                     
______________________________________                                    
               no. of updates                                             
                         no. of passes                                    
______________________________________                                    
Sample 1                                                                  
        original method                                                   
                     920         444                                      
        2nd alternative                                                   
                      32          48                                      
Sample 2                                                                  
        original method                                                   
                     800         391                                      
        2nd alternative                                                   
                      41          49                                      
______________________________________                                    
 
    
     After the training was completed, input vectors from outside the training set were presented to the network. The network&#39;s predictions were compared to the actual ninth month interest rate. The generalization capability provided by each of the two classification algorithms was compared by comparing the percentage of predictions which were within a specified percent of the actual rate. This comparison is shown in Table 2. 
     
                       TABLE 2                                                     
______________________________________                                    
            Percent Difference from Actual Rate                           
            0%   5%     10%     15%   20%                                 
______________________________________                                    
Sample 1                                                                  
        original  40%    66%  100%  100%  100%                            
        2nd altern.                                                       
                  55%    60%  90%   93%   100%                            
Sample 2                                                                  
        original  20%    33%  53%   80%    93%                            
        2nd altern.                                                       
                  33%    60%  82%   89%   100%                            
______________________________________                                    
 
    
     A Third Alternative Classification Method 
     A third alternative is a generalization of the second alternative. First, W +   is initialized so that it is highly correlated with the corner it classifies, and is correlated weakly, negatively, or not at all with the other input vectors. The initialization may include a representation of the relative importance of each of the n bits. Thus for j=1, . . . , n, we initially take w j  =p(j) if x ij  =1; and w j  =-p(j) if x ij  =0, where p(j) is a function assigning higher or lower priority to bit j, depending on its relative importance. 
     Next, set w a+1  =R-(p(1)x i1  +p(2)x i2  + . . . +p(n)x in ), where R is a function of the p (j)&#39;s; for example, R=(p(1)+ . . . +p(n))/n. 
     Note that if p(i)=1 for all values of i, this initialization is the same as that for the first alternative classification method above. 
     Next, randomly adjust the weights--typically the weights should be raised more frequently than they are lowered, in order to give better generalization by increasing positive correlations. I.e., update w j  by replacing it with w j  +r j , where r j  ε[a, b]; where typically a&lt;0&lt;b, and |a|&lt;&lt;|b|. 
     Then the weights are adjusted as follows. For jε {1, 2, . . . , i-1, i+1, . . . , k}, calculate s=W +  ·X j+ . If S&gt;0, a positive integer T is chosen, and the following two steps are iterated T times: 
     (1) Choose an integer l such that x jl  is not equal to x il . 
     (2) If x il  =1, raise w l  by s/T, and lower w n+1  by s/T. If x il  =0 lower w l  by s/T. 
     Example 5, Using The Third Alternative Method As an example, again consider the following function of two binary variables: 
     
         ______________________________________                                    
        Input Output                                                      
______________________________________                                    
        0 0   0                                                           
        0 1   1                                                           
        1 0   1                                                           
        1 1   0                                                           
______________________________________                                    
 
    
     Let 
     X 1  =[0 0] 
     X 2  =[0 1] 
     X 3  =[1 1] 
     X 4  =[1 1] 
     The feedforward network may thus consist of (a) three input neurons, where the third input has a constant value of 1; (b) two hidden neurons; and (c) one output neuron. The first hidden neuron classifies X 2 , and the second hidden neuron classifies X 3 . We need to select appropriate three-dimensional weight vectors w i  for i=1 and 2. 
     Case 1 Suppose both bits are given equal priority. Then p(1)=p(2)=1, and R=1. First we take as initial values w 1  =[-1 1 0] and w 2  =[1 -1 0]. With the p&#39;s equal, these initial values are in accordance with the first alternative classification. Next, we randomly adjust by adding numbers in the interval [-0.05, 0.35], giving weight vectors w 1  =[-0.81 1.02 0] and w 2  =[0.96 -1.04 0]. 
     Then the weights are adjusted as described above. For example, to adjust w 1 , we calculate X i  ·w 1  for each i≠2, where a third bit equal to 1 is added to each input vector X. This inner product exceeds 0 only in the case of X 4  ·w 2  =1.02-0.81=0.21. Because x 2i ≠X 4i  only for i=1, we lower w 11  by 0.21, giving w=[-1.02 1.02 0]. 
     For w 2 , we calculate X i  ·w 2  for each i≠3. None of these inner products exceeds 0, so w 2  remains [0.96 -1.04 0]. 
     Case 2 For the same mapping, suppose that each input vector is a 2-bit binary representation of an integer between 0 and 3. The left bit is thus more significant than the right. This greater significance may be expressed by setting p(1)=1, and p(2)=0.5. Then R=(1+0.5)/2=0.75, and the above procedure gives as initial weightings w 1  =[-1 0.5 0.25] and w 2  =[1 -0.5 -0.25]. 
     Randomly adjusting the weights with the same components in the interval [-0.05, 0.35] as in Case 1 yields w 1  =[-0.81 0.52 0.25] and w 2  =[0.96 -0.54 -0.25]. Then, adjusting the weights as provided in the last step above, the final w 1  remains [-0.81 0.52 0.25]. Because X 4  ·w 2  =0.17, we decrease w 22  by 0.17, to give a final w 2  of [0.96 -0.71 -0.25]. 
     General 
     Individual neurons in accordance with the present invention may be formed from any electrical, electronic, or logical devices which perform the indicated functions. Such devices are well known to the art, and their details are therefore not further specified. 
     It is intended that these inventions include any equivalents to the descriptions contained in the specification and claims, such as would result, for example, from substituting equivalent circuit elements, or from a transformation of the logic by an application of DeMorgan&#39;s Theorem.