Neural networks and methods for training neural networks

• US 5,426,721 A
• Filed: 06/17/1993
• Issued: 06/20/1995
• Est. Priority Date: 06/17/1993
• Status: Expired due to Term

• Current Assignee: Board of Supervisors of Louisiana State University Agricultural & Mechanical College (Louisiana State University System)
• Original Assignee: Board of Supervisors of Louisiana State University Agricultural & Mechanical College (Louisiana State University System)
• Inventors: Kak, Subhash, Pastor, John F.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Onka, Thomas
• Application Number:
  US08/080,490
• Time in Patent Office: 733 Days
• Field of Search: 395/11, 395/23, 395/24, 395/27
• US Class Current: 706/31
• CPC Class Codes: G06F 18/245 relating to the decision surface
• CPC Class Codes: G06N 3/04 Architecture, e.g. interconnection topology
• CPC Class Codes: G06N 3/08 Learning methods

Abstract

Novel neural networks and novel methods for training those networks are disclosed. The novel networks are feedforward networks having at least three layers of neurons. The training methods are easy to implement, converge rapidly, and are guaranteed to converge to a solution. 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. Four efficient, alternative classification methods for use with the novel neural networks are also disclosed.

Claims

1. A circuit for mapping an n-bit binary input sequence into an m-bit binary output sequence, wherein n is a positive integer and m is a positive integer, said circuit comprising n input neurons, each said input neuron adapted to receive one bit of the n-bit binary input sequence;

a plurality of hidden neurons, each of said hidden neurons having a threshold value; and

m output neurons, each said output neuron adapted to output one bit of the m-bit binary output sequence;

wherein said input neurons, said hidden neurons, and said output neurons comprise a plurality of neural networks, wherein each of said output neurons is associated with one of said neural networks, and wherein each of said neural networks comprises;

(a) said output neuron associated with said neural network;

(b) at least one of said hidden neurons;

(c) at least one of said input neurons;

(d) means, associated with each of said input neurons in said neural network, for distributing an input bit received by that neuron to at least one of said hidden neurons in said neural network;

(e) means, associated with each of said hidden neurons in said neural network, for receiving an input bit distributed from at least one of said input neurons in said neural network;

(f) means, associated with at least one of said hidden neurons in said neural network, for weighting at least one bit received by that hidden neuron;

(g) means, associated with each of said hidden neurons in said neural network, for sending a high signal to the output neuron of said neural network if, and only if, the arithmetic sum of the arithmetic products of each bit received by that hidden neuron multiplied by the weight given to that bit by said weighting means for that bit, or multiplied by zero if there be no said weighting means for that bit, exceeds the threshold value for that hidden neuron, and for outputting a low signal to the output neuron of said neural network otherwise;

(h) means, associated with said output neuron of said neural network, for weighting each high signal received by that output neuron equally with a fixed weight; and

(i) means, associated with said output neuron of said neural network, for outputting a high signal if said output neuron is sent a high signal by at least one of said hidden neurons of said neural network, and for outputting a low signal otherwise;

wherein for each of a plurality of said hidden neurons in said circuit, if the said hidden neuron is a component of one of said neural networks comprising one of said output neurons, then the said hidden neuron is not a component of any of said neural networks which comprises any other of said output neurons.

2. A circuit as recited in claim 1, wherein each of said hidden neurons has said weighting means as defined in part (f) of claim 1, and wherein for each of said hidden neurons in said circuit, if the said hidden neuron is a component of one of said neural networks comprising one of said output neurons, then the said hidden neuron is not a component of any of said neural networks which comprises any other of said output neurons.

3. A circuit as recited in claim 1, wherein each of said hidden neurons has said weighting means as defined in part (f) of claim 1, and wherein the weight vector for each of said hidden neurons is defined to be an ordered set w=w₁ w₂ . . . w_l . . . w_n, wherein w_l denotes the weighting given by said weighting means to the l-th input bit for said hidden neuron, and wherein each of said weight vectors is equal to a weight vector constructed by a process comprising the steps of:

