Neural Network With Learning Function Based on Simulated Annealing and Monte-Carlo Method

1. Field of the Invention

The present invention relates to a neural network which is widely utilized in various applications such as letter recognition, speech recognition, robot motion control, process control in general, and neuro-computers.

2. Description of the Background Art

The backward error propagation scheme is a very well known conventional mechanism for the learning of a multi-layer perceptron, for which much researches have been reported. The actual implementation of the neural network using this scheme has developed significantly. This backward error propagation scheme will be briefly outlined.

A conceptual configuration of a conventional neural network in a three-layer configuration is shown in FIG. 1, which generally comprises an input layer 1, an intermediate layer 2, and an output layer 3. In this neural network, a plurality of neurons are inter-connected through a plurality of synapse connections. In this configuration, learning is realized by comparing a teacher signal [t] with an output [O] outputted from the neuron of the output layer 3 in response to the input of an input pattern [X] entered from the neuron of the input layer 1.

For a certain neuron j, let an input of this neuron j be denoted as net.sub.pj, where a suffix .sub.p indicates that the input is the p-th input pattern [Xp]. Then, this net.sub.pj can be expressed by the following equation (1). ##EQU1## where .omega..sub.ij is a transmission efficiency of a synapse connection connecting the neuron i and the neuron j.

Next, let an input and output function of the neuron j be denoted as f.sub.j. Then, the output O.sub.pj of this neuron j in response to the p-th input pattern [Xp] can be expressed by the following equation (2).

In this case, the evaluation value E.sub.p can be defined by the following equation (3). ##EQU2## where t.sub.pj is a desired output of the neuron j. In other words, this evaluation value E.sub.p reflects the difference between the actual output and the desired output, so that it is desirable to minimize this evaluation value.

In order to minimize this evaluation value E.sub.p of the equation (3) by using the steepest descent method, it is known that a partial derivative of E.sub.p with respect to .omega..sub.ij should be used as an update value .DELTA..sub.p .omega..sub.ij for the synapse transmission efficiency .omega..sub.ij. Consequently, it is known that the update value .DELTA..sub.p .omega..sub.ij for the synapse transmission efficiency can be expressed by the following equation (4).

where .eta. is a relaxation coefficient and .delta..sub.pj is given by the following equation (5) when the neuron j belongs to the output layer 3,

and otherwise .delta..sub.pj is given by the following equation (6). ##EQU3## where ' denotes a derivative.

This manner of updating the synapse transmission efficiency according to the equation (4) has been known as the backward error propagation algorithm.

When this backward error propagation algorithm is applied to the neural network, as shown in FIG. 2, the input pattern [X] is entered into the neuron of the input layer 1, and propagated to the neuron of the intermediate layer 2 and the neuron of the output layer 3 through synapse connections, and the output [O] is outputted from the neuron of the output layer 3. On the other hand, the teacher signal [t] and this output [O] are compared at the neuron of the output layer 3 to obtain an error signal to be propagated through the neurons of each layer in a backward direction with respect to the propagation of the input, while updating the synapse transmission efficiency at each neuron according to the equation (4), so as to reduce the error of the output with respect to the teacher signal sequentially.

This process is called learning. Thus, in the backward error propagation scheme, it is necessary to provide a path for propagating the signal to be utilized in the learning process backwards, from the output side to the input side.

Now, this learning mechanism based on the backward error propagation scheme is known to work effectively in the computer simulation. However, the actual implementation of this learning mechanism by dedicated hardware has encountered various difficulties.

For example, in order to realize this learning mechanism based on the backward error propagation scheme in a large scale neural network by using a compact and inexpensive analog circuits, it becomes necessary to construct circuitry for carrying out the procedures described above by combining various circuit elements, such as multipliers and adders. However, in such a construction, the inevitable processing error introduced by the analog circuit for calculating the solution to the above equation (4) can severely deteriorate the performance of the neural network as a whole.

In addition, the backward error propagation scheme requires very high level precision in each neuron and each synapse for the backward propagation of the error signal, in order to achieve the effective learning, so that the very expensive, high precision circuit elements must be used for neurons and synapses, and even when such expensive circuit elements are used, there still remains a possibility for the performance of the neural network to be affected by offsets and variations among the circuit elements.

Moreover, there are cases in which it is quite difficult to obtain the truly optimum solution (absolute minimum) in the backward error propagation scheme using the steepest descent method.

