支持向量机 | 陈浩然的博客

支持向量机

概念引入

支持向量机(support vector machine 简称 SVM)是我一直想写但是没写的内容,它的数学推导较为复杂,理论意义没有之前线性回归、决策树那样明显,但却是传统机器学习中几乎最为强大的方法

支持向量机这个名字听起来较为奇怪,但是他却有深层次的含义,在之后会详细介绍。

如图所示,如果我们要进行一个分类的学习任务,将图中两种类别的样本分开,需要学习一个超平面,结果可能如$H_1,H_2,H_3$所示,如果仅仅以训练集来看三个分类器,他们没有任何差别,都是100%准确率,但从直觉上来看,位于中间的$H_3$似乎是最好的,因为它和任何样本的距离都比较远,其鲁棒性最强。

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

支持向量机的任务就是找到一个位于正中间的超平面,使之与任何样本之间都有较大间隔,以提高算法鲁棒性,所以又被称为最大间隔分类器

目标

尽管SVM的概念较为复杂,但是SVM的推导对于其理解还是有重要作用的,下面我们一步一步进行推导。

我们知道,任何空间中的超平面都可以由以下方程代表:
$$
\vec w^T \vec x + b=0
$$
所以一个样本点x(它在样本空间中的坐标由其各个属性决定)距离该超平面的距离为:
$$
r = \frac {|\vec w^T \vec x + b|} {||\vec w||}\\
(该公式和高中点到直线公式相同)
$$
对于一般的分类器(非SVM),我们要求在$y=1(标记为正)时,\vec w^T \vec x + b > 0,y=-1时,\vec w^T \vec x + b < 0 $,但是对于SVM,我们有更强的要求,即
$$
\begin{cases}
\vec w^T \vec x + b \ge 1&y=1\\
\vec w^T \vec x + b \le -1&y=-1
\end{cases}
$$
可以看出,SVM对算法预测的要求比一般的学习器要高,如果我们把上述两个式子看做个超平面,如下图所示,图中的红蓝两条线,SVM的要求就是,使所有的样本都出现在红蓝两条线之外,并且两条线的间隔要尽可能大,这也就是“最大间隔分类器”名称的由来。

图中两条线的间隔为:
$$
d=\frac {2} {||\vec w||}
$$
我们的目标正是最大化该式,max{d}。

数学推导

由上可知,我们的目标是:由上可知,我们的目标是:
$$
max_{w,b} \; d=\frac {2} {||\vec w||}\\
st \; y_i(\vec w^T \vec x_i + b) \ge 1\\
(将SVM的要求两式合成一式)
$$
实际上等价于最大化w:
$$
min_{w,b} \; \frac 12 {||\vec w||^2}\\
st \; y_i(\vec w^T \vec x_i + b) \ge 1\\
$$
$\frac 12$是为了求导方面添加的系数。

如何求解这个模型呢?显然,这是一个凸二次规划问题,可以使用拉格朗日乘子法来解决,添加系数$\alpha$:
$$
L(w,b,a)=\frac 12 ||\vec w||^2 +\sum_{i=1}^{m}\alpha_i(1-y_i(\vec w^T \vec x_i + b))
$$

接下来使用常规的拉格朗日解法即可,函数L对w,b求偏导,得到:
$$
\vec w = \sum_{i=1}^m \alpha_iy_i\vec x_i\\
\sum_{i=1}^m \alpha_iy_i = 0
$$
然后带入原式中,可以将目标问题化为其对偶问题,即:
$$
max_{\alpha} \; \sum_{i=1}^m {\alpha_i}-\frac 12 \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_jy_i y_jx_i^T x_j\\
st.\;\alpha_i > 0\;;\sum_{i=1}^m \alpha_iy_i = 0;
$$
观察这个式子可知:

  • 该式子中未知变量只有$\alpha$,我们要寻找$\alpha$使式子最大化
  • 一旦求出$\alpha$,即可算出$\vec w$和b,模型即得到求解

模型解释(选看)

那么,我们该如何理解这个模型呢,最主要的一个疑问是,为什么模型的名字叫做支持向量机?

为了求解模型:
$$
L(w,b,a)=\frac 12 ||\vec w||^2 +\sum_{i=1}^{m}\alpha_i(1-y_i(\vec w^T \vec x_i + b))
$$
我们使用了拉格朗日乘子法,由于$1-y_i(\vec w^T \vec x_i + b) \le 0$,满足KKT条件,即:
$$
\alpha_i \ge 0\\
y_i(\vec w^T \vec x_i + b)-1 \ge 0\\
\alpha_i(y_i(\vec w^T \vec x_i + b)-1)=0
$$
观察该方程组可以看到

  1. 要么$\alpha_i=0$,要么$y_i(\vec w^T \vec x_i + b)-1=0$,两者必须满足其中一个
  2. 如果$\alpha_i=0$,则该样本点$\vec x_i$没有被使用,即该样本对于构建后的SVM没有作用
  3. 如果$y_i(\vec w^T \vec x_i + b)-1=0$,即$y_i(\vec w^T \vec x_i + b)=1$,该样本正好处于最大间隔的分类处,而SVM与这些样本有关

