What Quadratic Programming Package?

[kurts]

Originally Posted by jg2012

Anyone have success with Octave + qp?

Here's the setup that I used for the qp function

    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,[]);

[lucag]

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.

[markweitzman]

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

Mark Weitzman

[danielfm]

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:

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.

[sakumar]

Originally Posted by kurts

Here's the setup that I used for the qp function

    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.

[kurts]

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.

[SamK52]

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.

[sakumar]

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 ...

[elkka]

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.

[dudefromdayton]

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