LFD Book Forum Octave QP issue
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
08-23-2012, 08:16 PM
 patrickjtierney Member Join Date: Jul 2012 Location: Toronto, Canada Posts: 33
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?
#2
08-24-2012, 05:35 AM
 htlin NTU Join Date: Aug 2009 Location: Taipei, Taiwan Posts: 601
Re: Octave QP issue

Quote:
 Originally Posted by patrickjtierney 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.
#3
08-24-2012, 08:22 AM
 patrickjtierney Member Join Date: Jul 2012 Location: Toronto, Canada Posts: 33
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.
#4
08-24-2012, 12:17 PM
 zifmia Junior Member Join Date: Jul 2012 Posts: 4
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
#5
02-20-2013, 08:33 PM
 dthal Junior Member Join Date: Jan 2013 Posts: 3
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.

 Tags hw7.8-10

 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 11:45 PM.

 Contact Us - LFD Book - Top