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.