A novel pattern classification scheme using the Baker's map

Neurocomputing 55 (2003) 779–786 www.elsevier.com/locate/neucom Letters A novel pattern classi!cation scheme using the Baker’s map Alan Rogersa;∗, John Keatingb, Robert Shortenc aDepartment of Electronic Engineering, NUI Maynooth, Maynooth, Co. Kildare, Ireland bDepartment of Computer Science, NUI Maynooth, Maynooth, Co. Kildare, Ireland cHamilton Institute, NUI Maynooth, Maynooth, Co. Kildare, Ireland Abstract We demonstrate a novel application of nonlinear systems in the design of pattern classi!cation systems. We show that pattern classi!cation systems can be designed based upon training algorithms designed to control the qualitative behaviour of a nonlinear system. Our paradigm is illustrated by means of a simple chaotic system—the Baker’s map. Algorithms for training the system are presented and examples are given to illustrate the operation and learning of the system for pattern classi!cation tasks. c 2003 Elsevier B.V. All rights reserved. Keywords: Pattern classi!cation; Chaos Baker’s map; Lyapunov dimension 1. Introduction Conventional pattern classi!cation systems are usually constructed by manipulating the parameters of some nonlinear function; the parameters are chosen such that the output of the function attains prescribed values for classes of input signal [3]. Although static functions are usually chosen for the design of pattern classi!cation systems, nonlinear dynamic systems can also be used for the design of such systems (e.g. Hop!eld neural networks). In this letter, we argue that e>ective pattern classi!cation systems can be designed by manipulating the parameters of nonlinear dynamic systems such that the qualitative behaviour of the function, rather than the steady-state output, acts as a signature of stored patterns. Potential advantages of this approach include: compact ∗Corresponding author. E-mail address: [email protected] (A. Rogers). 0925-2312/$ - see front matter c 2003 Elsevier B.V. All rights reserved. doi:10.1016/S0925-2312(03)00441-7 780 A. Rogers et al. / Neurocomputing 55 (2003) 779–786 representation of stored patterns; increased storage capacity; and the possibility of exploiting the qualitative behaviour of a function for speci!c applications. The objective of this letter is not to investigate these potential advantages, but rather to illustrate that controlling the qualitative behaviour of nonlinear systems provides a feasible basis for the design of pattern classi!cation systems. Speci!cally: (i) we show that a typical chaotic nonlinear system, the Baker’s map [2], can be used as the basis for the design of pattern classi!cation systems; (ii) we present algorithms for training our Baker’s map pattern classi!cation system; (iii) we present examples to illustrate the eFcacy of our paradigm. 2. The Baker’s map and Lyapunov dimensions In their classic study of fractal dimensions, Farmer et al. [4] re-introduced the Baker’s map [2]. 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 yn¿S; yn+1 =   yn=S if yn¡S; yn−S 1−Sif yn¿S: (1) Chaotic maps, such as the Baker’s map, are deterministic systems whose long-term behaviour is unpredictable. Despite this uncertainty in behaviour, there are quantitative measures of chaos which can be computed. One such measure is the Lyapunov dimension (DL) of the chaotic attractor. This is a particular type of fractal dimension, and is related to the average rates of expansion and contraction of the map. From Fig. 1, it can be seen that repeated iteration of the map leads to an attractor, which is the union of a line and a Cantor set, and thus the fractal dimension (Lyapunov S 1 1 00 S 1 R1 1 0.5+R2 0.5 x yy x 0 0.5 S 1 Strip widths not to scale Fig. 1. Action of Baker’s map on unit square: transforms square into two strips, then four strips, eight strips, and so on. A. Rogers et al. / Neurocomputing 55 (2003) 779–786 781 Fig. 2. Variation of Lyapunov dimension with parameters Rand S. dimension) must lie in the range 1 6DL62, depending on the choice of parameter values. The so-called Lyapunov numbers xand ycharacterise the stability of the map, and are de!ned as follows: log x=Slog R1+(1−S) log R2; log y=Slog 1 S+(1−S) log 1 1−S:(2a,2b) The Lyapunov dimension DLwas introduced by Kaplan and Yorke [6] and for the Baker’s map, DL=1+ log x log 1=y :(3) For the purposes of 2-bit pattern classi!cation, we require only two parameters, and so let R1=R2=R. The variation of Lyapunov dimension with Rand Sis shown in Fig. 2. It has the useful property that it is monotonically increasing for R; S ∈(0;5). From Fig. 3, it can be seen that many di>erent parameter pairs, or patterns, will lead to the same Lyapunov dimension, for example, in the !gure, (R; S)={(0:1;0:5);(0:36;0:1)} correspond to the same Lyapunov dimension DA(note the Lyapunov dimension DL varies between 1 and 2 depending on the values of Rand S, as can be seen in Fig. 2. 782 A. Rogers et al. / Neurocomputing 55 (2003) 779–786 Fig. 3. Side-view of Fig. 2showing two di>erent sets of parameters having the same Lyapunov dimension DA. Fig. 4. A more general way of solving the XOR problem: draw a straight line through the two points belonging to class A(say), and !nd where the line intersects the y-axis. For a general-purpose XOR-type pattern classi!er, described later, we use a linear transformation to map one of the classes onto the same fractal dimension, which we call DM, the modi!ed Lyapunov dimension as illustrated in Fig. 4. For di>erent types A. Rogers et al. / Neurocomputing 55 (2003) 779–786 783 of class arrangement, it is necessary to !nd some transformation which will separate the classes, so that for instance, patterns in class A lies below some value of DM, and patterns in class B lie above. We illustrate a training algorithm in the next section. 3. Training Training algorithms for the Baker’s map system involves estimating the parameters of the linear mapping onto DMfor a given set of inputs and associated class labels. In principle, a number of standard paradigms from the statistical pattern recognition and neural network literature could be used as the basis for a training algorithm for our system [3,5]. Here, we present a modi!ed simulated annealing training algorithm consisting of the following steps [8,7]: Initialise system parameters to state X0 Initialise annealing parameter T Repeat until {classi!cation error is below threshold OR annealing parameter Tis below annealing threshold { Repeat for large number of iterations { Perturb system to new state Xi; Determine change in cost(s) NEj=Ej(Xi)−Ej(Xi−1); If NEj¡0 Accept Xi; else if NEj¿0 Accept Xiwith probability e−NEjT; end; } } Reduce annealing parameter T; } To overcome diFculties associated with adopting a single cost function for general classi!cation tasks, we utilize a technique from the multiple-models and switching literature [9]: we specify a number of cost functions, one of which is guaranteed to converge for the unknown classi!cation task. Each cost function is evaluated online, using training and test data sets, and the algorithm is terminated when one of the cost functions converges or falls below some pre-speci!ed threshold. In the next section we present an example to illustrate our algorithm. 784 A. Rogers et al. / Neurocomputing 55 (2003) 779–786 4. XOR pattern classi$cation task We demonstrate the pattern classi!cation system with a simple XOR-type classi!- cation task. It is necessary to assign values to Rand S, representing high and low. We arbitrarily choose the following values (though limiting both Rand Sto (0, 0.5)). The training procedure is carried out on a line in the R-DL. plane, so we !nd the corresponding values of Lyapunov dimension DLfor each (R; S) pair. This is possible as there exists a closed-form expression for DLin terms of Rand S[4], DL=1−Sln[1=S]+(1−S)ln[1=(1 −S)] ln R:(4) Binary pattern R-value S-value DL 0 0 0.2 0.2 1.3109 0 1 0.2 0.4 1.4182 1 0 0.4 0.2 1.5461 1 1 0.4 0.4 1.7345 We now apply the simulated annealing algorithm to !nd a line, which will classify the patterns correctly, as shown in Fig. 5. Finally, we apply test patterns to the Baker’s map, to verify that the correct patterns are detected. The two cost functions used are as follows, where direpresent the perpendicular distances from the patterns to the line (a) E=classAB tanh(di) (b) E=classAB tanh(di)2. Fig. 5. Patterns/classes in R–DLplane, and a possible separating line. In practice, each diamond or star can represent a cluster of patterns. A. Rogers et al. / Neurocomputing 55 (2003) 779–786 785 Fig. 6. Patterns between the dotted lines belong to class A. We can classify the patterns simply by looking at their modi!ed Lyapunov dimension. When we apply the simulated annealing algorithm, we !nd that the slope m=0:487 and y-intercept = 1:34. This information is used to separate the classes, as shown in Fig. 6. There is some expected variation in Lyapunov numbers, (and hence the Lyapunov dimension) due to the nature of the map (see Eq. (1)). We !nd average values of the Lyapunov dimension, using a 500-point averaging window. In Fig. 6,we apply the four possible patterns to the system, as inputs. After modifying the Lyapunov dimension, the points lying below the separating line correctly correspond to the pattern Class B. 5. Conclusions We have shown that certain properties of chaotic mappings can be utilized to create a simple pattern classi!cation system. Our system has been based on a purely chaotic dynamical system, whereas some other researchers have found uses for nonlinear maps not necessarily operating in a chaotic regime [1]. As the study of nonlinear dynamics reaches a state of comparative maturity, it is hoped that other innovative applications of chaos will be found. 786 A. Rogers et al. / Neurocomputing 55 (2003) 779–786 References [1] Y.V. Andreyev, A. Dmitriev, S.O. Starkov, Information processing in 1-D systems with chaos, IEEE CAS-I Fund. Theory Appl. 44 (1997) 21–28. [2] J. Balatoni, A. Renji, Publ. Math. Inst. Hungarian Acad. Sci. 1 (9) (1956) 9– 40. [3] R. Duda, P. Hart, D. Stork, Pattern Classi!cation, Wiley, New York, 2001. [4] J.D. Farmer, E. Ott, J.A. Yorke, The dimension of chaotic attractors, Physica D 7 (1983) 153–180. [5] T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer, New York, 2001. [6] J. Kaplan, J. Yorke, Chaotic behaviour of multidimensional di>erence equations, in: H.O. Peitgen, H.O. Walther (Eds.), Functional Di>erential Equations and the Approximations of Fixed Points, Lecture Notes in Mathematics, Vol. 730, Springer, Berlin, 1979, pp. 204–207. [7] J.G. Keating, D. Noonan, The structure and performance of trained Boolean networks, in: G. Orchard (Ed.), Neural Computing: Research and Applications, Vol. II (Irish Neural Networks Association, Belfast, 1994, pp. 79–86). [8] S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi, Optimization by simulated annealing, Science 220 (1983) 671–680. [9] K.S. Narendra, Neural networks for control theory and practice, IEEE Proc. 84 (1996) 1385–1406.