在机器学习中,一个很需要我们关注的问题是欠拟合与过拟合(under-fitting and over-fitting)。在这篇文章里,我们将在多项式拟合的角度上从理论推导 L2正则 的作用原理。

我们知道,在使用多项式去拟合目标函数的过程中,我们选择的多项式次幂越高,则拟合效果越好。但另一方面,根据我们对 VC维 的了解,一个模型的自由度越高,其发生 Bad Sample 的概率也就越高:

$$
P[|E_{in}(h) - E_{out}(h)| > \epsilon] \leq 2exp(-2\epsilon^2N)
$$

所以,我们需要对过拟合的现象进行修正。

我们定义 $H_n$ 其中$n$为多项式的最高次幂。例如我们考查:

$$H_{10}=w_{0}+w_{1}x+w_{2}x^{2}+…+w_{10}x^{10} \
H_{2}=w_{0}+w_{1}x+w_{2}x
$$

我们只需使得 $w_3 = w_4 = … = w_{10} = 0$ , $H_{10}$ 就和 $H_1$ 等价了。另一方面,我们实际并不需要指定 $w_n=0$ 的具体项,只需限制整个多项式中 $w_n=0$ 的个数。即:

$$
\sum_{n=0}^N ||w_n \neq 0|| \leq C
$$

这里的 $C$ ,就是我们限制高次幂个数的参数了。
不过,很可惜的是,这个问题被计算机科学家证明为 NP-hard 是一个难解的问题。于是我们需要考虑放松我们的条件。

我们想到,之前是限制

$\sum_{n=0}^N ||w_n \neq 0|| \leq C$

,当严格地满足这个条件时,应该有:被限制项之和为 $0$ 。于是,我们把条件放松为:被限制项之和接近于$0$。即:

$$
\sum_{n=0}^Nw_q^2 \leq C
$$

于是在这种情况下,我们的求解问题变为了:

$$
\min_{w \in \mathbb{R}^{Q+1}} E_{in}(w) \text{ s. t.} \sum_{q=0}^{Q} w_q^2 \leq C
$$

我们把这个优化问题可视化如下:

reg.png

其中,圆形代表 $w_q^2 \leq C$ 这个限制条件,不带限制的全局最优解为 $w_{lin}$ ,椭圆代表 $E_{in}(w)$ 的一个等高线, $w^*$ 代表在约束条件下的最优解;红色向量代表圆上一点法线向量,绿色向量代表该点的切线向量,蓝色向量代表该点的负梯度方向。

我们的最优化过程应该为:在圆形球面上,某点顺着切线方向在圆周上运动,当且仅当该点的法线向量与负梯度方向共线时,优化算法停止。

为什么是法线向量与负梯度方向共线时停止呢?因为在这个时候,负梯度在切线方向上投影为 $0$ ,到达限制条件下的最优解。

我们假设已经找到了在限制条件内的最优解 $w^*$ ,一般地我们可以断言 $w^*$ 是在圆的周长上运动的。根据上面的推导,我们可以得出如下关系式:

$$
-\bigtriangledown E_{in}(w^*) = \lambda w^*
$$

此处的 $w^*$ 也代表圆在 $w^*$ 上的法向量。同时,为了后续推导方便,我们对常系数 $\lambda$ 变换为 $\dfrac{2\lambda}{N}$ 。
于是有:

$$
\bigtriangledown E_{in}(w^*) + \dfrac{2\lambda}{N} w^* = 0
$$

我们注意到,这个方程实际上是一个微分方程,我们对左边积分,得到:

$$
E_{in}(w^*) + \dfrac{\lambda}{N} ||w||^2
$$

于是,我们的目标变为了求取 $E_{in}(w^*) + \dfrac{\lambda}{N} ||w||^2$ 的导数为0的点。
我们定义新的函数,Augmented Error:

$$
{E_{aug}(w)= E_{in}(w) + \frac{\lambda}{N} w^T w}
$$

根据其他的数学知识(关于证明$E_{in}$是凸函数),我们最小化$E_{aug}(w)$的过程,就是在寻找限制范围下的最优解的过程。
我们调节$\lambda$即正则系数,就可以调节惩罚项与经验误差之间的关系,从而在模型复杂度和$E_{in}$中折衷得到优解。

关于参数$\lambda$的选择,我们可以先看看两张图:

lambda

lambda

从图中,我们可以看到,$\lambda$和$C$的作用是相同的,都是给出了约束条件,不过两个参量的正好是负相关的。

同时,我们不难发现,选择较小的$\lambda=0.0001$就会有不错的拟合效果,当$\lambda=0$时对应无约束的情况。

至此,我们对正则化过程的简易推导就结束了。不过因为我能力所限,并不能给出更为精确和具体的数学证明。同时对L1、L2的稀疏化研究也未能给出。有兴趣的读者,可以参考知乎专栏上的一篇文章深入理解L1、L2正则化

参考