Information Technology Reference
In-Depth Information
D
=
y
y
x
•
x
(8.28)
ij
i
j
i
j
This fact follows from the classical Karush-Kuhn-Tucker (KKT) theorem,
according to which necessary and sufficient conditions for the optimal
hyperplane are that the separating hyperplane satisfy the conditions:
1
?
α
{
y
(
w
•
x
+
b
)
−
1
=
0
i
=
2
,
l
(8.29)
i
i
According to equality (8.25), only these samples satisfying
ŋ
i
>0 determine
classification result while those samples satisfying
ŋ
i
=0 do not. We will call
these samples satisfying
ŋ
i
>0 support vectors.
We train samples to attain vectors
ŋ
* and
w
*. Selecting a support vectors
sample
x
i
, we attain
b
* by the following equality:
*
b
=
y
−
w
•
x
(8.30)
i
i
For a test sample
x
, calculate the following equality
l
Ã
=
*
d
(
x
)
=
x
•
w
*
+
b
*
=
y
α
(
x
•
x
)
+
b
*
(8.31)
i
i
i
i
1
According to the sign of
d
(
x
) to determine which class
x
belongs to.
8.4.2
Linearly non-separable case
In linearly separable case, decision function is constructed on the basis of Euclid
distance, i.e.
T
K x
(
,
x
)
=
x
•
x
=
x
x
. In linearly non-separable case, SVM
i
j
i
j
i
j
maps the input vectors
through some
nonlinear mapping (see Figure 8.5). In this space, an optimal separating
hyperplane is constructed. The nonlinear mapping
x
into a high-dimensional feature space
H
d
Φ
:
R
→
H
:
T
x
→
Φ
(
x
)
=
(
φ
(
x
),
φ
(
x
),
?
φ
,
,
?
)
(8.32)
1
2
i
(
x
)
where, φ
i
(
) is a real function.
Feature vector Φ(
x
x
) substitutes input vector
x
, equality (8.28) and (8.31) are
transformed as follows:
D
=
y
y
Φ
(
x
)
•
Φ
(
x
)
(8.33)
ij
i
j
i
j
l
Ã
=
*
*
*
d
(
x
)
=
Φ
(
x
)
•
w
+
b
=
α
y
Φ
(
x
)
•
Φ
(
x
)
+
b
(8.34)
i
i
i
i
1
