非线性可分问题

能用一个超曲面将训练数据集的正负例正确分开，则称这个问题为非线性可分问题。

方法：通过非线性变换将非线性问题转化为线性问题。

核函数的引入

定义一个从低维特征空间到高维特征空间的映射ϕ，将所有特征映射到一个更高的维度，让数据线性可分。

目标函数中高维特征仅以内积形式出现

$$ \begin{gathered}\underbrace{\min }\alpha \frac{1}{2} \sum{i=1, j=1}^m \alpha_i \alpha_j y_i y_j \phi\left(x_i\right) \bullet \phi\left(x_j\right)-\sum_{i=1}^m \alpha_i \\\text { s.t. } \sum_{i=1}^m \alpha_i y_i=0 \\0 \leq \alpha_i \leq C\end{gathered} $$

<aside> 💡 核函数的定义：

假设ϕ是一个从低维的输入空间χ（欧式空间的子集或者离散集合）到高维的希尔伯特空间的H映射。如果存在函数K(x,z)，对于任意x,z∈χ，都有：

$$ K(x, z)=\phi(x) \bullet \phi(z) $$

则称函数K(x,z)为核函数。

• 核函数的意义 </aside>

正定核

一般所说的核函数都是正定核函数。

<aside> 💡 正定核函数的充分必要条件

一个函数要想成为正定核函数，必须满足他里面任何点的集合形成的Gram矩阵是半正定的。

$$ \forall x_i\in \chi(i=1,2,\cdots,m),对应的Gram矩阵[K(x_i,x_j)]_{m\times m}是半正定矩阵 $$

</aside>

常用核函数

1. 线性核函数（即线性SVM）

   $$ K(x\cdot z)=x\cdot z $$

2. 多项式核函数

   $$ K(x, z)=(\gamma x \bullet z+r)^d $$

3. 高斯核函数

   $$ K(x, z)=\exp \left(-\gamma\|x-z\|^2\right) $$

4. sigmoid核函数

   $$ K(x, z)=\tanh (\gamma x \bullet z+r) $$