Category: All

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 的工具,我们可以设计使用 符合目标函数特性的,能说服自己的,又容易优化求解的 来使用。

 
 

下次讲怎么做选择。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

Machine Learning Foundations 13: Hazard of Overfitting


 
 

内容

  • Ocerfitting 的概念: Ein 变低, Eout 变高
  • Overfitting 很危险很容易发生,原因是:两种noise,数据不够,目标太复杂
  • 怎么解决 Overfitting:data cleaning/hinting/pruning, 等等,下面的课程继续介绍

     
     


     
     

    上一次我们讲到原来我们的model是线性的,如果我们把linear model配上non-linear的transform,那就产生的非线性的model来扩展我们的学习,代价是付出额外的model的complexity。

     
     

    今天我们从 complexity 出发,说到这额外的 model complexity 会造成机器学习里面一个很大的困难叫做 overfitting。我们首先将这个困难是如何产生的,然后说要怎么样解决它。

     
     


     
     

    我们先从一个例子出发:

     
     

    有五个资料点,X是随机产生的,Y则是X代入某个二次函数,再加上一些noise产生。

     
     

    如果我们假设我们用一四次的多项式来做回归分析,配合五个点,那就是有唯一解,也就是 Ein = 0,就是右边的红色的线,但是你会发现和蓝色的目标函数差距很大,也就是 Eout 很大。

     
     

    这个叫做:Bad Generation

    已有资料做得很好,未知资料结果就不好。

    当 Dvc 很大的时候,就会发生这样子 Ein 很小, Eout 很大的情况。

     
     


     
     

    前面提到过如果你用 1126 次方的多项式来做 learning,就会导致 Ein 很小,Eout 很大,这是不好的。

    同样讲过右边的图,Eout 会有一个先下降后上升的趋势,最低点就是最好的 Dvc 的位置。

     
     

    Overfitting: Ein越小,Fitting越好,但是会过头,造成Eout上升。

    Underfitting:fit的不够好。

     
     

    Underfitting 相对比较好解决,增加 Dvc 就可以,上次nonlinear transform就是来处理这个问题;overfitting比较不好解决,下面我们来探讨这个问题。

     
     

    Bad Generalization:描述的是一个当前状态的情况。

    Overfitting:描述的是变化的过程。

     
     


     
     

    如果选了一个好的如左图,右边是overfit的情况。

     
     

    我们如何来看这个问题,通过使用一些比喻来了解:

    overfit:好像出了车祸

    原因:开太快,等等(主观的)

    noise:路不平(客观的)

    资料量:路况(资料点够密,路熟悉)

     
     

    所以会发生overfitting:所以会发生车祸

     
     


     
     

    小测验

     
     


     
     

    为了让大家更了解 overfitting ,这里继续做一系列试验,来说明。

     
     

    还是考虑一维的回归分析,资料的产生:

     
     

    左边:

    用一个十次多项式来当作目标函数,X随机取样,Y由多项式值加上一些杂讯产生。

    右边:

    考虑一个五十次的多项式,不考虑杂讯生成 XY。

     
     

    我们用两个不同的 learning model:一个是2次的(绿色),一个是10次的(红色)。

    看哪个会表现得比较好。

     
     


     
     

    左边:g10 overfitting

    Ein: g10 < g2

    Eout:g10 >> g2

     
     

    右边:g10 overfitting

    Ein:g10 << g2

    Eout:g10 >> g2

     
     


     
     

    我们发现:

    G10,G2 如果今天这两个人都知道目标多项式,那么 G10 应该要比好吧?但是 G2 的结果反倒比较好。

     
     

    这叫做: concession for advantage (以退为进)

     
     


     
     

    为什么会这样?

     
     

    来看看 learning curve:描述得是资料量的多少和error的变化。

    上面左边的是 h2的 linear regression,其他h2类似。

    上面右边的是 h10的 linear regression,其他h10类似。Ein/Eout拉大了,因为 model complexity。

    重要的是左边的灰色区域 Eout_10 >> Eout_2。

     
     

    结论:资料量不够多的时候不用想太复杂的 model 。

     
     


     
     

    再来看没有 noise 的例子:这个时候还是 g2 做的好。

     
     

    你觉得这个时候真的是没有 noise 么?

    这里的noise的意思是:50次的 2/10 次理论上都做不到,而之间的差距就是 noise。

     
     

    结论:当你学的事情很复杂的时候,这个复杂度也可以当作是noise对结果产生影响。

     
     


     
     

    小测验。

     
     


     
     

    下面来做更细节的实验来告诉你说什么时候你要小心 overfit 会发生。

     
     

    产生资料分成三个变量:

    • Target function : 某个次方的多项式 ,多项式是 f 次。
    • Noise : Gaussion noise 强度不一样的时候对我的 overfitting 的影响,强度是 sigma^2。
    • 资料量:N

     
     

    这里要注意的是要产生真正的50次多项式,需要做一些手脚:正规化保证真正的50次。

    因为产生随机数的很多时候高次项系数为0的可能性很高。

     
     

    我们来探讨这三个变量对结果的影响。

     
     


     
     

    同样我们用两个学生来学习:

     
     

    G2: 只会最多2次多项式

    G10: 只会最多10次多项式

     
     

    结论:

    Ein_10 < Ein_2

    Overfitting 衡量: Eout_2 – Eout_10

     
     

    下面使用图示来 show overfit 的程度:

     
     


     
     

    左边:

    目标函数复杂度固定在20,横轴是资料量,纵轴是 gaussion noise 的程度 sigma^2。

    红色表示非常overfit,蓝色表示没有什么overfit。

    N 小,noise大会造成 overfit。

     
     

    右边:

    纵轴是目标复杂度,使用一样的gaussian sigma。

    目标越复杂,资料量不够会造成 overfit。

     
     

    这里的图就是 课程的 logo

     
     


     
     

    我们加上的 gasussion noise 是会对结果产生蛮大影响的,我们把它叫做 stochastic noise(随机噪声)

    我们的目标复杂度也会对结果产生很大的影响,我们把它叫做 deterministic noise(固定噪声)

     
     

    从上可以看出四个会发生 overfitting 的时间点:

    • 资料太少
    • 随机噪声太多
    • 固定噪声太大
    • 精力过剩(当今天目标函数是10次以下的时候,对于G10来说太简单,更容易 overfit)

     
     

    Overfit 很容易发生!!!

    就像小孩开大车。

     
     


     
     

    上面讲到如果今天目标函数太复杂的话和 noise 没什么区别。

    在CS里面常用:pseudo-random generator 随机数生成器 用的就是这个概念做的。

     
     

    如右图:蓝色标识的目标函数和红色标识的h之间是有差距的,当目标函数太过复杂,h没有办法表述的时候。灰色的区域就是 确定噪声。

     
     

    确定噪声特点:

    和 H 的复杂度相关

    对同一个 X 来说是一样的

     
     

    除了上面两点就是一般噪声

     
     


     
     

    小测验

     
     


     
     

    接下来我们要怎么样对付 overfitting 呢?

     
     

    机器学习:对比开车

     
     

    用简单一点的model:开慢一点

    Data cleaning/pruning:了解更精确的路况资料(下面讲)

    Data hinting(从现有的资料或者对这个问题的了解产生更多的资料):收集更多的路况资料(下面讲)

    Regularization:适时踩刹车(后面的课程讲)

    Validation:看看仪表板(后面的课程讲)

     
     

    综合使用多种工具来避免 overfitting。

     
     


     
     

    二分 1、5:

     
     

    如果把资料表示到 2d 平面就会有一群 1/5 。

    对于左上角的一个点被表示成5,你需要去确认他是 outline:

    如果标错了就改过来(Data Cleaning)。

    如果是没用的(data pruning)

     
     

    但是这里的难点是怎么去确认这个点有问题。

     
     


     
     

    Data Hinting:

     
     

    识别手写字,已有上面的这些资料,没办法再加了,但是根据我有的一些知识,对现有资料做一些小的变化,来创造出新的虚拟的资料,用在 model 里面。

     
     


     
     

    小测验。

     
     


     
     

    总结:

    • Ocerfitting 的概念: Ein 变低, Eout 变高
    • Overfitting 很危险很容易发生,原因是:两种noise,数据不够,目标太复杂
    • 怎么解决 Overfitting:data cleaning/hinting/pruning, 等等,下面的课程继续介绍

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

     
     

