LionKing数据科学专栏

购买普通会员高级会员可以解锁网站精华内容且享受VIP服务的优惠

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏

梯度下降法(gradient descent)

梯度(gradient)的定义

梯度是对多元函数定义的导数,假设有函数$f: \mathbb{R}^k \rightarrow \mathbb{R}$,我们定义$f$在点$(x_1, \ldots, x_k)$处的梯度为$f$在各个方向上的偏导数(partial derivative)组成的向量。

$$\nabla f|_{x_1, \ldots, x_k} = \begin{bmatrix} \frac{\partial f}{\partial x_1}|_{x_1, \ldots, x_k}\\ \vdots\\ \frac{\partial f}{\partial x_k}|_{x_1, \ldots, x_k} \end{bmatrix}$$

例如$f(x_1, x_2) = x_1^2 + x_2^3$,则偏导数$$\frac{\partial f}{\partial x_1} = 2x_1, \frac{\partial f}{\partial x_2} = 3x_2^2$$梯度为$$\nabla f = \begin{bmatrix}2x_1\\3x_2^2\end{bmatrix}$$

从某种意义上来讲,梯度是一个函数上升/下降最快的方向。

梯度下降法

梯度下降法是一种对函数进行最小化的方法。与之完全对称的,对函数进行最大化的方法,称为梯度上升法。梯度上升法完全等价于对$-f$使用梯度下降法,这里略去讨论。

梯度下降法的算法如下:

其中$\alpha$是超参数(hyperparameter),被称为学习速率(learning rate)。

梯度下降法的几何直观

负梯度与函数等高线$f(x) = C$在$(x_1, \ldots, x_p)$处切线正交/垂直(orthogonal/perpendicular),几何上,可以认为梯度下降法是在不断地以最快的速度滑向值最小的等高线,因此也被称为最速下降法(steepest descent)。

学习速率的选择

当$\alpha$充分小时,只要函数满足光滑可导等非常基本的性质,则$f$的值始终会单调递减,最终一定会收敛到局部最优解。过于小的$\alpha$的问题是学习过于缓慢,甚至会由于数值精度问题出现停止更新的情况。当$\alpha$太大时,反而会出现overshoot现象,即由于每一步改动过大增加了$f$的值。

因此需要检测学习曲线(learning curve),即函数值$f(x)$关于迭代次数$b$的曲线,用以决定是否需要更大或更小的学习速率。

梯度下降法的优缺点

梯度下降法的优点有:

梯度下降法的缺点有:

实例

我们来看一个简单的实例:

优化$f(x) = (x - 1)^2$。我们知道$f$的全局最优解为$\hat{x} = 1$。假设初值为$x^1 = 5$。我们观察不同$\alpha$的表现。

假设已经有$x^b$,我们首先计算梯度下降的更新公式:

$$x^{b + 1} = x^b - \alpha \nabla f|_{x = x^b} = x^b - 2\alpha(x^b - 1)$$

$$x^{b + 1} - 1 = (x^b - 1)(1 - 2\alpha)$$

$$|x^{b} - 1| = |x^1 - 1||1 - 2\alpha|^{b - 1}$$

当$|1 - 2\alpha| \gt 1$即$\alpha \gt 1$时,$x^b - 1$的绝对值会趋于正无穷,出现overshoot。

当$|1 - 2\alpha| = 1$即$\alpha = 1$时,$x^b - 1$的绝对值保持不变,解来回震荡但不收敛。

当$|1 - 2\alpha| \lt 1$即$\alpha \lt 1$时,$x^b - 1$的绝对值趋于0,$x^b$收敛到最优解$\hat{x} = 1$。

左图为学习曲线(learning curve),右图为各个学习速率对应的路径。

可以发现当$\alpha = 0.05$时,在第20步之后函数收敛到了最小值0;而在$\alpha = 0.5$时函数一步就收敛到最小值;$\alpha = 0.8$用了4步左右收敛到最小值;而$\alpha \gt 1$时出现了overshoot的现象。

线性回归

在线性回归的章节中,我们提到了使用随机梯度下降可以学习线性回归模型的参数。这里我们给出批量梯度下降(batch gradient descent)解线性回归问题的公式。

假设数据矩阵为$$X = \begin{bmatrix} 1 & x_1^{(1)} & \ldots & x_p^{(1)}\\ 1 & x_1^{(2)} & \ldots & x_p^{(2)}\\ \vdots & \vdots & \ddots & \vdots\\ 1 & x_1^{(n)} & \ldots & x_p^{(n)} \end{bmatrix}$$目标变量为$$y = \begin{bmatrix} y^{(1)}\\ \vdots\\ y^{(n)} \end{bmatrix}$$

待求参数为$\beta = \begin{bmatrix} a_0\\ a_1\\ \vdots\\ a_p \end{bmatrix}$要求$\|X\beta - y\|_2^2$最小化。

则梯度下降法的算法如下:

下面是用Python实现的一个例子

下图显示了均方误差随迭代次数的变化

相比直接使用正规方程$X^TX\beta = X^Ty$求解$\hat{\beta}$。梯度下降法需要调整学习速率$\alpha$,且在数据量较小时优势不明显。但在数据量很大,或者数据是在线数据,即一直会有新的样本进入时,则梯度下降法更为合适。梯度下降法的另一个优势是如果数据会有不断变动的参数,那么只要不断根据新的样本更新模型的参数,就能够得到随着时间而变化的参数,可以更好的抓住趋势。

更多最优化相关问题见本网站论坛最优化版面

更多面试问题见面试真题汇总

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