SVM1-线性可分支持向量机

1. 问题定义

训练数据集定义为：

$$T = {(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)}$$

其中，$x_i \in \mathbb{R}^{n}$, $y_i \in {+1, -1}$。

学习的目标是在特征空间中找到一个分离超平面$w \cdot x + b = 0$，使得实例能够分到不同的类。$w$为法向量，其指向正类一侧，$b$为截距。线性可分支持向量机利用间隔最大化求最有分离超平面，此时解是唯一的。这个唯一的解表示为：

$$w^* \cdot x + b^* = 0$$

相应的分类决策函数为：

$$f(x) = \operatorname{sign}(w^* \cdot x + b^*)$$

2. 函数间隔与几何间隔

函数间隔（functional margin）

一般来说，一个点距离分类超平面的远近可以表示分类预测的可信度，$|w \cdot x + b|$能够相对地表示点$x$到超平面的远近，而$w \cdot x + b$与类标记$y$符号的一致可以表示分类的正确性，所以可以用$y(w \cdot x + b)$来表示分类的正确性和可信度，这就是函数间隔，定义如下：

对于给定的训练集$T$和超平面$(w, b)$，定义超平面$(w, b)$关于样本点$(x_i, y_i)$的函数间隔为：

$$\hat{\gamma}_i = y_i(w \cdot x_i + b)$$

定义超平面$(w, b)$关于数据集$T$的函数间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i, y_i)$的函数间隔的最小值，即

$$\hat{\gamma} = \underset{i = 1, \cdots, N}{\min} \hat{\gamma}_i$$

函数间隔有其局限性，因为只要成比例的改变$w$和$b$，例如将它们改变为$2w$和$2b$，超平面并未发生改变，但函数间隔却变为原来的2倍。可以通过对法向量$w$加以约束，如规范化使得$\Vert w \Vert = 1$，使得间隔是确定的，这是函数间隔成为几何间隔

几何间隔（geometric margin）

首先推导实例中任一点$x$到超平面$w \cdot x + b = 0$的距离公式。

上图中$x$是超平面外的一点，$x^\prime$是超平面上任一点，显然存在$w \cdot x^\prime + b = 0$。$x$到超平面的距离记为$d$，就是图上红色的线段。根据三角函数可得：

$$\cos \theta = \frac{d}{\Vert x - x^\prime \Vert}$$

$d$的方向肯定是和法向量平行的，根据余弦公式可以计算：

$$\vert (x - x^\prime) \cdot w \vert = \Vert x - x^\prime \Vert \Vert w \Vert \cos \theta$$

这里因为法向量可能反向，所以给等式左边加上绝对值。联立上面两式可得：

$$d = \frac{\vert (x - x^\prime) \cdot w \vert}{\Vert w \Vert} = \frac{\vert w \cdot x - w \cdot x^\prime \vert}{\Vert w \Vert}$$

因为$w \cdot x^\prime = -b$，所以上式可以写为

$$d = \frac{\vert w \cdot x + b \vert}{\Vert w \Vert}$$

考虑到超平面两侧的类标记正负问题，当样本点$(x_i, y_i)$被超平面正确分类时，可以去掉上式的绝对值符号，将点$x_i$与超平面$(w, b)$的距离记为

$$\gamma_i = y_i (\frac{w}{\Vert w \Vert} \cdot x + \frac{b}{\Vert w \Vert})$$

这个距离定义为几何间隔。具体来说如下：

对于给定的训练集$T$和超平面$(w, b)$，定义超平面$(w, b)$关于样本点$(x_i, y_i)$的几何间隔为：

$$\gamma_i = y_i (\frac{w}{\Vert w \Vert} \cdot x + \frac{b}{\Vert w \Vert})$$

定义超平面$(w, b)$关于数据集$T$的函数间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i, y_i)$的函数间隔的最小值，即

$$\gamma = \underset{i = 1, \cdots, N}{\min} \gamma_i$$