Machine Learning Foundations 12: Nonlinear Transformation


 
 

今天讲的是非线性的变换

 
 


 
 

上次讲到三个linear model都可以用在各式的classification问题上面,包括二元分类和多元分类的问题。但是这些model的重点是linear的,用线性的方式算一个分数,今天我们要把这个model衍生到non-linear的情况。

 
 


 
 

Linear hypotheses

 
 

如果今天是二元分类的话,视觉上就像切一条线,数学上表示就是 分数 = 权重 * X

这样带来的好处是 VC 维度是受到控制的,复杂度可控,Ein/Eout 不会差别太远。坏处是有些资料不可能用直线可以切分。

 
 

因此下面讲的就是如何去突破linear model的限制。

 
 


 
 

怎么做呢?

 
 

对于上面图示的资料来说

资料 D 不是线性可分的,就是不能用直线切分。但是如果我们采用圆圈来切分的话,看起来我是可以把ooxx分开来的。

比较方式是点到圆心的距离的平方,把它跟0.6比,这样一个hypotheses是可以区分这些资料的。

 
 

那么可以说上面的资料是圆圈圈可分,这样我们就可以重新设计怎么杨用圆圈圈来做PLA, regression等等。

 
 

但是这样太麻烦了吧,因此我们要来考虑怎么样系统化的设计这些演算法。

 
 


 
 

