周志华西瓜书学习笔记（六）

支持向量机

6.1间隔与支持向量

1.线性可分

在这里插入图片描述

如图所示，要将两类点分开，有很多直线都能做到。但是，如果希望训练出一条直线在测试集上也有很好的表现，应该找位于两类训练样本“正中间”的直线，也称划分超平面。这个划分超平面所产生的分类结果是最鲁棒的，为未见示例泛化能力越强。

名词介绍

鲁棒性：鲁棒是Robust的音译，也就是健壮和强壮的意思。它也是在异常和危险情况下系统生存的能力。比如说，计算机软件在输入错误、磁盘故障、网络过载或有意攻击情况下，能否不死机、不崩溃，就是该软件的鲁棒性。

2.支持向量

划分超平面的线性方程式： $w^Tx+b=0$

对一个划分平面，每个分类点到划分平面的距离是 $r=\frac{|w^Tx+b|}{||w||}$ ?
在这里插入图片描述

如图所示，距离超平面最近的这几个训练样本点称为“支持向量”。

超平面参数成倍数变化，表示的是同一条直线。如 $2x_1+4x_2-8=0$ ??与 $x_1+2x_2-4=0$ ?表示的是同一个划分超平面，所以可以通过对参数的调整，使得支持向量机到划分超平面的距离为1。即 $r=\frac{|w^Tx+b|}{||w||}=\frac{1}{||w||}$ ，也就是说两个异类支持向量机到超平面的距离之和为 $\gamma=\frac{2}{||w||}$ ?

我们要做的优化就是在满足划分正确的前提下，使这个距离 $\gamma=\frac{2}{||w||}$ ?最大化

SVM基本型
$min_{w,b}\ \ \frac{1}{2}||w||^2\\ s.t.\ \ y_i(w^Tx_i+b)≥1,i=1,2……,m$

6.2对偶问题

1.拉格朗日乘数法

在这里插入图片描述

推导：

由上式(6.11)对偶形式可知，
$\left\{ \begin{array}{c} \alpha_i≥0;\\ y_if(x_i)-1≥0;\\ \alpha_i(y_if(x_i)-1)=0. \end{array} \right.$
上便是不等式约束优化优化问题的 KKT(Karush-Kuhn-Tucker) 条件， $\alpha$ ???称为 KKT 乘子。第一个约束是拉格朗日乘数法自身约束，第二个约束是SVM基本型自带的约束，第三个约束说明：对任意训练样本 $x_i;y_i)$ ???，必有 $\alpha=0$ ??或 $y_if(x_i)=1$ ??.若 $\alpha\_i=0$ ??，则该样本将不会在式(6.12)的求和中出现，也就不会对f(x)有任何影响；若 $\alpha_i＞0$ ?，则必有 $y_if(x_i)=1$ ?，所对应的样本点位于最大间隔边界.上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。

2.SMO算法求解

SMO(Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。

选择两个需要更新的参数 $\alpha_i$ ?和 $\alpha_j$ ?，固定其他参数。

SMO的思路是每次更新一个参数，为什么要选取两个参数？

因为我们的优化目标有约束条件： $\sum_{i=1}^n\alpha_iy_i=0$ (见式6.10)，所以我们一次需要选择两个参数

于是我们有以下约束：

$\alpha_iy_i+\alpha_jy_j=c\ \ \ \lambda_i≥0；\lambda_j≥0$ ?。其中 $c=-\sum_{k≠i,j}\alpha_ky_k$ 。

由此也可以推导出 $\alpha_j=\frac{c-\alpha_iy_i}{y_j}$ ，即我们可以用 $\alpha_i$ 来表示 $\alpha_j$ 。这样就相当于把目标问题转化成了仅有一个约束条件的最优化问题，仅有的约束是 $\alpha_i≥0$
固定除 $\alpha_i$ 和 $\alpha_j$ 以外的参数，求解 $\alpha_i$ 和 $\alpha_j$ 。即将 $\alpha_i$ 和 $\alpha_j$ 代入优化目标6.11式，对于仅有一个约束条件的最优化问题，可以对优化目标求偏导，令导数为零，从而求解。
选取其他参数，迭代更新直至收敛。
我们求偏导数时得 $w=\sum_{i=1}^m\alpha_iy_ix_i$ ，由此可以求得w。
找一个支持向量 $x_s,y_s)$ ，对支持向量而言，此时 $\alpha_s＞0$ ?，所以有 $y_s(wx_S+b)=1$ 。

