支持向量机

ryluo 2020-08-25 16:52:59

感知机

感知机模型是支持向量机和神经网络的基础,但是由于感知机模型只能应用于线性可分的情况,所以感知机模型在实际的应用比较少,但是是后续很多机器学习算法的基础。

感知机模型的核心思想:

能够找到一条直线或者一个超平面将数据分成正负两类。感知机模型的函数表示为(将w和x都增加一个维度可以将函数进行简化):

其中sign(x)表示的是符号函数,即:

感知机模型的损失函数:

感知机模型优化的目标是:使得所有误分类的样本到超平面距离之和最小

由上述感知机模型的定义可知:

所以不论$w\cdot x $的取值如何,对于分类错误的样本都满足$y*w\cdot x<0$,又因为任意样本点到分类超平面的距离可以定义为:

所以如果假设所有误分类样本的集合为M,那么所有误分类点到分类超平面的距离为:

由于上式中分子分母中都含有$w$并且分子的$w$增大$N$倍,分母的$||w||_2$也会增大$N$倍,所以为了简化公式,可以固定分子或者分母中的某个$w$的关系为1,然后让剩下的$w$的式作为最终的损失函数,所以感知机最终的损失函数表示为:

损失函数的优化:

通过上述的分析,得到了感知机模型的损失函数,其本质的含义是使得所有误分类样本点到分类超平面的距离之和最小,根据损失函数其实可以通过随机梯度下降的方法对损失函数进行优化。

损失函数相对于参数的偏导数为:

若设置学习率为$\alpha$,则参数的更新公式为:

感知机算法的步骤:

  1. 初始化感知机的参数和学习率
  2. 在数据集中选择一个误分类的点,使用改点来更新模型的参数
  3. 检查数据集中是否还有误分的点,如果没有算法就结束了,如果含有就不断的执行2

支持向量机

通过上面感知机模型的学习,会发现感知机模型通过使用误分类点对模型参数进行更新,每次通过跟新一点超平面的位置来减少误分类样本的数量,从原理上就可以发现,这种情况对于线性不可分的情况可能会使得算法进入死循环,此外如果可以通过一个分类超平面将数据正确的分离开,那么满足这个条件的超平面就不止一个,那么这么多的分类超平面中如何选择一个最优的超平面呢?如何定义一个最优的超平面呢?

函数间隔与几何间隔:

函数间隔:

几何间隔:

即在感知机算法中,模型的优化目标是几何间隔。

支持向量:

由于感知机算法在线性可分的情况下,可以得到多个满足将数据分离开的超平面,但是线性可分的SVM算法不仅要正确的将数据分离开,还需要尽可能使得正负样本之间的距离都尽可能的离分类超平面更远。如下图所示,$w^Tx+b=0$分类超平面已经将正负样本数据正确的分离开,此外,分类超平面离最近的正负样本都有一定的距离,正负样本中离分类超平面最近的点到分类超平面的距离为$\frac{1}{||w||_2}$,而离分类超平面最近的这些点就被成为支持向量(因为样本点本身就是一个向量表示),所以两个支持向量之间的距离为$\frac{2}{||w||_2}$。

image-20200825215139001

支持向量机的目标函数及优化方法:

上面已经说了支持向量机是最大化分类间隔,大致的意思就是使得数据中所有的样本点离分类间隔的距离都大于等于某个设定的值,为了模型的推导方便将该间隔设置为1,所以支持向量机的优化目标为:

可以转化为:

上面的式子是一个带约束的最小化问题,约束条件可以转化为$1-y_i(wx_i + b) \le 0$

由拉格朗日乘子法将约束问题转化为无约束问题:

所以上述可以写成最大最小求解问题:

因为求解的问题是一个二次的,并且条件是线性条件,所以求解模型满足强对偶关系,即最大最小的最优解等于最小最大的最优解,即:

首先计算$\min_{w,b} L(w,b,\lambda)$

对$w$和$b$分别求偏导,并令其为零有:

将上面两个式子带入到$(1)$式中可得:

再计算$max_{\lambda} L(w,b,\lambda)$

由于原问题与对偶问题满足强对偶关系,所以对偶问题满足KKT条件,如下是KKT条件:

对于上述KKT条件进行讨论:

  1. 当$1-y_i(wx_i+b) < 0 $时,$\lambda_i$恒等于0,对于公式(1)会发现目标函数与$\lambda$无关,只和$w$有关,此时不是最优解
  2. 当$1-y_i(wx_i+b) = 0 $时,$\lambda_i > 0$, 此时目标函数与$\lambda$相关,存在最优解

由$1-y_i(wx_i+b) = 0 $可以推出:

其实满足$1-y_i(wx_i+b) = 0 $条件的点,就是支持向量,如上图中所示的支持向量。

综上所述,支持向量机的最优解为:

分类超平面方程为:


参考资料:

刘建平博客支持向量机章节

https://www.cnblogs.com/pinard/p/6097604.html

机器学习-白板推导系列(六)-支持向量机SVM(Support Vector Machine)

https://www.bilibili.com/video/BV1Hs411w7ci?p=1

《统计机器学习》