References：

【机器学习】支持向量机 SVM（非常详细）

机器学习笔记（五）：支持向量机（SVM）

支持向量机（SVM）——原理篇

【假设形式】

对于给定容量为 $n$ 的线性可分训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_n,y_n)\}$，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $m$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})\in \mathbb{R}^m$，输出 $y_i\in\mathcal{Y}=\{+1,-1\}$

硬间隔支持向量机（Hard Margin Support Vector Machines）对于线性可分的训练集，通过求解硬间隔最大化问题：

$\begin{matrix} \min\limits_{\boldsymbol{\omega},\theta} && \frac{1}{2}||\boldsymbol{\omega}||_2^2 \\ s.t. && y_i ( \boldsymbol{\omega}\cdot\mathbf{x}_i+\theta)-1 \geq 0 ,&& i=1,2,\cdots,n \end{matrix}$

来求解唯一的最优分离超平面：

$S: \boldsymbol{\omega}^*\cdot \mathbf{x}+\theta^* = 0$

以及相应的分类决策函数：

$f(\mathbf{x}) = \text{sign}(\boldsymbol{\omega}^*+\theta^*)$

由于训练集是线性可分的，因此又称线性可分支持向量机（Linear Support Vector Machines in Linearly Separable Case）

【硬间隔支持向量机学习算法的原始形式】

硬间隔最大化

硬间隔最大化（Hard Margin Maximization）是找到使所有样本点的几何间隔的最小值最大的分离超平面，即寻找最大间隔分离超平面

其直观解释是：对于训练集找到分离超平面，意味着以充分大的确信度对训练集进行分类，也就是说，不仅将正负样本点分开，而且对最难分的样本点（距离分离超平面最近的点）也有足够大的确信度将它们分开

下面考虑如何求得一个最大间隔分离超平面

对于给定容量为 $n$ 的训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_n,y_n)\}$，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $m$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(m)})\in \mathbb{R}^m$，输出 $y_i\in\mathcal{Y}=\{+1,-1\}$

分离超平面 $S:\boldsymbol{\omega}\cdot\mathbf{x}+\theta=0$ 关于样本点 $(\mathbf{x}_i,y_i)$ 的几何间隔为：

$\gamma_i = y_i \big( \frac{1}{||\boldsymbol{\omega}||_2}(\boldsymbol{\omega}\cdot\mathbf{x}+\theta) \big)$

分离超平面 $S:\boldsymbol{\omega}\cdot\mathbf{x}+\theta=0$ 关于样本集 $D$ 的中所有样本点的几何间隔的最小值为：

$\gamma = \min_{i=1,2,\cdots,n} \hat{\gamma}_i$

具体来说，寻找最大间隔分离超平面可以表示为下面的约束最优化问题

$\begin{matrix} \max\limits_{\boldsymbol{\omega},\theta} && \gamma \\ s.t. && y_i \big( \frac{1}{||\boldsymbol{\omega}||_2}(\boldsymbol{\omega}\cdot\mathbf{x}_i+\theta) \big) \geq \gamma ,&& i=1,2,\cdots,n \end{matrix}$

即希望最大化超平面 $S:\boldsymbol{\omega}\cdot\mathbf{x}+\theta=0$ 关于训练集的几何间隔 $\gamma$，同时约束超平面 $S$ 关于每个训练样本点的几何间隔至少是 $\gamma$

考虑到几何间隔和函数间隔的关系：

$\begin{align*} \gamma_i &= \frac{1}{||\boldsymbol{\omega}||_2} \hat{\gamma_i} \\ \gamma &= \frac{1}{||\boldsymbol{\omega}||_2} \hat{\gamma} \end{align*}$

约束最优化问题可改写为：

$\begin{matrix} \max\limits_{\boldsymbol{\omega},\theta} && \frac{\hat{\gamma}}{||\boldsymbol{\omega}||_2} \\ s.t. && y_i ( \boldsymbol{\omega}\cdot\mathbf{x}_i+\theta) \geq \hat{\gamma} ,&& i=1,2,\cdots,n \end{matrix}$

其中，函数间隔 $\hat{\gamma}$ 的取值并不影响最优化问题的解

假设将 $\boldsymbol{\omega}$ 和 $\theta$ 等比例的改变为 $k \boldsymbol{\omega}$ 和 $k\theta$，此时函数间隔就变为 $k\hat{\gamma}$，这一改变对上面的最优化问题的不等式约束没有任何影响，对目标函数的优化也没有影响

