Neural network for processing both spatial and temporal data with time based back-propagation

• US 5,253,329 A
• Filed: 12/26/1991
• Issued: 10/12/1993
• Est. Priority Date: 12/26/1991
• Status: Expired due to Fees

• Current Assignee: The United States of America As Represented By The Secretary of Agriculture
• Original Assignee: United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration
• Inventors: Villarreal, James A., Shelton, Robert O.
• Primary Examiner(s): MacDonald, Allen R.
• Application Number:
  US07/813,556
• Time in Patent Office: 656 Days
• Field of Search: 395/24, 395/23
• US Class Current: 706/31
• CPC Class Codes: G06N 3/049 Temporal neural networks, e.g. delay elements, oscillating neurons or pulsed inputs

Abstract

Neural network algorithms have impressively demonstrated the capability of modelling spatial information. On the other hand, the application of parallel distributed models to processing of temporal data has been severely restricted. The invention introduces a novel technique which adds the dimension of time to the well known back-propagatio

ORIGIN OF THE INVENTION

The invention described herein was made by employees of the United States Government and ma be manufactured and used by or for the Government of the United States of America for governmental purposes without payment of any royalties thereon or therefor.

Claims

1. A processing element (i) for use in a space-time neural network for processing both spacial and temporal data, wherein the neural network comprises a plurality of layers of said processing elements, the plurality of layers comprising a first layer and at least one additional layer, the network further comprising connections between processing elements of the first layer and processing elements of an additional layer:

each said processing element adapted to receive a sequence of signal inputs X(n), X(n-1), X(n-2) . . . , each input X(n) comprising K signal components x₁ (n), x₂ (n), . . . x_j (n), . . . x_k (n), each said processing element comprising, in combination;

(a) a plurality K of adaptable filters (F_1i, F_2i, . . . F_ji, . . . F_ki) each filter F_ji having an input for receiving a respective component x_j (n), x_j (n-1), x_j (n-2), . . . , of said sequence of inputs, where x_j (n) is the most current input component, and providing a filter output y_j (n) in response to the input x_j (n) which is given by;

space="preserve" listing-type="equation">y.sub.j (n)=f(a.sub.mj Y.sub.j (n-m), b.sub.kj X.sub.j (n-k)),

where a_mj and b_kj are coefficients of the filter F_ji and f denotes the operation of the filter;

(b) a junction, coupled to each of said adaptive filters, providing a non-linear output p_i (S_i (n)) in response to the filter outputs y_j (n) which is given by;

space="preserve" listing-type="equation">p.sub.i (S.sub.i (n))=f(y.sub.j (n)),

where S_i (n) is the sum of the filter outputs,

whereby said junction presents a sequence of output signals, p_i (S_i (n)), p_i (S_i (n-1)), p_i (S_i (n-2)).

2. The processing element defined in claim 1, wherein said non-linear output provided by said junction is the sum S_i (n) of the filter outputs modified by a non-linear transformation p_i (S_i (n)) to the sum S_i (n), where S_i (n) is given by:

space="preserve" listing-type="equation">S.sub.i (n)=Σ

.sub.j y.sub.j (n).

3. The processing element defined in claim 2, wherein the non-linear transformation is a sigmoid transfer function given by:

space="preserve" listing-type="equation">p.sub.i (S.sub.i (n))=1/(1+e-S.sub.i (n)).

4. The processing element defined in claim 1, wherein said filters are non-linear filters.

5. The processing element defined in claim 4, wherein said non-linear filters are exponential auto-regressive filters.

6. The processing element defined in claim 1, wherein the coefficients a_mj and b_kj of each filter F_ji are adjustable.

7. The processing element defined in claim 1, wherein said adaptable filters are digital filters.

8. The processing element defined in claim 7, wherein said filters are linear filters.

9. The processing element defined in claim 8, wherein said filters are recursive, infinite impulse response filters and wherein the response of each filter is given by:

##EQU9##

