Quickprop介绍：一个加速梯度下降的学习方法

由于80年代/ 90年代的普通反向传播算法收敛缓慢，Scott Fahlman发明了一种名为Quickprop[1]的学习算法，它大致基于牛顿法。他的简单想法在诸如“N-M-N编码器”任务这样的问题域中优于反向传播(有各种调整)，即训练一个具有N个输入、M个隐藏单位和N个输出的de-/ Encoder网络。Quickprop的方法之一是寻找特定领域的最佳学习率，或者更确切地说:适当地动态调整学习率的算法。

在本文中，我们将研究Quickprop背后的简单数学思想。我们将实现基本的算法和一些改进。

为了跟随本文的学习，您应该熟悉如何使用损失梯度的反向传播来训练神经网络(从2020年开始，这是一种广泛使用的方法)。也就是说，您应该了解如何计算梯度，并将其应用于网络的参数，以迭代地尝试将损失收敛到全局最小值。

概述

我们将从Quickprop背后的数学知识开始，然后看看如何一步步实现和改进它。为了使后续更容易，使用的任何方程和推理步骤都比原论文中解释得更详细。

Quickprop背后的数学

对于神经网络来说，通常使用的反向传播学习方法是基于这样一种思想:通过在函数梯度的相反方向上采取较小的步骤，迭代地“沿着”函数的斜坡向下走。

这些“小步骤”是这里的关键。它们的长度通常取决于学习率因子，并且有意地保持较小，以不超过潜在的最小值。

在Fahlman开发Quickprop的时候，选择一个好的学习率是一个主要的问题。正如他在他的论文中提到的，在性能最好的算法中，科学家在每一步都是“用眼睛”(即手动和基于经验)选择学习速率的![1]

面对这种情况，法尔曼想出了一个不同的主意:解决一个更简单的问题。

最小化损失函数L，特别是对于深度神经网络，在分析上(即在整个领域上的一般方法)会变得极其困难。例如，在反向传播中，我们只逐点计算它，然后在正确的方向上做小的步骤。如果我们知道函数的“地形”通常是什么样的，我们就可以直接“跳跃”到最小值。

但是如果我们可以用一个更简单的版本来代替损失函数，我们知道它的地形?这正是Fahlmans在Quickprop中所做的假设:他假设L可以被一个简单的抛物线近似，这个抛物线朝正方向打开。这样，计算(抛物线的)最小值就像找到一条直线与x轴的交点一样简单。

如果这一点还不是损失函数的最小值，下一个抛物线可以从这里近似，如下图所示。

将抛物线拟合到原函数，并向其最小值迈出一步。并在哪里与下一个抛物线拟合，重复这个步骤。这两条虚线是抛物线当前和之前的一个静止点。（作者提供的图片）

那么，我们如何精确地估算L呢?很简单，用泰勒级数，还有一个小技巧。

注意，对于下面的方程，我们认为权向量w的分量是独立训练的，所以w被视为一个标量。但我们仍然可以利用GPU的SIMD架构，智能计算。

我们从L的二阶泰勒展开开始，得到一个抛物线(没有误差项):

大致步骤：在泰勒公式中输入L直到第二项，然后去掉其余项。

现在我们可以根据权重差定义权重的更新规则，并输入到T中:

Quickprop现在进一步使用差商线性近似L”(这是上面提到的小技巧):

使用这个，我们可以重写泰勒多项式到这个' Quickprop '调整版本，并建立它的梯度:

最后一个方程，可以用来计算抛物线的平稳点

现在，为了把这些东西放在一起，给定以前的权重、以前的权重差以及以前和当前权重下的损失斜率，Quickprop只需通过以下方法计算新的权重:

把它变成代码

在开始实际的Quickprop实现之前，让我们导入一些基础库:

import numpy as np

import torch

使用前面的数学方程的最后两行代码，我们可以从Quickprop开始!

