LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 8

Reply
 
Thread Tools Display Modes
  #1  
Old 05-22-2013, 05:28 AM
alasdairj alasdairj is offline
Member
 
Join Date: Mar 2013
Posts: 12
Default 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?
Reply With Quote
  #2  
Old 05-22-2013, 05:48 AM
Elroch Elroch is offline
Invited Guest
 
Join Date: Mar 2013
Posts: 143
Default 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)
Reply With Quote
  #3  
Old 05-22-2013, 08:34 AM
alasdairj alasdairj is offline
Member
 
Join Date: Mar 2013
Posts: 12
Default 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 :-).
Reply With Quote
  #4  
Old 05-22-2013, 10:01 AM
Elroch Elroch is offline
Invited Guest
 
Join Date: Mar 2013
Posts: 143
Default Re: Q1 Quadratic Programming

Quote:
Originally Posted by alasdairj View Post
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.
Reply With Quote
  #5  
Old 05-22-2013, 01:48 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q1 Quadratic Programming

Quote:
Originally Posted by alasdairj View Post
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.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #6  
Old 05-22-2013, 06:29 PM
alasdairj alasdairj is offline
Member
 
Join Date: Mar 2013
Posts: 12
Default Re: Q1 Quadratic Programming

Thank you Professor! I understand now!
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -7. The time now is 10:57 AM.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, 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.