Machine Learning Techniques Lecture 6: Support Vector Regression | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 6: Support Vector Regression


 
 

内容:

和大家讲了support vector regression,一开始的切入点就是把我们原来会的ridge regression变成kernel的形式,我们可以通过representer theorem来做到这件事情。不过呢这时候的beta是dence的,计算量太大,因此我们从一个 regularized tube error来做推导导出了对偶问题,根据KKT条件求解二次规划,得到sparse的beta的结果。

最后总结了一下kernel model以及使用情况,这里要特别提醒的是这里提供了无限强大的工具,但是你要仔细的去对症使用。

 
 


 
 

上一次:kernel logistic regression

如果我们想要把SVM这样的方法用在soft classification上面的话,我们可以用two-level learning的方式,先做SVM,然后再把SVM做出来的东西丢去logistic regression里面微调一下得到结果;或者是我们可以使用representer theorem直接把logistic regression变到一个kernel的形式来求解。

 
 

Support vector regression

我们从上面这个新的技巧出发,来探讨怎么把regression变成kernel的形式。

 
 


 
 

上一次讲到:representer theorem

什么时候我们的W可以变成一堆z的线性组合呢?如果你要处理的是一个有L2-regularize的linear model,那么你要处理的W=可以变成一堆Z的线性组合,也就是可以把它变成kernel的形式。

 
 

我们今天要探讨的就是怎么把regression变成kernel的形式。

regression的做法采用的是让squared error最小来达到结果。我们来看怎么在此加入kernel的概念。Ridge regression 表示的就是使用上面的错误公式计算的linear regression。

 
 


 
 

如果我们今天要做的是 Kernel Ridge Regression 的话,我们要求解的是上面黄色底框的问题。我们最后的最佳解能表示成z的线性组合。因此如上面的图示,我们可以把存在beta的公式代入原来的式子,就可以得到求解beta的式子(蓝色底框),kernel也就出现了。这也就可以看作是beta的线性模型,前面部分和beta的复杂度相关,后面的是beta通过kernel转换过的资料和。然后再考虑矩阵表达形式,就可以得到蓝色框内最后一行的结果。

 
 

这样就是把ridge regression变到了kernel的世界里了。剩下的问题是我们要怎么样去求解出最好的beta。

 
 


 
 

黄色框所示的式子就是上面一部得到的,最后ridge regression表示成了beta的函数的结果。这是一个beta的二次式,这是一个无条件的最佳化问题,算梯度=0(蓝色部分是为了后面讨论方便加入的不影响结果的变化的项),再整理一下得到最终结果。

 
 

然后我们想要的是梯度为0,其中一个是beta的系数是0,就是一个最佳解而且一定存在(lamda一定是大于0的,合法的K一定是半正定的)。这样你就可以求出最好的beta是什么,然后就有了最好的kernel ridge regression结果,但是直接求解的话,kernel矩阵大部分都不是0,复杂度是O(N的三次方)。

 
 

所以理论上我们现在可以很轻易的做non-linear regression。

 
 


 
 

比较,同一个资料做不同的学习。

左边是linear ridge regression:求解的是线性的分类结果,如要做的反矩阵是d*d大小。能力有限只能是线性,计算效率搞高。

右边是kernel ridge regression:求解的是kernel代表的分类结果,可以使非线性的,如果做的话反矩阵是N*N的大小。自由度高,计算效率低(复杂度和计算的资料的量有关)。

 
 

这里再次说到了 linear 和 kernel 的差别,效率和计算量之间的权衡。

 
 


 
 

练习

 
 


 
 

我们现在有了 kernel ridge regression,也可以拿来做classification,这时候叫做 least-squares SVM(LSSVM)。Least-sequares 描述的是这里使用的是regression的error来做classification。

 
 

我们来看拿同样的资料跑

Soft-margin gaussian SVM:只有少部分是support vector,好的性质是alpha是sparse的。

Gaussian LSSVM:每一个点都是support vector,这意味着未来做prediction的时候花费也会很高,也就是g会很肥大。这里的数学原因是求出来的beta大部分都不是0.(实际上 kernel logistic regression 求出来的也是dense的beta,也存在这个问题,train和prediction的时候花费代价都很大。)

从边界看差别不是很大。

 
 

那我们来考虑:有没有办法做出sparse beta的kernel ridge regression?

 
 


 
 

我们考虑一个很特别的问题叫做: Tube Regression

以前我们做regression的时候就是比较我们的数据和线的边界差多远,越远扣分越多。现在我们容许存在一个中立区,中立区里面的数据不扣分,中立区外面的数据才扣分。上面公式epson就是中立区的半边长,错误公式就是灰色框表示的部分,这个error叫做 espon-insensitive error。

 
 

然后,接下来做的就是把这个tube regression透过上一小结的方式来做推导求结果。

 
 


 
 

比较一下

Tube regression:蓝色里面不扣分,外面的才扣分,扣得是长度。

Squared regression:都要算扣分,扣得是长度的平方。

如果把两者的错误画出来的话,蓝色线表示的是tube,红色线表示的是squared,在比较中间的区域两者是约等于的,往外面走的时候区别就很大了,tube成长比较平缓。tube的最大好处是能够得到sparse beta solution。

 
 


 
 

然后我们来看怎么求解 L2-regularized tube regression。

 
 

