IEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.4 APRIL 2004

774

PAPER

Special Section on Selected Papers from the 16th Workshop on Circuits and Systems in Karuizawa

Markov Chain Modeling of Intermittency Chaos and Its
Application to Hopfield NN
Yoko UWATE†a) , Student Member, Yoshifumi NISHIO†b) , Member, and Akio USHIDA††c) , Fellow

SUMMARY
In this study, a modeling method of the intermittencychaos using the Markov chain is proposed. The performances of the intermittency chaos and the Markov chain model are investigated when they
are injected to the Hopfield Neural Network for a quadratic assignment
problem or an associative memory. Computer simulated results show thatthe proposed modeling is good enough to gain similar performance of theintermittency chaos.
key words: intermittency chaos, burst noise, Markov chain, neural network, QAP, associative memory

1.

Introduction

Intermittency chaos [1] is deeply related to the edge of chaos[2] and many researchers suggest that such a behavior between order and chaos gains better performance for various
kinds of information processing than fully developed chaos.
One good example of this is an application of chaos to the
Hopfield Neural Networks (Hopfield NN) [3] solving combinatorial optimization problems to avoid trappings of thesolutions into a local minimum. Hayakawa et al. pointed
out the chaos near the three-periodic window of the logistic
map gains the best performance for solving traveling salesman problems (TSP) [4]. However, the reason why the intermittency chaos exhibits such a good performance has notbeen clarified. Therefore, it is very important to make simpler models of the good characteristics of the intermittencychaos and to investigate their detailed properties.
In this study, we propose a modeling method of the intermittency chaos obtained from the logistic map by using
the Markov chain. Various people have already proposed
the Markov chain modelings of chaotic systems [5]–[7].
The modelings have been successfully applied to the chaosbased spread spectrum communication systems for the purposes of the noise cleaning of chaotic sequences [5] and theanalytical estimation of the performance [6]. Further, themodeling has been extended to generate more complex nonlinear phenomena such as self-similarity [7]. These modManuscript received June 30, 2003.
Manuscript revised September 16, 2003.
Final manuscript received November 10, 2003.
†
The authors are with the Department of Electrical and Electronic Engineering, Tokushima University, Tokushima-shi, 7708506 Japan.
††
The author is with the Department of Mechanical-Electronic
Engineering, Tokushima Bunri University, Sanuki-shi, 769-2193
Japan.
a) E-mail: uwate@ee.tokushima-u.ac.jpb) E-mail: nishio@ee.tokushima-u.ac.jpc) E-mail: ushida@fe.bunri-u.ac.jp

elings are eﬀective in the sense that the models could generate almost all the phenomena observed from the original
chaotic system. However, it is not appropriate to reveal thereasons of the good performance of the intermittency chaos.
Therefore, in this study, we pay our attentions only on the
distribution of the lengths of the laminar parts and the burst
parts, which seems to be the most distinguished feature of
the intermittency chaos. The proposed modeling using theMarkov chain is completely diﬀerent from those in the references on the point that each state in the Markov chain is
not a quantized value (or an interval) of a variable but a behavior of successive orbits. As a result, the model becomesvery simple and enhances the feature of the intermittencychaos.
In order to confirm that the proposed model keeps thegood property of the intermittency chaos, we investigate theperformances of the intermittency chaos and the Markov
chain model when they are injected to the Hopfield NN
for a quadratic assignment problem (QAP) or an associative
memory, which are known as representative applications of
the Hopfield NN. Computer simulated results show that the
proposed modeling is good enough to gain similar performance of the intermittency chaos.
2.

Intermittency Chaos

We consider the logistic map to generate chaotic time series;ẑ(t + 1) = αẑ(t)(1 − ẑ(t)).

(1)

Varying the control parameter α, Eq. (1) behaves chaotically
via a period-doubling cascade. Further, it is well known that

Fig. 1

Intermittency chaos for α=3.827940.

UWATE et al.: MARKOV CHAIN MODELING OF INTERMITTENCY CHAOS

775

the map produces intermittent bursts just before periodicwindows appear. Figure 1 shows an example of the intermittency chaos near the three-periodic window. As we cansee from the figure, the chaotic time series could be divided
into two phases; laminar part of periodic behavior with period 3 and burst part of spread points over the invariant interval. As increasing α, the ratio of the laminar parts becomeslarger and finally the three-periodic window appears.
3.

