140
5: Mahesh Pal, Pakorn Watanachaturaporn
inequalities in (5.8) and (5.9) can be combined into a single inequality as
Yi (w . Xi + b) - 1 ~ 0 .
(5.10)
The decision rule for the linearly separable case can be defined by a set of
classifiers (or decision functions) as
fw,b = sign (w . X + b) ,
(5.11)
where sign(·) is the signum function. It returns + 1 if the element is greater
than or equal to zero, and returns -1 if it is less than zero.
The distance D(x; w, b), or margin of separation or margin, for a point x
from the hyperplane defined by both wand b is given by
Iw·x+bl
D (x;w,b) =
,
Ilwllz
(5.12)
where 1·1 is the absolute function, and 11·llz is the 2-norm.
Let y be the value of the margin between two separating planes. To maximize
the margin, we express the value of y as
w·x+b+l
y=
Ilwllz
w·x+b-1
Ilwllz
2
Ilwllz
(5.l3)
The maximization of (5.13) is equivalent to the minimization of the 2-norm
Ilwllz /2. Thus, the objective function
The scale factor 1/2 is used for computational convenience only.
(5.14)
A constrained optimization problem can be constructed with the goal to
minimize the objective function in (5.14) under the constraints given in (5.10).
This constrained optimization problem is called a primal problem that has two
properties; the objective function is a convex function of wand the constraints
are linear.
Equation (5.14) can be solved using standard Quadratic Programming (QP)
optimization techniques. The QP optimization technique to solve (5.14) under
the constraints in (5.10) can be implemented by replacing the inequalities in
a simpler form by transforming the problem into a dual space representation
using Lagrange multipliers (Leunberger 1984). The method of Lagrange multipliers transforms the primal problem to its corresponding dual problem. The
primal Lagrangian is given by
k
k
L (w, b,A) = ~ IIwl12 - LAiYi (w. Xi + b) + LAi ,
i=l
i=l
(5.15)
where Ai ~ 0 are the unknown Lagrange multipliers.
5: Mahesh Pal, Pakorn Watanachaturaporn
inequalities in (5.8) and (5.9) can be combined into a single inequality as
Yi (w . Xi + b) - 1 ~ 0 .
(5.10)
The decision rule for the linearly separable case can be defined by a set of
classifiers (or decision functions) as
fw,b = sign (w . X + b) ,
(5.11)
where sign(·) is the signum function. It returns + 1 if the element is greater
than or equal to zero, and returns -1 if it is less than zero.
The distance D(x; w, b), or margin of separation or margin, for a point x
from the hyperplane defined by both wand b is given by
Iw·x+bl
D (x;w,b) =
,
Ilwllz
(5.12)
where 1·1 is the absolute function, and 11·llz is the 2-norm.
Let y be the value of the margin between two separating planes. To maximize
the margin, we express the value of y as
w·x+b+l
y=
Ilwllz
w·x+b-1
Ilwllz
2
Ilwllz
(5.l3)
The maximization of (5.13) is equivalent to the minimization of the 2-norm
Ilwllz /2. Thus, the objective function
The scale factor 1/2 is used for computational convenience only.
(5.14)
A constrained optimization problem can be constructed with the goal to
minimize the objective function in (5.14) under the constraints given in (5.10).
This constrained optimization problem is called a primal problem that has two
properties; the objective function is a convex function of wand the constraints
are linear.
Equation (5.14) can be solved using standard Quadratic Programming (QP)
optimization techniques. The QP optimization technique to solve (5.14) under
the constraints in (5.10) can be implemented by replacing the inequalities in
a simpler form by transforming the problem into a dual space representation
using Lagrange multipliers (Leunberger 1984). The method of Lagrange multipliers transforms the primal problem to its corresponding dual problem. The
primal Lagrangian is given by
k
k
L (w, b,A) = ~ IIwl12 - LAiYi (w. Xi + b) + LAi ,
i=l
i=l
(5.15)
where Ai ~ 0 are the unknown Lagrange multipliers.