Gadzan

SVR支持向量回归

严格的线性回归

线性回归是在向量空间里用线性函数去拟合样本。

该模型以所有样本实际位置到该线性函数的综合距离为损失,通过最小化损失来求取线性函数的参数。参见下图:

对于线性回归而言,一个样本只要不是正好落在最终作为模型的线性函数上,就要被计算损失。

宽容的支持向量回归(SVR)

模型函数

==支持向量回归(Support Vector Regression,SVR)==模型的模型函数也是一个线性函数: y = wx + b。

看起来和线性回归的模型函数一样

SVR 和线性回归,却是两个不同的回归模型

不同在哪儿呢?不同在学习过程。

说得更详细点,就是:计算损失的原则不同,目标函数和最优化算法也不同

原理

SVR 在线性函数两侧制造了一个“间隔带”,对于所有落入到间隔带内的样本,都不计算损失;只有间隔带之外的,才计入损失函数。之后再通过最小化间隔带的宽度与总损失来最优化模型。

如下图这样,只有那些圈了红圈的样本(或在隔离带边缘之外,或落在隔离带边缘上),才被计入最后的损失:

SVR 的两个松弛变量

SVR 看起来很像 SVM

不过有一点 SVR 和 SVM 正相反,那就是:SVR 巴不得所有的样本点都落在“隔离带”里面,而 SVM 则恰恰希望所有的样本点都在“隔离带”之外。

正是这一点区别,导致 SVR 要同时引入两个而不是一个松弛变量。

SVR 引入两个松弛变量:$\xi$ 和 $\xi^* $

上图显示了 SVR 的基本情况:

$f(x) = wx +b$ 是我们最终要求得的模型函数;

$wx + b + \epsilon$ 和 $wx +b – \epsilon$(也就是 $f(x) + \epsilon$ 和 $f(x) - \epsilon$)是隔离带的上下边缘;

$\xi$ 是隔离带上边缘之上样本点的 $y$ 值,与对应 $x$ 坐标在“上边缘超平面”上投影的差;

而 $\xi^* $ 则是隔离带下边缘之下样本点,到隔离带下边缘上的投影,与该样本点 $y$ 值的差。

这样说有些绕,我们用公式来反应:

$ \begin{Bmatrix} \begin{array}{lr}
\xi_i=y_i-(f(x_i)+\epsilon),& if \ y_i>f(x_i)+\epsilon \\
\xi_i=0, & otherwise
\end{array} \end{Bmatrix}$

$\begin{Bmatrix} \begin{array}{lr}
\xi_i^{* }=(f(x_i)-\epsilon)-y_i,& if \ y_i>f(x_i)-\epsilon \\
\xi_i^{* }=0, & otherwise
\end{array}\end{Bmatrix}$

对于任意样本 $x_i$,如果它在隔离带里面或者隔离带边缘上,则 $\xi_i$ 和 $\xi_i^* $ 都为$0$; 如果它在隔离带上边缘上方,则 $\xi_i > 0,\xi_i^* =0$;如果它在下边缘下方,则 $\xi_i = 0,\xi_i^* > 0$。

SVR 的主问题和对偶问题

SVR 的主问题

SVR 主问题的数学描述如下:

$min_{w,b,\xi,\xi^* }\frac{1}{2}||w||^2 + C\sum_{i=1}^{m}(\xi_i +\xi_i^* )$

$ s.t. \ \ f(x_i) - y_i \leqslant \epsilon + \xi_i;\ \ y_i - f(x_i) \leqslant \epsilon + \xi_i^* ;\ \ \xi_i \geqslant 0; \ \ \xi_i^* \geqslant 0,\ \ i = 1,2, ..., m.$

SVR 的拉格朗日函数和对偶问题

我们引入拉格朗日乘子 $\mu_i \geqslant 0,\mu_i^* \geqslant 0, \alpha_i \geqslant 0$ 和 $\alpha_i^* \geqslant 0$,来针对上述主问题构建拉格朗日函数,得到拉格朗日函数如下:

$L(w,b,\xi,\xi^* , \alpha,\alpha^* , \mu,\mu^* ) = \frac{1}{2}||w||^2 + C\sum_{i=1}^{m}(\xi_i +\xi_i^* ) + \sum_{i=1}^{m}\alpha_i(f(x_i) - y_i -\epsilon - \xi_i) + \sum_{i=1}^{m}\alpha_i^* (y_i - f(x_i) -\epsilon - \xi_i^* ) + \sum_{i=1}^{m}\mu_i(0 - \xi_i) + \sum_{i=1}^{m}\mu_i^* (0 - \xi_i^* ) $

它对应的对偶问题是:

$max_{\alpha, \alpha^* , \mu, \mu^* }min_{w,b,\xi,\xi^* }L(w,b,\xi,\xi^* , \alpha,\alpha^* , \mu,\mu^* ) $

求解 SVR 对偶问题

首先要求最小化部分:

$min_{w,b,\xi,\xi^* }L(w,b,\xi,\xi^* , \alpha,\alpha^* , \mu,\mu^* ) $

分别对 $w,b,\xi_i 和 \xi_i^* $ 求偏导,并令偏导为0,可得:

$ w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)x_i, $

$ 0 = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i),$

$ C = \alpha_i + \mu_i ,$

$ C = \alpha_i^* + \mu_i .$

将上述4个等式带回到对偶问题中,在通过求负将极大化问题转化为极小化问题,得到如下结果:

$min_{\alpha,\alpha^* }[\sum_{i=1}^{m}y_i(\alpha_i - \alpha_i^* ) + \epsilon\sum_{i=1}^{m}(\alpha_i + \alpha_i^* ) + \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}(\alpha_i -\alpha_i^* )(\alpha_j -\alpha_j^* )x_i^Tx_j ]$