从函数间隔和几何间隔的定义可知二者有以下关系：

$$\gamma_i = \frac{\hat{\gamma}_i}{\Vert w \Vert}$$ $$\gamma = \frac{\gamma}{\Vert w \Vert}$$

3. 间隔最大化

间隔最大化是指对训练数据集，找打几何间隔最大的超平面，以充分大的确信度对训练数据进行分类。这里的间隔最大化又称为硬间隔最大化。求一个最大间隔分离超平面，可以表示为如下的约束最优化问题：

$$\begin{align} & \underset{w, b}{\max} \quad \gamma \\ & \operatorname{s.t.} \quad y_i(\frac{w}{\Vert w \Vert}\cdot x_i + \frac{b}{\Vert w \Vert}) \ge \gamma, \quad i = 1, 2, \cdots, N \end{align}$$

上式中约束条件表示超平面关于每个训练样本的几何间隔至少是$\gamma$。

考虑几何间隔与函数间隔的关系$\gamma = \frac{\hat{\gamma}}{\Vert w \Vert}$，可以将上式改写为：

$$\begin{align} & \underset{w, b}{\max} \quad \frac{\hat{\gamma}}{\Vert w \Vert} \\ & \operatorname{s.t.} \quad y_i(w\cdot x_i + b) \ge \hat{\gamma}, \quad i = 1, 2, \cdots, N \end{align}$$

函数间隔$\hat{\gamma}$的取值并不影响最优化问题的解。事实上，假设将$w$和$b$按比例改变为$\lambda w$和$\lambda b$，这时函数间隔将相应地变为$\lambda \hat{\gamma}$。函数间隔地这一改变对上面的最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，这样即产生一个等价的最优化问题。因此，可以取$\hat{\gamma} = 1$。

将$\hat{\gamma} = 1$代入上面的最优化问题，并且$\max \frac{1}{\Vert w \Vert}$和$\min \frac{1}{2} \Vert w \Vert ^2$是等价的，由此可以得到下面的线性可分支持向量机学习的最优化问题：

$$\begin{align} & \underset{w, b}{\min} \quad \frac{1}{2}\Vert w \Vert^2 \\ & \operatorname{s.t.} \quad y_i(w\cdot x_i + b) - 1 \ge 0, \quad i = 1, 2, \cdots, N \end{align}$$

这是一个凸二次规划（convex quadratic programming）问题。

这样，线性可分支持向量机模型就转化成了上面的约束最优化问题。

支持向量和间隔边界

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）。支持向量使得约束条件等号成立，即：

$$y_i (w \cdot x_i + b) - 1 = 0$$

对于正样本点$y_i = +1$，支持向量在超平面

$$H_1: w \cdot x + b = 1$$

上，对于负样本点$y_i = -1$，支持向量在超平面

$$H_2: w \cdot x + b = -1$$

$H_1$和$H_2$平行，并且没有实例点落在它们之间。$H_1$和$H_2$的距离称为间隔（margin），其大小为$\frac{2}{\Vert w \Vert}$。$H_1$和$H_2$称为间隔边界。

在决定分离超平面时只有支持向量起作用，其他实例点并不起作用。

4. 学习的对偶算法

为了求解线性可分支持向量机的最优化问题，将它作为原始问题，应用拉格朗日对偶性，通过求解对偶问题（dual problem）得到原始问题（primal problem）的最优解，这就是线性可分支持向量机的对偶算法（dual algorithm）。

对偶算法的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。

首先构建拉格朗日函数（Lagrange function），对每一个不等式约束（在凸优化问题中，一般将约束写为小于等于0的形式，即$1 - y_i (w \cdot x_i + b) \le 0$）引进拉格朗日乘子（Lagrange multiplier）$\alpha_i \ge 0$, $i = 1, 2, \cdots, N$，定义拉格朗日函数为：

