机器学习优化理论 —— 学习笔记

发布时间：2024-05-06 05:08:38 人气：作者：佚名

优化是应用数学的一个分支，也是机器学习的核心组成部分。实际上，机器学习算法=模型表征 + 模型
评估 + 优化算法。其中，优化算法所做的事情就是在模型表征空间中找到模型评估指标最好的模型。
    随着大数据和深度学习的迅猛发展，在实际应用中面临的大多是大规模、高度非凸的优化问题，这给
传统的基于全量数据、凸优化的优化理论带来了巨大的挑战。

1、常见损失函数及特点
2、凸函数

2.1 凸函数性质
2.2 凸函数的证明
2.3 非凸函数的证明

3、经典优化算法

3.1 直接法
3.2 迭代法

4、梯度下降法

4.1 随机梯度下降法
4.2 动量法
4.3 AdaGrad
4.4 Adam

5、参考资料

分类损失函数

$L_{hinge}(f,y)=max\\{0, 1-fy\\}$

Hinge损失函数是0-1损失函数相对紧的凸上界,且当fy≥1时，该函数不对其做任何惩罚。Hinge损失在
fy=1处不可导，因此不能用梯度下降法进行优化，而是用次梯度下降法。

$L_{logistic}(f,y)=log_2(1+exp(-fy))$

该函数处处光滑，因此可以用梯度下降法进行优化。但是，该损失函数对所有的样本点都有所惩罚，因此
对异常值相对更敏感一些。

$L_{Cross Entropy}(f,y)=-log_2(\\frac{1+fy}{2})$

当预测值属于[-1，1]时，另一个常用的代理损失函数是交叉熵

回归损失函数

$L_{square}(f,y)=(f-y)^2$

平方损失函数是光滑函数，能够用梯度下降法进行优化。然而，当预测值距离真实值越远时，平方损失函数
的惩罚力度越大，因此它对异常点比较敏感。为了解决该问题，可以采用绝对损失函数

$L_{absolute}(f,y)=|f-y|$

绝对损失函数相当于是在做中值回归，相比做均值回归的平方损失函数，绝对损失函数对异常点更鲁棒
一些。但是，绝对损失函数在f=y处无法求导数。综合考虑可导性和对异常点的鲁棒性，可以采用
Huber损失函数

