由于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实现之前,让我们导入一些基础库:
importnumpyasnpimporttorch
使用前面的数学方程的最后两行代码,我们可以从Quickprop开始!
请注意,我们使用PyTorch为我们做自动梯度计算。我们还假设已经预先定义了一个激活和丢失函数。
#Setuptorchautogradforweightvectorww_var=torch.autograd.Variable(torch.Tensor(w), requires_grad=True) #Calcpredictedvaluesbasedoninputxandlossbasedonexpectedoutputypredicted=activation(torch.mm(x, w_var)) L=loss(predicted, y) #CalcdifferentialL.backward() #And, finally, dotheweightupdatedL=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很容易实现梯度下降——我们也会利用这个机会对上面的代码进行重构:
defcalc_gradient(x, y, w, activation, loss): #Helpertocalclossgradientw_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() returnL, dL, predicteddefgrad_descent_step(x, y, w, activation, loss, learning_rate=1e-5): #CalculatethegradientasusuallyL, dL, predicted=calc_gradient(x, y, w, activation, loss) #Thendoasimplegradientdescentstepdw=-learning_rate*dLnew_w=w+dwreturnnew_w, dw, L, dL
改进:梯度条件加法
当使用Quickprop抛物线方法时,权重增量会变得非常小。为了防止在坡度不为零时发生这种情况,Fahlman建议有条件地将坡度添加到权重增量中。
这个想法可以这样描述:如果你一直朝着这个方向前进,那就走得更远,但是如果你之前的更新把你推向了相反的方向(为了防止振荡),就不要再往前推了。
只需一小段决策器代码,就可以很容易地实现:
# (Thiscodeisjusttoillustratetheprocessbeforetherealimplementation, itwon't execute)# We'llreceivedwanddw_prevandneedtodecidewhethertoapplytheupdateornot. #Tonothavetoincludeconditionalexecution (ifclauses) 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'llhavethreecasesastheoutcomeofthesumtoconsiderhere: #-2, -1, 0, 1, 2#Butactually, 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.
有了这个,我们可以把它放在一个小函数中:
defcond_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) returndw+ddw* (-learning_rate*dL)
改进:最大增长因子
作为第二步,我们将解决一些函数特征(例如奇点附近)的权重增量爆炸的问题。为此,Fahlman建议剪裁权重更新,如果它大于上次权重更新乘以最大增长因子:
defclip_at_max_growth(dw, dw_prev, max_growth_factor=1.75): #Gettheabsolutemaximumelement-wisegrowthmax_growth=max_growth_factor*np.abs(dw_prev) #Andimplementthisbranchlesswithamin/maxclipreturnnp.clip(dw, a_min=(-max_growth), a_max=max_growth)
改进:防止除零
在某些情况下,先前和当前计算的坡度可能相同。结果是,我们将尝试在权重更新规则中除以零,然后继续使用NaN,这显然会破坏训练。
这里最简单的解决方法是做一个梯度下降步骤。
请遵守两个更新规则:
#Quickpropdw=dw_prev*dL/ (dL_prev-dL) #Gradientdescentdw=-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-子句),把所有东西都放在一个公式中:
# (Thiscodeisjusttoillustratetheprocessbeforetherealimplementation, itwon'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实现了一些与它们非常相似的东西——只是它的核心没有使用反向传播。
回到代码上来:由于我们之前已经实现了梯度下降,我们可以在此基础上尽可能多地重复使用:
defquickprop_step(x, y, w, dw_prev, dL_prev, activation, loss, qp_learning_rate=1.5, gd_learning_rate=1e-5): #CalculatethegradientasusuallyL, dL, predicted=calc_gradient(x, y, w, activation, loss) #Calculatea'decider'bitbetweenquickpropandgradientdescentddL=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) #Usetheconditionalslopeadditiondw=cond_add_slope(dw, dw_prev, dL, qp_learning_rate) #Usethemaxgrowthfactordw=clip_at_max_growth(dw, dw_prev) new_w=w+dwreturnnew_w, dw, L, dL, predicted
把它们放在一起
有了这些功能,我们就可以把它们放在一起了。样板代码仍然需要进行初始化并检查每个历元的平均损失的收敛性。
#Paramshapes: x_: (n,i), y_: (n,o), weights: (i,o) #Wherenisthesizeofthewholesampleset, iistheinputcount, oistheoutputcount#Weexpectx_toalreadyincludethebias#Returns: trainedweights, lastprediction, lastiteration, lastloss#NB: Differentiationisdoneviatorchdefquickprop(x_, y_, weights, activation=torch.nn.Sigmoid(), loss=torch.nn.MSELoss(), learning_rate=1e-4, tolerance=1e-6, patience=20000, debug=False): #Boxparamsastorchdatatypesx=torch.Tensor(x_) y=torch.Tensor(y_) w=torch.Tensor(weights) #Keeptrackofmeanresidualerrorvalues (usedtotestforconvergence) L_mean=1L_mean_prev=1L_mean_diff=1#KeeptrackoflossandweightgradientsdL=torch.zeros(w.shape) dL_prev=torch.ones(w.shape) dw_prev=torch.ones(w.shape) #InitializethealgorithmwithaGDstepw, dw_prev, L, dL_prev=grad_descent_step(x, y, w, activation, loss) i=0predicted= [] #Thisalgorithmexpectsthemeanlossestoconvergeorthepatiencetorunout... whileL_mean_diff>toleranceandi<patience: #Prepiterationi+=1dL_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() #Keeptrackoflossesanduseasconvergencecriterionifmeandoesn'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_meanif 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