Furthermore, the backward error propagation scheme is applicable only to the network having a multi-layer structure as shown in FIGS. 1 and 2. Consequently, there has been no known method for appropriately adjusting the synapse transmission efficiency for a case involving the feedback of the synapses or the loop formed by the synapses.

It is therefore an object of the present invention to provide a neural network with a learning function which does not require the backward propagation of the signals for learning.

It is another object of the present invention to provide a learning function for a neural network which is applicable for a case involving feedback of the synapses or the loop formed by the synapses.

It is another object of the present invention to provide a learning function for a neural network which enables the construction of a large scale neural network by using compact and inexpensive circuit elements.

According to one aspect of the present invention, there is provided a neural network device with a learning function, comprising: a network formed by a plurality of neurons inter-connected by a plurality of synapses, each synapse having its own synapse weight factor; comparison means for calculating an evaluation value according to a difference between each output signal of the network and a corresponding teacher signal; and inspection means for determining a manner of updating the synapse weight factor of said each synapse according to an evaluation value change between a present value and a previous value of the evaluation value calculated by the comparison means; wherein said each synapse having: random number generation means for generating a randomly changing update control signal according to a random number; and synapse weight factor update means for updating a synapse weight factor of said each synapse as a learning according to the update control signal generated by the random number generation means and the manner of updating determined by the inspection means.

According to another aspect of the present invention there is provided a method of learning in a neural network formed by a plurality of neurons inter-connected by a plurality of synapses, each synapse having its own synapse weight factor, comprising the steps of: calculating an evaluation value according to a difference between each output signal of the network and a corresponding teacher signal; determining a manner of updating the synapse weight factor of said each synapse according to an evaluation value change between a present value and a previous value of the evaluation value calculated at the calculating step; generating a randomly changing update control signal according to a random number; and updating a synapse weight factor of said each synapse according to the update control signal generated at generating step and the manner of updating determined at the determining step.

Other features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings.

FIG. 1 is a conceptual block diagram of a conventional three layer type neural network for explaining its basic operation.

FIG. 2 is a conceptual block diagram of a conventional three layer type neural network for explaining the learning mechanism based on the backward error propagation scheme.

FIG. 3 is a schematic block diagram of one embodiment of a neural network device according to the present invention.

FIG. 4 is a detailed block diagram of a comparison unit in the neural network device of FIG. 3.

FIG. 5 is a detailed block diagram of an inspection unit in the neural network device of FIG. 3.

FIG. 6 is a detailed block diagram of a synapse in the neural network device of FIG. 3.

FIG. 7 is a detailed block diagram of a random number generation unit in the synapse of FIG. 6.

FIG. 8 is a detailed block diagram of a transmission efficiency update unit in the synapse of FIG. 6.

FIG. 9 is a schematic block diagram of a modified configuration of a comparison unit that may be used in the neural network device of FIG. 3.

FIG. 10A is a schematic block diagram of an alternative configuration of a random number generator that may be used in the random number generation unit of FIG. 7.

FIG. 10B is a schematic block diagram of an alternative configuration of a random number generator that may be used in the random number generation unit of FIG. 7, which generalizes the configuration shown in FIG. 10A.

Referring now to FIG. 3, one embodiment of a neural network device according to the present invention will be described in detail.

In this embodiment, the neural network device comprises: a network 100 formed by a plurality of neurons 110 inter-connected by a plurality of synapses 200; a comparison unit 300 for comparing an output signal [O] of the neural network 100 in response to an input signal [X] with a teacher signal [t] to obtain an evaluation value; an inspection unit 400 for determining whether or not to update the transmission efficiency at the synapses 200; and a control unit 500 for supplying control signals to the synapses 200 of the network 100.

In this embodiment, the transmission efficiency at each synapse is used as a synapse weight factor to be updated.

As indicated in FIG. 3, the output signal [O] of the network 100 is outputted not only to the comparison unit 300, but also to an external device (not shown).

Here, the notation of the input signal [X]=(x.sub.1, x.sub.2, . . . , x.sub.m), the teacher signal [t]=(t.sub.1, t.sub.2, . . . , t.sub.n), and the output signal [O]=(O.sub.1, O.sub.2, . . . , O.sub.n) will be used below.

In this embodiment, the evaluation value is defined by either one of the following equations (7) and (8). ##EQU4##

