Thursday, December 23, 2010

stanford machine learning course - lecture#7

My takeaways from 7th lecture of stanford machine learning course.

This lecture starts with defining optimal margin classifier that works by maximizing the (geometric)margin. This basically defines an optimization problem. Then we transform it into a convex optimization problem so that it could be solved using an out of the box quadratic problem(a type of convex optimization problem) solver. [It is good to follow 2 handouts, given as course material, on convex optimization if you have never studied it.]
Then, the lecture introduces essential material from convex optimization theory, mainly the lagrangian and primal, dual problems and KKT conditions when solution to primal and dual problems become same. Usually dual problem is easier to solve, So if a problem satisfies KKT conditions then we can just solve dual problem to find solution to primal problem also.
After that we get back to optimal margin classifier optimization problem and convert it into a dual problem. Solving which we see an interesting property that for any x, output variable y can be evaluated by only calculating inner product of x with a handful of input variables from training set. Because of this property, this algorithm scales really well to solve classification problems. And, this property is what makes support vector machine to efficiently learn in very high dimensional spaces.

No comments:

Post a Comment