网络机器人吧社区

公开课|机器学习基石14 Regularization

机器学习小蜜蜂 2019-02-10 11:47:22

(点击上方蓝字,关注机器学习小蜜蜂)

 

转载时请标明本文链接和作者,谢谢合作!

微信号: 机器学习小蜜蜂

     

本篇介绍正则技术。着重解决为什么要正则,如何求解(L2正则),并从哲学上解释正则为什么能避免 overfitting。

        

Regularization


Regularization,正则化/正规化。Regularization 原本为了解决 ill-posed (不适定问题)。


具体到机器学习领域,Regularization 是解决 overfitting 的一种非常有效的手段。

上篇说到产生 overfitting 的重要原因就是数据量过少,模型过于复杂。


比如,考虑一维特征的回归问题,假设有五个点,如上图所示。显然 5 个点,可以找到无穷多个 10 次多项式,经过这五个点,即 Ein = 0(图中红色曲线就是其中一例),这样会产生明显的 overfitting 问题,反而,采用 2 次多项式会效果会更好 (如图蓝色曲线所示)。


Regularization,通俗的讲,就是在一堆解空间 (假设空间, Hypothesis Set) 中寻找一个"更好"的解 (假设)。所谓更好,即不会 overfitting


显然 假设空间 H2 (2 次多项式) 是 假设空间 H10 的子集。具体到这个例子而言,H2 更不容易产生 overfitting。


那么现在就要思考怎么从 H10 回到 H2 (怎么从 H10 寻找 H2)。这个过程被称为 "regularized fit" (如下图红色曲线所示)。


依然采用 多项式转换(Q-th order polynomial transform) + linear regression 解决这个问题。


H10 回到 H2,数学上可以用约束条件 (constraint) 表示,  只需要满足约束条件:w3~w10 = 0 即可。

对比: H10 和 H2。


Regularized Hypothesis Set



假设空间 H2 可以表示成带有"约束条件"的 H10。


显然 H2 很不灵活,可以将约束条件放的更宽泛一些,只需要 "不等于0的w" 不超过四个,这样就引入了 H'2。

H'2 是一个折中的选择,比 H2 更灵活,比 H10 overfitting 的风险更小。很遗憾,求解 H'2 被证明是一个 NP-Hard 问题。


不过没有关系,可以进一步放宽约束条件,采用平滑的限制条件替代离散的限制条件。


这样引入了 H(C) 假说空间。H(C) 有一些很好的特征:

1. H(C) 和  H'2 很大一部分重叠。通过调节 C,可以做到 w 不会太大。

2. 。当 C 为 ∞ 时,就是没有约束条件的情形。


H(C) 被称为 Regularized Hypothesis Set。H(C) 的最优解被称为 Regularized Hyothesis 


求解 Regularized Regression


Regularized Regression Problem 已经顺利被转化为优化问题,其本质就是带有条件的 Linear Regression Problem

和前面的 linear regression 一样,可以表示成矩阵形式:

okay,如果有微积分基础的同学不难发现,可以引入"拉格朗日算子"进行求解。


不会也没有关系,可以图解理解。

先看优化目标 min Ein,之前 linear regression 时说过,最优解可以通过沿着"梯度的反方向"游动 (梯度下降法, GD)。图中蓝色曲线的表示的是 Ein 的等值线,若没有约束条件限制的话,不断沿着梯度反方向,最终最优解就是 linear regression 的最优解 w_lin

再看约束条件,以 w 二维空间为例,约束条件  ,其实就是将解空间限定在一个圆内,那么最优解最终肯定发生在圆的边缘,在梯度的作用下沿着圆的边缘游动。

那么什么时候停止呢?几何上可以看出当圆的切线和梯度垂直时即为最优解,等价的就是 Normal // ▽Ein 的时,Normal 正好就是 w。


结论:


好吧,现在引入"拉格朗日算子" 就不难理解了。

注意 λ > 0,因为是梯度的反方向。

引入"拉格朗日算子"的好处就是直接把"约束条件"给消化掉了


利用前面的知识,不难发现这是一个线性方程,具体细节不赘述。

有没有发现,最优解 W_REG 就是统计学中的"岭回归"(ridge regression)。


另一种角度思考

梯度就是高维求导,微积分告诉我们,导数为 0 的点可能是极值点。那么思考这个式子是哪个的导数呢?两边积分即可。

等价问题:


对比两个等价问题

利用拉格朗日算子可以把有约束条件的优化问题转化为无条件的优化问题。称这个优化目标为 augmented err Eaug(w)


minimizing unconstrained Eaug effectively minimizes some C-constrained Ein 


恭喜,有条件的 H(C) 的问题变成无条件的 Eaut(w) 问题。正则项  可以看成是惩罚项,可以通过调节拉格朗日算子 λ 来惩罚那些过大的 w。


先来对比几个 λ 的效果。

发现,一点点的正则项 (λ = 0.0001) 能获得很好的效果。

λ 越大,正则项惩罚力度就越大,约束 w 不能太大,也就要求 C 越小。

此外需要说明的,weight-decay regularization 是一种的通用的技术,和转换与模型无关。


小技巧:

实践当中,并不直接使用简单的多项式转换。因为当 q 很大时,x^q 很小,那么对应的 w_q 还大时,x^q 这个特征才起作用。

实践当中,通常采用勒让德多项式 (Legendre polynomials),勒让德多项式一个非常重要的性质就是"交性"。


正则化和 VC 理论的哲学思考



两个公式很像,正则项 Ω(w) 描述的是一个假说的复杂度,Ω(H) 描述的是假说空间的复杂度。

直觉上,一个假说上表现不错,多少也启发了这个假说空间也不错 (优化目标 Eaug 是 Eout 一个不错的代理)。

或者是最小化 Eaug 是最小化 Eout 的启发式解,并且比 Ω(H) 来的灵活。



还可以从 VC 维角度思考。

1. H 的 VC 维是 d+1,最优化 Ein(w) 会考虑所有的 w

2. H(C),最优化 Eaug(w) 考虑的是实际有效的 wd_vc(H(C)) ≡ d_EFF(H, A)。实际上是定义了 H(C) 的 VC 维 (H(C) 假说空间是带有约束条件的假设空间)。


总结:


L1 和 L2


前面讨论的正则项,学名是 L2 正则项。正则项可以看成惩罚项,是约束 ≠0的 w 不宜过多的启发式描述。


正则项是一种通用技术。可以有各种形式的正则项,只要能起到惩罚作用即可。

实际当中,比较常用的就是 L1/L2。



L1/L2 实际上是将解空间约束在一个区域内。比如 L2 在圆内,L1 在方型内。

L2 正则项具有:凹性、可微分的性质,所以很容易优化求解。

L1 正则项具有:凹行、基本可微 (交叉点不可微),这样的好处最终得到的解是稀疏的(可以做到很多 w = 0)。


λ 的选择


Eout 上评估。可以看出:

噪声越大 (无论是 随机性/确定性 噪声),需要的正则项越大 (可以形象理解:就像路不平 (噪声),需要踩撒车(正则))。


小结


本篇系统讲解了正则技术,重点关注正则的引入、求解以及哲学思考。

下篇将介绍模型/参数如何选择。敬请期待!


参考: 

1. 本文截图来自林田轩老师的课件

感谢你关注“机器学习小蜜蜂”,期待你的留言和建议。



Copyright © 网络机器人吧社区@2017