SVM-PPT

SVM

在线性分类器中，我们知道，线性分类器的任务就是在样本空间中寻找一个超平面，将不同类别的样本分开。但是，对于特定的样本空间，我们可能能够找到很多的超平面都满足条件，那么哪个超平面是最好的呢？

直觉上，我们认为“正中间”的是最好的，它离两类样本都比较远，拥有较好的鲁棒性和泛化能力。

我们已经知道，超平面的方程为 $\boldsymbol{w}^\mathrm T\boldsymbol{x}+b=0$，为了找到“正中间”的超平面，我们要找出两类样本中距离超平面最近的那一个，计算出二者的距离，再将超平面放在中间。

两类样本中距离超平面最近的那个样本直接定义了这个超平面，我们把这几个样本称为“支持向量”：

则两个支持向量之间的距离被称做“间隔”，为

$$\gamma = \dfrac 2{\|\boldsymbol{w}\|}$$

支持向量机基本型

上面的讨论很自然的可以化为一个最优化问题：寻找参数 $\boldsymbol{w}$ 和 $b$，使得 $\gamma$ 最大，即：

$$\begin{aligned} \underset{\boldsymbol{w}, b}{\arg\max}&\ \dfrac 2{\|\boldsymbol{w}\|} \\ &\text{s.t.}\ y_i(\boldsymbol{w}^\mathrm T\boldsymbol{x}_i + b) \geq 1,\ i = 1, 2, \dots, m \end{aligned}$$

上式中由于两个支持向量到超平面的距离为 $1$，所以约束中为 $\geq 1$。

考虑对问题做等价变换，得到

$$\begin{aligned} \underset{\boldsymbol{w}, b}{\arg\min}&\ \dfrac 12 \|\boldsymbol{w}\|^2 \\ &\text{s.t.}\ y_i(\boldsymbol{w}^\mathrm T\boldsymbol{x}_i + b) \geq 1,\ i = 1, 2, \dots, m \end{aligned}$$

这是一个凸二次规划问题，后文将使用拉格朗日乘子法进行解决。

不等式约束的最优化问题：

此类最优化问题的标准形式为：

$$\begin{aligned} \min_{\boldsymbol{x}}&\ f(\boldsymbol{x}) \\ & \text{s.t. } g_i(\boldsymbol{x}) \leq 0, h_j(\boldsymbol{x}) = 0\quad i \in [1, m], j \in [1, p] \end{aligned}$$

其中 $g_i(x)$ 为不等式约束，$h_j(x)$ 为等式约束，$m$ 和 $p$ 为约束个数。

定义拉格朗日函数

$$L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = f(\boldsymbol x) + \sum_{i=1}^m \lambda_i g_i(\boldsymbol x) + \sum_{k=1}^p \mu_k h_k(\boldsymbol x)$$

如果存在一组解 $\boldsymbol{x}^*$ 满足

$$\begin{cases} \nabla_x L = 0 \\ h_k(\boldsymbol x^*) = 0,\ k = 1, 2, \cdots, p \\ g_j(\boldsymbol x^*) \leq 0 \\ \mu_j \geq 0 \\ \mu_j g_j(\boldsymbol x^*) = 0,\ j = 1, 2, \cdots, m \end{cases}$$

则这组解 $\boldsymbol x^*$ 为满足条件的一组可行解。

举例：

$$\begin{aligned} \min&\ x_1^2 + x_2^2 \\ & \text{s.t.} \begin{cases} x_1 + x_2 = 1 \\ x_2 \leq \alpha \end{cases} \end{aligned}$$

问题的拉格朗日函数为

$$L(x_1, x_2, \boldsymbol \lambda, \mu) = x_1^2+x_2^2 + \lambda(1 - x_1 - x_2) + \mu(x_2 - \alpha)$$

KKT 方程组为

$$\begin{cases} \dfrac {\partial L}{\partial x_i} = 0, i = 1, 2 \\ x_1 + x_2 = 1 \\ x_2 - \alpha \leq 0 \\ \mu \geq 0 \\ \mu(x_2 - \alpha) = 0 \end{cases}$$

由偏导得到

$$\begin{cases} 2x_1 - \lambda = 0 \\ 2x_2 - \lambda + \mu = 0 \end{cases}$$

代入 $x_1 + x_2 = 1$ 得到

$$\begin{cases} x_1 = \dfrac \mu 4 + \dfrac 12 \\ x_2 = -\dfrac \mu 4 + \dfrac 12 \end{cases}$$

由 $x_2 -\alpha \leq 0$ 得到 $\mu \geq 2 - 4\alpha$，下面对 $\alpha$ 进行讨论：

