Manual implementation of a Support Vector Machine
<p>I am wondering is there any article where SVM (Support Vector Machine) is implemented manually in R or Python.</p>

<p>I do <strong>not</strong> want to use a built-in function or package. ?</p>

<p>The example could be very simple in terms of feature space and linear separable. </p>

<p>I just want to go through the whole process to enhance my understanding.</p>

<p>The answer to this question is rather broad since there are several possible algorithms in order to train SVMs. Also packages like LibSVM (available both for Python and R) are open-source so you are free to check the code inside.</p>

<p>Hereinafter I will consider the Sequential Minimal Optimization (SMO) algorithm by J. Pratt which is implemented in LibSVM. Implementing manually an algorithm which solves the SVM optimization problem is rather tedious but, if that's your first approach with SVMs I'd suggest the following (albeit simplified) version of the SMO algorithm</p>

<p><a href="http://cs229.stanford.edu/materials/smo.pdf" rel="nofollow">http://cs229.stanford.edu/materials/smo.pdf</a></p>

<p>This lecture is from Prof. Andrew Ng (Stanford) and he shows a simplified version of the SMO algorithm. I don't know what your theoretical background in SVMs is, but let's just say that the major difference is that the Lagrange multipliers pair (<em>alpha_i</em> and <em>alpha_j</em>) is randomly selected whereas in the original SMO algorithm there's a much harder heuristic involved.<br>
In other terms, thus, this algorithm does not guarantee to converge to a global optimum (which is always true in SVMs for the dataset at hand if trained with a proper algorithm), but this can give you a nice introduction to the optimization problem behind SVMs.  </p>

<p>This paper, however, does not show any codes in R or Python but the pseudo-code is rather straightforward and easy to implement (~100 lines of code in either Matlab or Python).  Also keep in mind that this training algorithm returns <em>alpha</em> (Lagrange multipliers vector) and <em>b</em> (intercept). You might want to have some additional parameters such as the proper Support Vectors but starting from vector <em>alpha</em> such quantities are rather easy to calculate.</p>

<p>At first, let's suppose you have a <code>LearningSet</code> in which there are as many rows as there are patterns and as many columns as there are features and let also suppose that you have <code>LearningLabels</code> which is a vector with as many elements as there are patterns and this vector (as its name suggests) contains the proper labels for the patterns in <code>LearningSet</code>.<br>
Also recall that <em>alpha</em> has as many elements as there are patterns.  </p>

<p>In order to evaluate the Support Vector indices you can check whether element <em>i</em> in <em>alpha</em> is greater than or equal to 0: if <code>alpha[i]&gt;0</code> then the <em>i</em>-th pattern from <code>LearningSet</code> is a Support Vector. Similarly, the <em>i</em>-th element from <code>LearningLabels</code> is the related label.</p>

<p>Finally, you might want to evaluate vector <em>w</em>, the free parameters vector. Given that <em>alpha</em> is known, you can apply the following formula  </p>

<pre><code>w = ((alpha.*LearningLabels)'*LearningSet)'
</code></pre>

<p>where <code>alpha</code> and <code>LearningLabels</code> are column vectors and <code>LearningSet</code> is the matrix as described above. In the above formula <code>.*</code> is the element-wise product whereas <code>'</code> is the transpose operator.</p>

python svm