(a) selecting a sample comprising a set of k n-bit binary input sequences x, a set of k m-bit binary output sequences y, and a correlation defining for each input sequence x a corresponding output sequence y, where said correlations are in the form;

space="preserve" listing-type="tabular">______________________________________ 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 ;

______________________________________

(b) generating, for each y_ij having a high value, a weight vector w=w₁ w₂ . . . w_p . . . w_n ; and

(c) for each y_ij having a low value, either generating no weight vector w, or, equivalently, setting all elements of weight vector w equal to 0;

wherein k is a positive integer greater than or equal to 2;

wherein l is a positive integer such that 1≦

l≦

n;

wherein i is a positive integer such that [1≦

l≦

k;

] 2≦

l≦

k; and

wherein j is a positive integer such that 1≦

l≦

m.

4. A circuit as recited in claim 3, wherein said generating of each of said weight vectors w in step (b) of claim 3 comprises the following iterative method:

(a) selecting any initial trial values for w-w₁ w₂ . . . w_n ;

(b) inputting to said circuit one of the sample input sequences x_q -x_q1 x_q2 . . . x_qn, wherein 1≦

q≦

k, and observing the resulting j-th output bit, wherein the j-th output bit is the output of the j-th said output neuron;

(c) if the resulting j-th output bit is high and y_qj is low, then updating w by subtracting x_q from w;

if the resulting j-th output bit is low and y_qj is high, then updating w by adding x_q to w;

or if the resulting j-th output bit equals y_qj, then leaving w unchanged; and

(d) iterating steps (a), (b), and (c) for all sample input vectors x and for all outputs until the resulting j-th output bit equals y_qj in all cases, whereby the values of the weight vectors resulting after said iterating is complete become the weight vectors for the correlations defined by the selected sample.

5. A circuit as recited in claim 3, wherein each of said weight vectors w is equal to a weight vector whose elements w_j are:

##EQU4## wherein s_i is defined as the sum S_i =X_i1 +X_i2 +. . . +X_in.

6. A circuit as recited in claim 3, wherein said generating of each of said weight vectors w in step (b) of claim 3 comprises the following iterative method:

(a) selecting initial trial values for each w_j as follows;

##EQU5## wherein S_i is defined as the sum S_i =x_i1 +x_i2 + . . . +x_in ; and

r_j is a randomly chosen real number greater than or equal to 0, and less than 1; and

(1)) for every j not equal to i, if σ

_j >

0, finding an l such that x_i1 is not equal to x_jl ;

then if x_jl =1, updating w_l by subtracting σ

_j from w_l ;

or if x_jl =0, updating w_l by adding σ

_j to w₁, and also updating w_n+1 by subtracting σ

_j from w_n+1 ;

where σ

_j is defined as the inner product σ

_j =x_j ·

w.

7. A circuit as recited in claim 3, wherein said generating of each of said weight vectors w in Step (b) of claim 3 comprises the following iterative method:

(a) selecting initial trial values for each element w_j of w as follows;

##EQU6## wherein p(j) is a function of j, and R is a function of all the p(j)'"'"'s;

(b) updating each w_j by adding to it a number r_j, where r_j is a number less than or equal to a, and greater than or equal to b, wherein a is a real number and wherein b is a real number;

(c) for every j not equal to i, calculating σ

_j ×

x_j ·

w;

then if σ

_j >

0, choosing a positive integer T and iterating steps (d) and (e) below T times;

(d) finding an l such that x_il is not equal to x_jl ;

(e) if x_il =1, updating w_l by adding σ

_j /T to w_l, and updating w_n+1 by subtracting σ

_j /T from w_n+1 ;

or if x_il =0, updating w_l by subtracting σ

_j /T from w_l.

8. A circuit as recited in claim 7, wherein a<

0<

b, and |a|<

<

|b|.