梳理 SVM、Soft-margin SVM 及其对偶形式

1. 原始 SVM 问题

SVM (Supported Vector Machine) 要解决的是线性可分的分类问题，同时希望分类间隔 (margin) 尽可能大。

图1. SVM 分类超平面 (图片来自维基百科)

为什么 $\mathrm{margin}=\frac{2}{\lVert \mathbf w\rVert}$ 呢？

我们可以先从图中找到两个支持向量（即在虚线上的绿点 $\mathbf x^{-}$ 和蓝点 $\mathbf x^{+}$），我们有：

$$
\mathbf w(\mathbf x^{+}-\mathbf x^{-})=2 \Leftrightarrow \lVert \mathbf w\rVert \cdot \lVert \mathbf x^{+} -\mathbf x^{-}\rVert \cos\theta=2
$$

而 $\mathrm{margin}=\lVert \mathbf x^{+}-\mathbf x^{-}\rVert \cos\theta$，所以有 $\mathrm{margin}=\frac{2}{\lVert \mathbf w\rVert}$。

而最大化 $\mathrm{margin}=\frac{2}{\lVert \mathbf w\rVert}$ 等价于最小化 $\mathbf w^T\mathbf w$。

那么，原始 SVM 问题就是：
$$
\begin{equation}\begin{split}
\min \frac{1}{2}\mathbf w^T\mathbf w\newline
\mbox{subject to}\quad y_i(\mathbf w^T\mathbf x_i+b)\ge 1,\newline
\forall i=1,2,\dots,n
\end{split}\tag{1.1}
\end{equation}
$$

2. Soft-margin SVM

由于原始 SVM 问题的分类超平面的选取跟支持向量直接相关。为了解决错样本点（或者噪声样本点）带来的线性不可分的问题，Soft-margin SVM 通过引入新的参数 $\xi_i$ 从而允许错误样本点的存在。
$$
\begin{equation}\begin{split}
\min \frac{1}{2}\mathbf w^T\mathbf w+C\sum_i^n\xi_i \newline
\mbox{subject to}\quad\begin{cases}y_i(\mathbf w^T\mathbf x_i+b)\ge 1-\xi_i,\newline \xi_i\ge 0,\end{cases}\newline
\forall i=1,2,\dots,n
\end{split}\tag{2.1}
\end{equation}
$$
$\xi_i$ 表示第 $i$ 个样本点犯错误的程度。超参 $C$ 用来调节 $\mathrm{margin}$ 和犯错程度 $\sum\limits_i^n\xi_i$ 。更大的 $C$ 表示希望尽量减小犯错误程度 $\sum\limits_i^n\xi_i$，也意味着 $\mathrm{margin}$ 会变得更窄，反之亦然。

可以发现，这个问题是一个二次规划问题 (Quadratic programming)。限制条件个数是 $2n$，训练变量个数是 $2d+n$ ，通常来讲 $d \ll n$（$d$ 是变量 $x$ 的维度，$n$ 是样本点个数）。

下面介绍一下通过拉格朗日乘子法和 KKT 条件，以及如何用他们得到 Soft-margin SVM 的对偶形式。

3. 拉格朗日乘子法 & KKT 条件

3.1 拉格朗日乘子法

拉格朗日乘子法 (Lagrange Multipliers)^[1]^[2] 处理的是等式约束下的最优化问题。
$$
\begin{equation}\begin{split}
\min f(\mathbf x)\newline
\mbox{subject to }\quad h_i(\mathbf x)=0,\newline
\forall i=1,\dots,m\newline
\end{split}\end{equation}
$$

构造一个拉格朗日函数 $L(\mathbf x,\lambda)$：

$$
L(\mathbf x,\lambda)=f(\mathbf x)+\sum\limits_i^m\lambda_ih_i(\mathbf x)
$$

极值点存在的必要不充分条件就是对 $\mathbf x,\lambda$ 偏导数为$0$，

3.4 KKT 条件

而 KKT 条件 (Karush-Kuhn-Tucker Conditions) ^[1]^[3] 处理的是不等式约束下的最优化问题。
$$
\begin{equation}\begin{split}
\min f(\mathbf x)\newline
\mbox{subject to }\begin{cases}
h_i(\mathbf x)=0, \forall i=1,\dots,m\newline
g_i(\mathbf x)\le 0, \forall i=1,\dots,n\newline
\end{cases}
\end{split}\end{equation}
$$

构造一个拉格朗日函数 $L(\mathbf x,\lambda)$：

$$
L(\mathbf x,\lambda)=f(\mathbf x)+\sum\limits_i^m\lambda_ih_i(\mathbf x)+\sum\limits_i^n\mu_ig_i(\mathbf x)
$$

