Category: All

Machine Learning Techniques Lecture 7: Blending and Bagging


 
 

内容:

介绍了Blending和Bagging的方法,两者都属于Aggregation这个大家族,Aggregation要做的事情就是把一堆的小g合起来变成一个更符合需求的大G。最基本的方法就是求平均,算术平均,更进阶的方式是如果你今天想做linear/non-linear的化其实只要做一个two-level learning就可以做到了。最后我们介绍了如何通过 bootstraping 从已有的固定资料得到不一样的hypothesis,然后再合起来的方法。

 
 


 
 

我们之前讲到的是Kernel Model,做的事情是把很多很多的feature包在kernel里面,然后用不同的机制去求解。我们把kernel model延伸到可以做regression,你可以把原来知道的ridge regression利用representer theorem来得到他的kernel的形式,你也可以参考SVM设计一个新的formulation来得到sparse solution 的Kernel 形式。

 
 

今天开启一个新的主题,如果我们得到了一些hypothesis,这些hypothesis可以帮助我们做预测,我们怎么把这些有预测性的hypothesis合起来让他们变得更好,这样的模型叫做Aggregation model。今天讲两个常用的model,blending and bagging。

 
 


 
 

先来想想为什么想要用aggrregation?

假设今天你有15个朋友,每个人都告诉你明天股市的涨跌预测分析,那你听了以后作的决策是什么。

 
 

你的决策想法可能会有:

  1. 你的朋友里面有人炒股比较厉害,可能他的预测比较有参考价值,因此选择一个可以信赖的人的结果。(就是validation)
  2. 你的朋友每个人都有不同的专长,不知道相信谁,投票决定,看猜测涨的人多就决定相信涨。
  3. 如果你的朋友的炒股能力可以参数化,那就是加权投票看结果。
  4. 你的朋友有的人擅长科技类股票,有的人擅长能源类股票等等,所以呢在不同的条件之下就相信不同的人。

 
 

我们要做的就是把这些情境的处理对应到机器学习里面。做的这件事就是叫做 aggregation model 在做的事情。

 
 


 
 

我们把上面的口语化的表述数学化。

 
 

每个朋友就是 hypothesis 就是 g_n;

  1. 就是选Err_val最小的
  2. Uniformly 和
  3. Non-uniformly 加权和
  4. 函数代表了成立条件再乘以g_n

从一到四更加的泛化,2包含1,3包含2,4包含3。

 
 

Aggregation model 就是这么非常包山包海的丰富,未来的五讲会分别去在各个方向作介绍。

 
 


 
 

先来看比较简单的,比如靠的是selection,从里面选一个最好的。

黄色框就是公式表示,其实在前面的validation的时候的方法就是用到了selection,选一个最好的。

我们使用training error而不是使用validation error是否可以?很危险,非常可能overfitting。

这种方式里面的一个重要假设是:你想要选到一个好的g^-_t最后才能够选到好的。如果你的候选结果都是不好的,那就是废渣里面再怎么选也是废渣。

 
 

如果只靠选择的话,我们只要有一个强者就好了。

但是aggregation想象的是如果今天我们一堆看起来弱弱的,但是其实还算是可以的hypothesis,我们能够不能依靠集体的智慧让最终结果变得更好。也就是说不是靠一个很强的来做最终结果。

 
 


 
 

先来思考一下为什么aggregation可以做得更好?

 
 

先看左边的图,如果要求只能用水平垂直的线来分类,单个怎么样都做得不大好,如果多条水平垂直的线合起来,那么就有左图的折线,把圈圈叉叉完美分开。可能代表aggregation相当于拓展了模型的分类能力。

如果今天有一堆hypothesis如右图,每一条结果都还不错,如果让灰色的线投票的话会很接近比较中庸的线,就如图中的黑色实线,也就大概比较宽的线。这可能代表了aggregation可以有regularization的能力。

也就是说aggregation同时具有让模型更加复杂和简单的能力,如果你能利用好的话,就能得到比较好的学习结果。

 
 


 
 

练习

 
 


 
 

下面我们开始讲怎么样把这些hypothesis合起来。

 
 

第一个概念: blending


Uniform Blending(voting) for classification

这一般使用在我们手上已经有一堆g,怎么把他们的结果合起来变的更强。黄色框表示的就是公式化的投票方式的结果的表述。如果你所有的小g大体都是相同的,那么你的大G也就和他们相同。如果你的一堆小g结果都很不同,怎么去融合?

如右边的图,在横竖分成区块后,每一个区块单独进行投票,少数服从多数,就得到了这个折线结果。也就是说如果今天分类结果很不一样,那么我们可以通过民主投票的机制来获得更加复杂的分类边界,对于多类别的分类也可以做一样的事情。

 
 


 
 

Uniform blending for regression

把大家的输出都通通的加起来求平均得到大G。如果小g统统都一样,这种方式没带来什么好处,但是如果小g比较不一样,可以抵消一些低估和高估,得到一个比较中庸的结果比较好。

 
 

从blending用在classification/regression看出,如果我们这个aggregation要起作用,很重要的是我们的小g要diverse,就是意见要有不一样,这样融合的家过会比较好。

 
 


 
 

我们来进一步分析为什么uniform blending为什么会表现更好?

 
 

x表示输入,在下面都是一样的,写着比较麻烦,就省略了,这里推到的目标是把单个的小g和f的平方错误 的平均 和 大G和f的平方错误联系在一起。

首先展开,再代入G替换一次小g平均,根据目标凑G-f平方,再凑一个大g小g平方,的结果。

蓝色框表示的是单一的小g的结果,如果是对所有的小g则是下面黄色框所示:所有的小g的E_out = 大G的E_out + 大小g的平均的期望值的差(这一项一定是正的)。所以小g的平均E_out要比大G来得大,所以就证明了uniform blending是有好处的。

 
 


 
 

如果今天有这么个抽象的机器学习过程,在每一轮里面有n笔资料,通过已有的演算法来求每一笔资料的小g,结果就是取小g的平均。把上面这件事做无限多次,求平均期望值。

灰色部分就是写出的式子

物理上的解释:演算法表现的期望值 = variance(小g的特性表现) + bias(小g的共识表现),在统计的书里面比较常见,平均的过程就是消除前面这一项,让意见趋于一致。

 
 


 
 

练习

 
 


 
 

接下来讲的是 linear blending (就是加权平均)

什么样是好得票数,能够达到E_in最低的是好的票数,也就是说我们要调整我们的alpha让Ein最低,限制是每一个alpha都是大于等于0的。

因此红色框表示的就是regression的时候的公式,换成后边的框所示,和我们之前讲过的 transform 过的 linear regression 差不多形式,区别在于有alpha>0的条件。也就是说整个学到好的alpha的过程,就是之前讲过的two-level learning,在probilitistic SVM的时候提到的。现在的two-level是先得到一堆g,在做linear regression得到alpha。

 
 


 
 

问题是有了alpha>=0的限制。

如果alpha<0,则表示的是结果是反的,所以把符号相反。举个例子比如你有一个算法做binary classification得到的结果可是说是得到的结果99%是错的,那么反过来用正确率就非常高。

所以真正在做linear blending的时候忽略这个constraint 也没啥问题。

 
 


 
 

还有个问题是小g通常是怎么来的呢?

从各自不同的model通过求最好的E_in得到的。以前曾经提到过如果你选择模型的时候用的也是E_in的时候,你选的是best of best,你要付出的代价很大,所以后来说为什么我们要用validation而不是Ein来做选择。(譬如你要选的是两个班的第一名,你要付出的代价是查询两个班的结果)

这边类似,linear bendling包含了selection,alpha是说到底我的validationerror有没有最小。也就是说如果你用E_in来做blending,你现在选的是把所有的第一名集合起来做,你要付出的代价比best of best还要高(因为你包含best of best当作你的特例),也就是更危险。因此通常我们不建议使用Ein来学alpha,因为很容易就overfit了。【就是说g用了Ein学,alpha不要用Ein再来确定了】

这里建议在算alpha的时候,不要用training的Ein来算,而是采用E_validation来操作。

 
 


 
 

因此真正的操作过程【就是只从用来验证的资料来确定alpha】:

 
 

从一个比较小的Dtrain得到你的一堆g-,然后把你的validation set里面的资料透过这些g-转换成z空间的资料,我们把这个转换叫做phine-。

做完转换后你就可以把你的linear model用在这些新的资料上面求出alpha,这时候G就是这些alpha和phine(x)的线性组合的内积。

这里用的是phine(x)而不是phine-(x)是因为我们希望透过phine,也就是真正的g而不是g-,来让我们的表现更好。

 
 

对于non-linear blending(stacking):同样是做完转换的资料z,不再用linear model,而是任何的model Any,学习到g,最后一样得到的是g和phine(x)的组合即是G回传回去。

Any-blending:模型能力强大,但更容易overfit,使用上要非常小心。

 
 


 
 

故事:

11年的时候KDDCup一个冠军的方法:先学到小g(single model),然后做any-blending,融合后变成一下更强的G,然后再做一次linear-blending,得到了最好的结果。

 
 


 
 

练习

 
 


 
 

Blending:如果你已经透过某些方法得到小g,我们怎么去合起来,我们可以非常公平的投票,也可以加权投票。

更多的时候你更想要知道小g到底是怎么来的,我们能不能一边学小g,一边把它合起来,下面我们会讨论这个问题。

我们首先来看什么时候可以得到不一样的小g:

  1. 从不一样的模型得到不一样的小g
  2. 同一个模型,不同的参数得到不同的小g
  3. 演算法本身就存在randomness产生的不同的小g
  4. 你的资料存在randomness产生的不同的小g

 
 

下面我们探讨能不能拿同一份资料来制造很多的小g?

 
 


 
 

我们回头来看之前推导的理论结果:Bias + variance 概念就是强化共识

前提是我们需要很多不同的资料来获得共识,但问题是我们这里考虑得是同一份资料,怎么处理呢?

 
 

我们的目标是无限多小g的平均,但是我们做不到,因为首先没有办法产生无限多,其次资料要是新鲜的也做不到,现在只有现存的一堆资料。

所以妥协:有限多的大量的数据,通过已有的资料产生长得像新鲜的资料的资料。

 
 

