支持向量机

支持向量机是一种比较经典的二分类模型，它的基本理论原理是定义在特征空间上的间隔最大的线性分类器。支持向量机由于核函数的存在，这使得它可以比较方便的处理非线性的数据。支持向量机学习路径可以归纳为由简单到复杂，分别为：线性可分支持向量机，线性支持向量机，非线性支持向量机。简单模型是复杂模型的基础，也是复杂模型的特殊情况。
当训练数据可分时，通过硬间隔最大化，训练一个线性的分类器，即线性可分支持向量机，又成为硬间隔支持向量机；当训练数据近似可线性分类的时候，通过软间隔最大化，也学习一个线性分类器；当数据线性不可分时候，通过核技巧以及软间隔最大化学习学习非线性支持向量机。

1 线性可分支持向量机

考虑一个二分类问题，假设输入空间与特征空间为两个不同的空间，输入空间为欧式空间或离散集合，特征空间为欧式空间或者希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间的元素映射到特征空间，非线性支持向量机利用一个从输入空间到特征空间的一个非线性映射函数获得特征向量。所以支持向量机的学习都是在特征空间上进行的。
假设给定一个数据集上的特征样本数据为：

T={(x1,y1),(x2,y2),...,(xn,yn)}$$T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$$

其中xiϵX=Rn$x_iϵX=R^n$，yiϵ{−1,1}$y_iϵ\{-1,1\}$，xi$x_i$为第i$i$个特征向量，yi$y_i$是xi$x_i$的类标签，取值为-1或者1。我们假设数据是线性可分支持向量机利用间隔最大化求最优分离超平面，这时解是唯一的。

1.1 线性可分支持向量机

给定线性可分训练集，通过间隔最大化或等价求解凸二次规划问题学习得到的分离超平面为：

w∗x+b∗=0$$w^{\ast }x+b^{\ast }=0$$

以及相应的决策函数

f(x)=sign(∗x+b∗)$$f(x)=sign{(}^{\ast }x+b^{\ast })$$

如上图，一般地，当数据集线性可分时，存在无穷多个超屏幕可将两类数据正确分开，线性可分支持向量机对应着将两类数据正确划分且间隔最大的直线。

1.2 函数间隔和几何间隔

一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度，在超平面wx+b=0$wx+b=0$的情况下，|wx+b|$|wx+b|$表示点到超平面的距离，而wx+b$wx+b$值得符号与y$y$的符号是否一致表示分类是否正确，所以可以用y(wx+b)$y(wx+b)$表示分类的正确性及确信度，这就是函数间隔的概念。

1.2.1 函数间隔

对于给定的训练集T和超平面(w,b)$(w,b)$，定义超平面(w,b)$(w,b)$关于样本点(xi,yi)$(x_i,y_i)$之间的函数间隔为：

γi=yi(wxi+b)$${\gamma }_i=y_i(w{x}_i+b)$$

定义样本集合T到超平面(w,b)$(w,b)$之间的函数距离为所有样本点到超平面的最小距离所以有:

γ=mini=1,2..,nγi=mini=1,2..,nyi(wxi+b)$$\gamma =mi{n}_{i=1,\mathrm{2..},n}{\gamma }_i=mi{n}_{i=1,\mathrm{2..},n}{y}_i(w{x}_i+b)$$

为了防止数据成比例增长，可以将其除以一个法向量||w||$||w||$
所以公式可以改写为：

γi=yi(wxi+b)||w||$${\gamma }_i=y_i\frac{(w{x}_i+b)}{||w||}$$

上面公式就是几何间隔。如果||w||=1$||w||=1$的时候，函数间隔和几何间隔相等。如果函数的w$w$和b$b$按比例增长，函数的函数间隔也会按比例增长，但是几何间隔并不会改变，因为其实此时的方程也没有变化。

1.2.2

支持向量机学习的基本思路是求解能够正确划分数据集并且几何间隔最大的分离超平面。
间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对数据进行分类。
下面考虑何如求解几何间隔最大化问题，具体的可以将问题表示为下面的约束最优化问题：

max(γ)$$max(\gamma )$$

yi(wxi+b)||w||>γ$$y_i\frac{(w{x}_i+b)}{||w||}>\gamma$$

考虑几何间隔和函数间隔的关系，也可以将问题改写为：

max(γ/||w||)$$max(\gamma /||w||)$$

yi(wxi+b)>γ$$y_i(w{x}_i+b)>\gamma$$