极值点存在的必要不充分条件就是对 $\mathbf x,\lambda$ 偏导数为$0$，且 $\color{red}{\mu_ig_i(\mathbf x)=0, \mu_i\ge 0}$^[4]，

$$
\begin{cases}
\frac{\partial L}{\partial\mathbf x}=\frac{\partial f(\mathbf x)}{\partial \mathbf x}+\sum\limits_i^m\lambda_i\frac{\partial h_i(\mathbf x)}{\partial\mathbf x}+\sum\limits_i^n\mu_i\frac{\partial g_i(\mathbf x)}{\partial\mathbf x}=0\newline
\frac{\partial L}{\partial \lambda_i}=h_i(\mathbf x)=0, \quad i=1,\dots,m\newline
\mu_ig_i(\mathbf x)=0, \quad i=1,\dots,n\newline
\mu_i\ge 0, \quad i=1,\dots,n\newline
\end{cases}
$$

4. Soft-margin SVM 的对偶形式

写出 $(2.1)$ 对应的拉格朗日函数 $L(\mathbf w,b,\xi,\lambda,\mu)$：

$$
\begin{equation}\begin{split}
L(\mathbf w,b,\xi,\lambda,\mu)&=\frac{1}{2}\mathbf w^T\mathbf w+C\sum\limits_i^n\xi_i-\sum\limits_i^n\lambda_i[y_i(\mathbf w^T\mathbf x_i+ b)-(1-\xi_i)]-\sum\limits_i^n\mu_i\xi_i\newline
\mbox{where } & \lambda_i, \mu_i \ge 0
\end{split}\end{equation}
$$

显然，$\frac{1}{2}\mathbf w^T\mathbf w+C\sum\limits_i^n\xi_i \ge L(w,b,\xi,\lambda,\mu)$。换言之，拉格朗日函数 $L(\mathbf w,b,\xi,\lambda,\mu)$ 是原目标函数的下界，最小化原目标函数等价于最大化其下界函数，即最大化 $L(\mathbf w,b,\xi,\lambda,\mu)$ 。

跟据 KKT 条件，拉格朗日函数 $L(\mathbf w,b,\xi,\lambda,\mu)$ 的极值点的必要不充分条件是:
$$
\begin{cases}
\frac{\partial L}{\partial \mathbf{w}}=\mathbf w-\sum\limits_i^n\lambda_iy_i\mathbf x_i=0,\newline
\frac{\partial L}{\partial b}=-\sum\limits_i^n\lambda_iy_i=0, \newline
\frac{\partial L}{\partial \xi}=C-\lambda-\mu=0, \newline
\lambda_i\left[y_i(w^Tx_i+b)-(1-\xi_i)\right]=0\newline
\mu_i\xi_i=0\newline
\lambda_i, \mu_i\ge 0
\tag{4.1}
\end{cases}
$$

将约束条件代入拉格朗日函数 $L(\mathbf w,b,\xi,\lambda,\mu)$，得：

$$
\require{enclose}
\begin{equation}
\begin{split}
g(\lambda)&=\inf_{\mathbf w,b,\xi\in \mathcal D}L(\mathbf w,b,\xi,\lambda,\mu)\newline
&=\inf_{\mathbf w,b,\xi\in \mathcal D}\left\lbrace\frac{1}{2}\mathbf w^T\mathbf w+C\sum\limits_i^n\xi_i-\sum\limits_i^n\lambda_i[y_i(\mathbf w^T\mathbf x_i+b)-(1-\xi_i)]-\sum\limits_i^n\mu_i\xi_i\right\rbrace\newline
&=\inf_{\mathbf w,b,\xi\in \mathcal D}\left\lbrace\frac{1}{2}\mathbf w^T\mathbf w+\enclose{horizontalstrike}{\sum_i^n\xi_i(C-\lambda_i-\mu_i)}-\mathbf w^T\sum\limits_i^n\lambda_iy_i\mathbf x_i-\enclose{horizontalstrike}{b\sum\limits_i^n\lambda_iy_i}+\sum\limits_i^n\lambda_i\right\rbrace\newline
&=\frac{1}{2}\mathbf w^T\mathbf w-\mathbf w^T\mathbf w+\sum\limits_i^n\lambda_i\newline
&=-\frac{1}{2}\sum_i^n\sum_j^n\lambda_i\lambda_jy_iy_j\mathbf x_i^T\mathbf x_j+\sum\limits_i^n\lambda_i\newline
\end{split}
\tag{4.2}
\end{equation}
$$

