非线性支持向量机与序列最小最优化算法

(只突出与线性SVM不同的地方,具体的推导大部分过程相似见前面的讲线性SVM的文章)

线性(可分)SVM的分类平面是线性的,这就无法对如椭圆形特征空间进行分类,于是我们想到将原来特征空间$\mathbb X$(欧式空间$\mathbb R^n$或离散集合)上的非线性问题(超曲面模型),映射到新的高维特征空间$\mathbb H$(希尔伯特空间)成为线性可分(超平面模型)问题,这样我们就可以对新的线性可分的特征空间使用线性支持向量机的学习算法来解决非线性支持向量机的学习问题。(核技巧思想一)

核技巧

kernel trick

运用核技巧思想一,会发现如果我们想要直接计算映射,会非常困难。于是我们选择计算内积将输入空间中的内积转换为输出空间的内积),恰好在使用SVM学习算法的时候,无论是目标函数还是决策函数都只涉及输入实例与实例之间的内积,于是有以下方法——

在学习和预测中只定义核函数$K(x,z)$,而不显式定义映射函数$\phi$。因为通常直接计算核函数$K(x,z)$比较容易,而直接计算映射$\phi(x)和\phi(z)$并不容易。

观察到线性SVM的对偶问题中,无论是目标函数还是决策函数都只涉及输入实例与实例之间的内积,于是在对偶问题的目标函数中的内积$x_i·x_j$可以用核函数$K(x_i,x_j)=\phi(x_i)·\phi(x_j)$来代替。此时:

然后就只需要按照原来的线性可分SVM的学习算法,求对偶问题的外部问题,即求极值下的最优参数$\alpha^o$(可用SMO),然后再用KKT或等价求得$w^o,b^o$,得到超平面表达式

这等价于经过映射函数$\phi$将原来的输入空间变换到一个新的特征空间,将输入空间中的内积$x_i·x_j$变换为特征空间中的内积$\phi(x_i)·\phi(x_j)$

总结一下,核方法做了两件事:①样本空间映射到特征空间②计算了两样本在特征空间的内积(核技巧)

核技巧并不是SVM专用,可以用在其它地方

寻找核函数-正定核

函数$F(x,z)$满足什么条件才能成为核函数?也就是说对于映射函数$\phi$,直接计算$F(x,z)$即可而不用计算$\phi(x),\phi(z)$的条件是什么?

这种核函数一般都是正定核,直接给出结论:

正定核的充要条件:设$K:\mathbb X×\mathbb X\to \mathbb R$是对称函数,则$K(x,z)$为正定核函数的充要条件是对任意$x_i∈\mathbb X,i=1,2,\cdots,m,K(x,z)$对应的Gram矩阵

半正定矩阵(见后记-1)

正定核的等价定义:设$\mathbb X \subset \mathbb R^n,K(x,z)$是定义在$\mathbb X×\mathbb X$上的对称函数,如果对任意

$x_i∈\mathbb X,i=1,2,\cdots,m,K(x,z)$对应的Gram矩阵

半正定矩阵,则称$K(x,z)$是正定核

推导和证明略(先定义映射,构造向量空间;再构造内积空间;再完备化为希尔伯特空间;再在此之上证明)

这一定义在构造核函数的时候很有用,但要验证某函数是否为正定核函数是不容易的,因为要对所有输入集验证$K$对应的Gram矩阵是否为半正定矩阵。所以在实际问题中一般使用已有的核函数,见下

常用核函数

  1. 多项式核函数

  2. 高斯核函数

  3. 字符串核函数 O

    $k_n(s,t)$给出字符串$s$和$t$中长度为$n$的所有子串组成的特征向量的余弦相似度。两个字符串相似的字串越多,它们就越相似,字符串核函数的值就越大。

非线性支持向量机算法

第一部分即讲了与线性支持向量机算法的区别,用核函数替换内积即可,其它一样,略

序列最小最优化算法

sequential minimal optimization,SMO

思想:不断地将原多变量的二次规划问题分解为只有两个变量的二次规划子问题,并对子问题进行解析求解直到所有变量满足KKT条件为止(因为KKT条件是下面要求的最优化问题的充分必要条件)

目的:SMO算法主要是为了求解SVM中对偶问题的外部问题:

其中$\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T$,那么如何才能求得一个$\alpha_i$序列(也即向量$\alpha$)使得该问题为最优解呢?也即如何使得序列最小最优化

SMO是一个启发式算法,通过循环迭代的方式求得序列最优最小值。SMO输出的是一个近似解

算法:

知乎上看到一个讲得很好的,直接贴上来

  1. 两个二次规划变量的求解: https://zhuanlan.zhihu.com/p/78599113

    将其中一个作为变量来求解

    求解过程中设定的记号$v,g(x_i),E,\eta$都是为了方便表示求解过程,实际上求解思路就是

    ①将目标函数改写为记号表示形式(这里很复杂),$x_i,x_j分别为\alpha_1,\alpha_2$

    ②根据约束条件表示出$\alpha_1$,代入目标函数中,于是目标函数就只含$\alpha_1$变量

    ③对目标函数用对$\alpha_2$的0导数法,求得最优的$\alpha_2$表示

    ④上面求出的是未经剪辑的最优解,下一步求出经过剪辑的最优解即可

    注意:$k=\alpha_1^{old}-\alpha_2^{old},k=\alpha_1^{old}+\alpha_2^{old}$这个表示方法理解

  2. 变量的选择: https://zhuanlan.zhihu.com/p/78788836

    ①选取第一个变量$\alpha_1$的过程称为外层循环,选取违反KKT条件最严重的点

    ②选取第二个变量$\alpha_2$的过程称为内层循环,选取能使$\alpha_2$变化足够大的点(加快计算速度,使得目标函数尽快变小。根据公式$\alpha_2$依赖于$y_2(E_1-E_2)$,由于$\alpha_1$已定,那么$E_1$就定了,那么就可以选择合适的$\alpha_2$)

    如果第二个$\alpha_2$不能够使得目标函数有足够的下降,那就遍历数据集选取$\alpha_2$,如果遍历完了还没找到,那就通过外层循环重新寻找另外的$\alpha_1$

  3. 先选择变量,然后计算最优解,然后就要更新阈值$b$和差值$E_i$

总结:

先选择两个变量,再求解析解,直到达到停机条件(检验是否所有样本点都符合KKT条件,在精度$\epsilon$下进行)

具体略

后记

  1. 正定矩阵和半正定矩阵

    半正定矩阵:$A∈\mathbb R^{n×n},x∈\mathbb R^n$,对任意$x$,$x^TAx≥0$恒成立

    正定矩阵:$A∈\mathbb R^{n×n},x∈\mathbb R^n$,对任意$x$,$x^TAx>0$恒成立