Margin maximization with feed-forward neural networks: a comparative study with support vector machines and AdaBoost
Abstract
Feed-forward Neural Networks (FNN) and Support Vector Machines (SVM) are two machine learning frameworks developed from very different starting points of view. In this work a new learning model for FNN is proposed such that, in the linearly separable case, it tends to obtain the same solution as SVM. The key idea of the model is a weighting of the sum-of-squares error function, which is inspired by the AdaBoost algorithm. As in SVM, the hardness of the margin can be controlled, so that this model can be also used for the non-linearly separable case. In addition, it is not restricted to the use of kernel functions, and it allows to deal with multiclass and multilabel problems as FNN usually do. Finally, it is independent of the particular algorithm used to minimize the error function. Theoretic and experimental results, on synthetic and real-world problems, are shown to confirm these claims. Several empirical comparisons among this new model, SVM and AdaBoost have been made in order to study the agreement between the predictions made by the respective classifiers. The results obtained show that similar performance does not imply similar predictions, suggesting that different models can be combined leading to better performance.
Full text
Maximizing he Ma gin wi h Feed- o wa d Neu al
Ne wo ks
En ique Rome o and Rene Alqueza
Depa amen de Llengua ges i Sis emes In o ma ics, Uni e si a Poli ecnica de Ca alunya
Abs ac - Feed- o wa d Neu al Ne wo ks (FNNs)
and Supp o Vec o Machines (SVMs) a e wo ma-
chine lea ning amewo ks de elop ed om e y di -
e en s a ing p oin s o iew. In his wo k a new
lea ning mo del o FNNs is p op osed such ha , in
he linea ly sepa able case, ends o ob ain he same
solu ion ha SVMs. The key idea o he mo del is a
weigh ing o he sum-o -squa es e o unc ion, which
is inspi ed in he AdaBo os algo i hm. The mo del
dep ends on a pa ame e ha con ols he ha dness o
he ma gin, as in SVMs, so ha i can b e used o
he non-linea ly sepa able case as well. In addi ion,
i allows o deal wi h mul iclass and mul ilab el p ob-
lems in a na u al way (as FNNs usually do), and i is
no es ic ed o he use o ke nel unc ions. Finally,
i is indep enden o he conc e e algo i hm used o
minimize he e o unc ion. Bo h heo e ic and ex-
p e imen al esul s a e shown o con m hese ideas.
I. In o duc ion
Feed- o wa d Neu al Ne wo ks (FNNs) and Supp o
Vec o Machines (SVMs) a e wo die en machine lea n-
ing amewo ks o app oaching classica ion and eg es-
sion p oblems. We will conside he classica ion ask
gi en by a da ase
X
=
(
x
1
y
1
)
:::
(
x
L
y
L
)
g
, wi h
x
i
2
R
N
and
y
i
2 ;
1
+1
g
C
, whe e
C
is he numbe o
classes. Minimizing he sum-o -squa es (o c oss-en opy)
e o unc ion and maximizing he ma gin a e e y di -
e en p oin s o iew wi h e y in e es ing p op e ies (1],
2]). Lo oking a he simila i ies and die ences b e ween
FNNs and SVMs, i can b e obse ed ha he main die -
ence b e ween he sum-o -squa es minimiza ion p oblem o
an FNN and he maximiza ion p oblem o a (1-No m So
Ma gin) SVM lies on he cons ain s ela ed o he ob jec-
i e unc ion. Since hese cons ain s a e he esp onsible
o he exis ence o he supp o ec o s, hei b eha iou
will gi e he key o p op ose a new lea ning mo del o
FNNs ha , in he linea ly sepa able case, ends o ob ain
he same solu ion ha SVMs. T ying o ob ain supp o
ec o s ( ha is, p oin s wi h ma gin 1), a weigh ing o he
sum-o -squa es e o unc ion is p op osed. This weigh ing
is inspi ed in he AdaBo os algo i hm 3], and i consis s
o mo di ying he con ibu ion o e e y p oin o he o al
e o dep ending on i s ma gin. The mo del dep ends on a
This wo k was supp o ed by Consejo In e minis e ial de Ciencia
yTecnologa (CICYT), unde p o jec TAP1999-0747
pa ame e ha con ols he ha dness o he ma gin, as in
SVMs, so ha i can b e used o he non-linea ly sepa-
able case. In addi ion, he classical FNN a chi ec u e o
he new mo del p esen s some ad an ages. Fi s , i allows
o deal wi h mul iclass and mul ilab el p oblems in a na -
u al way. This is a dicul p oblem o SVMs, since hey
a e ini ially designed o bina y classica ion p oblems.
In addi ion, he nal solu ion is nei he es ic ed o ha e
an a chi ec u e wi h so many hidden uni s as p oin s (o
supp o ec o s) in he da ase no o use ke nel unc ions
necessa ily. Bo h heo e ic and exp e imen al esul s a e
shown o con m hese ideas.
Some p elimina ies ab ou FNNs, SVMs and AdaBo os
can b e ound in Sec ion I I. In Sec ion I I I, some simi-
la i ies and die ences b e ween FNNs and SVMs will b e
discussed. The lea ning mo del and some heo e ic esul s
will b e p esen ed in Sec ion IV. Finally, he exp e imen al
esul s will b e shown in Sec ion V.
II. P elimina ies
A. Feed- o wa d Neu al Ne wo ks
The well known a chi ec u e o an FNN is s uc u ed by
laye s o uni s, wi h connec ions b e ween uni s om di -
e en laye s in o wa d di ec ion 1]. A ully connec ed
FNN wi h one ou pu uni and one hidden laye o uni s
compu es he unc ion:
FNN
(
x
)=
'
0
N hid
X
i
=1
i
'
i
(
!
i
xb
i
)+
b
0
!
(1)
whe e
i
b
i
b
0
2
R
,
x !
i
2
R
N
and
N hid
is he numbe
o uni s in he hidden laye . The mos used ac i a ion
unc ions
'
i
(
! x b
) in he hidden uni s a e sigmoidal o
Mul i-laye Pe cep ons (MLPs) and adially symme ic
o Radial Basis Func ion Ne wo ks (RBFNs), al hough
many o he unc ions may b e used (6], 7]). Ou pu ac-
i a ion unc ions
'
0
(
u
) use o b e sigmoidal o linea .
The ob jec i e o he aining p o cess is o cho ose ade-
qua e pa ame e s o minimize a p ede e mined cos unc-
ion. The sum-o -squa es e o unc ion is he mos usual:
E
(
X
)=
L
X
i
=1
1
2
FNN
(
x
i
)
;
y
i
]
2
:
As i is well known, he sum-o -squa es e o unc ion
E
(
X
) isanap oxima ion o he squa ed no m o he e o
unc ion
FNN
(
x
)
;
y
in he Hilb e space
L
2
.
0-7803-7278-6/02/$10.00 ©2002 IEEE
The a chi ec u e (connec ions, numb e o hidden uni s
and ac i a ion unc ions) is usually xed
a p io i
, whe eas
he weigh s a e lea ned du ing he aining p o cess. Fo
con enience, we will di ide he weigh s in o equencies
(
!
i
)
Nhid
i
=1
, co ecien s (
i
)
Nhid
i
=1
and biases (
b
i
)
N hid
i
=1
. No e
ha he app ea ance o he ou pu unc ion gi en by (1)
is de e mined by he a chi ec u e o he ained FNN.
B. Supp o Vec o Machines
The idea o SVMs can b e s a ed as ollows (2], 13]):
he inpu ec o s a e mapp ed in o a (usually high-di-
mensional) inne p o duc space h ough some non-linea
mapping
,chosen
a p io i
. In his space ( he ea-
u e space), an op imal hyp e plane is cons uc ed. Us-
ing a ke nel unc ion
K
(
u
) he mapping can b e im-
plici , since he inne p o duc which denes he hyp e -
plane can b e e alua ed as
h
(
u
)
(
)
i
=
K
(
u
) o e -
e y wo ec o s
u
2
R
N
. In SVMs, an op imal hyp e -
plane means a hyp e plane wi h maximal no malized ma -
gin wi h esp ec o he da ase . The ( unc ional) ma gin
o apoin (
x
i
y
i
) wi h esp ec o a unc ion
is dened
as
m g
(
x
i
y
i
)=
y
i
(
x
i
). The ma gin o a unc ion
wi h esp ec o a da ase
X
is he minimum o he ma -
gins o he p oin s in he da ase . I
is a hyp e plane, he
no malized (o geome ic) ma gin is dened as i s ma -
gin di ided by he no m o he o hogonal ec o o he
hyp e plane. Using Lag angian and Kuhn-Tucke heo y,
he maximal ma gin hyp e plane o a bina y classica ion
p oblem u ns o b e
SV M
(
x
)=
L
X
i
=1
y
i
i
K
(
x
i
x
)+
b
(2)
whe e he ec o (
i
)
L
i
=1
is he (1-No m So Ma gin) so-
lu ion o he ollowing cons ained op imiza ion p oblem
in he dual space:
Maximize
W
(
X
)=
;
1
2
P
L
ij
=1
y
i
i
y
j
j
K
(
x
i
x
j
)+
P
L
i
=1
i
sub jec o
P
L
i
=1
y
i
i
=0
0
6
i
6
C i
=1
:::L
.
The p oin s
x
i
wi h
i
>
0 (ac i e cons ain s) a e
supp o ec o s, while b ounded supp o ec o s ha e
i
=
C
. Non-b ounded supp o ec o s ha e ma gin 1,
while b ounded supp o ec o s ha e ma gin less han 1.
A p oin iswell classied i and only i s ma gin wi h e-
sp ec o
SV M
is p osi i e. The cos unc ion
;
W
(
X
)is
(plus a cons an ) he squa ed no m o he e o unc ion
SV M
(
x
)
;
y
in he Rep o ducing Ke nel Hilb e Space
asso cia ed o
K
(
u
) (2], pag. 41). By se ing
C
=
1
,
one ob ains he ha d ma gin hyp e plane. The mos used
ke nel unc ions
K
(
u
) a e p olynomial o Gaussian-like.
In con as o FNNs, no e ha he app ea ance o he so-
lu ion is a consequence o he way he p oblem is sol ed.
C. AdaBo os
The AdaBo os algo i hm is a pa icula b o os ing algo-
i hm in o duced in 3] and la e imp o ed in 11]. Ad-
aBo os calls a gi en weak lea ning algo i hm in a se ies o
ounds. On each ound
i compu es a weak hyp o hesis
h
. One o he main ideas o he algo i hm is o main ain
a dis ibu ion
D
(a se o weigh s) o e he aining se .
Ini ially,all weigh s a e se equally, bu on each ound
,
he weigh s a e mo died:
D
(
x
i
y
i
H
)=
e
;
m g
(
x
i
y
i
H
)
Z
(3)
whe e
H
=
P
j
=1
j
h
j
(
x
i
) is he cu en hyp o hesis, and
Z
is a no maliza ion ac o so ha
D
is a p obabili y
dis ibu ion. The eec o he dis ibu ion
D
is ha he
weigh s o inco ec ly classied examples a e inc eased so
ha he weak lea ne
h
+1
is o ced o o cus on he ha d
(dep ending on
D
) examples in he aining se .
III. FNNs s SVMs
A. Compa ing he ou pu unc ions
As p oin ed ou elsewhe e (see, o example, 14]), he ou -
pu unc ion
SV M
o a SVM (2) can b e implemen ed
wi h a ully connec ed FNN wi h one ou pu uni and
one hidden laye o uni s:
1. Numbe o hidden uni s:
L
(=
k
X
k
)
2. Co ecien s:
i
=
y
i
i
3. F equencies:
!
i
=
x
i
4. Biases:
b
i
anishes, and
b
0
=
b
5. Ac i a ion unc ions:
(a) Hidden laye :
'
i
(
x
i
xb
i
)=
K
(
x
i
x
)
(b) Ou pu laye :
'
0
linea
As in SVMs, he only pa ame e s o b e lea ned in such
an FNN compu ing (1) would b e he co ecien s and he
biases. So, he main die ences b e ween FNNs and SVMs
ely b o h on he cos unc ion o b e op imized and he
cons ain s, since sp ecic lea ning algo i hms a e a con-
sequence o he op imiza ion p oblem o b e sol ed.
B. Compa ing he cos unc ions
Ou s ques ion has o do wi h he simila i ies b e ween
he esp ec i e cos unc ions. Dening
K
L
=(
K
(
x
i
x
j
))
N
ij
=1
y
=(
y
1
:::y
L
)
T
,
y
=(
y
1
1
:::y
L
L
)
T
and consid-
e ing he iden ica ions s a ed in Sec ion III-A we can
exp ess he esp ec i e cos unc ions as:
E
(
X
)=
1
2
y
T
K
L
K
L
y
;
y
T
K
L
y
+
1
2
L
W
(
X
)=
;
1
2
y
T
K
L
y
+
y
T
y
0-7803-7278-6/02/$10.00 ©2002 IEEE
Rega dless o hei appa en simila i y, is he e any e-
la ionship b e ween he minima o
E
(
X
) and he maxima
o
W
(
X
) (o equi alen ly, he minimao
;
W
(
X
))? The
nex esul pa ially answe s his ques ion.
P op osi ion 1.
I
K
L
is non-singula , hen he
esp ec i e cos unc ions
E
(
X
)and
;
W
(
X
) a ain hei
unique minimum (wi hou cons ain s) a he same p oin .
P oo .
As
E
(
X
)and
;
W
(
X
) a e con ex unc ions,
a necessa y and sucien condi ion o
y
o b e a
global minimum is ha hei de i a i e wi h esp ec o
y
anishes. Since
K
L
non-singula , b o h equa ions ha e
he same solu ion.
I
K
L
is singula , he e will b e mo e han one p oin
whe e he op imum alue is a ained, bu all o hem a e
equi alen . In addi ion,
K
L
has ows which a e linea ly
dep enden among hem. I indica es ha he in o ma ion
p o ided ( ia he inne p o duc ) by a p oin in he da ase
is edundan , since i is a linea combina ion o he in o -
ma ion p o ided by o he p oin s. Thus, ha p oin could
p obably b e elimina ed om he da ase and he nal
solu ion would no change.
Indeed, he op ima can b e e y die en dep ending on
he absence o p esence o he cons ain s. The e o e, i
seems ha he main die ence lies on he cons ain s.
IV. An FNN ha maximizes he ma gin
A. Howdoes e e y p oin con ibu e o he cos unc ion?
The exis ence o linea cons ain s in he op imiza ion
p oblem o b e sol ed in SVMs has a e y imp o an con-
sequence: only some o he
i
will b e die en om ze o.
These co ecien s a e asso cia ed wi h he so called sup-
p o ec o s. Thus, he emaining ec o s can b e omi ed,
b o h o op imize
W
(
X
) and o compu e he ou pu (2).
The p oblem is ha we do no know hem
a p io i
.In
he linea ly sepa able case (ha d ma gin), supp o ec-
o s ha e ma gin 1 ( ha is,
SV M
(
x
i
)=
y
i
), while he
emaining p oin s ( ha will b e e e ed o as sup e clas-
sied" p oin s) ha e a ma gin s ic ly g ea e han 1.
In con as , o FNNs minimizing he sum-o -squa es
e o unc ion e e y p oin makes i s con ibu ion o he
o al e o . The g ea e is he squa ed e o , he g ea e
will b e he con ibu ion, indep enden ly o whe he he
poin iswell o w ongly classied. Wi h linea ou pu
uni s, he e maybe poin s ( e y) well classied wi h a
( e y) big squa ed e o . Sup e classied" p oin s a e a
clea example o his yp e. Sigmoidal ou pu uni s can
help o sol e his p oblem, bu hey can also c ea e new
ones (in he linea ly sepa able case, o example, he so-
lu ion is no b ounded). An al e na i e idea o sigmoidal
ou pu uni s could b e o educe he con ibu ion o su-
p e classied" p oin s and ein o ce hose o misclassied
poin s, as explained in he nex sec ion.
B. Weigh ing he con ibu ion
Indeed, we do no know
a p io i
which p oin s will b e
nally sup e classied" o misclassied. Bu du ing he
FNN lea ning p o cess i is p ossible o ea e e y p oin in
a die en way dep ending on i s e o (o , equi alen ly, i s
ma gin). In o de o simula e he b eha iou o a SVM, he
lea ning p o cess could b e guided by he ollowing heu is-
ics:
1. Anywell classied p oin con ibu es less o he e o
han any misclassied p oin .
2. Be ween well classied p oin s, he con ibu ion is
la ge o smalle e o s in absolu e alue (o equi -
alen ly, smalle ma gins).
3. Be ween misclassied p oin s, he con ibu ion is
la ge o la ge e o s in absolu e alue (o equi -
alen ly, smalle ma gins).
These guidelines ein o ce he con ibu ion o misclassi-
ed p oin s and educes he con ibu ion o well classi-
ed ones. As can b e seen, his is exac ly he same idea
han he dis ibu ion (3) o AdaBo os . Simila ly, he
con ibu ion o e e y p oin o he e o can b e mo died
simply byweigh ing i indi idually as a unc ion o he
ma gin wi h esp ec o he ou pu unc ion
FNN
.Ino -
de o allow mo e exibili y o he mo del, wo pa ame e s
+
;
>
0canbein o duced in o he weigh ing unc ion
as ollows (
m g
=
m g
(
x
i
y
i
FNN
)):
D
(
x
i
y
i
+
;
)=
8
>
<
>
:
e
;j
m g
j
+
i
m g
>
0
e
+
j
m g
j
;
i
m g <
0 and
;
6
=0
1 o he wise
(4)
This weigh ing can b e applied a leas a wole els
(
E
p
=
E
p
(
FNN
(
x
i
)
y
i
+
;
)):
1. Weigh ing he sum-o -squa es e o :
E
p
=
1
2
FNN
(
x
i
)
;
y
i
]
2
D
(
x
i
y
i
+
;
) (5)
2. Weigh ing he sum-o -squa es e o de i a i e (only
i he de i a i eis in ol ed in he lea ning p o cess):
@E
p
@
FNN
=(
FNN
(
x
i
)
;
y
i
)
D
(
x
i
y
i
+
;
) (6)
G aphically (see gu e 1), he igh b ancho he
squa ed e o pa ab ola is b ended o a ho izon al asymp-
o e. Weigh ing he sum-o -squa es e o de i a i e also
implies a kind o weigh ing he sum-o -squa es e o , al-
hough in a sligh ly die en way.
The ollowing esul jus ies ha he p e iously
sugges ed weigh ing unc ions a e well ounded. In
addi ion, i allows o cons uc new e o unc ions in
o de o simula e he b eha iou o a SVM.
0-7803-7278-6/02/$10.00 ©2002 IEEE
Fig. 1.
Indi idual e o o he weigh ed sum-o -squa es e o
(5) (le ) and he weigh ed sum-o -squa es e o de i a i e(6)
( igh ) o se e al alues o
+
(
;
= 0).
Theo em 1.
Le
2
R
,
y
2 ;
1
+1
g
,
+
;
>
0
and
E
p
(
y
+
;
) an e o unc ion sa is ying:
1. Fo e e y
+
;
>
0,
E
p
a ains i s (absolu e) min-
imum alue when
y
= 1, and his alue
A
do es no
dep end on
+
.
2. Fo e e y
;
>
0and e e y
y
sa is ying
y >
1
weha e
lim
+
!1
E
p
(
y
+
;
)=
A
Then, i
X
=
(
x
1
y
1
)
:::
(
x
L
y
L
)
g
is a linea ly sepa a-
ble da ase , he hyp e plane
h
(
x
) ha maximizes he no -
malized ma gin also minimizes asymp o ically (
+
!1
)
he weigh ed sum-o -squa es e o unc ion
E
P
(
X
)=
L
X
i
=1
E
p
(
h
(
x
i
)
y
+
;
)
:
(7)
Rema ks.
The heo em holds ue indep enden ly o whe he he
da ase
X
is linea ly sepa able ei he in he inpu
space o in he ea u e space.
The p e iously sugges ed weigh ing unc ions (5) and
(6) sa is y he hyp o hesis o he heo em.
P oo .
Since
X
is linea ly sepa able,
h
(
x
) sa ises
ha he ma gin
y
i
h
(
x
i
) = 1 o he supp o ec o s,
whe eas
y
i
h
(
x
i
)
>
1 o he non-supp o ec o s. Since
A
is he absolu e minimum o
E
p
, ega dless o
+
,
he minimum alue ha
E
P
could a ain is
L
A
.
The s hyp o hesis implies ha o supp o ec o s,
E
p
(
h
(
x
i
)
y
+
;
)=
A
.Fo non-supp o ec o s, his
alue is asymp o ically a ained when
+
!1
, b ecause
o he second hyp o hesis.
The ecip o cal may no b e necessa ily ue, since he e
can b e many die en hyp e planes which asymp o ically
minimize
E
P
(
X
). Howe e , he solu ion ob ained bymin-
imizing
E
P
(
X
) is exp ec ed o ha e a simila b eha iou
ha a SVM. In pa icula :
1. I is exp ec ed ha a la ge
+
will b e ela ed o a
ha de ma gin.
2. Poin s wi h ma gin less o equal han 1 a e exp ec ed
o b e supp o ec o s. Fo he linea ly sepa able
case, he ma gin exp ec ed o e e y supp o is 1.
3. Theo e ical esul s o SVMs ( o example, gene al-
iza ion b ounds) a e exp ec ed o b e easily applicable
o adap ed o he ob ained solu ions.
C. P ac ical conside a ions
Some b ene s can b e ob ained by minimizing an e o
unc ion (7) as he p e iously dened.
Fi s , he minimiza ion o (7) do es no assume he ex-
is ence o any p ede e mined a chi ec u e in he FNN:
1. The e is no need o ha e, in he nal solu ion, as
many hidden uni s as p oin s (o supp o ec o s) in
he da ase , no he equencies mus b e he p oin s
in he da ase .
2. The e is no need o use ke nel unc ions, since he e
is no inne p o duc o compu e in he ea u e space.
In addi ion, i p esen s a numbe o ad an ages o e he
classical SVM mo del:
1. The e is no limi on he numb e o classes o deal
wi h. Fo
C
-class p oblems, i is enough o cons uc
an a chi ec u e wi h
C
ou pu uni s. The indi idual
squa ed e o o e e y p oin is dened as usual 1]:
E
P
(
X
)=
L
X
i
=1
C
X
c
=1
E
p
(
c
FNN
(
x
i
)
y
c
i
+
;
)
:
(8)
2. The same e o unc ion (8) allows o deal wi h mul-
ilab el p oblems wi hou es ic ions.
Finally, i is indep enden o he conc e e algo i hm used
o minimize he e o unc ion.
D. Rela ed wo k
In 4] an equi alence b e ween Spa se App oxima ion and
SVMsisshown, wi h some ela ionships o RBFNs. A
single-laye p e cep on lea ning algo i hm ha asymp o -
ically ob ains he maximum ma gin classie is p esen ed
in 8]. In o de o wo k, he da ase mus b e necessa -
ily linea ly sepa able, and he lea ning a e should b e in-
c eased exp onen ially, leading o weigh s a bi a ily la ge.
In 12], a mo died SVM app oach o aining an MLP
wi haxednumb e o hidden uni s is desc ib ed. An es-
ima ion o an upp e b ound o he Vapnik-Che onenkis
dimension is i e a i ely minimized o e he equencies
and he biases. The SVM me ho d inspi es he calcula ion
o he co ecien s, bu i is no he same one. The wo k in
15] in es iga es lea ning a chi ec u es in which he ke nel
unc ion can b e eplaced by mo e gene al simila i y mea-
su es ha can ha ein e nal pa ame e s. Al hough he
equencies a e o ced o b e he p oin s in he da ase , he
cos unc ion
E
(
X
)=
P
L
i
=1
0
:
65
;
anh(
m g
(
x
i
y
i
))]
2
is used.
0-7803-7278-6/02/$10.00 ©2002 IEEE
510
10
5
510
10
5
α = 9
x - y - 3 = 0
2x - 9y + 41/2 = 0
α = 3
α = 9 α = 3
+
+
+
+
Fig. 2.
Sepa a ing hyp e planes (solid lines) a e minimizing he
weigh ed sum-o -squa es (7) o die en alues o
+
in he
wo-class linea ly sepa able p oblems
L
2 (le ) and
R
2 ( igh ).
V. Exp e imen s
We p e o med some exp e imen s on a icial da a in
o de o es b o h he alidi y o he new mo del and he
p edic ions made in Sec ion IV. In pa icula , wewe e
in e es ed in es ing:
1. Whe he lea ning is p ossible o no wi h a s anda d
FNN a chi ec u e when a weigh ed sum-o -squa es
e o
E
P
(
X
) is minimized wi h s anda d me ho ds.
2. The eec o
+
on he ha dness o he ma gin.
3. The iden ica ion o he supp o ec o s, simply by
compa ing hei ma gin alue wi h 1.
4. The b eha iou o he mo del in mul iclass p oblems
minimizing he e o unc ion (8).
5. The b eha iou o he mo del in non-linea ly sepa a-
ble cases, when a non-linea ac i a ion unc ion in
he hidden laye is needed.
6. Whe he he use o non-ke nel unc ions can lead o
no o a b eha iou simila o ha o ke nel unc ions.
We se
;
= 0, so ha misclassied p oin s had all o
hem a weigh o 1. All exp e imen s we e p e o med wi h
FNNs ained wi h s anda d Back-p opaga ion 9] weigh -
ing he sum-o -squa es e o de i a i e(6). We will call
his me ho d BPW. E e y a chi ec u e had linea ou pu
uni s, and was ained in ba ch mo de.
A. Two linea ly sepa able classes
Ou s exp e imen consis ed o lea ning he maximal
ma gin hyp e plane o wo linea ly sepa able classes. We
cons uc ed wo die en linea ly sepa able da ase s (
L
2
and
R
2), shown in gu e 2. Despi e o hei appa en
simplici y, he e is a big die ence b e ween he maximal
ma gin hyp e plane (dashed line) and he minimum sum-
o -squa es hyp e plane (do ed line), used as he ini ial
weigh s o BPW in an MLP wi hou hidden laye s. Solid
lines in gu e 2 show he esul ing hyp e planes a e he
aining o die en alues o
+
. As can b e obse ed,
he maximalma ginhyp e plane was ob ained o
+
=9,
so ha he eec o
+
on he ha dness o he solu ion
ma gin was con med. When lo oking a he ou pu cal-
cula ed by he ne wo k, we could see ha e e y p oin had
510
10
5
510
10
5
Fig. 3.
Sepa a ing hyp e planes when minimizing he weigh ed
sum-o -squa es (8) o
+
= 9 in he h ee-class linea ly sepa-
able p oblems
L
3 (le ) and
R
3 ( igh ).
unc ional ma gin s ic ly g ea e han 1 excep :
Fo
L
2, p oin s
(9
2)
(10
3)
(4
5)
(7
8)
g
.
o
R
2, p oin s
(10
3)
(1
4)
(10
6)
g
.
which had ma gin
1. These p oin s a e, esp ec i ely,
he supp o ec o s o he maximal ma gin hyp e plane o
he da ase s, con ming he p edic ion ab ou he supp o
ec o s jus by lo oking a hei ma gin alue.
B. Th ee linea ly sepa able classes
Ou second exp e imen consis ed o ying o lea n h ee
linea ly sepa able classes. As p e iously,we cons uc ed
wo die en linea ly sepa able da ase s (
L
3and
R
3),
shown in gu e 3. In his case, he cons uc ed MLPs had
h ee ou pu uni s, and BPW minimized (8). In he same
condi ions ha in he p e ious sec ion, solid lines in g-
u e 3 show he esul ing hyp e planes ( he ou pu unc ion
o e e y ou pu uni ) a e he minimiza ion wi h BPW
o
+
=9. Welooked a he ou pu calcula ed by he
ne wo k o e e y p oin in he da ase , in o de o iden-
i y he supp o ec o s. Spli ing he esul ing ne wo k
in o one ne wo k o e e y class, we obse ed ha e e y
ou pu uni o e e y ne wo k, as in he wo linea ly sepa-
able case, had unc ional ma gin s ic ly g ea e han 1
o e e y p oin in he da ase excep
Fo
L
3:
{
(9
3)
(3
3)
(9
7)
g
o he ci cled p oin s class.
{
(9
1)
(5
5)
(7
9)
g
o he c ossed p oin s class.
{
(11
3)
(3
7)
(9
7)
g
o he squa ed p oin s class.
Fo
R
3:
{
(9
3)
(3
3)
(11
6)
g
o he ci cled p oin s class.
{
(9
1)
(5
5)
(5
8)
g
o he c ossed p oin s class.
{
(11
3)
(3
7)
(5
8)
g
o he squa ed p oin s class.
which had ma gin
1. These ec o s a e hose which
would ha e b een ob ained as supp o ec o s i wehad
bina ized he p oblem, sol ing he h ee esp ec i eSVM
op imiza ion p oblems. I con ms ou hyp o hesis ab ou
he go o dness o he mo del o mul iclass p oblems.
0-7803-7278-6/02/$10.00 ©2002 IEEE
Fig. 4.
Gene aliza ion ob ained by SVM-Ligh (le ), BPW
wi h gaussian unc ions (cen e ) and BPW wi h sine unc ions
( igh ) o he
Two Spi als
p oblem. The esul s o BPW a e
he mean o e 10 uns.
C. The
Two Spi als
P oblem
The well known
Two spi als
p oblem consis s o iden i y-
ing he p oin s o woin e lo cking spi als, wi h a aining
se o 194 p oin s. A SVM wi h gaussian ke nels and s an-
da d de ia ion 1 was cons uc ed using he SVM-Ligh
so wa e 5] ( o p olynomial ke nels we did no ob ain sa -
is ac o y esul s). The ha d ma gin solu ion con ained
176 supp o ec o s (0 b ounded). In o de o makea
compa ison wi h an FNN wi h he same ac i a ion unc-
ions and he same equencies, we cons uc ed an RBFN
wi h 194 hidden gaussian uni s (also wi h s anda d de-
ia ion 1). The equencies we e xed o b e he p oin s
in he da ase , and he ini ial ange o he co ecien s
was 0
:
001. As i was a sepa able p oblem wi h gaussian
ke nels, we se
+
= 9. A e 10 uns o a aining wi h
BPW, he mean o he numb e o p oin s wi h unc ional
ma gin less han 1
:
05 (supp o ec o s in ou mo del) was
168. These p oin s we e always a subse o he supp o
ec o s ob ained wi h he SVM-Ligh so wa e. None o
hem had unc ional ma gin less han 0
:
95.
We also cons uc ed an MLP wi h a hidden laye o 24
sinusoidal uni s, as in 10]. Ini ial equencies o BPW
we e assigned andomly o an in e al
;
3
:
5
3
:
5], and he
ini ial ange o he co ecien s was 0
:
0001. We se again
+
= 9. A e 10 uns o a aining wi h BPW, he mean
o he numb e o p oin s wi h unc ional ma gin less han
1
:
05 was 101
:
6, and none o hem had unc ional ma gin
less han 0
:
95. These exp e imen s con m ha he e is
no need o use ei he a SVM a chi ec u e" o ke nel
unc ions ( he sine is no a ke nel unc ion).
The gene aliza ion ob ained by hese mo dels can b e
seen in gu e 4, whe e he co ne s a e (
;
6
:
5
;
6
:
5) and
(+6
:
5
+6
:
5). I is wo h knowing ha all he p oin s in he
aining se a e adially equidis an inside a disk o adius
6
:
5. The e o e, while gaussian unc ions a e exp ec ed o
ha e a good beha iou o his p oblem, i is no so clea
a p io i
o sine unc ions.
VI. Conclusions and Fu u e Wo k
A new lea ning mo del o FNNs ha maximizes he
ma gin has b een p esen ed. The key idea o he mo del is
aweigh ing o he sum-o -squa es e o unc ion, whichis
inspi ed in he AdaBo os algo i hm. The ha dness o he
ma gin can b e con olled by a pa ame e , as in SVMs.
The p op osed mo del allows o deal wi h mul iclass and
mul ilab el p oblems in a na u al way (as FNNs usually
do), and i is no es ic ed o a SVM a chi ec u e" no
o he use o ke nel unc ions, indep enden ly o he con-
c e e aining algo i hm. Bo h heo e ic and exp e imen-
al esul s ha ebeen shown con ming hese ideas.
The weigh ing unc ions p op osed in his wo k a e no
he only ones ha can b e used o weigh he sum-o -
squa es e o unc ion. In his way, he app oachmus
b e es ed in eal wo ld p oblems, and compa ed wi h
b o h FNNs and SVMs. Al hough in his wo k weha e
only conside ed classica ion p oblems, he same idea
can b e applied o eg ession p oblems, jus bychang-
ing he condi ion o he weigh ing unc ion (4) om
m g
(
x
i
y
i
FNN
)
>
0 o
j
FNN
(
x
i
)
;
y
i
j
6
"
, whe e
"
is a new pa ame e ha con ols he esolu ion a which
wewan o lo ok a he da a. This idea is simila o he
"
;
insensi i e cos unc ion p op osed in 13].
Re e ences
1] Bishop, C.M. (1995).
Neu al Ne wo ks o Pa e n Recogni-
ion
. Ox o d Uni e si y P ess Inc., New Yo k.
2] C is ianini, N and Shawe-Taylo , J. (2000).
An In oduc ion o
Suppo Vec o Machines
.Camb idge Uni e si y P ess, UK.
3] F eund, Y. and Schapi e, R.E. (1997). A decision- heo e ic
gene aliza ion o on-line lea ning and an applica ion o b o os -
ing.
Jou nal o Compu e and Sys em Sciences
55 (1), 119-139.
4] Gi osi, F. (1998). An Equi alence Be ween Spa se App oxima-
ion and Supp o Vec o Machines.
Neu al Compu a ion
10,
1455-1480.
5] Joachims, T. (1999) Making la ge-Scale SVM Lea ning P ac i-
cal. In
Ad ances in Ke nel Me hods - Suppo Vec o Lea ning
,
B. Scholkop and C. Bu ges and A. Smola (Ed.), MIT-P ess.
6] Leshno, M., Lin, V.Y., Pinkus, A and Scho cken, S. (1993).
Mul ilaye Feed o wa d Ne wo ks Wi h a Nonp olynomial Ac i-
a ion Func ion Can App oxima e AnyFunc ion.
Neu al Ne -
wo ks
6, 861-867.
7] Pa k, J. and Sandb e g, I.W. (1993). App oxima ion and
Radial-Basis-Func ion Ne wo ks.
Neu al Compu a ion
5 (2),
305-316.
8] Raudys, S. (1998). E olu ion and gene aliza ion o a single
neu on: I. Single-laye p e cep on as se en s a is ical classi-
e s.
Neu al Ne wo ks
11, 283-296.
9] Rumelha , D.E., Hin on, G.E. and Williams, R.J. (1986).
Pa al lel Dis ibu edP ocessing
,Vol 1. MIT P ess.
10] Sop ena, J.M., Rome o, E. and Alqueza , R. (1999). Neu al
Ne wo ks wi h Pe io dic and Mono onic Ac i a ion Func ions:
A Compa a i e S udy in Classica ion P oblems.
P oc. 9 h
In . Con . A icial Neu al Ne wo ks
, 323-328.
11] Schapi e, R.E. and Singe , Y. (1999). Imp o ed Bo os ing Algo-
i hms Using Condence- a ed P edic ions.
Machine Lea ning
17 (3), 297-336.
12] Suykens, J.A.K and Vandewalle, J. (1999). T aning Mul ilaye
P ecep on Classie s Based on a Mo died Supp o Vec o
Me ho d.
IEEE T ans. on Neu al Ne wo ks
10 (4), 907-911.
13] Vapnik, V. (1995).
The Na u e o s a is ical lea ning heo y
.
Sp inge -Ve lag, New Yo k.
14] Vapnik, V. (1998). The Supp o Vec o Me ho d o Func ion
Es ima ion. In C. Bishop (Ed.),
Neu al Ne wo ks and Machine
Lea ning
, 239-268, Sp inge -Ve lag, Be lin.
15] Vincen , P. and Bengio, Y. (2000). A Neu al Supp o Vec o
A chi ec u e wi h Adap i e Ke nels.
In . Join Con e enceon
Neu al Ne wo ks
5, 187-192.