Description
Problem 1
Considering soft margin SVM, where we have the objective and constraints as follows:
min
1
2
||w||2
2 + C
Xm
i=1
ξi
s.t. yi(w
T xi+b) ≥ 1 − ξi (i = 1, 2, …m)
ξi ≥0 (i = 1, 2, …m)
(1)
Now we formulate another formulation as:
min
1
2
||w||2
2 +
C
2
Xm
i=1
ξ
2
i
s.t. yi(w
T xi+b) ≥ 1 − ξi (i = 1, 2, …m)
(2)
1. Different from Eq. (1), we now drop the non-negative constraint for ξi
, please show that
optimal value of the objective will be the same when ξi constraint is removed.
2. What’s the generalized Lagrangian of the new soft margin SVM optimization problem?
3. Now please minimize the Lagrangian with respect to w, b, and ξ.
4. What is the dual of this version soft margin SVM optimization problem? (should be similar
to Eq. (10) in the slides)
5. Please analysis bias-variance trade-off when C increases.
Problem 2
Recall vanilla SVM objective:
L(w, b, α) = 1
2
||w||2
2 −
Xm
i=1
αi
[yi(w
T xi + b) − 1] s.t. αi ≥ 0 (3)
If we denote the margin as γ, and vector α = [α1, α2, . . . , αm], now please show γ
2 ∗ kαk1 = 1.