In general, the evaluation value in this embodiment can be expresses as the following equation (9). ##EQU5## where g is a function which is minimum when (t.sub.i -O.sub.i)=0, monotonically increasing when t.sub.i -O.sub.i >0, and monotonically decreasing when t.sub.i -O.sub.i <0.

Referring now to FIG. 4, a detailed configuration of the comparison unit 300 will be described.

As shown in FIG. 4, the comparison unit 300 further comprises: as many difference calculation units 310-1 to 310-n as a number of neuron (n in this embodiment) in the network 100, and a sum calculation unit 320. Each difference calculation unit 310-i (i=1 to n) contains a first A/D converter 311-i for A/D converting the i-th output signal O.sub.i, a second A/D converter 312-i for A/D converting the i-th teacher signal t.sub.i, and a subtractor 313-i for calculating a difference (t.sub.i -O.sub.i) between the A/D converted i-th output signal and the A/D converted i-th teacher signal. The sum calculation unit 820 calculates a sum .SIGMA. .vertline.t.sub.i -O.sub.i .vertline. of the difference (t.sub.i -O.sub.i) calculated by the difference calculation units 310-1 to 310-n, in a case of using the evaluation value E of the equation (7). The sum calculated by the sum calculation unit 820 is then outputted to the inspection unit 400 as the evaluation value E.

In this configuration of FIG. 4, the sum calculation unit 320 has a calculation precision equal to (1+ln 2n) x (a precision of each neuron output).

Here, each of the first A/D converter 311-i and the second A/D converter 312-i may be formed by a circuit for converting a voltage value into a charge amount. Also, in a case of using an analog subtractor for the subtractor 313-i, the first A/D converter 311-i and the second A/D converter 312-i will be unnecessary, and the circuit configuration of the comparison unit 300 can be simplified.

Referring now to FIG. 5, a detailed configuration of the inspection unit 400 will be described.

This inspection unit inspects whether the evaluation value E entered from the comparison unit 300 has increased or decreased compared with the previous evaluation value, and outputs an inspection output to each of the synapses 200.

As shown in FIG. 5, the inspection unit 400 further comprises: a first hold circuit 410 for holding the evaluation value E entering from the comparison unit 300; a delay circuit 420 for delaying the evaluation value E entering from the comparison unit 300; a second hold circuit 430 for holding the evaluation value E delayed by the delay circuit 420; a comparator 440 for comparing the evaluation values held by the first and second hold circuits 410 and 430; and a judgement circuit 450 for judging the acceptance of a comparison result obtained by the comparator 440 as the inspection output of the inspection unit 400.

In this inspection unit 400 of FIG. 5, the present evaluation value held by the first hold circuit 410 and the previous evaluation value held by the second hold circuit 430 are compared at the comparator 440, and the comparator 440 outputs a comparison result .DELTA.E indicating whether the evaluation value has increased or decreased from the previous value to the present value. Here, the comparison result .DELTA.E may be given as a logical value "0" when the evaluation value has increased, and as a logical value "1" when the evaluation value has decreased.

The judgement circuit 450 makes the judgement regarding the acceptance of the comparison result .DELTA.E outputted from the comparator 440 as the inspection output of the inspection unit 400, by utilizing the technique of the simulated annealing as follows.

Namely, in this judgement circuit 450, according to the idea of the Boltzmann machine, a "temperature" variable T(.tau.) as a function of a discrete time (.tau.=0, 1, 2, etc.) is defined by the following equation (10). ##EQU6## where T.sub.0 is a prescribed initial value. According to this equation (10), this "temperature" variable T gradually decreases as the discrete time .tau. progresses.

Then, the judgement circuit 450 rejects the comparison result .DELTA.E="0" indicating the increase of the evaluation value E only at a probability p defined by the following equation (11). ##EQU7##

When the comparison result .DELTA.E="0" is rejected, the inspection output of the inspection unit 400 is changed to "1", whereas when the comparison result .DELTA.E="0" is not rejected, the inspection output of the inspection unit 400 is "0" as obtained by the comparator 440. As for the comparison result .DELTA.E="1", the inspection output of the inspection unit 400 is always "1" as obtained by the comparator 440.