综上可知,所谓的支持向量机,指的就是该模型仅由支持向量决定,即$\alpha_i\ne0$的向量,这些向量被称为支持向量

SMO算法求解

那么,该如何求得这个对偶问题呢?
$$
max_{\alpha} \; \sum_{i=1}^m {\alpha_i}-\frac 12 \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_jy_i y_jx_i^T x_j\\
st.\;\alpha_i > 0\;;\sum_{i=1}^m \alpha_iy_i = 0;由、、、
$$
可以看出这是一个二次规划问题,最好的求解方法是SMO算法。

  1. 选择一对需要更新的变量$\alpha_i和\alpha_j$
  2. 固定除了这两个变量外其他所有变量(即看做常量),将问题简化
  3. 求解简化后的问题,并更新$\alpha_i和\alpha_j$
  4. 重复1/2/3步骤直到收敛

当我们将$\alpha_i和\alpha_j$固定了之后,问题中的约束被简化为
$$
\alpha_iyi+\alpha_j y_j=c(c是一个常数)
$$
这是问题被简化为高中学过的二次函数求最值的问题,很容易求解。

在求解得到$\alpha$之后,利用支持向量的关系:
$$
y_i(\vec w^T \vec x_i + b) = 1 (该式子仅对于支持向量成立)
$$
即可求得b,当然也可以用所有支持向量求解的平均值。

至此,朴素形式的SVM求解完成

核函数优化

SVM的本质,依旧是在空间中找到一个超平面,将样本点分开。那么是否存在找不到这种超平面的情况呢?

如图所示,异或问题的求解在二维平面便找不到可以划分的直线,但是如果选用适当的三维空间,便可以找到一个合适的平面来分开正负样本。

核函数便是这样的思想,将样本从原始的特征空间映射到高维的样本特征空间,来有效划分不同的样本,假设映射函数为h(x),那么对应的超平面可以表示为:
$$
f(x)=\vec w ^Th(x)+b
$$
将前几节中所有模型中的x换成h(x),即可得到升维之后的模型

但是这里出现了一个困难,$x_i^T x_j$变成了$h(x_i)^Th(x_j)$之后,计算可能是很困难的,因为映射后的特征空间是很多维甚至是无穷维。

为了解决该问题,引入核函数
$$
令\kappa(x_i,x_j)=h(x_i)^Th(x_j)
$$
之后在所有问题中,我们都可以利用核函数来计算$h(x_i)^Th(x_j)$即可。核函数的本质就是高维空间中两个向量的内积。

有很多常用的核函数,例如:

  • 线性核:$$\kappa(x_i,x_j)=x_i^Tx_j$$
  • 高斯核:$$\kappa(x_i,x_j)=e^{-\frac {||x_i-x_j||^2} {2\sigma^2}}$$
  • 多项式核:$$\kappa(x_i,x_j)=(x_i^Tx_j)^d$$
  • sigmoid核:$$\kappa(x_i,x_j)=tanh(\beta x_i^Tx_j+\theta)$$

在真实的机器学习任务中,也可以通过这些核函数的线性组合,直积等来组合成新的核函数。

软间隔支持向量

在之前的SVM中,要求的都是必须满足间隔的约束,但是有可能有一些任务不可能满足所有的样本点,这时,可以适当降低要求,允许部分样本点出错——出现在间隔线内部,只需要给他们一个损失替代函数即可。

如下图所示,列出了常用的四种损失函数,仔细观察可以看出,这些损失函数在在$z\le1$时都会有大量损失,而在$z\ge1$之后,损失迅速下降。

软间隔支持向量和之前的推导很相似,在这里不详细讲述。

一般形式支持向量

实际上,支持向量机可以被表述为更为一般的形式:
$$
min_f\; \Omega(f)+C\sum_{i=1}^m l(f(x_i),yi)
$$

  • $\Omega(f)$为结构风险,用于描述模型的性质,例如$\frac 12 \omega^2$,这里用来显示间隔的大小
  • $\sum_{i=1}^m l(f(x_i),yi)$为经验风险,用于描述模型和数据的契合程度,例如软间隔支持向量中的损失函数
  • C为正则化常数,用于控制前面两者的比例,防止过拟合和欠拟合。

查看更多

所有的文章都会在我的博客和我的知乎专栏同步进行更新,欢迎阅读


本文结束啦感谢您的阅读
生活不易,求打赏
0%