两边各乘以 $y_s$ ，得 $y_s^2(wx_S+b)=y_s$ 。因为 $y_S^2=1$ 。所以 $b=y_s-wx_s$ 。

为了更具鲁棒性，可以使用所有支持向量求解的平均值： $b=\frac{1}{|S|}\sum_{s\in S}(y_s-wx_s)=\frac{1}{|S|}\sum_{s\in S}(\frac{1}{y_s}-\sum_{i\in S}\alpha_iy_ix_i^Tx_s)$ ?

6.3软间隔与正则化

1.软间隔

对于一些线性不可分的情况，我们允许部分样本点不满足约束条件： $1-y_i(w^Tx_i+b)\leq0$
在这里插入图片描述

为了度量这个间隔软到何种程度，我们为每个样本引入一个松弛变量，因此优化目标可以写为：

$min_{w,b,\xi_i}\ \ \frac{1}{2}\Vert w \Vert^2+ C\sum_{i=1}^m\xi_i$ ，其中 $\xi_i \geq0$ 为松弛变量，也代表了一种损失函数。而损失函数的具体形式有多种，
在这里插入图片描述

因此，可以得到软支持向量机的基本形式：
$\left\{ \begin{array}{c} min_{w,b,\xi_i}\ \ \frac{1}{2}\Vert w\Vert^2+C\sum_{i=1}^m\xi_i\\ s.t.\ \ y_i(w^Tx_i+b)\ge1-\xi_i\\ \xi_i\ge0,i=1,2…,m \end{array} \right.$

2.优化目标及求解

通过拉格朗日乘子法求解，得
在这里插入图片描述

将各片偏导结果代入拉格朗日函数中，得到
在这里插入图片描述

我们可以看到软间隔和硬间隔形式一样，两者唯一的区别就在于对偶变量的约束不同：前者是 $0\le\alpha_i\le C$ ，后者是 $0\le \alpha_i$ ，于是可以采取同样的SMO算法求解。

在这里对软支持向量机，有如下KKT条件要求在这里插入图片描述

于是，对任意训练样本 $x_i,y_i)$ ????，总有 $\alpha_i=0$ ????或 $y_if(x_i)=1-ξ_i$ ????。若 $\alpha_i=0$ ????，则该样本不会对f(x)有任何影响；若 $y_if(x_i)=1-ξ_i$ ????，即该样本是支持向量：由式(6.39)可知，若 $\alpha_i < C$ ??,则 $μ_i> 0$ ??,进而有 $\xi_i=0$ ??，即该样本恰在最大间隔边界上；若 $\alpha_i=C$ ??,则有 $μ_i=0$ ??，此时若 $\xi_i\le1$ ??则该样本落在最大间隔内部，若 $\xi_i> 1$ ?则该样本被错误分类。由此可看出，软间隔支持向量机的最终模型仅与支持向量有关，即通过采用hinge损失函数仍保持了稀疏性。

使用SMO算法继续求解得：
$\left\{ \begin{array}{c} w=\sum_{i=1}^m\alpha_iy_ix_i\\ b=\frac{1}{|S|}\sum_{s\in S}(y_s-wx_s) \end{array} \right.$
由此确定划分超平面。由求w的那个式子可看出，只要 $\alpha_i>0$ 的点都能够影响我们的超平面，因此都是支持向量。