为什么从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上写，然后把内容粘贴进来，就方便很多了，基本是无缝衔接。
