[ML Notes] SVM：回归

Author: nex3z 2020-09-04

  在线性回归问题中，给定训练样本 $D = \{(\boldsymbol x_1, y_1), (\boldsymbol x_2, y_2), \dots, (\boldsymbol x_m, y_m)\}$，$y_i \in \mathbb{R}$，我们希望找到一个模型

$$f(\boldsymbol x) = \boldsymbol w^\mathrm{T} \boldsymbol x + b \tag{1}$$

使得 $f(\boldsymbol x)$ 和 $y$ 尽可能接近，定义的损失为 $f(\boldsymbol x)$ 与 $y$ 之间的差异，当且仅当二者完全相同时，损失才为零。

  支持向量回归也希望找到形如式 $(1)$ 的模型，但能够容忍 $f(\boldsymbol x)$ 与 $y$ 之间存在最多 $\epsilon$ 的偏差，当且仅当二者之差的绝对值大于 $\epsilon$ 时才计算损失。相当于以 $f(\boldsymbol x)$ 为中心，构建了一个宽度为 $2\epsilon$ 的间隔带，若训练样本落入此间隔带，则认为预测是正确的。

  SVR 的问题可以写为

$$\min_{\boldsymbol w, b} \; \frac{1}{2} ||\boldsymbol w||^2 + C \sum_{i=1}^m l_{\epsilon}\big(f(\boldsymbol x_1) – y_i\big) \tag{2}$$

如果将 $\frac{1}{2} ||\boldsymbol w||^2$ 看成是正则化项，则 $C$ 可以看做是正则化系数；$l_{\epsilon}$ 称为 $\epsilon$-不敏感损失，定义为

$$l_{\epsilon}(z) = \begin{cases} 0, & \text{if } |z| \leq \epsilon \\ |z| – \epsilon, & \text{otherwise} \end{cases} \tag{3}$$

  引入松弛变量 $\xi_i$ 和 $\hat{\xi}_i$，式 $(2)$ 可以写为

$$\begin{aligned} \min_{\boldsymbol w, b, \xi_i, \hat{\xi}_i} \; & \frac{1}{2} ||\boldsymbol w||^2 + C \sum_{i=1}^m (\xi_i + \hat{\xi}_i) \\ \text{s.t.} \; & f(\boldsymbol x_i) – y_i \leq \epsilon + \xi_i \\ & y_i – f(\boldsymbol x_i) \leq \epsilon + \hat{\xi}_i \\ & \xi_i \geq 0, \hat{\xi}_i \geq 0, \;\; i = 1, 2, \dots, m \end{aligned}$$

  构造广义拉格朗日函数

$$\begin{aligned} &L(\boldsymbol w, b, \boldsymbol \xi, \hat{\boldsymbol\xi}, \boldsymbol \alpha, \hat{\boldsymbol\alpha}, \boldsymbol \mu, \hat{\boldsymbol\mu}) \\ &= \frac{1}{2} ||\boldsymbol w||^2 + C \sum_{i=1}^m (\xi_i + \hat{\xi}_i)\\ & \;\;\;\; – \sum_{i=1}^m \mu_i \xi_i – \sum_{i=1}^m \hat{\mu}_i \hat{\xi}_i \\ & \;\;\;\; + \sum_{i=1}^m \alpha_i \big(f(\boldsymbol x_i) – y_i – \epsilon – \xi_i\big) + \sum_{i=1}^m \hat{\alpha}_i \big(f(\boldsymbol x_i) – y_i – \epsilon – \hat{\xi}_i\big) \end{aligned} \tag{4}$$

  计算式 $(4)$ 对 $\boldsymbol w$、 $b$、 $\xi_i$、 $\hat{\xi}_i$ 的偏导，有

$$\begin{aligned} \nabla_{\boldsymbol w} L &= \boldsymbol w + \sum_{i=1}^m(\alpha_i – \hat \alpha_i) \nabla_{\boldsymbol w} f \\ &= \boldsymbol w + \sum_{i=1}^m(\alpha_i – \hat \alpha_i) \boldsymbol x_i \end{aligned}$$

$$\frac{\mathrm{d}L}{\mathrm{d}b} = \sum_{i=1}^m(\alpha_i – \hat \alpha_i) \frac{\mathrm{d}f}{\mathrm{d}b} = \sum_{i=1}^m(\alpha_i – \hat \alpha_i)$$

$$\frac{\mathrm{d}L}{\mathrm{d}\xi_i} = C – \mu_i – \alpha_i$$

$$\frac{\mathrm{d}L}{\mathrm{d}\hat{\xi}_i} = C – \hat\mu_i – \hat{\alpha}_i$$

令以上四个偏导为零，得到

$$\boldsymbol w = \sum_{i=1}^m(\hat \alpha_i – \alpha_i) \boldsymbol x_i \tag{5}$$

$$0 = \sum_{i=1}^m(\hat \alpha_i – \alpha_i)$$

$$C = \mu_i + \alpha_i$$

$$C = \hat\mu_i + \hat{\alpha}_i$$

将以上四式代入式 $(4)$，得到

