LFD Book Forum

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:
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 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 b 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 E_{\rm in}=0.

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.

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


All times are GMT -7. The time now is 01:05 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2021, 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.