也就是说，其产生了一个等价的最优化问题，这样可以取函数间隔 $\hat{\gamma}=1$，而最大化 $\frac{1}{||\boldsymbol{\omega}||_2} $ 和最小化 $\frac{1}{2}||\boldsymbol{\omega}||_2^2 $ 是等价的（此处乘以 $\frac{1}{2}$ 是为了后续求偏导方便），于是可以得到如下等价的约束最优化问题：

可以发现，其是一个凸二次规划（Convex Quadratic Programming）问题

最大间隔法

硬间隔支持向量机的学习算法为最大间隔法

输入：线性可分的容量为 $n$ 的训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_n,y_n)\}$，第 $i$ 组样本中的输入 $\mathbf{x}_i$ 具有 $m$ 个特征值，即：$\mathbf{x}_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(m)})\in \mathbb{R}^m$，输出 $y_i\in\mathcal{Y}=\{+1,-1\}$

输出：最大间隔分离超平面、分类决策函数

算法步骤：

Step1：构造并求解如下约束最优化问题

求得最优解 $\boldsymbol{\omega}^*$ 和 $\theta^*$

Step2：根据最优解 $\boldsymbol{\omega}^*$ 和 $\theta^*$，得到分离超平面

$\boldsymbol{\omega}^* \cdot \mathbf{x} +\theta^* = 0$

以及分类决策函数

$f(\mathbf{x}) = \text{sign}(\boldsymbol{\omega}^*\cdot\mathbf{x}+\theta^*)$

【硬间隔支持向量机学习算法的对偶形式】

对偶问题的转化

为求解硬间隔支持向量机的原始问题：

将其作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题来得到原始问题的最优解，这样做的好处有两点：对偶问题更容易求解、容易引入核函数，进而推广到非线性分类问题

首先，构建拉格朗日函数，即为每一个不等式约束引入拉格朗日乘子 $\lambda_i\geq 0$，即：

$L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda}) = \frac{1}{2}||\boldsymbol{\omega}||_2^2 - \sum_{i=1}^n \lambda_i y_i(\boldsymbol{\omega}\cdot \mathbf{x}_i + \theta) + \sum_{i=1}^n \lambda_i$

其中，$\boldsymbol{\lambda}=(\lambda_1,\lambda_2,\cdots,\lambda_n)^T$ 为拉格朗日乘子向量

此时，根据拉格朗日对偶性，原始问题的对偶问题就变为了极大极小问题，即：

$\max_{\boldsymbol{\lambda}} \min_{\boldsymbol{\omega},\theta} L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda})$

因此，为了得到对偶问题的解，就要先求拉格朗日函数 $L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda})$ 对 $\boldsymbol{\omega}$ 和 $\theta$ 的极小，再求对 $\boldsymbol{\lambda}$ 的极大

对偶问题中的极小问题

对于对偶问题中的极小问题：

$\min_{\boldsymbol{\omega},\theta} L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda})$

令拉格朗日函数 $L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda})$ 分别对 $\boldsymbol{\omega}$ 和 $\theta$ 求偏导，并令其等于 $0$，即：

$\begin{align*} \triangledown_{\boldsymbol{\omega}} L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda}) &= \boldsymbol{\omega} - \sum_{i=1}^n \lambda_i y_i \mathbf{x}_i = 0 \\ \triangledown_{\theta} L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda}) &= -\sum_{i=1}^n \lambda_i y_i = 0 \end{align*}$

可得：

$\begin{gather*} \boldsymbol{\omega} = \sum_{i=1}^n \lambda_i y_i \mathbf{x}_i \\ \sum_{i=1}^n \lambda_i y_i = 0 \end{gather*}$

将上式带回拉格朗日函数 $L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda})$ 中，有：