事实上函数间隔γ$\gamma$的改变，并不会影响最优化问题的解，也就是说，我们将γ$\gamma$取一个定制，可以转化为一个等价优化问题如下

min||w||2/2$$min||w|{|}^2/2$$

yi(wxi+b)−1>0$$y_i(w{x}_i+b)-1>0$$

这就是一个典型的凸二次优化问题

凸优化问题是指约束最优化问题：

minwf(w)$$mi{n}_{w}f(w)$$

gi(w)<=0$$g_i(w)<=0$$

hi(w)==0$$h_i(w)==0$$

当目标函数f(w)$f(w)$是二次函数时候，上述凸优化转换为凸二次最优化问题

1.2.3 支持向量和间隔边界

在线性可分情况下，训练数据集的样本中与分离超平面距离最近的样本点称为支持向量，所以支持向量是使得上面约束条件等号成立的点，即有：

yi(wix+b)−1=0$$y_i(w_{i}x+b)-1=0$$

因为数据集合中函数间隔的距离取得是所有样本点到超平面最小的几何距离。所以决定超平面时，其实只有超平面起到了作用，其他实例点并不起作用，所以我们将这种模型称为支持向量机。一般情况下，支持向量的个数会比较少，，所以支持向量机由很少重要的训练样本确定。

1.2.4 学习的对偶算法

为了求解线性可分支持向量机的最优化问题，将他作为原始的最优化问题，应用拉格朗日对偶性，通过求解对偶问题，得到原始问题的最优解。这是线性可分支持向量机的对偶算法。
首先构建拉格朗日函数，对每一个不等式的约束，引进拉格狼日算子αi${\alpha }_i$ i=1,2,..,N$i=1,2,..,N$，定义拉格朗日函数:

L(w,a,b)=12w2+∑i=1Nαi(1−(yi(wi+b)))$$L(w,a,b)=\frac{1}{2}{w}^2+\sum _{i=1}^N{\alpha }_i(1-(y_i(w_i+b)))$$

=12w2−∑i=1Nαiyi(wi+b)+∑i=1Nαi$$=\frac{1}{2}{w}^2-\sum _{i=1}^N{\alpha }_i{y}_i(w_i+b)+\sum _{i=1}^N{\alpha }_i$$

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

maxαminw,bL(α,w,b)$$ma{x}_{\alpha }mi{n}_{w,b}L(\alpha ,w,b)$$

为了优化上述问题，需要先求L(α,w,b)$L(\alpha ,w,b)$对w,b$w,b$取极小值，再求对α$\alpha$的极大值。
求w,b$w,b$的极小值：
对w,b$w,b$求导得：

ΛwL(w,b,a)=w−∑i=1Nαiyixi=0$${\mathrm{\Lambda }}_{w}L(w,b,a)=w-\sum _{i=1}^N{\alpha }_i{y}_i{x}_i=0$$

ΛbL(w,b,a)=−∑i=1Nαiyi=0$${\mathrm{\Lambda }}_{b}L(w,b,a)=-\sum _{i=1}^N{\alpha }_i{y}_i=0$$

得：

w=∑i=1Nαiyixi$$w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i$$

∑i=1Nαiyi=0$$\sum _{i=1}^N{\alpha }_i{y}_i=0$$

将上述式子代入原式得：

L(α,w,b)=−1/2∑i=1N∑i=1Nαiαjyiyj(xixj)+∑i=1Nαi$$L(\alpha ,w,b)=-1/2\sum _{i=1}^N\sum _{i=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i{x}_j)+\sum _{i=1}^N{\alpha }_i$$

上面方程需要对α$\alpha$求极大值，则有:

maxα−1/2∑i=1N∑i=1Nαiαjyiyj(xixj)+∑i=1Nαi$$\underset{\alpha }{max}-1/2\sum _{i=1}^N\sum _{i=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i{x}_j)+\sum _{i=1}^N{\alpha }_i$$

∑i=1Nαiyi=0$$\sum _{i=1}^N{\alpha }_i{y}_i=0$$

上面的方程可以转换为与之等价的二次凸优化问题的等价问题：

minα1/2∑i=1N∑i=1Nαiαjyiyj(xixj)−∑i=1Nαi$$\underset{\alpha }{min}1/2\sum _{i=1}^N\sum _{i=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i{x}_j)-\sum _{i=1}^N{\alpha }_i$$

∑i=1Nαiyi=0$$\sum _{i=1}^N{\alpha }_i{y}_i=0$$