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 + \epsilon$ 和 $wx +b – \epsilon$ （也就是 $f(x) + \epsilon$ 和 $f(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^*)$
分别对 $w$ ， $b$ ， $\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 即可。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 217,826评论 6赞 506
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 92,968评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 164,234评论 0赞 354
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,562评论 1赞 293
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,611评论 6赞 392
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,482评论 1赞 302
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,271评论 3赞 418
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,166评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,608评论 1赞 314
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,814评论 3赞 336
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,926评论 1赞 348
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,644评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,249评论 3赞 329
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,866评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,991评论 1赞 269
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,063评论 3赞 370
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,871评论 2赞 354