线性可分SVM摘记

0. 线性可分

\qquad 如下图所示，考虑训练数据“线性可分”的情况：
\qquad
\qquad 假设分类面 ${\mathbf{w}}^T\mathbf{x}+b=0$ 可以将两类数据完整分开，任一训练样本 $\mathbf{x}$ 的输出值（目标值） $y$ 满足：

$y=\text{sgn}({\mathbf{w}}^T\mathbf{x}+b)=\{\begin{array}{l}+1,{\mathbf{w}}^T\mathbf{x}+b>0(\mathbf{x}\in {\ell }_1)\\ -1,{\mathbf{w}}^T\mathbf{x}+b<0(\mathbf{x}\in {\ell }_2)\end{array}$
\qquad

1. 训练样本到分类面的距离

\qquad 任一样本 $\mathbf{x}$ 到分类面的垂直距离为： $r=\frac{y({\mathbf{w}}^T\mathbf{x}+b)}{\Vert \mathbf{w}\Vert }$

$\bullet$　正例 ${\mathbf{x}}_i$（满足 ${\mathbf{w}}^T{\mathbf{x}}_i+b>0,y_i=+1$）

\qquad\qquad

\qquad 假设 ${\mathbf{x}}_i$ 到分类面的距离为 $r_i$，向量 $\bar{\mathbf{x}}$ 在分类面（满足 ${\mathbf{w}}^T\bar{\mathbf{x}}+b=0$），显然 ${\mathbf{x}}_i=\bar{\mathbf{x}}+r_i\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }$

\qquad 那么
$\begin{array}{rl}{\mathbf{w}}^T{\mathbf{x}}_i+b& ={\mathbf{w}}^T(\bar{\mathbf{x}}+r_i\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert })+b\\ & ={\mathbf{w}}^T\bar{\mathbf{x}}+b+{\mathbf{w}}^T{r}_i\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }\\ & =r_i\frac{{\mathbf{w}}^T\mathbf{w}}{\Vert \mathbf{w}\Vert }\\ & =r_i\Vert \mathbf{w}\Vert \end{array}$

\qquad 可得到正例 ${\mathbf{x}}_i$ 到分类面的垂直距离 $r_i=\frac{{\mathbf{w}}^T{\mathbf{x}}_i+b}{\Vert \mathbf{w}\Vert }$

\qquad
$\bullet$　负例 ${\mathbf{x}}_j$（满足 ${\mathbf{w}}^T{\mathbf{x}}_j+b<0,y_j=-1$）

\qquad\qquad

\qquad 假设 ${\mathbf{x}}_j$ 到分类面的距离为 $r_j$，向量 $\bar{\mathbf{x}}$ 在分类面（满足 ${\mathbf{w}}^T\bar{\mathbf{x}}+b=0$），显然 ${\mathbf{x}}_j=\bar{\mathbf{x}}-r_j\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }$

\qquad 那么
$\begin{array}{rl}{\mathbf{w}}^T{\mathbf{x}}_j+b& ={\mathbf{w}}^T(\bar{\mathbf{x}}-r_j\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert })+b\\ & ={\mathbf{w}}^T\bar{\mathbf{x}}+b-{\mathbf{w}}^T{r}_j\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }\\ & =-r_j\frac{{\mathbf{w}}^T\mathbf{w}}{\Vert \mathbf{w}\Vert }\\ & =-r_j\Vert \mathbf{w}\Vert \end{array}$
\qquad 可得到负例 ${\mathbf{x}}_j$ 到分类面的垂直距离 $r_j=-\frac{{\mathbf{w}}^T{\mathbf{x}}_j+b}{\Vert \mathbf{w}\Vert }$
\qquad

2. 函数间隔和几何间隔、(硬)间隔最大化

\qquad 由于任一训练样本 ${\mathbf{x}}_i$ 的输出值 $y$ 满足：$y=\{\begin{array}{l}+1,{\mathbf{w}}^T{\mathbf{x}}_i+b>0(\forall {\mathbf{x}}_i\in {\ell }_1)\\ -1,{\mathbf{w}}^T{\mathbf{x}}_i+b<0(\forall {\mathbf{x}}_i\in {\ell }_2)\end{array}$，可定义两种间隔$(\text{margin})$来描述“训练样本 ${\mathbf{x}}_i$ 到分类面的远近”。

\qquad
$\bullet$　函数间隔 $(\text{functional margin})$

${\hat{\gamma }}_i=y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)=|{\mathbf{w}}^T{\mathbf{x}}_i+b|$

