机器学习技法笔记 – Kernel Logistic Regression (核逻辑回归)

Soft-Margin SVM as Regularized Model

在前四章中,我们从“最胖的分割线”出发,介绍了Hard-Margin SVM,之后我们为了解决使用了高维特征转换带来的计算复杂度,我们介绍了Solving Dual SVM  Problem,这种方法利用KKT条件,将求解原最佳化问题转化为求解原最佳化问题的强对偶问题,使用\(\alpha_n\)表示了\(b, w\),但是这种方法并没有完美的解决高维特征转换带来的高计算复杂度问题,它只是把这一计算过程隐含在了QP标准型中\(Q\)矩阵的计算过程中,之后我们介绍了Kernel Support Vector Machine,通过这种方法,可以将原高维特征转换需要的\(\widetilde d^2\)计算复杂度降低为\(\widetilde d\)或者更少,并介绍了两种重要的Kernel Function,通过改变Kernel Fcuntion的\(\zeta, \gamma\),可以得到各种不同形状的分类器,在第四章中,为了避免过于强大Kernel Function可能带来的过拟合问题,我们通过容忍分类器的犯错程度,引入了\(\xi\)这个参数,同时通过\(C\)系数用来权衡最大间隔和容忍犯错,从而引出了Soft-Margin Support Vector Machine,最终,我们通过调节\(\zeta, \gamma\, \xi, C\),再加上交叉验证或者留一法验证SVM的数量,来选择最合适的SVM。

本章将把SVM的思想运用于Logistic Regression。

以Soft-Margin SVM为例,通过下图我们可以发现,解Soft-Margin SVM问题与解L2 Regularization问题非常相似:

与解SVM问题不同的是,Regularization是以最小化\(E_{in}\)为目的,以\(w^Tw≤C\)为条件,而SVM则是以\(E_{in}\)做条件,但本质上,他们都是Regularization的一种思想。

对于Soft-Margin SVM,较大的\(C\)则对应了较小的\(\lambda\),即做更少的Regularization。

SVM versus Logistic Regression

那么SVM能不能用在Logistic Regression问题中呢?我们首先来看它们的误差函数:

我们可以发现,SVM与Logistic Regression的误差函数在值域上是比较近似的,所以我们可以近似的把解SVM问题看做解L2Regularization的Logistic Regression问题。

SVM for Soft Binary Classification

那么如何将SVM的思想用于Logistic Regression中呢?以下是一种做法:

我们先看原始Logistic Regression的交叉熵函数(误差函数):

再来对比使用SVM后的Logistic Regression的交叉熵函数:

我们先在原始数据中求出SVM的\(w_{SVM}, b_{SVM}\),然后再添加一个缩放因子\(A\),平移因子\(B\),然后通过梯度下降或者随机梯度下降求出\(A, B\),最后得到最终的结果:

Kernel Logistic Regression

我们首先介绍表示定理(Representer Theorem):

即解任意一个L2 Regularization的问题,其最佳\(w_*\)都可以用\(\beta_n\)与\(Z_n\)线性组合得到。

证明如下:

如果\(w_*=w_∥+w_⊥\),\(w_∥∈span(z_n)\),\(w_⊥⊥span(z_n)\),证明\(w_⊥=0\)

考虑一个最优\(w_*\),使得\(err(y_n, (w_∥+w_⊥)^Tz_n\)),

则\(w^T_{*}w_{*}=w^T_∥w_∥+2w^T_∥w_⊥+w^T_⊥w_⊥>w^T_∥w_∥\)

与\(w_*\)为最优解矛盾,所以\(w_⊥=0\)

所以任意一个L2 Regularization的问题,其最佳\(w_*\)都可以用\(\beta_n\)与\(Z_n\)线性组合得到,即他们都可以使用Kernel Function。

所以我们终于可以将Kernel Function用于L2 Regularization的Logistic Regression:

以下是Kernel Logistic Regression的一般做法:

使用Kernel Function后,上式可以改写为以下形式:

然后可以使用GD/SGD等方法求解:

以上是对Kernel Logistic Regression在台湾大学机器学习技法课程的笔记总结。

机器学习技法笔记 – Soft-Margin Support Vector Machine (软间隔支撑向量机)

Motivation and Primal Problem

在上一章中,我们介绍了Kernel Support Vector Machine,通过使用不同的Kernel Function及其不同的\(\zeta, \gamma\),既可以做到高维或者无限维的特征转换,同时简化了\(Q\)矩阵的计算复杂度,但这不是没有代价的,以RBF Kernel为例,如果\(\gamma\)选取的不恰当,很容易造成过拟合。

