LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 8 (http://book.caltech.edu/bookforum/forumdisplay.php?f=137)
-   -   Q1 Quadratic Programming (http://book.caltech.edu/bookforum/showthread.php?t=4305)

 alasdairj 05-22-2013 04:28 AM

Q1 Quadratic Programming

From that well known source, wikipedia:

Quadratic programming (QP) is a special type of mathematical optimization problem. It is the problem of optimizing (minimizing or maximizing) a quadratic function of several variables subject to linear constraints on these variables.

The hard-margin SVM problem is to minimize 0.5w'w subject to (yn(w'xn + b) >= 1.

So is this a quadratic programming problem?

 Elroch 05-22-2013 04:48 AM

Re: Q1 Quadratic Programming

A quadratic function of a set of variables is a linear combination of constants and products of one or two of the variables (including squares of them).

A linear constraint is an inequality which only contains a linear combination of constants and individual variables.

How do these relate to your description of the hard margin SVM problem? (The variables are the components of )

 alasdairj 05-22-2013 07:34 AM

Re: Q1 Quadratic Programming

Well, the problem was to minimize wrt w and b the value w'w (which is a combination of 2 values of our variable) subject to yn(w'xn + b) >= 1 where yn and xn are constants (our training data) i.e. a linear combination of our variable w.

So, the original problem for hard-margin SVM seems like a "quadratic programming" problem - so my real question is this: why do we do the "dual" mapping to get the problem stated in terms of alpha? Is this purely to get it into a more convenient form for QP packages? I am missing something, but I don't know what :-).

 Elroch 05-22-2013 09:01 AM

Re: Q1 Quadratic Programming

Quote:
 Originally Posted by alasdairj (Post 10914) Well, the problem was to minimize wrt w and b the value w'w (which is a combination of 2 values of our variable) subject to yn(w'xn + b) >= 1 where yn and xn are constants (our training data) i.e. a linear combination of our variable w. So, the original problem for hard-margin SVM seems like a "quadratic programming" problem - so my real question is this: why do we do the "dual" mapping to get the problem stated in terms of alpha? Is this purely to get it into a more convenient form for QP packages? I am missing something, but I don't know what :-).
If I understand correctly, the motivation is that it is often computationally efficient to do so.

 yaser 05-22-2013 12:48 PM

Re: Q1 Quadratic Programming

Quote:
 Originally Posted by alasdairj (Post 10914) the original problem for hard-margin SVM seems like a "quadratic programming" problem - so my real question is this: why do we do the "dual" mapping to get the problem stated in terms of alpha? Is this purely to get it into a more convenient form for QP packages? I am missing something, but I don't know what :-).
The number of variables in the original problem depends on the dimensionality of the weight space, whereas the number of variables in the dual problem does not. This makes a difference if that dimensionality is high, which is often the case in nonlinear transforms.

 alasdairj 05-22-2013 05:29 PM

Re: Q1 Quadratic Programming

Thank you Professor! I understand now!

 All times are GMT -7. The time now is 07:03 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.