LFD Book Forum  

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

Reply
 
Thread Tools Display Modes
  #1  
Old 08-23-2012, 08:16 PM
patrickjtierney patrickjtierney is offline
Member
 
Join Date: Jul 2012
Location: Toronto, Canada
Posts: 33
Default Octave QP issue

I came across a clever trick in the previous classes discussions for improving the stability and results of qp() in Octave. Essentially you just add a tiny amount to the H matrix's diagonal (10^-15) and then solve for alpha0 using qp. Then you rerun qp using alpha0 as the initial value and use your original H to obtain the value of alpha.

However, for N=10, I found the percent better for SVM went up by 15-20% as a result consistently. This leads to an in-between value which is on the verge of changing my answer to Q8.

I know this must have come up last time, but I wonder if this possible spread in the results due to implementation issues is accounted for in the answers?
Reply With Quote
  #2  
Old 08-24-2012, 05:35 AM
htlin's Avatar
htlin htlin is offline
NTU
 
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 601
Default Re: Octave QP issue

Quote:
Originally Posted by patrickjtierney View Post
I came across a clever trick in the previous classes discussions for improving the stability and results of qp() in Octave. Essentially you just add a tiny amount to the H matrix's diagonal (10^-15) and then solve for alpha0 using qp. Then you rerun qp using alpha0 as the initial value and use your original H to obtain the value of alpha.
Your trick indeed looks very clever. I find it difficult to believe the huge difference between your solutions, though. So you may want to double-check on which one is correct. Hope this helps.
__________________
When one teaches, two learn.
Reply With Quote
  #3  
Old 08-24-2012, 08:22 AM
patrickjtierney patrickjtierney is offline
Member
 
Join Date: Jul 2012
Location: Toronto, Canada
Posts: 33
Default Re: Octave QP issue

I think that Octave qp() is very sensitive to initial value for alpha. By improving the invertablity of the input matrix H, one gets a good approximation of alpha, which can then be used as a starting point when using the actual H. So its not so much magically improving the results as it is correcting a problem in qp() for this kind of usage. Basically qp() without the fix is frequently running to MaxIter without finding a solution. But I stand by the improvement in results. On different runs it is always 10-20% better versus PLA than it was without the "trick".

Also, credit for the idea goes to previous student elkka.
Reply With Quote
  #4  
Old 08-24-2012, 12:17 PM
zifmia zifmia is offline
Junior Member
 
Join Date: Jul 2012
Posts: 4
Default Re: Octave QP issue

Thanks for posting this. Went from only occasionally converging to converging always (N=100) or usually (N=10). Got all these answers correct on submission.

For N=10, I was finding that Octave failed to converge even on the modified problem about 10% of the time. For purposes of this assignment I just ignored these cases, but clearly there is more tweaking to be done. (Although other posts on Octave didn't seem to mention this, so perhaps there is something wrong with my problem formulation).

Followup: A quick experiment I should have done sooner shows that all of the cases that failed to converge were degenerate cases where all 10 points had the same classification. Apparently with my random line target and random point data this happens about 10% of the time with 10 points, and almost all of these fail to solve within the default 200 iterations. (Of course when they do solve, they have zero support vectors.)

Last edited by zifmia; 08-24-2012 at 12:36 PM. Reason: new data
Reply With Quote
  #5  
Old 02-20-2013, 08:33 PM
dthal dthal is offline
Junior Member
 
Join Date: Jan 2013
Posts: 3
Default Re: Octave QP issue

I have to second this trick. It got me from never converging to always converging.

Earlier, my code worked some of the time, and only on N=10. Other times, it returned wrong output. It took me a while to figure out that the problem was that qp wasn't converging. If you are using Octave, check the info object that you get back from qp to see if you are getting code 0 (OK) or something else.
Reply With Quote
Reply

Tags
hw7.8-10

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:20 AM.


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.