同时,如果数据集本身含有噪声较多,这时如果我们仍然坚持使用强大Kernel Function使得数据满足硬间隔来使之线性可分,这时也会造成过拟合。

在本章,我们将介绍一种权衡的方法,这种方法将在间隔与噪声之前做一个权衡,即容忍一部分数据集的噪声来避免过强的特征转换造成的过拟合。

我们既希望数据集具有Large-Margin,也希望容忍一部分分类错误的发生,所以我们可以将Hard-Margin Support Vector Machine的Primal Problem改写为以下形式:

通过引入参数\(C\),并使\(C\)乘以分类器在数据集上犯错的次数,直观的看,较大的\(C\)放大了犯错的惩罚效应,希望犯错越少越好,而较小的\(C\)认为缩小了犯错的惩罚效应,具体\(C\)是如何影响原始的最佳化问题的,我们将在下面的推导中说明。

但是“分类器在数据集上犯错的次数”这件事是一个Boolean运算,这不是一个线性的运算,这会使得改写后的最佳化问题不是一个QP问题,这里,我们通过引入\(\xi_n\)来代替“分类器在数据集上犯错的次数”,\(\xi_n\)描述了分类器在数据集上犯错的程度,即犯错数据距间隔的距离:

这样的代替使得原问题成为一个QP问题,改写后的问题具有如下形式:

Dual Problem

为了求解改写后的最佳化问题,我们选择第二章用过的方法,通过写出原最佳化问题的Lagrange Function,然后通过求解其强对偶问题,再通过KKT条件求解出\(w, b\),新的Lagrange Fcuntion具有以下形式:

求解其强对偶问题:

先对\(\xi_n\)求偏微分:

所以,\(\beta_n\)可以用\(\alpha_n\)表示:

$\(\beta_n=C-\alpha_n\)$

又因为\(\alpha>0, \beta>0\),所以\(0≤\alpha_n≤C\),所以原Lagrange Function可以改写为以下形式:

可以发现原Lagrange Function的条件约束全部被隐含在了条件中,之后和第二章一样分别对\(b, w\)求偏微分,就可以用\(\alpha_n\)来表示\(b, w\):

在Soft-Margin中,通过KKT的互不松弛条件\(b\)的计算方法与Hard-Margin有相似和不同:

最后\(b\)可以以如下形式表示:

最后写出原Lagrange Function的QP标准形式,通过QP Solver写出最佳化的\(\alpha\):

该QP问题具有\(N\)个变量,\(2N+1\)个条件。

这即是Soft-Margin Support Vector Machine了。

Messages behind Soft-Margin Support Vector Machine

下图是不同的参数\(C\)对分类器的影响的效果:

可以看出,对于较大的\(C\),有着更少的错误容忍度,但是也会出现过拟合的问题,所以我们仍然需要谨慎选择\(\gamma, C\)来避免过拟合。

接下来我们来讨论\(\alpha\)的物理意义以及\(C\)是如何影响分类器的形状的。

我们先观察对偶松弛条件:

根据不同满足对偶松弛条件对应的\(\alpha_n, \xi_n, C\)的取值,将有以下三种情况:

  1. 如果\(\xi_n=0\),\(\alpha_n=0\),这对应着那些没有犯错误的数据点
  2. 如果\(\xi_n=0\),\(0<\alpha<C\),这对应着那些刚好落在间隔上的点
  3. 如果\(\alpha_n=C\),这对应着那些落在间隔内的犯错误的点

可以看到对应2,3这两种情况,\(\alpha_n\)的上界是\(C\)的取值,而\(\alpha_n\)最终将计算出\(b, w\),这决定了间隔的大小,所以,较大的C会使得间隔越大。

这同样也是Soft-Margin Support Vector Machine中,Soft-Margin的意义。

Model Selection

下图是使用RBF Kernel通过不同的\(\gamma, C\)的取值对分类器形状的影响:

下图是采用交叉验证(Cross Validation)的\(E_{cv}\)值在各个分类器的表现:

所以,有时候\(\gamma, C\)的取值还是得具体问题具体分析。

当我们在用留一法(Leave-One-Out)在SVM上做验证时,有几点有趣的事实,我们很容易发现那些非支持向量对分类器的间隔是没有影响的,所以我们可以通过支持向量的数据来估计误差:

由于这种方法计算复杂度较低,我们通常使用这种方法快速排除一些不好的参数,但是通过这种方法选择的参数,也不一定是最好的,也需要具体问题具体分析。

以上是对Soft-Margin Support Vector Machine在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Kernel Logistic Regression。

