DOC PREVIEW
UT Dallas CS 6375 - SVM-Example2-solutions

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

SVM-Example2-solutionsQuestion 1The training data for an SVM consists of 5 points: (x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5), where: y1=−1, y2= 1, y3= −1, y4= 1, y5= 1. The values of the feature vectors (x1, . . . , x5) are not known explicitlybut their Gram matrix is known:G =9 0 −3 0 00 0 0 0 0−3 0 1 0 00 0 0 4 −20 0 0 −2 1(Element i, j of the Gram matrix is the dot product of xiand xj.) Let α1, . . . , α5be the Lagrange multipliersassociated with this data. (αiis associated with (xi, yi).)Part Aa.Using the linear kernel, what (dual) optimization problem needs to be solved in terms of the αiin order todetermine their values?AnswerMaximizeL(α1, α2, α3, α4, α5) = α1+ α2+ α3+ α4+ α5−12(9α21− 6α1α3+ α23+ 4α24− 4α4α5+ α25)Subject to:−α1+ α2− α3+ α4+ α5= 0α1≥ 0, α2≥ 0, α3≥ 0, α4≥ 0, α5≥ 0,b.Using the polynomial kernel of order 2 , and soft margins specified by the parameter C = 10, what (dual)optimization problem needs to be solved in terms of the αiin order to determine their values?AnswerThe Gram matrix:100 1 4 1 11 1 1 1 14 1 4 1 11 1 1 25 11 1 1 1 4MaximizeL(α1, α2, α3, α4, α5) = α1+ α2+ α3+ α4+ α5−12(100α21− 2α1α2+ 8α1α3− 2α1α4− 2α1α5+ α22− 2α2α3+ 2α2α4+ 2α2α5+ 4α23− 2α3α4− 2α3α5+ 25α24+ 2α4α5+ 4α25)Subject to:− α1+ α2− α3+ α4+ α5= 00 ≤ α1≤ 10, 0 ≤ α2≤ 10, 0 ≤ α3≤ 10, 0 ≤ α4≤ 10, 0 ≤ α5≤ 10Part BThe table below shows the results obtained for the 4 cases involving linear and second order polynomialkernels, with two different values of C.Case kernel C α1α2α3α4α51 linear ∞ 6.6 · 1079.4 · 1072.0 · 1085.6 · 1071.1 · 1082 2nd order polynomial ∞ 0 0.666 0.666 0 03 linear 10 3.6 4.8 10 2.9 5.84 2nd order polynomial 10 0 0.666 0.666 0 0a.Select one of these cases and show that the SVM correctly classifies the entire training data. Show andexplain your computations.AnswerI am using Case 2 or 4. From the first support vector (x2, y2):b =11− (0.66 · 1 · 1 + 0.66 · (−1) · 1) = 1For Point 1: 1 + (0.666 · 1 · 1 + 0.666 · (−1) · 4) < 0For Point 2: 1 + (0.666 · 1 · 1 + 0.666 · (−1) · 1) > 0For Point 3: 1 + (0.666 · 1 · 1 + 0.666 · (−1) · 4) < 0For Point 4: 1 + (0.666 · 1 · 1 + 0.666 · (−1) · 1) > 0For Point 5: 1 + (0.666 · 1 · 1 + 0.666 · (−1) · 1) > 0b.Select one of these cases and show that the SVM does not correctly classify the entire training data. Showand explain your computations.AnswerFor Case 1 the answer is not clean. It should probably not be used since the values of the alphas may beinfinity.For Case 3 the answer is clean. The second support vector (x2, y2) is on a hard margin. Its dot productwith all vectors is 0. Therefore:b =11− (0 + 0 + 0 + 0 + 0) = 1Point 3 is on a soft margin, and therefore, may not be correctly classified.For Point 3: 1 + (3.6 · 1 · (−3) + 10 · 1 · 1) >


View Full Document

UT Dallas CS 6375 - SVM-Example2-solutions

Documents in this Course
ensemble

ensemble

17 pages

em

em

17 pages

dtree

dtree

41 pages

cv

cv

9 pages

bayes

bayes

19 pages

vc

vc

24 pages

svm-2

svm-2

16 pages

svm-1

svm-1

18 pages

rl

rl

18 pages

mle

mle

16 pages

mdp

mdp

19 pages

knn

knn

11 pages

intro

intro

19 pages

hmm-train

hmm-train

26 pages

hmm

hmm

28 pages

hmm-train

hmm-train

26 pages

hmm

hmm

28 pages

ensemble

ensemble

17 pages

em

em

17 pages

dtree

dtree

41 pages

cv

cv

9 pages

bayes

bayes

19 pages

vc

vc

24 pages

svm-2

svm-2

16 pages

svm-1

svm-1

18 pages

rl

rl

18 pages

mle

mle

16 pages

mdp

mdp

19 pages

knn

knn

11 pages

intro

intro

19 pages

vc

vc

24 pages

svm-2

svm-2

16 pages

svm-1

svm-1

18 pages

rl

rl

18 pages

mle

mle

16 pages

mdp

mdp

19 pages

knn

knn

11 pages

intro

intro

19 pages

hmm-train

hmm-train

26 pages

hmm

hmm

28 pages

ensemble

ensemble

17 pages

em

em

17 pages

dtree

dtree

41 pages

cv

cv

9 pages

bayes

bayes

19 pages

vc

vc

24 pages

svm-2

svm-2

16 pages

svm-1

svm-1

18 pages

rl

rl

18 pages

mle

mle

16 pages

mdp

mdp

19 pages

knn

knn

11 pages

intro

intro

19 pages

hmm-train

hmm-train

26 pages

hmm

hmm

28 pages

ensemble

ensemble

17 pages

em

em

17 pages

dtree

dtree

41 pages

cv

cv

9 pages

bayes

bayes

19 pages

hw2

hw2

2 pages

hw1

hw1

4 pages

hw0

hw0

2 pages

hw5

hw5

2 pages

hw3

hw3

3 pages

20.mdp

20.mdp

19 pages

19.em

19.em

17 pages

16.svm-2

16.svm-2

16 pages

15.svm-1

15.svm-1

18 pages

14.vc

14.vc

24 pages

9.hmm

9.hmm

28 pages

5.mle

5.mle

16 pages

3.bayes

3.bayes

19 pages

2.dtree

2.dtree

41 pages

1.intro

1.intro

19 pages

21.rl

21.rl

18 pages

CNF-DNF

CNF-DNF

2 pages

ID3

ID3

4 pages

mlHw6

mlHw6

3 pages

MLHW3

MLHW3

4 pages

MLHW4

MLHW4

3 pages

ML-HW2

ML-HW2

3 pages

vcdimCMU

vcdimCMU

20 pages

hw0

hw0

2 pages

hw3

hw3

3 pages

hw2

hw2

2 pages

hw1

hw1

4 pages

9.hmm

9.hmm

28 pages

5.mle

5.mle

16 pages

3.bayes

3.bayes

19 pages

2.dtree

2.dtree

41 pages

1.intro

1.intro

19 pages

15.svm-1

15.svm-1

18 pages

14.vc

14.vc

24 pages

hw2

hw2

2 pages

hw1

hw1

4 pages

hw0

hw0

2 pages

hw3

hw3

3 pages

9.hmm

9.hmm

28 pages

5.mle

5.mle

16 pages

3.bayes

3.bayes

19 pages

2.dtree

2.dtree

41 pages

1.intro

1.intro

19 pages

Load more
Download SVM-Example2-solutions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view SVM-Example2-solutions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view SVM-Example2-solutions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?