python中的数值梯度下降

Question

我写这段代码是为了得到向量函数的梯度下降

其中：f为函数，X0为起点，eta为步长

它基本上由两部分组成，第一部分得到函数的梯度，第二部分迭代x，减去梯度

问题是，在某些函数上，您通常很难收敛，例如：

如果我们取，梯度下降不收敛于[20,25]

我需要更改或添加什么

def descenso_grad(f,X0,eta):

    def grad(f,X):
        import numpy as np
        def partial(g,k,X):
            h=1e-9
            Y=np.copy(X)
            X[k-1]=X[k-1]+h
            dp=(g(X)-g(Y))/h
            return dp
        grd=[]
        for i in np.arange(0,len(X)):
            ai=partial(f,i+1,X)
            grd.append(ai)
        return grd
    #iterations

    i=0
    while True:
        i=i+1
        X0=X0-eta*np.array(grad(f,X0))

        if np.linalg.norm(grad(f,X0))<10e-8 or i>400: break
    return X0

Answer 1

渐变下降实现是一个很好的基本实现，但是渐变有时会振荡和爆发。首先，我们应该确定你的梯度下降并不总是发散。对于eta和X0的某些组合，它实际上是收敛的

但首先让我建议对代码进行一些编辑：

• import numpy as np语句应该在文件的顶部，而不是在函数中。通常，任何导入语句都应该位于代码的开头，以便它们只执行一次
• 最好不要编写嵌套函数，而是将它们分开：可以在grad函数之外编写partial函数，在descendo_grad函数之外编写grad函数。它更适合于调试
• 我强烈建议将学习速率（eta）、步数（steps）和容差（在代码中设置为10e-8，或1e-7）等参数作为参数传递给descendo_grad函数。通过这种方式，您将能够比较它们对结果的影响

无论如何，以下是我将在回答中使用的代码的实现：

import numpy as np

def partial(g, k, X):
    h = 1e-9
    Y = np.copy(X)
    X[k - 1] = X[k - 1] + h
    dp = (g(X) - g(Y)) / h
    return dp

def grad(f, X):
    grd = []
    for i in np.arange(0, len(X)):
        ai = partial(f, i + 1, X)
        grd.append(ai)
    return grd

def descenso_grad(f,X0,eta, steps, tolerance=1e-7):

    #iterations
    i=0
    while True:
        i=i+1
        X0=X0-eta*np.array(grad(f,X0))

        if np.linalg.norm(grad(f,X0))<tolerance or i>steps: break
    return X0

def f(X):
    return (X[0]-20)**4 + (X[1]-25)**4

现在，关于趋同。我说过你的实现并不总是有分歧。事实上：

X0 = [2, 30]
eta = 0.001
steps = 400
xmin = descenso_grad(f, X0, eta, steps)
print(xmin) 

将打印[20.55359068 25.55258024]

但是：

X0 = [2, 0]
eta = 0.001
steps = 400
xmin = descenso_grad(f, X0, eta, steps)
print(xmin)

实际上会偏离到[ 2.42462695e+01 -3.54879793e+10]

1） 发生了什么事

你的梯度实际上是绕y轴摆动的。让我们计算一下f在X0 = [2, 0]的梯度：

print(grad(f, X0))

我们得到grad(f, X0) = [-23328.00067961216, -62500.01024454831]，这是相当高的，但方向正确

现在让我们计算梯度下降的下一步：

eta = 0.001
X1=X0-eta*np.array(grad(f,X0))
print(X1)

我们得到X1 = [25.32800068 62.50001025]。我们可以看到，在x轴上，我们实际上更接近极小值，但在y轴上，梯度下降跳到极小值的另一边，甚至更远。事实上，X0[1]与左边的最小（X0[1] - Xmin[1] = 25距离为25，而X0[1]现在距离65-25 = 40但在右边*。由于f绘制的曲线在y轴周围具有简单的U形，因此X1中f的值将比以前更高（为了简化，我们忽略x坐标的影响）

