Support Vector Machine, 30 lines

In this article, I will show you how to write your very simple support vector machine without scikit-learn or other libraries with a ready-made implementation in just 30 lines in Python. If you wanted to understand the SMO algorithm, but it seemed too complicated, then this article may be useful to you.



It is impossible to explain what the Matrix support vector machine is ... You have to see it yourself.





Having learned that Habré has the ability to insert media elements, I created a small demo (if it suddenly doesn't work, you can still try your luck with the version on github [1] ). Place on a plane (space of two features $$$X$ and $$$Y$ ) several red and blue points (this is our dataset) and the machine will perform the classification (each point of the background is painted over depending on where the corresponding request would be classified). Move the points, change the core (I advise you to try Radial Basis Functions) and the hardness of the border (constant $$$C$ ). My apologies for the terrible code in JS - I wrote in it only a few times in my life, to understand the algorithm, use the Python code later in the article.

Content

• , , , . , — . , — [2] [3], , , .
• « SMO» SMO , , . , , SMO, .
• , «» Python .
• « sklearn.svc.svm» — 2D confusion matrix MNIST.
• «» - .

Support Vector Machine is a machine learning method (supervised learning) for solving problems of classification, regression, anomaly detection, etc. We will consider it using the example of a binary classification problem. Our training sample is a set of feature vectors $$$\boldsymbol{x}_i$ classified into one of two classes $$$y_i = \pm 1$ ... Classification Request - Vector $$$\boldsymbol{x}$ to which we must assign the class $$$+1$ or $$$-1$ ...



In the simplest case, the classes of the training sample can be divided by drawing only one straight line as in the figure (for a larger number of features, this would be a hyperplane). Now, when a request comes to classify some point $$$\boldsymbol{x}$ , it is reasonable to place it in the class on which side it will be.



How to choose the best straight line? Intuitively, I want the straight line to pass in the middle between the classes. To do this, write the equation of the straight line as $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = 0$ and scale the parameters so that the dataset points closest to the straight line satisfy $$$\boldsymbol{x} \cdot \boldsymbol{w} + b = \pm 1$ (plus or minus, depending on the class) - these points are called support vectors .



In this case, the distance between the boundary points of the classes is $$$2/|\boldsymbol{w}|$ ... Obviously, we want to maximize this value in order to separate the classes as well as possible. The latter is equivalent to minimizing $$$\frac{1}{2} |\boldsymbol{w}|^2$ , the entire optimization problem is written

$$

$$\begin{aligned} &\min \frac{1}{2} |\boldsymbol{w}|^2 \\ \text{subject to: } &y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0. \end{aligned}$$

If you solve it, then the classification on request $$$\boldsymbol{x}$ produced like this

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}\left(\boldsymbol{x} \cdot \boldsymbol{w} + b\right).$$

This is the simplest support vector machine.



And what to do in the case when points of different classes mutually penetrate as in the figure?



We can no longer solve the previous optimization problem - there are no parameters that satisfy those conditions. Then it is possible to allow the points to violate the boundary by the amount $$$\xi_i \geq 0$ , but it is also desirable that such violators be as few as possible. This can be achieved by modifying the objective function with an additional term (regularization $$$L_1$ ):

$$

$$\begin{aligned} &\min\left( \frac{1}{2} |\boldsymbol{w}|^2 + C \sum_i \xi_i \right)\\ \text{subject to: }&\xi_i + y_i \left(\boldsymbol{x}_i \cdot \boldsymbol{w} + b\right) - 1 \geq 0,\\ &\xi_i \geq 0, \end{aligned}$$

and the classification procedure will continue as before. Here the hyperparameter $$$C$ is responsible for the strength of regularization, that is, it determines how strictly we require points to respect the boundary: the more $$$C$ - the more $$$\xi_i$ will vanish and the fewer points will violate the boundary. Support vectors in this case are the points for which $$$\xi_i > 0$ ...



But what if the training set resembles the logo of The Who and the dots can never be separated by a straight line?