怎么做?

统计学工具:bootstrapping,从你手上已有的资料去模拟不一样的资料。

 
 


 
 

bootstrapping:

重新的从我手上的资料里面去取n笔,取一笔记录一下再放回去,再取一笔记录再放回去,以此类推。有放回的抽样得到的资料在统计学上叫做 bootstrap sample(D_t)。

 
 

Virtual aggregation:每一次找一个新的小D_t得到新的小g_t,最后平均

Bootstrap aggregation(又叫做bagging):每一次从手上资料生一个D_t得到新的g_t,最后平均

 
 

这是一个meta algorithm,就是可以附着在任何基本演算法基础上使用。

 
 


 
 

举例:

已有的资料做bootstrap后得到的资料集用Pocket 算法算出来的结果是浅灰色的线,生出了25条;然后把线合起来得到黑色的线,效果相对会比较好一点。

 
 

这边要注意的是:你的演算法对随机是敏感的,得到的小g越不一样,效果会比较好。

 
 


 
 

练习

 
 


 
 

总结:

介绍了Blending和Bagging的方法,两者都属于Aggregation这个大家族,Aggregation要做的事情就是把一堆的小g合起来变成一个更符合需求的大G。最基本的方法就是求平均,算术平均,更进阶的方式是如果你今天想做linear/non-linear的化其实只要做一个two-level learning就可以做到了。最后我们介绍了如何通过 bootstraping 从已有的固定资料得到不一样的hypothesis,然后再合起来的方法。

 
 

下一讲:

我们你能不能得到比bagging更不一样的hypothesis呢?

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

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的技巧来做学习。下面我们开始讲如果我们有很多的机器学习的方法的时候,我能不能融合各种方法的好坏处,调出一个最佳解。

 
 

 
 

 
 

 
 

 
 

 
 

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 的问题

 
 

Machine Learning Techniques Lecture 4: Soft-Margin Support Vector Machine


 
 

内容:soft-margin SVM

首先列出soft-margin SVM的形式表达,出发点是不坚持所有的已知数据点不一定全部要分对,所以增加了一个参数用来控制设定违反分类结果的程度。推倒的时候也是一个QP问题,所以同样通过对偶问题来化简求解。soft-margin SVM可以告诉我们的是可以把数据通过alpha的值分为三类,边界上的,边界内的,边界外的,对于我们做资料分析很有用。另外我们还提到可以使用cross validation来选择模型参数。

 
 


 
 

上一讲:Kernel SVM

目的是通过把Dual SVM的转换和算内积步骤合起来成为Kernel消除空间维度对计算量的影响,这样以后对于任意维度的SVM都能做到。

 
 

Soft-margin support vector machine:

原来讲的都是不能违反任意一个数据的结果叫做Hard-Margin,这里放宽这个限制。从上一讲出发,gaussian svm太复杂了,我们有没有办法来减少overfitting。

 
 


 
 

上一讲我们得到的信息是:SVM可能会overfitting。

 
 

一个原因是转换太powerful了;另外一个原因是我们坚持要把资料完美的分开,不能出错。

如图所示,如果一定要分开的话就会像右边的图一样边界非常复杂,但不见得这样是合理的。

 
 

也就是看作资料里面存在noise,怎么去处理。

 
 


 
 

我们首先来看看我们以前是怎么处理资料里面存在noise的问题的。

 
 

Pocket 模型

没有办法找一条线分开,那么就找一条线犯最少的错误。

 
 

Hard-margin 模型

所有的圈圈叉叉都要分对,而且还要选择w最小的。

条件太多,所以我们应该像pocket一样容忍一些错误。

 
 

其中一个方式是(可以看作是 pocket 和 hard-margin 的合体):

和原来的SVM一样,我们希望的是w长度最短的,对于做对的点要符合原来的条件来求解,做错的点就不管了。

如果只是这样的话不行,机器会默认偏向统统做错,因此我们需要的是做错的越少越好。

 
 

我们又要W最小,又要做错的最少,因此加上一个参数C来做平衡。C越大表示越不要犯错越好,C比较小的时候表示W越短越好。

 
 


 
 

所以这是我们的新问题 soft-margin SVM,上面黄底表示的公式。

 
 

公式的问题:

存在boolean运算,不是线性的运算,也就是说不是QP问题,也就不能再使用Dual,Kernel机制。

不能区分错误的大小。

 
 

因此提出了下面黄底表示的新的问题公式。

我们把错误记录在 kesi_n 的变数里面, kesi_n >= 0,表示的是离我想要的那个值到底有多远。

这样我们minimize的式子里面也就可以来衡量你犯了多大的错误用kesi的和来表示。

这样就符合了线性变化的条件,同时也可以衡量错误大小的要求了。

 
 


 
 

Margin voilation:意思就是错误可以衡量,图示就是违规的数量的图解。

C:描述的是违反margin的程度,C越大表示允许违反的越小,反之边界会比较平滑和胖。

变数数量:d+1+N,N表示的是每个点到底违反了多少margin,因为只记录违反的N个点,所以多了N个条件。

 
 


 
 

练习

 
 


 
 

黄色底公式就是我们上面推导得到的soft-margin SVM公式。下面就是根据这个问题推导他的对偶问题,然后就可以和hard-margin时候一样,享用容易做feature transform的特性。

 
 

所以先写出 lagrange multipliers,步骤和原来一样,把条件合并到目标函数里面去。然后就得到了 lagrange dual,之后和之前一样用KKT condition来化简。

 
 


 
 

问题写下来如上面的黄底框所示。

化简的第一步是对整个式子求kesi的偏导等于0,就得到一个alpha,beta相关的等式,所以可以把beta换掉用alpha表示,同时alpha的限制条件加强了,得到的结果和原来的hard-margin问题化简结果相似。

 
 


 
 

式子就变得如上面黄底那样简单了。到这里首先是minimize,然后是maxmize,这个式子在hard-margin SVM几乎一样,同样里面的部分去微分求解,和第二讲讲过的dual一致,具体见那边的推导。

 
 


 
 

然后你就会得到一个几乎和hard-margin SVM一样的式子,唯一的差别就是对alpha_n有了一个最大值C的限制。

 
 

因此现在这个问题有N个变数,2N+1个条件。

 
 


 
 

练习

 
 


 
 

推倒完了以后就可以得到 Kernel soft-margin SVM的算法了:

  1. 求解这个问题的时候加上了额外的upper-bound条件。
  2. 一样去求解QP问题
  3. 一样去算b
  4. 得到最后的hypothesis SVM长什么样子

 
 

C的值就是来控制你想要得到边界是更细致变化还是更粗变化。

 
 

这里还需要探讨的问题是,这里面我们算b的方式与原来一样么?

 
 


 
 

Hard-margin里面就是列出KKT条件,图中所示一条的乘积的前后两部分必须有一个为0,那么因为alpha>0,所以后半部分就必须=0,就可以直接告诉我们b是多少。

Soft-margin一样依葫芦画瓢,列出不能同时存在的条件,这里不一样的就是多了一个kesi用来记录到底违反多少点。还存在另外一个条件。通过这两个条件,和原来的方式一样,先找一个support vector,也就是alpha>0,这样就会有 b = 一个和kesi相关的式子,如果kesi = 0,b就可以直接求出来。

 
 

所以求解b的方法总结来说就是:找一个可以使得kesi=0的support vector(命名为free support vector,不再是任意的support vector),这样b就可以很容易得到解。

 
 

实际中也有极少数的情况不存在free support vector,就只能用一堆不等式来限制,就可能存在一堆b,都是可以的答案。

 
 


 
 

然后我们来看看 soft-wargin SVM 的表现怎么样。

当C取不同的值的时候的结果如上面图示,C越大表示越不想犯错误,边界越复杂。C值越大越容易overfit,所以需要好好的去选择参数。

 
 


 
 

我们刚才就是使用 complementary slackness 这个条件来求解b,我们再通过这个来看看 soft-margin SVM 到底告诉我们一些什么信息。

 
 

Soft-margin SVM 的两个 complementary slackness 条件如黄底所示,根据这两个条件我们可以把手上的资料点分成三种。

第一种是free support vector,特点是0<alpha<C,kesi=0,可以用种点来唯一的算出b,这些点就是刚刚好在胖胖的边界上的点。

第二种是non-support vector,特点是alpha=0,kesi=0的点,也就是没有违反边界的点,分得非常好的点,在胖胖的边界外面。

第三种是bounded support vector,特点是alpha=C,kesi != 0的一个值,记录了违反多少,就是图中处于胖胖的边界内的点。

 
 

通过alpha的值就可以把手上的数据点分成三种,这三种对于你做资料分析很有用。

 
 


 
 

练习

 
 


 
 

讲完了model,我们来看看怎么选参数。

 
 

上面的九张图统统都是用的Gaussian kernel的SVM,但是采用了不同的C,garma的组合。横轴是表示的C,纵轴表示的是garma。

 
 

怎么选?

最好用的工具就是Validation。

 
 


 
 

通过采用 Cross Validation,算一下每一种情况下的Error,选一个最好的。

 
 


 
 

如果把 cross validation 递推到极限的话,就是每一份资料只包含一个的话,这时候就有一个特殊的名字叫做 leave-one-out CV Error,这个在SVM上面会有一个有趣的结果。

 
 

E_loocv 的结果和 support vector 的数量是有关系的,可以证明 E_loocv <= SV数量/资料量。

