How can Machine Learn Better? - Regularization

---

1. Regularized Hypothesis Set

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

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

图一 Regularization Fit ^[1]

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

$$H_{10} = w_0 + w_1 x + w_2 x^2 + w_3 x^3 + \dots + w_{10} x^{10} \tag{$1$}$$

$$H_{2} = w_0 + w_1 x + w_2 x^2 \tag{$2$}$$

$$H_{2} = w_0 + w_1 x + w_2 x^2 + w_3 x^3 + \dots + w_{10} x^{10} \quad s.t. w_3= w_4 = \dots = w_{10} =0 \tag{$3$}$$

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

$$H^{\prime}_{2} = w_0 + w_1 x + w_2 x^2 + w_3 x^3 + \dots + w_{10} x^{10} \quad s.t. \sum\limits_{q=0}^{10}(w_q \neq 0) \leq 3 \tag{$4$}$$

$$H_2 \subset H^{\prime}_{2} \subset H_{10} \tag{$5$}$$

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

$$H^{\prime}_{2} = w_0 + w_1 x + w_2 x^2 + w_3 x^3 + \dots + w_{10} x^{10} \quad s.t. \sum\limits_{q=0}^{10} w_q^2 = ||w||^2 \leq C \tag{$6$}$$

$$H(0) \subset H(1.126) \subset \dots \subset H(1126) \subset \dots \subset H(\infty) \subset H(10) \tag{$7$}$$

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

2. Weight Decay Regularization

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

$$\min\limits_{w \in R^{Q+1}} E_{in}(w) = \frac{1}{N} \underbrace{\sum\limits_{n=1}{N} (w^Tz_n - y_n) ^ 2}_{(Zw-y)^T(Zw-y)} \quad s.t. \underbrace{\sum\limits_{q=0}^Q w_q^2}_{w^Tw} \leq C \tag{$8$}$$

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

实际的变化方向如蓝色的向量 $- \nabla E_{in}$ 所示，其中红色向量normal 限定了切线的法向量的方向，而绿色的向量 $W_{lin}$ 就是我们需要想方法找到让他最短的时刻。

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

$$- \nabla E_{in}(W_{REG}) \propto W_{REG} \tag{$9$}$$

图二 The Lagrange Multiplier ^[2]

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

$$\begin{align*} & - \nabla E_{in}(W_{REG}) \propto W_{REG} \\ \Longrightarrow & - \nabla E_{in}(W_{REG}) \propto \frac{2 \lambda}{N} W_{REG} \\ \Longrightarrow & - \nabla E_{in}(W_{REG}) + \frac{2 \lambda}{N} W_{REG} = 0 \\ \Longrightarrow & \frac{2}{N} (Z^TZW_{REG} - Z^Ty) + \frac{2 \lambda}{N} W_{REG} = 0 \\ \Longrightarrow & W_{REG} = (Z^T Z + \lambda I )^{-1} Z^Ty \end{align*} \tag{$10$}$$

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

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

$$\DeclareMathOperator*{\argmin}{argmin} \begin{align*} & - \nabla E_{in}(W_{REG}) \propto W_{REG} \\ \Longrightarrow & E_{aug}(w) =E_{in} + \frac{\lambda}{N} w^Tw \\ \Longrightarrow & W_{REG} = \argmin\limits_w E_{in}(w) + \frac{\lambda}{N} w^Tw \end{align*} \tag{$11$}$$

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

图三 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]之间，那么可能导致 $x_n$ 相对于低阶的值要小得多，则其对于的w非常大，相当于要给高阶项设置很大的惩罚。 也就是说我们无论让每个w的元素设定不同的 $\lambda$ ， 从而如果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的表达式，$\Omega (w)$ 包含于 $Ω(H)$ 之内，所以， @H_502_4215@Eaug(w) $E_{aug}(w)$ 比 $E_{in}$ 更接近于 Eout@H_404_5071@(w) $E_{out}(w)$

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

所以当 $\lambda = 0$的时候，所有的w都没有收到惩罚，所以都考虑了，此时的 @H_52_5404@dvc $d_{vc}$ 比较大，容易产生overfitting，当 $\lambda > 0$ 的时候， 部分w的乘以0而被放弃考虑，所以 $d_{vc}$ 比较小，模型的复杂度就降下来了，就解决了overfitting的问题。当然如果 $\lambda$ 太大，使得过多的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)