1. 若 $2 - 4\alpha < 0$ 即 $\alpha > \frac 12$ 时，所有的 KKT 条件都能满足，此时得到一组解 $x_1^* = x_2^* = \frac 12$，目标函数的最小值为 $\frac 12$；
2. 若 $\alpha = \frac 12$ 时，也能满足所有的 KKT 条件，此时的解同上；
3. 若 $\alpha < \frac 12$ 时，$\mu > 0$，此时必须有 $x_2 = \alpha$，故 $x_1 = 1 - \alpha$，目标函数的极小值为 $\alpha^2 + (1 - \alpha)^2$。

注意到 KKT 条件中的其中一个为 $\mu g(\boldsymbol x) = 0$ 且 $\mu \geq 0$，则当 $g(\boldsymbol x) < 0$ 时，$\mu = 0$ 一定成立；而当 $g(\boldsymbol x) = 0$ 时，原问题变为若干个等式约束的最优化问题，必定有 $\mu > 0$。

根据定义，支持向量是位于间隔边缘上的点，此时有 $g(\boldsymbol x) = 0$，即 $\mu > 0$，于是有结论：对应 $\mu > 0$ 的点是支持向量。

核化法

核化法基于一个非常朴素的思考：前面的所有讨论都是基于训练样本是线性可分的基础上的，即我们可以找到一个超平面将训练样本正确分类。但在现实任务中，原始的样本空间可能是非线性可分的，即找不到一个能正确划分两类样本的超平面。

此时我们通过核化法将数据映射到一个更高维的特征空间，使得样本在特征空间中线性可分，从而完成分类任务。

定理：如果原始空间是有限维的，那么必定存在一个高维特征空间使样本线性可分。

设样本 $\boldsymbol x$ 映射后的向量为 $\phi(\boldsymbol x)$，划分超平面为 $f(\boldsymbol x) = \boldsymbol w^\mathrm T \phi(\boldsymbol x) + b$，则原始的最优化问题变为

$$\begin{aligned} \underset{\boldsymbol w, b}{\min}&\ \dfrac 12 \|\boldsymbol w\|^2 \\ &\text{s.t. } y_i(\boldsymbol w^\mathrm T\phi(\boldsymbol x_i) + b) \geq 1,\ i = 1, 2, \cdots, m \end{aligned}$$

其对偶问题为

$$\begin{aligned} \underset{\boldsymbol \alpha}{\max}&\ \sum_{i = 1}^m \alpha_i - \dfrac 12 \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right) \\ & \text{s.t. } \sum_{i = 1}^m \alpha_iy_i = 0, \alpha_i \geq 0, i = 1, 2, \cdots, m \end{aligned}$$

预测方程为

$$f(\boldsymbol x) = \boldsymbol w^\mathrm T\phi(\boldsymbol x) + b = \sum_{i = 1}^m\alpha_iy_i\phi(\boldsymbol x_i)^\mathrm T\phi(\boldsymbol x)+b$$

但是我们发现了一个计算上的问题：由于 $\phi(\boldsymbol x)$ 是一个维数非常高甚至无限的向量，两向量内积 $\phi(\boldsymbol x_i)^\mathrm T\phi(\boldsymbol x_j)$ 可能难以计算甚至无法计算，开销非常大。注意到，两个高维向量始终只以内积的形式出现，如果我们能找到一个可以代替内积的东西，同时比内积好计算，那么这个问题就可以解决了。

此时我们引入核函数 $\kappa(\boldsymbol x_i, \boldsymbol x_j) = \phi(\boldsymbol x_i)^\mathrm T \phi(\boldsymbol x_j)$，通过此我们可以绕过显式考虑特征映射和计算高维内积困难的问题。“核函数选择”成为决定支持向量机性能的关键。

常用的核函数有以下几种：

名称	表达式	参数
线性核	$\kappa(\boldsymbol x_i, \boldsymbol x_j) = \boldsymbol x_i^\mathrm T\boldsymbol x_j$
多项式核	$\kappa(\boldsymbol x_i, \boldsymbol x_j) = (\boldsymbol x_i^\mathrm T\boldsymbol x_j + r)^d$	$r$ 为偏移量，$d \geq 1$ 为多项式次数
高斯核	$\kappa(\boldsymbol x_i, \boldsymbol x_j) = \exp\left(-\frac{|\boldsymbol x_i - \boldsymbol x_j|^2}{2\sigma^2}\right)$	$\sigma > 0$ 为高斯核的带宽
拉普拉斯核	$\kappa(\boldsymbol x_i, \boldsymbol x_j) = \exp\left(-\frac{|\boldsymbol x_i - \boldsymbol x_j|}{\sigma}\right)$	$\sigma > 0$
Sigmoid 核	$\kappa(\boldsymbol x_i, \boldsymbol x_j) = \tanh(\beta\boldsymbol x_i^\mathrm T\boldsymbol x_j + \theta)$	$\beta > 0$，$\theta < 0$

