LFD Book Forum  

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

Reply
 
Thread Tools Display Modes
  #11  
Old 08-24-2012, 06:19 AM
jakvas jakvas is offline
Member
 
Join Date: Jul 2012
Posts: 17
Default Re: Quadratic programming

as for the matlab this worked for me

UB(1:N,1)=10^5;
options = optimset('LargeScale','off','MaxIter',2000);
alpha=quadprog(Q,f,[],[],Class,0,zeros(N,1),UB,[],options);

oh and for clarification Class is the +1/-1 classification of the points and the empty matricies are unused restrictions I hope this helps a little and isn't frowned upon from the collaboration point of view after all you know what you are doing;P
Reply With Quote
  #12  
Old 08-24-2012, 07:08 AM
apinde apinde is offline
Member
 
Join Date: Jul 2012
Posts: 12
Default Re: Quadratic programming

Can one use Solver in Excel for this problem? I've not used the other languages and platforms for quadratic programming packages and am desperately searching for a package that can be learned and used in a few days.
Reply With Quote
  #13  
Old 08-24-2012, 08:10 AM
patrickjtierney patrickjtierney is offline
Member
 
Join Date: Jul 2012
Location: Toronto, Canada
Posts: 33
Default Re: Quadratic programming

This was discussed extensively in the previous class. A user elkka found a solution to the non-terminating problem for Octave. The trick is to run qp on an altered version of H (using all the same other parameters) and then to use the output as the initial value alpha0 for qp on the original H. The second run seems to always terminate after one iteration.

The altered H is just to add a small amount to the diagonal of H (say 10^-15). This makes its determinant non-zero, which is helpful for qp. So HH=H+eye(n)*10^-15 should work. [ n is just the length of Y ] Also, the alpha0 I refer to goes first in the arg list for the second qp call.

The results are much better, both in terms of termination and in producing a noticeably higher prediction accuracy (ie 10+% rise in better than PLA results).

I posted about this here: http://book.caltech.edu/bookforum/showthread.php?t=1133 , but also there is the original thread: http://book.caltech.edu/bookforum/sh...p?t=513&page=5
Reply With Quote
  #14  
Old 08-24-2012, 12:24 PM
invis invis is offline
Senior Member
 
Join Date: Jul 2012
Posts: 50
Default Re: Quadratic programming

Wow !
I try it for n=10 on 400 iterations and have ZERO situations where QP cant solve !
Next I try to do the same iterations without altered version of H and have 164 problems without solving...

Thanks very much !
Reply With Quote
  #15  
Old 08-24-2012, 01:01 PM
patrickjtierney patrickjtierney is offline
Member
 
Join Date: Jul 2012
Location: Toronto, Canada
Posts: 33
Default Re: Quadratic programming

I know. It's like magic, isn't it? And it appears to be a legitimate workaround for a problem with gp() on our problem.

One warning. I don't know if the answers we get are acceptable as far as the assignment goes (ie too good) or if we are simply fixing a problem in Octave. YMMV.

I noticed that on both N=10 and N=100 that the average Eout for SVM drops by about 20% after using this technique.
Reply With Quote
  #16  
Old 08-24-2012, 01:05 PM
invis invis is offline
Senior Member
 
Join Date: Jul 2012
Posts: 50
Default Re: Quadratic programming

Quote:
Originally Posted by patrickjtierney View Post
It's like magic, isn't it?
ML entirely is like magic too but its just a mathematics
Reply With Quote
  #17  
Old 08-24-2012, 02:18 PM
jakvas jakvas is offline
Member
 
Join Date: Jul 2012
Posts: 17
Default Re: Quadratic programming

I'm a matlab user and adding the diagonal terms results in no significant change for the results so it's probably something with the implementation of qp in Octave.

@patrickjtierney
A change in Eout this big should be noticible when plotting the results (as in plotting the target function the PLA result and the SVM result with the training data set you should see that something is wrong?).


@All
Watch lecture 15 the part from 1:07:35 1:08:00 just to make us feel better
Reply With Quote
  #18  
Old 08-24-2012, 02:52 PM
invis invis is offline
Senior Member
 
Join Date: Jul 2012
Posts: 50
Default Re: Quadratic programming

Hmm, my SV looks pretty strange
Code:
    options = optimset("MaxIter", 400);
    H = (Y*Y') .* (X*X');
    A = Y';
    q=-1*ones(n,1);
    b=0;
    lb=zeros(n,1);
    ub=10^10*ones(n,1);
    alpha0 = qp ([], H+(eye(n)*10^-15), q, A, b, lb, ub, options);
    alpha = qp (alpha0, H, q, A, b, lb, ub, options);
After this I have Alpha vector size of n. Next check what of alphas bigger then threshold (mine is 10^-5). If Alpha[2] bigger then threshold this mean that X[2,:] (X is my n*2 matrix with points) is one of support vectors
Ok, look at this vectors (small black line is my f):





Some of them pretty good, I place here only strange. Any ideas about behavior of this support vectors ?


Or it is a part of homework ? Because I check with n=100 and vectors looks better, but some time some of them still strange
Reply With Quote
  #19  
Old 08-24-2012, 06:51 PM
zifmia zifmia is offline
Junior Member
 
Join Date: Jul 2012
Posts: 4
Default Re: Quadratic programming

I don't see anything odd with your support vectors. The solution may not be a great fit to your target f, but SVM doesn't see your f, it only sees 10 samples of f, and in all the cases you show, it looks like the support vectors could do a pretty good job of separating the given training points.

Try drawing the actual separating line found by SVM (from the w vector and b), then draw the parallels to this line through your support vectors to see the margin zone. I think you will find that SVM does a pretty good job of separating your points.

Last edited by zifmia; 08-24-2012 at 06:54 PM. Reason: correction
Reply With Quote
  #20  
Old 08-24-2012, 11:59 PM
jakvas jakvas is offline
Member
 
Join Date: Jul 2012
Posts: 17
Default Re: Quadratic programming

@invis

The support vectors look fine to me. Could you draw the final hypothesis with the target function and the SVs? Then you should see more or less if the SVs support the final hypothesis like they should
Reply With Quote
Reply

Tags
quadratic programming

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 05:29 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.