Chaotic maps and pattern recognition - the XOR problem

Chaotic maps and pattern recognition – the XOR problem Alan Rogers a,* , John G. Keating b , Robert Shorten a , Daniel M. Heffernan c,d a Department of Electronic Engineering, National University of Ireland, Maynooth, Co. Kildare, Ireland b Department of Computer Science, National University of Ireland, Maynooth, Co. Kildare, Ireland c Department of Mathematical Physics, National University of Ireland, Maynooth, Co. Kildare, Ireland d School of Theoretical Physics, Dublin Institute for Advanced Studies, Dublin 4, Ireland Accepted 31 July 2001 Abstract In this report, we describe a novel application of the Baker’s map. We demonstrate that the chaotic properties of this map can be used to implement basic operations in Boolean logic. This observation leads naturally to the possibility of new computational models and implementations for conventional computational systems. Here we show that by considering the variation of the fractal dimension of its attractor, and using varying parameter values as inputs, the generalised Baker’s map can be used as a natural exclusive OR (XOR) gate. Further, this map can also be used to create other logical functions such as the AND gate. The efficacy of our results are demonstrated by means of a concrete application; namely by designing, to the best of our knowledge, for the first time, a half-adder that is constructed entirely by utilising chaotic dynamics. Ó2002 Elsevier Science Ltd. All rights reserved. 1. Introduction Nonlinear dynamics, as a subject, has reached a considerable degree of maturity in recent years. However, despite rapid theoretical advances in the subject, the general area of nonlinear dynamics has also been characterised by a lack of engineering applications (with the exception of nonlinear control [1]) that exploit the fundamental theory and properties of nonlinear systems. This observation is somewhat surprising since many engineering systems are designed to exhibit behaviour commonly found in nonlinear systems. Examples of this abound in the aerospace industry. Fighter aircraft, for instance, are designed to have unstable dynamics to aid manoeuvrability under extreme flight conditions. Such aircrafts are artificially stabilised under normal flight conditions. The properties of local instability of trajectories (rapid manoeuvrability) and global stability of orbits (safety) are often found in nonlinear and chaotic systems. One property in particular is extremely attractive from an engineering perspective: exponential sensitivity to initial conditions, which allows chaotic systems to be hypersensitive to changes in system parameters; and yet underlying this sensitivity, chaotic systems have global properties, such as fractal dimension of state-space attractor, which can be extracted and used as output variables. This observation suggests that chaotic dynamics can be used as the design basis for rapid system identification, and in the design of high performance control systems. Here, we begin the process of examining the suitability of chaotic maps for such engineering applications. In this paper, we will show how the generalised Baker’s map can be used to solve the exclusive OR (XOR) problem. This is a fundamental problem of pattern recognition, and involves telling at a single glance whether a point belongs to one of the two classes: class A or NOT class A (class B), where class A consists of two diagonally opposite corners of a unit square, and class B consists of the other two corners. The inability of a single-layer perception to solve this problem Chaos, Solitons and Fractals 14 (2002) 57–70 www.elsevier.com/locate/chaos * Corresponding author. Tel.: 353-1-7086067; fax: 353-1-7083967. E-mail address: [email protected] (A. Rogers). 0960-0779/02/$ - see front matter Ó2002 Elsevier Science Ltd. All rights reserved. PII: S0960-0779(01)00181-3 is considered to be a severe drawback for ANNs as a mechanism for nonlinear problem-solving. We will consider the XOR problem in more depth later. The generalised Baker’s map is a two-dimensional, three-parameter, nonlinear mapping, which is chaotic for virtually all parameter values. We use it here because it is one of the best-understood chaotic maps, and is particularly suited to rigorous analysis (see [2]). It also has the useful property that its Lyapunov dimension is monotonically increasing for a wide range of parameter values, and we shall utilise this when we develop the XOR gate. To the best of our knowledge, neither Baker’s map, nor any other chaotic map, has been previously used to solve the XOR problem in this way. The rest of the paper is organised as follows. In Section 2 we will describe the XOR problem, and the way in which artificial neural networks (ANNs) can, and more importantly, cannot, solve this problem. We shall describe the Baker’s map in Section 3. In Section 4 we show how the Baker’s map can act as a natural XOR system, and we present some of the properties, advantages, and drawbacks, of the new system. In Section 5 we show how a half-adder can be built using two Baker’s maps. In Appendix A, we briefly describe ANNs and their use as pattern classifiers. 2. Pattern recognition and the XOR problem The pattern recognition problem consists of designing algorithms that automatically classify feature vectors associated with specific patterns as belonging to one of a finite number of classes. A benchmark problem in the design of pattern recognition systems is the Boolean exclusive OR (XOR) problem. The standard XOR problem is depicted in Fig. 1. Here the diagonally opposite corner-pairs of the unit square form two classes, A and B (or NOT A). From the figure, it is clear that it is not possible to draw a single straight line which will separate the two classes. This observation is crucial in explaining the inability of a single-layer perceptron to solve this problem (an overview of the perceptron is given in Appendix A). This problem can be solved using multi-layer perceptrons (MLPs), or by using more elaborate single-layer ANNs such as the radial basis function neural network [3]. However, the inability of simple ANNs, such as the Adeline [4], to solve this problem, effectively ended research interest in the area of ANNs for over 20 years, which highlights the importance of the XOR problem in the design of pattern recognition systems. In this paper, we show that the generalised Baker’s map can be trained to solve this problem in a straightforward manner. 3. Chaos and the Baker’s map 3.1. The generalised Baker’s map In their classic study of fractal dimensions, Farmer et al. [4] introduced the generalised Baker’s map in order to obtain rigorous results on the dimension of strange attractors. It is a transformation of the unit square ½0;1½0;1, and has three parameters, R1,R2and S: xnþ1¼R1xnif yn<S; 1=2þR2xnif ynPS;  ynþ1¼ yn=Sif yn<S; ynS 1Sif ynPS: 8 < : ð1Þ Fig. 1. The exclusive OR (XOR) problem: points (0,0) and (1,1) are members of class A; points (0,1) and (1,0) are members of class B. 58 A. Rogers et al. / Chaos, Solitons and Fractals 14 (2002) 57–70 We illustrate the Baker’s map transformation in Fig. 2. As can be seen from Eq. (1), the mapping depends on whether the point in question is above or below a horizontal line y¼S. Since the Baker’s Map is a mapping of the unit square, we restrict Sto the range (0,1) and R1and R2to the range (0, 0.5]. In Fig. 2, we show the action of the map on the entire unit square. Iterating the map gives two vertical strips, whose widths depend on R1and R2. Iterating the map again gives four strips, then eight strips, and so on. The attractor is the union of a line segment (vertical direction) and a Cantor set (horizontal direction). 3.2. Lyapunov numbers and Lyapunov dimension of the Baker’s map It can be seen in Fig. 2 that the action of the map leads to ‘stretching’ in the y-direction and ‘compressing’ in the xdirection. It is possible to put these actions into a more mathematical framework by using the notion of Lyapunov numbers. These numbers characterise the stability of the map, and are defined as follows: Let Jn¼½JðxnÞJðxn1Þ... Jðx1Þ, where JðxÞis the Jacobian of the map, JðxÞ¼ðoF=oxÞ, for some map F. Let j1ðnÞPj2ðnÞP PjpðnÞbe the magnitudes of the peigenvalues of Jn. Then the Lyapunov numbers are given by ki¼lim n!1½jiðnÞ1=n;i¼1;2;...;p:ð2Þ Since the Baker’s map is two-dimensional, it will have two Lyapunov numbers, characterising the average stretching/ compression factors in the xand y-directions (see Fig. 3). Note that the Lyapunov exponents are simply the logarithms of the Lyapunov numbers. It is customary to order the Lyapunov numbers, so that k1>k2>>kn. The Lyapunov dimension was introduced by Kaplan and Yorke [5] in the so-called Kaplan–Yorke conjecture: that the Lyapunov dimension DLis the same as the information dimension for ‘‘typical’’ attractors. For the Baker’s map, DL¼1þlog k1 log 1=k2 :ð3Þ Fig. 2. Action of the Baker’s map on unit square: transforms square into two strips, then four strips, eight strips, and so on. Fig. 3. Lyapunov Numbers characterise the average stretching factors of some small circle of radius d. In this case, k1>1 and k2<1. A. Rogers et al. / Chaos, Solitons and Fractals 14 (2002) 57–70 59 The Jacobian of Eq. (1) can be written in the following form: J¼L2ðyÞ0 0L1ðyÞ  ;where L1ðyÞ¼ 1=Swhen y<S; 1=ð1SÞwhen y>S;  L2ðyÞ¼ R1when y<S; R2when y>S:  So from Eq. (2) we get k1¼lim n!1 L1ðynÞ...L1ðy1Þ½ 1=n; k2¼lim n!1 L2ðynÞ...L2ðy1Þ½ 1=n: By taking logs, and with some manipulation, noticing that the orbits are ergodic in the y-direction, we find that the Lyapunov exponents are: log ky¼Slog 1 Sþð1SÞlog 1 1S;ð4aÞ log kx¼Slog R1þð1SÞlog R2:ð4bÞ In our implementation of the XOR gate, we only require two input parameters, so we shall let R2¼R1, in which case we find that log kx¼log R1:ð5Þ 4. Using the Baker’s Map to solve the XOR problem 4.1. Background If we plot the fractal dimension of Baker’s map for varying values of Rand S, it becomes obvious how we can use the map to solve the XOR problem. Firstly, we show how the Lyapunov exponents (Eqs. (4a) and (5)) vary with Rand S(see Fig. 4). Clearly, since the map is contractive in x-direction, the Lyapunov exponent in that direction is always negative. Conversely, the map is expansive in the y-direction, and therefore that Lyapunov exponent is always positive. From Eq. (3), the Lyapunov dimension is given by DL¼1log ky log kx :ð6Þ In Fig. 5, we plot DLagainst R, with Sas a parameter. Notice that the fractal dimension varies between 1 and 2, as we would expect. Due to the symmetry of Fig. 4(b), the fractal dimension is symmetrical about S¼0:5. We have chosen slightly asymmetrical values of Sto illustrate this. We can choose values of Rand S, so that a pair (low R, high S) and another pair (high R, low S) give the same fractal dimension, say DA. This corresponds to a diagonally opposite corner pair in the XOR problem. We can say, therefore, that if the fractal dimension DL¼DA, then the inputs are in class A, and if DL6¼ DA, then the inputs belong to class B. Note that we always limit Sto the range [0, 0.5], to ensure a unique fractal dimension for any given (R;S) pair. For example, in Fig. 6, we could say that the following pairs of parameters form classes. Obviously, the points in Table 1 do not lie on a perfect square, but that is unimportant. The key idea is that two pairs of diagonally opposing points are mapped to the same class. It is also clear that we are quite restricted in the possible pairs of points which we can map to the same fractal dimension. However, if we choose any four (R;S) pairs of points corresponding roughly to (low, low), (low, high), (high, low) and (high, high), then by drawing a straight line through the (low, high), (high, low) points and intersecting the y-axis, we can effectively solve the XOR problem for much larger set of inputs. We call the intersection of this line with the y-axis, DM, the (modified) Lyapunov dimension. This is illustrated in Fig. 6. Procedure for calculation of DM: (i) Given four points in the R–Splane, select the two points belonging to the same class: ðRa;SbÞ,ðRb;SaÞin Fig. 6. (ii) Calculate the Lyapunov dimensions corresponding to the two points, called D1,D2. (iii) Calculate the slope, m¼ðD1D2Þ=ðRaRbÞ. (iv) The dimension DM¼D1þmRa¼D2þmRb. 60 A. Rogers et al. / Chaos, Solitons and Fractals 14 (2002) 57–70 As DMis constantly calculated, we can tell whether the inputs are in class A, or not. An algorithm of this form is referred to as a training algorithm in the ANN and statistical pattern recognition literature [8]. The availability of such an algorithm, and its complexity, ultimately determines the applicability of a particular paradigm for a given problem. In our case, given a set of class labels, and a set of vectors, the training parts of the pattern recognition problem is trivial, involving only the simple calculation of a slope. For an ANN, solving this problem requires repeated calculation of the slope for at least two hyperplanes, and so is more computationally intensive. 4.2. Computer simulation The system is easily implemented with a few lines of code. Essentially, we need to simulate Baker’s map, given its input parameters, and then, using its state variables xand y, compute the Lyapunov dimension DLof the attractor (see Fig. 7). Fig. 4. Variation of Lyapunov exponent in the (a) x-direction, (b) y-direction. A. Rogers et al. / Chaos, Solitons and Fractals 14 (2002) 57–70 61 Obviously, the speed of the system depends on the computation of the Lyapunov dimension. The traditional way to do this is quite slow [6], and assumes that no detailed information is available about the system, that is to say, only a time-series x0;x1;x2;...;is available from the system. Given this time series, some value from the sequence is selected, Fig. 6. A more general way of solving the XOR problem: draw a straight line through the two points belonging to class A (say), and find where the line intersects the y-axis. Fig. 5. Variation of fractal dimension with varying parameter values. 62 A. Rogers et al. / Chaos, Solitons and Fractals 14 (2002) 57–70 say xi, and then one searches the sequence for another value xjthat is close to xi. The sequence of differences is assumed to diverge exponentially, on the average: d0¼jxjxij d1¼jxjþ1xiþ1j . . . dn¼jxjþnxiþnj ð7Þ We assume that dn¼d0ekn; which, after taking logarithms, gives k¼1 nlog dn d0 :ð8Þ Since we would like our system to be as fast as possible, this method is computationally expensive, as it involves continually searching through some large array of numbers, and then performing additional calculations given in Eqs. (7) and (8). As we have Baker’s map data readily available, and since we have its input parameters already, we have found a quicker way to compute the Lyapunov numbers. They are calculated as follows: we iterate the Baker’s map fðx;yÞas normal (call it B1), but we also iterate another Baker’s map ðB2Þin parallel with it. For each pair ðxn;ynÞ generated by B1, we use some nearby pair of numbers ðxnþd;ynþeÞas initial conditions for B2. We then iterate B2 once (we have found that iterating more than once does not improve accuracy, but merely slows things down). Now, we compute the Lyapunov numbers kx¼log jfðxn;ynÞfðxnþd;ynþdÞjXcomp: d; ky¼log jfðxn;ynÞfðxnþe;ynþeÞjYcomp: e: ð9Þ The numbers thereby computed tend to be noisy, but when averaged, they give the expected theoretical values. Note also that since the map is always contracting in the x-direction, choosing a very small value for dgives entirely inaccurate results, hence we tend to use d1. To illustrate the action of the system, we choose four distinct points, more or less arbitrarily (see Fig. 8). We compute the slope of the line between points 1 and 2, belonging to class A, to be m¼1:60667, and the (modified) Lyapunov dimension DM¼1:752 (see Table 2). In Fig. 9, we plot the output from Baker’s map system. Here, we have averaged every 200 points, to smooth the output. Clearly, there is a tradeoff between speed of pattern classification, and accuracy. If we average more points, then Fig. 7. The chaotic XOR system: the outputs from the map are the state variables xand y, and these are used to compute the Lyapunov dimension. Table 1 Parameter values and their corresponding fractal dimension, and class, as in Fig. 5 Rvalue Svalue Fractal dimension Class 0.1 0.5 1.3 A 0.36 0.1 1.3 A 0.1 0.1 1.14 B (NOT A) 0.36 0.5 1.68 B (NOT A) A. Rogers et al. / Chaos, Solitons and Fractals 14 (2002) 57–70 63 Fig. 8. The four points selected to illustrate the chaotic XOR system. Fig. 9. Output from the chaotic XOR system, with inputs as in Table 2. Contiguous sets of 200 points are averaged. Class A corresponds to a modified Lyapunov dimension DM1:75. Note that we cycle through points (1), (4), (2), (3) and (1), respectively. Table 2 Parameter values and their corresponding classes, as shown in Fig. 6 Point no. Rvalue Svalue Class 1 0.2 0.5 A 2 0.3 0.1 A 3 0.15 0.2 B 4 0.35 0.4 B 64 A. Rogers et al. / Chaos, Solitons and Fractals 14 (2002) 57–70 we get a smoother output, but this introduces a delay into the recognition process (see Figs. 10 and 11). Note also that the relative smoothness also depends on how large the value of Sis, with S¼0:5 giving a perfectly smooth output. This is because the expansion rates in the y-direction are the same only when S¼0:5 (see Fig. 2). It is clear from Fig. 11 that by merely observing if the output dimension lies in some suitable range about 1.75, we can tell if the input is in class A, or class B. Fig. 10. Output from the system with a 5-point averaging window. Since the output dimension switches between two values only, the 5-point averaging leads to six possible values for the output. Fig. 11. Output from the system with 1000-point averaging windows. A. Rogers et al. / Chaos, Solitons and Fractals 14 (2002) 57–70 65