[ML Notes] SVM：回归
在线性回归问题中，给定训练样本 $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})$ 为核函数。