0%

Regularization and Shrinkage

为什么把参数变小有助于防止过拟合?

正则化(Regularization)是机器学习中常见的技术。一种常见的正则化技术是$\ell_2$-Regularization (又称作weight decay). 这类正则化基本的思路就是在最终损失函数中加一个$\ell_2$正则化项,使得参数尽量变小:

$$L(\boldsymbol{f}(\boldsymbol{x};\boldsymbol{\theta}),\boldsymbol{y})=L(\boldsymbol{x},\boldsymbol{y})+\lambda \lVert \boldsymbol{\theta} \rVert_2$$

我们将$\lambda$称为正则化系数

一种常见的说法是,正则化通过减小模型的复杂性来降低过拟合的可能。参数少的模型具有较低的复杂性,这听起来是容易理解的。然而,我们通常使用基于梯度的方法(如SGD)来优化损失函数。对于$\theta_i$, $\ell_2$正则化项的导数是$2\theta_i$。这使得在计算$\theta_i$梯度的时候随着$\theta_i$的减小,$\frac{dL}{d\theta_i}$会越来越小,导致$\theta_i$只能无限趋近于$0$,而很难等于$0$. 这时,利用$\ell_2$正则化降低模型复杂性就显得难以理解了。参数没有似乎是完全不同的两件事。一个具有非常多参数的模型,即使这些参数的值很小,但他们参数空间和参数值很大的情况下是一样的。正则化是如何降低模型的复杂度的?

解释1: Bias-variance tradeoff

这个理论的基本思想是,$\ell_p$正则化通过放弃估计的无偏性来获取更小的方差。我们在附录A中简单介绍了无偏性和方差的基本概念。简单来说,无偏性(unbias)代表了估计均值与真实值的差异,方差(variance)代表估计的离散程度。

为什么我们需要更小的方差?直观来说,一个无偏的估计在训练集上能够达到最好的效果(估计的期望与训练集的期望保持一致),但这样的估计显然可能不适用于测试集。尤其是在数据集具有较大方差的情况下,训练集和测试集有着较大的差异,就导致估计器(或模型)在训练集上有着优良的表现,而在测试集上表现很差,这就是所谓的过拟合

为什么需要放弃无偏性来获取更小的方差?高斯-马尔科夫定理(附录B)指出,如果误差满足零均值、同方差且互不相关,最小二乘法估计就是最佳线性无偏估计,即最小二乘回归(Ordinary Least Squares, OLS)在所有无偏估计中有着最小的方差。但是,方差较低不意味着方差非常低。在一些情况下,OLS估计的方差会非常大,导致OLS的结果毫无作用。如果这个估计仍然存在过拟合的情况,我们只能考虑放弃无偏性来获得更优的估计。我们希望通过放弃无偏性,获得一种有偏估计,这种估计的期望可能略微和真实值有所偏离,但他获得了更小的方差。

Bias–variance decomposition

Notation

$f$: $\boldsymbol{f}(\boldsymbol{x};\boldsymbol{\theta})$, 估计的真实值
$\hat{f}$: $\boldsymbol{f}(\boldsymbol{x};\hat{\boldsymbol{\theta}})$, 模型估计的值
$y$: 模型的标签,是真实值和噪声$\varepsilon$的叠加: $y=f+\varepsilon$

考虑Squared Loss:
$$L_{Square}(\hat{f},\boldsymbol{y})=\Bbb{E}[(\hat{f}-\boldsymbol{y})^2]$$

Squared Loss可以被分解为Bias, Variance和Noise之和:

$$L_{Square}(\hat{f},\boldsymbol{y})=Bias[\hat{f}]^2+Var[y]+Var[\hat{f}]$$

可以看出,Square Loss是由偏差, 方差和数据噪声三个部分共同组成的。数据噪声是数据集带来的(例如人工标注错误等),不在模型的控制范围内。我们调节Bias和Variance,就是在这两者直接取一个均衡,来获得最小的损失。

Limitations

