LFD Book Forum Q8-Q10, computing b, Ein non-zero
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
05-16-2013, 03:55 PM
 Katie C. Member Join Date: Apr 2013 Posts: 17
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?
#2
05-16-2013, 04:35 PM
 yaser Caltech Join Date: Aug 2009 Location: Pasadena, California, USA Posts: 1,477
Re: Q8-Q10, computing b, Ein non-zero

Quote:
 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 .
__________________
Where everyone thinks alike, no one thinks very much
#3
05-17-2013, 06:24 AM
 Katie C. Member Join Date: Apr 2013 Posts: 17
Re: Q8-Q10, computing b, Ein non-zero

Thank you for confirming that. I will keep looking.
#4
05-17-2013, 06:37 AM
 Katie C. Member Join Date: Apr 2013 Posts: 17
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.
#5
05-20-2013, 09:28 PM
 marek Member Join Date: Apr 2013 Posts: 31
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.
#6
05-20-2013, 10:39 PM
 jforbes Member Join Date: Apr 2013 Posts: 12
Re: Q8-Q10, computing b, Ein non-zero

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

 Thread Tools Display Modes Linear 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 10:02 AM.

 Contact Us - LFD Book - Top