Method for operating an optimal weight pruning apparatus for designing artificial neural networks

• US 5,636,326 A
• Filed: 07/07/1995
• Issued: 06/03/1997
• Est. Priority Date: 09/04/1992
• Status: Expired due to Term

• Current Assignee: Ricoh Corporation (Ricoh Company Limited)
• Original Assignee: Ricoh Corporation (Ricoh Company Limited)
• Inventors: Hassibi, Babak, Stork, David G.
• Primary Examiner(s): Downs, Robert W.
• Application Number:
  US08/499,386
• Time in Patent Office: 697 Days
• Field of Search: 395/21, 395/23, 395/24
• US Class Current: 706/25
• CPC Class Codes: G01N 33/005 for H2
• CPC Class Codes: G06N 3/082 modifying the architecture, e.g. adding, deleting or silencing nodes or connections
• CPC Class Codes: Y10T 436/20 Oxygen containing
• CPC Class Codes: Y10T 436/22 Hydrogen, per se

Abstract

A method and apparatus for designing a multilayer feed forward neural network that produces a design having a minimum number of connecting weights is based on a novel iterative procedure for inverting the full Hessian matrix of the neural network. The inversion of the full Hessian matrix results in a practical strategy for pruning weights of a trained neural network. The error caused by pruning is minimized by a correction that is applied to remaining (un-pruned) weights thus reducing the need for retraining. However, retraining may be applied to the network possibly leading to further the simplification of the network design.

Claims

1. A method for operating a design system for designing a minimal connection neural network from a given trained neural network design by iteratively pruning, by removing synaptic weights, and by adjusting any remaining synaptic weights so that the resulting neural network design performance satisfies a prescribed error budget, the design system including

a processor control unit for overall control of the design system,

arithmetic processing, and for providing external input/output data ports,

a data memory for storage of neural network input/output data, and neural network design data,

a synaptic weight pruning unit for producing a reduced connection neural network design from a given trained neural network design,

a neural network modelling unit for modelling a neural network from a set of neural network design data that includes a topological network description, a set of synaptic weights, and activation function descriptions,

the method for operating the design system comprising:

(a) storing the given trained neural network design data that includes a topological network description, activation function descriptions, and synaptic weight values;

(b) storing a set of exemplar input pruning vectors and corresponding response vectors for use in the neural network pruning module;

(c) initializing the neural network modelling unit using the set of trained neural network design data;

(d) operating the neural network modelling unit using the set of exemplar input pruning vectors as input data and storing each response vector in data memory;

(e) initializing the neural network pruning unit with initializing data that includes the stored trained neural network design data together with the set of exemplar pruning response vectors and the corresponding response vectors from step (d);

(f) operating the synaptic weight pruning unit for producing an iterated set of pruned neural network design data, the operating step including

(i) computing a Hessian matrix of the trained neural network using the initializing data from step (d),

(ii) computing an inverse Hessian matrix of the Hessian matrix of step (f)(i),

(iii) computing a saliency value of each synaptic weight using the inverse Hessian matrix and the stored trained synaptic weights,

(iv) selecting a synaptic weight with the smallest salient value as a selected pruning candidate weight,

(v) computing a total error value that would result from pruning the selected pruning candidate weight,

(vi) comparing the total error value with a specified error budget value and proceeding to step (g) if the total error value is less, otherwise terminating the method because the given trained neural network design is the minimal connection neural network design;

(g) operating the synaptic weight pruning unit for pruning and post pruning synaptic weight correction by

(i) pruning the candidate weight by removing the candidate weight from the given trained neural network design data,

(ii) modifying the topological network description by eliminating the pruning candidate weight branch,

(iii) computing a weight correction vector, with one vector element for each remaining weight of the given trained neural network design data, that minimizes the total error value caused by pruning the pruning candidate weight, and

(iv) adjusting the synaptic weights by applying the weight correction vector elements to the corresponding synaptic weights; and

(h) performing another iteration by returning to step (c) and using the modified topological description and the adjusted synaptic weights of step (g) as the given trained neural network design data topological description and synaptic weights.

2. The method of claim 1 wherein step (f)(ii) computing the inverse of the Hessian matrix is an iterative process, wherein the (m+1)^th estimate of the inverse of the Hessian matrix, H^-1, is computed in accordance with ##EQU26## where:

H₀^-1 =[a^-1 l.]α

^-1 l, α

is a small constant (10^-8 <

α

<

10^-4);

I is an identity matrix;