Here we will be helped by a clever technique - the kernel trick [4] . However, in order to apply it, one must pass to the so-called dual (or dual ) Lagrange problem. A detailed description of it can be found in Wikipedia [5] or in the sixth lecture of the course [3] . Variables in which a new problem is solved are called dual or Lagrange multipliers... The dual problem is often simpler than the original one and has good additional properties, for example, it is concave even if the original problem is not convex. Although its solution does not always coincide with the solution of the original problem (duality break), there are a number of theorems that, under certain conditions, guarantee such a coincidence (strong duality). And this is just our case, so you can safely go to the dual problem

$$

$$\begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j (\boldsymbol{x}_i \cdot \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$$

Where $$$\lambda_i$ - dual variables. After solving the maximization problem, it is also necessary to calculate the parameter $$$b$ , which is not included in the dual problem, but is needed for the classifier

$$

$$b = \mathbb{E}_{k,\xi_k \neq 0}\left[y_k - \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}_k)\right].$$

The classifier can (and should) be rewritten in terms of dual variables

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i (\boldsymbol{x}_i \cdot \boldsymbol{x}) + b.$$

What is the advantage of this recording? Please note that all vectors from the training set are included here exclusively in the form of dot products $$$(\boldsymbol{x}_i \cdot \boldsymbol{x}_j)$ ... You can first map points to a surface in a higher-dimensional space, and only then calculate the dot product of the images in the new space. Why do this can be seen from the figure.



If the mapping is successful, the images of the points are separated by a hyperplane! In fact, everything is even better: there is no need to display, because we are only interested in the dot product, and not in the specific coordinates of the points. So the whole procedure can be emulated by replacing the dot product with the function $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)$ , which is called the core . Of course, not every function can be a kernel - there must at least hypothetically exist a mapping $$$\varphi$ such that $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j)=(\varphi(\boldsymbol{x}_i) \cdot \varphi(\boldsymbol{x}_j))$ ... The necessary conditions are determined by Mercer's theorem [6] . The Python implementation will represent linear ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = \boldsymbol{x}_i^T \boldsymbol{x}_j$ ), polynomial ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = (\boldsymbol{x}_i^T \boldsymbol{x}_j)^d$ ) the kernel and the kernel of the radial basis functions ( $$$K(\boldsymbol{x}_i; \boldsymbol{x}_j) = e^{-\gamma |\boldsymbol{x}_i - \boldsymbol{x}_j|^2}$ ). As you can see from the examples, kernels can introduce their specific hyperparameters into the algorithm, which will also affect its operation.



You may have seen a video where the action of gravity is explained using the example of a stretched rubber film in the form of a funnel [7] . This works, since the movement of a point along a curved surface in a high-dimensional space is equivalent to the movement of its image in a space of a lower dimension, if provided with a nontrivial metric. In fact, the core bends space.

SMO Algorithm

So, we are at the goal, it remains to solve the dual problem posed in the previous section

$$

$$\def\M{{\color{red}M}} \def\L{{\color{blue}L}} \begin{aligned} &\max_{\lambda} \sum_{i=1}^n \lambda_i - \frac12 \sum_{i=1}^n \sum_{j=1}^n y_i y_j K(\boldsymbol{x}_i; \boldsymbol{x}_j) \lambda_i \lambda_j,\\ \text{subject to: } &0 \leq \lambda_i \leq C, \quad \mbox{ for } i=1, 2, \ldots, n,\\ &\sum_{i=1}^n y_i \lambda_i = 0, \end{aligned}$$

then find the parameter

$$

$$b = \mathbb{E}_{k,\xi_k \neq 0}[y_k - \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}_k)], \tag{1}$$

and the classifier will take the following form

$$

$$\text{class}(\boldsymbol{x}) = \text{sign}(f(\boldsymbol{x})),\quad f(\boldsymbol{x}) = \sum_i \lambda_i y_i K(\boldsymbol{x}_i; \boldsymbol{x}) + b. \tag{2}$$

