 LFD Book Forum What Quadratic Programming Package? #31
 kurts Invited Guest Join Date: Apr 2012 Location: Portland, OR Posts: 70 Re: What Quadratic Programming Package?

Quote:
 Originally Posted by jg2012 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,[]);```
#32
 lucag Member Join Date: Apr 2012 Posts: 44 Re: What Quadratic Programming Package?

Quote:
 Originally Posted by markweitzman 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.
#33
 markweitzman Invited Guest Join Date: Apr 2012 Location: Las Vegas Posts: 69 Re: What Quadratic Programming Package?

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

Mark Weitzman
#34
 danielfm Member Join Date: Apr 2012 Location: Rio de Janeiro - Brazil Posts: 10 Re: What Quadratic Programming Package?

Quote:
 Originally Posted by kurts 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 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 .

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. #35
 sakumar Member Join Date: Apr 2012 Posts: 40 Re: What Quadratic Programming Package?

Quote:
 Originally Posted by kurts 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.
#36
 kurts Invited Guest Join Date: Apr 2012 Location: Portland, OR Posts: 70 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.
#37
 SamK52 Member Join Date: Apr 2012 Posts: 25 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.
#38
 sakumar Member Join Date: Apr 2012 Posts: 40 Re: What Quadratic Programming Package?

Quote:
 Originally Posted by kurts 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 ...
#39
 elkka Invited Guest Join Date: Apr 2012 Posts: 57 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.
#40
 dudefromdayton Invited Guest Join Date: Apr 2012 Posts: 140 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. Tags hw7, package, quadratic programming Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 06:39 PM.