目标

非线性二分类

原理

  • 核技巧

    非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。

    非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。

    用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。

    核技巧应用到支持向量机，其基本想法就是通过一个非线性变换将输入空间（欧式空间\(R^n\)或离散集合）对应于一个特征空间（希尔伯特空间\(H\))，使得在输入空间\(R^n\)中的超曲面模型对应于特征空间\(H\)中的超平面模型（支持向量机）。

    设\(\X\)是输入空间（欧式空间\(\R^n\)的子集或离散集合），又设\(H\)为特征空间（希尔伯特空间），如果存在一个从\(X\)到\(H\)的映射

    \[\phi(x): X \to H\]

    使得对多有\(x,z \in X\)，函数\(K(x,z)\)满足条件

    \[K(x,z)=\phi(x) \bullet \phi(z)\]

    则称\(K(x,z)\)为核函数，\(\phi(x)\)为映射函数，式中\(\phi(x) \bullet \phi(z)\)为\(\phi(x)\)和\(\phi(z)\)的内积。

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

  • 核技巧在支持向量机中的应用

    我们注意到在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例和实例之间的内积。在对偶问题的目标函数中的内积\(x_i \bullet x_j\)可以用核函数\(K(x,z)=\phi(x) \bullet \phi(z)\)来代替。此时对偶问题的目标函数成为

    \[W(\alpha)=\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j) - \sum_{i=1}^N \alpha_i\]

    同样，分类决策函数中内积也可以用核函数代替，而分类决策函数式成为

    \[f(x)=sign(\sum_{i=1}^{N_s} \alpha_i^* y_i \phi(x_i) \bullet \phi(x) + b^*) = sign(\sum_{i=1}^{N_s} \alpha_i^* y_i K(x_i, x) + b^*)\]

    这等价于经过映射函数\(\phi\)将原来的输入空间变换到一个新的特征空间，将输入空间中的内积\(x_i \bullet x_j\)变化为特征空间的内积\(\phi(x_i) \bullet \phi(x_j)\)，在新的特征空间里从训练样本中学习线性支持向量机。当映射函数是非线性函数时，学习到的含有核函数的支持向量机是非线性分类模型。

    也就是说，在核函数\(K(x,z)\)给定的条件下，可以利用解线性分类问题的方法求解非线性分类问题的支持向量机，学习是隐式地在特征空间进行的，不需要显示地定义特征空间和映射函数，这样的技巧称为核技巧，它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。

正定核

通常所说的核函数就是正定核函数（positive definite kernel function）

正定核的充要条件：设\(K: X \times X \to R\)是对称函数，则\(K(x,z)\)为正定核函数的充要条件是对任意\(x_i \in X, i=1,2,...,m\)，\(K(x,z)\)对应的Gram矩阵:

$$K=[K(x_i,x_j)]_{m\times m}

是半正定矩阵。

正定核的等价定义：设\(X \subset R^n\)，\(K(x,z)\)是定义在\(X \times X\)上的对称函数，如果对于任意\(x_i \in X, i=1,2,...,m\)，\(K(x,z)\)对应的Gram矩阵:

$$K=[K(x_i,x_j)]_{m\times m}

是半正定矩阵，则称\(K(x,z)\)是正定核。

常用的核函数

  1. 多项式核函数（polynomial kernel function）
\[K(x,z) = (x \bullet z +1)^P\]

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

\[f(x)=sign(\sum_{i=1}^{N_s} \alpha_i^* y_i (x_i \bullet x +1)^P + b^*)\]
  1. 高斯核函数（Gaussian kernel function）
\[K(x,z)=exp(-\frac{\|x-z\|^2}{2\sigma^2})\]

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

\[f(x)=sign(\sum_{i=1}^{N_s} \alpha_i^* y_i exp(-\frac{\|x-z\|^2}{2\sigma^2}) + b^*)\]
  1. 字符串核函数（string kernel function）

核函数不仅可以定义在欧式空间上，还可以定义在离散数据的集合上。字符串核是定义在字符串集合上的核函数。字符串核函数在文本分类、信息检索、生物信息学等方面都有应用。