Machine learning 05: nonlinear support vector machines

The main idea

---

Theorem ：
For linearly nonseparable points , There must be a dimension that makes it linearly separable .

Based on this theorem , We can use support vector machines to solve the problem of linearly nonseparable data , That is to map the data set to a high latitude , Then linear classification .

L d

---

Suppose the original sample point is ${\vec{x}}_i$, use $\varphi ({\vec{x}}_i)$ Represents a new sample point mapped to a new feature space . Then the split hyperplane can be expressed as

$$f(\vec{x})=\vec{w}\varphi (\vec{x})+b$$

So the dual problem of nonlinear support vector machine becomes ：

$$\begin{gathered} \underset{\vec{\alpha }}{\max }\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\varphi ({\vec{x}}_i{)}^T\varphi ({\vec{x}}_j) \\ s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C \end{gathered}$$

But the dimension after mapping from low dimensional space to high dimensional space may be very high , This will greatly increase $\varphi ({\vec{x}}_i{)}^T\varphi ({\vec{x}}_j)$ Amount of computation , So we need other ways to simplify the operation . This is the kernel function .

Kernel function

---

The function of kernel function

Both the objective function and the classification decision function only involve the inner product between samples , So there is no need to explicitly specify the nonlinear transformation , Instead, replace the inner product with a kernel function . set up $K(x,z)$ Is a kernel function , Or positive definite nucleus , Then there is a from input space To The feature space Mapping $\varphi (\vec{x})$, For any input space $\vec{x},\vec{z}$ Yes

$$K(\vec{x},\vec{z})=\varphi (\vec{x})\cdot \varphi (\vec{z})$$

Suppose our input space is $m$ dimension , The feature space is $d$ dimension , Then we can get the result of the kernel function $d$ The dimension operation is reduced to $m$ Dimensional operation . When $d$ Very large or even infinite , Kernel functions can reduce a lot of computation .

Common kernel functions

1. Linear kernel function ：$K({\vec{x}}_i,{\vec{x}}_j)={\vec{x}}_i^T{\vec{x}}_j+c$

2. Polynomial kernel function ：$K({\vec{x}}_i,{\vec{x}}_j)=(\alpha {\vec{x}}_i^T{\vec{x}}_j+c{)}^d$

3. Radial basis function （ Gaussian kernel ）：$K({\vec{x}}_i,{\vec{x}}_j)=e^{-\gamma \parallel {\vec{x}}_i-{\vec{x}}_j{\parallel }^2}$

4. $sigmod$ Kernel function ：$K({\vec{x}}_i,{\vec{x}}_j)=\tanh (\alpha {\vec{x}}_i^T{\vec{x}}_j+c)$

Sync update on ：SP-FA The blog of

---

return