The SMO (Sequential minimal optimization, [8] ) algorithm for solving the dual problem is as follows. In the loop, using a complex heuristic ( [9] ), a pair of dual variables is selected $$$\lambda_\M$ and $$$\lambda_\L$ , and then the objective function is minimized over them, with the condition of the constancy of the sum $\$\; inline\; \$\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; +\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L\; \$\; inline\; \$$$y_\M\lambda_\M + y_\L\lambda_\L$ and restrictions $$$0 \leq \lambda_\M \leq C$ , $$$0 \leq \lambda_\L \leq C$ (setting the hardness of the border). The sum condition stores the sum of all $$$y_i\lambda_i$ unchanged (after all, we did not touch the rest of the lambdas). The algorithm stops when it detects a sufficiently good observance of the so-called KKT conditions (Karush-Kuna-Tucker [10] ).



I'm going to make some simplifications.

• I will abandon the complex heuristics of index selection (this is done in the Stanford University course [11] ) and will iterate over one index, and select the second at random.
• I will refuse to check the CCP and will perform a predetermined number of iterations in advance.
• In the optimization procedure itself, in contrast to the classical work [9] or the Stanford approach [11] , I will use the vector straight line equation. This will greatly simplify calculations (compare the volume of [12] and [13] ).

Now for the details. Information from the training sample can be written in the form of a matrix

$$

$$\boldsymbol{K} = \begin{pmatrix} y_1 y_1 K(\boldsymbol{x}_1; \boldsymbol{x}_1) & y_1 y_2 K(\boldsymbol{x}_1; \boldsymbol{x}_2) & \dots & y_1 y_N K(\boldsymbol{x}_1; \boldsymbol{x}_N) \\ y_2 y_1 K(\boldsymbol{x}_2; \boldsymbol{x}_1) & y_2 y_2 K(\boldsymbol{x}_2; \boldsymbol{x}_2) & \dots & y_2 y_N K(\boldsymbol{x}_2; \boldsymbol{x}_N) \\ \cdots & \cdots & \cdots & \cdots \\ y_N y_1 K(\boldsymbol{x}_N; \boldsymbol{x}_1) & y_N y_2 K(\boldsymbol{x}_N; \boldsymbol{x}_2) & \dots & y_N y_N K(\boldsymbol{x}_N; \boldsymbol{x}_N) \\ \end{pmatrix}. \tag{3}$$

In what follows, I will use the notation with two indices ( $$$\boldsymbol{K}_{i,j}$ ) to refer to an element of the matrix and with one index ( $$$\boldsymbol{K}_{k}$ ) to denote the column vector of the matrix. Collect the dual variables into a column vector $$$\boldsymbol{\lambda}$ ... We are interested in

$$

$$\max_{\boldsymbol{\lambda}} \underbrace{ \sum_{i=1}^n \lambda_i - \frac12 \boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda} }_{\mathscr{L}}.$$

Suppose, at the current iteration, we want to maximize the objective function by indices $$$\L$ and $$$\M$ ... We will take derivatives, so it is convenient to select the terms containing the indices $$$\L$ and $$$\M$ ... It's easy to do in the sum part $$$\lambda_i$ , but the quadratic form will require several transformations.



When calculating $$$\boldsymbol{\lambda}^T \boldsymbol{K} \boldsymbol{\lambda}$ summation is performed over two indices, let $$$i$ and $$$j$ ... Highlight pairs of indices containing $$$\L$ or $$$\M$ ...





Let's rewrite the problem by combining everything that does not contain $$$\lambda_\L$ or $$$\lambda_\M$ ... To make it easier to keep track of the indices, pay attention to $$$\boldsymbol{K}$ in the image.