It is to be noted here that the comparison result .DELTA.E obtained by the comparator 440 may be used directly as the inspection output of the inspection unit 400 by bypassing the judgement circuit 450 as indicated by the dashed line in FIG. 5, provided that evaluation value E as a function has a unique minimum. However, when this bypassing is adopted in a case the evaluation value E as a function has local minima along with an absolute minimum, only one of the local minima of the evaluation value E can be found, so that the simulated annealing cannot be achieved effectively.

Referring now to FIG. 6, a detailed configuration of the synapse 200 will be described.

As shown in FIG. 6, the synapse 200 further comprises: a random number generation unit 210 for generating an update control signal as a random number according to the inspection output and control signals 216,217, and 218 supplied from the control unit 500; a transmission efficiency update unit 220 for determining an updated transmission efficiency according to the update control signal supplied from the random number generation unit 210 at a timing given by a system clock 223; and a multiplier 230 for multiplying a synapse input and the updated transmission efficiency determined by the transmission efficiency update unit 220 to obtain a synapse output.

Here, the control unit 500 supplies the same control signals 216, 217, and 218 to all of the synapses 200 of the network 100.

In this configuration of FIG. 6, the transmission efficiency .omega. of the synapse 200 can be updated by an amount of either +.DELTA..omega. or -.DELTA..omega. in the transmission efficiency update unit 220, according to the update control signal based on the random number which is generated by the random number generation unit 210, in a manner of the Monte-Carlo method.

Referring now to FIG. 7, a detailed configuration of the random number generation unit 210 will be described.

As shown in FIG. 7, the random number generation unit 210 further comprises: a random number generator 213 for generating a random number according to the control signals 217 and 218; a sign inversion circuit 211 for inverting the sign of the random number generated by the random number generator 213 according to the inspection output supplied from the inspection unit 400; and a gain adjustment circuit 212 for adjusting an input and output gain according to the control signal 216, in order to control the absolute value of the random number outputted from the random number generator 213 through the sign inversion circuit 211, so as to obtain the update control signal to be supplied to the transmission efficiency update unit 220.

In further detail, the random number generator 213 is formed by an odd number of inverters 215-1 to 215-k (k is an odd integer) connected in series, a first switch S1 for selectively connecting an output of a second inverter 215-2 to an input of a last inverter 215-k by bypassing a first inverter 215-1 according to the control signal 218, and a second switch S2 for selectively connecting the output of the first inverter 215-1 to the input of the last inverter 215-k according to an inversion of the control signal 218 obtained by an additional inverter 214. The input of the last inverter 215-k is also supplied with the control signal 217 for initialization. Here, the random number to be generated by this random number generator 213 includes +.DELTA..omega. and -.DELTA..omega., which are generated in a random order.

Thus, when the control signal 218 is in ON state, the switch S1 is closed so that the even number of inverters 215-2 to 215-k remains active while the first inverter 215-1 is bypassed, such that the random number outputted to the sign inversion circuit 211 remains the same as the previously generated one. On the other hand, when the control signal is in OFF state, the switch S2 is closed so that the odd number of inverters 215 are active, such that the random number outputted to the sign inversion circuit 211 is a new random number. During generation of a new random number, the output of the update control signal from the random number generation unit 210 is suspended.

The control signal 218 is generated by the control unit 500 according to a random number. In other words, the periods at which the control signal 218 is in ON state is determined according to a random number generated inside the control unit 500.

The sign inversion circuit 211 inverts the sign of the random number supplied from the random number generator 213 when the inspection output supplied from the inspection unit 400 indicates "0" and outputs the sign inverted random number to the gain adjustment circuit 212. This changing of the sign of the random number is incorporated in order to cancel out the previous update due to the previous random number because the inspection output of "0" indicates the increase of the evaluation value E, which is a motion moving away from the minima to be found. Here, however, as a certain number of cases with the increase of the evaluation value E given by the probability p expressed by the equation (11) are allowed to take place as the inspection output is changed from "0" to "1" by the judgement circuit 450 at the probability p, in order to allow the evaluation value to move out from the local minima and to find the absolute minimum.

On the other hand, when the inspection output supplied from the inspection unit 400 indicates "1", the sign inversion circuit 211 leaves the sign of the random number supplied from the random number generator 213 as it is, such that the random number generated by the random number generator 213 is outputted as it is, without changing its sign, to the gain adjustment circuit 212.

The gain adjustment circuit 212 gradually reduce the input and output gain according to the control signal 216, such that the absolute value of the random number .vertline..DELTA..omega..vertline. is decreased gradually. This adjustment of the input and output gain at the gain adjustment circuit 212 is incorporated in order to speed up the learning process.