Markov Chain ModelingIn this section, we model the intermittency chaos by using
the Markov chain.
At first, we distinguish the laminar part and the burst
part of the intermittency chaos. Because we treat only theintermittency chaos near the three-periodic window, we regard three successive sequences starting from a point whose
value is 0.9444 or more as one-period of the laminar part.
Other points are regarded as the burst part.
In order to make the Markov chain model precisely, we
counted the period of the laminar parts. The frequency ofeach period of the laminar part during 100000 iterations of
the logistic map is shown in Fig. 2. We can see that the curve
does not obey any simple scaling rules. Namely, the periodof the laminar part is bounded and the maximum value ofthe period takes a peak. The intermittency chaos occurs justbefore a tangent bifurcation. The movement of the laminarpart of the intermittency chaos is shown in Fig. 4 of [1]. If
the control parameter of a given map is fixed, the width ofthe channel between the map and the bisector is decided.
Since the width is finite, the number of the iteration to passthrough the channel is bounded. We consider that this is themost distinguished feature of the intermittency chaos.
In order to model the above-mentioned feature of theintermittency chaos, we propose the Markov chain as shownin Fig. 3. In this Markov chain, the state S 0 corresponds tothe burst part and the states S 1 , S 2 , · · ·, S L correspond to thelaminar parts where the subscript k of S k indicates the periodof the continuing laminar part and L is the maximum periodof the laminar part. In the state S 0 , three points whose values are uniformly spread over the interval [0.160, 0.956] are

Fig. 2 Distribution of period of laminar part (Intermittency chaos for
α=3.827940).

generated. In the state S k (k  0), three successive points{0.956, 0.160, 0.514} corresponding to the three-periodic
points of the logistic map are generated. The conditional
probabilities P(S k |S l ) means the transition probability fromthe state S l to the state S k , andP(S k+1 |S k ) + P(S 0 |S k ) = 1 (0 ≤ k < L)(2)must be satisfied.
If we denote the stationary probability for the state S k
as Q(S k ), the transition probabilities satisfy the following
equations.
Q(S 0 ) =L−1
P(S 0 |S l )Q(S l ) + Q(S L )

(3)

l=0

Q(S k ) = P(S k |S k−1 )Q(S k−1 )LQ(S k ) = 1.

(0 < k ≤ L)

(4)
(5)

k=0

We derive the stationary probabilities of the Markov
chain from the simulated data of the intermittency chaos bycounting the number of the corresponding state. Further,
the transition probabilities are calculated from the stationary
probabilities by using Eqs. (3) and (4).
Figure 4 shows an example of time series obtained
from the Markov chain model for L = 15. The transitions
between the states are decided by using a random function
according to the obtained transition probablities and the values in the burst parts are also given by using a random function. In order to check the statistical property of the obtained

Fig. 3Fig. 4

Markov chain.

Time series of the Markov chain model for L=15.

IEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.4 APRIL 2004

776

4.1 Solving QAP with Hopfield NN
A QAP is expressed as follow: given two matrices, distancematrix C and flow matrix D, and find the permutation p
which corresponds to the minimum value of the objectivefunction f (p) in Eq. (6).
f (p) =NQ
NQ 
Ci j D p(i)p( j)(6)i=1 j=1

Fig. 5 Distribution of period of laminar part (Markov chain model for
L = 15).
Table 1model.

Statistical properties of intermittency chaos and Markov chain

L
7
9
11
13
15
17
19
21
23
25
30
40
50
70
100

Ratio of laminar part

Average period of laminar partChaos
0.42150.47140.50490.53480.55580.57980.59050.62510.64220.64450.68780.72610.76550.82400.8563Chaos
3.14953.8271
4.34864.97325.43895.91856.56887.08887.44307.48539.2968
11.5463
13.6257
19.7186
24.8647

Markov
0.41560.45800.50490.52890.55240.57000.60830.63130.64240.64270.68040.71960.75800.81670.8532

Markov
3.07893.71394.27294.92165.29845.72666.53587.18357.34447.47648.870411.1663
12.8656
19.2385
24.4863

time series, we counted the period of the laminar part. The
result is shown in Fig. 5. We can say that the result is very
close to that in Fig. 2.
Further, we produce the Markov chain models for various sizes of the maximum period L of the laminar part. The
comparison of the statistical properties of the original intermittency chaos and the corresponding Markov chain model
is summarized in Table 1. We can confirm that the propertyof the Markov chain models is similar to that of the original
intermittency chaos.
4.

Application to Hopfield NN for QAP

