西瓜书笔记：支持向量机（第 6 章）

支持向量机，核方法等。

最大化间隔

给定训练集

$$D=\{ ({\pmb{x_1}}, y_1), ({\pmb{x_2}}, y_2), \ldots, ({\pmb{x_m}}, y_m) \}, y_i \in \{ -1, +1 \}$$

寻找 划分超平面 将样本集按不同类别分开。其中，划分超平面 可以用如下方程表示：

$${\pmb w}^{\mathrm T} {\pmb x} + b = 0$$

其中 ${\pmb w}^{\mathrm T}$ 为法向量，$b$ 为位移项。则样本空间中任意点 ${\pmb x}$ 到该平面的距离为

$$r = \frac{\vert {\pmb w}^{\mathrm T} {\pmb x} + b \vert}{\Vert {\pmb w} \Vert}$$

缩放 ${\pmb w}$ 与 $b$ 使得训练集中所有点到到超平面的最小距离为 $\frac{1}{\Vert {\pmb w} \Vert}$，则有

$$\begin{cases} {\pmb w}^{\mathrm T} {\pmb{x_i}} + b \geq 1, \; & \mathrm{if} \; y_i = +1 \\ {\pmb w}^{\mathrm T} {\pmb{x_i}} + b \leq -1, \; & \mathrm{if} \; y_i = -1 \end{cases}$$

上式等价于

$$y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) \geq 1$$

支持向量机 的目标是最大化间隔，即

$$\begin{aligned} \max_{\pmb w, b} \quad & \frac{2}{\Vert {\pmb w} \Vert} \\ \mathrm{s.t.} \quad & y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) \geq 1 \end{aligned}$$

上式等价于

$$\begin{aligned} \min_{\pmb w, b} \quad & \frac{1}{2} \Vert {\pmb w} \Vert^2 \\ \mathrm{s.t.} \quad & y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) \geq 1 \end{aligned}$$

这就是 支持向量机 的 基本型。该问题本身是一个 凸二次规划 问题，可以直接用优化计算包求解。

对偶问题

对 基本型 的每一条约束添加朗格朗日乘子 $\alpha_i \geq 0$，则该问题的拉格朗日函数可以写为

$$L({\pmb w}, b, {\pmb \alpha}) = \frac{1}{2} \Vert {\pmb w} \Vert^2 + \sum_{i=1}^{m} \alpha_i \left( 1 - y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) \right)$$

令 $L({\pmb w}, b, {\pmb \alpha})$ 对 ${\pmb w}$ 与 $b$ 求偏导，得到

$$\begin{cases} {\pmb w} = \sum_{i=1}^{m} \alpha_i y_i {\pmb{x_i}} \\ 0 = \sum_{i=1}^{m} \alpha_i y_i \end{cases}$$

将上式代回 $L({\pmb w}, b, {\pmb \alpha})$，得到

$$\begin{aligned} \max_{\pmb \alpha} \quad & \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \underbrace{\sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j {\pmb{x_i}}^{\mathrm T} {\pmb{x_j}}}_{=\Vert \sum_{i=1}^{m} \alpha_i y_i {\pmb{x_i}} \Vert^2} \\ \mathrm{s.t.} \quad & \sum_{i=1}^{m} \alpha_i y_i = 0, \, \alpha_i \geq 0 \end{aligned}$$

这就是 支持向量机 的 对偶型。该问题也是一个 凸二次规划 问题，可以直接用优化计算包求解。

注意到

• 对偶问题约束有 $$\alpha_i \geq 0$$
• 原问题约束有 $$y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) - 1 \geq 0$$
• 拉格朗日函数中，若 $\alpha_i > 0$，则必有 $ 1 - y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) = 0$，因此 $$\alpha_i \left( y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) - 1 \right) = 0$$ 以上三条构成 KKT （Karush-Kuhn-Tucker）条件，即 $$\begin{cases} \alpha_i \geq 0 \\ y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) - 1 \geq 0 \\ \alpha_i \left( y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) - 1 \right) = 0 \end{cases}$$ 其中，$\alpha_i > 0$ 对应的点 ${\pmb{x_i}}$ 满足 $ y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) - 1 = 0$，也就是 支持向量。一般，绝大多数点对应的 $\alpha_i = 0$，是 非支持向量。

SMO 算法

每次选取一对 $( \alpha_i, \alpha_j)$，确保 $( \alpha_i, \alpha_j)$ 中至少有一个违背 KKT 条件；然后，固定 ${\pmb \alpha}$ 向量中所有其他元素，更新 $( \alpha_i, \alpha_j)$ 的值。这样每次更新后目标函数的值都能变大。

核函数

若训练集线性不可分，则可以将样本 ${\pmb x}$ 从 原始空间 映射到一个 高维空间，记映射后得到的 特征向量 为 $\phi({\pmb x})$。在映射后特征空间中的 划分超平面 为

$$f({\pmb x}) = {\pmb w}^{\mathrm T} \phi({\pmb x}) + b$$

映射后特征空间中的 基本型 为

$$\begin{aligned} \min_{\pmb w, b} \quad & \frac{1}{2} \Vert {\pmb w} \Vert^2 \\ \mathrm{s.t.} \quad & y_i \left({\pmb w}^{\mathrm T} {\phi(\pmb{x_i})} + b \right) \geq 1 \end{aligned}$$

其 对偶型 为