$$\begin{align} L(w, b, \alpha) &= \frac{1}{2} \Vert w \Vert ^2 + \sum_{i=1}^{N}\alpha_i(1 - y_i(w \cdot x_i + b)) \\ &= \frac{1}{2} \Vert w \Vert ^2 - \sum_{i=1}^{N}\alpha_i y_i(w \cdot x_i + b) + \sum_{i=1}^{N}\alpha_i \end{align}$$

其中，$\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_N)^T$为拉格朗日乘子向量。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

$$\underset{\alpha}{\max} \underset{w, b}{\min} L(w, b, \alpha)$$

为了求得对偶问题的解，需要先求$L(w, b, \alpha)$对$w, b$的极小，再求对$\alpha$的极大。

1. 求$\underset{w, b}{\min} L(w, b, \alpha)$

   将$L(w, b, \alpha)$分别对$w, b$求偏导并令其等于0：

   $$\nabla_w L(w, b, \alpha) = w - \sum_{i=1}^N \alpha_i y_i x_i = 0$$ $$\nabla_b = -\sum_{i=1}^N \alpha_i y_i = 0$$

   得

   $$w = \sum_{i=1}^N \alpha_i y_i x_i$$ $$\sum_{i=1}^N \alpha_i y_i = 0$$

   代入拉格朗日函数得

   $$\begin{align} L(w, b, \alpha) &= \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^N \alpha_i y_i ((\sum_{j=1}^N \alpha_j y_j x_j) \cdot x_i + b) + \sum_{i=1}^{N}\alpha_i \\ &= \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - b\sum_{i=1}^N \alpha_i y_i + \sum_{i=1}^{N}\alpha_i \\ &= -\frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^{N}\alpha_i \end{align}$$

   即

   $$\underset{w, b}{\min}{L(w, b, \alpha)} = -\frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^{N}\alpha_i$$

2. 求$\underset{w, b}{\min} L(w, b, \alpha)$对$\alpha$的极大，就是对偶问题

   $$\begin{align} & \underset{\alpha}{\max} \quad -\frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^{N}\alpha_i \\ & \operatorname{s.t.} \quad \sum_{i=1}^N \alpha_i y_i = 0 \end{align}$$

   将上式的目标函数由极大转换成求极小，就得到如下与之等价的对偶最优化问题：

   $$\begin{align} & \underset{\alpha}{\min} \quad \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N}\alpha_i \\ & \operatorname{s.t.} \quad \sum_{i=1}^N \alpha_i y_i = 0 \end{align}$$

对线性可分训练数据集，假设上面的对偶最优化问题对$\alpha$的解为$\alpha^\ast = (\alpha_1^\ast, \alpha_2^\ast, \cdots , \alpha_N^\ast)^T$，则可以得到$(w, b)$的解$w^\ast, b^\ast$。定理如下：

设$\alpha^\ast = (\alpha_1^\ast, \alpha_2^\ast, \cdots , \alpha_N^\ast)^T$是对偶最优化问题的解，则存在下标$j$，使得$\alpha_j^\ast > 0$，并可以按下式求解原始最优化问题的解$w^\ast, b^\ast$：

$$w^\ast = \sum_{i=1}^N \alpha_i^\ast y_i x_i$$ $$b^\ast = y_j - \sum_{i=1}^N \alpha_i^\ast y_i (x_i \cdot x_j)$$

由$w^\ast$和$b^\ast$的求解式可知，$w^\ast$和$b^\ast$只依赖于训练集中对应于$\alpha_i^\ast > 0$的样本点$(x_i, y_i)$，而其他样本点对$w^\ast$和$b^\ast$没有影响。把训练数据集中对应于$\alpha_i^\ast > 0$的实例点$x_i \in \mathbb{R}^n$称为支持向量。

对于$\alpha_i^\ast > 0$的实例点$x_i$，有

$$y_i (w^\ast \cdot x_i + b^\ast) - 1 = 0$$

这与前面给出的支持向量的定义是一致的。