【机器学习】梯度下降
Gradient Descent 梯度下降
梯度下降 (Gradient Descent) 的直观解释
得到 loss function 之后，我们需要一种方法求解其最小值解 \(\theta = \arg \min L(\theta)\). 这种方法最好满足以下条件：
- 对任何 Loss function 都是通用的
- 在能求得目标解的条件下，越快越好
首先看第一个条件. 怎样才能找到对任何函数都能通用的办法呢？想象一下假如我们在下山，但是对周围的路况一无所知，我们如何判断更低的地方在哪里呢？这个 task 太难了，我们得给出一些条件，比如 \(L(\theta)\) 是一阶可微的，这样我们就能环顾四周，从而知道哪个方向比目前所处的位置高，哪个方向比所处的位置低了. 我们猜想顺着低处走就可以下山了，而且步子迈大一点就走得快，迈小一点就走得慢. 把下山整理成数学语言就是：
- \(L(\theta)\) 目前的海拔
- \(-\dfrac{d L(\theta)}{d \theta} = -\nabla L(\theta)\) 地势下降最快的方向
- \(\eta\) 步长 / 学习率 (learning rate)
第 \(t\) 步梯度下降的公式
\]
以上介绍的方法又称为 Vanilla Gradient Descent.
梯度下降的影响因素
除公式外，梯度下降的结果还受到以下几个因素的影响：
- 学习率 \(\eta\)
- 样本数量
- 特征尺度
- 损失函数
学习率对梯度下降的影响
仍以下山为例，如果步子太小，下山得下到猴年马月啊；步子太大，一个筋斗云过去都不知道自己在哪儿了.
- （静态观点）学习率太小导致收敛过慢，学习率太大导致不收敛
而在山顶的时候可以走快一点，到山脚就不用那么着急了.
- （动态观点）刚开始学习率较大，训练末期学习率较小
静态观点要求选择一个合适的初始值，这个值是ad hoc的（或者说是超参数）；动态观点要求适当地变化学习率. 一种方法是 Adagrad（注意，很多 Ada 开头的模型指的都是 adaptive 的方法）：
\]
里面的 \(\odot\) 表示 element-wise dot，其他运算符也都是 element-wise 操作. 这样梯度越大的方向，分母上的惩罚也就越大，也就是限制往梯度最大的方向移动. 就好像人在山谷中行走，两侧梯度大，Adagrad方法会限制人尽量少地往两边走，这样就能更快地前进. 又比如现在处在斜面上，Vanilla会先顺着斜面冲到底，然后再考虑向左还是向右；Adagrad 会一边横向走一边顺着斜面下降，这样走得距离更短，还有可能避开 local minimum
还有一种解释是类比牛顿法，根号里的内容可以看作是二阶微分大小的一种表示，而且是通过历史的一阶微分来表示的。
样本数量
- 如果我们用所有的样本来求梯度，那么就称为 (Batch) Gradient Descent
- 如果我们只用一个样本来求梯度，那么就称为 Stochastic Gradient Descent
- 如果我们用一部分样本来求梯度，那么就称为 Mini-batch Gradient Descent
类似的定义还有 Online learning 和 Offline learning
- Online learning = Stochastic Gradient Descent，当然收集几个数据再做 Mini-batch 也是可以的
- Offline learning = (Batch) Gradient Descent，当让想用 Batch 或者 Mini-batch 也是可以的
总的规律是：一次下降中使用的样本越少，梯度波动也就越大，学习率也要相应的调小，但是 iteration 的次数会更多，下降得更快；反之同理.
调整 batchsize 时，需要相应调整学习率. batch 越大，学习率也越大，这样才能保证 epoch 差不多时结果差不多.
特征尺度
如果某个特征 A 的范围是 0~1000，另一个特征 B 的范围是 0~1，那么特征 A 在损失函数中所占的比重会远远高于特征 B 的比重，梯度下降就会忽略特征 B 而全力学习特征 A. 为了消除这种不平衡，需要对先做 Feature Scaling，把每个特征都转化到大致相等的范围内. 常用的方法有
- min-max
- Z-score
损失函数
对于非凸的损失函数，梯度下降可能陷入局部极小值. 目前已知的凸函数模型有：
- Linear Regression, MLE Loss
- Logistic Regression, Cross Entropy Loss 证明
其他优化方法
还有一些著名的优化方法，比如：
-
SGD with momentum (SGDM)
\[v^{t+1} = \lambda v^t – \eta \nabla L(\theta^t) \\
\theta^{t+1} = \theta^t + v^{t+1}
\]SGDM 的优点
- 下降的速度更快
- 不会卡在梯度为零的点（比如鞍点），因为有惯性
- 可能冲出一些 local optima 的范围从而走向 global optima
-
RMSProp
\[\theta^{t+1} = \theta^t – \frac{\eta}{\sqrt{v^t}}\odot g^t \\
v^1 = g^0 \odot g^0 \\
v^t = \alpha v^{t-1} + (1-\alpha) g^{t-1} \odot g^{t-1}
\]解决 Adagrad 存在的一些问题：
- Adagrad 没有衰减，原始梯度会持续地影响后续的训练. 如果开始梯度很大的话，后面的步长就会很小. RMSProp 引入衰减系数解决这个问题
-
Adam
Adam相当于 SGDM 和 RMSProp 的结合
\[\theta^{t+1} = \theta^t – \frac{\eta}{\epsilon+\sqrt{v^{t+1}}}\odot \hat m^t \\
m^t = \beta_1 m^{t-1} + (1-\beta_1) g^{t-1}, \hat m^t = \frac{m^t}{1-\beta_1^t}\\
v^t = \beta_2 v^{t-1} + (1-\beta_v) g^{t-1} \odot g^{t-1}, v^t = \frac{v^t}{1-\beta_2^t}\\
\beta_1=0.9, \beta_2=0.999, \epsilon=10^{-8}
\]
到此为止，所有的模型训练方法基本都被囊括了。一般论文中能用到的模型也就是 Adam 和 SGDM，二者的对比如下：
| Speed | Generalization | Stable | |
|---|---|---|---|
| Adam | √ | ||
| SGD | √ | √ |
