Q8-Q10, computing b, Ein non-zero

[Katie C.]

I am finding that when I use N=100 I get a non-zero Ein value for about 6% of the trials (60 out of 1000). On those trials I get one misclassified training point which is very close the the boundary. I think it is due to the calculation of b. I am seeing a range of b values depending on which support vector I pick to compute it. As a result, I started using the mean b value. However, I suspect that is causing the misclassification. I am using Matlab's quadprog with the interior point method as recommended here:
http://courses.csail.mit.edu/6.867/w...p-quadprog.pdf

It is converging reliably. I am adding a very small amount to the diagonal of H.

What is the best method for computing b? how much variability is expected?

[yaser]

Originally Posted by Katie C.

I am finding that when I use N=100 I get a non-zero Ein value for about 6% of the trials (60 out of 1000). On those trials I get one misclassified training point which is very close the the boundary. I think it is due to the calculation of b. I am seeing a range of b values depending on which support vector I pick to compute it.

As you know, this should not happen so I suspect some type of bug. The value of should be the same regardless of which SV you use to compute it, and this is in fact a good check that the solution is right. Also, the data is linearly separable by design so you should get .

[Katie C.]

Thank you for confirming that. I will keep looking.

[Katie C.]

I found that the problem was in adding that small amount to the diagonal of H. Apparently, in Matlab quadprog() with Algorithm='interior-point-convex' it is unnecessary and in fact, harmful.

[marek]

I'm having a similar issue and am using python cvxopt. First off the alphas are never identically 0. They are extremely close, but always just a little bit off. Is it supposed to give identically 0, or is what I'm experiencing typical?

As a result, in the calculation of w, I ignored alpha's that were not at least 10^-5 away from 0. And then depending on which remaining SV I select, my b values differ very slightly. As a result, I imagine this is what is causing a small fraction of cases to have nonzero Ein (however in my case, its very rare. Only 2 out of 1000).

I am quite unhappy with how things are turning out, as none of this feels right. But unfortunately I have no idea how to fix it -- this seems to be internal to this QP solver.

[jforbes]

Originally Posted by marek

I'm having a similar issue and am using python cvxopt. First off the alphas are never identically 0. They are extremely close, but always just a little bit off. Is it supposed to give identically 0, or is what I'm experiencing typical?

As a result, in the calculation of w, I ignored alpha's that were not at least 10^-5 away from 0. And then depending on which remaining SV I select, my b values differ very slightly. As a result, I imagine this is what is causing a small fraction of cases to have nonzero Ein (however in my case, its very rare. Only 2 out of 1000).

I am quite unhappy with how things are turning out, as none of this feels right. But unfortunately I have no idea how to fix it -- this seems to be internal to this QP solver.

Same here. I'm about to follow the advice on this thread http://book.caltech.edu/bookforum/showthread.php?t=1209
i.e. using all the alpha's, not just those with |alpha| > 1e-5 to calculate w.

I also seem to remember a thread which I can't find right now which suggests changing the tolerance parameters of cvxopt. This page has the relevant options: http://abel.ee.ucla.edu/cvxopt/userg...thm-parameters