机器学习中的正则化
机器学习中的正则化 - Regularization
目录
- 先验知识
- L0正则[范数]
- L1正则[范数]
- L2正则[范数]
- L1和L2的区别
1. 先验知识
监督机器学习问题是在规则化参数的同时最小化误差。最小化误差是为了让我们的模型拟合我们的训练数据,而规则化参数是防止我们的模型过分拟合我们的训练数据。 因为参数太多,会导致我们的模型复杂度上升,容易过拟合。但训练误差小并不是我们的最终目标,我们的目标是希望模型的测试误差小,也就是能准确的预测新的样本。 所以,我们需要保证模型“简单”的基础上最小化训练误差,这样得到的参数才具有好的泛化能力,而模型“简单”就是通过规则函数来实现的。 另外,规则项的使用还可以约束我们的模型的特性。这样就可以将人对这个模型的先验知识融入到模型的学习当中,强行地让学习到的模型具有人想要的特性,例如稀疏、低秩、平滑等等。
还有几种角度来看待规则化的。 规则化符合奥卡姆剃刀(Occam’s razor)原理:在所有可能选择的模型中,选择能够很好地解释已知数据并且简单的模型。 从贝叶斯估计的角度来看,规则化项对应于模型的先验概率。 还有个说法,规则化是结构风险最小化策略的实现,是在经验风险上加一个正则化项(regularizer)或惩罚项(penalty term)。
一般来说,监督学习可以看作最小化下面的目标函数:
其中,第一项$L(yi,f(xi;w))$衡量我们的模型对第$i$个样本的预测值$f(x_i;w)$和真实的标签$y_i$之前的误差。 因为模型是要拟合训练样本,所以要求这一项最小,也就是要求模型尽量的拟合训练数据。 但正如上面说言,不仅要保证训练误差最小,更希望模型测试误差小,所以需要加上第二项,也就是对参数$w$的规则化函数$\Omega(w)$去约束模型尽量的简单。
对于第一项Loss函数,不同的loss函数,具有不同的拟合特性,具体问题具体分析:
- 如果是Square loss,是最小二乘
- 如果是Hinge Loss,是SVM
- 如果是exp-Loss,是Boosting
- 如果是log-Loss,是Logistic Regression
- 等等
规则化函数$\Omega(w)$也有很多种选择,一般是模型复杂度的单调递增函数,模型越复杂,规则化值就越大。
- 零范数
- 一范数
- 二范数
- 迹范数
- Frobenius范数(对应元素的平方和再开方) $ \sqrt{\sum_{i=1}^m \sum_{j=1}^n | a_{ij} | ^2} $
- 核范数 $ tr(\sqrt{X^TX}) $
- 等等
2. L0正则[范数]
定义: L0范数是指向量中非0的元素的个数。
如果我们用L0范数来规则化一个参数矩阵W的话,就是希望W的大部分元素都是0,换句话说就是让参数W是稀疏的。
所以L0范数非常适合机器学习中稀疏编码,特征选择。但是由于L0范数很难优化求解(NP难问题),而L1范数又是L0范数的最优凸近似[??],故通常用L1范数来代替。
其他可以参考Emmanuel Candes的工作。
3. L1正则[范数]
定义:L1范数是指向量中各个元素绝对值之和。
L1范数和L0范数可以实现稀疏,L1因具有比L0更好的优化求解特性而被广泛应用。
3.1 参数稀疏的优势
(1)特征选择
大家对稀疏规则化趋之若鹜的一个关键原因在于它能实现特征的自动选择。 一般来说,$x_i$的大部分元素(也就是特征)都是和最终的输出$y_i$没有关系或者不提供任何信息的,在最小化目标函数的时候考虑$x_i$这些额外的特征,虽然可以获得更小的训练误差,但在预测新的样本时,这些没用的信息反而会被考虑,从而干扰了对正确$y_i$的预测。 稀疏规则化算子的引入就是为了完成特征自动选择的任务,它会学习地去掉这些没有信息的特征,也就是把这些特征对应的权重置为0。
(2)可解释性
另一个理由是,模型更容易解释。 例如患某种病的概率是$y$,假设收集到的数据$x$是1000维的,也就是需要寻找这1000种因素到底是怎么影响患上这种病的概率的。 假设我们这个是个回归模型:$ y = w_1 x_1 + w_2 x_2 + … + w_1000 x_1000 + b$(当然了,为了让y限定在[0,1]的范围,一般还得加个Logistic函数)。 通过学习,如果最后学习到的$w^{\ast}$就只有很少的非零元素,例如只有5个非零的$w_i$,那么我们就有理由相信,这些对应的特征在患病分析上面提供的信息是巨大的,决策性的。 也就是说,患不患这种病只和这5个因素有关,那医生就好分析多了。但如果1000个$w_i$都非0,医生面对这1000种因素就无从下手。
4. L2正则[范数]
定义:欧式距离
L2正则对于改善过拟合具有强大的功效。 让L2范数的规则项最小,可以使得$w$的每个元素都很小,都接近于0,但与L1范数不同,它不会让它等于0,而是接近于0。而越小的参数说明模型越简单,越简单的模型则越不容易产生过拟合现象。
1 | 为什么参数越小模型越简单? |
通过L2范数,可以实现对模型空间的限制,从而在一定程度上避免了过拟合。
说到可以避免过拟合,就要涉及到条件数(详见 条件数-维基百科, 矩阵条件数-百度百科)
从优化或者数值计算的角度来说,L2范数有助于处理条件数不好的情况下矩阵求逆很困难的问题。 优化有两大难题,一是:局部最小值,二是:病态(ill-condition)问题。前者找的是全局最小值,如果局部最小值太多,那优化算法就很容易陷入局部最小而不能自拔,这不是我们愿意看到的。 病态对应着良置(well-condition),假设我们有个方程组$AX=b$,我们需要求解$X$。如果$A$或者$b$稍微的改变,会使得$X$的解发生很大的改变,那么这个方程组系统就是病态的, 反之就是良置的。
下面看个例子:
先看左边,第一行假设是$AX=b$,第二行稍微改变下$b$,得到的$x$和没改变前的差别很大,第三行稍微改变下系数矩阵$A$,可以看到结果的变化也很大。 换句话来说,这个系统的解对系数矩阵$A$或者$b$太敏感了。又因为一般系数矩阵$A$和$b$是从实验数据里面估计得到的,所以是存在误差的,如果系统对这个误差是可以容忍的就还好, 但系统对这个误差太敏感了,以至于解的误差更大,那这个解就太不靠谱了。所以这个方程组系统就是病态(ill-conditioned)的,不正常的,不稳定的,有问题的。右边那个就叫良置(well-condition)的系统。 上面的条件数就是拿来衡量病态系统的可信度的。条件数衡量的是输入发生微小变化的时候,输出会发生多大的变化,也就是系统对微小变化的敏感度。条件数值小的就是良置的,大的就是病态的。
对条件数来个总结:条件数是一个矩阵(或者它所描述的线性系统)的稳定性或者敏感度的度量,如果一个矩阵的条件数在1附近,那么它就是良置的, 如果远大于1,那么它就是病态的,如果一个系统是病态的,它的输出结果可信度就很低。
回到第一句话:从优化或者数值计算的角度来说,L2范数有助于处理条件数不好的情况下矩阵求逆很困难的问题。 因为目标函数如果是二次的,对于线性回归来说,那实际上是有解析解的,求导并令导数等于零即可得到最优解为:
然而,如果当样本$X$的数目比每个样本的维度还要小的时候,矩阵$X^TX$将会不是满秩的,也就是$X^TX$会变得不可逆,所以$w^{\ast}$就没办法直接计算出来了。 或者更确切地说,将会有无穷多个解(因为我们方程组的个数小于未知数的个数)。也就是说,我们的数据不足以确定一个解,如果我们从所有可行解里随机选一个的话,很可能并不是真正好的解,总而言之,我们过拟合了。
但如果加上L2规则项,就变成了下面这种情况,就可以直接求逆了:
要得到这个解,通常并不直接求矩阵的逆,而是通过解线性方程组的方式(例如高斯消元法)来计算。 考虑没有规则项的时候,也就是$\lambda=0$的情况,如果矩阵$X^TX$的条件数很大的话,解线性方程组就会在数值上相当不稳定,而这个规则项的引入则可以改善条件数。
另外,如果使用迭代优化的算法,条件数太大仍然会导致问题:它会拖慢迭代的收敛速度,而规则项从优化的角度来看,实际上是将目标函数变成$ \lambda-strongly convex, (\lambda$强凸)的了。
关于强凸和普通凸的对比,看下图[其他详细数学内容自行查阅资料]:
设最优解为$w^{\ast}$指向的地方。如果我们的函数$f(w)$,见左图,也就是红色那个函数,都会位于蓝色虚线的那根二次函数之上,这样就算$w_t$和$w^{\ast}$离的比较近的时候,$f(wt)$和$f(w^{\ast})$的值差别还是挺大的,也就是会保证在最优解$w^{\ast}$附近的时候,还存在较大的梯度值,这样才可以在比较少的迭代次数内达到$w^{\ast}$。 但对于右图,红色的函数$f(w)$只约束在一个线性的蓝色虚线之上,假设是如右图的很不幸的情况(非常平坦),那在$w_t$还离我们的最优点$w^{\ast}$很远的时候,我们的近似梯度$(f(w_t)-f(w^{\ast}))/(w_t-w^{\ast})$就已经非常小了,在$w_t$处的近似梯度$\partial f / \partial w $就更小了,这样通过梯度下降,我们得到的结果就是$w$的变化非常缓慢。 如果要获得强凸性质怎么做?最简单的就是往里面加入一项$ (\alpha/2)* || w ||^2 $。
一言以蔽之:L2范数不但可以防止过拟合,还可以让优化求解变得稳定和快速。
5. L1和L2的区别
5.1 下降速度
L1和L2都是规则化的方式,将权值参数以L1或者L2的方式放到代价函数里面去。然后模型就会尝试去最小化这些权值参数。而这个最小化就像一个下坡的过程,L1和L2的差别就在于这个“坡”不同,如下图:L1就是按绝对值函数的“坡”下降的,而L2是按二次函数的“坡”下降。所以实际上在0附近,L1的下降速度比L2的下降速度要快。所以会非常快得降到0。
L1又称Lasso,L2又称Ridge。
5.2 模型空间的限制
实际上,对于L1和L2规则化的代价函数来说,我们可以写成以下形式:
也就是说,我们将模型空间限制在$w$的一个L1-ball中。 为了便于可视化,我们考虑两维的情况,在$ (w_1, w_2) $平面上可以画出目标函数的等高线,而约束条件则成为平面上半径为C的一个norm ball。等高线与norm ball首次相交的地方就是最优解:
可以看到,L1-ball与L2-ball的不同就在于L1在和每个坐标轴相交的地方都有“角”出现,而目标函数的等高线除非位置摆得非常好,大部分时候都会在角的地方相交。 注意到在角的位置就会产生稀疏性,例如图中的相交点就有$w_1=0$,而更高维的时候(想象一下三维的L1-ball 是什么样的?)除了角点以外,还有很多边的轮廓也是既有很大的概率成为第一次相交的地方,又会产生稀疏性。 相比之下,L2-ball就没有这样的性质,因为没有角,所以第一次相交的地方出现在具有稀疏性的位置的概率就变得非常小了。这就从直观上来解释了为什么L1正则能产生稀疏性,而L2正则不行的原因了。
因此总结:L1会趋向于产生少量的特征,而其他的特征都是0,而L2会选择更多的特征,这些特征都会接近于0。Lasso在特征选择时候非常有用,而Ridge就只是一种规则化而已。