支持向量机（SVM）

机器学习

---

1. 间隔与支持向量
   给定训练样本集 $D=\{(x_1,y_1),(x_2,y_2)...,(x_m,y_m)\}, y\in \{-1,+1\}\}$, 分类学习最基本的想法就是基于训练集 $D$在样本空间中找到一个划分超平面，将不同类别的样本分开。
   需要找到划分结果最鲁棒，对未见示例的泛化能力最强的超平面。
   在样本空间中，划分超平面可通过如下线性方程来描述：
   $$w^T+b=0$$
   其中$w=(w_1;w_2;...;w_d)$为法向量，决定了超平面的方向；$b$为位移项，决定了超平面与原点之间的距离。显然，划分超平面可被法向量$w$和位移$b$确定。我们将其记为$(w,b)$。样本空间中任一点$x$到超平面$(w,b)$的距离可写为：
   $$r=\frac{|w_Tx+b|}{||w||}$$
   假设超平面$(w,b)$能将训练样本正确分类，即对于$(x_i,y_i)\in D$，若$y_i=+1$，则有 $w^Tx_i+b>0$；若$y_i=-1$，则有 $w^Tx_i+b<0$，令：
   $$\begin{cases} w^Tx_i+b\geq+1, y_i=+1;\\ w^Tx_i+b\leq-1, y_i=-1. \end{cases}$$
   距离超平面最近的这几个训练样本点使上式等号成立，它们被称为“支持向量”(support vector)，两个异类支持向量到超平面的距离之和为：
   $$\gamma=\frac{2}{||w||}$$
   它被称为“间隔”(margin)
   欲找到具有“最大间隔”(maximum margin)的划分超平面，也就是要找到能满足约束的$w$和$b$，使得$\gamma$最大，即
   $$\max_{w,b}\frac{2}{||w||}\\ s.t. y_i(w^Tx_i+b)\geq1,i=1,2,...,m.$$
   显然，为了最大化间隔，仅需最大化$||w||^{-1}$，这等价于最小化$||w||^2$，于是：
   $$\min_{w,b}\frac{||w||^2}{2}\\ s.t. y_i(w^Tx_i+b)\geq1,i=1,2,...,m.$$
   这就是支持向量机(support vector machine)的基本型

要最优化$w$，可以化解为一个凸二次规划的问题，但是面对高维向量空间时，直接求解二次规划问题需要耗费问题复杂度指数倍的时间，因此常化解为求解其对偶问题。
对基本型方程组使用拉格朗日乘子法可得到其对偶问题。该问题的拉格朗日函数可写为：

$$L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum^{m}_{i=1}\alpha_i(1-y_i(w^Tx_i+b)),$$
其中$\alpha=(\alpha_1;\alpha_2;...;\alpha_m)$。令$L(w,b,\alpha)$对 $w$ 和 $b$ 的偏导为零可得
$$w=\sum^{m}_{i=1}\alpha_iy_ix_i,(A)\\ 0=\sum^m_{i=1}\alpha_iy_i.(B)$$
将上式代入拉格朗日函数，即可将 $L(w,b,\alpha)$ 中的 $w$ 和 $b$ 消去，再考虑B式的约束，就得到对偶问题：
$$\max_{\alpha} \sum^{m}_{i=1}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum^{m}_{i=1}\alpha_i\alpha_jy_iy_jx_i^Tx_j \\ s.t. \sum^{m}_{i=1}a_iy_i=0, \\ \alpha_i\geq0, i=1,2,...,m.$$