前验知识

在支持向量机的对偶算法 这一节中，将SVM的原始问题：

$$ \begin{equation*}\begin{aligned}&\min {b, w} ;;;\frac{1}{2} w^{T} w\&\text { s.t. } \quad 1-y{n}\left(\mathbf{w}^{T} \mathbf{x}_{n}+b\right) \leq 0 ,n=1,2,…,N\end{aligned}\end{equation*} $$

转为了对偶问题：

$$ \begin{equation*}\begin{split} \min_{\alpha}& ;;;\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} x_{i}^{T} x_{j} -\sum_{i=1}^{N} \alpha_{i}\ \text { s.t. }&;;; \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \ &;;; \alpha_{i} \geq 0, i=1,2, \ldots, N \end{split}\end{equation*} $$

由于原始问题与对偶问题为强对偶关系，所以可以利用KKT条件对其求解。

可以发现，目标函数只涉及输入实例与实例之间的内积。

核函数引入&定义

基于高维空间比低维空间更容易线性可分的思想，对于线性不可分的分类问题，所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题。核技巧就 属于这样的方法。

核技巧应用到支持向量机，其基本想法就是通过一个非线性变换将输入空间（欧氏空间$R^n$ 或离散集合）对应于一个特征空间（希尔伯特空间$H$)，使得在输入空间 $R^n$ 中的超曲面模型对应于特征空间$H$中的超平面模型（支持向量机）。这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。

核函数定义：设$X$是输入空间（欧氏空间$R^n$的子集或者离散集合），又设$H$为特征空间（希尔伯特空间），如果存在一个从$X$到$H$的映射

$$ \phi(x):X->H $$

使得对所有的$x,z\in X$，函数$K(x,z)$满足：

$$ K(X,Z) = \phi(x)\cdot\phi(z) $$

则称$K(x,z)$为核函数，$\phi(x)$为映射函数。

核技巧的想法是，在学习与预测中只定义核函数$K(x,z)$，而不显式地定义映射函$\phi(x)$。通常，直接计算$K(x,z)$比较容易，而通过$\phi(x)$和$\phi(z)$计算$K(x,z)$并不容易。注意，$\phi$是输入空间$R^n$到特征空间$H$的映射，特征空间$H$一般是高维的，甚至是无穷维的。可以看到，对于给定的核$K(x,z)$，特征空间$H$和映射函数$\phi(\cdot)$的取法并不唯一，可以取不同的特征空间，即便是在同一特征空间里也可以取不同的映射。

核函数应用

我们注意到在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积。在对偶问题的目标函数中，内积 $x_i^Tx_j = x_i \cdot x_j$ 可以用核函数

$$ K(x_i,x_j) = \phi(x_i) \cdot \phi(x_j) $$

来代替，此时对偶问题的目标函数成为：

$$ \min_{\alpha} ;;;\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j} \text K(x_i,x_j) -\sum_{i=1}^{N} \alpha_{i} $$

同样分类决策函数中的内积也可以用核函数代替，此时分类决策函数成为：

$$ \begin{equation*}\begin{aligned}f(x) &=\operatorname{sign}\left(\sum_{i=1}^{N_{}} a_{i}^{} y_{i} \phi\left(x_{i}\right) \cdot \phi(x)+b^{}\right) \&=\operatorname{sign}\left(\sum_{i=1}^{N_{}} a_{i}^{} y_{i} K\left(x_{i}, x\right)+b^{}\right)\end{aligned}\end{equation*} $$

这等价于经过映射函数$\phi(\cdot )$将原来的输入空间变换到一个新的特征空间，将输入空间中的内积$x_i \cdot x_j$变换为特征空间中的内积$\phi(x_i) \cdot \phi(x_j)$，在新的特征空间里从训练样本中学习线性支持向量机。

当映射函数$\phi(x) = x$，即不做任何变换，那么得到的还是原先的线性分类模型。当映射函数$\phi(x)$是非线性函数时，学习到的含有核函数的支持向量机是非线性分类模型。

也就是说，在核函数$K(x,z)$给定的条件下，可以利用解线性分类问题的方法求解非线性分类问题的支待向量机。学习是隐式地在特征空间进行的，不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧，它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。

核函数刨析

先验知识

希尔伯特空间：完备的、可能无限维的、定义了内积的线性空间。

知识扩展：函数空间

常用核函数

1. 多项式核函数

多项式核函数（polynomial kernel function）,如下：

$$ K(x,z) = (x\cdot z+1)^p $$

对应的支持向量机是一个$p$次多项式分类器。在次情形下，分类器决策函数为：

$$ f(x)=\operatorname{sign}\left(\sum_{i=1}^{N_{s}} a_{i}^{} y_{i}\left(x_{i} \cdot x+1\right)^{p}+b^{}\right) $$

2. 高斯核函数

高斯核函数(Gaussian kernel function).如下：

$$ K(x, z)=\exp \left(-\frac{|x-z|^{2}}{2 \sigma^{2}}\right) $$

对应的支持向量机是高斯径向基函数（radial basis function）分类器。在此情形下，分类决策函数成为

$$ f(x)=\operatorname{sign}\left(\sum_{i=1}^{N_{s}} a_{i}^{} y_{i} \exp \left(-\frac{\left|x-x_{i}\right|^{2}}{2 \sigma^{2}}\right)+b^{}\right) $$