Machine Learning Techniques Lecture 5: Kernel Logistic Regression | Cheney Shen

Technology blog

Machine Learning Techniques Lecture 5: Kernel Logistic Regression


 
 

内容:kernel logistic regression

一开始先把soft-margin SVM解释成一个和logistic regression有关的模型,他所在做的就是L2 regularization,对应到一个特别的hinge error measure。然后把SVM和logistic regression连上关系,SVM几乎就是L2-regularized logistic regression。如果是这样的话,有一个SVM的解,可以透过第二个阶段的训练的方式把它变成一个适用于soft binary classification的。如果硬要在z空间里面真的求解一个logistic regression的问题,也可以透过representer theorem做到,付出的代价是求解用的beta很多都不是0,计算量很大。

 
 

 
 


 
 

上一讲:

如果我们容许SVM对于已有的资料分类犯错误的话,就从原来的hard-margin改成了soft-margin。我们用C来代表容许错误的参数,这样经过推到以后你会发现dual SVM问题下soft-margin带来的是alpha_n有一个上限就是C。

 
 

今天从soft-margin继续延伸,如果我们要把kernel的技巧用在logistic regression这个问题上,怎么去处理。

 
 


 
 

回顾以前的对比:

  1. Hard-margin Primal:找到能完全分开的最胖的分隔线;

    Hard-margin Dual:对应primal的对偶问题,使得求解的过程与z空间的维度没有关系。

  2. Soft-margin Primal:允许存在已知的数据点没有分对的最胖的分隔线;

    Soft-margin Dual:对应primal的对偶问题,同hard的处理方式,唯一的区别是alpha存在上限C。

 
 

Soft-margin 才是真的大家常用的SVM。

推荐两个特别好用的SVM工具:LIBLINEAR, LIBSVM

 
 


 
 

再来看看Soft-margin里面做了什么事情:

我们把违反胖胖的边界的部分记录下来存储在kesi_n,然后把SVM的有条件问题写出来,再转化成对偶问题求解。

 
 

从另外一个角度来看我们在求解这个问题的时候到底在做什么事情:

给定任何一条分割边界b,w,那么对于任何一个点来说有两种情形,第一种是如果这个点违反了胖胖的边界,则kesi_n记录的就是违反的位置到胖胖的边界的边界的距离。第二种是如果这个点没有违反胖胖的边界,则kesi_n的值就是0.

所以综合上面两种情况,kesi_n 就可以表示成 max(…, 0) 这个公式。有了这个kesi_n的表示公示,则SVM可以写成一个新的公式如上面的PPT所示,也就意味着我们在最佳化里面不再有kesi_n这个变量了。

 
 


 
 

有了上面的那个式子特点是:我们要最小化的是两项加起来,其中一项是和w的长度有关,另外一项就是拿b,w的值来算一些结果。

再来看我们以前在做regularization的时候,我们有一个替代的error要做最小化的动作,但是我们加上了一个w的长度来作为regularization,两者公式在形式上面一致。

 
 

既然形式是一致的,那么为什么不从regularization开始介绍SVM呢?

原因1:这不是一个QP问题,不能用上dual,kernel的技巧求解;

原因2:两个值之间取最大值的函数,可能存在不能微分的点,直接拿来最佳化很难。

 
 


 
 

SVM 和 regularization 的关系:

 
 

Regularization:想要E_in变小,但是存在 w^T * W <= C 的条件;

Hard-margin SVM:想要 W^T * W 最小,但是存在 E_in = 0 的条件,正好相反。

 
 

L2 regularization:把 regularization 的条件丢到目标函数里面去;

Soft-margin SVM:把 hard-margin SVM的条件丢到目标函数里面去。

 
 

所以:

 
 

Large margin 就是 regularization 的实现,代表了我们可以找到的 pyherplane 能比较少,就和L2 regularization 很接近。

Soft margin 对应到特别的计算err的方式。

蓝色的C,红色的C,不管是哪个,比较大的话对应的就是比较小的 lamda,也就代表了越少的 regularization。

 
 

这里对比的意义是:思考可不可以把SVM延伸到其他问题上,比如regression的问题。

 
 


 
 

练习

 
 


 
 

上面我们已经把 soft-margin SVM 写成了新的形式。

 
 

我们首先来看看里面的max函数的两个项和我们一般在二元分类里面所在意的Err_0/1有什么关系:

