SVMs
Notes SVM References
- interior point method is a good method for a small dataset: <20000 because it’s memory consumption goes like O(N^2) where N is number of examples. This is because it must store whole kernel matrix in memory which is NxN = N^2. So for double precision: 8 bytes/ point * (20kpoints)^2 = 3.2 gigabytes
- A FAQ for nonlinear programming from a usenet newsgroup.
- kernel-machines.org site w/lots of SVM software links.
- Chapter 7 (Training/Optimization) references from orange SVM book by Cristianini
- sites for various QPT solvers:
- Ipopt: an open source package for large-scale non-linear optimization
- OPT++: An Object-Oriented Nonlinear Optimization Library
- Optimization software guide
- SVM-QP Active set method specifically coded for SVM’s
- QPC - Quadratic Programming in C
- OOQP: Object Oriented Quadratic Programing (good & source is available w/documentation)
- Apparently interior point methods are mainly good for QP problems where “the Hessian of an objective function (for SVMs it’s the matrix Q_ij = y_i*y_j*K(x_i,x_j)) and/or of the constraint matrix is sparse.” In SVMs Q is dense. [ref]
- However, if Q for SVM problem is dense and low rank IPMs can be used. [ref]
- A paper on an active set method algorithm to solve the QP problem found in SVMs by author of SVM-QP (Scheinberg from IBM).
- memory consumption on # of data points, N, is key to optimization routines for SVMs
- Have 3 types of optimization techniques:
- Interior Point Methods: mem ~ O(N^2) —> good for small datasets
- Active Set Methods: mem ~ O(N_f^2) w/N_f being only the active set (i.e. only the support vectors). Usually N_f << N so ASMs are good for medium size datasets.
- Working Set Methods: mem ~ O(N^2) —> good for large data sets. Ex. SMO, chunking. WSMs aka decomposition methods.
- confused about meaning of working set vs active set
- A better copy of the paper on an active set method Scheinberg has posted on her site.
- Good info on SMO method.
- svm torch paper
- better way of calculating b in SMO
- SVMlight uses an active set method based on Osuna’s work
- a paper on a generalization of SMO
- Xianping Ge SMO writeup of an SMO implementation… thank you Xianping Ge! This write-up rocks! Clear and to the point and explains it all with code!
- Wikstrom SMO report
- A free, HTML machine learning book
Notes on Platt’s + Keerthi’s + Ge’s SMO code: PKGSMO
Outer loop i.e. Main Function
- Iterate once over all examples and execute examineExample() for each alpha_i in set of all examples (i.e. all alpha_i).
- If executing examineExample() failed (returned 0) for all examples above, then quit. If it succeeded for at least one, then now only iterate over the examples in the subset 0<alpha_i<C and execute examineExample() on each of these. If examineExample() is successful at least once, then keep re-iterating over the subset 0 < alpha_i < C executing examineExample() on alpha_i in 0 < alpha_i < C.
- Repeat this until examineExample() fails for all alpha_i in subset 0 < alpha_i < C. Then quit.