函数间隔只能够相对地描述“训练样本 ${\mathbf{x}}_i$ 到分类面的远近”。
例如，${\mathcal{H}}_1:{\mathbf{w}}^T\mathbf{x}+b=0$ 与 ${\mathcal{H}}_2:\lambda {\mathbf{w}}^T\mathbf{x}+\lambda b=0$ 实际上是指同一个分类面（假设 $\lambda >0$）
　
对训练样本 ${\mathbf{x}}_i$ 而言，却有 $\{\begin{array}{l}{\hat{\gamma }}_{1i}=|{\mathbf{w}}^T{\mathbf{x}}_i+b|\\ {\hat{\gamma }}_{2i}=\lambda |{\mathbf{w}}^T{\mathbf{x}}_i+b|\end{array}$，函数间隔 ${\hat{\gamma }}_{2i}=\lambda {\hat{\gamma }}_{1i}$

\qquad
$\bullet$　几何间隔 $(\text{geometricl margin})$

${\gamma }_i=y_i{r}_i=\frac{y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)}{\Vert \mathbf{w}\Vert }=\frac{|{\mathbf{w}}^T{\mathbf{x}}_i+b|}{\Vert \mathbf{w}\Vert }$

几何间隔就是“训练样本 ${\mathbf{x}}_i$ 到分类面的垂直距离”，也就是“规范化的函数间隔”。
　
上例中，$\{\begin{array}{l}{\gamma }_{1i}=\frac{{\hat{\gamma }}_{1i}}{\Vert \mathbf{w}\Vert }=\frac{|{\mathbf{w}}^T{\mathbf{x}}_i+b|}{\Vert \mathbf{w}\Vert }\\ \\ {\gamma }_{2i}=\frac{{\hat{\gamma }}_{2i}}{\Vert \lambda \mathbf{w}\Vert }=\frac{\lambda |{\mathbf{w}}^T{\mathbf{x}}_i+b|}{\Vert \lambda \mathbf{w}\Vert }=\frac{|{\mathbf{w}}^T{\mathbf{x}}_i+b|}{\Vert \mathbf{w}\Vert }\end{array}$，几何间隔 ${\gamma }_{1i}={\gamma }_{2i}$，仍然相等。

\qquad 显然，函数间隔和几何间隔之间的关系为：

$\gamma =\frac{\hat{\gamma }}{\Vert \mathbf{w}\Vert }$

\qquad
$\bullet$　以最大化训练样本的几何间隔为目标函数，并定义约束最优化问题

\qquad 约束最优化问题（1）

$\begin{array}{rl}& \underset{\mathbf{w},b}{\max }\gamma \\ & s.t.\frac{y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)}{\Vert \mathbf{w}\Vert }\ge \gamma ,\forall {\mathbf{x}}_i\end{array}$

也就是，在确保所有训练样本到分类面的垂直距离都大于 $\gamma$ 的前提下，尽可能让（几何）间隔最大。

\qquad 利用两种间隔之间的关系 $\gamma =\frac{\hat{\gamma }}{\Vert \mathbf{w}\Vert }$，在约束最优化问题（1）中使用函数间隔 $\hat{\gamma }$ 来描述几何间隔 $\gamma$，也就是

\qquad 约束最优化问题（2）

$\begin{array}{rl}& \underset{\mathbf{w},b}{\max }\frac{\hat{\gamma }}{\Vert \mathbf{w}\Vert }\\ & s.t.y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge \hat{\gamma },\forall {\mathbf{x}}_i\end{array}$

\qquad 　
\qquad 考虑满足约束最优化问题（2）的同一个分类面的两种表示 ${\mathcal{H}}_1:(\mathbf{w},b)$ 和 ${\mathcal{H}}_2:(\lambda \mathbf{w},\lambda b)$，对于任一训练样本 ${\mathbf{x}}_i$ 而言（$\lambda >0$），那么：

\qquad ①${\mathcal{H}}_1:{\mathbf{w}}^T\mathbf{x}+b=0$　 　（函数间隔为 $\hat{\gamma }=|{\mathbf{w}}^T{\mathbf{x}}_i+b|$）