$$\begin{aligned} L &= (\boldsymbol w, b, \boldsymbol \xi, \hat{\boldsymbol\xi}, \boldsymbol \alpha, \hat{\boldsymbol\alpha}, \boldsymbol \mu, \hat{\boldsymbol\mu}) \\ &= \frac{1}{2} \boldsymbol w^\mathrm{T} \sum_{i=1}^m(\hat{\alpha}_i – \alpha_i) \boldsymbol x_i + C \sum_{i=1}^m (\xi_i + \hat{\xi}_i) \\ & \;\;\;\; – \sum_{i=1}^m \mu_i \xi_i – \sum_{i=1}^m \hat\mu_i \hat{\xi}_i – \sum_{i=1}^m \alpha_i \xi_i – \sum_{i=1}^m \hat{\alpha}_i \hat{\xi}_i \\ & \;\;\;\; – \sum_{i=1}^m (\alpha_i – \hat{\alpha}_i) (y_i – \epsilon) + \sum_{i=1}^m (\alpha_i – \hat{\alpha}_i) f(\boldsymbol x_i) \\ &= \frac{1}{2} \sum_{i=1}^m(\hat \alpha_i – \alpha_i) \boldsymbol w^\mathrm{T} \boldsymbol x_i + C \sum_{i=1}^m (\xi_i + \hat{\xi}_i) \\ & \;\;\;\; – C \sum_{i=1}^m (\xi_i + \hat{\xi}_i) \\ & \;\;\;\; – \sum_{i=1}^m (\alpha_i – \hat{\alpha}_i) (y_i – \epsilon) – \sum_{i=1}^m (\hat{\alpha}_i – \alpha_i) \boldsymbol w^\mathrm{T} \boldsymbol x_i \\ &= \sum_{i=1}^m (\hat{\alpha}_i – \alpha_i) (y_i – \epsilon) – \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m (\hat{\alpha}_i – \alpha_i) (\hat{\alpha}_j – \alpha_j) \boldsymbol x_i^\mathrm{T} \boldsymbol x_j \end{aligned} \tag{6}$$

于是得到 SVR 的对偶问题

$$\begin{aligned} \max_{\boldsymbol\alpha, \hat{\boldsymbol\alpha}} \; & \sum_{i=1}^m (\hat{\alpha}_i – \alpha_i) (y_i – \epsilon) – \frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m (\hat{\alpha}_i – \alpha_i) (\hat{\alpha}_j – \alpha_j) \boldsymbol x_i^\mathrm{T} \boldsymbol x_j \\ \text{s.t.} \; & \sum_{i=1}^m(\hat{\alpha}_i – \alpha_i) = 0, \\ & 0 \leq \alpha_i, \hat{\alpha}_i \leq C. \end{aligned}$$

  上述过程的 KKT 条件为

$$\begin{aligned} \begin{cases} \alpha_i\big(f(\boldsymbol x_i) – y_i – \epsilon – \xi_i \big) = 0 & (i) \\ \alpha_i\big(y_i – f(\boldsymbol x_i) – \epsilon – \hat{\xi}_i \big) = 0 & (ii) \\ \alpha_i \hat{\alpha}_i = 0 & (iii) \\ \xi_i \hat{\xi}_i = 0 & (iv) \\ (C – \alpha_i) \xi_i = 0 & (v) \\ (C – \hat{\alpha}_i) \hat{\xi}_i = 0 & (vi) \end{cases} \end{aligned} \tag{7}$$

  由式 $(7)$ 中前两个条件，可知

• 当且仅当 $f(\boldsymbol x_i) – y_i – \epsilon – \xi_i = 0$ 时，$\alpha_i$ 能取非零值；
• 当且仅当 $y_i – f(\boldsymbol x_i) – \epsilon – \hat{\xi}_i$ 时，$\hat{\alpha}_i$ 能取非零值。

即仅当样本不落入 $\epsilon$-间隔带中，相应的 $\alpha_i$ 和 $\hat{\alpha}_i$ 才能取非零值。此外一个样本只能落入间隔带中的一侧，$f(\boldsymbol x_i) – y_i – \epsilon – \xi_i = 0$ 和 $y_i – f(\boldsymbol x_i) – \epsilon – \hat{\xi}_i$ 不能同时成立，因此 $\alpha_i$ 和 $\hat{\alpha}_i$ 中最少有一个为零。

  将式 $(5)$ 带入式 $(1)$，得到 SVR 的模型为

$$f(\boldsymbol x) = \sum_{i=1}^m (\hat{\alpha}_i – \alpha_i) \boldsymbol x_i^\mathrm{T} \boldsymbol x \tag{8}$$

能使上式中 $\hat{\alpha}_i – \alpha_i \neq 0$ 的样本即为支持向量，它们必落在 $\epsilon$-间隔带之外。支持向量只是训练样本的一部分，因此 SVR 仍具有稀疏性。

  求解得到 $\alpha_i$ 后，若 $0 < \alpha_i < C$，由式 $(7)$ 中条件 $(v)$，必有 $\xi_i = 0$，由条件 $(i)$ 可得

$$f(\boldsymbol x_i) – y_i – \epsilon = 0$$

将式 $(8)$ 带入上式，可以解得

$$b = y_i +\epsilon – \sum_{i=1}^m (\hat{\alpha}_i – \alpha_i) \boldsymbol x_i^\mathrm{T} \boldsymbol x \tag{9}$$

虽然通过上式只需一个满足 $0 < \alpha_i < C$ 的样本即可求得 $b$，实际中通常选择多个满足条件 $0 < \alpha_i < C$ 的样本求解 $b$ 后取平均值。

  如果引入特征映射，则式 $(5)$ 变为

$$\boldsymbol w = \sum_{i=1}^m (\hat{\alpha}_i – \alpha_i) \phi(\boldsymbol x)$$

模型为

$$f(\boldsymbol{x}) = \sum_{i=1}^m (\hat{\alpha}_i – \alpha_i) \mathcal{K}(\boldsymbol{x_i}, \boldsymbol{x_2}) + b$$

其中 $\mathcal{K}(\boldsymbol{x_i}, \boldsymbol{x_2})$ 为核函数。