支持向量机（一）

  支持向量机（Support Vector Machine）是一种强大的监督式学习算法。尽管目前深度学习非常流行，但这种经典的机器学习算法仍然有着非常大的研究价值，并且它在机器学习领域仍占有着一席之地。本次学习材料主要是CS229课程以及一些网上的资料。

SVM目标

  为了引入SVM思想，我们来看一个二分类问题。假设我们有一组训练样本$\{(x_1,y_1),…,(x_m,y_m)\}$，其中$x_i\in\Bbb{R}^n$为第$i$个训练样本的特征，是一个$n$维向量；$y_i$为第$i$个训练样本的输出，由于这是个二分类问题，因此$y_i$只能取$1$或$0$，分别代表正负样本。
  若使用逻辑线性回归模型（logistic regression）对样本进行分类，预测函数则为：

$$h(x)={\rm sigmoid}(w^Tx+b)\tag{1}$$

  其中${\rm sigmoid}(z)$是一个特殊函数，它的定义如下：

$${\rm sigmoid}(z)={1 \over {1+e^{-z}}}\tag{2}$$

  我们可以将预测函数的输出看作是$y=1$的概率。若输入特征$x$使得$w^Tx+b\geq0$，预测函数$h(x)\geq0.5$，则预测输出$y=1$；若输入特征$x$使得$w^Tx+b<0$，预测函数$h(x)<0.5$，则预测输出$y=0$。我们发现，$w^Tx+b$越大，预测函数输出越接近$1$，我们就越有把握预测$y=1$；同样$w^Tx+b$越小，预测函数输出越接近$0$，我们就越有把握预测$y=0$。若一个模型能使得所有训练样本满足：

$$\begin{cases} w^Tx^{(i)}+b\gg0,\ 若y^{(i)}=1\\ w^Tx^{(i)}+b\ll0,\ 若y^{(i)}=0 \end{cases}\tag{3}$$

  我们就认为该模型是个高可信度的模型，它的决策边界$w^Tx+b=0$能够将正负样本分开，且样本点距离决策边界足够远。换句话说，就是能够将正负样本分得足够开，这样它就不会因为微小的扰动将样本从其中一侧划到另一侧去，增加了模型抗扰动的能力。SVM的目标就是找到这样一组$(w,b)$，使得模型的可信度最高。

函数间隔与几何间隔

  在这里我们将二分类问题及模型稍微更改一下。取$y\in\{1,-1\}$，并且将预测函数更改为：

$$h(x)={\rm sign}(w^Tx+b)\tag{4}$$

  其中${\rm sign}(z)$为符号函数，它的定义为：

$$\begin{cases} 1&,z\geq0\\ -1&,z<0 \end{cases}\tag{5}$$

  实际上，更改前后的模型本质是一样的：$w^Tx+b\geq0$时，预测为正样本；$w^Tx+b<0$时，预测为负样本。只是$y$的取值变了，并且预测函数输出不再是概率而是直接输出预测值。
  为了描述正负样本分开的程度，我们引入函数间隔（functional margin）的概念。对于样本$(x^{(i)},y^{(i)})$来说，它的函数间隔定义为：

$$\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)\tag{6}$$

  若$y^{(i)}=1$，我们希望$w^Tx^{(i)}+b\gg0$；若$y^{(i)}=-1$，我们希望$w^Tx^{(i)}+b\ll0$。根据式(6)，我们可以用函数间隔的概念将这两种情况合并，即无论$y^{(i)}$取值，我们都希望训练样本的函数间隔$\hat{\gamma}^{(i)}\gg0$（若$\hat{\gamma}<0$，则表示预测错误）。若所有训练样本均满足$\hat{\gamma}^{(i)}\gg0$，那么模型是一个高可信度的模型。因此我们使用所有训练样本函数间隔的最小值来定义模型$(w,b)$的函数间隔$\hat{\gamma}$：

$$\hat{\gamma}=\min_{i=1,...,m}\hat{\gamma}^{(i)}\tag{7}$$

  $\hat{\gamma}$代表了一个模型的可信程度。但是这里存在一个问题：如果将$(w,b)$同时放大$k$倍，我们发现$w^Tx+b$的正负没有改变，但$\hat{\gamma}$却放大为了原来的$k$倍。这表示模型的本质没有变化但可信度却强行提高了。为了避免这种情况产生，需要对$(w,b)$的数值有一定的限制，因此我们利用$||w||$对参数$(w,b)$进行标准化：

$$(w,b)\longrightarrow \left({w \over ||w||},{b \over ||w||}\right)\tag{8}$$

  由此我们可以定义样本$(x^{(i)},y^{(i)})$的几何间隔（geometric margin）：

