LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 7 (http://book.caltech.edu/bookforum/forumdisplay.php?f=136)
-   -   Q8-Q10, computing b, Ein non-zero (http://book.caltech.edu/bookforum/showthread.php?t=4292)

 Katie C. 05-16-2013 03:55 PM

Q8-Q10, computing b, Ein non-zero

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:

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 05-16-2013 04:35 PM

Re: Q8-Q10, computing b, Ein non-zero

Quote:
 Originally Posted by Katie C. (Post 10853) 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. 05-17-2013 06:24 AM

Re: Q8-Q10, computing b, Ein non-zero

Thank you for confirming that. I will keep looking.

 Katie C. 05-17-2013 06:37 AM

Re: Q8-Q10, computing b, Ein non-zero

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 05-20-2013 09:28 PM

Re: Q8-Q10, computing b, Ein non-zero

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 05-20-2013 10:39 PM

Re: Q8-Q10, computing b, Ein non-zero

Quote:
 Originally Posted by marek (Post 10894) 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.