请注意，我们使用PyTorch为我们做自动梯度计算。我们还假设已经预先定义了一个激活和丢失函数。

# Setup torch autograd for weight vector w

w_var = torch.autograd.Variable(torch.Tensor(w), requires_grad=True)

# Calc predicted values based on input x and loss based on expected output y

predicted = activation(torch.mm(x, w_var))

L = loss(predicted, y)

# Calc differential

L.backward()

# And, finally, do the weight update

dL = w_var.grad.detach() # =: partial(L) / partial(W)

dw = dw_prev * dL / (dL_prev - dL)

dw_prev = dw.clone()

w += learning_rate * dw

这是一个学习阶段最简单的Quickprop版本。要真正地使用它，我们必须运行它几次，看看损失是否收敛(我们将在后面介绍)。

然而，这个实现在几个方面是有缺陷的，我们将在以下部分调查和修复:

我们实际上没有初始化任何。_prev变量权值delta变量可能会在零值上卡住，因为它在自己的更新步骤中被用作一个因子

如果梯度“爆炸”，实现可能会超调或通常无法收敛。

如果在一次迭代中梯度不变，则会导致除零

改进：通过梯度下降初始化

我们可以应用的第一个简单方法是使用梯度下降（学习率很小）来准备dw_prev和dL_prev变量。这将使我们对损失功能地形有一个很好的初步了解，并在正确的方向启动Quickprop

使用pytorch很容易实现梯度下降——我们也会利用这个机会对上面的代码进行重构:

def calc_gradient(x, y, w, activation, loss):

# Helper to calc loss gradient

w_var = torch.autograd.Variable(torch.Tensor(w), requires_grad=True)

predicted = activation(torch.mm(x, w_var))

L = loss(predicted, y)

L.backward()

dL = w_var.grad.detach()

return L, dL, predicted

def grad_descent_step(x, y, w, activation, loss, learning_rate=1e-5):

# Calculate the gradient as usually

L, dL, predicted = calc_gradient(x, y, w, activation, loss)

# Then do a simple gradient descent step

dw = -learning_rate * dL

new_w = w + dw

return new_w, dw, L, dL

改进：梯度条件加法

当使用Quickprop抛物线方法时，权重增量会变得非常小。为了防止在坡度不为零时发生这种情况，Fahlman建议有条件地将坡度添加到权重增量中。

这个想法可以这样描述：如果你一直朝着这个方向前进，那就走得更远，但是如果你之前的更新把你推向了相反的方向（为了防止振荡），就不要再往前推了。

只需一小段决策器代码，就可以很容易地实现：

# (This code is just to illustrate the process before the real implementation, it won't execute)

# We'll receive dw and dw_prev and need to decide whether to apply the update or not.

# To not have to include conditional execution (if clauses) we'll want to do it branchless.

# This can be achieved by a simple mutliplication rule using the sign function:

# Sign gives us either -1, 0 or 1 based on the parameter being less, more or exactly zero

# (check the docs for specifics),

np.sign(dw) + np.sign(dw_prev)

# With this, we'll have three cases as the outcome of the sum to consider here:

# -2, -1, 0, 1, 2

# But actually, we're really only interested if this is 0 or not, so we can do:

np.clip(np.abs(np.sign(dw) + np.sign(dw_prev)), a_min=0, a_max=1)

# And use that as our deciding factor, which is either 1 or 0 when the dw and dw_prev share the sign or not.

有了这个，我们可以把它放在一个小函数中：

def cond_add_slope(dw, dw_prev, dL, learning_rate=1.5):

ddw = np.clip(np.abs(np.sign(dw) + np.sign(dw_prev)), a_min=0, a_max=1)

return dw + ddw * (-learning_rate * dL)

改进：最大增长因子

作为第二步，我们将解决一些函数特征（例如奇点附近）的权重增量爆炸的问题。为此，Fahlman建议剪裁权重更新，如果它大于上次权重更新乘以最大增长因子：