$$\gamma^{(i)}=y^{(i)}\left({w \over ||w||}^Tx^{(i)}+{b \over ||w||}\right)\tag{9}$$

  $\gamma^{(i)}$表示在$n$维空间中，样本与超平面之间的距离。考虑如下示意图：

  图中的超平面为决策边界$w^Tx+b=0$，且向量$w$与该超平面垂直（可通过数学证明）。点$B$为样本$A$在超平面上的投影，因此点$A$到超平面的距离就是$AB$的长度，且向量$BA$方向与$w$相同或相反（相同时为正样本；相反时为负样本）。设$A$点坐标为$x^{(i)}，$$AB$长度为$\gamma^{(i)}$，则$B$点坐标可以表示为：

$$\vec{OB}=\vec{OA}-\vec{BA}=x^{(i)}-\gamma^{(i)}{y^{(i)}w \over ||w||}\tag{10}$$

  而$B$在超平面上，因此满足超平面方程

$$w^Tx+b=0\tag{11}$$

  将式(10)带入式(11)中得到：

$$w^T\left(x^{(i)}-\gamma^{(i)}{y^{(i)}w \over ||w||}\right)+b=0\tag{12}$$

  其中$w^Tw=||w||$，化简后得到：

$$\gamma^{(i)}=y^{(i)}\left({w^T \over ||w||}x^{(i)}+{b \over ||w||}\right)\tag{13}$$

  式(13)与式(9)一致，几何间隔就是样本与超平面之间的距离。与式(6)类似，我们也使用所有训练样本几何间隔的最小值来定义模型$(w,b)$的几何间隔$\gamma$：

$$\gamma=\min_{i=1,...,m}\gamma^{(i)}\tag{14}$$

  我们可以发现函数间隔与几何间隔的关系为：

$$\gamma={\hat{\gamma \over ||w||}}\tag{15}$$

  当$||w||=1$时，函数间隔与几何间隔相等。

最优间隔分类器

  在SVM目标中我们希望得到一个高可信度的模型，它的决策边界能够将正负样本分开，并且样本点距离决策边界足够远。在这里，我们使用间隔的定义更加严谨地描述一下这个优化目标：假设训练数据是线性可分离的（linearly separable），那么我们希望得到一个模型，使得它对于训练样本的几何间隔尽可能大。数学表达如下：

$$\begin{split} \max_{\gamma ,w,b}\ &\gamma\\ {\rm s.t.}\ &y^{(i)}(w^Tx^{(i)}+b)\geq \gamma,\ i=1,...,m\\ &||w||=1 \end{split}\tag{16}$$

  式(16)表明所有训练样本的几何间隔均大于等于$\gamma$，而条件$||w||=1$则确保函数间隔与几何间隔相等，而我们要做的就是使这个几何间隔$\gamma$取到最大。如果我们能解决这个问题，那么就已经可以了。但是由于条件$||w||=1$导致优化函数是非凸的，极值点不唯一，无法通过优化软件进行计算。因此我们将问题的数学描述更改一下：

$$\begin{split} \max_{\gamma,w,b}\ &{\hat{\gamma} \over ||w||}\\ {\rm s.t.}\ &y^{(i)}(w^Tx^{(i)}+b)\geq \hat\gamma,\ i=1,...,m \end{split}\tag{17}$$

  在这里我们舍弃了$||w||=1$这个条件，不再要求函数间隔等于几何间隔。同时让所有样本函数间隔均大于等于$\hat\gamma$，而最大化$\hat\gamma /||w||$。根据式(15)，$\hat\gamma /||w||$就是几何间隔，因此式(16)与式(17)实际是等价的。但由于$\hat\gamma /||w||$仍然是非凸的函数，还是无法通过优化软件进行计算。因此我们需要继续修改优化问题的数学描述。
  我们发现，这个优化问题实质是最大化几何间隔，而函数间隔是多少我们并不关心，它随时可以通过给$(w,b)$乘以常数来改变。因此我们可以假设函数间隔$\hat\gamma=1$，而最大化几何间隔$1/||w||$即可。因此我们将优化问题转化为：

$\begin{split} \min_{\gamma,w,b}\ &{1 \over 2}||w||^2\\ {\rm s.t.}\ &y^{(i)}(w^Tx^{(i)}+b)\geq1,\ i=1,...,m \end{split}\tag{18}$

  式(18)中最小化$||w||^2$与最大化$1/||w||$是等价的，并且$||w||^2$是个二次凸函数，因此可以使用优化软件来解决。通过它所得到的模型就是最优间隔分类器（optimal margin classifier）。为了更好地求解式(18)的优化问题，接下来的章节我们将介绍拉格朗日对偶并且导出式(18)的对偶形式，再由此引入支持向量以及核的概念。

小结

1. SVM目标是最大化模型决策边界与训练样本的几何间隔。
2. 利用式(18)将该目标转化为一个带约束条件的优化问题。