统计学习方法笔记（十一）支持向量机（三）

非线性支持向量机与核函数

一、核技巧
1、非线性分类问题是指通过非线性模型才能很好的进行分类的问题。如下图所示：

很显然，不能通过直线（线性模型）将图示实例点进行分离，只能通过一条椭圆曲线。
在实际问题中，非线性问题往往很难求解，然而，如果我们可以先将其变成线性问题，再进行求解，那么问题就得到了解决。
使用线性分类方法求解非线性问题的步骤：首先使用一个变换将原空间的数据映射到新空间，然后在新空间用线性分类学习方法进行分类。核技巧就是这样的方法。
所谓的核技巧实际就是使用核函数的方法，将其应用到向量机，其实质就是通过一个非线性变换将输入空间（欧式空间）对应到一个特征空间（希尔伯特空间），使得在输入空间中的超曲面模型对于特征空间中的超平面空间。
2、核函数
定义：设X$\mathcal{X}$ 是输入空间，又设H$\mathcal{H}$ 为特征空间，如果存在一个映射：
ϕ(x):X→H$\varphi (x):\mathcal{X}\to \mathcal{H}$
使得对所有的x,z∈X$x,z\in \mathcal{X}$ ，函数K(x,z)$K(x,z)$ 满足条件
K(x,z)=ϕ(x)⋅ϕ(z)$K(x,z)=\varphi (x)\cdot \varphi (z)$
则称K(x,z)$K(x,z)$ 为核函数
核技巧的想法是通常只定义核函数，而不显式的定义映射函数。
3、核技巧在线性支持向量机中的应用
在对偶问题的目标函数中的内积xi⋅xj$x_i\cdot x_j$ 用核函数K(xi,zj)=ϕ(xi)⋅ϕ(zj)$K(x_i,z_j)=\varphi (x_i)\cdot \varphi (z_j)$ 代替，此时，对偶问题的目标函数变为：
W(α)=12∑i=1N∑j=1NαiαjyiyjK(xi,zj)−∑i=1Nαi$W(\alpha )=\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,z_j)-\sum _{i=1}^N{\alpha }_i$
二、正定核
通常所说的核函数就是指正定核
假设K(x,z)$K(x,z)$ 是定义在X×X$\mathcal{X}\times \mathcal{X}$ 的对称函数，对于任意的x1,x2,⋯,xm∈X$x_1,x_2,\cdots ,x_m\in \mathcal{X}$ ，K(x,z)$K(x,z)$ 关于x1,x2,⋯,xm$x_1,x_2,\cdots ,x_m$ 的Gram矩阵是半正定的，可以依据函数K(x,z)$K(x,z)$ 构造一个希尔伯特空间，其步骤是，首先定义映射ϕ$\varphi$ 构成向量空间S$\mathcal{S}$ ，然后在上面定义内积称为内积空间，最后将其完备化构成希尔伯特空间。
先定义映射：
ϕ:x→K(⋅,x)$\varphi :x\to K(\cdot ,x)$
根据这一映射定义线性组合：
f(⋅)=∑i=1mαiK(⋅,xi)$f(\cdot )=\sum _{i=1}^m{\alpha }_{i}K(\cdot ,x_i)$
之后在上面定义内积，使其称为内积空间
f(⋅)=∑i=1mαiK(⋅,xi)$f(\cdot )=\sum _{i=1}^m{\alpha }_{i}K(\cdot ,x_i)$
g(⋅)=∑j=1lβjK(⋅,zj)$g(\cdot )=\sum _{j=1}^l{\beta }_{j}K(\cdot ,z_j)$
定义运算*：
f∗g=∑i=1m∑j=1lαiβjK(xi,zj)$f\ast g=\sum _{i=1}^m\sum _{j=1}^l{\alpha }_i{\beta }_{j}K(x_i,z_j)$
将其完备化为希尔伯特空间
由于核K具有再生性，即满足：
K(⋅,x)⋅f=f(x)$K(\cdot ,x)\cdot f=f(x)$
K(⋅,x)⋅K(⋅,z)=K(x,z)$K(\cdot ,x)\cdot K(\cdot ,z)=K(x,z)$
三、常用核函数
多项式核函数：K(x,z)=(x⋅z+1)p$K(x,z)=(x\cdot z+1{)}^p$
高斯核函数： K(x,z)=exp(−||x−z||22σ2)$K(x,z)=\exp \left(-\frac{||x-z|{|}^2}{2{\sigma }^2}\right)$
字符串核函数

序列最小最优化算法

算法提出的原因：训练样本容量很大时，许多最优化算法非常低效，由此导致了SMO算法的提出。
算法的思路：SMO算法是一种启发式算法，如果所有变量的解满足最优化问题的KKT条件，则这个最优化的解就可以得到了，因为KKT条件是最优化问题的充分必要条件，如果不满足KKT条件，此时选择两个变量，固定其他变量，针对这两个变量构造一个二次规划问题，这个二次规划问题的解应该更接近于原始二次规划问题的解，因为这会使得原始二次规划问题目标函数的值更小，且此时子问题可以通过解析方法求解。子问题共有两个变量，一个是违反KKT条件最严重的那个，另一个则是由约束条件自动确定。
整个SMO算法共包括两个部分：求解两个变量的二次规划的解析方法以及选择变量的启发方法
一、两个变量二次规划的求解方法
子问题写为：

s.t.α1y1+α2y2=−∑i=3Nyiαi=ς$s.t.{\alpha }_1{y}_1+{\alpha }_2{y}_2=-\sum _{i=3}^N{y}_i{\alpha }_i=\varsigma$
对其求解即可
二、变量的选择方法
1、第一个变量的选择：选择违反KKT条件最严重的样本点
2、第二个变量的选择：选择|E1−E2|$|E_1-E_2|$ 最大时所对应的点
3、计算阈值和差值