LFD Book Forum  

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

Reply
 
Thread Tools Display Modes
  #31  
Old 05-21-2012, 04:30 PM
kurts kurts is offline
Invited Guest
 
Join Date: Apr 2012
Location: Portland, OR
Posts: 70
Default Re: What Quadratic Programming Package?

Quote:
Originally Posted by jg2012 View Post
Anyone have success with Octave + qp?
Here's the setup that I used for the qp function

Code:
    n = length(X(:,1)); % How many points
    d = length(X(1,:)); % Dimensionality of X
    H = zeros(n,n);
    L = ones(n,1);
    L = -1.*L;       % Linear term is tall vector of -1
    lb = zeros(n,1); % Lower bound on alpha is tall vector of 0
    A = Y';          % Linear coefficient  (A)(alpha) + blin = 0
    blin = 0;        % 
    
    for i = 1:n;
        for j = 1:n;
            H(i,j) = Y(i)*Y(j)*X(j,:)*X(i,:)';
        end;
    end;

    [alpha, obj, info, lambda] = qp([],H,L,A,blin,lb,[]);
Reply With Quote
  #32  
Old 05-21-2012, 04:33 PM
lucag lucag is offline
Member
 
Join Date: Apr 2012
Posts: 44
Default Re: What Quadratic Programming Package?

Quote:
Originally Posted by markweitzman View Post
I am using A as a 1 by n matrix (or a transpose of vector ) and b is a 1 by 1 matrix scalar. Doesn't seem to work
I don't know
My suggestion is to check all the matrices and vectors and scalars you have defined against what was shown in class.
Reply With Quote
  #33  
Old 05-21-2012, 05:06 PM
markweitzman markweitzman is offline
Invited Guest
 
Join Date: Apr 2012
Location: Las Vegas
Posts: 69
Default Re: What Quadratic Programming Package?

All right a little 1 for i error lol, but I have cvxopt working now,

Mark Weitzman
Reply With Quote
  #34  
Old 05-21-2012, 06:56 PM
danielfm danielfm is offline
Member
 
Join Date: Apr 2012
Location: Rio de Janeiro - Brazil
Posts: 10
Default Re: What Quadratic Programming Package?

Quote:
Originally Posted by kurts View Post
Here's the setup that I used for the qp function...
My code uses Octave + qp just like that, and I'm able to find a solution such that E_{in}=0 most of the time.

However, when the margin is very close to the hyperplane itself (e.g. positive and negative examples are too close), qp has trouble finding a solution, resulting in E_{in}>0.

I also increased the maximum number of iterations of qp just to be sure:

Code:
opt = optimset ("MaxIter", 1000); % 200 is the default
[alpha, obj, info, lambda] = qp([],H,L,A,blin,lb,[],opt);
My theory is that this has to do with the fact that SVMs have fewer dichotomies than a classifier such as the perceptron (Slide 14#5), but I'm not so sure.
Reply With Quote
  #35  
Old 05-21-2012, 09:36 PM
sakumar sakumar is offline
Member
 
Join Date: Apr 2012
Posts: 40
Default Re: What Quadratic Programming Package?

Quote:
Originally Posted by kurts View Post
Here's the setup that I used for the qp function

Code:
    n = length(X(:,1)); % How many points
    d = length(X(1,:)); % Dimensionality of X
    H = zeros(n,n);
    L = ones(n,1);
    L = -1.*L;       % Linear term is tall vector of -1
    lb = zeros(n,1); % Lower bound on alpha is tall vector of 0
    A = Y';          % Linear coefficient  (A)(alpha) + blin = 0
    blin = 0;        % 
    
    for i = 1:n;
        for j = 1:n;
            H(i,j) = Y(i)*Y(j)*X(j,:)*X(i,:)';
        end;
    end;

    [alpha, obj, info, lambda] = qp([],H,L,A,blin,lb,[]);
I used pretty much the same setup, but with alpha0 = 1 to start with.

However, did you check the info.info return code? I always get a 3 even if I increase the number of iterations from the default of 200 to 1000 (options.MaxIter = 1000). Code 3 just means that maximum number of iterations reached. I can see pretty decent support vectors though, so I'm hoping that's OK.
Reply With Quote
  #36  
Old 05-21-2012, 09:59 PM
kurts kurts is offline
Invited Guest
 
Join Date: Apr 2012
Location: Portland, OR
Posts: 70
Default Re: What Quadratic Programming Package?

Quote:
However, did you check the info.info return code?

No, I never did check the info. I was pretty sure things were working right because I got a reasonable number of support vectors, and almost all the time when I calculated b, I got the same value with all the support vector alphas. However, once in a while, I would get different b values for a given set of alphas, but I just chose to ignore those.
Reply With Quote
  #37  
Old 05-21-2012, 09:59 PM
SamK52 SamK52 is offline
Member
 
Join Date: Apr 2012
Posts: 25
Default Re: What Quadratic Programming Package?

I also get lots of Code 3s. I think all that means is that qp's stopping condition is too strict. In fact, I set MaxIter to 40. With this setting, my code runs in about 1/5th of the time it takes when MaxIter is at its default value, and the results are substantially the same.
Reply With Quote
  #38  
Old 05-21-2012, 11:03 PM
sakumar sakumar is offline
Member
 
Join Date: Apr 2012
Posts: 40
Default Re: What Quadratic Programming Package?

Quote:
Originally Posted by kurts View Post
No, I never did check the info. I was pretty sure things were working right because I got a reasonable number of support vectors, and almost all the time when I calculated b, I got the same value with all the support vector alphas. However, once in a while, I would get different b values for a given set of alphas, but I just chose to ignore those.
I see something strange too, but I am not sure if you are referring to that.

What I see is that occasionally I get back an alpha vector that has a surprising number of non-zero values. Several times the normal. If I actually use that anomalous alpha to calculate the average number of SVs, it will seriously skew the statistics. I checked to make sure that this isn't being caused by all my data points being on one side of the target function line. It isn't. Then the alternative is that it hasn't converged. Or that I have a bug ...
Reply With Quote
  #39  
Old 05-22-2012, 05:54 AM
elkka elkka is offline
Invited Guest
 
Join Date: Apr 2012
Posts: 57
Default Re: What Quadratic Programming Package?

I also get lots of code 3. In case N=10, approximately 30% of experiments return 3.

Obviously, the algorithm can't settle on a perfect w, and gives me whatever it comes up with on iteration 1000. By the way, changing MaxIter to 100000 did nothing to help the algorithm choose. It still returned 3s, just ran way longer.

By coincidence, in some 50% of the cases, where I see 3, my resulting (b,w) fails to separate the linearly separable 10 points correctly and E_in is positive. Not surprisingly, that same (b,w) loses to perceptron in all those cases. SVM is more likely to win, than to lose, if I only consider experiments with code0.

I don't like this at all. I don't trust those cases 3, and they seem to affect the answers considerably. I have managed to get rid of them with a trick, that I am not sure is quite legal.

Ohh. Those homeworks do make me think!


P.S. Noticed, that in all case3's I get inconsistent b values when using different SVs.
Reply With Quote
  #40  
Old 05-22-2012, 06:18 AM
dudefromdayton dudefromdayton is offline
Invited Guest
 
Join Date: Apr 2012
Posts: 140
Default Re: What Quadratic Programming Package?

@sakumar, I wrote a long response here to what I think is a different observation with the same root causes.
Reply With Quote
Reply

Tags
hw7, package, 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 06:39 PM.


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.