林轩田机器学习技法第五讲-Kernel Logistic Regression

上一讲学习了Soft-Margin Support Vector Machine，至此基本的支持向量机就介绍完了。那么其中涉及的思想能否和其他的算法结合起来呢？这讲就看一下如何将核技巧和之前学习的Logistic Regression结合起来

首先回顾一下之前学习的几种支持向量机如下所示，具体的内容可见前面几讲，具体不再赘述

具体再来看一下Soft-Margin SVM的内容，我们用ξn来表示允许分错的程度，在图像中表示为距离直线的距离，ξn=0表示没有犯错，ξn>0表示有错。在得到如下所示的表达式后，使用二次规划进行求解

那么对于任意一点(xn,yn)来说，ξn描述了(xn,yn)距离直线yn(wTzn+b)=1有多远。如果没有错误ξn=0；如果分错了ξn = 1-yn(wTzn+b)。因为只有这两种情况，所以将其整合到一起后即如下黄色框所示。

那么对应的Soft-Margin SVM的最小化问题就如下所示，这样就消去了ξn，只与w和b相关

上面的表达式中其中包含两项，第一项是w的内积，第二项关于y和w，b，z的表达式，好像和之前见过的err的形式很像，比如子L2正则化中的最小化目标表达式，只是W的维度不同，某些参数不同。这样的话就给了我们一个猜想：能否使用L2正则化的方法求解上面的问题呢？答案是不行，原因主要有两个：一是这种无条件的最优化问题无法通过QP解决，即对偶推导和kernel都无法使用；另一个是这种形式中包含的max()项可能造成函数并不是处处可导，这种情况难以用微分方法解决

下面讲几种形式相似的问题做一个对比，主要是它们的最小化目标和限制条件，如下所示。其中L2 正则化和Soft-Margin SVM的形式是相同的，两个式子分别包含了参数λ和C。Soft-Margin SVM中的large margin对应着L2 正则化中的short w，也就是都让hyperplanes更简单一些。所以使用特别的err_hat来代表可以容忍犯错误的程度，即soft margin。L2 正则化中的和Soft-Margin SVM中的C也是相互对应的， λ越大，w会越小，正则化的程度就越大；C越小， Ein会越大，相应的margin就越大。所以说增大C，或者减小，效果是一致的，LargeMargin等同于正则化，都起到了防止过拟合的作用

经过上面的转换，Soft-Margin的表达式已经变成了这样，类比于前面的0/1err，将第二项设置为err_hat。Err0/1图像如下图的黑色的线所示，当ys<0时，err=1，否则err=0；而errsvm的图像如下图紫色的线所示，他始终位于err0/1的上面，可以将其做为err0/1的上界，故可以使用errsvm来替代err0/1，解决二元分类问题，并且它是一个凸函数，很方便使用现有的方法求解。

而在Logistic Regression中的错误衡量中，它的表达式如下黄色的曲线所示，当ys=0时err=1。显然errsce也是err0/1的上界，而errsce与errsvm也是比较相近的。因为当ys趋向正无穷大的时候， errsce和errsvm都趋向于零；当ys趋向负无穷大的时候，errsce和errsvm都趋向于正无穷大。

正因为二者的这种相似性，我们可以把SVM看成是L2-regularized logistic regression

总结一下前面学过的可以用于分类的算法PLA、Soft-Margin SVM和新学的L2-regularized logistic regression。
至此可以看出，求解regularized logistic regression的问题等同于求解soft-margin SVM的问题。反过来，如果我们求解了一个soft-margin SVM的问题，那这个解能否直接为regularized logistic regression所用？来预测结果是正类的几率是多少？

基于上面的猜想，我们可能会想到以下的两种做法：一种是运行SVM算法得到相应的bsvm和wsvm，然后将其带入到Logistic Regression的g中直接使用，这样做简单易行，但是简单的代入，并没有使用到Logistic Regression本身的一些性质；另一种是同样先得到bsvm和wsvm，将其作为Logistic Regression的参数的初始化值，再运行它本身的算法的到最后的g，但这样做参数的初始化感觉并没有什么实质上的作用。

下面构造一个结合了两个算法优势的模型，g的表达式如下所示，A和B是代表放缩和平移。首先利用SVM的参数解bsvm和Wsvm的解来构造这个模型，放缩因子A和平移因子B是待定系数。然后再用通用的logistic regression优化算法，通过迭代优化，得到最终的A和B。一般来说，如果bsvm和Wsvm较为合理的话，满足A>0且B≈0

则新的logReg的表达式如下所示，bsvm和Wsvm是已经求出的，只需要解A和B即可。

总结一下这种做法，主要分为以下三个步骤：
• 运行SVM得到bsvm和Wsvm，做特征转换到新的域中得到Z’n
• 使用新的（z’n,yn）运行Logistic Regression算法得到A和B
• 代入到g的表达式中，得到最后的分类边界

如果我们希望直接在z空间中直接求解logistic regression，通过引入kernel，来解决最优化问题，又该怎么做呢？SVM中使用kernel，转化为QP问题，进行求解，但是logistic regression却不是个QP问题，看似好像没有办法利用kernel来解决.

如果w可以表示为z的线性组合，即下图黄框的形式，那么乘积项蓝框的形式，即其中包含了z的内积。也就是w可
以表示为z的线性组合是kernel trick可以work的关键。

我们之前介绍过SVM、PLA包括logistic regression都可以表示成z的线性组合，这也提供了一种可能：将kernel应用到这些问题中去，简化z空间的计算难度

对于L2regularized linear model，如果它的最小化问题形式为如下的话，那么最优解就是如下的W*

具体的证明如下所示

经过证明和分析，我们得到了结论是任何L2-regularized linear model都可以使用kernel来解决。现在，我们来看看如何把kernel应用在L2-regularizedlogistic regression上。上面我们已经证明了w一定可以写成z的线性组合形式，。那么我们就无需一定求出w，而只要求出其中的βn就行了。直接将W* 的表达式代入到L2-regularizedlogistic regression最小化问题中，得到：


上式中，所有的w项都换成βn来表示了，变成了没有条件限制的最优化问题。我们把这种问题称为kernel logistic regression，即引入kernel，将求w的问题转换为求βn的问题。

从另外一个角度来看Kernel Logistic Regression（KLR）：式中log的项可以看成是变量β和K(xm,xn)的内积(红框所示)。第二式中的项可以看成是β关于的正则化项βTKβ。所以KLR是β的线性组合，其中包含了kernel内积项和kernel regularizer。这与SVM是相似的形式。

但KLR中的βn与SVM中的αn是有区别的。SVM中的大部分为零，SV的αn个数通常是比较少的；而KLR中的βn通常都是非零值

最后做个总结，这一讲主要学习了如何将SVM的思想应用到Logistic Regression中，从而建立两者的联系。然后讲了如何使用SVM的解来处理Soft Classification 问题；最后介绍了Kernel Logistic Regression