我们想办法把err对于不同的 y * 分数 画出来。如果两者同号,那么01误差就是0;如果两者是异号的,那么01误差就是1,有图就是图解(横轴是y*分数,err_0/1是纵轴)。

 
 


 
 

如果是 err_svm 怎么来画:

也是两个部分,第一个部分是 y * 分数 比 1 还来得小的时候,则结果是max的前面那一个项,图中前面线性的部分,就是记录要扣几分;否则,就是不扣分,就是0。(图解紫色的折线)

 
 

Err_SVM是E_0/1的上限,因此可以由这个上限推导出一些演算法来间接的把 Err_0/1 做好。soft-margin SVM就可以看作是在做这件事情。

 
 


 
 

我们在logistic regression的时候就讲过了这个上限的概念,我们来看看logistic regression到底在做什么事情,如果把logistic regression印出来的话就是橙色的那条线,同样他也是盖在Err_0/1的上面。

 
 

我们来看 SVM 和 logistic regression 的err,两者是比较像的,当ys像两个极端逼近的时候,两者的结果也是相似的。

 
 

因此可以想象说 SVM 其实也很像是在做 L2 regularization。

 
 


 
 

因此可以来做 binary classification 的 linear model 有:

  1. PLA:最小化Err_0/1,只有在线性可分的时候很好求解。
  2. Soft-margin SVM:通过QP来获得Err_SVM,同样求解很容易,存在模型复杂度保护,但是最佳化的结果只是Err_0/1的上限。
  3. Regularized logistic regression for classification:通过GD/SGD来获得Err_SCE,函数很平滑,最佳化比较容易,有一些些模型复杂度的保护,但是最佳化的结果只是Err_0/1的上限。

 
 

至此,我们可以认为 regularized logistic regression 几乎就是再做 SVM,反之也是。

 
 


 
 

练习

 
 


 
 

因此我们来看看怎么把 SVM 用在 Soft binary classification。

 
 

想法一:

既然两者那么像,那么通过求解SVM得到b,w,然后直接把b,w当作是logistic regression的近似解,也就是直接如上面那样构建g当作是 soft binary classification。这里直接使用了两者的相似性,使用上通常表现得还不错,但是这里丧失了logistic regression的特性。

 
 

想法二:

如果想要logistic regression的特性的话,势必要做一些原来做的一些maximun likelihood这样的learning的动作,做法是首先从SVM里面得到一个解b,w,然后把这个解当作是logistic regression的起始点,然后再使用GD/SGD这样的去学的话应该可以得到一个不错的结果。这样做和你直接跑个logistic regression的结果应该差不多,几乎没有SVM的特性在。

 
 

这两个方法都存在问题,我们有没有办法去融合来做出一个不一样的方式。

 
 


 
 

我们考虑的一个不一样的模型:

首先做SVM出来的结果实际上是一个分数,然后我们在这个分数上面加上两个自由度,一个是放缩(A),一个是平移(B),在这两个参数上做logistic regression的训练,让他可以比较吻合我们在logistic regression里面所需要的manimum likelihood的需求。

这样一来,我们骨子里面使用的是SVM,因此SVM里面讲的dual/kernel等都可以用上,然后再在logistic regression层面操作,它的特性也都统统可以用。

在几何上的意义是用SVM找出分隔线得法向量,然后法向量就不会变化了,但是我们能在法向量基础之上,加上一下放缩和平移来更吻合maximum likelihood的需求。

完美融合,通常情况下,如果SVM求解合理,A一般是要>0的,B很接近0。

 
 

这样我们就得到了新的 logistic regression 的问题,红色框框所示。

这里可以看作是两步,第一步SVM把所有的高维度x转化为单一维度的分数,然后第二步就是对单一维度分数求解logistic regression。

 
 


 
 

这是SVM常用的一个方法,最开始是由 Platt 提出来的,步骤是:

  1. 跑SVM,把结果当作转换,转换到某一个很特别的单维度的z空间,用SVM的分数来当作转换。
  2. 跑Logistic regression微调。两个变数的求解很简单。
  3. 把结果传回去。

 
 

做完你就可以得到 soft binary classifier,这个结果和原来的SVM结果略微有差别,在于A(缩放),B(平移)。

 
 

到此讲的是我们如何从 kernel SVM 到 logistic regression 在 Z 空间里面的估计结果。做法不是真的在z空间求解 logistic regression,而是通过SVM来解z空间的结果,再用logistic regression微调。