例：假设 $r = 1$，$d = 2$，则多项式核函数为

$$\begin{aligned} (a \times b + 1)^2 &= (a \times b + 1)(a \times b + 1) \\ &= a^2b^2 + 2ab + 1 \\ &= (\sqrt 2a, a^2, 1) \cdot (\sqrt 2b, b^2, 1) \end{aligned}$$

映射函数为

$$\begin{cases} \phi: \mathbb R^1 \to \mathbb R^3 \\ (x) \to (z_1, z_2, z_3) = (\sqrt 2x, x^2, 1) \end{cases}$$

另一个例：当映射函数 $\phi(\boldsymbol x) = (x_1^2, \sqrt2x_1x_2, x_2^2)$ 时，多项式核函数的 $r$ 和 $d$ 分别是多少？

写做两个向量内积形式为

$$\begin{aligned} \phi(\boldsymbol x)\phi(\boldsymbol x') &= x_1x_1'^2 + 2x_1x_2x_1'x_2'+x_2x_2'^2 \\ &= (x_1x_1' + x_2x_2')^2 \\ &= (\boldsymbol x \times \boldsymbol x')^2 \end{aligned}$$

所以 $r = 0$，$d = 2$。

根据核函数我们可以推导得到特征空间中两个向量间的距离和夹角：