$⟹\{\begin{array}{l}目标函数值：\frac{\hat{\gamma }}{\Vert \mathbf{w}\Vert }\\ 约束函数：y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge \hat{\gamma },\forall {\mathbf{x}}_i\end{array}$

\qquad ②${\mathcal{H}}_2:\lambda {\mathbf{w}}^T\mathbf{x}+\lambda b=0$　（函数间隔为 $\lambda \hat{\gamma }$）

$⟹\{\begin{array}{l}目标函数值：\frac{\lambda \hat{\gamma }}{\Vert \lambda \mathbf{w}\Vert }\\ 约束函数：y_i\lambda ({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge \lambda \hat{\gamma },\forall {\mathbf{x}}_i\end{array}$
\qquad
\qquad 显然，权值 $(\mathbf{w},b)$ 与其同比例的缩放值 $(\lambda \mathbf{w},\lambda b)$ 对于约束最优化问题（2）而言是没有影响的。

\qquad
$\bullet$　构造凸二次规划问题

\qquad 在约束最优化问题（2）中，可以简单地取函数间隔 $\hat{\gamma }=1$。

假设待求解的权值为 $(\mathbf{w},b)$， 样本 $\mathbf{x}$ 到 ${\mathbf{w}}^T\mathbf{x}+b=0$ 的几何间隔为 $\frac{\hat{\gamma }}{\Vert \mathbf{w}\Vert }$
函数间隔 $\hat{\gamma }=1$ 时的几何间隔写为 $\frac{1}{\Vert {\lambda }^{\prime }\mathbf{w}\Vert }$，也就是 $(\mathbf{w},b)$ 缩放为了 $({\lambda }^{\prime }\mathbf{w},{\lambda }^{\prime }b),{\lambda }^{\prime }=1/\gamma$
而 ${\mathbf{w}}^T\mathbf{x}+b=0$ 和 ${\lambda }^{\prime }{\mathbf{w}}^T\mathbf{x}+{\lambda }^{\prime }b=0$ 是同一个分类面

\qquad 那么，约束最优化问题（2）就可以写为：

$\begin{array}{rl}& \underset{\mathbf{w},b}{\max }\frac{\hat{\gamma }}{\Vert \mathbf{w}\Vert }\\ & s.t.y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge \hat{\gamma },\forall {\mathbf{x}}_i\end{array}\stackrel{\hat{\gamma }=1}{⟹}\begin{array}{rl}& \underset{\mathbf{w},b}{\max }\frac{1}{\Vert \mathbf{w}\Vert }\\ & s.t.y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1,\forall {\mathbf{x}}_i\end{array}$

\qquad
\qquad 又由于 $\max \frac{1}{\Vert \mathbf{w}\Vert }⟺\min \frac{1}{2}\Vert \mathbf{w}{\Vert }^2$，因此可以构造出一个凸二次规划问题

\qquad 约束最优化问题（3）

$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\\ & s.t.y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1,\forall {\mathbf{x}}_i\end{array}$

\qquad

3. 支持向量

\qquad 支持向量 $(\text{support vector})$ 是指距离分类面最近的训练样本（红色 + 点），两个（红色点线）超平面 ${\mathbf{w}}^T\mathbf{x}+b=1$ 和 ${\mathbf{w}}^T\mathbf{x}+b=-1$ 之间的距离，称为间隔$(\text{margin})$。
\qquad
\qquad 考察该凸二次规划最优化问题：

$\begin{array}{rl}& \underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\\ & s.t.y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1,\forall {\mathbf{x}}_i\end{array}$

\qquad 支持向量也是使得约束条件的等式成立的点，即：$y({\mathbf{w}}^T\mathbf{x}+b)=1$。在线性可分的情况下，选择不同的点作为支持向量，就可以确定不同的分离超平面 ${\mathbf{w}}^T\mathbf{x}+b=0$。

• （正例的）支持向量 ${\mathbf{x}}_i,y_i=+1:y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)=1\Rightarrow H_1:{\mathbf{w}}^T{\mathbf{x}}_i+b=1$
  其余的 （正例的）训练样本满足 ${\mathbf{w}}^T{\mathbf{x}}_i+b>1$
• （负例的）支持向量 ${\mathbf{x}}_j,y_j=-1:y_j({\mathbf{w}}^T{\mathbf{x}}_j+b)=1\Rightarrow H_2:{\mathbf{w}}^T{\mathbf{x}}_j+b=-1$
  其余的 （负例的）训练样本满足 ${\mathbf{w}}^T{\mathbf{x}}_i+b<-1$
• 两个超平面 $H_1$ 与 $H_2$ 之间的间隔为 $\frac{2}{\Vert \mathbf{w}\Vert }$

\qquad
\qquad
【写在最后】SVM的资料太多了，越写越觉得没什么特别的内容值得去写。攒在草稿箱里太久，发出来就当留个记录吧。