# Princeton COS 424 - Homework #3 (4 pages)

Previewing page*1*of 4 page document

**View the full content.**## Homework #3

Previewing page *1*
of
actual document.

**View the full content.**View Full Document

## Homework #3

0 0 146 views

Problems/Exams

- Pages:
- 4
- School:
- Princeton University
- Course:
- Cos 424 - Computer Graphics

**Unformatted text preview: **

COS424 Homework 3 Due Tuesday April 3 2007 See the course website for important information about collaboration late policies grading policies as well as where and when to turn in assignments Problem 1 Consider the Gaussian kernel a k a Gaussian radial basis function kernel given by Kc x z exp c x z where x and z are points in Rn and c is a positive constant This problem considers how SVM s behave with this kernel as c becomes large Note There is an important difference between the way that SVM s were presented in class and the way they are presented in the reading that was posted on line In class we assumed that the hyperplane we are seeking must pass through the origin In the reading on the other hand the hyperplane is not required to pass through the origin This makes the math slightly more complicated For this problem you should follow the development that was given in class a For fixed x and z let us define K x z lim Kc x z c to be the limit of Kc x z as c becomes very large As a function of x and z what is the value of K x z b Consider a fixed training set x1 y1 xm ym You can assume that all of the xi s are distinct In the limit as c becomes extremely large what happens to the Lagrange multipliers i computed by SVM s Although there are some technical issues that we are ignoring you can assume that it is okay to answer this question by computing the Lagrange multipliers that would be found if we simply used the kernel K defined in the last part c Suppose that c is finite but sufficiently large that we are close to the limiting behavior determined in the last parts of this problem How will the classifier found by SVM s using this Gaussian kernel classify a new test point x How do these predictions relate to the nearest neighbor algorithm Problem 2 Prove that the k means algorithm will terminate after a finite number of steps Hint recall that k means is a coordinate descent algorithm 1 Problem 3 Y Z X X Y Z Y 1 2 X Z 3 For the three graphical models above

View Full Document