How can Machine Learn Better? - Regularization

1. Regularized Hypothesis Set

正则化的主要思想：将假设函数从高次多项式的数降低到低次，即把复杂的模型变成简单模型。如图一所示的表示高次多项式函数，明显产生了过拟合现象，而左图的表示使用正则化后的低次函数。并且从图中的下方的Hypothesis Set的圈中可以看出，高次的多项式会包含低次的多项式。所以在转换的过程，就是把模型从外圈降至内圈的过程。

但是：Regularization 不适用于多个解的模型，因为在降阶的过程中面临着选择最适解

图一 Regularization Fit ^[1]

下面来讨论如何进行降阶：
1.首先我们在列出10次和2次的多项式，如公式（1）（2）所示。对比可以发现，其实 H2 可以看成是 H10 的3~10次项的系数为0，如公式（3）所示，其中 s.t. 是subject to的意思，即约束条件

2.接着我们稍微放宽一下条件：我们不限定说一定要 3~10次多项式系数为0，我们只要要求满足有8项为0，即3项不为零（包括常数项），如公式（4）所示。这种Hypothesis称为 H′2 。并且这个Hypothesis与 H2 H10 的关系如公式（5）所示。显然， H′2 比 H2 更加的Flexible， 而 H′2 比 H10 的复杂度更低。

3.但是这个Hypothesis H′2 的求解也是一个np-hard问题。所以我们继续寻找容易求解的宽松情况。如公式（6）所示，这种Hypothesis我们称为 H(C) 其中C为常数，H(C)称为regularized hypothesis set。这个方程的限定条件是让 权重的平方和小于C，当C增大时，限定的条件越宽松。如果C接近于无穷大，那么就和 H10 没什么区别了,如公式（7）所示

这种形式的限定条件是可以进行求解的，我们把求解的满足限定条件的权重w记为wREG。接下来就要探讨如何求解wREG。

2. Weight Decay Regularization

1.首先我们为了表示方便，把公式（6）做一定的调整：写成向量矩阵的形式，得到公式（8）

2.我们的目的是计算 Ein(w) 的最小值，其中限定条件是 ||w2||≤C 如图二所示，这个限定条件从几何角度上的意思是，权重w被限定在半径为 C−−√ 的圆内（红色的圆），而球外的w都不符合要求，即便它是靠近 Ein(w) 梯度为零的w。

实际的变化方向如蓝色的向量 −∇Ein 所示，其中红色向量normal 限定了切线的法向量的方向，而绿色的向量 Wlin 就是我们需要想方法找到让他最短的时刻。

显然，红色和绿色的向量其实就是蓝色向量的相互垂直的分向量，由高中的数学知识，我们知道，当蓝色向量越接近于红色的向量，那么绿色的向量长度越小，即如公式（9）所示

图二 The Lagrange Multiplier ^[2]

3.然后我们队公式（9）加入拉格朗日算子 λ ， 进行调整得到公式（10）

上式中包含了求逆矩阵的过程，因为 ZTZ 是半正定矩阵，如果 λ 大于零，那么 ZTZ+λI 一定是正定矩阵，即一定可逆。统计学上把这叫做ridge regression(岭回归)

4.如果把公式（10）的反过来求积分，我们可以得到公式（11）。该表达式称为增广错误（augmented error）用 Eaug(w) 表示，其中 wTw 为正则化项（regularizer）。之所以叫做增广错误，是因为比传统的多了一正则化项。

所以我们只需要调整不同的 λ 的值就可以对模型复杂度进行一定的调整，如图三所示。

图三 Result of Weith Decay Regularization ^[2]

从图中可以看出，当λ=0时，发生了过拟合；当λ=0.0001时，拟合的效果很好；当λ=0.01和λ=1时，发生了欠拟合。我们可以把λ看成是一种penality，即对hypothesis复杂度的惩罚，λ越大，w就越小，对应于C值越小，即这种惩罚越大，拟合曲线就会越平滑，高阶项就会削弱，容易发生欠拟合。λ一般取比较小的值就能达到良好的拟合效果，过大过小都有问题，但究竟取什么值，要根据具体训练数据和模型进行分析与调试。

这种regularization不仅可以用在多项式的hypothesis中，还可以应用在logistic regression等其他hypothesis中，都可以达到防止过拟合的效果。

但是这种方法有一个问题：我们目前讨论的多项式是形如x,x2,x3,⋯,xn的形式，若x的范围限定在[-1,1]之间，那么可能导致 xn 相对于低阶的值要小得多，则其对于的w非常大，相当于要给高阶项设置很大的惩罚。 也就是说我们无论让每个w的元素设定不同的 λ ， 从而如果x的范围很大的话，那么会使得部分数据很小。

克服这个问题的方法是用Legendre polynomials代替x,xn这种形式，Legendre polynomials各项之间是正交的，用它进行多项式拟合的效果更好。

3. Regularization and VC Theory

本节介绍正则化与VC理论的关系。即从VC理论的角度说明为什么正则化的效果好

我们将从2个角度来讨论这个问题： 1) 误差方程 2） VC Dimension

1.首先对比 Augmented Error 和 VC Bound， 如图四所示

图四 Augmented Error and VC Bound ^[3]

根据Augmented Error和VC Bound的表达式， Ω(w) 包含于 Ω(H) 之内，所以， Eaug(w) 比 Ein 更接近于 Eout(w)

2.从VC Dimension的角度。根据VC Dimension理论，整个hypothesis set的 dvc=d˘+1 ，这是因为所有的w都考虑了，没有任何限制条件。而引入限定条件的 dvc(H(C))=dEFF(H,A) ，即有效的VC Dimension。很显然， dvc 比较大，因为它代表了整个hypothesis set，但是 dEFF(H,A) 比较小，因为由于regularized的影响，限定了w只取一小部分。

所以当 λ=0 的时候，所有的w都没有收到惩罚，所以都考虑了，此时的 dvc 比较大，容易产生overfitting，当 λ>0 的时候， 部分w的乘以0而被放弃考虑，所以 dvc 比较小，模型的复杂度就降下来了，就解决了overfitting的问题。当然如果 λ 太大，使得过多的w被舍弃，那么就会出现 underfitting的情况了

4. General Regularizers

Regularizers主要有 L0,L1 和L2，前面用到的是 L2的Regularizer
关于范数的概念老师课上没有讲的很明白，可以参考这两篇博客，后续我也会写关于范数的博客

@ Todo L0、L1与L2范数

机器学习中的范数规则化之（一）L0、L1与L2范数

机器学习中的范数规则化之（二）核范数与规则项参数选择

Summary

1. 这一节首先介绍了Regularization：在Hypothesis Set的基础上 加入 Regularizer 作为 Penality。使得最终结果中的部分w被惩罚掉而不被考虑，从而实现了降低模型复杂度的功能。
2. 接着我们讨论了为什么 Regularization 能让模型复杂度降低，并且模型的泛化能力更强
3. 最后我们讨论了常用的范数:L0 L1 L2 范数

Reference

[1] 机器学习基石(台湾大学-林轩田)\14\14 - 1 - Regularized Hypothesis Set (19-16)

[2] 机器学习基石(台湾大学-林轩田)\14\14 - 2 - Weight Decay Regularization (24-08)

[3] 机器学习基石(台湾大学-林轩田)\14\14 - 3 - Regularization and VC Theory (08-15)