$s.t. \sum_{i=1}^{m}(\alpha_i^* - \alpha_i) = 0; \ \ 0 \leqslant \alpha_i, \alpha_i^* \leqslant C. $

用 SMO 算法求解 SVR

SMO 算法针对的是任意样本 $x_i$ 只对应一个参数 $\alpha_i$ 的情况,而此处,这个样本却对应两个参数 $\alpha_i 和 \alpha_i^* $。

可以把 $\alpha_i$ 和 $\alpha_i^* $ 转化为一个参数。

整个求解过程采用的是拉格朗日对偶法,对偶问题有解的充要条件是满足 KKT 条件。

对于 SVR 的对偶问题,它的 KKT 条件是:

$ \alpha_i(f(x_i) - y_i - \epsilon - \xi_i) = 0, $

$ \alpha_i^* (y_i - f(x_i) - \epsilon - \xi_i^* ) = 0, $

$ \alpha_i\alpha_i^* =0, $

$\xi_i\xi_i^* = 0, $

$(C - \alpha_i)\xi_i = 0, $

$ (C - \alpha_i^* )\xi_i^* = 0. $

由 KKT 条件可见,当且仅当 $f(x_i) - y_i - \epsilon - \xi_i = 0$ 时,$\alpha_i$ 才可以取非0值;当且仅当 $y_i - f(x_i) - \epsilon - \xi_i^* = 0$ 时,$\alpha_i^* $ 才可以取非0值。

$f(x_i) - y_i - \epsilon - \xi_i = 0 => y_i = f(x_i) - \epsilon - \xi_i$ 对应的是在隔离带下边缘以下的样本。

而 $y_i - f(x_i) - \epsilon - \xi_i^* = 0 => y_i = f(x_i) + \epsilon + \xi_i^* $ 对应的是在隔离带上边缘之上的样本。

一个样本不可能同时既在上边缘之上,又在上边缘之下,所以这两个等式最多只有一个成立,相应的 $\alpha_i$ 和 $\alpha_i^* $ 中至少有一个为0。

我们设:$\lambda_i = \alpha_i – \alpha_i^* $。

既然 $\alpha_i$ 和 $\alpha_i^* $ 中至少有一个为0,且 $0 \leqslant \alpha_i,\alpha_i^* ,\leqslant C $ (参见文章上节“求解 SVR 对偶问题”结尾),于是有 : $|\lambda_i| = \alpha_i + \alpha_i^* $。

将 $\lambda_i$ 和 $|\lambda_i|$ 带入对偶问题,则有:

$min_{\lambda}[\sum_{i=1}^{m}y_i(\lambda_i) + \epsilon( |\lambda_i|) + \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\lambda_i \lambda_j x_i^Tx_j ]$

$s.t. \sum_{i=1}^{m}(\lambda_i) = 0; \ \ -C \leqslant \lambda_i \leqslant C. $

接下来就可以用 SMO 求解了

当然,这样一个推导过程仅仅用于说明 SMO 也可以应用于 SVR,具体的求解过程和 SVM 的 SMO 算法还是有所差异的。

支持向量与求解线性模型参数

因为 $f(x) = wx + b$,又因为前面已经求出 $ w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)x_i $,因此:

$f(x) = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)x_i^Tx + b$

由此可见,只有满足 $\alpha_i^* - \alpha_i \ne 0$ 的样本才对 $w$ 取值有意义,才是 SVR 的支持向量。

也就是说,只有当样本满足下列两个条件之一时,它才是支持向量:

$f(x_i) - y_i - \epsilon - \xi_i = 0$

$ y_i - f(x_i) - \epsilon - \xi_i^* = 0$

换言之,这个样本要么在隔离带上边缘以上,要么在隔离带下边缘以下(含两个边缘本身)。

也就是说,落在 $\epsilon$-隔离带之外的样本,才是 SVR 的支持向量!

可见,无论是 SVM 还是 SVR,它们的解都仅限于支持向量,即只是全部训练样本的一部分。因此 SVM 和 SVR 的解都具有稀疏性。

通过最优化方法求解出了 $w$ 之后,我们还需要求 $b$。

$f(x_i) = wx_i + b => b = f(x_i) – wx_i $

而且,对于那些落在隔离带上边缘上的支持向量,有 $f(x_i)= y_i+\epsilon$,落在隔离带下边缘上的支持变量有 $f(x_i) = y_i -\epsilon$。

因此,$ b = \frac{1}{|S_u| + |S_d|}[\sum_{s\in S_u}(y_s + \epsilon - w x_s) + \sum_{s\in S_d}(y_s - \epsilon - w x_s)]$

其中 $S_u$ 是位于隔离带上边缘的支持向量集合,而 $S_d$ 则是位于隔离带下边缘的支持向量集合。

SVR 的核技巧

前面讲到的适用于 SVM 的核技巧也同样适用于 SVR。

SVR 核技巧的实施办法和 SVM 一样,也是将输入空间的 $x$ 通过映射函数 $\phi(x)$ 映射到更高维度的特征空间。然后再在特征空间内做本文前面所述的一系列操作。

因此,在特征空间中的线性模型为:

$f(x) = w\phi(x) + b$

其中:

$ w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)\phi(x_i) $

对照 SVM 核函数的做法,我们也令:

$k(x_i,x_j) = \phi(x_i)^T \phi(x_j)$

则:

$f(x) = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)k(x,x_i) + b$

具体核技巧的实施过程,也对照 SVM 即可。


知识共享许可协议 本作品采用知识共享署名 4.0 国际许可协议进行许可。

评论

评论加载中...