1 间隔与支持向量

给定一个 $p$ 维的数据集，线性分类器希望用一个 $p-1$ 维的超平面将数据集分类。

能将样本分类的超平面可能有很多，但是选择最中间的容忍性好、鲁棒性高、泛化能力最强。

怎样刻画“正中间”？

假设超平面的方程是 $w^Tx+b=0$，这里 $x,w$ 都是 $p-1$ 维的。我们希望用样本点到超平面的距离来刻画“正中间”这种说法。样本点 $\boldsymbol{x}$ 到上述超平面的距离可以写为 $$ \newcommand{\w}{\boldsymbol{w}} \newcommand{\x}{\boldsymbol{x}} r=\frac{|\w^T\x+b|}{||\w||} $$ 假定超平面把样本正确分类，即 $$ \begin{aligned} y_i=+1\Rightarrow w^Tx_i+b>0\newline y_i=-1\Rightarrow w^Tx_i+b<0 \end{aligned} $$ 也就是说 $y_i*(w^Tx_i+b)>0.$

只要让上述不等式右边从 0 开始增大（以变量 $\epsilon$ 代之），就可以刻画这个超平面沿着其法向量方向远离，两个平面 $w^Tx_i+b=\pm\epsilon$ 之间的距离是 $\displaystyle{}\frac{2\epsilon}{||\w||}$。这个 $\epsilon$ 让问题复杂了一点，事实上，在我们的假设下，存在一个缩放变换 $\alpha\w→\w',\alpha b→b'$ 可以让这个 $\epsilon$ 固定为 $1$，我们只需要找参数 $\w,b$，让距离 $\displaystyle \gamma=\frac{2}{||\w||}$ 最大即可。

伸缩变换

假设 $y_i\left(\boldsymbol{w}^{\top} \boldsymbol{x}_i+b\right) \geq \epsilon$ ，则 $y_i\left(\frac{\boldsymbol{w}^{\top}}{\epsilon} \boldsymbol{x}_i+\frac{b}{\epsilon}\right) \geq 1$

将上面的想法写成优化问题就是

$$\begin{gathered} \max _{\boldsymbol{w}, b} \frac{2}{\|\boldsymbol{w}\|} \newline \text { s.t. } y_i\left(\boldsymbol{w}^{\top} \boldsymbol{x}_i+b\right) \geq 1 \quad i=1, \cdots, m \end{gathered}$$

为了方便求导等操作，可以写成等价的问题（平方是因为这里是 2-范数）

$$\begin{gathered} \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^2 \\ \text { s.t. } y_i\left(\boldsymbol{w}^{\top} \boldsymbol{x}_i+b\right) \geq 1 \quad i=1, \cdots, m \end{gathered}$$

本文阅读量