Know your SVMs
The Support Vector Machine (SVM) is a supervised learning algorithm which many believe is one of the best (or indeed the best ) [NGNotes].
From Wikipedia [SVMWiki] —
The original SVM algorithm was invented by Vladimir N. Vapnik and Alexey Ya. Chervonenkis in 1963. In 1992, Bernhard E. Boser, Isabelle M. Guyon and Vladimir N. Vapnik suggested a way to create nonlinear classifiers by applying the kernel trick to maximum-margin hyperplanes. The current standard incarnation (soft margin) was proposed by Corinna Cortes and Vapnik in 1993 and published in 1995.
Overtime, there have been so many variants of SVMs, that it is easy to get lost trying to identify the differences between them. So here is a one-page ‘cheat-sheet’ to know your SVMs.
Most machine learning algorithms can be said to have three basic aspects [domingos2012]: The hypothesis function, the loss function, and the optimisation method. We will record these aspects for the different SVM formulations. In addition, we will capture the multi-class strategy where appropriate. We would also capture some notes/comments on the formulations.
For all the following formulations, we have a training data of `m’ instances : X = (X_i, y_i), i = 1 … m. Each training instance has `n’ features and is represented as: X_i = (x_1, x_2, … x_n). The label, y_i for an instance can be in {-1, 1} in {0, 1} for the binary case and in {0, 1, … k} for a `k’ multi-class classification (the appropriate version will be specified).
<X_a, X_b> denotes the dot product (or inner product) between the equal sized vectors X_a and X_b.
The most popular implementations of SVM that are practically used is the LIBSVM and LIBLINEAR libraries. In addition to these, we will capture the formulations of other important to know variants.
References:
[NGNotes] Andrew, N.: Cs229 lecture notes. part v — support vector machines. http://cs229.stanford.edu/notes/cs229-notes3.pdf
[SVMWiki] https://en.wikipedia.org/wiki/Support_vector_machine
[Domingos2012] Domingos, P.: A few useful things to know about machine learning. Communications of the ACM 55(10), 78-87 (2012).
[LIBSVM] C.-C. Chang and C.-J. Lin. LIBSVM : a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1–27:27, 2011. https://www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf
[LIBLINEAR] R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification Journal of Machine Learning Research 9(2008), 1871–1874.
[Rifkin2004] Rifkin, R., Klautau, A.: In defense of one-vs-all classi cation. Journal of machine learning research 5(Jan), 101{141 (2004)
[KarpathyLinearClassifyCode] Karpathy, A.: Linear classi cation loss visualization. http://vision.stanford.edu/teaching/cs231n-demos/linear-classify/
