## Description

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 2

You are given a training data set consisting of 2 data points, in a 2-class problem. In

the expanded feature space, the data points 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 data 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.)

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