10. The processing element defined in claim 8, wherein said filters are nonrecursive finite impulse response filters and wherein the response of each filter is given by:

##EQU10##

11. The processing element defined in claim 8, wherein the response of each filter is given by:

##EQU11##

12. The processing element defined in claim 11, further comprising means for adjusting the coefficients a_mj and b_kj of each filter F_ji in dependence upon the junction output p_i (S_i (n)).

13. The processing element defined in claim 12, wherein said adjusting means includes means for determining an error in the output p_i (S_i (n)) between the actual and desired response of the processing element (i) and adjusting the filter coefficients a_mj and b_kj of each filter F_ji in dependence upon said error.

14. The processing element defined in claim 13, wherein the non-linear transformation is a sigmoid transfer function with output p_i (S_i (n)) given by:

space="preserve" listing-type="equation">p.sub.i (S.sub.i (n))=1/(1+e-S.sub.i (n)).

15. The processing element defined in claim 14, wherein said error Δ

_i (n) is given by;

space="preserve" listing-type="equation">Δ

.sub.i (n)=(D.sub.i (n)-A.sub.i (n)) p'"'"'(S.sub.i (n))

where;

D_i (n) is the nth desired response from a given sequence for neuron i at the output layer

A_i (n) is the network'"'"'s output response i for the nth input sequence pattern

p'"'"'(S_i (n)) is the first derivative of p_i (S_i (n)), the non-linear transfer function for the ith output'"'"'s activation value or in the case of said sigmoid non-linear transfer function, p'"'"'(S_i (n)) is given by;

space="preserve" listing-type="equation">p'"'"'(S.sub.i (n))=p.sub.i (S.sub.i (n))(1-p.sub.i (S.sub.i (n))).

16. The processing element defined in claim 15, wherein said filter coefficient b_ijk is adjusted in accordance with the formula:

space="preserve" listing-type="equation">Δ

b.sub.ijk =α

[η

Δ

b.sub.ijk.sup.old +(1-η

)Δ

.sub.i (n) x.sub.j (n-k)]

where;

Δ

b_ijk is the update for a zero coefficient, b_ijk, lying between processing elements i and j

α

is the learning rate of the neural network

Δ

b_ijk^old is the most recent update for the kth zero element between processing elements i and j

η

damps the most recent update

X_j (n-k) is the output of the jth neuron in the hidden layer.

17. The processing element defined in claim 15, wherein said filter coefficient a_ijk is adjusted in accordance with the formula:

space="preserve" listing-type="equation">Δ

a.sub.ijk =α

[η

Δ

a.sub.ijk.sup.old +1-η

)Δ

.sub.i (n) y.sub.ij (n-k)]

where;

Δ

a_ijk is the update for a pole coefficient, a_ijk, lying between processing elements i and j

α

is the learning rate of the neural network

Δ

a_ijk^old is the most recent update for the kth pole coefficient between processing elements i and j

η

damps the most recent update

y_ij (n-k) is the activation value for the filter elements between neurons i and j, k time steps ago.

18. The processing element defined in claim 15, wherein said filter coefficients a_ijk and b_ijk are adjusted in accordance with the formula:

space="preserve" listing-type="equation">Δ

b.sub.ijk =α

[η

Δ

b.sub.ijk.sup.old +(1-η

)Δ

.sub.i (n) x.sub.j (n-k)]

space="preserve" listing-type="equation">Δ

a.sub.ijk =α

[η

Δ

a.sub.ijk.sup.old +(1-η

)Δ

.sub.i (n) y.sub.ij (n-k)]

where;

Δ

a_ijk is the update for a pole coefficient a_ijk lying between processing elements i and j

Δ

b_ijk is the update for a zero coefficient b_ijk lying between processing elements i and j

α

is the learning rate of the neural network

Δ

b_ijk^old is the most recent update for the kth zero element between processing elements i and j

η

damps the most recent update

Δ

a_ijk^old is the most recent update for the kth pole element between processing elements i and j

x_j (n-k) is the output of the jth neuron k time steps ago