$$\begin{aligned} \max_{\pmb \alpha} \quad & \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j {\phi(\pmb{x_i})}^{\mathrm T} {\phi(\pmb{x_j})} \\ \mathrm{s.t.} \quad & \sum_{i=1}^{m} \alpha_i y_i = 0, \, \alpha_i \geq 0 \end{aligned}$$

在实践中，只需要知道任意 ${\pmb{x_i}}$ 与 ${\pmb{x_j}}$ 在映射后的内积 $\phi({\pmb{x_i}})^{\mathrm T} \phi({\pmb{x_j}})$ 即可，不必知道映射 $\phi$ 的具体形式。所以，定义核函数：

$$\kappa({\pmb{x_i}}, {\pmb{x_j}}) = \phi({\pmb{x_i}})^{\mathrm T} \phi({\pmb{x_j}})$$

常用核函数有

核函数	表达式	参数说明
线性核	$\kappa({\pmb{x_i}}, {\pmb{x_j}}) = \pmb{x_i}^{\mathrm T} \pmb{x_j}$
多项式核	$\kappa({\pmb{x_i}}, {\pmb{x_j}}) = \left( \pmb{x_i}^{\mathrm T} \pmb{x_j} \right)^d$	$d \ge 1$，为多项式次数
高斯核	$\kappa({\pmb{x_i}}, {\pmb{x_j}}) = \exp \left( -\frac{\Vert \pmb{x_i} - \pmb{x_j} \Vert^2}{2 \sigma^2} \right)$	$\sigma > 0$，为带宽

软间隔

允许一些样本不满足约束 $y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) \geq 1$，但需要施加惩罚。所以，优化目标可以写为

$$\min_{\pmb w, b} \quad \frac{1}{2} \Vert {\pmb w} \Vert^2 + C \cdot \sum_{i=1}^{m} {\mathcal L}_{0/1} \left( y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) - 1 \right)$$

其中，$C$ 是惩罚力度，${\mathcal L}_{0/1}(\cdot)$ 是 0/1 损失函数，即

$${\mathcal L}_{0/1}(z) = \begin{cases} 1, \; \mathrm{if} \; z < 0 \\ 0, \; \mathrm{if} \; z \ge 0 \end{cases}$$

注意该损失函数中，约束违背的 程度 不影响惩罚项的大小。其他损失函数形式有：

损失函数	表达式
Hinge 损失函数	${\mathcal L}_{hinge}(z) = \max(0, 1-z)$
指数损失函数	${\mathcal L}_{exp}(z) = \exp(-z) $
对数损失函数	${\mathcal L}_{log}(z) = \log(1 + \exp(-z))$

若采用 Hinge 损失函数，引入 松弛变量 （Slack Variables） $\xi_i \ge 0$，可以将 原问题 重写为

$$\begin{aligned} \min_{\pmb w, b, \pmb \xi} \quad & \frac{1}{2} \Vert {\pmb w} \Vert^2 + C \cdot \sum_{i=1}^m \xi_i \\ \mathrm{s.t.} \quad & y_i \left({\pmb w}^{\mathrm T} {\pmb{x_i}} + b \right) \geq 1 - \xi_i, \; \xi_i \ge 0 \end{aligned}$$

则其 对偶问题 为

$$\begin{aligned} \max_{\pmb \alpha} \quad & \sum_{i=1}^{m} \alpha_i - \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j y_i y_j {\pmb{x_i}}^{\mathrm T} {\pmb{x_j}} \\ \mathrm{s.t.} \quad & \sum_{i=1}^{m} \alpha_i y_i = 0, \, 0 \le \alpha_i \le C \end{aligned}$$

若采用对数损失函数，则模型很接近 Logit 回归。

结构风险与经验风险

更一般地，可以将优化目标写成

$$\min_{f} \quad \Omega(f) + C \sum_{i=1}^m \mathcal{L}(f(\pmb{x_i}), y_i)$$

其中，$\Omega(f)$ 代表 结构风险，如 $\frac{1}{2} \Vert {\pmb w} \Vert^2$，也被称为 正则化项，这里是 $\mathrm{L}_2$ 范数。
$\sum_{i=1}^m \mathcal{L}(f(\pmb{x_i}), y_i)$ 代表 经验风险，用于描述模型与数据的契合程度，如似然函数。

支持向量回归

支持向量回归（Support Vector Regression, SVR）是指，在回归中容忍 $f({\pmb x})$ 与 $y$ 存在 $\varepsilon$ 的偏差，当实际偏差大于 $\varepsilon$ 才开始计算损失。
支持向量回归问题可以写为

$$\min_{\pmb w, b} \quad \frac{1}{2} \Vert {\pmb w} \Vert^2 + C \cdot \sum_{i=1}^m \mathcal{L}_{\varepsilon} \left( f({\pmb{x_i}}) - y_i \right)$$

其中损失函数为

$$\mathcal{L}_{\varepsilon}(z) = \begin{cases} 0, \; & \mathrm{if} \; \vert z \vert \le \varepsilon \\ \vert z \vert - \varepsilon, \; & \mathrm{if} \; \vert z \vert > \varepsilon \end{cases}$$

• 如果损失函数是均方误差，则 SVR 等价于 Ridge 回归。
• 如果 $\varepsilon = 0$，即损失函数是误差的绝对值，则 SVR 等价于带有 $\mathrm{L}_2$ 范数的中位数回归。