16.gitchat训练营-SVR——一种“宽容”的回归模型

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

一种“宽容的”回归模型:支持向量回归(Support Vector Regression,SVR)

支持向量回归模型的模型函数也是一个线性函数:y=wx+b。看起来和线性回归的模型函数一样!但 SVR 和线性回归,却是两个不同的回归模型

这两个模型不同点学习过程,就是:计算损失的原则不同,目标函数和最优化算法也不同

1.1.原理

SVR 在线性函数两侧制造了一个“间隔带”,对于所有落入到间隔带内的样本,都不计算损失;只有间隔带之外的,才计入损失函数。之后再通过最小化间隔带的宽度与总损失来最优化模型。如下图这样,只有那些圈了红圈的样本(或在隔离带边缘之外,或落在隔离带边缘上),才被计入最后的损失:

image

1.2.SVR 的两个松弛变量

这样看起来,是不是 SVR 很像 SVM?不过请注意,有一点 SVR 和 SVM 正相反,那就是:SVR 巴不得所有的样本点都落在“隔离带”里面,而 SVM 则恰恰希望所有的样本点都在“隔离带”之外!正是这一点区别,导致 SVR 要同时引入两个而不是一个松弛变量。

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

SVR的基本情况

f(x) = wx +b是我们最终要求得的模型函数;wx + b + \epsilonwx +b – \epsilon(也就是f(x) + \epsilonf(x) - \epsilon)是隔离带的上下边缘;\xi是隔离带上边缘之上样本点的y值,与对应x坐标在“上边缘超平面”上投影的差;而\xi^*则是隔离带下边缘之下样本点,到隔离带下边缘上的投影,与该样本点y值的差。用公式来反应:

image

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

2.SVR 的主问题和对偶问题

2.1.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.

2.2.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^*)

2.3.求解 SVR 对偶问题

首先要求最小化部分:
min_{w,b,\xi,\xi^*}L(w,b,\xi,\xi^*, \alpha,\alpha^*, \mu,\mu^*)
分别对wb\xi\xi^*求偏导,并令偏导为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.

2.4.用 SMO 算法求解 SVR

SMO 算法针对的是任意样本x_i只对应一个参数\alpha_i的情况,而此处,这个样本却对应两个参数\alpha_i\alpha_i^*。有没有办法把\alpha_i\alpha_i^*转化为一个参数呢?办法还是有的!

我们整个求解过程采用的是拉格朗日对偶法,对偶问题有解的充要条件是满足** KKT 条件**。那么对于 SVR 的对偶问题,它的 KKT 条件是什么呢?它的 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,于是有 :|\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 算法还是有所差异的。

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

因为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则是位于隔离带下边缘的支持向量集合。

4.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 即可。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一、SVM模型 1. SVM功能体验   首先通过一个例子来了解SVM的作用;不用关注该例子的代码,直接观察图示效...
    杨强AT南京阅读 4,540评论 3 6
  • 以西瓜书为主线,以其他书籍作为参考进行补充,例如《统计学习方法》,《PRML》等 第一章 绪论 1.2 基本术语 ...
    danielAck阅读 10,155评论 0 5
  • 1. 回顾拉格朗日乘数法 为了找到曲线上的最低点,就从最低的等高线(0那条)开始网上数。数到第三条,等高线终于和曲...
    jiandanjinxin阅读 7,523评论 0 5
  • 一座山,两座山,无数座山, 万籁俱寂, 景色皆无, 掀翻攀缘的人,故技在白天, 阴森恐怖的笑,暴虐在黑夜。 飞流的...
    小人物眼里的世界阅读 1,176评论 0 2
  • 下午和朋友一起聊天,聊到了之前我们一起培训考试! 我:你发现一个现象没? 乐:啥现象? 我:就是在考试之前,大家在...
    王唯一的理想阅读 2,286评论 1 1