XPost: comp.ai.neural-nets   
   From: kimon@ath.forthnet.gr   
      
   > Unfortunately, the situation is quite complex.  As part of my Phd   
   > work, I wrote an SVM solver (SvmFu, no longer supported or in wide use   
   > or recommended).  SvmFu worked by using SMO to solve subproblems over   
   > a chunk (a few hundred to a few thousand examples, user settable).   
      
   Yes Rian, of course I am aware of your work.   
      
   > Around the same time, Joachims' SvmLight was using a general purpose   
   > QP to solve subproblems.  On some examples, SvmFu was faster, on some   
   > examples, SvmLight was faster, and I could not easily tell which would   
   > be faster on a given problem without trying.  Both were *much* faster   
   > than the SMO algorithm described in Platt's 1998 paper, which did not   
   > mention caching of kernel products; caching of frequently needed   
   > kernel products is one of the primary keys to solving SVMs rapidly.   
      
   Of course. I should have clarified from the start that I meant the   
   modern SMO implementations after Keerthi's et al work, including   
   caching of kernel rows.   
      
   >   
   > In general, if I can easily store and work with O(n^2) memory, I   
   > expect to be able to solve a subproblem in time O(n^3) using a general   
   > purpose QP.  In SMO, the individual steps are very rapid, but I will   
   > need to take many more steps, even in the best case.   
      
   Yes, especially the first steps can be easily reversed later and it   
   takes too many iterations to lower the maximum violation just a bit.   
   After that it's faster, ie it's better at tidying-up things. There is   
   my curiosity. Would it make a difference to increase the dimension of   
   these steps a little? I don't have any serious reason to believe so,   
   only that curiosity.   
      
      
   > If I don't do   
   > some sort of chunking, it may take me a long time just to figure out   
   > what step to take next.  It's unclear where the balance was.  I   
   > suspect that around a few hundred points, you will do about equally   
   > well solving the whole subproblem using a general purpose QP and using   
   > SMO.  In particular, if the dimensionality is quite high, you will   
   > spend a lot of the total time just calculating the kernel matrix, and   
   > assuming your subproblem is mostly support vectors, you will need that   
   > entire kernel matrix, so SMO and general purpose will both pay this   
   > cost.   
      
   But the problem with general purpose QP routines is that they are   
   suited for problems with few active bounds! Take for example Goldfarb   
   and Idnani, it is an excellent algorithm for such sizes, but it starts   
   with an empty working set.   
      
   >   
   > I eventally discontinued this line of work, on the grounds that I   
   > could spend a lot of time digging at the algorithms, and I might get   
   > another 30% performance improvement, but I certainly wasn't going to   
   > get a factor of 10.   
      
   A very correct point. This does not apply to me, I am new in this area   
   and would be happy to make even a small contribution :)   
      
   Thanks very much for your help and best regards,   
      
   Kimon   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)