A novel pattern classification scheme using the Baker's map

Neu ocompu ing 55 (2003) 779–786 www.else ie .com/loca e/neucom Le e s A no el pa e n classi!ca ion scheme using he Bake ’s map Alan Roge sa;∗, John Kea ingb, Robe Sho enc aDepa men o Elec onic Enginee ing, NUI Maynoo h, Maynoo h, Co. Kilda e, I eland bDepa men o Compu e Science, NUI Maynoo h, Maynoo h, Co. Kilda e, I eland cHamil on Ins i u e, NUI Maynoo h, Maynoo h, Co. Kilda e, I eland Abs ac We demons a e a no el applica ion o nonlinea sys ems in he design o pa e n classi!ca- ion sys ems. We show ha pa e n classi!ca ion sys ems can be designed based upon aining algo i hms designed o con ol he quali a i e beha iou o a nonlinea sys em. Ou pa adigm is illus a ed by means o a simple chao ic sys em— he Bake ’s map. Algo i hms o aining he sys em a e p esen ed and examples a e gi en o illus a e he ope a ion and lea ning o he sys em o pa e n classi!ca ion asks. c 2003 Else ie B.V. All igh s ese ed. Keywo ds: Pa e n classi!ca ion; Chaos Bake ’s map; Lyapuno dimension 1. In oduc ion Con en ional pa e n classi!ca ion sys ems a e usually cons uc ed by manipula ing he pa ame e s o some nonlinea unc ion; he pa ame e s a e chosen such ha he ou - pu o he unc ion a ains p esc ibed alues o classes o inpu signal [3]. Al hough s a ic unc ions a e usually chosen o he design o pa e n classi!ca ion sys ems, non- linea dynamic sys ems can also be used o he design o such sys ems (e.g. Hop!eld neu al ne wo ks). In his le e , we a gue ha e>ec i e pa e n classi!ca ion sys ems can be designed by manipula ing he pa ame e s o nonlinea dynamic sys ems such ha he quali a i e beha iou o he unc ion, a he han he s eady-s a e ou pu , ac s as a signa u e o s o ed pa e ns. Po en ial ad an ages o his app oach include: compac ∗Co esponding au ho . E-mail add ess: [email p o ec ed] (A. Roge s). 0925-2312/$ - see on ma e c 2003 Else ie B.V. All igh s ese ed. doi:10.1016/S0925-2312(03)00441-7 780 A. Roge s e al. / Neu ocompu ing 55 (2003) 779–786 ep esen a ion o s o ed pa e ns; inc eased s o age capaci y; and he possibili y o ex- ploi ing he quali a i e beha iou o a unc ion o speci!c applica ions. The objec i e o his le e is no o in es iga e hese po en ial ad an ages, bu a he o illus a e ha con olling he quali a i e beha iou o nonlinea sys ems p o ides a easible basis o he design o pa e n classi!ca ion sys ems. Speci!cally: (i) we show ha a ypical chao ic nonlinea sys em, he Bake ’s map [2], can be used as he basis o he design o pa e n classi!ca ion sys ems; (ii) we p esen algo i hms o aining ou Bake ’s map pa e n classi!ca ion sys em; (iii) we p esen examples o illus a e he eFcacy o ou pa adigm. 2. The Bake ’s map and Lyapuno dimensions In hei classic s udy o ac al dimensions, Fa me e al. [4] e-in oduced he Bake ’s map [2]. I is a ans o ma ion o he uni squa e [0;1]×[0;1], and has h ee pa ame e s, R1,R2and S: xn+1 =R1xni yn¡S; 1=2+R2xni yn¿S; yn+1 =   yn=S i yn¡S; yn−S 1−Si yn¿S: (1) Chao ic maps, such as he Bake ’s map, a e de e minis ic sys ems whose long- e m beha iou is unp edic able. Despi e his unce ain y in beha iou , he e a e quan i a- i e measu es o chaos which can be compu ed. One such measu e is he Lyapuno dimension (DL) o he chao ic a ac o . This is a pa icula ype o ac al dimension, and is ela ed o he a e age a es o expansion and con ac ion o he map. F om Fig. 1, i can be seen ha epea ed i e a ion o he map leads o an a ac o , which is he union o a line and a Can o se , and hus he ac al dimension (Lyapuno S 1 1 00 S 1 R1 1 0.5+R2 0.5 x yy x 0 0.5 S 1 S ip wid hs no o scale Fig. 1. Ac ion o Bake ’s map on uni squa e: ans o ms squa e in o wo s ips, hen ou s ips, eigh s ips, and so on. A. Roge s e al. / Neu ocompu ing 55 (2003) 779–786 781 Fig. 2. Va ia ion o Lyapuno dimension wi h pa ame e s Rand S. dimension) mus lie in he ange 1 6DL62, depending on he choice o pa ame e alues. The so-called Lyapuno numbe s xand ycha ac e ise he s abili y o he map, and a e de!ned as ollows: log x=Slog R1+(1−S) log R2; log y=Slog 1 S+(1−S) log 1 1−S:(2a,2b) The Lyapuno dimension DLwas in oduced by Kaplan and Yo ke [6] and o he Bake ’s map, DL=1+ log x log 1=y :(3) Fo he pu poses o 2-bi pa e n classi!ca ion, we equi e only wo pa ame e s, and so le R1=R2=R. The a ia ion o Lyapuno dimension wi h Rand Sis shown in Fig. 2. I has he use ul p ope y ha i is mono onically inc easing o R; S ∈(0;5). F om Fig. 3, i can be seen ha many di>e en pa ame e pai s, o pa e ns, will lead o he same Lyapuno dimension, o example, in he !gu e, (R; S)={(0:1;0:5);(0:36;0:1)} co espond o he same Lyapuno dimension DA(no e he Lyapuno dimension DL a ies be ween 1 and 2 depending on he alues o Rand S, as can be seen in Fig. 2. 782 A. Roge s e al. / Neu ocompu ing 55 (2003) 779–786 Fig. 3. Side- iew o Fig. 2showing wo di>e en se s o pa ame e s ha ing he same Lyapuno dimension DA. Fig. 4. A mo e gene al way o sol ing he XOR p oblem: d aw a s aigh line h ough he wo poin s belonging o class A(say), and !nd whe e he line in e sec s he y-axis. Fo a gene al-pu pose XOR- ype pa e n classi!e , desc ibed la e , we use a linea ans o ma ion o map one o he classes on o he same ac al dimension, which we call DM, he modi!ed Lyapuno dimension as illus a ed in Fig. 4. Fo di>e en ypes A. Roge s e al. / Neu ocompu ing 55 (2003) 779–786 783 o class a angemen , i is necessa y o !nd some ans o ma ion which will sepa- a e he classes, so ha o ins ance, pa e ns in class A lies below some alue o DM, and pa e ns in class B lie abo e. We illus a e a aining algo i hm in he nex sec ion. 3. T aining T aining algo i hms o he Bake ’s map sys em in ol es es ima ing he pa ame e s o he linea mapping on o DM o a gi en se o inpu s and associa ed class labels. In p inciple, a numbe o s anda d pa adigms om he s a is ical pa e n ecogni ion and neu al ne wo k li e a u e could be used as he basis o a aining algo i hm o ou sys em [3,5]. He e, we p esen a modi!ed simula ed annealing aining algo i hm consis ing o he ollowing s eps [8,7]: Ini ialise sys em pa ame e s o s a e X0 Ini ialise annealing pa ame e T Repea un il {classi!ca ion e o is below h eshold OR annealing pa ame e Tis below annealing h eshold { Repea o la ge numbe o i e a ions { Pe u b sys em o new s a e Xi; De e mine change in cos (s) NEj=Ej(Xi)−Ej(Xi−1); I NEj¡0 Accep Xi; else i NEj¿0 Accep Xiwi h p obabili y e−NEjT; end; } } Reduce annealing pa ame e T; } To o e come diFcul ies associa ed wi h adop ing a single cos unc ion o gene al classi!ca ion asks, we u ilize a echnique om he mul iple-models and swi ching li e a u e [9]: we speci y a numbe o cos unc ions, one o which is gua an eed o con e ge o he unknown classi!ca ion ask. Each cos unc ion is e alua ed online, using aining and es da a se s, and he algo i hm is e mina ed when one o he cos unc ions con e ges o alls below some p e-speci!ed h eshold. In he nex sec ion we p esen an example o illus a e ou algo i hm. 784 A. Roge s e al. / Neu ocompu ing 55 (2003) 779–786 4. XOR pa e n classi$ca ion ask We demons a e he pa e n classi!ca ion sys em wi h a simple XOR- ype classi!- ca ion ask. I is necessa y o assign alues o Rand S, ep esen ing high and low. We a bi a ily choose he ollowing alues ( hough limi ing bo h Rand S o (0, 0.5)). The aining p ocedu e is ca ied ou on a line in he R-DL. plane, so we !nd he co esponding alues o Lyapuno dimension DL o each (R; S) pai . This is possible as he e exis s a closed- o m exp ession o DLin e ms o Rand S[4], DL=1−Sln[1=S]+(1−S)ln[1=(1 −S)] ln R:(4) Bina y pa e n R- alue S- alue 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 he simula ed annealing algo i hm o !nd a line, which will classi y he pa e ns co ec ly, as shown in Fig. 5. Finally, we apply es pa e ns o he Bake ’s map, o e i y ha he co ec pa e ns a e de ec ed. The wo cos unc ions used a e as ollows, whe e di ep esen he pe pendicula dis ances om he pa e ns o he line (a) E=classAB anh(di) (b) E=classAB anh(di)2. Fig. 5. Pa e ns/classes in R–DLplane, and a possible sepa a ing line. In p ac ice, each diamond o s a can ep esen a clus e o pa e ns. A. Roge s e al. / Neu ocompu ing 55 (2003) 779–786 785 Fig. 6. Pa e ns be ween he do ed lines belong o class A. We can classi y he pa e ns simply by looking a hei modi!ed Lyapuno dimension. When we apply he simula ed annealing algo i hm, we !nd ha he slope m=0:487 and y-in e cep = 1:34. This in o ma ion is used o sepa a e he classes, as shown in Fig. 6. The e is some expec ed a ia ion in Lyapuno numbe s, (and hence he Lyapuno dimension) due o he na u e o he map (see Eq. (1)). We !nd a e age alues o he Lyapuno dimension, using a 500-poin a e aging window. In Fig. 6,we apply he ou possible pa e ns o he sys em, as inpu s. A e modi ying he Lyapuno dimension, he poin s lying below he sepa a ing line co ec ly co espond o he pa e n Class B. 5. Conclusions We ha e shown ha ce ain p ope ies o chao ic mappings can be u ilized o c ea e a simple pa e n classi!ca ion sys em. Ou sys em has been based on a pu ely chao ic dynamical sys em, whe eas some o he esea che s ha e ound uses o nonlinea maps no necessa ily ope a ing in a chao ic egime [1]. As he s udy o nonlinea dynamics eaches a s a e o compa a i e ma u i y, i is hoped ha o he inno a i e applica ions o chaos will be ound. 786 A. Roge s e al. / Neu ocompu ing 55 (2003) 779–786 Re e ences [1] Y.V. And eye , A. Dmi ie , S.O. S a ko , In o ma ion p ocessing in 1-D sys ems wi h chaos, IEEE CAS-I Fund. Theo y Appl. 44 (1997) 21–28. [2] J. Bala oni, A. Renji, Publ. Ma h. Ins . Hunga ian Acad. Sci. 1 (9) (1956) 9– 40. [3] R. Duda, P. Ha , D. S o k, Pa e n Classi!ca ion, Wiley, New Yo k, 2001. [4] J.D. Fa me , E. O , J.A. Yo ke, The dimension o chao ic a ac o s, Physica D 7 (1983) 153–180. [5] T. Has ie, R. Tibshi ani, J. F iedman, The Elemen s o S a is ical Lea ning, Sp inge , New Yo k, 2001. [6] J. Kaplan, J. Yo ke, Chao ic beha iou o mul idimensional di>e ence equa ions, in: H.O. Pei gen, H.O. Wal he (Eds.), Func ional Di>e en ial Equa ions and he App oxima ions o Fixed Poin s, Lec u e No es in Ma hema ics, Vol. 730, Sp inge , Be lin, 1979, pp. 204–207. [7] J.G. Kea ing, D. Noonan, The s uc u e and pe o mance o ained Boolean ne wo ks, in: G. O cha d (Ed.), Neu al Compu ing: Resea ch and Applica ions, Vol. II (I ish Neu al Ne wo ks Associa ion, Bel as , 1994, pp. 79–86). [8] S. Ki kpa ick, C.D. Gela J ., M.P. Vecchi, Op imiza ion by simula ed annealing, Science 220 (1983) 671–680. [9] K.S. Na end a, Neu al ne wo ks o con ol heo y and p ac ice, IEEE P oc. 84 (1996) 1385–1406.