机器学习技法笔记 – Kernel Support Vector Machine (核支持向量机)

Kernel Trick

在上一章中,我们通过解原Lagrange Function的强对偶问题,将原方程中的\(b, w\)用\(\alpha\)表示,后通过KKT条件求解出\(b, w\),其QP问题的标准形式如下图:

但是这并没有解决上一章开始时提出的问题,即表面上我们似乎通过求解原Lagrange Function的强对偶问题,避开了\(\widetilde d\)维度的复杂计算,然而实际上复杂度为\(O(\widetilde d)\)的计算被隐含在了标准QP问题的\(Q_d\)矩阵计算过程中。

但是真的是这样吗?

下面将以一个\(\widetilde d\)维的二次多项式为例,引出Kernel Trick(核技巧)。

其计算过程可以展开为以下形式:

可以看到,通过简单的公因式提取,将原来\(O(d^2)\)计算复杂度简化为\(O(d)\)的复杂度。

我们将推导的结果称之为原特征转换函数的Kernel Function,它具有以下形式:

可以看出,原特征转换方程的内积,可以被简化的写成上述形式,极大的简化了计算量。

所以\(Q_d\)矩阵计算过程,可以改写为以下形式:

而\(b, w\)可以改写为以下形式:
而最终的\(g_{svm}(x)\)可以改写为以下形式:

所以,我们可以总结出使用Kernel Trick的Kernel Dual SVM的QP问题标准形式:

Polynomial Kernel

通过对之前二次\(d\)维多项式添加系数\( \sqrt{2\gamma}\),可以得到各种不同的特征转换方程,他们具有不同的几何意义。

他们的通式如下:

下图通过修改\(\gamma\)的值,从而得到不同的三个特征转换方程,以及他们对应的效果:

实际上我们很难说这三条曲线哪条是更好的,需要注意的是,我们通过修改\(\gamma\)的值,使得Kernel Function改变,从而间接改变了\(b, w\)的取值,所以曲线的形状发生了变化。

更一般的,多项式核具有以下通式:

在实际应用中,通过调节\(\zeta, \gamma\)来寻求最合适的曲线。

Gaussian Kernel

通过Gaussian Kernel,可以做无限维的特征转换,接下来,我们将介绍Gaussian Kernel。

对于特征转换函数\(\phi(x)^T\phi(x)=e^{-(x-x’)^2}\),可以进一步展开成\(e^{-x^2}e^{-x’^2}e^{2xx’}\),考虑\(e^x\)的Taylor展开:

$$e^x=\sum_{n=0}^{∞}\frac{x^n}{n!}$$

所以,\(\phi(x)^T\phi(x)=e^{-(x-x’)^2}\)可以改写为以下形式:

更一般的,Gaussian Kernel(通常也称作RBF(Radial Basis Function Kernel))具有以下形式:

下图通过调整不同的\(\gamma\)值,表示了三种RBF Kernel的效果:

明显可以看出,非常大的\(\gamma\)可能导致Overfitting(过拟合)

Comparison Of Kernels

  • Linear Kernel:

优点:较为安全,不易出现过拟合的情况,计算快速,易于解释。

缺点:对线性不可分的数据集不可用。

  • Polynomial Kernel:

优点:限制较少,可以控制\(Q\)矩阵的计算复杂度。

缺点:参数较多,比较难选,\(Q\)维度较大时,计算较为复杂。

  • RBF Kernel:

优点:非常强大,参数较少

缺点:不易解释,计算较慢,容易过拟合

以上是对Kernel Support Vector Machine 在台湾大学机器学习技法课程的笔记总结。

下一章,我们将介绍实际中更为广泛使用的Soft-Margin Support Vector Machine。

机器学习技法笔记 – Solving Dual SVM Problem (解SVM对偶问题)

Motivation Of Dual SVM

在Hard-Margin SVM的结尾,我们提到对于Non-linear separable(非线性可分)的数据集,可以通过做特征转换的方式,将原始数据映射到一个更高维度的空间,将原始非线性可分的数据集转换成线性可分的数据集。

经过特征转换后的数据集有\(\widetilde{d}+1\)个变量,其中\(\widetilde{d}\)为经过特征转换后\(\phi_{z}\)的维度,\(N\)个约束。

直观的看,似乎随着\(\widetilde{d}\)的维度增大,转换后的QP问题的计算复杂度也会变大,但是稍后将会通过求解Dual SVM问题证明,无论转换后的空间有多么复杂,求解转后的QP问题的复杂度只与转换前原始数据的维度\(N\)有关,与\(\widetilde{d}\)无关。

