A General Updating Rule for Discrete Hopfield-Type Neural Network with Delay

1 Introduction

Recently the convergence of various connectionist models including discrete Hopfield neural network (DHNN) [Hopfield, 1982; Wilson and Pawley, 1988; Bruck, 1990], continuous Hopfield neural network (CHNN) [Hopfield, 1982] and network with delay [Clouse and Lee, 1997] has been studied extensively. Since Hopfield and Tank [Hopfield, 1982] first applied DHNN to the traveling salesman problem, DHNN (which has a very simple and efficient hardware implementation) has demonstrated the capability to solve a wide variety of combinatorial optimization problems. However, Hopfield and Tank's approach has been subjected to severe criticism on the quality of its solutions, especially for large-scale problems [Wilson and Pawley, 1988]. Other issues concerning DHNN such as computational complexity [Orponen, 1992], computational power, finite automata equivalency and dynamic system simulation by DHNN are beyond the scope of this paper.

1 Corresponding to: Shenshan Qiu, Department of Automatic

Control Engineering, South China University of Technology, Guangzhou, 510640 China;

It is well known that the DHNN without delay has an important property, i.e., it always converges to a stable state when operating in a serial mode and to a cycle of length at most 2 when operating in a parallel mode [Hopfield, 1982; Wilson and Pawley, 1988; Bruck, 1990; Xu et al., 1998]. The problem of convergence is considered one of the most important theoretical issues in the study of the neural networks. However, in most optimization problems, the corresponding matrix and updating rule mode do not satisfy convergence conditions. Therefore its application domain is rather limited. To correct the deficiencies of the Hopfield network, various attempts such as optimal parameter selection and infeasible solution elimination have been made. Among these attempts, some are to maintain the structure of the Hopfield network, while others are to modify the network structure. In [Qiu et al., 2000; Qiu et al., 1999a; Qiu et al., 1999b] a DHNN with delay is constructed and a serial (updating rule) mode similar to one in Hopfield network without delay is also presented. But the corresponding convergence conditions are strictly constrained. It is also shown that the energy function is dependent on the updating rule mode. It is well known that a detailed specification for the convergence of DHNN is very critical to most of the applications and it remains an open problem on how much could the convergence conditions be relaxed.

In fact, the convergence conditions, network architecture, network initial conditions as well as updating rule modes are intimately related. The aim of this paper is to extend the convergence conditions given in [Qiu et al., 2000] and to specify the updating rule mode which will make the energy function decrease monotonically with respect to the evolution time. The energy function is modified by means of a modified DHNN as well as its updating rule mode, so that the convergence of DHNN with delay is obtained.

This paper has the following organization. Section 1 is the introduction. Section 2 gives a brief review for DHNN with delay. Section 3 introduces some definitions and notations. Section 4 discusses the convergence of DHNN with delay and presents the main result. The last section concludes the paper.

2 Hopfield Networks with Delay

Discrete Hopfield neural network (DHNN) [Hopfield, 1982; Wilson and Pawley, 1988; Bruck, 1990; Xu et al., 1998] is described as follows. The state of the network at time t is the vector ( ) ( ) ( ) ( ) [ ]T n t x t x t x t X ,..., , 2 1 = . In general, the state of the network at time t+1 is a function of { } θ , W and the state of network at time t. This network is thus completely determined by the parameters { } θ , W , the initial state values ( ) 0 X , and the manner in which the nodes are updated (evolved). If at time step t, node i x is chosen for updating, then at the next time step 1 + t ,

If only one neuron is allowed to change state at each time step by performing the state evolving equation (1) while the states of the other nodes are unchanged, then the network is said to be operating in a serial mode. If all the nodes are chosen to be updated at each time step by performing the state evolving equation (1), then the network is said to be operating in a parallel mode.

A DHNN with delay is a computational model, similar to a multilayer perceptron in which all connections are feedforward. The difference between a DHNN with delay and a multilayer perceptron is as follows. The inputs to any node i x for DHNN with delay may consist of the outputs of earlier nodes not only during the current step t, but also during previous d time steps ( ) d t t t - - - ,..., 2 , 1 . Following [Bruck, 1990; Orponen, 1992], the state of a neuron is updated according to the following equation:

In order to simplify the analysis presented later in this paper, only the special case d=1, ( ) θ θ ≡ t will be discussed here. ( ) ⋅ i σ represents the content of the output function of the neuron and the updating rule mode. The quadruple ( ) σ θ, , , 1 0 w w N = is used to represent the model (2). For instance, if n n O w × = 1 , ( ) ( ) ⋅ = ⋅ sgn i σ , then the quadruple ( ) sgn , , , 1 0 θ w w N = represents the DHNN model.