那我们首先来看看怎么用圆圈圈的方式来做到资料分类呢?

 
 

先把上面扯到的圆圈圈的方程式列出来,0.6代表圆的半径的平方,与点到圆心的距离的平方做减法,拆分出来就会有三个系数 w0, w1, w2,系数代表了hypotheses的圆的大小,系数同时配合输入x决定在圈内还是圈外。

 
 

上面的公式符号化表示也同样可以是 sign( w z ),和线性的时候是相似的,都是向量内积。

 
 

这样你就会发现:

这里面使用圆圈圈来区分可以看作是把 原来 x 空间里面的点 都转化到 Z 空间里面去。这里就是 z1 = xa^2, z2 = x2^2,也就是说对每一个点的值取平方画到新的空间中去,这样以后得到的就是右图。

这样就线性可分了,这条直线对应到原来的空间就是曲线。

 
 

上面做的 x -> z 的过程就是 feature transform(特征转换),这样后就可以继续使用线性分类了。

 
 

那么反过来也是对的么?就是说新的资料线性可分,那么可以得出旧的资料可以用圆圈分开这个结论么?

 
 


 
 

上面的转换的数学表示

新的资料线性可分:Z0, Z1, Z2

新的 hypotheses:w * 转换过的x

 
 

我们上面探讨的情形就是 w0, w1, w2 对应 0.6, -1, -1 正圆里面是oo

反过来的话 -0.6, 1, 1 正圆外面是oo

再如果是 0.6, -1, -2 得到的是椭圆

再来 0.6, -1, 2, 得到的是双曲线

还有 0.6, 1, 2 是常量

 
 

所以z空间里的每一条线对应到的可能是 圆/椭圆/双曲线/常量 等等,但这里面三个数值对应到的二次曲线也不是完整的一般二次曲线。

 
 


 
 

如果你要对应到所有可能的二次曲线,则你需要所有的 0/1/2 次项,这样你在Z空间里面的perceptions 对应到的就是 x空间里面的某一个分类方式。

 
 

这些就是我们目前可以考虑的分类方式:二次的 H_phine2 就是先把 x 透过 phine2(二次) 转化到 z 空间,再用某个线性分类器分类。

 
 

所以举个例子:如上式子表示的椭圆,则需要的就是橘色标识的那些系数来表示,对应到上面通用公示的六度空间的系数。

 
 

直线其实也已经包含在这个式子里面了。

 
 

到这里我们讲了我们怎么定义一个二次的hypotheses, 下面讲我们怎么学到好的二次hypotheses。

 
 


 
 

小测验

如果要是抛物线,系数会是什么样子?

 
 


 
 

我们现在已经建立的关系是这样:

 
 

Z 空间里面的直线 对应到 X 空间里面的所有的二次曲线

Z 空间里面找到一个好的分类直线 对应到 X空间里面的好的分类二次曲线

 
 

现在我们想要在 Z 空间里面找出好的直线,我们知道的是X空间的数据,应此做法就是先通过变换讲X空间的数据统统变化到Z空间上面,然后在Z空间上面找一条好的直线。

 
 


 
 

如上图所示将 (x, y) 转化成 (z, y),然后在右上图找到一条好的直线来做分类,然后再反对应到X空间,就可以看作是通过二次曲线在(x, y)空间做分类。

 
 


 
 

在这个流程里面有两件是我们可以选择的事情:

  1. 怎么做转换,转换到什么空间中去
  2. 用什么样的linear model:上面我们使用binarg classification来和大家做就讲解,但是同样的方式可以延伸到linear regression/logistic regression等等方法以及多类分类上面。


潘多拉盒子:

现在我们可以做很多很多事情,原来学过的所有东西都可以二次化,三次化,等等。

 
 


 
 

其实我们早就说过 feature transform 很重要,在之前讨论在做机器学习的时候可以用哪些feature(第三课):收集到的资料你可以把它做一些整理,处理。

 
 

原来是把 raw feature(原始资料) 透过我们对这个问题的了解,来做转换变成 比较容易吸收的资料的过程。

 
 

特征转换 这个是 机器学习里面的 the force(原力)。

 
 

但是这边特征转换听起来是那么的好,但是使用它是否也会有代价呢?下面来回答这个问题。

 
 


 
 

小测验

 
 


 
 

这么多个项的意思是什么呢?

如果我们今天想要general的情况的表示,就是 phine_Q = 0次的部分 + 1次的部分 + … + Q次的部分。

 
 

