机器算法验证 - 如果学习率太大，梯度下降会爆炸 - 吾爱随笔录

如果学习率太大，梯度下降会爆炸

机器算法验证 Python 最小二乘梯度下降计算统计

2022-03-24 03:15:53

我已经为 OLS 实现了自己的梯度下降算法，代码如下。但是，当学习率太大（即 learn_rate >= .3）时，我的方法是不稳定的。系数爆炸，我得到一个溢出错误。我知道如果我的学习率太大，我会得到不好的结果。该算法将采取太大的步骤并不断错过最佳状态。然而，鉴于 OLS 损失函数是一个凸优化问题，我很惊讶大的学习率会导致爆炸性的系数估计。任何见解将不胜感激（以及编码建议，虽然我知道这不是那种谈话的正确地方）

import pandas as pd
import numpy as np
y1 = np.array([0, 1, 2])
X1 = np.array([[0, 0], [1, 1], [2, 2]])

def gradient_descent(LHS, RHS, N, learn_rate, tol, params, max_iter):
    #Append intercept
    constant = np.ones((N, 1))
    RHS = np.hstack((constant, RHS))

    #Define Gradient - Using Matrix Notation
    def gradient(X, y, p):
        grad_part1 = -2*np.dot(np.transpose(X),y)
        grad_part2 = 2*np.dot(np.dot(np.transpose(X), X), p)
        return((1/len(y))*(grad_part1 + grad_part2))

    #Define Gradient update
    def param_update(p,lr,X,y):
        return(p - lr*gradient(X, y, p))

    #Check if we start at optimia
    old_params = params
    params = param_update(params, learn_rate, RHS, LHS)

    if all(abs(params - old_params) <= tol):
        return(params)
    #If not, run gradient descent
    else:
        iter = 1
        while(any(abs(params - old_params)) > tol and iter < max_iter):
            old_params = params
            params = param_update(params, learn_rate, RHS, LHS)
            iter += 1
        return([params, iter])

LHS = y1.reshape(len(y1),1)
RHS = X1

myres = gradient_descent(LHS, RHS, len(LHS), .1, .1, np.array([[1], [1], [1]]), 10000)
myres = gradient_descent(LHS, RHS, len(LHS), .3, .1, np.array([[1], [1], [1]]), 10000)

2个回答

学习率可以看作步长，。因此，梯度下降正朝着最小值的方向采取连续的步骤。如果步长太大，它可以（似是而非地）“跳过”我们试图达到的最小值，即。我们超调。这可能导致在最小值附近的密切接触，或者在某些情况下导致完全背离。重要的是要注意，梯度下降所采用的步长是步长以及梯度值的函数。如果我们处于梯度为零的局部最小值，算法将不会更新参数，因为梯度为零，类似地，如果处于“陡坡”中，即使是小的 $\eta$ $\eta$ $\eta$ $g$ $p$ $p$ $\eta$ 将导致值的大量更新。 $p$

特别是对于发散的情况，一旦从初始点，梯度下降算法就会降落到比在成本方面。在这个新的但成本函数更差的点处，当重新计算梯度时，梯度值会增加，因此下一个（希望是纠正的）步骤甚至更大。然而，如果下一步导致点的误差更大，因为我们再次过冲，我们可能会被引导使用更大的梯度值，最终导致梯度值不断增加和“系数爆炸”的恶性循环" $\eta$ $p_{i=0}$ $p_{i=1}$ $p_{i=0}$ $p_{i=1}$ $p_{i=2}$ $p_i$ .

在您提供的代码中，您可能希望在函数中添加一条print(gradient(X, y, p))语句。param_update如果是加法，我们可以监控每次迭代中的梯度，并看到在合理的值的情况下，梯度值缓慢下降，而在不合理的大的情况下，梯度值逐渐变大。 $\eta$ $\eta$

梯度下降的高级变体使用自适应学习率的概念，优化算法Adadelta就是一个著名的例子。我们可能希望通过使用稳步减小的步长来玩这个概念的玩具版本。假设我们从开始，我们可以根据以下公式缩放用于次迭代的步长。请注意，如果我们自适应地减小，我们需要从一个相当大的（比如你的例子）。 $\eta = \eta_0$ $\eta_t$ $t$ $\eta_t = \frac{\eta_0}{t}$ $\eta$ $\eta_0$ 1.0

有理论结果表明，梯度下降（GD）保证收敛，因为我们根据手头的问题 $\eta$

据了解，您希望最小化最小二乘成本，其中是您的决策变量， ,是给定数据。这个成本的梯度是，与您的代码一致。 $f(p) = (1/3)\|y - Xp\|_2^2$ $p$ $X$ $y$ $\nabla f(p) = (2/3)(X^\top Xp - X^\top y)$

为了选择保证收敛我们说函数是 -smooth 如果，对于所有。，GD 会收敛。由于最小二乘成本是平滑的，我们只需要估计它的参数。根据您的问题，我们有为 $\eta$ $f$ $\beta$ $\|\nabla f(u) - \nabla f(v)\|_2 \leq \beta\|u - v\|_2$ $u,v$ $\eta \leq 1/\beta$ $\beta$

\begin{aligned} ‖ \nabla f (u) - \nabla f (v) ‖_{2} & = (2 / 3) ‖ X^{⊤} X u - X^{⊤} X v ‖_{2} \\ \leq (2 / 3) ‖ X^{⊤} X ‖_{2} ‖ u - v ‖_{2} \\ = (20 / 3) ‖ u - v ‖_{2} \end{aligned}

$\begin{align*} \|\nabla f(u) - \nabla f(v)\|_2 &= (2/3)\|X^\top Xu - X^\top Xv\|_2 \\ &\leq (2/3)\|X^\top X\|_2\|u - v\|_2 \\ &= (20/3)\|u - v\|_2 \end{align*}$

X

$X$ 在您的代码中定义。因此，对于这个特定的成本，我们有保证了 GD 的收敛。这与您的数值实验一致，其中 GD 收敛于，但不是。

β = 20 / 3

$\beta = 20/3$

η \leq 1 / β = 0.15

$\eta \leq 1/\beta = 0.15$

η = 0.1

$\eta = 0.1$

η = 0.3

$\eta = 0.3$

最后，请注意是收敛的充分条件，但不是必要条件。也就是说，这并不意味着 GD 算法在使用时总是会发散。 $\eta \leq 1/\beta$ $\eta > 1/\beta$

其它你可能感兴趣的问题

上一篇数据没有很好分离时的不稳定逻辑回归下一篇Kullback-Leibler 散度