BianC的日常

  • 首页
  • 机器学习
  • 摄影作品
  • 算法拾遗
  • 热爱生活
海的一边
分享科研与生活
  1. 首页
  2. 机器学习
  3. 正文

SVM 一瞥

2021-06-19 171点热度 1人点赞 0条评论

为什么从SVM开始呢,是因为之前听说SVM的中文“支持向量机”最早是由我的导师翻译过来的,如果没猜错的话应该是从关于统计学习理论与支持向量机这篇2000年的文章开始广泛传播的。不过在知网上也能搜到1999年李衍达院士写的交互支持向量机学习算法及其应用,但考虑到李先生是张老师的导师,具体是谁想出来的这个名字暂时也就无从考证了。

本文主要参考支持向量机通俗导论(理解SVM的三层境界)这篇来自CSDN的2012年的文章,写得十分深入浅出。我以学习的态度来写本文,既是为了重温一下经典的算法(谁知道去大厂面试的时候会不会考这个呢),也是为了试一下我这个新建的博客好不好用,以及$latex$打公式舒服不舒服。

线性可分的情况

首先,先理解一下最简单的情况下SVM是怎么工作的。
最简单的情况是两类样本、线性可分的情况,有一个超平面可以把两类样本切开,一类位于超平面之上,另一类位于超平面之下。之所以叫超平面是因为在三维以上的空间里,它不是平平的,而可能是想象不出来的样子。

线性可分示例

可以用平面方程来表示一个超平面 $w^\top x+ b = 0$ ,这里面$w$其实就是平面的法线向量,满足这个方程的所有点的坐标 $x$ 就构成了这个超平面,$x$ 是高维向量。也就是说,令 $f(x) = w^\top x+b$,那么使 $f(x)=0$ 的点在超平面上,使 $f(x)>0$ 的点在超平面一侧,使 $f(x)<0$ 的点在另一侧。

如果把上述两类样本第一类用$y = 1$,第二类用$y = -1$来标记,那么我们数据集中的N个点都可以写成$(x_i , y_i), i=1,2,..N$。$y_i f(x_i)$就可以用来代表$x_i$ 有没有被分到对的那一侧。因为对两类样本而言,如果分对了的话$yf(x)$为正,否则为负。令$\gamma_i = y_i f(x_i)$,$\gamma$可以看作是点到平面的距离,叫做functional margin,距离为正说明点远离平面,为负说明某一类点跑错了方向。令 $\hat{\gamma} = min(\gamma_i)$。$\hat{\gamma}$是所有点里面到平面距离最小的,试想如果连$\hat{\gamma}$都为正的,那么这个平面肯定能把两类点分开。而且如果$\gamma$很大的话,说明超平面把它们分得很开。进一步,用$\tilde{\gamma} = \frac{\hat{\gamma}}{||w||}$表示点到平面的几何距离,其实也就是把$w$从法向量变成了标准法向量。
我们还是希望$\tilde{\gamma}$越大越好,这也就是我们想要优化的目标:$max \ \tilde{\gamma}, s.t.\ \gamma_i = y_i (w^\top x_i +b) \geq \hat{\gamma}$。如果我们取一个阈值为1(方便计算),那么可以重新写优化问题为$max \ \frac{1}{||w||}, s.t.\ y_i (w^\top x_i +b) \geq 1, i = 1,…,N$。$\frac{1}{||w||}$就是最优的几何间隔。

最优超平面、支持向量

如图所示,中间实线是最优的超平面,两条虚线是满足$\ y_i (w^\top x_i +b) = 1$的点,也被称作支持向量。实线到虚线的距离就是几何间隔$\hat{\gamma}$,我们这里设的是1。在支持向量之外的点,必然都满足$\ y_i (w^\top x_i +b) > 1$

以上就是最简单的线性可分的情况。P.S. wordpress打latex公式着实不好用,因为没有自动补全和纠错,也没法即时编译观看,就有点烦。我现在先在overleaf上写,然后把内容粘贴进来,就方便很多了,基本是无缝衔接。

 

 

标签: 暂无
最后更新:2021-06-23

superbianc

弱水三千,只取一瓢

点赞
下一篇 >

COPYRIGHT © 2022 海的一边. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

京ICP备2021021901号-1