1
'
+
=
w
x
O
O
O
O
O
O
O
O
w
2
=
1
'
-
=
w
x
Margin
A+
A-
O
O
O
O O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
O
X
O
O
X
X
X
=
w
x'
Separating Plane
w
X
(a) Standard SVM
classifier
1
'
+
=
w
x
O
O
O
O
O
O
O
O
=
w
2
1
'
-
=
w
x
Margin
A+
A-
O
O
O
O O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
O
X
O
O
X
X
X
0
'
=
-
w
x
Separating Plane
w
X
(b)
Proximal
SVM
classifier
Fig. 1. SVM and PSVM
min
(w,,y)R
n+1+m
{ve y +
1
2
w w}
s.t. D(Aw - e) + y e
y 0
(1)
A R
m×n
, D {-1, +1}
m×1
, e = 1
m×1
Fung and Mangasarian [5] replaced the inequality constraint in (1) with an
equality constraint. This changed the binary classification problem, because the
points in Fig. 1(b) are no longer bounded by the planes, but are clustered around
them. By solving the equation for y and inserting the result into the expression
to be minimized, one gets the following unconstrained optimization problem:
min
(w,)R
n+1+m
f (w, ) =
2
D(Aw - e) - e
2
+
1
2
(w w +
2
)
(2)
Setting
f =
f
w
,
f
= 0 one gets:
w
X
=
A A +
I
-A e
-e A
1
+ m
-1
A De
-e De
=
I
+ E E
-1
A
-1
E De
B
(3)
E = [A - e], E R
m×(n+1)
Fung and Mangasarian [6] later showed that (3) can be rewritten to handle
increments (E
i
, d
i
) and decrements (E
d
, d
d
), as shown in (4). This decremental
approach is based on time windows.
Paper F
109