那么，对 $(4.1)$ 中的公式化简之后，最终我们可以得到 Soft-margin SVM 的对偶形式 (Dual problem)：
$$
\begin{equation}\begin{split}
\min \frac{1}{2}\sum_i^{n}\sum_j^{n}\lambda_i\lambda_jy_iy_j\mathbf x_i^{T}\mathbf x_j-\sum_i^n\lambda_i\newline
\mbox{subject to}\begin{cases}
\sum\limits_i^{n}\lambda_iy_i=0, \newline
0\le \lambda_i\le C
\end{cases}
\end{split}\tag{4.3}\end{equation}
$$

对偶形式虽然依旧是一个二次规划问题，但是限制条件的形式都简化了，只有一个等式约束和方形约束 (Box constraints)，这是可以用 SMO (Sequential minimal optimization)^[6] 求解的问题。

假设现在已经求得了对偶问题的最优解 $\lambda^*$，那么，原问题的最优解：

$\mathbf w^*=\sum\limits_i^n\lambda_i^*y_i\mathbf x_i$；
而 $b^{\ast}$ 的值可以根据支持向量方程 $b^*=y_i-\mathbf w^{*T}\mathbf x_i$ 来求解，点 $(\mathbf x_i,y_i)$ 是支持向量当且仅当 $\lambda_i$ 为 $0$，而且此时 $\xi_i=0$ ；
然后，枚举所有样本点就可以求得 $\xi^*$。
那么，分类决策函数 $p(\mathbf x)=\mathrm{sign}(\mathbf w^{*T}\mathbf x+b^{\ast})$。

下面的问题就是如何用 SMO 求解对偶问题的最优解 $\lambda^*$。

5. Sequential minimal optimization (SMO)

SMO 是一种迭代优化算法^[6]^[7]：

首先随机构造一组初始解 $\lambda^{0}$；
然后选两个变量 $\lambda_{i}, \lambda_{j}$ 进行优化，将其他变量看成常量。由于存在一个等式约束，所以这两个变量是线性相关的，此时实际上是一个单变量二次规划问题，存在闭式解。
并迭代这个过程，直到所有的变量都满足 KKT 条件，或者目标函数 $g(\lambda)$ 增长率小于某个阈值，即:

$$
\frac{g(\lambda^{t+1})-g(\lambda^{t})}{g(\lambda^{t})}\lt T
$$

那么，步骤 2 中怎么选出两个变量 $\lambda_i, \lambda_j$ 进行优化呢？这里我引用一下 Github/familyld

怎么选取 $\lambda_i$ 和 $\lambda_j$呢？^[8]^[9]

注意到，只要选取的 $\lambda_i$ 和 $\lambda_j$ 中有一个不满足KKT条件，那么更新后目标函数的值就会增大。而且违背KKT条件的程度越大，则更新后导致目标函数增幅就越大。

因此，SMO算法先选取一个违背KKT条件程度最大的变量 $\lambda_i$，然后再选一个使目标函数增长最快的变量 $\lambda_j$，但由于找出 $\lambda_j$ 的开销较大，所以SMO算法采用了一个启发式，使选取的两变量对应的样本之间间隔最大。这样两个变量差别很大，与选取两个相似变量相比，这种方法能为目标函数带来更大的变化，从而更快搜索到全局最大值。

6. SVM 的非线性拓展: 核函数 (Kernel Function)

对于非线性分类问题，我们可以通过对特征进行非线性映射/变换，然后在变换后的特征空间里面进行线性分类，即 $f(\mathbf x)=\mathbf w^T\phi(\mathbf x)+b$。

$\phi(\mathbf x)$ 通常是由 $\mathbf x$ 的各个属性的高阶项组成的向量，在阶数确定的情况下，随着变量 $\mathbf x$ 的维度的增加，$\phi(\mathbf x)$ 的维度是指数增长的。

更好的做法是使用核函数 (Kernel Function)，核函数 $\kappa(\mathbf{x}_i,\mathbf{x}_j)$ 从形式上看就是特征映射函数的内积：

$$
\kappa(\mathbf{x}_i,\mathbf{x}_j)=\phi(\mathbf{x_i})^T\phi(\mathbf{x_j})
$$

引入核函数之后，Soft-margin SVM 的对偶问题 $(4.3)$ 可以写成：
$$
\begin{equation}\begin{split}
\min \frac{1}{2}\sum_i^n\sum_j^n\lambda_i\lambda_jy_iy_j\kappa(\mathbf x_i,\mathbf x_j)-\sum_i^n\lambda_i\newline
\mbox{subject to}\begin{cases}
\sum\limits_i^n\lambda_iy_i=0, \newline
0\le \lambda_i\le C
\end{cases}
\end{split}\tag{6.1}\end{equation}
$$

而且，有 $\mathbf w^{\ast}=\sum\limits_i^n\lambda_i^{\ast}y_i\phi(\mathbf x_i)$。