def clip_at_max_growth(dw, dw_prev, max_growth_factor=1.75):

# Get the absolute maximum element-wise growth

max_growth = max_growth_factor * np.abs(dw_prev)

# And implement this branchless with a min/max clip

return np.clip(dw, a_min=(-max_growth), a_max=max_growth)

改进：防止除零

在某些情况下，先前和当前计算的坡度可能相同。结果是，我们将尝试在权重更新规则中除以零，然后继续使用NaN，这显然会破坏训练。

这里最简单的解决方法是做一个梯度下降步骤。

请遵守两个更新规则：

# Quickprop

dw = dw_prev * dL / (dL_prev - dL)

# Gradient descent

dw = -learning_rate * dL

# We'll get a nicer result if we shuffle the equations a bit:

dw = dL * dw_prev / (dL_prev - dL)

dw = dL * (-learning_rate)

除了最后一个因子，它们看起来很相似，不是吗?这意味着我们可以再次实现无分支(即为我们保留一些if-子句)，把所有东西都放在一个公式中:

# (This code is just to illustrate the process before the real implementation, it won't execute)

# If (dL_prev - dL) is zero, we want to multiply the learning rate instead,

# i.e. we want to switch to gradient descent. We can accomplish it this way:

# First, we make sure we only use absolute values (the 'magnitude', but element-wise)

np.abs(dL_prev - dL)

# Then we map this value onto either 0 or 1, depending on if it is 0 or not (using the sign function)

ddL = np.sign(np.abs(dL_prev - dL))

# We can now use this factor to 'decide' between quickprop and gradient descent:

quickprop_factor = ddL       * (dw_prev / (dL_prev - dL))

grad_desc_factor = (1 - ddL) * (-learning_rate)

# Overall we get:

dw = dL * (quickprop_factor + grad_desc_factor)

细心的读者可能注意到了我们在上面使用的“学习率”因子——一个我们认为可以去掉的参数……

实际上，我们在某种程度上解决了，或者至少我们解决了在训练过程中调整学习速率的问题。Quickprop学习率可以在整个过程中保持不变。在开始时，每个域只需要调整一次。实际的动态步长是通过抛物线跳跃来选择的，这反过来很大程度上取决于当前和最后计算的斜率。

如果您认为这听起来与反向传播学习率优化器的工作原理非常相似(想想动量)，那么您就在正确的轨道上了。从本质上说，Quickprop实现了一些与它们非常相似的东西——只是它的核心没有使用反向传播。

回到代码上来:由于我们之前已经实现了梯度下降，我们可以在此基础上尽可能多地重复使用:

def quickprop_step(x, y, w, dw_prev, dL_prev,

                activation, loss,

                qp_learning_rate=1.5,

                gd_learning_rate=1e-5):

# Calculate the gradient as usually

L, dL, predicted = calc_gradient(x, y, w, activation, loss)

# Calculate a 'decider' bit between quickprop and gradient descent

ddL = np.ceil(np.clip(np.abs(dL_prev - dL), a_min=0, a_max=1) / 2)

quickprop_factor = ddL       * (dw_prev / (dL_prev - dL))

grad_desc_factor = (1 - ddL) * (-gd_learning_rate)

dw = dL * (quickprop_factor + grad_desc_factor)

# Use the conditional slope addition

dw = cond_add_slope(dw, dw_prev, dL, qp_learning_rate)

# Use the max growth factor

dw = clip_at_max_growth(dw, dw_prev)

new_w = w + dw

return new_w, dw, L, dL, predicted

把它们放在一起

有了这些功能，我们就可以把它们放在一起了。样板代码仍然需要进行初始化并检查每个历元的平均损失的收敛性。

# Param shapes: x_: (n,i), y_: (n,o), weights: (i,o)

#   Where n is the size of the whole sample set, i is the input count, o is the output count

#   We expect x_ to already include the bias

# Returns: trained weights, last prediction, last iteration, last loss