如果我们看一下接下来的步骤，我们可以清楚地看到围绕最小值的爆炸性振荡：

X0 = [2, 0]
eta = 0.001
steps = 10

#record values taken by X[1] during gradient descent
curve_y = [X0[1]]

i = 0
while True:
    i = i + 1
    X0 = X0 - eta * np.array(grad(f, X0))
    curve_y.append(X0[1])

    if np.linalg.norm(grad(f, X0)) < 10e-8 or i > steps: break

print(curve_y)

我们得到[0, 62.50001024554831, -148.43710232226067, 20719.6258707022, -35487979280.37413]。我们可以看到，X1在围绕极小值振荡时，离极小值越来越远

为了说明这一点，我们假设沿x轴的值是固定的，只看y轴上发生了什么。图中以黑色显示了在梯度下降的每一步中函数值的振荡（合成数据仅用于说明）。梯度下降使我们在每一步都远离最小值，因为更新值太大：

请注意，作为示例，我们给出的梯度下降只进行了5步，而我们编程了10步。这是因为当函数取的值太高时，python无法成功地在f(X[1])和f(X[1]+h)之间求差，因此它计算的梯度等于零：

x = 24 # for the example
y = -35487979280.37413
z = f([x, y+h]) - f([x, y])
print(z)

我们得到0.0。这个问题是关于计算机的计算精度，但我们将在稍后再讨论这个问题

因此，这些振荡是由以下因素组合而成：

• 相对于y轴的偏梯度的非常高的值
• eta的值太大，无法补偿更新中爆炸的渐变

如果这是真的，那么如果我们使用较小的学习率，我们可能会趋同。让我们检查一下：

X0 = [2, 0]
# divide eta by 100
eta = 0.0001
steps = 400
xmin = descenso_grad(f, X0, eta, steps)
print(xmin)

我们将得到[18.25061287 23.24796497]我们可能需要更多的步骤，但这次我们正在收敛

2） 如何避免这种情况

A） 在您的特定情况下

由于函数形状简单，没有局部极小值或鞍点s、 我们可以通过简单地剪裁渐变值来避免此问题。这意味着我们定义了梯度范数的最大值：

def grad_clipped(f, X, clip):
    grd = []
    for i in np.arange(0, len(X)):
        ai = partial(f, i + 1, X)
        if ai<0:
            ai = max(ai, -1*clip)
        else:
            ai = min(ai, clip)
        grd.append(ai)
    return grd

def descenso_grad_clipped(f,X0,eta, steps, clip=100, tolerance=10e-8):

    #iterations
    i=0
    while True:
        i=i+1
        X0=X0-eta*np.array(grad_clipped(f,X0, clip))

        if np.linalg.norm(grad_clipped(f,X0, clip))<tolerance or i>steps: break
    return X0

让我们使用发散示例来测试它：

X0 = [2, 0]
eta = 0.001
steps = 400
clip=100
xmin = descenso_grad_clipped(f, X0, eta, clip, steps)
print(xmin)

这次我们会聚在一起：[19.31583901 24.20307188]。请注意，这可能会减慢过程，因为梯度下降将采取较小的步骤。在这里，我们可以通过增加步骤的数量来接近真正的最小值

请注意，此技术还解决了函数值过高时我们面临的数值计算问题

B） 通常

一般来说，梯度下降算法都试图避免很多警告（梯度爆炸或消失、鞍点、局部极小值…）。像Adam、RMSprop、Adagrad等反向传播算法试图避免这些警告

我不打算详述细节，因为这本书值得一整篇文章，但这里有两个资源可以帮助您加深对该主题的理解（我建议您按照给定的顺序阅读）：

• A good article on towardsdatascience.com 解释渐变的基本原理和最常见的缺陷
• An overview of gradient descent algorithms