Lagrange Dual SVM

对于求解有条件约束的最佳化问题,使用拉格朗日乘数法,简要地说,原函数的条件极值将在原函数的梯度与约束函数的梯度方向相反时取得。

对于一个L2 Regularization,拉格朗日乘数法的流程如下:

将L2 Regularization最佳化问题的约束函数乘以\(\lambda\)后求其梯度与原函数梯度相加,令其和为\(0\),然后求解。

对于Hard-Margin SVM,其Lagrange Function可以写成如下形式:

所以,原始问题可以改写为以下形式:

对于目标函数需要最小化\(\frac{1}{2}w^Tw\)求解\(b, w\)这一过程,与\(\alpha\)的取值无关。所以一个可行的思路是先确定\(\alpha\)的值,可以求其最大或者最小值,这里我们选择求取其最大值。

当求\(\alpha\)的最大值,\(b, w\)可以视为常数,且约束条件\(y_{n}(w^Tz_{n}+b)≥1\)蕴含在了式中,对于任意一对违反约束条件的取值,将会造成\(\alpha\)与一个正数相乘,使得其最大值为无限大,而对于任意一对符合约束条件的取值,会使得\(\alpha\)与一个非负数相乘,其最大值为\(0\)。

所以我们可以通过求解这个Lagrange Function从而进一步求得\(b, w\)。

Solving Dual SVM

对于原Lagrange Function,先求解\(\alpha\)再求解\(b, w\)面临着一些问题,如果直接求解\(\alpha\),必然会用\(b, w\)表示\(\alpha\),之后继续求解\(b, w\),这种顺序并没有解决由于特征转换后维度变大带来的计算复杂问题。

为了解决这个问题,这里的做法是求解原Lagrange Function的强对偶问题,这个强对偶问题具有一些很好的轻质,最终使得我们可以用\(\alpha\)表示\(b, w\),避免了上述问题。

接下来,通过我们将通过一系列推导来证明这样的做法是可行的。

证明如下:

对于任意给定的\(\alpha\),且\(\alpha≥0\),都有上式成立。

对于最大的\(\alpha\),都有上式成立,上图的右式为原Lagrange Function的对偶问题。左式和右式的区别在于,左式把\(b, w\)看做常数,求原函数的最大值下\(\alpha\)的取值,在求原函数最小值下\(b, w\)的取值,而右式则顺序相反。

如果原函数满足(即下文将要提到的KKT条件):

  1. 原函数是凸函数
  2. 数据集在\(\phi_{z}\)中线性可分
  3. 线性约束条件

则右式为左式的强对偶问题,而在本问题中,以上三个条件全部满足,所以我们可以将直接求解原Lagrange Function转换为求解其强对偶问题。

其强对偶问题方程如下:

此时,将\(\alpha\)看做常数,先求\(b\)的偏微分:

所以上式进一步被化简为:

接着对\(w\)求偏微分:

上式进一步被化简为:

原对偶问题化简到上式,可以发现\(b, w\)已经全部被\(\alpha\)表示,原式已经转化为一个求解\(\alpha\)的最佳化问题。

根据强对偶问题中\(\alpha\)与\(b, w\)以及约束的关系,总结出KKT条件,KKT条件是解含有不等式约束的最佳化问题的充分必要条件:

即:

  1. 特征转换后数据线性可分
  2. \(\alpha≥0\)
  3. \(\sum y_{n}\alpha_{n}=0\),\(w = \sum\alpha_{n}y_{n}z_{n}\)
  4. 对偶松弛条件:\(\alpha_{n}(1-y_{n}(w^Tz_{n}+b))=0\)

最后,找到上式与QP Solver对应的系数,通过QP Solver求解:

最后通过对偶松弛条件,求出\(b\):

Message Behind Dual SVM

由对偶松弛条件,又因为\(\alpha>0\):

所以:\(1-y_{n}(w^Tz_{n}+b)=0\),即所有参与计算\(\alpha\)向量,全部落在了最大间隔上,这些向量,称之为支撑向量。

而求解得到的\(b, w\),其实是\(\alpha\)与\(y_{n}\)与\(z_{n}\)的线性组合(在后续的章节,将会证明表示定理,即任何求L2 Regularization的\(w\)最终都可以表示为\(\alpha\)与\(y_{n}\)与\(z_{n}\)的线性组合)。

最后用下图引出下一章节要解决的问题,即在计算\(Q_{d}\)二次型的系数矩阵时,每行每列的\(q_{n, m}=y_{n}y_{m}z^T_{n}z_{m}\)时,\(z^T_{n}z_{m}\)的内积仍然是\(\widetilde{d}\)维的,其计算依然具有非常高的复杂度,在下一章,我们将通过引入Kernel的概念解决这个问题。

