前言
在机器学习中,当训练数据太少或者模型过于复杂等情况,当模型学习了数据的噪声的细节,那么模型在未知的数据表现就会不好,即泛化误差比训练误差大,这就是过拟合。模型选择的典型方法是正则化,使用正则化技术可以很大程度上减缓过拟合问题。
“没有免费的午餐”定理(NFL)
“没有免费的午餐”定理表明,在机器学习中无论是瞎猜还是一些很牛的算法,它的期望性能都相同。也就是说,考虑所有可能的目标函数,没有哪个算法比其他算法高效。如果要想在某些问题上得到性能的提高,必须在一些问题上付出同等代价!就像算法的时间复杂度和空间复杂度。
符号说明:
- $\mathcal{X}$:样本空间(离散)
- $\mathcal{H}$:假设空间(离散),例如在线性回归中我们假设数据满足某种线性关系
- $P(h|X, \mathcal{L}a)$:算法 $\mathcal{L}a$ 基于训练数据 $X$ 产生假设 $h$ 的概率
- $f$:真实目标函数
- $E_{ote}(\mathcal{L}a|X, f)$:算法 $\mathcal{L}a$ 的训练集外误差(Off-trainning error),即算法 $\mathcal{L}a$ 在x 训练集之外的所有样本上的误差
对于一个特定问题,即真实目标函数确定,算法 $\mathcal{L}a$ 的训练集外误差为:
$$
E_{ote}(\mathcal{L}a|X, f) = \sum_{h}\sum_{x\in \mathcal{X}-X}P(x)1\lbrace h(x)\neq f(x)\rbrace P(h|X, \mathcal{L}a)
$$
对于二分类问题,真实目标函数一共有 $2^{\lvert\mathcal{X}\rvert}$ 个,且均匀分布。对于一个真实目标函数,一个假设 $h$ 的输出有 $\frac{1}{2}$ 的可能与真实目标函数相等。 所以对于所有可能的目标函数,算法 $\mathcal{L}a$ 的训练集外误差为:
$$
\begin{align}
\sum_{f}E_{ote}(\mathcal{L}a|X, f) &= \sum_{f}\sum_{h}\sum_{x\in \mathcal{X}-X}P(x)1\lbrace h(x)\neq f(x)\rbrace P(h|X, \mathcal{L}a) \\
&= \sum_{x\in \mathcal{X}-X}P(x)\sum_{h}P(h|X, \mathcal{L}a)\sum_{f}1\lbrace h(x)\neq f(x)\rbrace \\
&= \sum_{x\in \mathcal{X}-X}P(x)\sum_{h}P(h|X, \mathcal{L}a)\frac{1}{2}2^{\lvert\mathcal{X}\rvert} \\
&= 2^{\lvert\mathcal{X}\rvert-1}\sum_{x\in \mathcal{X}-X}P(x)\cdot 1
\end{align}
$$
对于所有可能的目标函数,一个算法最终的总误差和这个算法无关。没有任何一个算法能够解决所有问题,在现实生活中我们有一套先验知识来判断哪些更优,这些先验知识包含简单性(“奥卡姆剃刀”原理),平滑性等等,所以我们就应该更具这些先验知识来具体问题具体分析。
NFL定理最重要的寓意是让我们清楚地认识到:脱离具体问题,空泛地谈论”什么学习算法更好“毫无意义。因为若考虑所有潜在的问题,则所有的算法一样好,要谈论算法的相对优劣,必须要针对具体问题;在某些问题上表现好的学习算法,在另一问题上却可能不尽如人意,学习算法自身的归纳偏好与问题是否相配,往往会起到决定性作用.
“奥卡姆剃刀”原理
如无必要,勿增实体。
意思是相比较于复杂的假设,我们更倾向于选择简单的、参数少的假设。如果线性回归和高阶的多项式回归在某个问题上的表现相似(例如训练误差相同),那么我们应该选择较为简单的线性回归。从贝叶斯估计的角度来看,简单的模型有较大的先验概率,毕竟一个高阶多项式随机采样的数据呈线性的概率太小了。
正则化
大部分正则化通过在代价函数上加一个正则项或者惩罚项,让算法在训练过程中尽量学习一个简单的模型,即满足“奥卡姆剃刀”原理,这样就可以减缓过拟合的发生。正则化项大概有以下几类:
- L0 正则化:L0 正则化的值是模型参数中非零参数的个数(0范数)。稀疏的参数可以让模型变得简单,但是 L0 正则化难于求解。
- L1(Lasso) 正则化:L1 正则化的值是模型各个参数的绝对值之和(1范数),也会获得稀疏的参数。
- L2(Ridge) 正则化:L2 正则化的值是模型各个参数的平方之和(2范数的平方,平方是为了易于优化),也称为权重衰减,因为最后会获得值很小的参数。
- Dropout:在深度学习的训练过程中,按照一定的概率随机让一些神经元结点失活。
- 数据增广:例如通过对图像进行旋转、扭曲等操作,获得更多的训练数据。
- Early stop:在泛化误差上升之前,停止网络的训练,缺点是会导致 $J$ 被优化得不够小。
- …
L1 正则化
$$
J(\boldsymbol{w})=\frac{1}{m}\sum_{i=1}^m\mathcal{L}(\hat y^{(i)}, y^{(i)})+\frac{\lambda}{m}\Vert\boldsymbol{w}\Vert_1
$$
$$
dw_i=\frac{\partial J}{\partial w_i}=\frac{\lambda}{2m}sign(w_i)=\pm\frac{\lambda}{m}
$$
$$
w_i=w_i-\alpha dw_i=w_i\mp\frac{\alpha\lambda}{m}
$$
通过梯度下降最小化代价函数时,更新参数 $w_i$ 每次都会加减一个固定的数,往 0 逼近,多次迭代后则有可能变成成 0,稀疏的参数可以用于特征选择。
L2 正则化
$$
J(\boldsymbol{w})=\frac{1}{m}\sum_{i=1}^m\mathcal{L}(\hat y^{(i)}, y^{(i)})+\frac{\lambda}{2m}\Vert\boldsymbol{w}\Vert_2^2
$$
$$
dw_i=\frac{\partial J}{\partial w_i}=\frac{\lambda}{m}w_i
$$
$$
w_i=w_i-\alpha dw_i=(1-\frac{\alpha\lambda}{m})w_i
$$
通过梯度下降最小化代价函数时,更新参数 $w_i$ 每次都会乘以 $(1-\frac{\alpha\lambda}{m})$ 这个小于 1 的数(权重衰减),往 0 逼近,多次迭代后也只能是更加逼近 0 而不会等于 0。Xavier 表示,除非需要稀疏的参数进行特征选择,在实际应用中,L2 总是比 L1 好,所以推荐使用 L2 正则化。
惩罚参数 $\lambda$ 增大则参数 $\boldsymbol{w}$ 减小。在神经网络中,如果参数值逼近 0,则该神经元结点对结果的影响也逼近 0,因此可以有效减缓过拟合。如果一个神经网络的激活函数是 Tanh 函数,而且所有参数值都逼近 0,那么神经元结点的输入就约等于输出(Tanh 函数原点处大致呈线性),最终不管网络多深,都只能计算线性函数。
前向传播
$$
J_{regularized} = \small \underbrace{-\frac{1}{m} \sum\limits_{i = 1}^{m} \large{(}\small y^{(i)}\log\left(a^{[L](i)}\right) + (1-y^{(i)})\log\left(1- a^{[L](i)}\right) \large{)} }_\text{cross-entropy cost} + \underbrace{\frac{1}{m} \frac{\lambda}{2} \sum\limits_l\sum\limits_k\sum\limits_j W_{k,j}^{[l]2} }_\text{L2 regularization cost}
$$
1 | def compute_cost_with_regularization(A3, Y, parameters, lambd): |
反向传播
$$
\frac{d}{dW} ( \frac{1}{2}\frac{\lambda}{m} W^2) = \frac{\lambda}{m} W
$$
1 | def backward_propagation_with_regularization(X, Y, cache, lambd): |
Dropout
Dropout 也就是随机失活,通常用于计算机视觉领域,因为特征比较多。每个神经元结点都以固定的概率 keep-prob
随机保留,但是在 Dropout 后为了不影响 $Z$ 的期望而导致梯度消失,$Z=Z/keep-prob$,神经网络的训练过程如下所示:
对于整个网络来说,随机失活后导致网络规模变小,减缓了过拟合的发生。对于每一个神经元结点,由于它的输入随时都有可能失活,因此训练后任何一个输入的权重都不会太大,由于这个神经元自己本身也可能失活,因此 Dropout 将产生类似 L2 正则化的权重衰减的效果,但是只有当 Dropout 用于线性回归时才相当于 L2 权重衰减。
Dropout 也可以被近似认为是集成大量深层神经网络的 Bagging 方法(结合多个模型降低泛化误差),不太一样的地方是 Bagging 中所有模型都是独立的,而 Dropout 中所有模型共享参数。当可用训练样本太少时(例如 5000),Dropout 的效果不会很好。
前向传播
在前向传播时,需要生成失活矩阵 D
,前向传播后需要缓存 D
用于反向传播。需要注意的是,Dropout 会导致代价函数不明确,因此可以先不 Dropout 观察代价函数是否下降,然后在开启 Dropout;同时在测试的时候不能开启 Dropout 。
1 | def forward_propagation_with_dropout(X, parameters, keep_prob=0.5): |
反向传播
1 | def backward_propagation_with_dropout(X, Y, cache, keep_prob): |
参考文献
[1] 吴恩达. DeepLearning.
[2] Ian Goodfellow, Yoshua Bengio, Aaron Courville. Deep Learning. 人民邮电出版社. 2017.
[3] 周志华. 机器学习. 清华大学出版社. 2016.
[4] 李航. 统计学习方法. 清华大学出版社. 2017.