LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 7

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

Quote:
Originally Posted by Katie C. View Post
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.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #3  
Old 05-17-2013, 07:24 AM
Katie C. Katie C. is offline
Member
 
Join Date: Apr 2013
Posts: 17
Default Re: Q8-Q10, computing b, Ein non-zero

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

Quote:
Originally Posted by marek View Post
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
Reply With Quote
Reply

Thread Tools
Display Modes

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 Jump


All times are GMT -7. The time now is 02:10 PM.


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