$$\begin{aligned} \mathscr{L} &= \lambda_\M + \lambda_\L - \sum_{j} \lambda_\M \lambda_j K_{\M,j} - \sum_{i} \lambda_\L \lambda_i K_{\L,i} + \text{const} + \\ {\text{}\atop\text{ }} \rightarrow\qquad &+ \frac{1}{2}\lambda_\M^2 K_{\M,\M} + \lambda_\M \lambda_\L K_{\M,\L} + \frac{1}{2}\lambda_\L^2 K_{\L,\L} = \\ &= \lambda_\M \left(1-\sum_{j} \lambda_j K_{\M,j}\right) + \lambda_\L \left(1-\sum_{i} \lambda_i K_{\L,i}\right)+\\ &+\frac{1}{2}\left(\lambda_\M^2 K_{\M,\M} + 2 \lambda_\M \lambda_\L K_{\M,\L}+\lambda_\L^2 K_{\L,\L} \right) + \text{const} = \\ &=\boldsymbol{k}^T_0 \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}, \end{aligned}$$

Where $$$\text{const}$ denotes terms independent of $$$\lambda_\L$ or $$$\lambda_\M$ ... In the last line, I used the notation

$$\begin{align} \boldsymbol{v}_0 &= (\lambda_\M, \lambda_\L)^T, \tag{4a}\\ \boldsymbol{k}_0 &= \left(1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\M}, 1 - \boldsymbol{\lambda}^T\boldsymbol{K}_{\L}\right)^T, \tag{4b}\\ \boldsymbol{Q} &= \begin{pmatrix} K_{\M,\M} & K_{\M,\L} \\ K_{\L,\M} & K_{\L,\L} \\ \end{pmatrix},\tag{4c}\\ \boldsymbol{u} &= (-y_\L, y_\M)^T. \tag{4d} \end{align}$$

note that $$$\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0$ does not depend on $$$\lambda_\L$ nor from $$$\lambda_\M$

$\$\$\; display\; \$\$\; \backslash \; boldsymbol\; \{k\}\; \_0\; =\; \backslash \; begin\; \{pmatrix\}\; 1\; -\; \backslash \; lambda\_\; \backslash \; M\; K\; \_\; \{\backslash \; M,\; \backslash \; M\}\; -\; \backslash \; lambda\_\; \backslash \; L\; K\; \_\; \{\backslash \; M,\; \backslash \; L\}\; -\; \backslash \; sum\_\; \{i\; \backslash \; neq\; \backslash \; M,\; \backslash \; L\}\; \backslash \; lambda\_i\; K\; \_\; \{\backslash \; M,\; i\}\; \backslash \backslash \; 1\; -\; \backslash \; lambda\_\; \backslash \; M\; K\; \_\; \{\backslash \; L,\; \backslash \; M\}\; -\; \backslash \; lambda\_\; \backslash \; L\; K\; \_\; \{\backslash \; L,\; \backslash \; L\}\; -\; \backslash \; sum\_\; \{i\; \backslash \; neq\; \backslash \; M,\; \backslash \; L\}\; \backslash \; lambda\_i\; K\; \_\; \{\backslash \; L,\; i\}\; \backslash \backslash \; \backslash \; end\; \{pmatrix\}\; =\; \backslash \; begin\; \{pmatrix\}\; 1\; -\; \backslash \; sum\_\; \{i\; \backslash \; neq\; \backslash \; M,\; \backslash \; L\}\; \backslash \; lambda\_i\; K\; \_\; \{\backslash \; M\; ,\; i\}\; \backslash \backslash \; 1\; -\; \backslash \; sum\_\; \{i\; \backslash \; neq\; \backslash \; M,\; \backslash \; L\}\; \backslash \; lambda\_i\; K\; \_\; \{\backslash \; L,\; i\}\; \backslash \backslash \; \backslash \; end\; \{pmatrix\}\; -\; \backslash \; boldsymbol\; \{Q\}\; \backslash \; boldsymbol\; \{v\}\; \_0.\$\$\; display\; \$\$$