假设今天你有一万个点,如果你解完这个问题以后,对于第一万个点刚好他的alpha=0。意味着只踢掉第10000个点,前面的9999笔资料都丢进SVM,这组alp[ha还会是最佳解,也就意味着最后一个没有用,alpha=0。也就是说把non-support vector 拿掉对于解SVM一点影响也没有。

同样的对于 non-support vector 对于 cross validation 的贡献也是0。

所以就有上面的结论。

 
 


 
 

也可以通过上面的结论来做模型的选择。

 
 

把所有的情况的support vector的数量列出来如上面的图示,但要注意的是这个公式说的只是个上限,不是实际的错误率。

把上限做到最好不代表把真正的错误率做到最好,因此这个结论通常是拿来排除比较危险的结果,就比如上面的三张图所示的结果,先予以排除。

 
 


 
 

练习

 
 


 
 

总结:soft-margin SVM

首先列出soft-margin SVM的形式表达,出发点是不坚持所有的已知数据点不一定全部要分对,所以增加了一个参数用来控制设定违反分类结果的程度。推倒的时候也是一个QP问题,所以同样通过对偶问题来化简求解。soft-margin SVM可以告诉我们的是可以把数据通过alpha的值分为三类,边界上的,边界内的,边界外的,对于我们做资料分析很有用。另外我们还提到可以使用cross validation来选择模型参数。

 
 

下一讲:

至此对SVM进行了一个完整的介绍,但这些都是在binary classification的情况下,下面开始讲如何将SVM延伸到更复杂问题的求解。

Machine Learning Techniques Lecture 3: Kernel Support Vector Machine


 
 

内容: kernel SVM

首先讲了把原来的dual SVM的转换和内积的两步合并为Kernel,通过这样回避了原来SVM计算涉及到的对空间维度的依赖,然后讲了多项式kernel和Gaussian kernel,最后对这些kernel做了简单的比较,如果想要的是效率的话往linear走,想要复杂边界的话往高纬度走。

 
 


 
 

上一次我们看的是SVM的对偶形式,其新的形式好像跟空间维度D没有关系,可以使用二次规划来求解。

 
 

今天来看一下 Kernel support vector machine,把好像拿掉,使SVm的形式真的和空间维度没有关系。

 
 


 
 

这是我们上一次推到出来的对偶问题:

从条件的数量和变数的数量来看,这个问题好像都和空间维度D没有关系。但是如果计算Q_d这个矩阵,就需要用到D空间的维度,维度越大越难求解,这里就是瓶颈。

 
 

怎么做?

 
 

求解 Q_d 对于Z空间来说是做内积,但是如果从x空间的角度,其实是两个步骤。步骤是先把x做转换,再做内积,每一步都和维度相关。我们能不能把这两个步骤合起来算得快一些?

 
 


 
 

先考虑一个简单的例子:二次的多项式转换

 
 

使得有 0次项,1次项,2次项,x1x2,x2x1同时存在;

这样转换了再做内积,如上面的推导,就会得到只和 x * x’ 内积的结果。

可以将运算复杂度降低到了O(d)!

 
 


 
 

Kernel function: 转换操作 + 内积操作

 
 

上面的例子所对应的 kernel function 表示为黄底所示部分。

 
 

接下来我们来看SVM里面怎么使用kernel function:

  1. SVM用到内积的地方首先是 二次项系数q,是Z空间里面的内积,可以换成x的kernel function求解。
  2. svm里面算出了alpha以后需要再求得b,w,算出alpha之后通过挑一个support vector来求得b,这里有 w * Z 的内积求解问题,可以转换成Z空间的内积,同样就可以转换成x的kernel function来求解。
  3. 最后得到SVM的结果的这一步,也存在 w * phine 的内积,phine函数就是z,w可以转化成z相关,这样同样可以转换成x的kernel function来求解。

 
 

也就是说没有任何一个时刻真的在z空间做,所有的运算都是在x空间完成,就不会受到空间维度d的影响了,就会很有效率。

 
 


 
 

Kernel SVM 的表示(就是原来的z的内积全部替换为kernel function):

  1. 算Q的时候全部换成Kernel function来求解
  2. 同样的求解alpha
  3. 再算b的时候也是使用kernel function来求解,这里只需要一个support vector就能得到b。
  4. 最后预测函数的表达式求解的时候也是使用kernel function来求解

 
 

时间复杂度:

1的是 算kernel的力气 * N平方

2的是 QP 只有N个变数,N+1个条件

3、4的是 O(SV)

 
 

Kernel SVM 就和空间维度d没有关系了,而且和原来一样,只需要support vector就可以对未来做预测。

 
 


 
 

练习

 
 


 
 

对于二次多项式来说,有些很容易写出 kernel function,有些就比较难,下面介绍一些常用的二次多项式转换。

 
 

蓝色的是原来的,在这基础上做一些些放缩,比如*根号2,对应的kernel函数的一次项前面就会有一个2,如上面红色的公式,再复杂如绿色phine标识的那样。

 
 

整理起来,这里讲的是二次项转换中一次项系数的扩展的方法。这里的变化都是相同的空间内的(power),不同的形式(内积,geometry特性,不同的边界)

 
 


 
 

不同的转换对应到不同的几何定义,不同的距离。

 
 

上面三幅图就是不同的一次项系数对应到的边界变化。相对来说你比较难比较哪个比较好,这里想给大家建立的概念是,换掉kernel,就可能会得到不一样的解。

所以我们要对kernel做选择,才能有比较好的分类结果的表现。

 
 



从二次出发,还能一路推导下去,这里对常数部分做手脚加上theta,然后你能考虑q次方。

 
 

grama:控制一次项系数;

theta:控制常数项;

Q:控制次方。

 
 

这样以后,你做高次转换的复杂度和维度无关,计算也就很简单,只要能把kernel计算出来。

右边的图就是10次方做出来的图,虽然特别高次方,但是边界还算简单,large-margin相对来说可以帮你控制overfitting。

 
 

Polynomail SVM 就是 Polynomial Kernel 配合 SVM 来使用。

 
 


 
 

如果我们回到一次转换,也可以做,通常叫做linear kernel。

 
 

Linear 是值得你最先尝试的一种方式!

 
 


 
 

练习

 
 


 
 

如果我们可以用kernel有效率的解决高纬度空间的运算的话,那么对于无限多维的转换是不是也能解决?

 
 

特例:

原始资料只有一个维度,考虑一个特别的函数如上面所示的高斯函数

经过一翻推导你会发现最终也是一个x函数phine(x)的内积,而且是无限多维的高斯函数。

 
 


 
 

这是后来考虑G_SVM,是一堆中心在support vector上面的高斯函数的线性组合。

所以也被叫做 Radial Basis Function(RBF) kernel

 
 

Gaussian SVM:使用高斯函数来做kernel的SVM,意思是把x映射到无限多维的空间里面,在这里面找出一个最胖的分割情况。

 
 


 
 

通过 kernel SVM 可以有效率的做到 large-margin + hyperplanes + transform。

 
 

不再去算Z,直接用kernel替代;

不再存储W,只存w的表现方式support vector和alpha;

 
 

现在还可以做无限多维度的SVM,比如通过Gaussian kernel实现的 Gaussian SVM,large-margin在这些过程中提供不overfitting的保障。

 
 


 
 

真的那么美好么?

 
 

举一个gaussian kernel的例子,不同的gaussian kernel得到的结果如上面三幅图。

参数不合理还是会overfit,还是要慎重选择kernel!Gaussian SVM里面不建议使用太大的garma,garma越大fit越强烈。

 
 


 
 

练习

 
 


 
 

我们接下来分析一下各种kernel的好坏处:

 
 

  1. Linear Kernel

其实就是把原始的内积丢进去就好,各种求解方式的效率差很小。

好处是最简单最安全最优先尝试的方法;不牵扯到特别转换,所以可以设计特别的QP solver,计算得更快;对于人来说可以很容易的看出来到底怎么去做分类。

坏处是有限制的,如果data不具有线性则没有办法做

 
 


 
 

  1. Polynomial kernel

有限情况下的kernel。

好处是比linear更加宽松,高次解决了非线性data不能处理的限制;可以通过对Q的设定来表达你对这个模型的想象。

坏处是你要算kernel的值的时候比较困难,Q越大越难求解;参数多而且需要你去选择,比较困难。

 
 


 
 

  1. Gaussian Kernel

无限情况下的kernel。

好处是表达能力是无限的,因为是无限多维的转换;比起polynormial来说数值求解的难度比较低;只有一个参数garma所以比较容易选择。

缺点是无限多维度的转换,不直观;比起linear来说计算相对比较慢;能力太强可能会overfitting。

 
 


 
 

  1. 其他的kernel

kernel代表的是x和x’转换以后在z空间的相似性(内积表示的就是一种相似性)。

那么从相似性来考虑采用什么样的kernel?

不见得可以,因为kernel是一种相似性,一种向量的内积在Z空间的相似性。

如果你要用自己的kernel的话,要注意的是你要想办法证明它到底为什么是个kernel。

 
 

kernel的充分必要条件:

对称,从矩阵角度看kernel矩阵是两个z矩阵相乘,也就是说kernel矩阵是半正定的。

 
 


 
 

练习

 
 


 
 

总结: kernel SVM

首先讲了把原来的dual SVM的转换和内积的两步合并为Kernel,通过这样回避了原来SVM计算涉及到的对空间维度的依赖,然后讲了多项式kernel和Gaussian kernel,最后对这些kernel做了简单的比较,如果想要的是效率的话往linear走,想要复杂边界的话往高纬度走。

 
 

下一讲:如何避免高纬度SVM(Gaussian SVM)的overfitting

Machine Learning Techniques Lecture 2: Dual Support Vector Machine

 
 


 
 

内容:dual(对偶) support vector machine

 
 

告诉大家一个新的SVM问题:SVM的对偶问题。对偶问题的出发点是希望移除维度d对于non-linear SVM运算的影响,然后推导出透过 KKT 条件就可以得到对偶的SVM,KKT条件可以转化为QP形式来求解对偶SVM,但最好需要根据SVM来优化QP的运算过程。解的结果你会发现那些活下来的alpha>0的点有重要意义,就是support vector,就这些直接决定了最胖的分隔线。

 
 

 
 


 
 

回顾:linear SVM

可以通过QP求解得到比较robust的分隔线

 
 

今天把linear SVM转成另外一种形式以便更加容易的应用到不同的领域。

 
 


 
 

复习一下上一次上的内容:

 
 

求解:

可以通过二次规划来解SVM,应用于多维的话就是把x转换成Z空间即可,就是对z的线性二次规划求解,这对于x来说就是非线性的SVM。

 
 

作用:

控制模型的复杂度的同时,透过特征转换降低Ein。

 
 

我们Z空间的维度d越大,相对来说求解的难度就越高。

那么如果d无限大的话,还能不能求解。

 
 

因此我们的目标是移除 d 对于SVM求解的影响。

 
 


 
 

原来的VSM:d+1 个变量,N个限制条件

目标(看作是dual)的SVM:只会有N个变数,N+1个限制条件

 
 

这样变数的数量就不会和特征转换的维度增加而增加。

 
 

这里的数学很复杂!涉及到很多深入的最佳化理论,因此这里只讲有助于了解SVM特性的重点,其他就略过了

 
 


 
 

regularization时候的思路:

原来做 regularization 要解决的是有条件的最佳化问题,这个不好解,我们则把这个条件塞到最小化的公式里面,把问题转化为没有条件的公式的最佳化问题。

 
 

工具:

lagrange multipliers – 把条件乘上一定的系数加到目标函数里面去的东西

regularization里面原来每个条件都带一个参数C表示的是我们的w最长可以是多长,他会对应到一个lamda,这个lamda通过最佳解(梯度要往一个方向走但是已经无路可走了,这时候就是最佳解)要满足的条件来得到。

这时候呢,使用者只需要提供lamda而不是原来的C就可以求解问题了。

 
 

这里同样要使用 lagrange multipliers 来求解这里的 有条件的最佳化问题。但是这里的使用方式会比较不一样,这里会直接把 lagrange multipliers 当作是变数,而不是使用者直接给我们的已知量,然后去求解。

 
 

总结:

SVM 里面的每一个条件对应到一个 lagrange multiplier,然后把它当作是变数,去求解和这个变数有关的最佳化问题,这个问题其实最后就是对偶问题。

SVM 里面有 N 个条件,所以就有N个lagrange multiplier,就是有这么多变数。

 
 


 
 

做法:

Lagrange multipliers 在regularization里面叫lamda,但是这里通常用alpha表示。

原来的有条件问题可以写成一个看似没有条件的问题,上面绿框所示,包含红色部分表示原来想要的最佳化的目标,再加上蓝色部分所有的条件乘上其对应的alpha。整个定义为 lagrange function (L(b,w,alpha)表示)。

 
 

SVM 就可以转化成一个看起来没有条件的最小化问题了,黄框所示。

SVM 等式的含义是:每一个b,w的时候我都能算出一个值,这个值是把所有的alpha作为变量得到的最大的lagrange function的值,SVM要获得的就是所有b,w的对应的值的最小值。

证明:

任意的b,w:算分数的过程可能是好的(符合原来的那些限制条件),可能是坏的(不符合原来的那些限制条件至少一条),

  1. 坏的的情况下这个分数会是无限大(原来的有一条蓝色部分大于1,所以lapha越大的结果就是无限大)。
  2. 好的情况下条件这部分这个分数会是0,因此结果就只有原来式子中红色部分的结果(蓝色部分小于1,所以alpha越小越好趋近于0)

所以通过最小化b,w的值就可以淘汰掉那些原来的不符合条件的b,w。

 
 

至此,原来的SVM就转化成了一个看似没有条件的式子来求解。

 
 


 
 

练习

 
 


 
 

灰色公式:

 
 

现在有了一个新的问题:

有了一个lagrange函数,先对alpha做最佳化的动作,然后再对b,w做最小化的动作。

 
 

特性:

如果今天只考虑一个固定的alpha’,这个alpha’的最大值会比任意的最大值小,所以有了式子中的大于等于符号,有了右边部分去掉了max的式子。

任意的alpha’都有此等式,所以先做minb,w以后再考虑取最大的alpha’也是满足的,因此就有了蓝色底的公式。

 
 

像上面一样对掉了最佳化的过程的问题叫做 lagrange dual problem

 
 

对调关系还存在一个大于等于关系,也就是说如果我们解决了这个对偶问题,这个解就是没有对调前的式子的下限解。

 
 


 
 

>= : 叫做 weak duality(弱对偶关系)

= :叫做strong duality(强对偶关系)

  1. 问题是凸的
  2. 问题是有解的,原来的条件没有限制到说找不到任何的解
  3. 条件是线性的

    满足这三点叫做constraint qualification,强对偶关系,可以直接解右边的问题来当作左边的问题的解。也就是说存在一组b,w,alpha的组合对于左边来说是最好的,最右边来说也是最好的。

 
 


 
 

求解右边的问题:

  1. 里面的min部分是没有条件最佳化问题,那么就是求梯度是0的地方,谷底就是最佳解。先来对b微分就得到上面蓝色部分第一点的式子。

    上一步得到的一个等于0的式子代入,原来式子各个+0,则可以把b化简掉,没有b了。

 
 


 
 

  1. 同样的方式来对于w求偏微分得到一个=0的式子,同样的方式加入到原来的式子,可以将原来的式子消掉w,所以得到的式子就只剩下alpha了。所以minimize这一个步骤被化简掉了。

 
 


 
 

剩下一个只有alpha的问题,就是lagrange对偶问题的简化版。

 
 

结论:

如果是强对偶关系的话,需要满足下面的条件(KKT conditions):

  1. 满足原来问题的条件
  2. 满足对偶问题的条件
  3. 满足微分以后产生的条件
  4. Alpha * 里面部分原来的条件要等于0,也就是说这个式子的两部分至少一部分等于0

 
 

下面就是用这些条件来求解最佳的b,w,alpha

 
 


 
 

练习

 
 


 
 

上一步就得到了对偶问题的简化版,这里首先将其转化成我们常看到的SVM的对偶问题,会有一些些小小的变化:

将最大化变成最小化操作,通过取负号保证正的,然后通过导数来做到。

条件部分只是写法不一样,没变化,一共N+1个条件,w的条件用不着了(隐藏了),这里只需要专心求解alpha。

目标函数的二次式做了个展开的动作

 
 

至此得到了SVM的QP问题,而后就继续求解QP(二次规划)问题。

 
 


 
 

求解QP问题,代入模版。

 
 


 
 

SVM对偶问题的Q取名为 Q_d,d代表对偶的意思。

至此我们就可以解出来了,但是这个求解过程真的有那么容易么,我们来看看这个Q_d有多大。

 
 

Q_d:

每一格的内容是: y_n * y_m * z_n * z_m 相乘,一般不会是0。

如果是3000笔资料,其存储量差不多会是3G的大小

需要特殊处理:不存整个Q,而是用到再算,或者是使用特殊的条件来加速求解

也就是说需要用特别为SVM设计的二次规划来求解,不然的话计算会特别慢。

 
 


 
 

上面因此就可以得到中间产物alpha,然后我们怎么来得到b,w呢

 
 

使用KKT条件由最好的alpha来得到最好的b,w。

  1. w和alpha的关系就一个条件而已,直接解得。
  2. 两个条件和b有关,alpha大于0的时候最后一条后面的部分必须等于0,则可以求解得到b。(这里后半部分等于0可以得到那个点就是在胖胖的边界上,也就是support vector)

 
 


 
 

练习

 
 


 
 

Support Vector:就是在胖胖的分界线边界的那些点,这些是我们所需要的,其他的则是不需要的。【SV candidate】

求解SVM得到说:如果alpha>0的话,这个点一定在胖胖的边界上。【SV positive】

所以:我们将alpha_n>0的这些点叫做 support vector(SV positive)。

SV positive 可能会比原来我们所定义的 SV candidate 少一些,也可能一样多。

 
 

SV 重要性:

由原来w的求解公示可以看到W 是 alpha的线性组合,也就是说alpha=0就不需要计算。也就是说求解w只需要用到alpha>0的值。

同样你会发现求解b的时候使用的也是alpha>0的点。

也就是说w,b都是只靠support vector来求解得到的,所以和SV的定义相一致。

 
 

SV 就直接可以区分资料对结果是有用的还是无用的。

 
 


 
 

SVM里面的W表示成alpha相关的公式:alpha是对偶解

PLA里面也有相似的定义:beta表示的是犯错几次

 
 

两者w都是原始资料的线性组合

不完全是偶然,一般来说你做gradient decent这些演算法,和PLA一样从0出发,你也会得到类似的式子,这样的结果叫做:最佳的w可以被我们的资料 represent。

 
 

SVM特别的是:只需要资料里面的support vector就可以表示出来。

PLA特别的是:只需要用资料里面的犯错的点表示出来。

 
 


 
 

总结来说,从上一讲到这一共介绍了SVm的两种表示方式:

 
 

第一种是原始的(Primal SVM):让w越小越好,有一堆的条件限制;变数的数量和哪一个空间有关,空间维度越高越难求解;原来是通过对b,w的特别的放缩来得到最佳解。

第二种是对偶的(Dual SVM):切换到alpha空间去求解;问题的大小和资料的数量有关,资料量越大越难求解;通过最佳化求解得到support vector和对应的alpha,用这些来得到b,w最佳解。

都是得到最佳的b,w来创建SVM的式子来分类。

 
 


 
 

我们做完了没有?

 
 

我们想要求解SVM但是不想要碰d,因为d可能是很大很大。

然后这里讲的新的推导看起来只和N有关,和D无关,但真的是这样么?

D藏到了计算Q矩阵的地方,计算Q_n,m的内积,d越大越难以求解。

 
 

所以我们要想办法避开Q里面的D相关运算,这是下一讲的内容。

 
 


 
 

练习

 
 


 
 

总结:

告诉大家一个新的SVM问题:SVM的对偶问题。对偶问题的出发点是希望移除维度d对于non-linear SVM运算的影响,然后推导出透过 KKT 条件就可以得到对偶的SVM,KKT条件可以转化为QP形式来求解对偶SVM,但最好需要根据SVM来优化QP的运算过程。解的结果你会发现那些活下来的alpha>0的点有重要意义,就是support vector,就这些直接决定了最胖的分隔线。

 
 

下一讲:

移除 Q 对 D 的依赖。

Machine Learning Techniques Lecture 1: Linear Support Vector Machine


 
 

这里讲的是 linear support vector machine

 
 

我们的出发点是想要找那个比较胖的分隔线,更加兼容测量错误,然后把问题公式化以后开始简化他直到得到一个二次规划的标准问题,然后就可以求解了,这就是一个完整的方法。然后我们再回头来看这个方法的理论保障是减少了有效的Dvc,这样就可以做得更好,这就是SVM。

 
 


 
 

课程基本信息。

 
 

Coursera 前8周是基石课程,后面8周是技法课程。

华语授课,投影片授课。

 
 


 
 

与机器学习基石的课程的异同点:

一样的是:哲学的讨论,理论分析,算法和实现,笑话。

不一样的是:把基石课程提到的基本理论工具延伸成为实用的学习模型,围绕在一个主要的点就是特征转换上面:

  1. 有大量的特征转换怎么运用,如何控制复杂度 – SVM
  2. 找出一些比较具有预测性质的特征以及混合应用 – AdaBoost
  3. 学习资料的一些隐藏特征 – Deep Learning

 
 

通过往这三个方向的学习来使得你能够专业的使用相关工具。

 
 


 
 

练习。

 
 


 
 

第一讲:线性支持向量机

 
 


 
 

先来看看之前讲过的 linear classification,他做的事情就是如图所示,通过画一条直线来区分圈圈叉叉。数学上的意义就是资料拿过来算一个分数,看分数的值是正的还是负的来决定其是圈圈还是叉叉。

 
 


 
 

PLA 是以前课程讲过的算法,在确定存在线的时候,此方法可以帮助我们找出这条线。

 
 

但是如上图所示,如果资料给定,有可能不会只存在一条线可以区分这些资料。问题是,从上面三幅图,哪一条线来区分圈圈叉叉比较好?

 
 

PLA 算法会选择的是随机一条线。

VC Bound 理论上看,上面三条线是一样好的。

而你是不是会选择最右边的线是比较好的吧,为什么?

 
 


 
 

简单的解释:

假设我们已经得到原始资料xn,未来我们用到的资料是和原始资料相近的一些资料,因为存在误差不可能是完全一样的,那么上面的三条线对相近的容错能力就是在能区分的情况下每个原始资料对的点所能画的圆圈的最大半径,就如上图所示,第三张图的线对于圆圈的容错能力最好,所以的三条线比较好。

 
 

也就是说每一个点离得线越远,那么能容忍的测量误差越大,反过来说就是找出一条线,离每一个点越远越好。

More robust:离最近的训练资料的距离来判断。

 
 

 
 


 
 

从线的角度看就是如下面三图:看线能长的多胖,越胖的线越robust。

 
 


 
 

也就是原来的问题可以变为一个最佳化的问题:找出一条最胖的线满足可以很好的分开所有的圈圈叉叉。

胖的定义:算一下线到每一个点的距离,取两边最小的。

 
 

下面要做的事情就是把这个最佳化问题变成可以数学求解的最佳化问题。

 
 


 
 

margin:线的边界,就是学术上线有多胖的说词。

 
 


 
 

练习

 
 


 
 

上面的最佳化问题里面有一个重要问题:找出的这条线你需要去看一下他和每一个点的距离是多远,取最小的距离。

 
 

探讨距离的运算:

 
 

分开w0和其他的wi,w0单独处理,w0取名为b,就是截距的意思。

所以公示里面的部分包括了 W^T*X + b

 
 


 
 

所以我们要算的是:一个用b,w表示的平面到一个点x的距离

 
 

假设我们已经有一个平面在手上,考虑平面上的两个点:x’和x”

因为都在平面上,所以有:w * x’ +b = 0, w * x” + b = 0

所以有上面的标号1的结论,然后两个相减,就得到标号2的结果。

x” – x’ 表示的是平面上的向量,w 与平面上任意的 (x” – x’) 向量都等于0,也就是说 w 垂直于平面,也就是说 w 是平面的法向量。

有了法向量任意一点x到平面的距离就比较好求解了。也就是说标号3所示:将(x-x’)向量投影到垂直于平面的方向w。

所以结果就是黄色所示公式:线性代数里面的投影距离公式。

然后做一下化简你会发现:就是 绝对值(W^t * x + b) / 绝对值 w 【这里只是除以w的长度,所以上面要把b分出来的原因】

 
 


 
 

因此有了点到一条线的距离,但是我们需要的是点到分隔线的距离。

 
 

分隔线的性质:我们要的分数(W^T * Xn + b)和结果(yn)是同号的。因此上面的距离公式的绝对值可以化简掉。

 
 


 
 

至此得到的新的式子,但还是不会解。

 
 

世界上其实没有那么多条线,也就是说同一条线能用不同的方程式来表示,例如蓝色框框的第一点所述,也就是说线的系数可以放缩。

所以我们可以用特殊放缩使得式子更简单。

蓝色框框第二点所述,那部分最小的话刚好等于1,则margin就可以表示为 1/w长度。

所以可以把 margin 换掉为 1/||w||,但是要求yxb相关部分要取最小值1.这个条件就包含了原来的要求yxb相关部分要大于0。

 
 


 
 

所以得到了上面的黄色狂所述的简洁的表示,还是不会解,因为最大化的问题里面还包含一个最小化的问题。

 
 

所以考虑放松一下条件,看能不能化简求解。但是我们首先要证明的是,就算我们把条件放松,最后的到的解还是落在原来的区域。

 
 

条件放松为 大于等于1,而不是等于1.

反证法:如果放松后最佳解落在外面(min yxb 部分最小的大于1),例如大于1.126,那么bw都除以1.126的结果比bw更好,这就矛盾了,所以可以证明:即使条件放宽到大于等一1,也会有不落在外面的结果。

 
 

所以原来的公式可以放松得到第二个黄色框所示,大大的简化了原来的问题。

这里还做了两个变化:最大化变成了最小化,求导,去掉根号部分,加上1/2。

 
 


 
 

练习

 
 


 
 

因此接下来我们要求解的是黄色框所示公式。

 
 

先举例一个特殊的例子,蓝色框所示,四个点就有四个条件,目标是最小化 W^t * W。

1式和3式 得到 W1 >= 1

2式和3式 得到 W2<=-1

所以就有了 W^T * W >= 1

所以就得到最终解了。

 
 

SVM 就冒出来了。

 
 


 
 

最胖的线就一定会有几个点离他最近。

如果我们去掉除这些最近点以外的点,在去找分隔线,会得到一样的结果。

也就是说这条分隔线就是由这些最近点决定的,其他点都不重要。

 
 

也就是说原来的资料可以看作两种:

一部分资料:告诉我们分隔线在哪 – support vector

另一部分资料:不需要

 
 

Support vector machine:可以看作一种找出最胖平面的方法,就是考虑分隔线最边边的点,就是上面的图示所标识的方法。

 
 


 
 

上面是解特例,那么通用解怎么解。

 
 

坏消息:不容易

好消息:目标最小化的是二次函数,条件是b,w的一次式,也就是二次规划(quadratic programming)的问题【线性规划进阶版】。数学上是可以求解的。

 
 

所以下一步:把问题变成二次规划的一般形式,然后使用已有的数学工具求解。

 
 


 
 

左边是目前的公式形式。

右边是二次规划的标准型。最小化u向量的二次函数,二次项系数Q,一次项系数P,条件是U向量的一次式,条件有M个,一次项系数A,常数项c。

 
 

因此我们要把这些系数向量提出来,如红色部分。Q里面与w有关的系数用I矩阵表示,其他都为0。P就是0向量。

 
 

直接使用matlab解QP问题。

 
 


 
 

因此这里就得到了一个新的演算法(linear hard-margin svm altorithm):

  1. 算系数
  2. 二次规划求解
  3. 得到的就是最胖的分隔线

 
 

Hard-margin:坚持圈圈叉叉一定是要完全分开的,不能有犯错误。

linear:使用直线分

 
 

如果你要非线性的,那就是把x做一个转换,基石里面有类似的方法来说明从直线到曲线的变化转换,此处类似。

 
 


 
 

练习

 
 


 
 

此处黄色公式用z代替x表示的就是非线性,在z空间做SVM。

 
 

此处我们再从理论上来解释为什么SVm可以得到好的结果。

 
 

与 regularization 比较,有趣的是条件和优化对调了:

Regularization:Ein 越小越好,条件是 W^T * W <= C 为的是不 overfit

SVM: W^T * W 越小越好,条件是 Ein = 0,就是上面那句话反着说

 
 

因此:SVM可以看作是一种 weight-decay 的 regularization。

 
 


 
 

另外一种解释:

 
 

Dvc:解决的是我想要知道我的线到底能产生多少种圈圈叉叉的排列组合。

 
 

现在考虑:

如果我今天喜欢的是胖的线,定一个胖的标准,如果资料拿来能找到达标的胖的线就是好的结果,找不到足够胖的线就没有结果

那么同样考虑在一组特定的资料上,到底能够找出多少足够胖的区分圈圈叉叉的组合

 
 

举例:

不计较胖瘦,绿色图示,三个点八种情况,都能分开。

计较胖瘦,红色图示,线的粗度要超过1.126,那么三个点,八种情况下都不一定能分开(具体和数据点相关)。

 
 

Dvc 有你能够做出几种情况来决定,情况越少复杂度越低。因此线越粗,有效的Dvc就可能越低,就是越好的分类。

 
 


 
 

我们考虑线的胖度来算演算法的Dvc,就看其最多最多能shatter多少个点。

(演算法的Dvc是没有绝对定义的,其结果与实际拿到的资料有关)

 
 

shatter的意思就是所有圈圈叉叉的排列组合。

 
 

如图平面上有三个点,在一个单位圆的边上。

如果不在乎分隔线的胖瘦,区分这三个点的所有排列组合都能做出来,Dvc就是3。

如果线要有 (根号3)/2 那么胖,那么圆上任意三点你做不到所有情况都产生出来(存在两个差异点之间的距离小于根号3就不能产生出区分情况),所以 Dvc 小于3。

 
 

数学上证明结论如上面公式,其Dvc与两个事情相关:资料的空间大小R,你容许的胖的程度p。

就是说:透过设定胖瘦条件,真的可以降低Dvc,所以理论上SVM就是一种控制复杂度的方式。

 
 


 
 

一开始我们喜欢 hyperplanes 的原因是它的有效数量不是很多,Dvc比较小,可以有效控制复杂度,但是呢太简单的平面不一定能把事情做好。 – not many

反过来我们考虑更复杂的平面,通过feature transform来实现,虽然可以处理很复杂的情况了,但是数量就变多了,Dvc就变得很大。- sophisticated(复杂)

原来只能二选一。

 
 

这里我们讲了一个新的概念 large-margin ,就是要胖的 hyperplanes,作用是控制数量,Dvc变比较小。

 
 

Large-margin hyperplanes + feature transform

可以做到的是,降低Dvc,但同时还能透过transform得到复杂的boundary。- not many & sophisticated

 
 

SVM 的好处:有了一种新的控制复杂度的方法,这样就可以尽情的采用各式各样不同的 feature transform。

 
 


 
 

练习

 
 


 
 

总结:

这里讲的是 linear support vector machine

我们的出发点是想要找那个比较胖的分隔线,更加兼容测量错误,然后把问题公式化以后开始简化他直到得到一个二次规划的标准问题,然后就可以求解了,这就是一个完整的方法。然后我们再回头来看这个方法的理论保障是减少了有效的Dvc,这样就可以做得更好,这就是SVM。

 
 

下一讲

我们开始讲将SVM的复杂度控制配合非线性的转换,看可以做到什么事情。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 16: Three Learning Principles


 
 

总结:

Occam’s Razer: 简单是好的

Sampling Bias: 小心抽样的偏差

Data Snooping: 小心不要偷看资料

 
 


 
 

上一节:

很重要的工具 validation,留下一定的验证资料来模拟测试程序,来衡量和选择比较好的训练模型。

 
 

这一节:

三个做机器学习时候的精囊妙计。

 
 


 
 

第一个: occam’s razor (occam 的剃刀)

 
 

今天你要对你的资料作解释的话,越简单越好。(爱因斯坦说的?)

不要对一个东西做过多的处理。(William of occam)

 
 

我们不要对资料过分解释。

 
 


 
 

举例:

两张图,左边的比较简单,比较好。

 
 

问题是:

什么样叫做简单的解释?

为什么简单的比较好?

 
 


 
 

什么是简单的?

 
 

简单的 hypothesis:

看起来很简单(就像上面大大的圆)表示只需要少出参数就能描述。

 
 

简单的 model:

有效的 hypothesis 不是很多的话就是简单的,Dvc 很小。

 
 

关联性:

Hypothesis set 有 2^L 次方个 h,那么一个 h 有L个参数来描述。

所以整个hypothesis set 数量不多的话,单个h也相对简单。

 
 

所以只要得到上面的两者之一简单,那么就可以说资料是简单的。

 
 


 
 

为什么简单是好的?

 
 

直觉的解释:

想象你有一个简单的model,也就是成长函数很小,成长很慢的。

成长函数很小意味着:给随机的数据,只有很小的机会模型的Ein会很小;给非随机的数据,模型的Ein会很小。

如果是复杂的模型,不管给什么样的资料统统都可以分开,那就不知道这个资料到底是不是具有显著性了。

 
 

所以一般都从线性模型开始考虑,使用了模型以后一定要思考一下还有没有更简单的来做。

 
 


 
 

小测验

 
 


 
 

1948 年的总统选举电话民调,根据民调结果说 deway defeats truman。

 
 


 
 

结果是 Truman(杜鲁门) 赢了。

 
 

为什么?

编辑搞错 – 不是

运气不好 – 不是

 
 

提示:电话当时是很贵的,所以抽样的是有钱人。

 
 


 
 

第二个:Sampling Bias

 
 

抽样有偏差的时候,学习的结果也是有偏差的。

 
 

训练和测试要在同样的分布下做。

 
 


 
 

经验;

Netflix 办的一个比赛,比原来的好10%就可以获得100万美金;

老师第一次尝试采用标准的随机 Dval 的结果就好了 13%;

但是没有拿到奖金。

 
 

为什么?

比赛的测试环境:前7部电影用来训练,后3部电影用来测试,测试的资料具有时间关系,不是随机取样。

所以 随机取样的Dval 和 具有时间关系的 Dtest 是不一样的。

 
 


 
 

怎么办?

 
 

了解你的测试环境,让你的训练环境和你的测试环境尽可能的接近。

 
 

上个例子:

可以是:后面的资料权重比较多。

也可以是:不随机的验证资料,而是已有资料的比较靠后的资料来做验证资料。

 
 

回到我们所讲的第一个机器学习的问题:银行发卡,问题在哪?

银行已有的资料都是已经经过筛选的发了卡片的客户的资料,而排除了那些没有资格获得卡片的用户的资料,这两者是有区别的。

 
 


 
 

小测验

 
 


 
 

用眼睛看资料,用人脑学很危险。

 
 

第三个: visual data snooping(不要偷看资料)

 
 


 
 

不仅仅是用眼睛偷看图

在使用资料的任何一个过程都是在偷看资料,脑袋里的任何决策都是污染了 model complexity。

 
 

例如:

有8年的训练资料来预测未来两年的走势。

比如:用前面六年做训练,后两年做验证,是蓝色的线;如果偷用8年的数据来做训练,后两年的再做验证,结果就是红色的线。乍一看红线投资报酬率非常高,但是那是不可信的。

 
 

偷看是自欺欺人的做法。

 
 


 
 

其他偷看的例子:研究的例子,一篇比一篇好

 
 

后面的论文是在前面的论文的测试结果的好坏基础上再继续做的,可以看作是间接的偷看了测试资料的表现特征。所以越后面的论文越容易被污染。

 
 


 
 

所以:你要仔细的去考虑偷看这件事情。

 
 

做法:

要么完全不偷看

做 validation

避免用资料做决定,比如做语音的,先考虑语音的特性建模再输入资料,不要去看了一遍资料再来建模处理问题。

时时刻刻存着怀疑,时时刻刻考虑污染的问题。

 
 

能在 KDDCup 表现那么好,诀窍:

非常小心的平衡两件事情:data-driven modeling(snooping) & validation()。

也就是说靠 validation 而不是 snooping 来做合理的选择。

 
 


 
 

小测验

 
 


 
 

总结课程(3的魅力):

 
 

  1. 介绍了3个和机器学习相关的领域

Data mining:数据挖掘,和ML高度相关

Artificial Intelligence:人工智能,ML是实现Ai的一个方法

Statistics:统计学,ML使用了大量的统计工具

 
 


 
 

  1. 3个理论上的保障

 
 

Hoeffding:抽样的动作,用在测试。测试的时候只有一个 hypothesis,hoeffding告诉你怎样一个结果保障。

Multi-Bin Hoeffding:很多个选择的 hoeffding,validation/model selection 的时候,有限多个选择的时候用,告诉你对结果的限制。

VC:无限多的选择的时候用,描述机器学习在训练的时候的保证。

 
 


 
 

  1. 三个线性模型

 
 

PLA/Pocket:采用01错误,flipping noise 越小越好

Linear regression:线性回归,采用平方错误,公式解

Logistic regression:把分数透过一个s型的函数再输出出去,梯度下降求解

 
 


 
 

  1. 三个很重要的工具

 
 

Feature Transform:扩大维度使得Ein变小,代价是Dvc变大

Regularization:让Dvc变小,代价是维度变小Ein变大

Validation:留下一块干净的资料来做validation,选择比较少,代价是train用的数据变少了

 
 


 
 

  1. 三个锦囊妙计

 
 

Occam’s Razer: 简单是好的

Sampling Bias: 小心抽样的偏差

Data Snooping: 小心不要偷看资料

 
 


 
 

  1. 三个未来的学习方向

 
 

More Transform:更多的数据转换方式

More Regularization:更进阶的regularzation

Less Label:更少的label,unsupervised怎么弄

 
 

大量的名词

 
 


 
 

小测验

 
 


 
 

总结:

Occam’s Razer: 简单是好的

Sampling Bias: 小心抽样的偏差

Data Snooping: 小心不要偷看资料

 
 

下一课程:机器学习技法

 
 

 
 

 
 

 
 

Machine Learning Foundations 15: Validation


 
 

总结:Validation(验证)

从要选择一个好的模型来做切入:如果用 Ein 做选择是很危险的,但是你没有办法用 Etest 来做选择,我们用 Validation来做选择,我们做了相应的理论证明。

再讲 leave one out cross validation:假设validation最小达到1,然后做很多次取平均结果,理论上结果会比较好,但是这要花很大的计算上的时间。

实际上 leave one out vross validation没有那么可行,常用的是 v-fond cross validation,就是切5/10份就可以。

 
 


 
 

Validation (验证)

 
 

上一次讲到避免 overfitting 的一种方式叫做 regularization:在 Ein 上面加上 regularizer 项变成 E_aug,对此做 minimize 的动作,这样可以有效的限制 model complexity。

 
 

面临的问题的是:整个过程当中有很多的选择要做,这里 validation 就是用来帮助你作出合理的选择。

 
 


 
 

即使你要做 binary classification,根据当前所学,你已经可以使用 PLA, pocket, linear regression, logistic regression 等很多种方法。

 
 

这些方法存在的一些需要做选择的地方:迭代次数T,每一步步长n,特征转换sigma,错误衡量regularizer方法omega,regularizer强度lamda,等等。

 
 

你面临那么多的选择,而且组合还是叠加的,那么我们怎么来做选择?

 
 


 
 

我们之前其实就引导大家做过选择了,譬如光看着两个图的话,你会选择几次曲线?但是以前没有系统的来阐述这个问题。

 
 

已知:我们有 M 个模型,每个模型由他自己的 hypothiesis set,有他相对应的演算法。

目标:我们希望从 M 个里面选出某一个,然后把资料用在这个模型上面,最后得到的那个 g 会很小,选出来的那个用星号来标识表示最好的 Eout(gm*)。

但是 Eout 不知道,所以不能够直接用 Eout做选择,因此要思考新的方法。

这就是ML里面最重要的问题。

 
 

因此怎么选择?

 
 

肉眼看:

不可以,那是人的学习不是机器学习。

 
 


 
 

选择 Ein 最小的:

 
 

在这样的情况下,你用 1126 维度的phine 一定要比 phine1 好,因为曲线越复杂,Ein可以做到的越小,所以你会去选择高维度的曲线。不加 regularizer一定比加上好,因为加regularizer会导致曲线fit已知信息的能力下降。

这样子会导致 overfitting。

 
 

如果算法1选出h1 的时候Ein最小,算法2选出h2的时候Ein最小。这样整体来看就是要选一个 H1并上H2的hypothiesis set 里面选择最好的,增加了复杂度。(这边的例子莫名其妙,我的理解是各个H都是从整个目标model出来的,而这里最好的是用所有的已知数据的Ein最小,所以才会存在各个H的并集。)

 
 

因此用 Ein 来选择是很危险的。

 
 


 
 

找一串测试的资料,来看看到底哪个模型的表现最好:

 
 

可以得到的保证是 finite-bin hoeffding


以前的课推到过,这样确实可以得到比较好的效果。

 
 

问题是你找得到测试资料么?

 
 


 
 

比较:

 
 

Ein 做决定:只需要已知的资料,拿得到这些资料,但是这些资料决定了H,容易overfitting

Etest 做决定:需要额外的测试资料,但事实上根本没有这些资料,但是这些资料是没被使用过的,不会出问题。

 
 

综合上面两种:

 
 

Eval 做决定:对于所有已有的资料,一部分用于H,留下一部分只用于测试并做选择。

 
 


 
 

小测验

 
 


 
 

从已知的资料里面分出一部分做测试,这部分资料的大小定义为K,叫做验证资料,用来模拟测试资料,验证的时候产生的错误叫做 Eval(验证的错误)

 
 

因为已知的资料就是来自于 目标模型,而Dval就是来自于已知的资料,所以随机从已知资料抽取一部分K作为Dval就可以保证, Dval也来自于目标模型。

 
 

切出来N-k的数据叫做训练资料Dtrain,用于送到模型里面选一个hypothiesis。这里定义为 gm-, 因为相对来说训练资料减少了。

 
 

这里不同的数据用于训练和验证,可以得到的理论保障是:


 
 


 
 

做法过程(右图):

Dtrain 送到演算法里面,得到一群 gm- 以后,然后通过Dtest 来获得各个的验证错误,最后选择验证错误最小的。

 
 

问题是上面讲的都是 g- 而不是 g,一般来说资料量越多能选出的模型越好,因此如果你获得的 gm*- 对应的 Eout 要比 gm* 对应的差一些,就有下面的公式:


(灰色是因为,这没有经过严格证明,但实际上是这样)

 
 

这样我们结合 gm- 的 finite-bin hoeffding,就有上面黄色区域所示的公式。

 
 


 
 

如果将 validation 用在五次/十次多项式的时候的结果 。

 
 

上图横轴是你用的验证资料的数量,纵轴则是Eout,越低越好。

使用 Ein 来做选择是黑色实线,这时候选的总是10次多项式;

使用 Etest 来做选择是黑色虚线,这时候应该总是选最好的,但是你做不到这件事;

使用 Eval 来做选择,但回传 gm- ;

使用 Eval 来做选择,但回传 gm,选择5/10次多项式以后再重新算一个g5/10回传回去用。

 
 

蓝色的线总是比红色的低,验证上面的灰色公式,数据量大了以后总是相对更好。

蓝色的线总是比Ein低,就是说使用 Eval 会比 Ein 好。

红色的线有时候比 Ein 还差,因为 Dtrain 变小了,用了很少的资料算的 Eval 还不一定比 Ein 好。

 
 


 
 

上面告诉我们: 用于 validation 的数据资料的大小是很重要的。

 
 

上面的推论基于:Eout(g), Eout(g-) 够像,Eout(g-),Eval(g-)够像。因为我们是根据 Eval(g-) 做选择,选择 Eout(g) 最小的。

 
 

但是这两个等式对于 K 的大小的要求是不一样的,前面的希望 K 小,后面的希望 K 大。

大的K: 红色的和蓝色的线差很多,

小的K:Eval(g-) 和 Eout(g-) 接近不能确定。

 
 

到底 K 多大合适:一般是资料总数的五分之一。

 
 


 
 

小练习。

 
 


 
 

考虑 K 非常小,等于1.

则 g, g- 非常非常接近;Eval(g-), Eout(g-) 相似就比较难满足了。

 
 


表示留了n笔资料做validation;


表示减掉了n笔资料的g。


看看n笔资料上的错误是多少,标记为en(验证n笔资料的错误)

 
 

如果只一个 en 的话,不能保证他接近于 eout(g),但是如果我们有很多笔 en 的话,是不是可以确定 eout(g) 。

 
 

交叉验证(cross validation):每次留 n 笔数据,做很多次训练和验证,取平均结果。交叉的意思是,同一笔资料,有时候是用于训练,有时候是用于验证。

 
 

Eloocv(H, A):交叉验证的平均结果。

期望的事情是 Eout(g) 接近 Eloocv(H, A)。

 
 


 
 

假设我们有三个点,跑上面的情况,每次留一个验证,得到上面三图;在上面的结果取平均获得 Eloocv(linear)。

假设用常数来分,则有下面三幅图,也有三种情况,同样取平均得到 Eloocv(constant)

 
 

结果你会发现下面结果比较好,也就是说只有三个点这种超级简单情况常数就够用来分类了。

 
 

这就是使用 交叉验证 的方法过程步骤。

 
 



Eloocv 到底能不能告诉我们 Eout(g) 有多好?

大概可以。

 
 

目标:

我们要证明的是 N笔资料的 Eloocv


和 N-1笔资料的 Eout


是一样的。

 
 

过程:

第一步把期望和sum交换,因为两者是线性的;

en有两个部分:训练用的 + 验证用的,en则用其定义替换;

蓝色 sum 部分以及后面的总和 就是 Eout(g-);

红色 sum (Eout(gn-)) 就是 Eout(N-1) 的平均;

N-1笔资料的 Eout 就是 Eout(g-) 的平均值。

 
 

因此上面的证明目标成立。

 
 


 
 

手写辨识的例子的结果。

 
 

横轴表示的是特征维度,纵轴是错误率,蓝色表示使用 Ein 做 validation,红线表示直接使用目标 Eout 来做 validation,黑线就是交叉验证的方式来做的结果,和用 Eout 很接近。

 
 


 
 

小测验

 
 


 
 

接下来看 Eloocv 的问题是什么?

 
 

我有1000个点就要计算 1000次,每次丢999个点训练,一个点验证,非常花时间,而且计算的时候除了有一些有特殊解,其他的计算也很复杂费时。

 
 

用单一个点做衡量,最后用平均的方式消除变动,还是很不容易的,像上面的图的曲线有跳动,因此也不算稳定。

 
 

因为有着两个问题,所以其实在实际上 Eloocv 也不是很常用。

 
 


 
 

实际上需要的是:降低在做交叉验证的时候的计算量。

 
 

Eloocv 切的实在是太细,那么这里我们不要切那么细来做,可以有效减少计算量。

 
 

这样的话也一样获得平均的错误,叫做 Ecv。

 
 

那我们怎么知道要切几份,实际上常用的是切10份。

 
 


 
 

最后讲一下实际上常用的一些 validation 原则:

 
 

通常 cross-validation 要比 single-validation 要来得好,相对比较稳定,但是计算量会比较大。

通常情况下 cross-validation 切5份/10份表现就不错了。

 
 

Validation 带来的不一样的地方:

 
 

训练模型是在大大的 hypothiesis set 里面做选择;validation 则是在有限的train model里面选。

Train 像是初赛,validation像是决赛,最终选出结果。

 
 

因为 validation 还是在做选择,因此其结果还是会比真实的结果乐观(optimistic)一点。

所以 测试的表现 才是你要注意的点,而不是把 validation做到极致。

 
 


 
 

小测验。

 
 


 
 

总结:Validation(验证)

从要选择一个好的模型来做切入:如果用 Ein 做选择是很危险的,但是你没有办法用 Etest 来做选择,我们用 Validation来做选择,我们做了相应的理论证明。

再讲 leave one out cross validation:假设validation最小达到1,然后做很多次取平均结果,理论上结果会比较好,但是这要花很大的计算上的时间。

实际上 leave one out vross validation没有那么可行,常用的是 v-fond cross validation,就是切5/10份就可以。

 
 

下一次:讲一些小秘密

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 14: Regularization


 
 

这里讲的内容:

Regularizer hypothesis set 就是在原来 H 的基础上加上条件,这样以后可以把要解的问题转换成 augmented error 的问题,就是把 W 的平方加进去,这代表了我们会降低 effective 的 Dvc,最后我们说到 regularizer 是一个非常 general 的工具,我们可以设计使用 符合目标函数特性的,能说服自己的,又容易优化求解的 来使用。

 
 


 
 

回顾:

ML里面最大的问题就是overfitting,当有太多的power,存在两种noise,数据量又不够多的时候,overfitting很有可能发生。

 
 

今天讲的 regularization 可以看作是处理 overfitting 的一种方法,我们首先讲数学推倒,然后延伸到各种不同的变化情况。

 
 


 
 

右图是我们上次举例的一种典型的overfitting的情况:资料量不多有noise,用了一个高次方多项式来fit,红色线 Ein 很低,但是 Ein 和 Eout(蓝线,目标)差别很大。

 
 

我们今天要做的就是从这么不好的情况 变成 左图所示的情况:规则化的fit

 
 

我们要怎么做呢?

就是从高次多项式走回到低次多项式的fit。

 
 

下图表示的是 高次hypotheses set包含低次的关系图,我们要做的就是从大圈圈走回小圈圈。

 
 

Ill-posed problems:意思是有很多的函数都满足我们的solution,我们不知道选择哪一个,因此我们需要做一定的限制来帮助做出一个选择,不然的话解太多会有问题。

 
 

在这里 regularzation 就是通过增加限制来解决解太多的问题。

 
 

因此下面举个例子就是怎么样从10次多项式走回到2次的多项式去。

 
 


 
 

我们还是用 高次方转换 和 linear regression 来做例子。这里用 W 来代替 W(上划线) 描述转换后的 weight。

 
 

这样的话,10次和2次 的表示如上面的公式。

10 次有 11个系数,2次有 3个系数,我们可以把2次看作是10次的3-10次项的系数都为0。这就是包含关系的解释。

 
 

10次多项式 走回 2次多项式,就是加上一个条件:3-10次项系数都为0.

 
 

 
 


 
 

也就是说(上面两个框框所讲的事情):

如果要找一个最好的10次多项式来 minimize Ein,就以前讲过的做法。

如果要找一个最好的2次多项式来 minimize Ein,我们还是考虑用10次多项式来做,但是我们加上一个限制条件说 3-10 次方的系数都是0。

 
 

也就是说:

Step back 就是所加的那个条件。

 
 

为什么要这么绕一圈往回走,而不是从低次往高次走?

 
 


 
 

为了赋予更强的范围表示能力,可以把条件放宽松:

从(H2)左边的框框是 11 维空间(H10) + 特定的 3次方及以上的项为0(特定的8个维度为0)

到(H’2)右边的框框是 11 维空间(H10) + 任意的8个维度为0

 
 

两者做比较,对于 H’2:

好消息:H’2 比 H2 条件更宽松,和 H2 一样的计算速度的情况下扩展了包含范围。H’2 比 H10 则紧很多,也就是说不会那么容易的 overfit。

坏消息:约束条件是一个离散算式,最佳化比较困难,是一个被证明的 NP 难题。

 
 

那么怎么办?

 
 


 
 

因此继续做变化:

左边是上面说的不大好解的问题;

右边把条件换掉:算W的大小,W的平方和给一个上限C。

 
 

我考率所有的W,希望所有的W平方加起来 <= C,这样的 hypotheses set 叫做 H(C)。

 
 

H(C) 和 H’2 有一定的 Overlap,HC里面一些属于H’2,H’2里面有一些也会属于HC。

HC 之间也有一定的重叠关系:C越大表示范围越大。

 
 

我们就把 HC 上面的 hypotheses set 叫做 regularized hypothesis set;而这个对应的规则叫做 W_reg。

 
 


 
 

小测验。

 
 


 
 

我们来看看怎么去求解新的这个最佳化问题?

 
 

首先把公式表示成 向量矩阵 的形式,淡蓝色框框表示。

同样条件也用 向量矩阵 表示,在几何上的意义是在一个半径为 根号C 的球里面,我们只考虑在这个球里面的W,找出这个球里最好的W来让Ein最小。

 
 


 
 

因此得到上面黄框表示公式。

 
 

来看看这个条件对于我们的最佳化问题造成了什么影响。

 
 

在没有条件的时候:

就看 目标函数朝着谷底的方向一路滚下去,谷底的方向就是梯度的反方向。

用上面的图表示,譬如在w点的位置,再一路滚下去,则继续向蓝色方向滚动,滚到 Wlin 就是做 linear regression 的 solution。Win表示的就是一个椭圆形,我们要从椭圆的周围一路滚到其中心,中心Ein最小,梯度的方向就是告诉你滚下去的路径。

 
 

有条件的时候:

W要在一个半径为根号C的球里面。

用上面的图表示,红色的球就是限制条件,我们要在球里面的才符合要求。

你可以想象一般情况下最佳解都会出现在球的边界(除非原本的最佳解就在限制条件内),因此我们来考虑如果现在的解已经在球的边边,我们怎么来判断其是否是最佳解?也就是说在符合条件的状况下还能不能往最佳方向滚。

因此目标的滚的方向可以分为 球的表面法向量方向(滚出球的方向,红线)和切线方向(还在球的方向,绿线),切线方向滚是可行的。所以当目前的位置在红色球边界上,且其目标方向(蓝色)和切线垂直,或者说与法向量平行,则就是满足要求的最好的解。

 
 

Linear regression 的理论 Ein/Eout 平均错误是 2 lamda/N

因为有与红线平行的条件,因此最终有上面的黄色表示式子。

 
 


 
 

我们的目标:


 
 

这里既要求解 lamda,又要求解 w,变得复杂了。但是假设告诉你 lamda 是多少,那么就可以有 W_reg 的线性方程式。

 
 

Ein 的梯度里面有 2(Z’Z W – Z’y)/N ,其要等于0.

所以带入上面的公式,就有:


线性方程式求解可以得到:


 
 

这个就是最佳解。

只要 lamda 大于0,lamda相关项反矩阵存在,整个就是可逆的,也就是这个解存在且唯一。这个东西在统计里面叫做 ridge regression。

 
 


 
 

如果今天不是 linear regression 的情况下怎么去求解?

 
 

首先可以反过来看:如果我们今天要解的是


这个问题的最小值,就是要去求解


这两个公式就是 微分/积分 的关系。

 
 

因此新观点:

把有条件的问题的求解 看作是 多带一项的新的问题

整个公式(augumented error)= Ein + regularizer,可以看作是在原来的基础上求解一个新的比较大一点的问题,这个问题里面没有条件限制了。

能解这个问题的条件是 lamda 是多少已知,通常情况下 lamda > 0,设成0的话就是原来的没有做规则化的问题。

 
 

这样做就是把 原来需要已知的参数 C 替换成了 lamda。

给 C:需要求解带限制条件的解,中间过程就包括找出lamda。

给 lamda:看作是解不带限制条件的多一项的新问题,只需要做给C情况下的找到lamda以后的步骤,求解方便了。

 
 


 
 

结果:

四种lamda的值用在最初的例子上。没有lamda会 overfitting,lamda很大的情况红线蓝线也差的比较远,就是underfitting。

可以说你只要加一点点regularzation就可以得到很好的结果。

 
 

Lamda/C 关系:

Lamda 越大,代表你希望的W越短越好,也就是你要比较小的C。

 
 


 
 

细节:上面讲的 regression可以和任何的 transform 做搭配使用,因此为了让结果比较好,在做transform的时候做了一点手脚:

 
 

问题:

使用 polynomial transform 有一定的缺陷:如果X在-1到1之间的话,因为q越大,x的q次方会很小很小,但是其这一项需要很大的影响力的时候,W需要很大。可以说是过度的惩罚了高纬度的项。

 
 

原因:regularization的时候因为各个基本向量不是垂直的,因此会导致不同次方的地方的地方regularization程度不同。

 
 

解决:采用垂直基底(线性代数有这个内容)

下面的五张图表示的是前五个垂直基底。

 
 


 
 

小测验

 
 


 
 

上面已经学了Regularization,我们这里来看看它和 VC Theory 的关系。

 
 

我们最初要求解的是 带限制条件的Ein最小化的问题。

因为 C 与 lamda 的替换关系,可以看作是一个扩展一项的不带限制条件的Ein的求解。

原始的问题对应到 VC Guarantee 可以看作是


 
 

也就是说做 min E_aug 就是间接的把 Dvc 做出来了。

 
 


 
 

比对 Augmented Error 与 VC Bound:

W^t * W 正则化 – 可以看作是 一个 hypothesis 到底有多复杂。

Omega(H) – 可以看作是 整个 hypothesis set 有多复杂。

 
 

因此,一种理解方式:

如果 单一的h复杂度 和 整体的 接近,也许 E_aug 相比较Ein而言,是一个好的 真正的H的Eout 的代理人。

 
 


 
 

H 而言:所有的w都是可选的,理论上 Dvc 的变数就是 d+1(就是H);

实际上,只有HC里面的w可能会出现在谷底,才是需要考虑的;

因此实际上 Dvc 的变数就是 HC 那么多,而不是 H;

也就是说可以定义一个 Dvc_eff:考虑H,同时考虑做选择的方法,得到的等效的 Dvc。

 
 

因此,另外一种理解方式:

理论上的是 Dvc, 但是 Dvc_eff 可以等效替代 Dvc 来用。

 
 


 
 

小测验

 
 


 
 

前面讲到的 regularizer 都集中在 weight-decay,如果今天换更加一般的 regularizer,那么要加上什么样的条件才是好的呢?

 
 

也就是第一个问题,挑W的计算方式。

 
 

最好的:告诉你 target function,但是对ML来说是不可行的。

告诉你好的 target function 在哪个方向,就是给你缩小范围。

 
 

所以好的 regularizer 特点(Regularizer 常用选择方式):

  1. 知道taget的一些特性,用上去。
  2. 选择使用一些可以说服我们的对象,比如用上的 regularizer 可以帮我选出 比较平滑简单的 h(overfitting来源于noise,noise就是不平滑的,target就应该选比较平滑的),比如使用 L1。
  3. 容易做优化的,比如 L2。

 
 

如果你选到不好的,加入lamda=0,就等于是不使用 regularizer,就不会导致结果比原来更差。

 
 

回忆一下第八堂课,错误的衡量有三个可能性:

  1. User 告诉我们她真的想要什么
  2. User不知道,选一个我们能说服我们自己的
  3. 选一个容易 optimize 的

 
 

这就是设计ML的时候很重要的考虑范围:

Augmented error = error(三条意见)+regularizer(三条意见)

 
 


 
 

L2 regularizer : W的平方和

特点:平滑,凸的,可以微分,容易最佳化

 
 

L1 regularizer:所有的W的绝对值加起来

特点:凸的,w=0的地方是不可以微分的,因为有些尖的转角比较难解,解通常是 sparse 的,就是有很多个0,少数是1。

sparse:如图边界的normal一般是一致的,因此最后的解常常发生在顶点上,因此在做预测的时候,使用L1就可以直接去猜测顶点结果使用就行,很快就可以求解。

 
 


 
 

第二个问题:lamda 选多少

 
 

左图表示加入 stochastic noise 的时候,sigma取三个定值的时候,lamda与Eout的关系。颜色的点就是Eout的最小的点。

右图表示加入 deterministic noise 的时候,sigma取三个定值的时候,lamda与Eout的关系。颜色的点就是Eout的最小的点。

 
 

最好的lamda取决于你的noise有多少,noise越高,lamda越大。类比就是 路况越不好,刹车要踩的越重,regularizer就是踩刹车。

 
 

但是你不知道noise是多少,因此你很有可能需要在不同的lamda里面挑一个好的lamda,才能让regularizer发挥作用。

下一堂课就是来讲怎么选择 lamda,phine,linear model。

 
 


 
 

小测验

 
 


 
 

总结:

Regularizer hypothesis set 就是在原来 H 的基础上加上条件,这样以后可以把要解的问题转换成 augmented error 的问题,就是把 W 的平方加进去,这代表了我们会降低 effective 的 Dvc,最后我们说到 regularizer 是一个非常 general 的工具,我们可以设计使用 符合目标函数特性的,能说服自己的,又容易优化求解的 来使用。

 
 

下次讲怎么做选择。