支持向量机（SVM）

• SVM是一种监督学习二元分类器，通过核函数将线性不可分变成线性可分，同时在实践中也是小样本学习效果最好的算法。

支持向量

• 关于线性分类的概念请参考逻辑回归，对于不同的分类器可能会得到不同的拟合结果，例如

  

  上图中是三个分类器得到的决策边界，对于蓝色和黄色分类器，不能将正负类别分开，拟合能力较弱，同时对于黑色分类器来说，其不仅可以达到分类效果，还满足距离两个类别的最近样本最远。而这两个类别中离决策边界最近的样本我们称其为支持向量，其与决策边界之间的距离称为margin。

  当从二维扩展到多维空间时，决策边界将变成一个超平面，我们同样是寻找满足下面条件的拟合结果：

  1. 两类样本分别在超平面的两侧；
  2. 最大化支持向量与超平面之间的距离。

• 对于一个超平面我们可以用如下线性方程来描述

  $$\boldsymbol{w}^T\boldsymbol{x} + b = 0$$

  同时在$n$维空间中，点$\boldsymbol{x} = (x_1, x_2, \dots, x_n)$到这个平面的距离为

  $$d = \frac{|\boldsymbol{w}^T\boldsymbol{x} + b|}{\Vert \boldsymbol{w}\Vert}$$

  其中$\Vert \boldsymbol{w}\Vert = \sqrt{w_1^2+w_2^2+\cdots+w_n^2}$，我们可以设支持向量到超平面的距离为$d$，其他样本到超平面的距离大于$d$。为了方便我们将正向类别定义为$y=1$，负向类别定义为$y=-1$，此时我们得到超平面的一个约束

  $$\begin{cases} \frac{\boldsymbol{w}^T\boldsymbol{x} + b}{\Vert \boldsymbol{w}\Vert} \ge d &,y=1\\ \frac{\boldsymbol{w}^T\boldsymbol{x} + b}{\Vert \boldsymbol{w}\Vert}\le -d &, y=-1 \end{cases}$$

  同时我们两边乘以$\Vert \boldsymbol{w}\Vert$变成

  $$\begin{cases} \boldsymbol{w}^T\boldsymbol{x} + b \ge \Vert \boldsymbol{w}\Vert d &,y=1\\ \boldsymbol{w}^T\boldsymbol{x} + b\le -\Vert \boldsymbol{w}\Vert d &, y=-1 \end{cases}$$

  因为$\Vert \boldsymbol{w}\Vert d$是正数，我们可以移走或者说令其等于1简化算式（这对后续的优化没有影响），并且合并两个算式，得到

  $$y(\boldsymbol{w}^T\boldsymbol{x} + b)\ge 1$$

  由于该式恒大于0，故有$y(\boldsymbol{w}^T\boldsymbol{x} + b) = |\boldsymbol{w}^T\boldsymbol{x} + b|$，所以之前的距离公式可以改为

  $$d = \frac{y(\boldsymbol{w}^T\boldsymbol{x} + b)}{\Vert w\Vert}$$

  而我们的目标则是最大化这个距离，同时对于支持向量有$y(\boldsymbol{w}^T\boldsymbol{x} + b)=1$，所以最大化的目标为

  $$\gamma = \max(\frac{2}{\Vert \boldsymbol{w}\Vert})$$

  乘2的目的和MSE中乘2类似，不影响性质的情况下简化后续的运算。

  

• 同时这里还可以进一步转换将目标变为求

  $$\min(\frac{1}{2}\Vert \boldsymbol{w}\Vert)$$

  去除掉除法，同时为了去除模长的根号可以再添加一个平方变为

  $$\min(\frac{1}{2}\Vert \boldsymbol{w}\Vert^2)$$

  其中$y^{(i)}(\boldsymbol{w}x^{(i)} + b)\ge 1$