$\begin{align*} L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda}) &= \frac{1}{2}||\boldsymbol{\omega}||_2^2 - \sum_{i=1}^n \lambda_i y_i(\boldsymbol{\omega}\cdot \mathbf{x}_i + \theta) + \sum_{i=1}^n \lambda_i \\ &= \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \lambda_i\lambda_j y_i y_j (\mathbf{x}_i\cdot\mathbf{x}_j) - \sum_{i=1}^n \lambda_iy_i \Big( \big(\sum_{j=1}^n \lambda_j y_j\mathbf{x}_j\big) \cdot \mathbf{x}_i +\theta \Big) + \sum_{i=1}^n \lambda_i \\ &= \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \lambda_i\lambda_j y_i y_j (\mathbf{x}_i\cdot\mathbf{x}_j)-\sum_{i=1}^n \sum_{j=1}^n \lambda_i\lambda_j y_i y_j (\mathbf{x}_i\cdot\mathbf{x}_j) - \theta\sum_{i=1}^n\lambda_i y_i + \sum_{i=1}^n \lambda_i \\ &= -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \lambda_i\lambda_j y_i y_j (\mathbf{x}_i\cdot\mathbf{x}_j) + \sum_{i=1}^n \lambda_i \end{align*}$

故有：

$\min_{\boldsymbol{\omega},\theta} L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda}) = -\frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n \lambda_i\lambda_j y_i y_j (\mathbf{x}_i\cdot\mathbf{x}_j) + \sum_{i=1}^n \lambda_i$

对偶问题中的极大问题

对于对偶问题中的极大问题：

$\max_{\boldsymbol{\lambda}} \min_{\boldsymbol{\omega},\theta} L(\boldsymbol{\omega},\theta,\boldsymbol{\lambda})$

即为对偶问题，有：

$\begin{matrix} \max\limits_{\boldsymbol{\lambda}} && -\frac{1}{2} \sum\limits_{i=1}^n \sum\limits_{j=1}^n \lambda_i\lambda_j y_i y_j (\mathbf{x}_i\cdot\mathbf{x}_j) + \sum\limits_{i=1}^n \lambda_i \\ s.t. && \sum\limits_{i=1}^n\lambda_i y_i= 0 \\ && \lambda_i \geq 0 ,\quad i=1,2,\cdots,n \end{matrix}$

将该问题的目标函数由求极大转为求极小，就得到如下的等价的对偶最优化问题：

$\begin{matrix} \min\limits_{\boldsymbol{\lambda}} && \frac{1}{2} \sum\limits_{i=1}^n \sum\limits_{j=1}^n \lambda_i\lambda_j y_i y_j (\mathbf{x}_i\cdot\mathbf{x}_j) - \sum\limits_{i=1}^n \lambda_i \\ s.t. && \sum\limits_{i=1}^n\lambda_i y_i= 0 \\ && \lambda_i \geq 0 ,\quad i=1,2,\cdots,n \end{matrix}$

可以发现，原始问题是凸优化问题，且 Slater 条件成立，那么，原始问题强对偶性成立，即求解原始问题可以转换为求解上述的对偶问题

假设上述的对偶问题对 $\boldsymbol{\lambda}$ 的解为 $\boldsymbol{\lambda}^* = (\lambda_1^*,\lambda_2^*,\cdots,\lambda_n^*)^T$，那么根据 KKT 条件，可得：

$\begin{gather*} \triangledown_{\boldsymbol{\omega}} L(\boldsymbol{\omega}^*,\theta^*,\boldsymbol{\lambda}^*) = \boldsymbol{\omega}^* - \sum_{i=1}^n \lambda_i^* y_i \mathbf{x}_i = 0 \\ \triangledown_{\theta} L(\boldsymbol{\omega}^*,\theta^*,\boldsymbol{\lambda}^*)= -\sum_{i=1}^n \lambda_i^* y_i = 0 \\ \lambda_i^*(y_i(\boldsymbol{\omega}^*\cdot \mathbf{x}_i+\theta^*)-1) = 0 \\ y_i(\boldsymbol{\omega}^*\cdot \mathbf{x}_i+\theta^*)-1 \geq 0 \\ \lambda_i^* \geq 0,\quad i=1,2,\cdots,n \end{gather*}$

故而有：

$\boldsymbol{\omega}^* = \sum_{i=1}^n \lambda_i^* y_i\mathbf{x}_i$

同时，其中至少有一个 $\lambda_j^*>0$，对此 $j$ 有：

$y_j(\boldsymbol{\omega}^* \cdot \mathbf{x}_j+\theta^*)-1=0$

将 $\boldsymbol{\omega}^* = \sum\limits_{i=1}^n \lambda_i^* y_i\mathbf{x}_i$ 带入到上式，并由 $y_j^2=1$，可得：

$\theta^* = y_j - \sum_{i=1}^n \lambda_i^* y_i (\mathbf{x_i}\cdot \mathbf{x}_j)$

故而，分离超平面可写为：