对应的判别函数为：
$$
\begin{equation}\begin{split}
f(\mathbf x)&=\mathbf w^{\ast T}\phi(\mathbf x)+b\newline
&=\sum\limits_i^n\lambda_i^{\ast}y_i\phi(\mathbf x_i)^T\phi(\mathbf x)+b\newline
&=\sum\limits_i^n\lambda_i^{\ast}y_i\kappa(\mathbf{x}_i,\mathbf{x})+b\newline
&=\sum\limits_{(\lambda_i\neq 0)\cap (i=1,\dots,n)}\lambda_i^{\ast}y_i\kappa(\mathbf{x}_i,\mathbf{x})+b\newline
\end{split}\tag{6.2}\end{equation}
$$

变换后的特征空间可能维度很高，甚至可能是无穷维，直接 $\phi(\mathbf x)$ 的计算量可能就会很大。而此时我们可以计算 $\mathbf x$ 与支持向量$\mathbf x_i$（即满足 $\lambda_i \neq 0$ 的点）的核函数 $\kappa(\mathbf{x}_i,\mathbf{x})$，从而减小计算量。

比如说高斯核函数（或称径向基核函数）$\kappa(\mathbf{x}_i,\mathbf{x}_j)=\exp (-\frac{\Vert \mathbf{x}_i-\mathbf{x}_j \Vert ^2}{2\sigma^2})$ 实际上无穷维特征空间中点的内积。证明如下：
$$
\begin{equation}\begin{split}
\kappa(\mathbf{x}_i,\mathbf{x}_j)&=\exp\left(-\frac{\Vert \mathbf{x}_i-\mathbf{x}_j \Vert ^2}{2\sigma^2}\right)\newline
&=\exp\left(-\frac{\Vert \mathbf{x}_i\rVert^2+\lVert\mathbf{x}_j \Vert ^2-2\mathbf x_i^T\mathbf x_j}{2\sigma^2}\right)\newline
&=\exp\left(-\frac{\Vert \mathbf{x}_i\rVert^2}{2\sigma^2}\right)\exp\left(-\frac{\Vert \mathbf{x}_j\rVert^2}{2\sigma^2}\right) \exp\left(\frac{\mathbf x_i^T\mathbf x_j}{\sigma^2}\right)\newline
&\Downarrow \mbox{泰勒展开}\newline
&=\exp\left(-\frac{\Vert \mathbf{x}_i\rVert^2}{2\sigma^2}\right)\exp\left(-\frac{\Vert \mathbf{x}_j\rVert^2}{2\sigma^2}\right) \sum_{n=0}^{+\infty}\frac{\left(\frac{\mathbf x_i^T\mathbf x_j}{\sigma^2}\right)^n}{n!}\newline
&=\exp\left(-\frac{\Vert \mathbf{x}_i\rVert^2}{2\sigma^2}\right)\exp\left(-\frac{\Vert \mathbf{x}_j\rVert^2}{2\sigma^2}\right) \sum_{n=0}^{+\infty}\frac{\left({\mathbf x_i^T\mathbf x_j}\right)^n}{n!\sigma^{2n}}\newline
&=\exp\left(-\frac{\Vert \mathbf{x}_i\rVert^2}{2\sigma^2}\right)\sum_{n=0}^{+\infty}\frac{(\mathbf x_i^T)^n}{\sigma^{n}\sqrt{n!}} \exp\left(-\frac{\Vert \mathbf{x}_j\rVert^2}{2\sigma^2}\right) \sum_{n=0}^{+\infty}\frac{(\mathbf x_j)^n}{\sigma^{n}\sqrt{n!}}\newline
\end{split}\tag{6.3}\end{equation}
$$

所以，高斯核函数（或称径向基核函数）对应的特征映射函数为：
$$
\begin{equation}\begin{split}
\phi(\mathbf{x})&=\exp\left(-\frac{\Vert \mathbf{x}\rVert^2}{2\sigma^2}\right)\sum_{n=0}^{+\infty}\frac{(\mathbf x)^n}{\sigma^{n}\sqrt{n!}}\newline
&=\exp\left(-\frac{\lVert\mathbf x \rVert^2}{2\sigma^2}\right) \cdot\left(1, \frac{1}{\sigma\sqrt{1!}}\mathbf x,\frac{1}{\sigma^2\sqrt{2!}}\mathbf x^2,\cdots\right)\newline
\mbox{Here, } \mathbf{x}^n&=\mathbf x \cdot\mathbf x^T\cdot\mathbf x\cdot\mathbf x^T\cdots;\newline
\mbox{e.g. }\mathbf{x}^2&=\mathbf x\mathbf x^T, \mathbf{x}^3=\mathbf x\mathbf x^T\mathbf x\newline
\end{split}\tag{6.4}\end{equation}
$$