优化算法系列（1）：梯度下降算法与推导

深度学习（机器学习）算法 = 模型表征 + 模型评估 + 优化算法，而基本上所有的机器学习算法都在损失函数下转化为某种形式的优化问题，可以说模型训练就是一个数值优化过程。

当前，常见的深度学习优化算法大部分都是在梯度下降算法的思路上改进。可以说，梯度下降算法是优化算法的基础。本文打算从若干思路理解梯度下降算法，以便对机器学习的优化过程有更深刻的理解。

此外，还有组合优化中涉及到的算法，如模拟退火、遗传算法、蚁群算法等，它们不能在深度学习上流行的大概率原因是效率。基于梯度思想的二价优化算法同样也是效率和计算问题的原因并没有在深度学习中流行起来。

梯度计算

假设$\theta = (\theta_{1}, \dots, \theta_{n})$，那么多元函数$L(\theta)$的梯度可以表示为，

$$\nabla_{\theta}L(\theta) = (\frac{\partial L}{\partial \theta_{1}}, \dots, \frac{\partial L}{\partial \theta_{n}})$$

有些书籍上会写成这种形式，

$$\nabla_{x} f(\boldsymbol{x})=\left[\frac{\partial f(\boldsymbol{x})}{\partial x_{1}}, \frac{\partial f(\boldsymbol{x})}{\partial x_{2}}, \ldots, \frac{\partial f(\boldsymbol{x})}{\partial x_{d}}\right]^{\top}$$

本质上是一致的，只不过在不同的数学符号环境下的不同形式而已。

当$n=3$时，还可以如下表示，

$$\nabla_{\theta}L(\theta) = \frac{\partial L}{\partial \theta_{1}}\boldsymbol{i} + \frac{\partial L}{\partial \theta_{2}}\boldsymbol{j} + \frac{\partial L}{\partial \theta_{3}}\boldsymbol{k}$$

对于每个分量，

$$\frac{\partial L}{\partial \theta_{i}} = \lim_{\Delta \theta \rightarrow 0} \frac{L(\theta_i + \Delta\theta)-L(\theta_i)}{\Delta \theta}$$

以上就是梯度的简单介绍。当然，在实践中，深度学习框架由于涉及复杂函数的梯度，一般会使用自动微分的方式，可查阅相关资料，如Tensorflow的官方文档。

梯度下降算法

首先我们还是来谈谈梯度下降算法的使用场景。传统的机器学习算法的优化离不开梯度下降算法，就连深度学习场景，很多优化器都是以梯度下降算法作为基础而衍生。

损失函数用来度量一次预测的代价或差异，假设有样本 $(x, y)$ ,那么损失可以表示为 $L(y,f_{\theta}(x))$，$\theta$ 为模型 $f$ 的参数。如果有训练样本数据集 $D = { (x_{1}, y_{1}), …, (x_{n}, y_{n}) }$ ，那么整体的损失为

$$\begin{align} L(\theta) = \frac{1}{\left | D \right |} \sum_{(x,y) \in D}L(y,f_{\theta}(x)) \tag{1.1} \end{align}$$

使用梯度下降算法求解参数 $\theta$ ，如下

$$\begin{align} \theta_{n+1} = \theta_{n} - \gamma \nabla_{\theta}L(\theta_{n}) \tag{1.2} \end{align}$$

如果每次计算整体损失 $L(\theta)$ 只从 $D$​ 中选出一个样本，那么优化过程称为随机梯度下降。 如果每次只取部分（批量），则称为批量梯度下降。随机梯度下降、批量梯度下降本质上都是通过部分样本来估计梯度，这也就是随机的本意。

梯度下降的导出 （思路1）

从优化角度看，全局最优点 $\theta^{*}$ 处一定有

$$\begin{align} \frac{dL(\theta^{*})}{d\theta^{*}} = 0 \tag{2.1} \end{align}$$

使用假设法容易证明这一点。然而，通常情况下 $\theta^{n}$ 难以直接求解，我们需要迭代的方法逐步逼近它。假定有一系列的变量：$\theta_{0}, \theta_{1}, …, \theta^{n}$ ，满足

$$\begin{align} L(\theta_{0}) > L(\theta_{1}) > ... > L(\theta^{*}) \tag{2.2} \end{align}$$

更一般地，可以表示为

$$\begin{align} L(\theta_{t}) > L(\theta_{t+1}) \tag{2.3} \end{align}$$

其中 $t=0，1, 2, 3,…$ 可以化为如下形式

$$\begin{align} L(\theta_{t+1}) - L(\theta_{t}) \lt 0 \tag{2.4} \end{align}$$

损失函数$L$一阶连续可微（具体的数学性质取决于我们选择的损失函数 $L$），使用泰勒公式有

$$\begin{align} L(\theta_{t+1}) &= L(\theta_{t}+\Delta\theta) \\ &\approx L(\theta_{t}) + \Delta\theta^{T}\nabla_{\theta} L(\theta_{t}) \tag{2.5} \end{align}$$

把上式代入到（2.4）中，有

$$\Delta\theta^{\top}\nabla{\theta} L(\theta{t}) < 0 \tag{2.6}$$

选择恰当的 $\gamma>0$，只需要取