X.sup.[k] is a partial derivative vector calculated from the trained neural network to the k^th input exemplar pruning vector, f(net.sup.[k]), and ##EQU27## f'"'"'(net.sup.[k])_q is the partial derivative of the activation function, f(net), with respect to the weight v_q connecting the q^th hidden layer output, 0_q.sup.[k], in response to the k^th pruning vector, evaluated at net=net.sup.[k], f'"'"'(net_q.sup.[k])_m is the activation function, f(·

), partial derivative with respect to m^th weight connecting the input layer to the q^th hidden layer, evaluation at net=net_q, the input value to the q^th hidden layer activation function;

P is the total number of exemplar pruning vectors, 1≦

k≦

P; and

T is a transpose operator.

3. The method of claim 1 wherein the untrained multilayer neural network includes an input layer of n_i input terminals, indexed 1≦

i≦

n_i, a hidden layer of n_j neurons, indexed 1≦

j≦

n_j, each hidden layer neuron having a set of synaptic weights, {u_ji }, where synaptic weight u_ji connects the j^th hidden layer neuron to the i^th input layer terminal, and an output layer of no neurons, indexed 1≦

b≦

n₀, each output layer neuron with a set of synaptic weights, {v_bj }, where synaptic weight v_bj connects the j^th hidden layer neuron output to the b^th output layer neuron, each hidden layer and output layer neuron have an activation function, f(·

), for operating on a sum of synaptic weighted input signals, net, associated with each neuron for producing a neuron output signal, f(net), step (f)(i) for computing the Hessian matrix comprising;

(a'"'"''"'"') forming a matrix of partial derivative vectors, {X.sup.[b,k] }, one partial derivative vector for each output layer neuron observed response, f(net.sup.[k])_b, where ##EQU28## T is a transpose operator, k is the input exemplar pruning vector index,

f'"'"'(net.sup.[k])_j is the partial derivative of the activation function f(net) with respect to the synaptic weight v_j, evaluated at net=net.sup.[k], where net.sup.[k] is the value of net in response to the k^th input exemplar pruning vector,

.sub. j.sup.[k] is the j^th hidden layer neuron output in response to the k^th input exemplar pruning vector, f'"'"'(net_j.sup.[k])_i is the partial derivative of the activation function with respect to u_ji evaluated at net=net_j.sup.[k], the sum of all synaptic weighted input values to the j^th hidden layer neuron activation function in response to the k^th input exemplar pruning vector; and

(b'"'"''"'"') iteratively computing Hessian matrix estimates using the following expressions;

space="preserve" listing-type="equation">H.sub.b+1,k =H.sub.b,k +1/PX.sup.[b+1,k] ·

X.sup.[b+1,k]T,

space="preserve" listing-type="equation">H.sub.1,k+1 =H.sub.n.sbsb.0.sub.,k +1/PX.sup.[1,k+1] ·

X.sup.[1,k+1]T,

space="preserve" listing-type="equation">H.sub.0,k =α

l,

H_n.sbsb.0.sub.,P is the P^th estimate where P is the number of input exemplar pruning vectors, α

is a small constant (10^-8 <

α

<

10^-4), and l is an identity matrix.

4. The method of claim 3 wherein step (f)(ii) of computing the inverse of the Hessian matrix is an iterative process in accordance with the following expressions:

##EQU29##

5. The method of claim 1 further comprising the following steps that are executed by the synaptic pruning module prior to terminating the method of claim 17:

