$30
p. 1 of 3
EE 559 Homework 9
1. In the parts below, you will set up the primal Lagrangian and derive the dual
Lagrangian, for support vector machine classifier, for the case of data that is
separable in expanded feature space.
For the SVM learning, we stated the optimization problem for the linearly separable
(in -space) case, as:
Assume our data is linearly separable in the expanded feature space. Also,
nonaugmented notation is used throughout this problem.
(a) If the above set of constraints (second line of equations above) is satisfied, will all
the training data be correctly classified?
(b) Write the Lagrangian function for the minimization problem stated
above. Use for the Lagrange multipliers. Also state the KKT
conditions. (Hint: there are 3 KKT conditions).
(c) Derive the dual Lagrangian , by proceeding as follows:
(i) Minimize w.r.t. the weights.
Hint: solve for the optimal weight (in terms of and other
variables); and set and simplify.
(ii) Substitute your expressions from part (i) into , and use your expression from
as a new constraint, to derive as:
subject to the (new) constraint: . Also give the other two KKT
conditions on , which carry over from the primal form.
2. In this problem you will do SVM learning on 2 data points, using the result from
Problem 1 above.
u
Minimize J (w) = 1
2 w
2
s.t. zi w
T
ui + w ( 0 ) −1 ≥ 0 ∀i
L w,w0 ( ,λ)
λi
, i = 1, 2,!, N
LD
L
∇wL = 0 w* λi
∂L
∂w0
= 0
L
∂L
∂w0
= 0 LD
LD (λ) = − 1
2 λi
λ j
zi
zj
ui
T
u j
j=1
N
∑
i=1
N
∑
⎡
⎣
⎢
⎢
⎤
⎦
⎥
⎥
+ λi
i=1
N
∑
λi
zi
i=1
N
∑ = 0
λi
p. 2 of 3
You are given a training data set consisting of 2 samples, in a 2-class problem. In
the expanded feature space, the samples are:
(a) Solve, by hand, for the SVM decision boundary and regions. To do this, use
Lagrangian techniques to optimize w.r.t. subject to its equality constraint
, in order to find the optimal weight vector , and also find the optimal
. Plot the training samples and the decision boundary in 2D (nonaugmented) uspace, and show which side of the boundary is positive ( ).
Hints: Start from:
in which the last term has been added to incorporate the equality constraint stated
above. Once finished, then check that the resulting satisfies the KKT conditions
on that you stated in Problem 1(c)(ii); one of these can also help you find .
(b) Use the data points and solution you found in part (a), and call its solution decision
boundary . Calculate in 2D space the distance between and , and the
distance between and . Is there any other possible linear boundary in
space that would give larger values for both distances (“margins”) than gives?
(No proof required.)
3. In this problem you will derive the dual Lagrangian for the case of data that is not
linearly separable in -space. From class, the optimization problem can be stated
as:
Tip: Write clearly so that and are always distinguishable.
u1 = −1
0
⎡
⎣
⎢ ⎤
⎦
⎥ ∈ S1; u2 = 0
1
⎡
⎣
⎢ ⎤
⎦
⎥ ∈ S2 .
LD λ
λi
zi
i=1
N
∑ = 0 w*
w0
Γ1
LD′(λ,µ) = λi
i=1
N
∑ − 1
2 λiλ jzizjui
T
u j
j=1
N
∑
i=1
N
∑
⎡
⎣
⎢
⎢
⎤
⎦
⎥
⎥
+ µ ziλi
i=1
N
∑
⎛
⎝
⎜
⎞
⎠
⎟
λ
λ w0
*
H u − u1 H
u2 H u −
H
u
Minimize J (w) = 1
2 w
2
+ C ξi
i=1
N
∑
s.t. zi w
T
ui + w ( 0 ) ≥ 1− ξi ∀i
ξi ≥ 0 ∀i
µi ui
p. 3 of 3
(a) Write the Lagrangian function for the minimization problem stated
above. Use for the Lagrange multipliers relating to the first set of
constraints, and use for the Lagrange multipliers relating to the
second set of constraints State the KKT conditions. Hint: there are 6 KKT
conditions: 4 sets of restrictions on the and , and the 2 given sets of constraints.
(b) Derive the dual Lagrangian , by minimizing w.r.t. , , and , and give
the formula for . Also list the restrictions and constraints on the Lagrange
multipliers ( and ): there are 5 sets of them.
Hints:
(1) Procedure is similar to the separable-data case.
(2) Each can be treated as another independent variable, so that .
(3) To minimize L w.r.t. , set . This gives an equation that can be
combined with restrictions on and to yield a revised restriction on .
L w,w0 ( ,ξ, λ,µ)
λi
, i = 1, 2,!, N
µi
, i = 1, 2,!, N
λi ui
LD L w w0 ξ
w*
λ µ
ξi
∂ξi
∂w = 0
ξ δ L
δξi
= 0
µi λi λi