以上是对Solving Dual SVM Problem在台湾大学机器学习技法课程的笔记总结。

机器学习技法笔记 – Hard-Margin Support Vector Machine (硬间隔支持向量机)

Large-Margin Separating Hyperplane

在下图所示三条分隔线中,虽然三条分隔线都在训练集上使得\(E_{in} = 0\),但是我们在直觉上会仍然倾向于认为第三条分隔线是最佳的。

较为直观的解释是,相较于第三条分隔线,第一条和第二条分隔线对于靠近训练集的数据点的判断可能不够精准,而第三条分隔线对于这些数据点而言,具有更好的鲁棒性。 具有更好的鲁棒性,就说明该分隔线具有更好的容错能力。

我们希望找到这样一条线,这条线在训练集上到每个数据点距离越大越好,且正确分隔数据点,即\(E_{in} = 0\)下图描述分隔线到训练集上数据点的间隔。

更具体地,可以将如何找到这样一条线描述为如下图所示的一个最优化问题,即找到一个最大的超平面,既能正确的区分训练集上每一个数据点,且使距离超平面距离最近的数据点的距离最大:

Standard Large-Margin Problem

我们用如下形式表示超平面:

以下图三维空间为例,其中,\(w\)为右图所示平面的法向量,\(x’\)为平面上一点:

则点\(x\)到平面的距离可以表示为\(x\)到\(w\)的投影,如下图所示:

所以,原最优化问题可以改写为以下形式:

由于缩放超平面的\(w \)与\(b\)的值并不影响超平面的形状,考虑一个特殊缩放:

$$cw^T+cb=0$$

使得

$$\min \limits_{n=1,…,N}y_n(w^Tx_n+b)=1$$

通过这样的特殊缩放,使得原问题的目标函数与约束被简化为如下形式:

上述问题被称之为等式约束的二次规划问题,本问题已经可以使用拉格朗日乘子法求解,但是在此处为了结合讲义进度,拉格朗日乘子法将会在后期与KKT条件一并介绍,此处为了将问题改写为能够被一般求解程序求解的形式,还需要对等式约束进行如下改写:

即使原等式约束

$$\min \limits_{n=1,…,N}y_n(w^Tx_n+b)=1$$

被放宽为

$$\min \limits_{n=1,…,N}y_n(w^Tx_n+b)≥1$$

最终目标函数的解也不会受到影响。

证明如下:如果存在一个最优解\((b, w)\),使得

$$\min \limits_{n=1,…,N}y_n(w^Tx_n+b)=1.126$$

那么对于目标函数\(\frac{1}{\Vert{w}\Vert}\),该最优解可以进一步缩放为

$$(\frac{w}{1.126}, \frac{b}{1.126})$$

这与\((b, w)\)为最优解相矛盾,故最优解一定使得

$$\min \limits_{n=1,…,N}y_n(w^Tx_n+b)=1$$

所以,即使对原等式约束条件进行放宽,也不会影响最终目标函数的解。最终,我们将原问题改写为以下形式:

Support Vector Machine

通过上下图发现,待求的目标函数及其约束条件所构成的问题属于右图所代表的二次规划问题,且由于范数函数是凸函数,即\(\frac{1}{2}w^Tw\)为凸函数,对于凸函数而言,局部的最优解即是全局的最优解,在本问题中,我们只需要找到右图二次规划中目标函数及其不等式约束的各项参数,即可用现有的一些解二次规划的程序工具求解,而具体求解的过程会在后续的文章提及。

通过观察和简单计算,二次规划各项参数具有如下图所示的关系:

找到上述各项系数对应关系后,通过解QP的应用程序求解:

同样,可以通过\(z_n=\Phi(x_n)\)对$x_n$将问题映射到更高维度的空间来求解。

hard-margin SVM与regularization有着相似与不同之处,对于regularization,它以\(w^Tw ≤ C\)为约束,以最小化\(E_{in}\)为目标,而hard-margin SVM则以\(E_{in}=0\)为约束,希望最小化\(\frac{1}{2}w^Tw ≤ C\),本质上hard-margin SVM也是一种regularization的体现。

通常来说,较少的dichotomies意味着更小的VC维,而在hard-margin SVM中,由于对margin的限制,使得dichotomies减少,这一定程度上使得VC维变小,从而可能使得\(E_{out}\)表现更好。

以上是对Hard-Margin Support Vector Machine在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Dual SVM Problem。