$L_{Huber}(f,y)=\\begin{equation}\\left\\{ \\begin{aligned}(f-y)^2,|f-y| \\leq \\delta \\\\ 2\\delta|f-y|-\\delta^2,|f-y|>\\delta \\end{aligned}\\right. \\end{equation}$

Huber损失函数在|f?y|较小时为平方损失，在|f?y|较大时为线性损失，处处可导， 且对异常点鲁棒。

2.1 凸函数性质

什么是凸函数？
它的严格定义为，函数L(·) 是凸函数当且仅当对定义域中的任意两点x，y和任意实数λ属于[0,1]总有

$L(\\lambda x+(1-\\lambda)y)\\leq \\lambda L(x) + (1-\\lambda)L(y)$

该不等式的一个直观解释是，凸函数曲面上任意两点连接而成的线段，其上的任意一点都不会处于该函数
曲面的下方。

2.2 凸函数的证明

计算目标函数的二阶Hessian矩阵，若该矩阵半正定，则为凸函数

2.3 非凸函数的证明

只要找到，不满足凸函数定义的点，即为非凸函数，一般常用反证法进行证明。

3.1 直接法

直接法，顾名思义，就是能够直接给出优化问题最优解的方法。这个方法听起来非常厉害的样子，但它不
是万能的。直接法要求目标函数需要满足两个条件。
    第一个条件是，L(·)是凸函数。若L(·)是凸函数，那么θ是最优解的充分必要条件是L(·)在θ处的
梯度为0，即

$\\Delta L(\ heta^*)=0$

第二个条件是，上式有闭式解。同时满足这两个条件的经典例子是岭回归，其目标函数为

$L(\ heta)=||X\ heta-y||_2^2 + \\lambda||\ heta||_2^2$

得到最优解为

$\ heta^*=(X^TX+\\lambda I)^{-1}X^Ty$

3.2 迭代法

一阶法

其中α称为学习率。一阶法也称梯度下降法，梯度就是目标函数的一阶信息。

二阶法

二阶法也称为牛顿法，Hessian矩阵就是目标函数的二阶信息。二阶法的收敛速度一般要远快于一阶法，
但是在高维情况下，Hessian矩阵求逆的计算复杂度很大，而且当目标函数非凸时，二阶法有可能会收敛
到鞍点.

4.1 随机梯度下降法

经典的梯度下降法采用所有训练数据的平均损失来近似目标函数，即

$L(\ heta)=\\frac{1}{M}\\sum^M_{i=1}L(f(x_i,\ heta), y_i)$

经典的梯度下降法在每次对模型参数进行更新时，需要遍历所有的训练数据。当M很大时，这需要很大的计
算量，耗费很长的计算时间，在实际应用中基本不可行。
    为了解决该问题，随机梯度下降法（Stochastic Gradient Descent，SGD）用单个训练样本的
损失来近似平均损失。即

$L(\ heta)=L(f(x_i,\ heta), y_i)$

为了降低随机梯度的方差，从而使得迭代算法更加稳定，也为了充分利用高度优化的矩阵运算操作，在实际
应用中我们会同时处理若干训练数据，该方法被称为小批量梯度下降法。

$L(\ heta)=\\frac{1}{m}\\sum^m_{i=1}L(f(x_i,\ heta), y_i)$

对于小批量梯度下降法的使用，有以下三点需要注意的地方。
    1）如何选取参数m？在不同的应用中，最优的m通常会不一样，需要通过
调参选取。一般m取2的幂次时能充分利用矩阵运算操作，所以可以在2的幂次中挑选最优的取值，
例如32、64、128、256等。
    2）如何挑选m个训练数据？为了避免数据的特定顺序给算法收敛带来的影响，一般会在每次遍历训练
数据之前，先对所有的数据进行随机排序，然后在每次迭代时按顺序挑选m个训练数据直至遍历完所有的数据。
    3）如何选取学习速率α？为了加快收敛速率，同时提高求解精度，通常会采用衰减学习速率的方案：
一开始算法采用较大的学习速率，当误差曲线进入平台期后，减小学习速率做更精细的调整。最优的学习
速率方案也通常需要调参才能得到。
    综上，通常采用小批量梯度下降法解决训练数据量过大的问题。每次更新模型参数时，只需要处理m个
训练数据即可，其中m是一个远小于总数据量M的常数，这样能够大大加快训练过程。

4.2 动量法

思想：
    为了解决随机梯度下降法山谷震荡和鞍点停滞的问题，我们做一个简单的思维实验。想象一下纸团在
山谷和鞍点处的运动轨迹，在山谷中纸团受重力作用沿山道滚下，两边是不规则的山壁，纸团不可避免地
撞在山壁，由于质量小受山壁弹力的干扰大，从一侧山壁反弹回来撞向另一侧山壁，结果来回震荡地滚下；
如果当纸团来到鞍点的一片平坦之地时，还是由于质量小，速度很快减为零。纸团的情况和随机梯度下降法
遇到的问题简直如出一辙。直观地，如果换成一个铁 球，当沿山谷滚下时，不容易受到途中旁力的干扰，
轨迹会更稳更直；当来到鞍点中心处，在惯性作用下继续前行，从而有机会冲出这片平坦的陷阱。
    模型参数的迭代公式为

$v_t=\\gamma v_{t-1}+\\eta g_t$

$\ heta_{t+1}=\ heta_t-v_t$

4.3 AdaGrad

AdaGrad方法采用“历史梯度平方和”来衡量不同参数的梯度的稀疏性，取值越小表明越稀疏，具体的更新
公式表示为

4.4 Adam

Adam方法将惯性保持和环境感知这两个优点集于一身。一方面，Adam记录梯度的一阶矩即过往梯度与当前
梯度的平均，这体现了惯性保持；另一方面，Adam还记录梯度的二阶矩，即过往梯度平方与当前梯度平方
的平均，这类似AdaGrad方法，体现了环境感知能力，为不同参数产生自适应的学习速率。一阶矩和二阶矩
采用类似于滑动窗口内求平均的思想进行融合，即当前梯度和近一段时间内梯度的平均值，时间久远的梯度
对当前平均值的贡献呈指数衰减。

《百面机器学习》

机器学习 优化理论 —— 学习笔记

机器学习优化理论 —— 学习笔记