y_ij (n-k) is the activation value for the filter element between neurons i and j, k time steps ago.

19. A neural network for processing both spacial and temporal data, wherein said neural network comprises a plurality of layers of processing elements, the plurality of layers comprising a first layer and a second layer, the network further comprising connections between processing elements of the first layer and processing elements of the second layer;

said first layer of said network adapted to receive a sequence of signal inputs X(n), X(n-1), X(n-2) . . . , each input X(n) comprising N signal components x₁ (n), x₂ (n), . . . x_j (n), . . . x_N (n), said first layer of said network comprising, in combination;

(a) a plurality L of first processing elements, each first processing element (i) comprising a plurality N of adaptable filters (F_1i, F_2i, . . . F_ji, . . . F_Ni), each filter F_ji having an input for receiving a respective component x_j (n), x_j (n-1), x_j (n-2), . . . , of said sequence of inputs, where x_j (n) is the current input component, and providing a filter output y_j (n) in response to an input x_j (n) which is given by;

space="preserve" listing-type="equation">y.sub.j (n)=f(a.sub.mj y.sub.j (n-m), b.sub.kj x.sub.j (n-k)),

where a_mj and b_kj are coefficients of the filter F_ji and f denotes the action of the filter;

each first processing element (i) further comprising a first junction, coupled to each of said adaptive filters, providing a non-linear output p_i (S_i (n)) in response to the filter outputs y_j (n) which is given by;

space="preserve" listing-type="equation">p.sub.i (S.sub.i (n))=f(y.sub.j (n)),

where S_i (n) is the sum of the filter outputs,

each first junction presenting a sequence of first output signals, p_i (S_i (n)), p_i (n-1)), p_i (S_i (n-2)), . . . .

20. The neural network defined in claim 19, wherein said second layer comprises:

a plurality of M of second processing elements (k) each coupled to a plurality of said first junctions, each second processing element comprising a plurality O of adaptable filters (F_1k, F_2k, . . . F_hk, . . . F_Ok), each connected to one of said first junctions, each filter F_hk having an input for receiving a respective first junction output signal S_k (n), S_k (n-1), S_k (n-2), . . . , of said sequence of first junction output signals, where S_k (n) is the most current output signal, and providing a filter output, y_h (n), in response to an input S_k (n) which is given by;

space="preserve" listing-type="equation">y.sub.i (n)=f(C.sub.qk Y.sub.h (n-1)), d.sub.rk p.sub.k (S.sub.k (n-r)),

where C_qk and d_rk are coefficients of the filter F_hk and f denotes the action of the filter;

each second processing element (k) further comprising a second junction, coupled to each of said second adaptive filters of the respective second processing element and providing a non-linear output p_g (S_g (n)) in response to the filter outputs y_h (n) which is given by;

space="preserve" listing-type="equation">p.sub.g (S.sub.g (n))=f(y.sub.h (n)),

where S_g (n) is the sum of said second filter outputs,