$$\boldsymbol{k}_0 = \begin{pmatrix} 1 - \lambda_\M K_{\M,\M} - \lambda_\L K_{\M,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \lambda_\M K_{\L,\M} - \lambda_\L K_{\L,\L} - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} = \begin{pmatrix} 1 - \sum_{i \neq \M,\L} \lambda_i K_{\M,i}\\ 1 - \sum_{i \neq \M,\L} \lambda_i K_{\L,i}\\ \end{pmatrix} - \boldsymbol{Q} \boldsymbol{v}_0.$$

The kernel is symmetrical, therefore $$$\boldsymbol{Q}^T = \boldsymbol{Q}$ and you can write

$$

$$\mathscr{L} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0 - \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 + \frac{1}{2}\boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}_0 - \frac{1}{2} \boldsymbol{v}^{\,T}_0 \, \boldsymbol{Q} \, \boldsymbol{v}_0 + \text{const}$$

We want to perform the maximization so that $\$\; inline\; \$\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L\; +\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; \$\; inline\; \$$$y_\L\lambda_\L + y_\M\lambda_\M$ remained constant. To do this, the new values ​​must lie on the straight line

$\$\$\; display\; \$\$\; (\backslash \; lambda\_\; \backslash \; M\; ^\; \backslash \; text\; \{new\},\; \backslash \; lambda\_\; \backslash \; L\; ^\; \backslash \; text\; \{new\})\; ^\; T\; =\; \backslash \; boldsymbol\; \{v\}\; (t)\; =\; \backslash \; boldsymbol\; \{v\}\; \_0\; +\; t\; \backslash \; boldsymbol\; \{u\}.\$\$\; display\; \$\$$

$$(\lambda_\M^\text{new}, \lambda_\L^\text{new})^T = \boldsymbol{v}(t) = \boldsymbol{v}_0 + t \boldsymbol{u}.$$

It is easy to make sure that for any $$$t$

$\$\$\; display\; \$\$\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; ^\; \backslash \; text\; \{new\}\; +\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L\; ^\; \backslash \; text\; \{new\}\; =\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; +\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L\; +\; t\; (-y\_\; \backslash \; M\; y\_\; \backslash \; L\; +\; y\_\; \backslash \; L\; y\_\; \backslash \; M)\; =\; y\_\; \backslash \; M\; \backslash \; lambda\_\; \backslash \; M\; +\; y\_\; \backslash \; L\; \backslash \; lambda\_\; \backslash \; L.\$\$\; display\; \$\$$

$$y_\M\lambda_\M^\text{new} + y_\L\lambda_\L^\text{new} = y_\M \lambda_\M + y_\L \lambda_\L + t (-y_\M y_\L + y_\L y_\M) = y_\M\lambda_\M + y_\L\lambda_\L.$$

In this case, we must maximize

$$

$$\mathscr{L}(t) = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \boldsymbol{v}(t) - \frac12 \boldsymbol{v}^{\,T}(t) \, \boldsymbol{Q} \, \boldsymbol{v}(t) + \text{const},$$

which is easy to do by taking the derivative

$$

$$\begin{align} \frac{d \mathscr{L}(t)}{d t} = (\boldsymbol{k}_0 + \boldsymbol{Q} \boldsymbol{v}_0)^T \frac{d \boldsymbol{v}}{dt} &- \frac12 \left(\frac{d(\boldsymbol{v}^{\,T} \, \boldsymbol{Q} \, \boldsymbol{v})}{d \boldsymbol{v}}\right)^T \frac{d\boldsymbol{v}}{d t} =\\ &= \boldsymbol{k}_0^T \boldsymbol{u} + \underbrace{\boldsymbol{v}_0^T \boldsymbol{Q}^T \boldsymbol{u} - \boldsymbol{v}^T \boldsymbol{Q}^T \boldsymbol{u}}_{(\boldsymbol{v}_0^T - \boldsymbol{v}^T)\boldsymbol{Q} \boldsymbol{u}} = \boldsymbol{k}_0^T \boldsymbol{u} - t \boldsymbol{u}^T \boldsymbol{Q} \boldsymbol{u}. \end{align}$$