(a'"'"''"'"''"'"') identifying a set of inoperative neural cells of the trained multilayer neural network that have all of their outputs connected to pruned synaptic weights; and

(b'"'"''"'"''"'"') pruning the set of inoperative neural cells and their associated synaptic weights for further reducing the complexity of the trained multilayer neural network.

6. The method of claim 1 wherein the selecting step (f)(iv) is for selecting a single pruning operation candidate weight.

7. The method of claim 1 wherein the selecting step (f)(iv) is for selecting more than one low saliency pruning operation candidate weights.

8. The method of claim 1 wherein step (k)(iv) is for selecting at least one complete set of synaptic weights belonging to a common neuron.

9. The method of claim 1 wherein the synaptic weight pruning unit and the neural network modelling unit are programs operating in the processor control unit.

10. A method for operating a design system for designing a minimal connection neural network from a given untrained neural network design by training the untrained network using a set of exemplar input training vectors and a set of exemplar response vectors, then operating on the resulting trained neural network design by iteratively pruning, by removing synaptic weights, and by adjusting any remaining synaptic weights so that the resulting neural network design performance satisfies a prescribed error budget, the design system including

a control unit for overall control of the design system and for providing external input/output data ports,

a data memory for storage of neural network input/output data, and neural network design data,

a neural network training unit for training of an untrained neural network and for producing a trained neural network design by using a set of exemplar training input vectors and corresponding exemplar response vectors,

a synaptic weight pruning unit for producing a reduced connection neural cell design from a given trained neural network design,

a neural network modelling unit for modelling a neural network from a set of neural network design data that includes a topological network description, a set of synaptic weights, and activation function descriptions,

the method for operating the design system comprising:

(a) storing the untrained neural network design that includes a topological network description, activation function descriptions, and synaptic weight values,

(b) storing a set of exemplar input and output training vectors;

(c) initializing the neural network modelling unit with a set of untrained neural network design data that includes a topological network description, a set of synaptic weights, and activation function descriptions,

(d) operating the neural network training unit for controlling the neural network modelling module for generating a response to a set of exemplar input training vectors, comparing each response vector to a corresponding exemplar response vector, and adjusting the untrained neural network set of synaptic weights in accordance with a known training procedure, for generating a description of a trained neural network design data,

(e) storing the trained neural network design data that includes a topological network description, activation function descriptions, and synaptic weight values;

(f) storing of a set of exemplar input pruning vectors and corresponding response vectors for use in the neural network pruning unit;

(g) initializing the neural network modelling unit using the trained neural network design data;

(h) operating the neural network modelling unit using the set of exemplar input pruning vectors as input data and storing each response vector in data memory;

(j) initializing the neural network pruning unit using the stored trained neural network design data together with the set of exemplar pruning response vectors and the corresponding response vectors from step (h);

(k) operating the neural network pruning unit for producing an iterated set of pruned neural network design data, the operating step including

(i) computing a Hessian matrix of the trained neural network using the data from step (h),

(ii) computing an inverse Hessian matrix of the Hessian matrix of step (h)(i),

(iii) computing a saliency value of each synaptic weight using the inverse Hessian matrix and the stored trained synaptic weights,

(iv) selecting a synaptic weight with the smallest salient value as a selected pruning candidate weight,

(v) computing a total error value that would result from pruning the selected pruning candidate weight,

(vi) comparing the total error value with a specified error budget value and proceeding to step (I) if the total error value is less, otherwise terminating the method;

(l) operating the synaptic weight pruning module for pruning and post pruning synaptic weight correction by

(i) pruning the candidate weight by removing the candidate weight from the trained neural network design data,

(ii) modifying the topological network description by eliminating the pruning candidate weight branch,

(iii) computing a weight correction vector, with one vector element for each remaining weight of the trained neural network design data, that minimizes the total error value caused by pruning the pruning candidate weight, and

(iv) adjusting the synaptic weights by applying the weight correction vector elements to the corresponding synaptic weights; and

(m) performing another iteration by returning to step (g) and using the modified topological description and the adjusted synaptic weights of step (I) as the trained neural network design data topological description and synaptic weights.

11. The method of claim 10 wherein the untrained multilayer neural network includes an input layer of n_i input terminals, indexed 1≦

i≦

n_i, a hidden layer of n_j neurons, index 1≦

j≦

n_j, each hidden layer neuron having a set of synaptic weights, {u_ji }, where synaptic weight u_ji connects the j^th hidden layer neuron to the i^th input layer terminal, and an output layer neuron with a set of synaptic weights, {v_j }, where synaptic weight v_j connects the output of the j^th hidden layer neuron, each hidden layer neuron and the output layer neuron having an activation function f(·

) for operating on a sum of synaptic weighted input signals, net, associated with each neuron for producing a neuron output signal f(net), the step of computing the Hessian matrix comprising;

(a'"'"') forming a k^th partial derivative vector, X.sup.[k], from the observed output layer response f(net.sup.[k]) where net[^k] is the value of net for the output layer neuron is response to a k^th input exemplar pruning vector, where ##EQU30## f'"'"'(net.sup.[k])_b is the partial derivative of f(net.sup.[k])_b, the output layer b^th neuron response to the k^th input exemplar pruning vector, with respect to the weight v_bj that connects the output of the j^th hidden layer neuron to the b^th output layer neuron, evaluated at net=net.sup.[k], and 1≦

b≦

n_j,

T is a transpose operator,

o_j,b.sup.[k] is the output of the hidden layer j^th neuron in response to the k^th input exemplar pruning vector,

f'"'"'(net_j.sup.[k])_i is the partial derivative of the activation function with respect to u_ji evaluated at net=net.sup.[k], the sum of all synaptic weighted input values to the j^th hidden layer neuron activation function in response to the k^th input exemplar pruning vector; and

(b'"'"') iteratively computing a Hessian matrix estimate, H_m+ 1, from (m+1) successive partial derivative vectors in accordance with ##EQU31## where H_b =α

l, l is an identity matrix, α

is a small constant (10^-8 <

α

<

10^-4), until m+1=P so that Hp is a final Hessian matrix obtained by using P input exemplar pruning vectors.

12. The method of claim 10 wherein the neural network training unit, the synaptic weight pruning unit, and the neural network modelling unit are programs operating in the processor control unit.