这个理论的限制在于,Bias–variance decomposition基于的是多个独立的数据集多次实验的平均结果,而实际应用中,我们往往只有单一的数据集和单次的实验结果。如果我们有更大的数据集,我们完全不需要分割开做多次实验,而是一次用一个非常大的数据集来训练模型,这样往往能够有效降低过拟合。

Further Reading

  1. Christopher M. Bishop, Pattern Recognition and Machine Learning, Section 3.2: The Bias-Variance Decomposition

解释2: Shrinkage Estimation

我们从Stein Estimator谈起。直觉上说,James–Stein估计器表达了这样一个思想:将参数收缩可以获得更好的估计。

例子:估计一组随机变量的均值$\boldsymbol{\theta}$

问题

考虑$p$个随机变量$X_1,…,X_p$服从正态分布$X_i \sim N(\theta_i,1)$,每个随机变量方差均为$1$,但均值$\theta_i$各不相同。

找到一个对随机变量分布期望的估计$\hat{\boldsymbol{\theta}}=\hat{\boldsymbol{\theta}}(X)$, 其中$\boldsymbol{\theta}=(\theta_1,…,\theta_p)^T$。

损失函数 我们使用Squared Loss作为损失函数:
$$L(\hat{\theta},\theta)=\lVert \hat{\boldsymbol{\theta}} - \boldsymbol{\theta} \rVert_2$$

由于$\boldsymbol{\theta}$是随机变量,具体到某个数据集,我们考虑风险函数(risk function):
$$R(\hat{\theta},\theta)=\Bbb{E}[L(\hat{\theta},\theta)]$$

一个简单的估计器 一种非常容易想到的估计器是$\hat{\boldsymbol{\theta}}(X)=X$. 由于$\Bbb{E}[X_i]=\theta_i$, 因此$X_i$是$\theta_i$的一个无偏估计(附录A)。 实际上,这个估计就是对$\theta$的MLE估计(附录C)。

Stein Estimator 在$p>2$时,Stein证明了,下述Stein估计的效果好于(dominate)好于MLE估计:

$$\hat{\theta}^{J S}(X)=\left(1-\frac{p-2}{|X|^{2}}\right) X$$

注: 实际上也好于MLP估计,参见Efron et al., Computer Age Statistical Inference: Algorithms, Evidence and Data Science, Section 7.1: The James–Stein Estimator.

$\left(1-\frac{p-2}{|X|^{2}}\right)$对$X$起到收缩的作用。在当时(1960s)的统计学界,这一发现无疑是令人震惊的。这一发现直击MLE的关键阵地:正态分布和Squared Loss。在维度低的情况下,或许有道理考虑MLE估计,但在现代数据中的高维情况下,不考虑收缩分布是没有道理的。

在此之后,大量收缩估计(Shrinkage Estimator)被开发出来,其中最具有代表性的就是岭回归(Ridge Regression, $\ell_2$正则化)和Lasso回归($\ell_1$正则化)。

为什么几乎没有人直接使用Stein Estimator?

一个原因是,目前没有很好针对Stein Estimator的优化方法。

Further Reading

  1. Bradley Efron and Trevor Hastie, Computer Age Statistical Inference: Algorithms, Evidence and Data Science, Section 7: James–Stein Estimation and Ridge Regression
  2. Richard J. Samworth, Stein’s Paradox
  3. Unified view on shrinkage: what is the relation (if any) between Stein’s paradox, ridge regression, and random effects in mixed models?

Conclusion

现如今,正则化几乎成为了机器学习方法的标准配置,从岭回归到神经网络,正则化都发挥着不可或缺的作用。本文从两个不同的方向介绍了regularization的基本思想,希望给读者带来一些启示。

Appendix

Appendix A: 无偏性和方差

统计学中的“偏差” (Bias) 指的是估计量$\hat{\theta}$的期望与真实值$\theta$之差:
$$\Bbb{E}[\hat{\theta}]-\theta$$

