Support vector machine for machine learning

One 、 Concept of support vector machine

Support vector machine (Support Vector Machine) It is a kind of generalized linear classifier which classifies data according to supervised learning （generalized linear classifier）, The decision boundary is the maximum margin hyperplane for learning samples (maximum-margin hyperplane).
SVM There are three treasures ： interval 、 dual 、 Nuclear skills
SVM There are three kinds of ：hard-margin SVM、soft-margin、kernel SVM
Given the training sample set $D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m),\},y_i\in \{-1,+1\}$, Find a hyperplane in the sample space , As far as possible Separate samples of different categories , Make the classification result produced by this partition hyperplane the most robust , See the thick line in the figure below .

The partition hyperplane can be described by the following linear equation ：
$$w^{T}x+b=0$$
among $w=(w_1;w_2;...w_d)$ For the normal vector , It determines the direction of the hyperplane ;b Is the displacement term , Determines the distance between the hyperplane and the origin , Partition hyperplane by normal vector w And displacement b determine .
Support vector machine $f(x)=sign(w^{T}x+b)$ It is a classical discriminant model .

Two 、SVM Basic type derivation

SVM Also called Maximum interval classifier , Define the model as ：

$$\begin{gathered} maxmargin(w,b)=maxdistance(w,b,x_i)(1) \\ s.t.\{\begin{array}{r}{w}^T{x}_i+b\ge 0,y_i=+1\\ w^T{x}_i+b\le 0,y_i=-1\end{array},i=1,2,...,m(2) \end{gathered}$$
By way of (2) Telescopic transformation is available ：
$$s.t.\{\begin{array}{r}{w}^T{x}_i+b\ge 1,y_i=+1\\ w^T{x}_i+b\le -1,y_i=-1\end{array}(3)$$
Let a point on the partition hyperplane be x‘, Then there are $w^T{x}^{\prime }=-b(4)$
Distance formula ：
$r=|\frac{w^T}{||w||}(x-x^{\prime })|(castshadow)=\frac{1}{||w||}|w^{T}x+b|(generationEnter\; into(4)type)$

As shown in the figure , These training sample points closest to the hyperplane make (3) The equation equals sign holds , So for the recent point $|w^T+b|=1$, They are called ” Support vector “, According to the distance formula ：

$$r=\frac{1}{||w||}(5)$$
The sum of the distances from the two heterogeneous support vector machines to the hyperplane is ：
$$\gamma =\frac{2}{||w||}(6)$$
It's called spacing (margin).
Want to find the maximum interval (maximum margin) The partition hyperplane of , That is to find satisfaction (3) There are three constraint parameters w and b, bring $\gamma$ Maximum , namely
$$\begin{array}{rl}& \underset{w,b}{\max }=\frac{2}{||w||}\\ & s.t.y_i(w^T{x}_i+b)\ge 1,i=1,2,...,m\end{array}(7)$$
Obviously maximize the interval , Just maximize $||w|{|}^{-1}$, This is equivalent to minimizing $||w|{|}^2$, therefore （7） Formula rewritten as

$$\begin{array}{rl}& \underset{w,b}{\min }=\frac{1}{2}{||w||}^2\\ & s.t.y_i(w^T{x}_i+b)\ge 1,i=1,2,...,m\end{array}(8)$$
(8) The formula is SVM The basic type of