这里有多少个dimension呢?

1 + d:1代表常数,其他非常数的维度 = 有多少种不同的方法来组成 Q 那么多的项。

对应到概率论就是 重复组合 问题:d种东西可以重复取的化,一共有多少种不同的组合,结果就是 (Q+d / Q) 这么多种情况,大概就是 Q^d 这么多项,也就是说你今天就要花大么多的力气去计算。

 
 

所以特性转换的一个大的代价就是,计算和存储都需要花额外的力气,特别是Q很大的时候,这件事情非常困难。

 
 


 
 

上面讲到这个展开式有 Q^d 这么多项,也就是说需要 那么多个 W ,也就是 自由度,也就是说 Dvc 非常大,自由度大量的增加。

 
 

怎么办?

事实上我们可以证明的是 Dvc <= d+1,因为任何一个 Z 空间里面的 d+2 个点是没有任何办法 shatter 的,也就是说回到X空间里面 d+2 个点也不能够被 Q 次曲线来 shatter,这样就对我们的Dvc产生了限制。

因此上限就是 d+2

 
 

所以第二个代价就是,当Q变大的时候,Dvc也变大。

 
 


 
 

那么这件事情有什么坏处呢?

 
 

看上面两张图,同一资料两种不同的分类方式,左边说用一条线分类,右边说用一个四次曲线来分类。请问你会选择哪种分类方式?

 
 

你有没有更加觉得左边的图更加符合资料的特性,右边那个是不是可能太过头。

 
 

今天我们使用不同的 hypotheses 的时候,会冒出不同的问题来,两个核心的问题:Ein/Eout 接近不接近;Ein 够不够小。两个问题的 trade off 是不一样的。

 
 

如果 d(Q) 特征变换 大的时候 Ein小 Ein/Eout 隔得比较元远,反过来就相反。这是 ML 领域里面最重要的 trade off。

 
 

所以问题就来了:我们要怎么去选择适当的变换。

 
 


 
 

用眼睛来决定会存在问题:

 
 

如果资料在10维度空间,你可以做到?

如果是低维度,你用的是 phine_2, 原本是6参数,但是你算一下发现这里不那么复杂不用6维度,是不是只需要三个维度就能解决,再来,两个维度,第二个维度是 x1^2 + x2^2 也能解决,这样是不是都可以?

还有最聪明的方式,把结果 sign(0.6-x1^2-x2^2) 当作变换,这样是不是Dvc就是1,可以么?

 
 

上面你的化简,都是你聪明的小脑袋经过了一些运算和学习过程,把适合的变换用在了这个资料上。这里使用了你的主观感受,也就是说这是 humen learning,你替代了机器做了选择。

 
 

你没有把你脑袋的 Dvc 算到整个 model 里面去,那么你就会变得很乐观,但是你的 model 不会是你想象的那样好。

 
 


 
 

小测验。

 
 


 
 

这边我们来看看上面提到的多项式变换,首先来定义一下变换的次项:

 
 

这里 phine_0 表示0维的变换,就是常数项,phine_1表示1维的变换,就是所有的一次项加上phine_0的变换,以此类推,直到phine_Q = phine_Q-1 + 所有的Q次项。

 
 

也就是说你的每一变换都包含了前面的变换,也就是说高维的变换包含低维,低维的就是高维的特例。他们的 hypotheses set 也就是包含关系,画成图就如上面所示。

 
 

图示就是 hypotheses set structure。

 
 


 
 

这个结构告诉我们:

Hypotheses set 大包含小;H越大Dvc越大;hypotheses set大对应的最好的Ein小。 三串关系。

 
 

画成图就如上面所示。

 
 


 
 

这告诉我们:

如果你一开始就用一个超级高纬度的变换,结果一定也不好,在这个曲线的右边。

 
 

安全的做法是从 低维度开始做起,如果Ein(g1) 结果就很好,那就是好的结果,如果Ein不够小,就增加维度。

其实你会发现线性很多时候就已经可以得到很好的结果了。

 
 


 
 

小测验。

 
 


 
 

总结:

今天把大家熟悉的原来的 linear model 延伸到 nonlinear model。

一开始说怎么做二次的事情,然后还能继续扩展;然后说完整的nonlinear流程到底是什么样子;接着说这虽然看起来很好用,但实际上是要付出代价的,最重要的代价就是model complexity;最后告诉大家说你要付出这代价的情况下最安全的做法是从简单的model开始试。

 
 

这边我们就讲完了在 linear/nonlear model 上最基本的工具是哪一些。

我们提到过 变换 就是 the force(原力),下一次我们要和大家说的 the force 的黑暗面到底是什么,造成了什么不好的影响,怎么去控制黑暗势力。