$$\Delta\theta = -\gamma\nabla_{\theta} L(\theta_{t}) \tag{2.7}$$

此处$\gamma>0$就是我们所谓的学习率，在凸优化中$\gamma$可以通过一维搜索确定，但是深度学习应用中，通常是重要的炼丹参数，需要根据个人经验调整。结合（2.5）中的 $\theta_{t+1} = \theta_{t}+\Delta\theta$，有

$$\begin{align} \theta_{t+1} = \theta_{t} - \gamma \nabla_{\theta}L(\theta_{t}) \tag{2.8} \end{align}$$

这就是我们所说的梯度下降算法。如果优化的目标函数是凸函数，那么局部极小点为全局最小点，但是如果目标函数非凸，梯度下降无法保证全局最优。以上的推导有点冗余，但看起来还是相当清晰。

梯度下降的导出（思路2）

从整个模型训练过程看，参数的取值可以看作是步数的函数，即，考虑优化过程的损失 $\theta(t)$，那么损失函数可以表示为 $L(\theta(t))$。优化的目标是期望$L(\theta(t))$以最快的速度下降。根据链式法则有

$$\frac{dL(\theta(t))}{dt} = \frac{dL(\theta)}{d\theta} \frac{d\theta(t)}{dt} \tag{3.1}$$

要使$L(\theta(t))$​下降最快，要求上式越小越好。上述可以改为如下形式，

$$\begin{align} \frac{dL(\theta(t))}{dt} &= \frac{dL(\theta)}{d\theta} \frac{d\theta(t)}{dt} \newline &= \vert \frac{dL(\theta)}{d\theta}\vert \vert \frac{d\theta(t)}{dt} \vert \cos{\alpha} \end{align}$$

为让损失最大，要求 $\alpha=2\pi$ ，于是有

$$\frac{d\theta(t)}{dt} = -\gamma\nabla_{\theta} L(\theta_{t})$$

这个思路相当几何化。

在机器学习中，$\gamma>0$ 称为学习率。此式就是我们所说的梯度下降法。此外，其收敛速度也不是最快的。当n足够大时，$\theta_{n}$ 足够接近 $\theta_{n}$，根据以上推导，我们可以设计如下算法，

$$\begin{align} \theta_{n+1} = \theta_{n} - \gamma \nabla_{\theta}L(\theta_{n}) \end{align}$$

梯度下降的导出（思路3）

以上两种思路都是从一阶出发，那么能不能从二阶出发来逼近原函数，并从中导出梯度下降思路。首先我们对原始函数进行二阶泰勒展开，即通过抛物线来局部逼近原函数，由于计算过程设计到 hessian 矩阵求逆，自然地, 我们会把二次部分取常数。

我们使用抛物线来局部逼近函数 $f(x)$ ，使用二价泰勒展开

$$\begin{align} f(x) \approx f\left(x_{n}\right)+f^{\prime}\left(x_{n}\right)\left(x-x_{n}\right)+\frac{1}{2} f^{\prime \prime}\left(x_{n}\right)\left(x-x_{n}\right)^{2} = h(x) \end{align}$$

不难求出抛物线的极值点的迭代形式，

$$x_{n+1} = x_{n}-\frac{f^{\prime}\left(x_{n}\right)}{f^{\prime \prime}\left(x_{n}\right)}$$

事实上，这种思路和思路（1）类似，只不过使用了二价泰勒级数展开。这就是牛顿法的迭代公式，可以参考历史文章牛顿迭代法的导出。令$\alpha = \frac{1}{f’’(x)}$，有

$$x_{n+1} = x_n - \alpha f'(x_n)$$

这里的$\alpha$可以理解为步速因子，即以多大的速度更新$x_n$​。牛顿法则是使用$f’’(x)$的倒数来控制步速。为化简步速，我们把它改为常数也可以，

$$x_{n+1} = x_n - \gamma f'(x_n)$$

推广到一般形式就是，

$$\boldsymbol{x}_{n+1} = \boldsymbol{x}_{n} - \gamma \nabla_{\boldsymbol{x} }f(\boldsymbol{x}_{} )$$

于是得到梯度下降的一般形式。

简单分析

梯度下降算法在深度学习中有个致命的缺点，就是每个都使用全量的数据估算梯度，即

$$\begin{align} \nabla_{\theta} L(\theta) = \nabla_{\theta}\Big[\frac{1}{\left | D \right |} \sum_{(x,y) \in D}L(y,f_{\theta}(x)) \Big] \end{align}$$

每一轮的迭代都要对上万甚至百万的样本计算梯度，这个计算力是支撑不起的，即便计算里足够，也要消耗巨大的内存（显存）。

总结

以上我们谈了梯度下降算法的三种导出（理解）思路。这三种思路均在欧几里得空间上的推导，其实梯度下降算法并不止于欧几里得空间，还可以是黎曼空间。有兴趣的读者可以查阅相关文献。同时也指出单纯的GD方案消耗非常大的计算力且耗费内存（显存）。下篇深入分析GD的改进版本SGD。

参考文献

[1] How Does Batch Normalization Help Optimization?

[2] https://tensorflow.google.cn/api_docs/python/tf/keras/optimizers/Optimizer

[3] https://tensorflow.google.cn/api_docs/python/tf/keras/optimizers