$\sum_{i=1}^n \lambda_i^* y_i(\mathbf{x}\cdot\mathbf{x}_i) + \theta^* =0$

分类决策函数可写为：

$f(\mathbf{x}) = \text{sign}\Big(\sum_{i=1}^n \lambda_i^* y_i(\mathbf{x}\cdot\mathbf{x}_i)+\theta^*\Big)$

对偶学习算法

根据上述对偶问题的推导，可得到硬间隔支持向量机的对偶学习算法

输出：最大间隔分离超平面、分类决策函数

算法步骤：

Step1：构造并求解如下约束最优化问题（原始问题的对偶问题）

求得最优解 $\boldsymbol{\lambda}^*$

Step2：根据最优解 $\boldsymbol{\lambda}^*$，计算分离超平面的法向量 $\boldsymbol{\omega}^*$ 和截距 $\theta^*$

对于法向量 $\boldsymbol{\omega}^*$，有：

$\boldsymbol{\omega}^* = \sum_{i=1}^n \lambda_i^* y_i\mathbf{x}_i$

选择最优解 $\boldsymbol{\lambda}^*$的一个正分量 $\lambda_j^*>0$，计算截距 $\theta^*$，有：

$\theta^* = y_j - \sum_{i=1}^n \lambda_i^* y_i (\mathbf{x_i}\cdot \mathbf{x}_j)$

Step3：根据最优解 $\boldsymbol{\omega}^*$ 和 $\theta^*$，得到分离超平面

$\boldsymbol{\omega}^* \cdot \mathbf{x} +\theta^* = 0$

以及分类决策函数

$f(\mathbf{x}) = \text{sign}(\boldsymbol{\omega}^*\cdot\mathbf{x}+\theta^*)$

对于 Step1 中的凸二次规划问题，可使用 SMO 算法来求解，关于 SMO 算法，详见：序列最小最优化算法 SMO

【支持向量与间隔边界】

在线性可分的情况下，对于训练集中与分离超平面距离最近的样本点 $(\mathbf{x}_i,y_i)$ 的实例 $\mathbf{x}_i$，被称为硬间隔的支持向量（Support Vector），即：

$y_i(\boldsymbol{\omega}\mathbf{x}_i+\theta)-1=0$

对于 $y_i=1$ 的正例点，支持向量位于超平面：

$H_1 : \boldsymbol{\omega} \cdot \mathbf{x} + \theta =1$

对于 $y_i=-1$ 的负例点，支持向量位于超平面：

$H_2 : \boldsymbol{\omega} \cdot \mathbf{x} + \theta = -1$

如图所示，在 $H_1$ 和 $H_2$ 上的点就是支持向量

可以发现，$H_1$ 与 $H_2$ 平行，两者之间形成一条长带，且没有样本点位于这条长带中，分离超平面与它们平行且位于它们中央

长带的宽度，即 $H_1$ 与 $H_2$ 间的距离被称为间隔（Margin），其依赖于超平面的法向量 $\boldsymbol{\omega}$，等于 $\frac{2}{||\boldsymbol{\omega}||_2}$，此外，称 $H_1$ 和 $H_2$ 为间隔边界（Margin Border）

在决定这个位于两类训练样本的正中间的分离超平面时，只有支持向量起作用，如果移动支持向量将改变所求的解

此外，对于分类决策函数：

$f(\mathbf{x}) = \text{sign}\Big(\sum_{i=1}^n \lambda_i^* y_i(\mathbf{x}\cdot\mathbf{x}_i)+\theta^*\Big)$

根据 KKT 条件，对于任意样本 $(\mathbf{x}_i,y_i)$，总有 $\lambda_i=0$ 或 $y_i(\boldsymbol{\omega}\cdot \mathbf{x}_i+\theta)=1$

当 $\lambda_i=0$ 时，该样本不会在分类决策函数 $f(\mathbf{x})$ 的求和中出现，也就不会对 $f(\mathbf{x})$ 造成任何影响
当 $\lambda_i>0$ 时，必有 $y_i(\boldsymbol{\omega}\cdot \mathbf{x}_i+\theta)=1$，所对应的样本点正好位于间隔边界上，是一个支持向量

也就是说，硬间隔支持向量机的分类决策函数只依赖于支持向量，即训练数据中对应于 $\lambda_i>0$ 的样本点 $(\mathbf{x}_i,y_i)$，其他样本点对 $\boldsymbol{\omega}^*$ 和 $\theta^*$ 没有影响