1. 两向量间的距离为

   $$\begin{aligned} \|\phi(\boldsymbol x) - \phi(\boldsymbol x')\| &= (\phi(\boldsymbol x) - \phi(\boldsymbol x'))^\mathrm T(\phi(\boldsymbol x) - \phi(\boldsymbol x')) \\ &= \phi(\boldsymbol x)^\mathrm T\phi(\boldsymbol x) - \phi(\boldsymbol x)^\mathrm T\phi(\boldsymbol x') - \phi(\boldsymbol x')^\mathrm T\phi(\boldsymbol x) + \phi(\boldsymbol x')^\mathrm T\phi(\boldsymbol x') \\ &= \kappa(\boldsymbol x, \boldsymbol x) - \kappa(\boldsymbol x, \boldsymbol x') - \kappa(\boldsymbol x', \boldsymbol x) + \kappa(\boldsymbol x', \boldsymbol x') \\ &= \kappa(\boldsymbol x, \boldsymbol x) - 2\kappa(\boldsymbol x, \boldsymbol x') + \kappa(\boldsymbol x', \boldsymbol x') \end{aligned}$$

2. 两向量间的夹角余弦为

   $$\begin{aligned} \cos \theta &= \dfrac{\phi(\boldsymbol x) \cdot \phi(\boldsymbol x')}{\|\phi(\boldsymbol x)\|\|\phi(\boldsymbol x')\|} \\ &= \dfrac{\phi(\boldsymbol x)^\mathrm T\phi(\boldsymbol x')}{\sqrt{\phi(\boldsymbol x)^\mathrm T\phi(\boldsymbol x)}\sqrt{\phi(\boldsymbol x')^\mathrm T\phi(\boldsymbol x')}} \\ &= \dfrac{\kappa(\boldsymbol x, \boldsymbol x')}{\sqrt{\kappa(\boldsymbol x, \boldsymbol x)}\sqrt{\kappa(\boldsymbol x', \boldsymbol x')}} \end{aligned}$$

以二分类为例，升维后我们找到两类数据的中心：

根据两类数据的中心可以算出两个中心间的向量 $\vec w = \vec {c_+} - \vec{c_-}$：

再计算出分隔这两类的超平面 $\vec c = \frac 12 (\vec{c_+} + \vec{c_-})$：

对于一个测试数据 $(\boldsymbol x, y) \to (\phi(\boldsymbol x), y)$：

1. 当数据属于正类时，有

   

   即

   $$0 \leq \theta < \dfrac \pi 2 \Longleftrightarrow 0 < \cos \theta \leq 1 \Longleftrightarrow \kappa(\phi(\boldsymbol x) - \vec c, \vec w) \geq 0$$

2. 当数据属于负类时，由上面讨论有 $\kappa(\phi(\boldsymbol x) - \vec c, \vec w) \leq 0$。

综上，数据类别为 $y = \operatorname{sign}(\kappa(\phi(\boldsymbol x) - \vec c, \vec w))$，现在考虑如何计算：

1. 若已知 $\phi(\boldsymbol x)$时，那么可以直接进行分类计算；

2. 在不知道 $\phi(\boldsymbol x)$ 时，可以通过核函数进行计算：

   $$\begin{aligned} \kappa(\phi(\boldsymbol x) - \vec c, \vec w) &= \boldsymbol w^\mathrm T(\phi(\boldsymbol x) - \boldsymbol c) \\ &= (\boldsymbol c_+ - \boldsymbol c_-)^\mathrm T\phi(\boldsymbol x) - \dfrac 12 (\boldsymbol c_+ - \boldsymbol c_-)^\mathrm T(\boldsymbol c_+ + \boldsymbol c_-) \\ &= \left(\dfrac 1{m_+} \sum_{(i \mid y_i = 1)} \phi(\boldsymbol x_i) - \dfrac 1{m_-} \sum_{(i \mid y_i = -1)} \phi(\boldsymbol x_i)\right)^\mathrm T\phi(\boldsymbol x) - \dfrac 12(\boldsymbol c_+^\mathrm T\boldsymbol c_+ - \boldsymbol c_-^\mathrm T \boldsymbol c_-) \\ &= \left(\dfrac 1{m_+} \sum_{(i \mid y_i = 1)} \phi(\boldsymbol x_i)^\mathrm T\phi(\boldsymbol x) - \dfrac 1{m_-} \sum_{(i \mid y_i = -1)} \phi(\boldsymbol x_i)^\mathrm T \phi(\boldsymbol x)\right) \\& - \dfrac 12\left(\dfrac 1{m_+} \sum_{(i \mid y_i = 1)} \phi(\boldsymbol x_i)^\mathrm T \cdot \dfrac1{m_+}\sum_{(j \mid y_j = 1)} \phi(\boldsymbol x_j) - \dfrac 1{m_-}\sum_{(i \mid y_i = -1)}\phi(\boldsymbol x_i)^\mathrm T\cdot\dfrac 1{m_-}\sum_{(j \mid y_j = -1)} \phi(\boldsymbol x_j)\right) \\ &= \left(\dfrac 1{m_+} \sum_{(i \mid y_i = 1)}\kappa(\boldsymbol x_i, \boldsymbol x) - \dfrac 1{m_-} \sum_{(i \mid y_i = -1)} \kappa(\boldsymbol x_i, \boldsymbol x)\right) \\ &- \dfrac 12 \left(\dfrac 1{m_+^2}\sum_{(i \mid y_i = 1)} \sum_{(j \mid y_j = 1)} \kappa(\boldsymbol x_i, \boldsymbol x_j) - \dfrac 1{m_-^2}\sum_{(i \mid y_i = -1)} \sum_{(j \mid y_j = -1)} \kappa(\boldsymbol x_i, \boldsymbol x_j)\right) \end{aligned}$$

   我们发现，即便是我们只有核函数，我们仍然能够在高维空间（特征空间）里面进行分类。

   综上，映射函数 $\phi$ 不是必须的，只有核矩阵

   $$\begin{bmatrix} \kappa(x_1, x_1) & \kappa(x_1, x_2) & \cdots & \kappa(x_1, x_n) \\ \kappa(x_2, x_1) & \kappa(x_2, x_2) & \cdots & \kappa(x_2, x_n) \\ \vdots & \vdots & \vdots & \vdots \\ \kappa(x_n, x_1) & \kappa(x_n, x_2) & \cdots & \kappa(x_n, x_n) \end{bmatrix}$$

   是半正定时，$\kappa(\cdot, \cdot)$ 才是一个可使用的核函数；给定一个 $\phi$ 也能找到其对应的 $\kappa$，给定一个 $\kappa$ 也能找到一个对应的特征空间使得 $\kappa$ 对应空间中的向量内积。

   半正定：给定一个大小为 $n \times n$ 的实对称矩阵 $A$，若对于任意长度为 $n$ 的向量 $x$，有 $x^\mathrm TAx\geq 0$ 恒成立，则称矩阵 $A$ 是一个半正定矩阵。

硬间隔 SVM

在上面的讨论中，我们得到 hard-margin SVM 的最优化问题：

$$\begin{aligned} \underset{\boldsymbol{w}, b}{\arg\min}&\ \dfrac 12 \|\boldsymbol{w}\|^2 \\ &\text{s.t.}\ y_i(\boldsymbol{w}^\mathrm T\boldsymbol{x}_i + b) \geq 1,\ i = 1, 2, \dots, m \end{aligned}$$

构造拉格朗日函数：

$$L(\boldsymbol w, b, \boldsymbol \alpha) = \dfrac 12 \boldsymbol w^\mathrm T\boldsymbol w +\sum_{i=1}^m \alpha_i(1 - y_i(\boldsymbol w^\mathrm T\boldsymbol x_i + b))$$

分别对 $\boldsymbol w$、$b$ 求偏导可得

\begin{aligned} \dfrac{\part L}{\part \boldsymbol w} &= 0 \Longrightarrow \boldsymbol w = \sum_{i=1}^m \alpha_iy_i\boldsymbol x_i \\ \dfrac {\part L}{\part b} &= 0 \Longrightarrow \sum_{i = 1}^m \alpha_iy_i = 0 \end{aligned}

将上述两式代入拉格朗日函数得

$$\begin{aligned} L(\alpha) &= \dfrac 12 \boldsymbol w^\mathrm T\boldsymbol w + \sum_{i=1}^m \alpha_i - \sum_{i=1}^m \alpha_iy_i\boldsymbol w^\mathrm T \boldsymbol x_i - \sum_{i=1}^m \alpha_iy_ib \\ &= \dfrac 12 \left(\sum_{i=1}^m \alpha_iy_i \boldsymbol x_i^\mathrm T\right)\left(\sum_{j=1}^m \alpha_jy_j\boldsymbol x_j\right) + \sum_{i=1}^m \alpha_i - \sum_{i=1}^m \alpha_iy_i\left(\sum_{j=1}^m \alpha_jy_j \boldsymbol x_j^\mathrm T\right) \boldsymbol x_i \\ &= \sum_{i=1}^m \alpha_i - \dfrac 12 \sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j \boldsymbol x_i^\mathrm T \boldsymbol x_j \end{aligned}$$

结合上面对 $b$ 的偏导得到的约束，我们得到原最优化问题的对偶问题：

$$\begin{aligned} \underset{\boldsymbol \alpha}{\max}& \sum_{i=1}^m \alpha_i - \dfrac 12 \sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j \boldsymbol x_i^\mathrm T \boldsymbol x_j \\ &\text{s.t. } \sum_{i=1}^m \alpha_iy_i = 0, \alpha_i \geq 0,\ i = 1, 2, \cdots, m \end{aligned}$$

下面证明上式存在最大值：

若推广至高维只需要 $\boldsymbol x \to \phi(\boldsymbol x)$，$\boldsymbol x_i^\mathrm T \boldsymbol x_j \to \kappa(\boldsymbol x_i, \boldsymbol x_j)$。

软间隔 SVM

由于 hard-margin SVM 无法容忍无法线性可分的情况，可能在确定超平面时出现过拟合的情况，于是我们允许一部分异类样本落入另一侧的区域，形成 soft-margin SVM。此时最优化问题可写为

$$\begin{aligned} \underset{\boldsymbol w, b, \boldsymbol \xi}{\min}&\ \dfrac 12 \boldsymbol w^\mathrm T \boldsymbol w + C \sum_{i = 1}^m \xi_i, C > 0 \\ &\text{s.t. } \xi_i \geq 0, y_i(\boldsymbol w^\mathrm T \boldsymbol x_i + b) \geq 1 - \xi_i,\ i = 1, 2, \cdots, m \end{aligned}$$

其中 $\xi_i$ 被称为松弛变量。

当 $C$ 增大时，$\sum \xi_i$ 必定减小，$\xi_i$ 必定减小，则由限制可知间隔减小。

上问题的拉格朗日函数为

$$L(\boldsymbol w, b, \boldsymbol \xi, \boldsymbol \alpha, \boldsymbol \beta) = \dfrac 12 \boldsymbol w^\mathrm T \boldsymbol w + C\sum_{i = 1}^m \xi_i + \sum_{i = 1}^m \alpha_i[1 - \xi_i - y_i(\boldsymbol w^\mathrm T \boldsymbol x_i + b)] - \sum_{i = 1}^m \beta_i \xi_i$$

令上式分别对 $\boldsymbol w$、$b$ 和 $\boldsymbol \xi$ 求偏导可得

\begin{aligned} \dfrac {\part L}{\part \boldsymbol w} &= 0 \Longrightarrow \sum_{i = 1}^m \alpha_iy_i\boldsymbol x_i = \boldsymbol w \\ \dfrac {\part L}{\part b} &= 0 \Longrightarrow \sum_{i = 1}^m \alpha_iy_i = 0 \\ \dfrac {\part L}{\part \xi_i} &= 0 \Longrightarrow C - \alpha_i - \beta_i =0 \rightarrow 0 \leq \alpha_i, \beta_i \leq C \end{aligned}