Machine Learning Foundations 14: Regularization | Cheney Shen

Technology blog

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

 
 

下次讲怎么做选择。

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 


One Comment

Post a Comment

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

  • Categories

  • Tags