In preparation for an upcoming exam I decided to implement a Support Vector Machine (SVM) in c++.
It is to be used on data with n samples and p features.
A SVM is given by:
\(
\begin{align}
\arg\min \frac{1}{2}w^Tw + C \, \sum_i\xi_i \\
&s.t. \\
&y_i(w^Tf_i+b) \ge 1-\xi_i \\
&\xi_i \ge 0
\end{align}
\)
\(y\) are the labels, \(f_i\) are the features, \(C\) is the free parameter of the SVM.
I do not care about creating my own quadratic program (QP) solver, so I am using the cgal library that provides a QP solver. However, this requires a reformulation of the QP to fit the requirements of cgal (compare http://www.cgal.org/Manual/latest/doc_html/cgal_manual/QP_solver/Chapter_main.html):
\(
\begin{align}
\arg\min x^TDx + c^Tx + c_0 \\
&s.t. \\
&Ax \ge \tilde b \\
&l \le x \le u
\end{align}
\)
It took me quite a bit to figure out how to do that, but in the end I got it:
Any entries, that are not specified, are 0
\(
\begin{align}
x &= (w, \xi, b)^T \\
D_{ij} &= \frac{1}{2} \;\forall i \le p \wedge i = j \\
c_i &= C \;\forall i: \, p < i \le p + n \\
A_i &= (y_i f_i, s,y_i) \\
\tilde b_i &= 1 \;\forall i \\
l_i &= -\infty \;\forall i \le p \lor i > p + n \\
u_i &= \infty \; \forall i
\end{align}
\)
With \(s\) being a vector containing a non-zero entry (1) at the i-th component.
Based on that, an implementation is possible. This covers only the primal problem. More on the dual problem and kernel trick will follow.
An implementation for the primal program can be found in my github repository:
https://github.com/hanslovsky/exercise/blob/master/cpp/svm/include/svm.hpp
For running it, you need only cgal. However, it still needs testing and verification as well as a way to visualize the results.
