LFD Book Forum

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 05: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 05: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 w)

alasdairj 05-22-2013 08: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 10: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 01: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 06:29 PM

Re: Q1 Quadratic Programming
 
Thank you Professor! I understand now!


All times are GMT -7. The time now is 02:29 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.