【机器学习基础】第二十课:支持向量回归

支持向量回归(SVR)

Posted by x-jeff on April 27, 2021

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.支持向量回归

现在我们来考虑回归问题,给定训练样本$D={(\mathbf x_1,y_1),(\mathbf x_2,y_2),…,(\mathbf x_m,y_m) },y_i \in \mathbb R$,希望学得一个形如$f(\mathbf x)=\mathbf w^T \mathbf x + b$的回归模型,使得$f(\mathbf x)$与$y$尽可能接近,$\mathbf w$和$b$是待确定的模型参数。

对样本$(\mathbf x,y)$,传统回归模型通常直接基于模型输出$f(\mathbf x)$与真实输出$y$之间的差别来计算损失,当且仅当$f(\mathbf x)$与$y$完全相同时,损失才为零。与此不同,支持向量回归(Support Vector Regression,简称SVR)假设我们能容忍$f(\mathbf x)$与$y$之间最多有$\epsilon$的偏差,即仅当$f(\mathbf x)$与$y$之间的差别绝对值大于$\epsilon$时才计算损失。如下图所示,这相当于以$f(\mathbf x)$为中心,构建了一个宽度为$2 \epsilon$的间隔带,若训练样本落入此间隔带,则认为是被预测正确的:

于是,SVR问题可形式化为:

\[\min \limits_{\mathbf w,b} \frac{1}{2} \parallel \mathbf w \parallel ^2 + C \sum^m_{i=1} \ell_{\epsilon} (f(\mathbf x_i)-y_i) \tag{1}\]

其中$C$为正则化常数,$\ell_{\epsilon}$是下图所示的$\epsilon$-不敏感损失($\epsilon$-insensitive loss)函数:

\[\ell_{\epsilon} (z) = \left \{ \begin{array}{l} 0, \quad if \ \mid z\mid \leqslant \epsilon; \\ \mid z \mid - \epsilon, \quad otherwise \end{array} \right. \tag{2}\]

引入松弛变量$\xi _i$和$\hat \xi _i$,可将式(1)重写为:

\[\begin{align*} &\min \limits_{\mathbf w,b,\xi _i,\hat \xi _i} \frac{1}{2} \parallel \mathbf w \parallel ^2 + C \sum^m_{i=1} (\xi _i+\hat \xi _i) \\ & \begin{array}{l@{\quad}l@{}l@{\quad}l} s.t.& f(\mathbf x_i)-y_i \leqslant \epsilon+\xi_i, \\& y_i-f(\mathbf x_i) \leqslant \epsilon+\hat \xi_i, \\& \xi_i \geqslant 0 , \hat \xi_i \geqslant 0 , i=1,2,...,m. \\ \end{array} \end{align*} \tag{3}\]

间隔带两侧的松弛程度可有所不同。

通过引入拉格朗日乘子$\mu_i \geqslant 0, \hat \mu_i \geqslant 0,\alpha_i \geqslant 0 , \hat \alpha_i \geqslant 0$,由拉格朗日乘子法可得到式(3)的拉格朗日函数:

\[L(\mathbf w,b,\mathbf \alpha, \hat{\mathbf \alpha},\mathbf \xi, \hat{\mathbf \xi},\mathbf \mu , \hat{\mathbf \mu})=\frac{1}{2} \parallel \mathbf w \parallel ^2 + C \sum^m_{i=1}(\xi_i+\hat \xi_i)-\sum^m_{i=1} \mu_i \xi_i - \sum^m_{i=1} \hat \mu_i \hat \xi_i+ \sum^m_{i=1} \alpha_i (f(\mathbf x_i)-y_i-\epsilon - \xi_i)+\sum^m_{i=1}\hat \alpha_i (y_i-f(\mathbf x_i)-\epsilon-\hat \xi_i) \tag{4}\]

将$f(\mathbf x)=\mathbf w^T \mathbf x + b$代入,再令$L(\mathbf w,b,\mathbf \alpha, \hat{\mathbf \alpha},\mathbf \xi, \hat{\mathbf \xi},\mathbf \mu , \hat{\mathbf \mu})$对$\mathbf w,b,\xi_i,\hat \xi_i$的偏导为零可得:

\[\mathbf w=\sum^m_{i=1} (\hat \alpha_i - \alpha_i) \mathbf x_i \tag{5}\] \[0=\sum^m_{i=1} (\hat \alpha_i - \alpha_i) \tag{6}\] \[C=\alpha_i+\mu_i \tag{7}\] \[C=\hat \alpha_i + \hat \mu_i \tag{8}\]

将式(5)-(8)代入式(4),即可得到SVR的对偶问题:

\[\begin{align*} &\max \limits_{\mathbf \alpha,\hat{\alpha}} \sum^m_{i=1} y_i (\hat{\alpha_i} - \alpha_i) - \epsilon (\hat{\alpha_i} + \alpha_i) -\frac{1}{2} \sum^m_{i=1} \sum^m_{j=1} (\hat{\alpha_i} - \alpha_i)(\hat{\alpha_j} - \alpha_j) \mathbf x^T_i \mathbf x_j \\ & \begin{array}{l@{\quad}l@{}l@{\quad}l} s.t.& \sum^m_{i=1} (\hat{\alpha_i} - \alpha_i)=0, \\& 0\leqslant \alpha_i, \hat{\alpha_i} \leqslant C . \\ \end{array} \end{align*} \tag{9}\]

上述过程中需满足KKT条件,即要求:

\[\left\{ \begin{array}{c} \alpha_i (f(\mathbf x_i)-y_i-\epsilon - \xi_i)=0, \\ \hat \alpha_i (y_i-f(\mathbf x_i)-\epsilon-\hat \xi_i)=0, \\ \alpha_i \hat \alpha_i=0, \xi_i \hat \xi_i=0, \\ (C-\alpha_i)\xi_i = 0 , (C-\hat \alpha_i)\hat \xi_i = 0 .\end{array} \right. \tag{10}\]

将式(5)代入$f(\mathbf x)=\mathbf w^T \mathbf x + b$,则SVR的解形如:

\[f(\mathbf x)=\sum^m_{i=1}(\hat \alpha_i - \alpha_i) \mathbf x^T_i \mathbf x + b \tag{11}\]

能使式(11)中的$(\hat \alpha_i - \alpha_i) \neq 0$的样本即为SVR的支持向量,它们必落在$\epsilon$-间隔带之外。显然,SVR的支持向量仅是训练样本的一部分,即其解仍具有稀疏性。

落在$\epsilon$-间隔带中的样本都满足$\alpha_i=0$且$\hat \alpha_i=0$。

原因:因为样本是落在$\epsilon$-间隔带内,所以有$f(\mathbf x_i) -y_i < \epsilon$且$y_i-f(\mathbf x_i) < \epsilon$,又因为$\xi_i \geqslant 0 , \hat \xi_i \geqslant 0$。因此$f(\mathbf x_i)-y_i-\epsilon - \xi_i<0$且$y_i-f(\mathbf x_i)-\epsilon-\hat \xi_i<0$,根据式(10),此时必须有$\alpha_i=0$且$\hat \alpha_i=0$。

由KKT条件(10)可看出,对每个样本$(\mathbf x_i,y_i)$都有$(C-\alpha_i) \xi_i=0$且$\alpha_i (f(\mathbf x_i)-y_i-\epsilon - \xi_i)=0$。于是,在得到$\alpha_i$后,若$0<\alpha_i<C$,则必有$\xi_i=0$,进而有:

\[b=y_i + \epsilon - \sum^m_{i=1}(\hat \alpha_i - \alpha_i) \mathbf x^T_i \mathbf x \tag{12}\]

因此,在求解式(9)得到$\alpha_i$后,理论上来说,可任意选取满足$0<\alpha_i<C$的样本通过式(12)求得$b$。实践中常采用一种更鲁棒的办法:选取多个(或所有)满足条件$0<\alpha_i<C$的样本求解$b$后取平均值。

若考虑特征映射形式$f(\mathbf x)=\mathbf w ^T \phi (\mathbf x)+b$,则相应的,式(5)将形如:

\[\mathbf w=\sum^m_{i=1} (\hat \alpha_i - \alpha_i) \phi (\mathbf x_i) \tag{13}\]

将式(13)代入$f(\mathbf x)=\mathbf w ^T \phi (\mathbf x)+b$,则SVR可表示为:

\[f(\mathbf x)=\sum^m_{i=1}(\hat \alpha_i - \alpha_i) \kappa (\mathbf x,\mathbf x_i)+b \tag{14}\]

其中$\kappa (\mathbf x_i,\mathbf x_j)=\phi (\mathbf x_i)^T \phi (\mathbf x_j)$为核函数。

2.式(10)的推导

将式(3)的约束条件全部恒等变形为小于等于0的形式可得:

\[\left\{ \begin{array}{c} f(\mathbf x_i)-y_i-\epsilon - \xi_i \leqslant 0 \\ y_i-f(\mathbf x_i)-\epsilon-\hat \xi_i \leqslant 0 \\ -\xi_i \leqslant 0 \\ -\hat \xi_i \leqslant 0 \end{array} \right.\]

由于以上四个约束条件的拉格朗日乘子分别为$\alpha _i , \hat \alpha_i , \mu_i , \hat \mu_i$,可相应转化为以下KKT条件:

\[\left\{ \begin{array}{c} \alpha_i (f(\mathbf x_i)-y_i-\epsilon - \xi_i) = 0 \\ \hat \alpha_i (y_i-f(\mathbf x_i)-\epsilon-\hat \xi_i) = 0 \\ -\mu_i \xi_i = 0 \Rightarrow \mu_i \xi_i = 0 \\ -\hat \mu_i \hat \xi_i = 0 \Rightarrow \hat \mu_i \hat \xi_i = 0 \end{array} \right.\]

由式(7)、式(8)可知:

\[\mu_i = C-\alpha_i\] \[\hat \mu_i = C - \hat \alpha_i\]

所以上述KKT条件可以进一步变形为:

\[\left\{ \begin{array}{c} \alpha_i (f(\mathbf x_i)-y_i-\epsilon - \xi_i) = 0 \\ \hat \alpha_i (y_i-f(\mathbf x_i)-\epsilon-\hat \xi_i) = 0 \\ (C-\alpha_i) \xi_i = 0 \\ (C - \hat \alpha_i) \hat \xi_i = 0 \end{array} \right.\]

又因为样本$(\mathbf x_i,y_i)$只可能处在间隔带的某一侧,那么约束条件$f(\mathbf x_i)-y_i-\epsilon - \xi_i=0$和$y_i-f(\mathbf x_i)-\epsilon-\hat \xi_i=0$不可能同时成立,所以$\alpha_i$和$\hat \alpha_i$中至少有一个为0,也即$\alpha_i \hat \alpha_i=0$。在此基础上再进一步分析可知,如果$\alpha_i=0$的话,那么根据约束$(C-\alpha_i) \xi_i = 0$可知此时$\xi_i=0$;同理,如果$\hat \alpha_i=0$的话,那么根据约束$(C - \hat \alpha_i) \hat \xi_i = 0$可知此时$\hat \xi_i=0$。所以$\xi_i$和$\hat \xi_i$中也是至少有一个为0,也即$\xi_i \hat \xi_i=0$。将$\alpha_i \hat \alpha_i=0,\xi_i \hat \xi_i=0$整合进上述KKT条件中即可得到式(10)。

3.参考资料

  1. 南瓜书PumpkinBook