机器学习--支持向量机理论知识(四)

机器学习 | 支持向量机理论知识(四)

大家好,之前我们进行了线性支持向量机的学习,今天我们一起来学习非线性支持向量机。

非线性向量机的主要特点是利用核技巧(kernel trick)。为此,先要介绍核技巧。核技巧不仅应用于支持向量机,而且应用于其他统计学习问题。

核技巧

非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。如下面的左图所示:

捕获

由图可见,无法用直线(线性模型将正负实例正确分开,但可以用一条曲线(非线性模型)将它们正确分开。

非线性问题往往不好求解,希望能够通过某种变换将非线性问题变换为线性问题,通过解变换后的线性问题的方法求解原来的非线性问题。如上图所示,将左图中的曲线变成了右图中的平面,即把非线性分类问题变换成了线性分类问题。这样的方法即为核技巧,这样的变换函数即为核函数。

核函数定义:设\(\chi\)是输入空间(欧式空间\(R^n\)的子集或离散集合),又设\(H\)为特征空间(希尔伯特空间),如果存在一个从\(\chi\)\(H\)的映射: \[ \phi(x):\chi\longrightarrow H \] 使得对所有\(x,z\in\chi\),函数\(K(x,z)\)满足条件: \[ K(x,z) = \phi(x)·\phi(x) \] 则称\(K(x,z)\)为核函数,\(\phi(x)\)为映射函数,式中\(\phi(x)·\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·x_j\)可以用核函数\(K(x_i,x_j) = \phi(x_i)·\phi(x_j)\)来代替。此时对偶问题的目标函数成为: \[ W(\alpha) = \frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum^N_{i=1}\alpha_i \] 同样,分类决策函数中的内积也可以用核函数代替,而分类决策函数式成为: \[ f(x) = sign(\sum^{N_s}_{i=1}a^*_iy_i\phi(x_i)·\phi(x)+b^*) = sign(\sum^{N_s}_{i=1}a^*_iy_iK(x_i,x)+b^*) \] 这等价于经过映射函数\(\phi\)将原来的输入空间变换到一个新的特征空间,将输入空间中的内积\(x_i·x_j\)变换为特征空间中的内积\(\phi(x_i)·\phi(x_j)\),在新的特征空间里从训练样本中学习线性支持向量机。当映射函数是非线性函数时,学习到的含有核函数的支持向量机是非线性分类模型。在实际应用中,往往依赖领域知识直接选择核函数,核函数选择的有效性需要通过实验验证。

常用核函数

  1. 多项式核函数

\[ K(x,z) = (x·z+1)^p \]

对应的支持向量机是一个p次多项式分类器。在此情形下,分类决策函数成为: \[ f(x) = sign(\sum^{N_s}_{i=1}a^*_iy_i(x_i·x+1)^p+b^*) \]

  1. 高斯核函数

\[ K(x,z) = exp(-\frac{||x-z||^2}{2\sigma^2}) \]

对应的支持向量机是高斯径向基函数分类器。在此情形下,分类决策函数成为: \[ f(x) = sign(\sum^{N_s}_{i=1}a^*_iy_iexp(-\frac{||x_i-x||^2}{2\sigma^2})+b^*) \]

  1. 字符串核函数

核函数不仅可以定义在欧式空间上,还可以定义在离散数据的集合上,比如,字符串核是定义在字符串集合上的核函数。字符串核函数在文本分类、信息检索、生物信息学等方面都有应用。字符串核函数\(k_n(s,t)\)给出了字符串s和t中长度等于n的所有子串组成的特征向量的余弦相似度。直观上,两个字符串相同的子串越多,他们就越相似,字符串核函数的值就越大。字符串核函数可以由动态规划快速的计算。

非线性支持向量机

利用核技巧,可以将线性分类的学习方法应用到非线性分类问题中去。将线性支持向量机拓展到非线性支持向量机,只需将线性支持向量机对偶形式中的内积换成核函数。

非线性支持向量机学习算法

输入:训练数据集\(T = {(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}\),其中\(x_i\in\chi=R^n\)\(y_i\in Y = \lbrace -1,+1\rbrace,i =1,2,...,N\)

输出:分类决策函数。

(1)选取适当的核函数\(K(x,z)\)和适当的参数\(C\),构造并求解最优化问题: \[ min_a\quad\frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum^N_{i=1}\alpha_i\quad\\s.t.\quad\sum^N_{i=1}\alpha_iy_i = 0\\\quad0\le\alpha_i\le C,i = 1,2,...,N \] 求得最优解\(\alpha^* = (\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T\)

(2)选择\(\alpha^*\)的一个正分量\(0 < \alpha_j^*<C\),计算: \[ b^* = y_j-\sum^N_{i=1}\alpha_i^*y_iK(x_i·x_j) \] (3)构造决策函数: \[ f(x) = sign(\sum^{N}_{i=1}a^*_iy_iK(x·x_i)+b^*) \]\(K(x,z)\)是正定核函数时,以上三个式子是凸二次规划问题,解是存在的。

以上便是今天的内容,谢谢大家的观看~