In this section, as the first example of applications of theMarkov chain model of the intermittency chaos, we investigate the performance of the Hopfield NN for a QAP when
the intermittency chaos and the Markov chain model are injected to the network in order to avoid the local minimum
trapping problem.

where Ci j and Di j are the (i, j)-th elements of C and D, respectively, p(i) is the i-th element of vector p, and NQ is thesize of the problem. There are many real applications which
are formulated by Eq. (6).
Because QAP is very diﬃcult, it is almost impossible tosolve the optimum solutions in larger problems. The largest
problem which is solved by deterministic methods may be
only 20 in recent study. Further, computation time is very
long to obtain the exact optimum solutions. Therefore, it isusual to develop heuristic methods which search nearly optimal solutions in reasonable time. For solving NQ -element
QAP by the Hopfield NN, NQ × NQ neurons are required
and the following energy function is defined to fire (i, j)-thneuron at the optimal position:
EQ = −

NQ NQ
NQ

1  
wim; jn xim x jn +
θim xim .
2 i,m=1 j,n=1
i,m=1

(7)

The neurons are coupled each other with the synaptic connection weight. Suppose that the weight between (i, m)-th
neuron and ( j, n)-th neuron and the threshold of the (i, m)-th
neuron are described by:
Ci j Dmn
wim; jn = −2 A(1 − δmn )δi j + Bδmn (1 − δi j ) +qθim = −(A + B)
(8)
where A and B are positive constants, and δi j is Kronecker’s
delta. The states of the NQ × NQ neurons are asynchronously
updated due to the following diﬀerence equation:
 NQ

 


wim; jn x jn (t) + θim + βQ zim (t) (9)xim (t + 1) = g j,n=1

where g(·) is a sigmoidal function
1(10)g(x) =x ,1 + exp −εzim (t) is the intermittency chaos or the Markov chain model,
and βQ limits the amplitude of the injected time series. Notethat we normalize ẑim by Eq. (11) before the injection.
ẑim (t) − z̄zim (t + 1) =(11)
σzwhere z̄ is the average of ẑ(t), and σz is the standard deviation of ẑ(t).
Further, we use the method suggested by Sato et al. (1.1
in [8]) to decide firing of neurons.

UWATE et al.: MARKOV CHAIN MODELING OF INTERMITTENCY CHAOS

777

4.2 Simulated Results for QAP
The problem used here is chosen from the site QAPLIB
which collects the bench mark problems [9]. We carried out
computer simulations for the problems with various sizes.
The results for “Nug12” are shown in this section. The
global minimum of this problem is known as 578. The parameters of the Hopfield NN are fixed as A = 1.0, B = 1.0,
q = 100 and ε = 0.02 and the amplitude of the injected
time series is fixed as βQ = 0.6. The number of updating the
network Nit is 10000.
In order to evaluate the performance precisely, we neglect the once-appeared-solutions and use the two functions
Depth 1 and Depth 2 proposed in our previous study [10].
Both functions have been introduced to evaluate finding a lotof nearly optimal solutions. The diﬀerence between them isthe treatment of bad solutions. The function Depth 1 evaluates all obtained solutions as good factor, even if the energies of the solutions are much worse than the optimal energy. The concept of this function is based on the idea thatthe network which finds a lot of bad solutions is better than
the network does not find any solutions at all. On the other
hand, Depth 2 evaluates bad solutions as bad factor. In order to eliminate the eﬀect of bad solutions, we not only set
up a threshold but give a penalty according to the energy.
The concept of this function is based on the idea that finding
a lot of bad solutions hinders finding good solutions.
4.2.1

Fig. 6

Result of Depth 1 (D∞ = 1000).

Fig. 7

Result of Depth 2 (Dth = 812).

Depth 1

The first function Depth 1 is defined as
Depth 1 =n

{ f (pk ) − D∞ }2

(12)

k=0

The Markov chain model gains similar performance to theintermittency chaos. This result shows that the Markov
chain model keeps the good characteristic of the intermittency chaos to find a lot of nearly optimal solutions of QAP.
5.

where D∞ is a constant which is large enough to include
the energies of all solutions, n is the number of the accepted
solutions and the energy f (pk ) is calculated by Eq. (6) using
the permutation pk corresponding to the k-th solution.
The calculated result of Depth 1 is shown in Fig. 6.
The horizontal axis is the maximum period of the laminarpart L. We confirm that both the intermittency chaos andthe Markov chain model exhibit similar tendency such that
Depth 1 decreases as the maximum period L of the laminarpart increases. However, the Depth 1 for the Markov chain
model is not as large as those for the intermittency chaos.