Bias为零的估计被称为“无偏估计”,Bias不为零的估计被称为“有偏估计”。Variance是容易理解的,即多次$\hat{\theta}$估计的离散程度。Bias是对期望的衡量,Variance是对方差的衡量。我们希望$\hat{\theta}$满足:

  • Bias为0. 即所有估计量的期望$\Bbb{E}[\hat{\theta}]$恰好等于真实值$\theta$.
  • Variance为0. 即每次估计都得到稳定一致的估计量$\hat{\theta}$.

Appendix B: 高斯-马尔科夫定理 (Gauss-Markov Theorem)

高斯-马尔科夫定理:

在线性回归模型中,如果误差满足零均值、同方差且互不相关,则回归系数的最佳线性无偏估计(BLUE, Best Linear unbiased estimator)就是最小二乘法估计

Appendix C: MLE and MAP

最大似然估计 (Maximum Likelihood Estimation, MLE)

对于一组数据$D$, 最大似然估计分为以下两步:

  1. 对数据的分布作出假设: 数据是从何种分布中采样而来的。即$P(D;\theta)$, 其中$\theta$是分布的参数。

例子:对于抛硬币的结果(正或者反),假设数据从二项分布中采样,参数$\theta$就是每次实验中抛出正面的概率。

  1. 怎样的$\theta$能够使得这个数据最有可能存在?即最大化$P(D;\theta)$:
    $$\hat{\theta}_{MLE}=\underset{\theta}{\operatorname{argmax}} P(D ; \theta)$$

最大后验概率 (Maximum a Posteriori Probability Estimation, MAP)

贝叶斯方法与MLE最大的不同在于,MLE将数据$D$的概率分布记为$P(D;\theta)$(此时$\theta$是一个参数),而贝叶斯方法将数据$D$的概率分布记为$P(D|\theta)$(此时$\theta$是一个随机变量)。

$\theta$并不与一个随机事件相关联,也不对应一个采样空间,在频率学派统计中,这不能成为一个随机变量,而在贝叶斯统计中是允许的。

贝叶斯统计中,我们把$\theta$服从的分布$P(\theta)$叫做先验 (prior),即在我们没有观察数据$D$的时候对参数$\theta$服从分布的预备知识;$P(D|\theta)$叫做似然(likelihood),即给定$\theta$的情况下这个数据存在的可能性;$P(\theta|D)$叫做后验 (posterior),即我们在已经观察到数据之后对$\theta$的概率估计。

MLE就是最大化似然函数$P(D|\theta)$,MAP就是最大化后验概率$P(\theta|D)$:

$$\hat{\theta}_{MAP}=\underset{\theta}{\operatorname{argmax}} P(\theta | D)$$

先验分布从哪里来?

贝叶斯估计要求预先知道参数的先验分布$P(\theta)$,否则无法进行估计。那么我们怎么知道先验分布呢?通常来说,我们根据自己的知识假设一个先验分布(即使他不一定对)。

  1. 抛硬币:$\theta$表示每次抛硬币正面向上的概率。根据经验,$\theta$的分布应当满足:(a) $P(\theta)$最大值应在$P(\theta=0.5)$处;(b) $\theta \in [0, 1]$;(c) $\theta$的分布类似于一个钟形分布,在$0.5$处最大,$0$和$1$处最小。根据上述三个条件,我们选择Beta分布.
  2. 均值的先验分布:我们希望估计高斯分布$N(\theta,1)$的均值$\theta$,由于高斯分布是常见的分布,我们可以假设$\theta$服从高斯分布$\theta \sim N(M,N)$。

此外,也可以从数据中估计先验分布,请参考经验贝叶斯.

Further Reading

  1. Kilian Weinberger, Lecture 7 Estimating Probabilities from Data: Maximum Likelihood Estimation - Cornell CS4780 SP17, https://www.youtube.com/watch?v=RIawrYLVdIw&t=17s
  2. Bradley Efron and Trevor Hastie, Computer Age Statistical Inference: Algorithms, Evidence and Data Science, Section 6: Empirical Bayes