但是这不是在Z空间里面最好的logistic regression的结果。

那么怎么去找真的z空间最好的解?

 
 


 
 

练习

 
 


 
 

我们想要的是z空间里面真的最好的logistic regression的解,怎么做?

 
 

当我们存在z的内积的时候,就可以使用kernel来求解。而最开始的w是一堆z的线性组合,才是推倒后可以使用kernel的关键。

 
 

最大的w是一堆z的线性组合:

  1. SVM:系数就是对偶问题的解
  2. PLA:系数就是每个z到底参与了多少次次数修正的过程
  3. LogReg by SGD:系数就是gradient告诉我们跨步多大

这些都能表示成一堆z的线性组合,也就可以猜测这些方法都能使用kernel方式来求解。

 
 

那么什么时候最好的w可以透过这些z表达出来呢?

 
 


 
 

数学上的答案:如果你今天解的是L2 regularized 的linear model问题,也就是 W^T * W 在你的模型里面,那么一定有一个最好的W,可以表示成这些Z原始资料的线性组合。

 
 

证明:

如果有一个最佳解W_*,拆成两个部分,一部分可以用z表示(W平行),一部分不可以(W垂直)。所以当W垂直=0的时候,就是证明的上述公式。

如果W垂直!=0,首先来看看W平行

第一点讲的是垂直的部分相乘z一定是0,所以原来式子第二项err部分 W_* 和 W平行 结果应该一样。

原来式子中第一部分式子分解的情况,这里的大于号会导致:原来说的是找到的已经是最佳解,现在有出现了比最佳解还要好的解,这就矛盾了。

所以 w_* 式最佳解,则w垂直就是0。

 
 

所以结论是只要你解决L2 regularized 线性问题,就可以把kernel套上去。

 
 


 
 

我们来看怎么把这个式子kernel化:

因为 W_* 一定是 Z 的线性组合,因此我们要求解的就是最佳的线性组合的系数 beta_n。把结论代入原来的式子,然后两个z内积相乘就可以轻易的换成kernel来计算。剩下就是求解beta就好了,这时候是一个没有条件的最佳化问题,求解方法很多种多样。

 
 

这通常叫做: kernel logistic regression

 
 


 
 

我们怎么去理解这个公式在做什么?

后面这一项,把一堆kernel和beta做内积,也就是把原来的x转化成了k,在这基础上使用beta(权重)得结果。

前面这一项,beta^T * kernel matrix * beta 的形式,可以看作是 beta^T * beta 的结果再做一些放缩转换的动作。

所以 kernel logistic regression 可以看作是 beta 的 linear model 作用在用kernel 转换过的资料,kernel还用在regularizer。(原来看作是w的线性模型作用在w的藏起来的转换和L2 regularizer)

 
 

这些解释都可以套用在SVM上面。

 
 

警告:这里和原来求解SVM的alpha不一样,beta大部分都不是0。

 
 


 
 

练习

 
 


 
 

总结:kernel logistic regression

一开始先把soft-margin SVM解释成一个和logistic regression有关的模型,他所在做的就是L2 regularization,对应到一个特别的hinge error measure。然后把SVM和logistic regression连上关系,SVM几乎就是L2-regularized logistic regression。如果是这样的话,有一个SVM的解,可以透过第二个阶段的训练的方式把它变成一个适用于soft binary classification的。如果硬要在z空间里面真的求解一个logistic regression的问题,也可以透过representer theorem做到,付出的代价是求解用的beta很多都不是0,计算量很大。

 
 

下一讲:

Kernel for 一般的 regression 的问题

 
 


5 Comments

  • wonderful submit, very informative. I’m wondering why the other experts of this sector do not understand this. You must proceed your writing. I am confident, you have a great readers’ base already!

  • Hi there! I could have sworn I’ve been to your blog before but after going through a few of the articles I realized it’s new to me. Anyways, I’m certainly delighted I stumbled upon it and I’ll be bookmarking it and checking back frequently!

  • I am no longer certain where you’re getting your information, but great topic. I must spend some time studying more or understanding more. Thanks for fantastic information I used to be looking for this info for my mission.

  • I blog frequently and I truly appreciate your content. This great article has really peaked my interest. I’m going to take a note of your site and keep checking for new details about once a week. I opted in for your RSS feed too.

Post a Comment

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

  • Categories

  • Tags