Equating the derivative to zero, we get

$$

$$t_* = \frac{\boldsymbol{k}^T_0 \boldsymbol{u}}{\boldsymbol{u}^{\,T} \boldsymbol{Q} \boldsymbol{u}}. \tag{5}$$

And one more thing: perhaps we will climb further than necessary and find ourselves outside the square as in the picture. Then you need to take a step back and return to its border

$\$\$\; display\; \$\$\; (\backslash \; lambda\_\; \backslash \; M\; ^\; \backslash \; text\; \{new\},\; \backslash \; lambda\_\; \backslash \; L\; ^\; \backslash \; text\; \{new\})\; =\; \backslash \; boldsymbol\; \{v\}\; \_0\; +\; t\; \_\; *\; ^\; \{\backslash \; text\; \{restr\}\}\; \backslash \; boldsymbol\; \{u\; \}.\$\$\; display\; \$\$$

$$(\lambda_\M^\text{new}, \lambda_\L^\text{new}) = \boldsymbol{v}_0 + t_*^{\text{restr}} \boldsymbol{u}.$$

This completes the iteration and selects new indices.

Implementation

The schematic diagram of training a simplified support vector machine can be written as







Let's take a look at the code in a real programming language. If you don't like the code in the articles, you can study it on the github [14] .







When creating an object of the SVM class, you can specify hyperparameters. Training is done by calling the fit function, the classes must be specified as $$$0$ and $$$1$ (internally converted to $$$-1$ and $$$+1$ , made for greater compatibility with sklearn), the dimension of the feature vector is allowed arbitrary. The predict function is used for classification.

Comparison with sklearn.svm.SVC

Not that this comparison makes much sense, because we are talking about an extremely simplified algorithm, developed solely for the purpose of teaching students, but still. For testing (and to see how to use it all), you can do the following (this code is also available on the github [14] ).





After launch, pictures will be generated, but since the algorithm is randomized, they will be slightly different for each launch. Here is an example of how the simplified algorithm works (from left to right: linear, polynomial and rbf kernels)



And this is the result of the industrial version of the support vector machine.



If the dimension $$$2$ seems too small, you can still test on MNIST





For MNIST, I tried several random pairs of classes (the simplified algorithm only supports binary classification), but I found no difference in the work of the simplified algorithm and sklearn. The following confusion matrix gives an idea of ​​the quality.

Conclusion

Thanks to everyone who read to the end. In this article, we looked at a simplified tutorial implementation of a support vector machine. Of course, it cannot compete with an industrial design, but due to the extreme simplicity and compact code in Python, and the fact that all the basic ideas of SMO have been preserved, this version of SVM may well take its place in the classroom. It should be noted that the algorithm is simpler not only than a very tricky algorithm [9] , but even its simplified version from Stanford University [11] . After all, a support vector machine in 30 lines is beautiful.

List of references

1. https://fbeilstein.github.io/simplest_smo_ever/
2. page at http://www.machinelearning.ru
3. "Beginnings of Machine Learning", KAU
4. https://en.wikipedia.org/wiki/Kernel_method
5. https://en.wikipedia.org/wiki/Duality_(optimization)
6. http://www.machinelearning.ru
7. https://www.youtube.com/watch?v=MTY1Kje0yLg
8. https://en.wikipedia.org/wiki/Sequential_minimal_optimization
9. Platt, John. Fast Training of Support Vector Machines using Sequential Minimal Optimization, in Advances in Kernel Methods – Support Vector Learning, B. Scholkopf, C. Burges, A. Smola, eds., MIT Press (1998).
10. https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions
11. http://cs229.stanford.edu/materials/smo.pdf
12. https://www.researchgate.net/publication/344460740_Yet_more_simple_SMO_algorithm
13. http://fourier.eng.hmc.edu/e176/lectures/ch9/node9.html
14. https://github.com/fbeilstein/simplest_smo_ever