理解SVM

考虑二分类问题，样本用向量$\boldsymbol{x}$表示，类比为$\boldsymbol{y}\in \{-1,1\}$，SVM的核心思想是：寻找一个超平面，定义一个“距离”，计算所有数据点到该平面的“距离”，使得其中最小的“距离”达到最大。

从函数间隔到几何间隔

首先考虑线性可分的情况。定义带有参数$\boldsymbol{w},b$的超平面$\boldsymbol{w}^{\top}\boldsymbol{x} + b$，给定第$i$个测试样本$(\boldsymbol{x}^{(i)}, y^{(i)})$，那么其到该平面到函数间隔（Functional Margin）为：

可以发现，如果对超平面对参数$\boldsymbol{w}, b$等比例地放大缩小，其实际作用不变（即不影响分类结果），但是函数间隔会随之变化，所以用如此定义的函数来衡量样本点到某分类超平面的“距离”并不可靠。因此，考虑将超平面等式归一化，因此就有了：

这个经归一化后的函数间隔被成为几何间隔（Geometric Margin），其可以很好地衡量样本点到某分类超平面到“距离”。

最优化问题

有了对样本点到超平面的“距离”的定义（可以理解成某样本点被正确分类的信心），就可以通过使离分类超平面最近的点到分类超平面的距离最大来求得一个最佳的分类超平面，于是就有了下面的最优化问题：

再进一步转化（个人感觉从归一化函数间隔的角度上来理解的话可以直接得到下面的形式）：

由于函数间隔可以任意缩放而不影响结果，因此不妨设$\hat{\gamma} = 1$，则优化目标变为了$\max_{\boldsymbol{w}, b}\frac{1}{\left|\boldsymbol{w}\right|}$，为方便后续求解，一般写成如下形式：

可以证明，该最优化问题的解是存在且唯一的。

松弛变量

由于在实际情况下样本可能无法做到线性可分，于是便引入了松弛变量（slack variables），其思想即是允许某些点到分类超平面的距离小于最优的分类间隔（甚至误分类），具体的优化问题可以表示成：

其中$\xi^{(i)}\geq 0$即松弛变量，其允许某些样本点不满足严格的间隔约束（此时$0 \leq \xi^{(i)} \leq 1$）或被误分类（此时$\xi^{(i)} > 1$）。而参数$C > 0$用于控制“最大化间隔”与“最小化松弛量”之间的权重。

核函数

除了采用线性分类器（即由线性函数定义的分类超平面），SVM还可以通过把数据点映射到高维空间以得到在原始空间中的非线性分类器。而不管在何种空间，我们定义分类器需要的都是点与面的距离而不是具体的映射函数，前者可以通过空间中的点积求得。我们定义从原始空间$\mathcal{X}$到特征空间$\mathcal{F}$的非线性映射$\phi: \mathcal{X} \to \mathcal{F}$，于是可以定义核函数（kernel function）以接收原始空间中的点为输入来计算其在特征空间中的点积：