# NB: Differentiation is done via torch

def quickprop(x_, y_, weights,

          activation=torch.nn.Sigmoid(),

          loss=torch.nn.MSELoss(),

          learning_rate=1e-4,

          tolerance=1e-6,

          patience=20000,

          debug=False):

# Box params as torch datatypes

x = torch.Tensor(x_)

y = torch.Tensor(y_)

w = torch.Tensor(weights)

# Keep track of mean residual error values (used to test for convergence)

L_mean = 1

L_mean_prev = 1

L_mean_diff = 1

# Keep track of loss and weight gradients

dL = torch.zeros(w.shape)

dL_prev = torch.ones(w.shape)

dw_prev = torch.ones(w.shape)

# Initialize the algorithm with a GD step

w, dw_prev, L, dL_prev = grad_descent_step(x, y, w, activation, loss)

i = 0

predicted = []

# This algorithm expects the mean losses to converge or the patience to run out...

while L_mean_diff > tolerance and i < patience:

    # Prep iteration

    i += 1

    dL_prev = dL.clone()

    w, dw, L, dL, predicted = quickprop_step(x, y, w, dw_prev, dL_prev, activation, loss, qp_learning_rate=learning_rate)

    dw_prev = dw.clone()

    # Keep track of losses and use as convergence criterion if mean doesn't change much  

    L_mean = L_mean + (1/(i+1))*(L.detach().numpy() - L_mean)

    L_mean_diff = np.abs(L_mean_prev - L_mean)

    L_mean_prev = L_mean

    if debug and i % 100 == 99:

        print("Residual           ", L.detach().numpy())

        print("Residual mean     ", L_mean)

        print("Residual mean diff ", L_mean_diff)

return w.detach().numpy(), predicted.detach().numpy(), i, L.detach().numpy()

警告

Quickprop有一个重要的警告，这大大降低了它的实用性:我们使用的数学“技巧”，即用简单的差商来近似损失函数的二阶导数，依赖于这个二阶导数是一个连续函数的假设。

对于激活函数，例如直线单元或ReLU，没有给出这一条件。二阶导数是不连续的，算法的行为可能变得不可靠(例如，它可能发散)。

回顾我之前关于级联关联实现的文章，我们使用Quickprop训练网络的隐藏单元，并使用协方差函数作为估计过程中损失的一种方法。但是，协方差(在那里实现的)被包装在一个绝对值函数中。即它的二阶导数是不连续的，因此不应该使用Quickprop。Fahlman等人的级联相关论文[2]的细心读者可能也注意到，他们实际上是使用梯度上升来计算最大协方差。

除此之外，Quickprop似乎在某些领域提供了更好的结果。Brust等人的一项有趣的总结表明，与基于反向传播的技术相比，它在一些简单的图像分类任务(对基本形状进行分类)上取得了更好的训练效果，但在更为真实的图像分类任务[3]上效果较差。

我还没有在这个方向上做过任何研究，但是我想知道这是否意味着Quickprop可以更好地处理不那么模糊和结构化的数据(想想业务上下文中使用的数据框架/表格)。这无疑是值得研究的。

总结

本文介绍了Scott Fahlman关于改进反向传播的想法。我们看了数学基础和可能的实现。

现在开始在你自己的项目中尝试一下——我很想看看Quickprop可以用来做什么!

引用

[1] S. E. Fahlman, An empirical study of learning speed in back-propagation networks (1988), Carnegie Mellon University, Computer Science Department

[2] S. E. Fahlman and C. Lebiere, The cascade-correlation learning architecture (1990), Advances in neural information processing systems (pp. 524–532)

[3] C. A. Brust, S. Sickert, M. Simon, E. Rodner and J. Denzler, Neither Quick Nor Proper — Evaluation of QuickProp for Learning Deep Neural Networks (2016), arXiv preprint arXiv:1606.04333

作者 Johanna Appel

deephub翻译组