如果直接去求解的话,因为是一个regularized formulation,所以理论上用任何unconstrained的方法去求解w。但是可能存在不可以微分的地方,你需要额外的考虑,比较复杂。如果要用上kernel的话,使用represerter是没有问题,但是做完之后你不能知道会不会得到你想要的sparse的beta。

 
 

那我们来看原来的SVM的求解,如果直接求解一样遇到上面的问题,但是我们把它转化成一个QP问题求解比较容易。这里是通过KKT条件的求解得到的sparse结果。

 
 

所以,我们来模仿标准的SVM求解来得到sparse的beta。所以我们来把原来的式子写成和标准SVM接近的式子,如上面底下的黄色框所示。

 
 


 
 

有了式子,怎么去化简求解呢?

 
 

原来SVM里面拆max是通过引进变数kesi_n,这里也是,然后加入到最佳化的条件里面去。然后再拆掉绝对值,变成两个部分,又多了两个条件。这样我们就得到了一个二次规划的问题,且条件是线性的。

 
 

这就是标准的 Support Vector Regression(SVR)的primal问题:两个条件下最小化regularizer。

 
 


 
 

我们从图来看这个问题:

在tube之外的部分就需要算kesi的结果,边界里面的就不需要。要求解的最佳化就是把红线的错误都加起来,以及reguarizer那一项,这样子去找出一条最好的线作为结果。

 
 

参数C:控制的是在乎regularization多一点还是tube violation。

参数epson:你的tube的宽度是两倍的epson。

二次规划问题:d+1+2N个变数,4N个条件。

 
 

然后考虑怎么把对空间维度的依赖d去掉,和之前的做法一样,转化成对偶问题,然后通过kernel trick求解,见下一节。

 
 


 
 

练习

 
 


 
 

转对偶问题:

 
 

首先需要的是 lagrange multipliers,然后写下 lagrange function,然后对里面的变数做微分,然后得到KKT condition(灰色框所示),然后替换掉得到一个新的问题。具体见第二/四课的内容。

 
 


 
 

比较来看其实对偶问题的长相是有迹可循的。

 
 

SVM Dual:绿色的部分跑到了二次项系数,蓝色的跑到了一次项系数,紫色的变成了sum条件,红色的是式子和条件的结合。

SVR Dual:同上,绿色的变成了二次项的系数,蓝色的跑到了一次项系数,紫色的变成了sum条件,红色的是式子和条件的结合。

 
 

相似的二次规划求解,相似的求解结果。

 
 


 
 

SVR的结果:beta是sparse的!!!

 
 


 
 

练习

 
 


 
 

回顾一下上过的Kernel模型

 
 

在机器学习基石里面上过的线性模型:

  1. PLA/Pocket:使用的是0/1错误
  2. Linear ridge regression:使用的是平方和错误
  3. Regularized logistic regression:使用的是GD/SGD来描述错误

 
 

在这课程里又给大家介绍了另外的几种:

  1. Linear soft-margin SVM

也是用来解决线性的分类问题,使用的错误是到分隔线的距离平方和,通过二次规划求解。

  1. Linear SVR

求解linear regression问题的一种方法,最佳化的是Err_tube,求解的是二次规划。

 
 

第二排的三种方法,就是LIBLINEAR这个工具的核心方法。

 
 


 
 

再来看看Kernel,上面讲到的这些linear的东西,只要使用regularize,你都可以把他延伸到kernel求解。

 
 

  1. Linear soft-margin SVM 延伸到 SVM

求解的是对偶问题

  1. Linear SVR 延伸到 SVR

求解的是对偶问题

  1. Linear rigid regression 延伸到 kernel rigid regression

就是上节课讲到的怎么变成kernel形式的方法

  1. Regularized logistic regression 延伸到 kernel logistic regression

做法同上面一个

  1. Kernel logistic regression 进一步可以延伸到 probilistic SVM

我们在SVM的世界里面不是很爱用kernel logistic regression,因为beta不是sparse的,因此再次处理让beta sparse就是这个

 
 

看第四行的方法就包含在 LIBSVM 这个工具里面

 
 


 
 

再来看一下这些模型的实用度:

 
 

第一排的是很少被使用的,因为分类表现相对于其他没有那么好。

第三排也是很少有人用,因为dense的beta,计算的时候数据量非常大。

 
 


 
 

这前面的6讲都是围绕着这些 kernel models,然后你可以任意配合上我们所讲过的polynormial, gaussian, 等等符合 mercer’s condition 的kernel形式来做使用。这是linear model的非常power的延伸,但是要小心使用,避免overfit。

 
 


 
 

练习

 
 


 
 

总结:

和大家讲了support vector regression,一开始的切入点就是把我们原来会的ridge regression变成kernel的形式,我们可以通过representer theorem来做到这件事情。不过呢这时候的beta是dence的,计算量太大,因此我们从一个 regularized tube error来做推导导出了对偶问题,根据KKT条件求解二次规划,得到sparse的beta的结果。

最后总结了一下kernel model以及使用情况,这里要特别提醒的是这里提供了无限强大的工具,但是你要仔细的去对症使用。

 
 

下一讲:

至此讲完了embedding numerous features:你有很多很多features的时候你可以用kernel的技巧来做学习。下面我们开始讲如果我们有很多的机器学习的方法的时候,我能不能融合各种方法的好坏处,调出一个最佳解。

 
 

 
 

 
 

 
 

 
 

 
 


Post a Comment

Your email address will not be published. Required fields are marked *

  • Categories

  • Tags