Application to Hopfield NN for Associative Memory

In this section, as the second example, we investigate theconvergence performance of the Hopfield NN working as
an associative memory when the intermittency chaos andthe Markov chain model are injected to the network as anoise. Similarly to the case of QAP, we have shown that the
injection of the intermittency chaos to the Hopfield NN for
an associative memory could avoid the local minimum trapping problem and could improve the rate and the speed of
the convergence to a stored pattern [11].
5.1 Hopfield NN Working as Associative Memory

4.2.2

Depth 2

The function Depth 2 is defined as follows:
Depth 2 =n

{ f (pk ) − Dth }2 −

k∈kg

where

kg = {k | f (pk ) ≤ Dth }.

n{ f (pk ) − Dth }2

kkg

(13)

The calculated result of Depth 2 is shown in Fig. 7.

Associative memory is a system which returns a stored pattern that is similar to a presented pattern. Noisy patterns
can be corrected or distorted patterns can be recognized bya well-constructed associative memory.
The Hopfield NN is used as an associative memory by
exploiting the property that the network has multiple stablestates. Namely, if the parameters of the network can be decided in such a way that the patterns to be stored become

IEICE TRANS. FUNDAMENTALS, VOL.E87–A, NO.4 APRIL 2004

778

stable states of the network, the network produces a stored
pattern that is similar to an input pattern.
The energy function of the Hopfield NN with NA neurons and M stored binary patterns is defined by the following
equation.
EA = −

NA
NA 
NA

1
wi j x i x j −θi x i2 i=1 j=1
i=1

(14)

where wi j is the weight between i-th neuron and j-th neuron,and θi is the threshold of the i-th neuron. They are given as
follows.
 
M




(2xmi − 1)(2xm j − 1) (i  j)(15)
wi j = 
m=1





0
(i = j)θi = 0.
(16)
The states of the neurons are asynchronously updated
due to the following diﬀerence equation:

N
A



xi (t + 1) = g  wi j x j (t) + θi + βA zi 
(17)
j=1

where g(·) is a sigmoidal function, zi is the intermittencychaos or the Markov chain model, and βA limits the amplitude of the injected time series.
In this application, firing of neurons is decided by theoutput value of more than 0.5.
5.2 Simulated Results for Associative Memory
In the computer simulations, we consider the Hopfield NN
with 400 neurons. In order to investigate the performance ofthe network under diﬃcult conditions, we prepare an input
binary pattern at random and produce several binary patterns
to be stored whose distances from the input pattern are theexactly same. The Hamming distance dH is used to evaluate
the convergence of the network. Namely, the convergencetime T conv is defined as the iteration number of the network
when the Hamming distance between the output of the network and one of the stored patterns becomes zero. Further,
we propose S conv to evaluate convergence speed more precisely. S conv is defined by Eq. (18).
min[ T conv , Nmax ]S conv = 1 −
Nmax

(18)

where Nmax is the given upper limit of the iteration numberof the simulation. Namely, if the network dose not converge
to any stored patterns during the given iteration, the value of
S conv is zero.
Computer simulations are carried out for various conditions. Typical results for two cases of 5 stored patterns and8 stored patterns are shown in Fig. 8. For this simulation, theintermittency chaos for α = 3.827940 and the corresponding
Markov chain model with L = 15 are injected. The amplitude of the injected time series is βA = 50.0, the parameter

Fig. 8Simulated results of S conv .

of the Hopfield NN is ε = 0.02, and the maximum iteration number of the network is fixed as Nmax = 10000. The
horizontal axis is the Hamming distance between the input
pattern and the stored patterns and the vertical axis is theaverage value of S conv in 100 trials.
The Markov chain model gains similar performance tothe intermittency chaos. This result shows that the Markov
chain model keeps the good property of the intermittencychaos, which can improve the rate and the speed of the convergence of the Hopfield NN as an associative memory.
6.

Conclusions

In this study, a modeling method of the intermittency chaosusing the Markov chain has been proposed. The performances of the intermittency chaos and the Markov chain
model were investigated when they were injected to the
Hopfield NN for a QAP or an associative memory. Computer simulated results showed that the proposed modelingwas good enough to gain similar performance of the intermittency chaos.
References[1] Y. Pomeau and P. Manneville, “Intermittent transition to turbulencein dissipative dynamical systems,” Commun. Math. Phys., vol.74,
pp.189–197, 1980.