3 Updating Rule of DHNN with Delay

Let { }n n B 1 , 1 - ≡ represent the set of all vectors = X ( , , 2 1 x x )T n x ..., where each component i x assumes the value +1 or -1.We propose a new updating rule for DHNN with delay in order to extend the convergence conditions and establish an algorithm that will enable the network to escape from the local maximum points. The following is the definition of a generalized updating rule.

Definition 1. Let ( ) σ θ , , , 1 0 w w N = represent a DHNN with delay, starting from any initial vector n B X X ∈ = ) 0 ( ) 1 ( . Given a sequence of neural index subsets } ,..., 2 , 1 { ) ( n k L ⊆ for 1 ≥ k , the neural network is updated in the following form: When 1 = k , ) 1 ( L is a neural index subset by means of random selection (in general } ,.., 2 , 1 { ) 1 ( n L ≡ ), ( ) 1 + k x i ( ) k x i = , if ) (k L i∉ and for ) (k L i∈ , 1 > k , the following defines updating rule σ :

The updating mode is called the general updating rule for the neural network with delay, GURD for short. A sequence of neural index subsets ⊆ ) (k L } ,..., 2 , 1 { n satisfying the above conditions is generalized in an evolution mode. It includes a serial mode for neural network with delay when the sequence of neural index subsets is chosen which satisfy 1 ) ( = k L [Xu et al., 1998; Sun, 1998]. The following gives an illustrated example.

Example 1.1

The updating results of example 1.1 are presented in Table 1. It is noted that, for each updating mode, the threshold of a neuron is different, depending on the given sequence of neural index subsets ) (k L which determines the sequence of updating mode. The threshold ) (k T i changes with the updating time k. However, for a Hopfield Neural network, its threshold is a constant. So the stable state of the network is constrained. In other words, when the weights and threshold parameters of a network are given, its fixed points or stable states have been fixed, and they can not change with different updating modes, such as serial mode or parallel mode. On the other hand, the stable state of GURD mode is dynamically distributed based on a given sequence of neural index subsets ) (k L . Of course, the global maximum point will not change with respect to different updating modes. Only the local maximum points will be affected by these updating modes. Thus this dynamically distributed mechanism and delay relation enable the network to escape from local maximum points and finally reach the global maximum point (similar to LME algorithm [Peng, et al., 1996], a strategy to identify which delay item can be regarded as a certain noise). This is what motivates the investigation on the updating mode and the delay neural network model.

Definition 2. The function ) , ( v u E defined below is called a bivariate energy function on n B for ( ) σ θ, , , 1 0 w w N = :

where ( ) t x u = , ( ) 1 - = t x v . In short, the bivariate energy function is written as ( ) ( ) ( ) ( ) 1 , - ≡ t x t x E t E .

4 Main Results

Based on the GURD mode, the neural network with delay has the following convergence properties.

Theorem 1. Let ( ) σ θ, , , 1 0 w w N= be a DHNN with delay, operating in GURD mode σ . Suppose 0 w is a symmetric matrix and 1 w is a diagonal dominant matrix, i.e., ∑≠ ≥ i j ji ii w w 1 1 . Then for any 1 ≥ k , ( ) 0 ≠ ∆ k x or ( ) 0 1 ≠ - ∆ k x , it is

guaranteed that ( )

For any } ,..., 2 , 1 { ) ( n k L ⊆ the equality holds if only and if = + ) 1 (k x = ) (k x ). 1 ( - k x

Proof: According to definition 2

where ( ) ( ) 1 , - = = k x v k x u , θ is a threshold vector ( , , 2 1 θ θ θ = )T n θ ..., . Then

For any 2 ≥ k , } ,..., 2 , 1 { ) ( n k L i ⊆ ∈ and GURD in the operating mode, let ( ) ( ) ( ) ( ) ( ) ( ) k E k E k E k x k x k x i i i - + ≡ ∆ - + ≡ ∆ 1 , 1 , we have

∆

(

E

)

k

≡

T

x

-

k

(

1

+

)

0

x

k

(

1

+

)

+

2

T

x

k

(

1

+

)

1

x

k

( )

-

2

T

x

k

(

( ) ( ) ( ) . ) ( 2 1 ) ( 2 1 0 θ k x k x w k x k x w k x T T T + - -

= = i j 1 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ∑ ∑ ∑ = = = ⎪⎭⎪⎬⎫ ⎪⎩⎪⎨⎧ - ∆ + ∆ + ∆ = n i n j n j ij j ij j i i w k x w k x k x H k x 1 1 1 1 0 1 2 1 2 ( ) ∑ ∑ - ∈ = ⎪⎭⎪⎬⎫ ⎪⎩⎪⎨⎧ - ∆ + ) 1 ( 1 1 ) ( 1 2 k L j n i ij i j w k x k x ( ) ( ) ( ) ( ) ( ) ( ) ( ) ∑ ∑ ∑ ∈ ∈ - ∈ ⎪⎭⎪⎬⎫ ⎪⎩⎪⎨⎧ - ∆ + ∆ + ∆ = ) ( ) ( ) 1 ( 1 0 1 2 1 2 k L i k L j k L j ij j ij j i i w k x w k x k x H k x ( ) ∑ ∑ - ∈ = ⎪⎭⎪⎬⎫ ⎪⎩⎪⎨⎧ - ∆ + ) 1 ( 1 1 ) ( 1 2 k L i n j ji j i w k x k x (case 1) If ( ) 0 > ∆ k x i , then ( ) 1 - = k x i and ( ) 1 1 = + k x i .

Thus we have

being a sufficient condition for ( ) 0 ) ( > ∆ i k E ; (case 2) If ( ) 0 < ∆ k x i , then ( ) 1 = k x i and ( ) 1 1 - = + k x i .

Thus we have

being a sufficient condition for ( ) 0 ) ( > ∆ i k E ; (case 3) as 1 w is a column diagonal dominant matrix, then

w

w

1

+

θ

)

Any nonzero update with ( ) 0 ≠ ∆ k x or ( ) 0 1 ≠ - ∆ k x in the GURD is of these three cases. So 0 ) ( ≥ ∆ k E .

Tables 1 and 2 present the updating results of example 1.1. Especially in Table 2, the experimental results support our main theorem. It shows that our method is more likely to converge to the maximum or the submaximum values than the Hopfield neural network method does (the Hopfield neural network could be applied to the energy function of the example 1.1, after modifying the diagonal elements of the weight matrix). The three stable points (coded SPs: 5,6,7) which are neither max nor submax value points, have the greatest energy function values.

The following example 1.2 is a revised version of example 1.1. After modifying the original threshold vector (by adding a certain noise or standard Gaussian noise) and the diagonal elements of the weight 0 w . The updating results of example 1.2 are given in Table 3. The experimental results of example 1.2 show a much better performance than example 1.1. There are only two stable points. SP 13 is the maximum value point and SP 15 is the submaximum value point.

Example 1.2

It is no surprise that the convergence performance of example 1.2 is better than that of example 1.1. This shows that by adjusting the original threshold values of the network parameters, one can change or decrease the local maximum value points. However, this improvement comes as a result of 20 times updating tests and 50 random selection of parameter threshold values. It remains an important open problem on how such threshold values can be adjusted to produce a better performance.

All the updating rules are summarized in Table 4. The following illustration is used to explain the entries in Table 4.

Let the initial value ) 0 ( ) 1 ( X X = be ( )T 1 , 1 , 1 , 1 - - - - 4 B ∈ . The evolving operational process can be interpreted as follows. First choose a sequence of neural index subsets } 1 { ) 1 ( = L ,

where ] [s denotes the largest integer which is smaller than s ; bivariant } , _ { 1 m EFvalue code st = represents the neuron state vector code(st_code) and the corresponding energy function value(EFvalue); and ⎯ ⎯ → ⎯ ) (i L means updating all elements of the neural index subsets in ) (i L .

Initial value } 647 . 111 , 0 { - = EFvalue ( ) ( ) ( )⎯ ⎯ ⎯ ⎯ ⎯ ⎯ → ⎯ 4 , 3 , 2 ), 1 ( L L L L EFvalue , 13 { } 717 . 243 = ⎯ ⎯→ ⎯ ) 4 ( L …. It converges to the stable state 13.

Theorem 2. Let ( ) σ θ, , , 1 0 w w N = be a DHNN with delay, operating in a GURD mode. Suppose 0 w is a symmetric matrix and 1 w is a diagonal dominant matrix, i.e., for all i , ∑≠ ≥ i j ji ii w w 1 1 . Then for any 1 ≥ k , we have

The inequality holds if only and if I∞ =1 ) ( k k L is a nonempty

set, and there is an index i I∞ = ∈ 1 ) ( k k L such that ∑≠ > i j ij ii w w 1 1 , where ( ) k x v k x u = + = ), 1 ( .

Proof: According to definition 2

where ( ) 1 ), ( - = = k x v k x u , and θ is a threshold vector ( )T n θ θ θ θ ,..., , 2 1 = . Let ( ) ( ) ( ) k x k x k x i i i - + ≡ ∆ 1 , ( ) ( ) ( ) k E k E k E - + ≡ ∆ 1 . Then

Without loss of generality, we assume that ≡ - ) 1 (k L } ,..., 2 , 1 { n , 0 ) 1 ( ≠ - ∆ k x i , ) 1 ( - ∈ K L i . Since 1 w is a column diagonal dominant matrix, it implies that 0 ≥ ∆E .

diagonal dominant matrix and there is an index i I∞ = ∈ 1 ) ( k k L

On other hand, if ( ) u u E E , ≡ ∆ 0 ) , ( ≤ - v u E , i.e.,

Since 1 w is a diagonal dominant matrix, hence = wii 1 ∑≠i j ji w 1 is satisfied for all { } n i ,..., 2 , 1 ∈ . It is a contradiction as

there is an index i such that ∑≠ > i j ji ii w w 1 1 . This completes the

proof of theorem 2.

From the general updating rule (5) in theorem 1, it is noted that the network trajectory evolves in such a way that the energy function is always nondecreasing; that is,

Using the inequality (6) in theorem 2

Hence

The network trajectory now has a new step, i.e., at the ( 1 + k )th step, instead of updating from the k th step with initial values ) 1 ( ), ( - k x k x , now updating from the k th step with initial values ) ( ), ( k x k x . The modification allows the energy function to accelerate the rate of convergence and simplify the GURD. In the following, we define a new GURD rule.

Definition 3. Let ( ) σ θ, , , 1 0 w w N = represent DHNN with delay, starting from any initial vector n B X X ∈ = ) 0 ( ) 1 ( , given a sequence of neural index subsets } ,..., 2 , 1 { ) ( n k L ⊆ for 1 ≥ k , the neural network is updated as follows:

1. When 1 = k , } ,..., 2 , 1 { ) 1 ( n L ⊆ is a neural index subset by means of random selection (in general } ,.., 2 , 1 { ) 1 ( n L ≡ ),
2. For } ,.., 2 , 1 { ) ( n k L ⊆ , if ) (k L i∉ , let ( ) 1 + k x i ( ) k x i = and for ) (k L i∈ . The updating rule σ is given by:

This updating mode is also called the simplified general updating rule for neural network with delay, SGURD for short.

It is noted that both w 0 being a symmetric matrix and w 1 being a diagonally dominant matrix are required for the SGURD. Comparing the two constrained conditions (6) and (8), one may easily conclude that the range region of x invariable condition (otherwise case in (8)) decreases. It means that the energy function can reach the local maximum value in a short updating time. In other words, we only need to execute the SGURD rule 2n+1 steps at most [Qiu et al., 1999a]. But for the Hopfield network, the updating rule may require up to n 2 steps in order to obtain a stable state when the energy function has reached to a local maximum [Bruck, 1990].

It is noted that theorem 2 generalizes the results in [Qiu et al., 2000; Qiu et al., 1999a; Qiu et al., 1999b] which extend the constrained conditions of the weight matrices w 0 , w 1 . The requirement that the diagonal elements in w 0 are nonnegative (serial mode) and w 0 is nonnegative definite (parallel mode) are not necessary for the GURD mode. It has been shown that the updating rule process of the network and the activation process of the neurons are characterized by a dynamical process. But the sigmoid function still remains as the most popular choice for the network's activation function, and the serial, parallel and partially parallel modes are considered as important updating rule modes. There are no other modes.

Corollary 2.1 After a finite number of updates, under the GURD mode, the neural network with delay will converge to a fixed point.

In fact the fixed point is a local minimum point of the energy function. On the other hand, the convergence property is indispensable for any practical application design of neural network with delay.

5 Conclusion

In this article we have demonstrated how a generalized updating rule can cause the energy function to increase monotonously for neural network with delay. The GURD mode can operate in any sequence of updating modes. We have shown that the neural network with delay converges when operating in the GURD mode. The algorithm presented in [Qiu et al., 2000; Qiu et al., 1999a; Qiu et al., 1999b], including the original MHNN algorithm and the partially parallel mode algorithm [Hopfield, 1982; Wilson and Pawley, 1988; Bruck, 1990; Xu et al., 1998;Sun, 1998; Lee, 1999], can be easily derived from our main result which is supported by the experimental results of examples 1.1 and 1.2.

Acknowledgements

The authors would like to thank reviewers for their comments and suggestions which helped in improving the manuscript. This research was partially supported by the national nature sciences foundation, China (Grant:69934030) and nature sciences foundation of South China of University Technology.