each second junction presenting a sequence of second output signals p_g (S_g (n)), p_g (S_g (n-1), p_g (S_g (n-2)), . . . .

21. The network defined in claim 20, wherein said non-linear outputs provided by said junctions are a sum S_g (n) of the filter outputs modified by an arbitrary non-linear transformation p_g (S_g (n)) to the sum S_g (n), where S_g (n) is given by:

##EQU12##

22. The network defined in claim 21, wherein the non-linear transformation is a sigmoid transfer function given by:

space="preserve" listing-type="equation">p.sub.i (S.sub.i (n))=1/(1+e-S.sub.i (n)).

23. The network defined in claim 20, wherein said filters are non-linear filters.

24. The network defined in claim 23, wherein said non-linear filters are exponential auto-regressive filters.

25. The network defined in claim 20, wherein said adaptable filters are digital filters.

26. The network defined in claim 25, wherein said filters are linear filters.

27. The network defined in claim 26, wherein said filters are recursive, infinite impulse response filters and wherein the response of each filter is given by:

##EQU13##

28. The network defined in claim 26, wherein said filters are non-recursive finite impulse response filters and wherein the response of each filter is given by:

##EQU14##

29. The network defined in claim 26, wherein the response of each filter is given by:

##EQU15##

30. The network defined in claim 29, wherein the coefficients c_mj and d_kj of each filter F_ji are adjustable.

31. The network defined in claim 29, further comprising means for adjusting the coefficients c_mj and d_kj of each filter F_ji in dependence upon the plurality N of junction outputs p_g (S_g (n)).

32. The network defined in claim 31, wherein said adjusting means includes means for determining and error in said outputs p_g (S_g (n)) between the actual and desired response of the network and adjusting the filter coefficients c_mj and d_kj of each filter F_ji in dependence upon said error.

33. The network defined in claim 32, wherein the non-linear transformation is a sigmoid transfer function given by:

space="preserve" listing-type="equation">p.sub.g (S.sub.g (n))=1/(1+e-S.sub.g (n)).

34. The network defined in claim 33, wherein said error is given by:

space="preserve" listing-type="equation">δ

.sub.g =(D.sub.g (n)-A.sub.g (n)) p'"'"'(S.sub.g (n))

where;

D_g (n) is the nth desired response from a given sequence for neuron g at the output layer

A_g (n) is the network'"'"'s output response at neuron g for the nth input sequence pattern

p'"'"'(S_g (n)) is the first derivative of the non-linear transfer function for the gth output'"'"'s activation value or in the case of said sigmoid non-linear transfer function, p'"'"'(S_g (n)) is given by

space="preserve" listing-type="equation">p'"'"'(S.sub.g (n))=p(S.sub.g (n)) (1-p)S.sub.g (n))).

35. The network defined in claim 34, wherein the kth zero coefficient d_ijk of the filter between first processing element j and second processing element i is adjusted in accordance with the formula:

space="preserve" listing-type="equation">Δ

d.sub.ijk =α

[η

Δ

d.sub.ijk.sup.old +(1-η

) Δ

.sub.i.sub.x.sub.j (n-k)]

where;

Δ

d_ijk is the update for a zero coefficient, d_ijk, lying between first processing element j and second processing element i

α

is the learning rate of the neural network

Δ

d_ijk^old is the most recent update for the kth zero coefficient between first processing element j and second processing element i

η

damps the most recent update

x_j (n-k) is the output of the jth first processing element k time steps in the past.

36. The network defined in claim 34, wherein the kth pole coefficient for said filter between first processing element j and second processing element i, c_ijk, is adjusted in accordance with the formula:

space="preserve" listing-type="equation">Δ

c.sub.ijk =α

[η

Δ

c.sub.ijk.sup.old +(1-η

) Δ

.sub.i.sub.y.sub.ij (n-k)]

where

Δ

c_ijk is the update for the kth pole coefficient, c_ijk, lying between first processing element j and second processing element i

α

is the learning rate of the neural network

Δ

c_ijk^old is the most recent update for the kth pole coefficient between first processing element j and second processing element i

η

damps the most recent update

y_ij (n-k) is the activation value for the filter element between first processing element j and second processing element i, k time steps in the past.

37. The network defined in claim 34 wherein said filter coefficients c_ijk and d_ijk are adjusted in accordance with the formulae:

space="preserve" listing-type="equation">Δ

d.sub.ijk =α

[η

Δ

d.sub.ijk.sup.old +(1-η

) Δ

.sub.i.sub.x.sub.j (n-k)]

space="preserve" listing-type="equation">Δ

c.sub.ijk =α

[η

Δ

c.sub.ijk.sup.old +(1-η

) Δ

.sub.i.sub.y.sub.ij (n-k)]

where;

Δ

c_ijk is the update for the kth pole coefficient c_ijk lying between first processing element j and second processing element i

Δ

d_ijk is the update for the kth pole coefficient d_ijk lying between first processing element j and second processing element i

α

is the learning rate of the neural network

Δ

d_ijk^old is the most recent update for the kth zero element between first processing element j and second processing element i

η

damps the most recent update

Δ

c_ijk^old is the most recent update for the kth zero element between first processing element j and second processing element i

x_j (n-k) is the output of the jth first processing element k time steps in the past

y_ij (n-k) is the activation value for the filter element between first processing element j and second processing element i, k time steps in the past.

38. The network defined in claim 34, wherein the kth pole coefficient for said filter between network input element j and first processing element i, a_ijk, is adjusted in accordance with the formula:

space="preserve" listing-type="equation">Δ

a.sub.ijk =α

[η

Δ

a.sub.ijk.sup.old +(1-η

)ε

.sub.i y.sub.ij (n-k)]

where

Δ

a_ijk is the update for the kth pole coefficient, a_ijk, lying between network input element j and first processing element i

α

is the learning rate of the neural network

Δ

a_ijk^old is the most recent update for the kth pole coefficient between network input element j and first processing element i

ε

_i is the backpropagated network error at the ith first processing element

η

damps the most recent update

y_ij (n-k) is the activation value for the filter element between network input element j and first processing element i, k time steps in the past.

39. The network defined in claim 34 wherein said filter coefficients a_ijk and b_ijk are adjusted in accordance with the formulae:

space="preserve" listing-type="equation">Δ

b.sub.ijk =α

[η

Δ

b.sub.ijk.sup.old +(1-η

)ε

.sub.i x.sub.j (n-k)]

space="preserve" listing-type="equation">Δ

a.sub.ijk =α

[η

Δ

a.sub.ijk.sup.old +(1-η

)ε

.sub.i y.sub.ij (n-k)]

where;

Δ

a_ijk is the update for the kth pole coefficient a_ijk lying between network input element j and first processing element i

Δ

b_ijk is the update for the kth zero coefficient b_ijk lying between network input element j and first processing element i

ε

_i is the backpropagated network error at the ith first processing element

α

is the learning rate of the neural network

Δ

b_ijk^old is the most recent update for the kth zero element between network input element j and first processing element i

η

damps the most recent update

Δ

a_ijk^old is the most recent update for the kth pole coefficient of the filter between network input element j and first processing element i

x_j (n-k) is the jth network input k time steps in the past

y_ij (n-k) is the activation value for the filter element between network input element j and first processing element i, k time steps in the past.

40. The network defined in claim 34, wherein the kth zero coefficient b_ijk of the filter between network input element j and first processing element i is adjusted in accordance with the formula:

space="preserve" listing-type="equation">Δ

b.sub.ijk =α

[η

Δ

b.sub.ijk.sup.old +(1-η

)ε

.sub.i x.sub.j (n-k)]

where;

Δ

b_ijk is the update for a zero coefficient, b_ijk, lying between network input element j and first processing element i

ε

_i is the backpropagated network error at the ith first processing element

α

is the learning rate of the neural network

Δ

b_ijk^old is the most recent update for the kth zero coefficient between network input element j and first processing element i

η

damps the most recent update

x_j (n-k) is the jth network input k time steps in the past.

41. The network described in claim 33, further comprising a means for propagating the error Δ

_g (n) measured at the outputs of the gth second processing element backward through the intervening filter connections between first and second processing elements thereby to provide a means for adjusting the coefficients of the filters which connect the inputs of the network to the first processing elements.

42. The network defined in claim 38, wherein said means for backward propagation of error is described by the formula:

##EQU16## where ε

_i (n) is the result of backward propagation of network error from the outputs of all second processing element through the filters between first processing element i and the plurality N of second processing elements

c_jik is the kth pole coefficient of the filter between first processing element i and second processing element j

d_ijk is the kth zero coefficient of the filter between first processing element i and second processing element j

T and U are respectively the non-recursive and recursive orders of the filter through which back-propagation occurs

Δ

_j (n+k) is the error computed at the output of the jth second processing element k time steps in the future

γ

_ij (n-k) is the output from k time steps in the past of the filter operating on the inverted sequence of network errors.