Referring now to FIG. 8, a detailed configuration of the transmission efficiency update unit 220 will be described.

As shown in FIG. 8, the transmission efficiency update unit 220 further comprises: an up/down counter 221 for counting a count value up or down at a timing specified by the system clock 223 according to the sign and the magnitude of the update control signal supplied from the random number generation unit 210; and a D/A converter 222 for D/A converting the count value obtained by the up/down counter 221 and supplying the D/A converted count value as the updated transmission efficiency to the multiplier 230.

Thus, when the update control signal supplied from the random number generation unit 210 is +.DELTA..omega., the up/down counter counts the count value up by .vertline..DELTA..omega..vertline., whereas when the update control signal supplied from the random number generation unit 210 is -.DELTA..omega., the up/down counter counts the count value down by .vertline..DELTA..omega..vertline..

The D/A converted updated transmission efficiency supplied to the multiplier 230 plays a role of the synapse weight factor to be multiplied with the synapse input to obtain the synapse output.

According to this embodiment, it becomes possible to realize a learning function based on the simulated annealing and the Monte-Carlo method which does not require the very high precision backward propagation of the signals for the learning required in the conventional learning based on the backward error propagation scheme.

As a consequence, the level of the precision required in each neuron and each synapse in order to achieve the effective learning can be reduced considerably, so that the large scale neural network incorporating this learning function can be implemented by using compact and inexpensive circuit elements.

In addition, this learning function based on the simulated annealing and the Monte-Carlo method is applicable to any network configuration in general, including those having the feedback of the synapses or the loop formed by the synapses.

Moreover, this learning function is free of the problem related to the difficulty of finding the absolute minimum by the steepest descent method, so that the reliability of the neural network can be improved according to this embodiment.

It is to be noted that the neural network device of FIG. 3 has been described above in terms of various units for the sake of explanation, but there is no need to implement each of these various units separately, and a part or a whole of the various units involved in this neural network device of FIG. 3 may be implemented in a form of a single neuro-chip in practice.

It is also to be noted that the random number generation at the random number generation unit 210 may not necessarily be totally random, and can be statistically biased to reflect the past effective weight factor (transmission efficiency) update patterns, so as to increases the chance of achieving the effective weight factor update.

It is also to be noted that the neural network device of FIG. 3 may be modified to incorporate the backward propagation of the signals for realizing the learning function based on the backward error propagation scheme, such that the learning process is progressed by using the learning based on the backward error propagation scheme up to a certain level first, prior to the execution of the learning based on the simulated annealing and the Monte-Carlo method according to the present invention, in a case the learning according to the present invention turns out to be rather time consuming.

It is also to be noted that, as shown in FIG. 9, the comparison unit 300 described above may be divided into sub-units (comparison unit-1 300-1 to comparison unit-N 300-N, where N is an integer), each of which is substantially similar to the comparison unit 300 shown in FIG. 4 and the outputs of these sub-units are added together by a summation circuit 300-X. Such a configuration is effective when the number of neuron n involved in the network 100 is very large.

It is also to be noted that the random number generator 213 in the random number generation unit 210 is not necessarily limited to the configuration formed by using the inverters 215 as shown in FIG. 7, and can be replaced by any alternative random number generation circuit.

For example, the random number generation circuit utilizing the thermal noise of the circuit element can be formed in a configuration shown in FIG. 10A in which a thermal noise occurring in resistors 501 connected to a differential amplifier 502 is amplified by the differential amplifier 502 and an inverter 503 to obtain the amplified thermal noise in a form of the random number, and then the obtained random number is latched by a latch circuit 504, which outputs the random number at the timing specified by the control signal 218 to the sign conversion circuit 211.

It is to be noted that the configuration of FIG. 10A is only an example of this type of the random number generation circuit, and can be generalized to a configuration shown in FIG. 10B, in which a thermal noise occurring in a resistor 510 is amplified by an amplifier 520 to obtain the amplified thermal noise in a form of the random number, and the obtained random number is latched by the latch circuit 504, which outputs the random number at the timing specified by the control signal 218 to the sign conversion circuit 211.

Besides these, many modifications and variations of the above embodiment may be made without departing from the novel and advantageous features of the present invention. Accordingly, all such modifications and variations are intended to be included within the scope of the appended claims.