UWATE et al.: MARKOV CHAIN MODELING OF INTERMITTENCY CHAOS

779[2] C.G. Langton, “Computation at the edge of chaos: Phase transitions
and emergent computation,” Physica D, vol.42, pp.12–37, 1990.
[3] J.J. Hopfield, “Neurons with graded response have collective computational properties like those of two-state neurons,” Proc. Natl.
Acad. Sci. USA, vol.81, pp.3088–3092, 1984.
[4] Y. Hayakawa and Y. Sawada, “Eﬀects of the chaotic noise on theperformance of a neural network model for optimization problems,”
Phys. Rev. E, Stat. Phys. Plasmas Fluids Relat. Interdiscip Top.
vol.51, no.4, pp.2693–2696, 1995.
[5] H. Dedieu and M.J. Ogorzalek, “Overview of nonlinear noise
reduction algorithms for systems with known dynamics,” Proc.
NOLTA’98, vol.3, pp.1297–1300, 1998.
[6] R. Rovatti, G. Mazzini, and G. Setti, “A tensor approach to higher
order expectations of quantized chaotic trajectories; part I and II,”IEEE Trans. Circuits Syst. I, Fundam. Theory Appl., vol.47, no.11,
pp.1571–1596, 2000.
[7] R. Rovatti and G. Mazzini, “Tensor function analysis of quantizedchaotic piecewise-aﬃne pseudo-Markov systems; I and II,” IEEE
Trans. Circuits Syst. I, Fundam. Theory Appl., vol.49, no.2, pp.137–
162, 2002.
[8] K. Sato, T. Ikeguchi, M. Hasegawa, and K. Aihara, “An optimization
method for quadratic assignment problems by chaotic dynamics andits characterization by Lyapunov dimensions,” IEICE Technical Report, NLP64-13, 2001.
[9] R.E. Berkard, S.E. Karisch, and F. Rendl, “QAPLIB—A
quadratic assignment problem library,” http://www.opt.math.tugraz.ac.at/qaplib[10] Y. Uwate, Y. Nishio, T. Ueta, T. Kawabe, and T. Ikeguchi, “Performance of chaos noise injected to Hopfield NN for quadratic assignment problems,” Proc. NOLTA’02, pp.267–270, Oct. 2002.
[11] Y. Uwate, Y. Nishio, and T. Ikeguchi, “Associative memory by Hopfield NN with chaos injection,” IEICE Technical Report, NLP200344, 2003.

Yoko Uwate
was born in Tokushima, Japan,
in 1980. She received the B.E. degree from
Tokushima University, Tokushima, Japan, in
2003. She is currently working towards M.E.
degree at the same university. Her research interests include complex phenomena in chaotic
circuits and neural networks. Ms. Uwate is a
student member of the IEEE.

Yoshifumi Nishio
received the B.E., M.E.
and Ph.D. degrees in Electrical Engineeringfrom Keio University, Yokohama, Japan, in
1988, 1990 and 1993, respectively. In 1993, hejoined the Department of Electrical and Electronic Engineering at Tokushima University,
Tokushima, Japan, where he is currently an Associate Professor. From May 2000 he spent a
year in the Laboratory of Nonlinear Systems(LANOS) at the Swiss Federal Institute of Technology Lausanne (EPFL) as a visiting professor.
His research interests include analysis and application of chaos in electrical circuits, analysis of synchronization in nonlinear circuits, developmentof analytical methods for nonlinear circuits and theory and application ofcellular neural networks. Dr. Nishio is a member of the IEEE.

Akio Ushidareceived the B.E. and M.E. degrees in Electrical Engineering from Tokushima
University in 1961 and 1966, respectively, and
the Ph.D. degree in Electrical Engineering form
University of Osaka Prefecture in 1974. He
was an Associate Professor from 1973 to 1980
at Tokushima University. From 1980 to 2003,
he was a Professor in the Department of Electrical and Electronic Engineering at Tokushima
University. Since 2003, he has been with the
Department of Mechanical-Electronic Engineering, Tokushima Bunri University. From 1974 to 1975 he spent one year as
visiting scholar at the Department of Electrical Engineering and Computer
Sciences at the University of California, Berkeley. His current researchinterests include numerical methods and computer-aided analysis of nonlinear systems. Dr. Ushida is a member of IEEE.