LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 8 (http://book.caltech.edu/bookforum/forumdisplay.php?f=137)

 alasdairj 05-22-2013 04:28 AM

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

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

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

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

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