Information Technology Reference
In-Depth Information
Eq. (
6.7
)asfollows:
X
T
Y
ʲ
−
1
n
(
ʱ
,
ʲ
)
=
1
ʱ
t
,
T
YXX
T
Y
ʱ
+
b
t
:
argmin
ʱ
P
1
2
ʱ
ʱ
(6.8)
s.t.
√
y
T
C
√
ʻ
ʻ
ʱ
=
0
,
0
n
≤
ʱ
≤
1
n
,
where the bias
b
t
is derived analogously to the conventional L2-SVM approach. As
a matter of fact, Eq. (
6.8
) is a simple reformulation of the conventional dual formu-
lation of L2-SVM, which can be solved by exploiting any of the several approaches
proposed in the last decades (Shawe-Taylor and Sun
2011
). If, instead, we fix
ʱ
to some constant value
ʱ
, which also satisfies the constrains, we can reformulate
Eq. (
6.7
) in the following manner:
T
YX
ʲ
t
1
T
I
ʲ
+
:
argmin
ʲ
P
2
(
ʲ
,
ʱ
)
=
2
ʲ
ʱ
ʲ
(6.9)
−
(
1
−
ʻ)
1
d
≤
ʲ
≤
(
1
−
ʻ)
s.t.
1
d
.
√
√
ʻ
ʻ
Equation (
6.9
) has a closed form solution, as we have to identify the minimum of
a paraboloid in a box, which is characterized by an identity Hessian matrix:
max
min
(
T
YX
T
−
(
1
−
ʻ)
√
1
−
ʻ)
√
ʲ
t
=
1
d
,
1
d
,
ʱ
.
(6.10)
ʻ
ʻ
Consequently, we propose an approach to solve Eq. (
6.7
) which is detailed in
Algorithm 1. For this, solutions of Eqs. (
6.8
) and (
6.9
) are iteratively found. The
former case can therefore be solved with any of the methods surveyed by (Shawe-
Taylor and Sun
2011
).
Particularly, we have also described Algorithm 2 which is focused on the adoption
of the SMO algorithm (Platt
1998
;Keerthietal.
2001
) for solving Eq. (
6.8
). Note
that, since, at every optimization step, two
ʱ
i
coefficients are optimized by the SMO,
in order to better balance the overall L1-L2 optimization procedure we can run
2
iterations of SMO and, then, update
ʲ
i
∈{
1
,...,
d
}
.
Algorithm 1
: Algorithm for solving Problem (6.7)
Data
:
D
n
,
ʻ
,
C
,
ʵ
and numerical precision
w
∗
,
b
∗
Result
:
t
=
0,
ʱ
t
=
0
n
,
ʲ
t
=
0
d
;
repeat
ʱ
t
+
1
,
b
t
+
1
=
argmin
ʱ
P
1
(
ʱ
,
ʲ
t
)
;
max
min
(
1
−
ʻ)
1
YX
T
;
,
ʱ
−
(
1
−
ʻ)
t
ʲ
t
+
1
=
1
d
,
1
d
√
ʻ
√
ʻ
+
t=t+1;
until
;
ʲ
t
−
ʲ
t
−
1
2
2
2
ʱ
t
−
ʱ
t
−
1
+
<
√
ʻ
ʻ
X
T
Y
ʱ
t
+
ʲ
t
,b
w
∗
=
return
=
b
t
Search WWH ::
Custom Search