Databases Reference
In-Depth Information
where
α
i
are the Lagrange multipliers,
α
=
α
1
,
α
2
,
...,α
N
, subject to in-
equality constraints:
α
i
≥
i
, and linear equality constraint:
i
=1
y
i
α
i
=0.
By solving the dual optimization problem, one obtains the coe
cients
α
i
,
i
=1
,...,N
, from which the normal vector
w
and the threshold b can be
derived [22].
To deal with non-linearly separable data in feature space, Cortes and Vap-
nik [6] introduced slack-variables to relax the hard-margin constraints. The
modification is:
0
,
∀
N
min
1
2
||w
2
+C
||
ξ
i
(4)
i=1
subject to
y
i
(
w
·x
i
+
b
)
i
,where
ξ
i
is slack variable that allows margin
failure and constant
C>
0 determines the trade-off between the empirical
error and the complexity term. This leads to dual quadratic problem involving
[3] subject to the constraints
C
≥
1
−
ξ
i
,
∀
i
and
i
=1
y
i
α
i
=0.
To solve the dual quadratic problem, we apply sequential minimal opti-
mization [22] which is a very e
cient algorithm for training SVMs.
≥
α
i
≥
0
,
∀
3.3 Sequential Minimal Optimization
Sequential Minimal Optimization (SMO) [22] is a simple algorithm that can
e
ciently solve the SVM quadratic optimization (QO) problem. Instead of di-
rectly tackle the QO problem, it decomposes the overall QO problem into QO
sub-problems based on Osunna's convergence theorem [20]. At each step, SMO
chooses two Lagarange multipliers to jointly optimize, find the optimal values
for these multipliers, and updates the SVM to reflect the new optimal values.
In order to solve for the two Lagrange multipliers, SMO firstly computes
the constraints on these multipliers and then solves for the constrained mini-
mum. Normally, the objective function is positive definite, SMO computes the
minimum along the direction of the linear constraints
i
=1
y
i
α
i
= 0 within
the boundary
C
≥
α
i
≥
0
,i
=1
,
2.
α
new
2
=
α
2
+y
2
(E
1
−
E
2
)
η,
(5)
where
E
i
=
y
i
α
i
K
(
x
i
,
x
)
y
i
is the error on the
i
th training example,
x
i
is the stored training vector and
x
is the input vector, and
η
is the second
derivative of [3] along the direction of the above linear constraints:
−
η
=
K
(
x
1
,x
1
)+
K
(
x
2
,x
2
)
2
K
(
x
1
,x
2
)
.
−
(6)
Next step, the constrained minimum is found by clipping the unconstrained
minimum to the ends of the line segment:
α
new,clipped
2
is equal to
H
if
α
new
2
≥
<H
, and is equal to
α
new,clipped
2
H
,isequalto
α
new
2
if
L<α
new
2
=
L
if
α
new
2
≤
L
. If the target
y
1
is not equal to the target
y
2
,
L
= max(0
,α
2
−
α
1
),
