Digital Signal Processing Reference
In-Depth Information
Fig. 7.3
Example of an
optimal hyper plane
H
∗
(w,
b
)
(
lighter shaded
) in two dimen-
sional space with maximum
margin of separation
x
2
μ
∗
(
dashed parallel lines
). “x”
and “o” indicate exemplary
instances of the two classes to
be separated
w
*
μ
*>
μ
μ
*>
μ
b*
H*(
w
*,b*)
x
1
w
∗
.From(
7.8
) result linear side conditions for the
posseses a unique minimum
optimisation:
T
x
l
+
y
l
(w
b
)
−
1
≥
0 with
l
=
1
,...,
L
.
(7.12)
To solve this boundary value problem one can use Langrange multipliers. In [
6
]
this is explained in detail.
In the general, non-trivial case, there does not exist—as opposed to the previously
made assumption—a hyper plane to separate a training instances set
flawlessly. In
this case the equations in (
7.8
) are extended by so called slack variables
L
ξ
l
≥
0
,
l
=
1
L
. This allows to stay with the approach, as vectors which cross the hyper
plane may be placed on the 'wrong side':
,...,
T
x
l
+
y
l
=+
1
⇒
w
b
≥+
1
−
ξ
l
,
T
x
l
+
y
l
=−
1
⇒
w
b
≤−
1
+
ξ
l
.
(7.13)
By that, the expression
L
1
2
w
T
w
+
·
1
ξ
l
G
(7.14)
l
=
needs to be minimised, where
G
is a free error weighting factor that needs to be
determined. It can be shown that this optimisation—also called a 'primal problem'—
is equivalent to a 'dual problem' of the maximisation of
L
L
L
1
2
x
k
x
l
),
a
l
−
a
k
a
l
y
k
y
l
(
(7.15)
l
=
1
k
=
1
l
=
1
