精华内容
下载资源
问答
  • 机器学习和凸优化领域大牛Yurii Nesterov 2018年的最新力作。经典凸优化书籍 Introductory Lectures on Convex Optimization: A Basic Course 的再版。原书也可从如下地址下载...
  • 【翻译自 : Gradient Descent With Nesterov Momentum From Scratch】 【说明:Jason BrownleePhD大神的文章个人很喜欢,所以闲暇时间里会做一点翻译和学习实践的工作,这里是相应工作的实践记录,希望能帮到有...

            【翻译自 : Gradient Descent With Nesterov Momentum From Scratch

            【说明:Jason Brownlee PhD大神的文章个人很喜欢,所以闲暇时间里会做一点翻译和学习实践的工作,这里是相应工作的实践记录,希望能帮到有需要的人!】

             梯度下降是一种优化算法,遵循目标函数的负梯度以定位函数的最小值。

            梯度下降的一个限制是,如果目标函数返回嘈杂的梯度,则它可能会卡在平坦的区域中或反弹。动量是一种加速搜索过程的方法,可在平坦区域上浏览并平滑弹力梯度。

            在某些情况下,动量的加速度会导致搜索丢失或超出盆地或山谷底部的最小值。 Nesterov动量是动量的扩展,涉及计算搜索空间中投影位置的梯度的递减移动平均值,而不是计算实际位置本身。

            这具有利用动量加速收益的作用,同时在接近最优值时允许搜索减慢速度,并减少了丢失或超调的可能性。

           在本教程中,您将发现如何从头开始使用Nesterov Momentum开发梯度下降优化算法。完成本教程后,您将知道:

    梯度下降是一种优化算法,它使用目标函数的梯度来导航搜索空间。
    通过扩展算法并添加Nesterov动量,可以加快梯度下降优化算法的收敛速度。
    如何从头开始实现Nesterov动量优化算法,并将其应用于目标函数并评估结果。

    教程概述

         本教程分为三个部分: 他们是:

    梯度下降
    内斯特罗夫动量
    Nesterov动量的梯度下降
        二维测试问题
        Nesterov动量的梯度下降优化
        内斯特罗夫动量的可视化

    梯度下降

            梯度下降是一种优化算法。它在技术上称为一阶优化算法,因为它明确利用了目标目标函数的一阶导数。

           一阶导数,或简称为“导数”,是目标函数在特定点(例如,点)上的变化率或斜率。用于特定输入。

            如果目标函数采用多个输入变量,则将其称为多元函数,并且可以将输入变量视为向量。反过来,多元目标函数的导数也可以视为向量,通常称为“梯度”。

           梯度:多元目标函数的一阶导数。
          对于特定输入,导数或梯度指向目标函数最陡峭的上升方向。梯度下降是指一种最小化优化算法,该算法遵循目标函数的下坡梯度负值来定位函数的最小值。梯度下降算法需要一个正在优化的目标函数和该目标函数的导数函数。目标函数f()返回给定输入集合的分数,导数函数f'()给出给定输入集合的目标函数的导数。梯度下降算法需要问题中的起点(x),例如输入空间中的随机选择点。假设我们正在最小化目标函数,然后计算导数并在输入空间中采取一步,这将导致目标函数下坡运动。首先通过计算输入空间中要移动多远的距离来进行下坡运动,计算方法是将步长(称为alpha或学习率)乘以梯度。然后从当前点减去该值,以确保我们逆梯度移动或向下移动目标函数。

    x(t + 1)= x(t)–step* f'(x(t))

            在给定点的目标函数越陡峭,梯度的大小越大,反过来,在搜索空间中采取的步伐也越大。使用步长超参数来缩放步长的大小。

                步长(alpha):超参数,控制算法每次迭代时相对于梯度在搜索空间中移动多远。
            如果步长太小,则搜索空间中的移动将很小,并且搜索将花费很长时间。如果步长太大,则搜索可能会在搜索空间附近反弹并跳过最优值。 现在我们已经熟悉了梯度下降优化算法,下面我们来看看Nesterov动量。

    内斯特罗夫动量

         Nesterov动量是梯度下降优化算法的扩展。这种方法由Yurii Nesterov在1983年发表的题为“一种用收敛速度为O(1 / k ^ 2)解决凸规划问题的方法”描述(并以此名称命名)。Ilya Sutskever等。 负责在他们的2013年论文“深度学习中初始化和动量的重要性”中描述了Nesterov动量在具有随机梯度下降的神经网络训练中的广泛应用。 他们将这种方法称为“ Nesterov的加速梯度”,简称NAG。Nesterov动量就像更传统的动量一样,除了使用投影更新的偏导数而不是导数当前变量值执行更新。

           然后,该变量的最后更新或最后更改将添加到由“动量”超参数缩放的变量中,该超参数控制要添加的最后更改的数量,例如 0.9为90%。更容易从两个步骤来考虑此更新,例如,使用偏导数计算变量的变化,然后计算变量的新值。

    change(t + 1)=(momentum * change(t))–(step_size * f'(x(t)))
    x(t + 1)= x(t)+change(t + 1)

           我们可以从下坡滚球的角度来思考动量,即使在有小山丘的情况下,它也会加速并继续朝着相同的方向前进。

           动量的问题在于,加速度有时会导致搜索超出盆地或山谷底部的最小值。内斯特罗夫动量可以被认为是对动量的一种修正,可以克服这个过小问题。它涉及首先使用从上次迭代开始的更改来计算变量的投影位置,并在计算变量的新位置时使用投影位置的导数。计算投影位置的坡度就像已累积加速度的校正因子一样。

    Nesterov Momentum可以从以下四个步骤中轻松考虑这一点:

    1.投影解决方案的位置。
    2.计算投影的梯度。
    3.使用偏导数计算变量的变化。
    4.更新变量。

          让我们更详细地完成这些步骤。首先,使用在算法的最后一次迭代中计算出的变化来计算整个解决方案的投影位置。

    projection(t+1) = x(t) + (momentum * change(t))

           然后,我们可以计算该新位置的梯度。

    gradient(t+1) = f'(projection(t+1))

         现在,我们可以使用投影的梯度来计算每个变量的新位置,首先通过计算每个变量的变化。

    change(t+1) = (momentum * change(t)) – (step_size * gradient(t+1))

           最后,使用计算出的变化为每个变量计算新值。

    x(t+1) = x(t) + change(t+1)

         更一般地,在凸优化领域中,已知Nesterov Momentum可以提高优化算法的收敛速度(例如,减少找到解所需的迭代次数)。

         现在,我们已经熟悉Nesterov Momentum算法,接下来,我们将探讨如何实现它并评估其性能。

    Nesterov动量的梯度下降

           在本节中,我们将探索如何使用Nesterov动量实现梯度下降优化算法。

    二维测试问题

            首先,让我们定义一个优化函数。我们将使用一个简单的二维函数,该函数将每个维的输入平方,并定义有效输入的范围(从-1.0到1.0)。下面的Objective()函数实现了此功能。

    # objective function
    def objective(x, y):
    	return x**2.0 + y**2.0

          我们可以创建数据集的三维图,以了解响应面的曲率。下面列出了绘制目标函数的完整示例。

    # 3d plot of the test function
    from numpy import arange
    from numpy import meshgrid
    from matplotlib import pyplot
    
    # objective function
    def objective(x, y):
    	return x**2.0 + y**2.0
    
    # define range for input
    r_min, r_max = -1.0, 1.0
    # sample input range uniformly at 0.1 increments
    xaxis = arange(r_min, r_max, 0.1)
    yaxis = arange(r_min, r_max, 0.1)
    # create a mesh from the axis
    x, y = meshgrid(xaxis, yaxis)
    # compute targets
    results = objective(x, y)
    # create a surface plot with the jet color scheme
    figure = pyplot.figure()
    axis = figure.gca(projection='3d')
    axis.plot_surface(x, y, results, cmap='jet')
    # show the plot
    pyplot.show()

             运行示例将创建目标函数的三维表面图。我们可以看到全局最小值为f(0,0)= 0的熟悉的碗形状。

            我们还可以创建函数的二维图。 这在以后要绘制搜索进度时会很有帮助。下面的示例创建目标函数的轮廓图。

    # contour plot of the test function
    from numpy import asarray
    from numpy import arange
    from numpy import meshgrid
    from matplotlib import pyplot
    
    # objective function
    def objective(x, y):
    	return x**2.0 + y**2.0
    
    # define range for input
    bounds = asarray([[-1.0, 1.0], [-1.0, 1.0]])
    # sample input range uniformly at 0.1 increments
    xaxis = arange(bounds[0,0], bounds[0,1], 0.1)
    yaxis = arange(bounds[1,0], bounds[1,1], 0.1)
    # create a mesh from the axis
    x, y = meshgrid(xaxis, yaxis)
    # compute targets
    results = objective(x, y)
    # create a filled contour plot with 50 levels and jet color scheme
    pyplot.contourf(x, y, results, levels=50, cmap='jet')
    # show the plot
    pyplot.show()

            运行示例将创建目标函数的二维轮廓图。我们可以看到碗的形状被压缩为以颜色渐变显示的轮廓。 我们将使用该图来绘制在搜索过程中探索的特定点。

            现在我们有了一个测试目标函数,让我们看一下如何实现Nesterov动量优化算法。

    Nesterov动量的梯度下降优化

            我们可以将Nesterov动量的梯度下降应用于测试问题。首先,我们需要一个函数来计算此函数的导数。x ^ 2的导数在每个维度上均为x * 2,并且derivative()函数在下面实现此功能。

    # derivative of objective function
    def derivative(x, y):
    	return asarray([x * 2.0, y * 2.0])

          接下来,我们可以实现梯度下降优化。

          首先,我们可以选择问题范围内的随机点作为搜索的起点。

           假定我们有一个数组,该数组定义搜索范围,每个维度一行,并且第一列定义最小值,第二列定义维度的最大值。

    # generate an initial point
    solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])

            接下来,我们需要从当前位置计算投影点并计算其导数。

    # calculate the projected solution
    projected = [solution[i] + momentum * change[i] for i in range(solution.shape[0])]
    # calculate the gradient for the projection
    gradient = derivative(projected[0], projected[1])

           然后,我们可以创建一个新的解决方案,一次创建一个变量。

           首先,使用偏导数和学习率以及变量最后一次变化的动量来计算变量的变化。 存储此更改以供算法的下一次迭代。 然后,更改将用于计算变量的新值。

    # build a solution one variable at a time
    new_solution = list()
    for i in range(solution.shape[0]):
    	# calculate the change
    	change[i] = (momentum * change[i]) - step_size * gradient[i]
    	# calculate the new position in this variable
    	value = solution[i] + change[i]
    	# store this variable
    	new_solution.append(value)

            对目标函数的每个变量重复此操作,然后对算法的每个迭代重复此操作。然后可以使用Objective()函数评估该新解决方案,并可以报告搜索的性能。

    # evaluate candidate point
    solution = asarray(new_solution)
    solution_eval = objective(solution[0], solution[1])
    # report progress
    print('>%d f(%s) = %.5f' % (it, solution, solution_eval))

            就是这样。我们可以将所有这些绑定到一个名为nesterov()的函数中,该函数采用目标函数和导数函数的名称,该数组具有域边界和超参数值,用于算法迭代的总数,学习率, 和动量,并返回最终解决方案及其评估。下面列出了完整的功能。

    # gradient descent algorithm with nesterov momentum
    def nesterov(objective, derivative, bounds, n_iter, step_size, momentum):
    	# generate an initial point
    	solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
    	# list of changes made to each variable
    	change = [0.0 for _ in range(bounds.shape[0])]
    	# run the gradient descent
    	for it in range(n_iter):
    		# calculate the projected solution
    		projected = [solution[i] + momentum * change[i] for i in range(solution.shape[0])]
    		# calculate the gradient for the projection
    		gradient = derivative(projected[0], projected[1])
    		# build a solution one variable at a time
    		new_solution = list()
    		for i in range(solution.shape[0]):
    			# calculate the change
    			change[i] = (momentum * change[i]) - step_size * gradient[i]
    			# calculate the new position in this variable
    			value = solution[i] + change[i]
    			# store this variable
    			new_solution.append(value)
    		# evaluate candidate point
    		solution = asarray(new_solution)
    		solution_eval = objective(solution[0], solution[1])
    		# report progress
    		print('>%d f(%s) = %.5f' % (it, solution, solution_eval))
    	return [solution, solution_eval]

          请注意,为了提高可读性,我们有意使用列表和命令式编码样式,而不是矢量化操作。 随意将实现改编为带有NumPy数组的矢量化实现,以实现更好的性能。

           然后,我们可以定义我们的超参数并调用nesterov()函数来优化我们的测试目标函数。

           在这种情况下,我们将使用算法的30次迭代,学习速率为0.1,动量为0.3。 经过一些反复试验后,发现了这些超参数值。

    # seed the pseudo random number generator
    seed(1)
    # define range for input
    bounds = asarray([[-1.0, 1.0], [-1.0, 1.0]])
    # define the total iterations
    n_iter = 30
    # define the step size
    step_size = 0.1
    # define momentum
    momentum = 0.3
    # perform the gradient descent search with nesterov momentum
    best, score = nesterov(objective, derivative, bounds, n_iter, step_size, momentum)
    print('Done!')
    print('f(%s) = %f' % (best, score))

            综合所有这些,下面列出了使用Nesterov Momentum进行梯度下降优化的完整示例。

    # gradient descent optimization with nesterov momentum for a two-dimensional test function
    from math import sqrt
    from numpy import asarray
    from numpy.random import rand
    from numpy.random import seed
    
    # objective function
    def objective(x, y):
    	return x**2.0 + y**2.0
    
    # derivative of objective function
    def derivative(x, y):
    	return asarray([x * 2.0, y * 2.0])
    
    # gradient descent algorithm with nesterov momentum
    def nesterov(objective, derivative, bounds, n_iter, step_size, momentum):
    	# generate an initial point
    	solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
    	# list of changes made to each variable
    	change = [0.0 for _ in range(bounds.shape[0])]
    	# run the gradient descent
    	for it in range(n_iter):
    		# calculate the projected solution
    		projected = [solution[i] + momentum * change[i] for i in range(solution.shape[0])]
    		# calculate the gradient for the projection
    		gradient = derivative(projected[0], projected[1])
    		# build a solution one variable at a time
    		new_solution = list()
    		for i in range(solution.shape[0]):
    			# calculate the change
    			change[i] = (momentum * change[i]) - step_size * gradient[i]
    			# calculate the new position in this variable
    			value = solution[i] + change[i]
    			# store this variable
    			new_solution.append(value)
    		# evaluate candidate point
    		solution = asarray(new_solution)
    		solution_eval = objective(solution[0], solution[1])
    		# report progress
    		print('>%d f(%s) = %.5f' % (it, solution, solution_eval))
    	return [solution, solution_eval]
    
    # seed the pseudo random number generator
    seed(1)
    # define range for input
    bounds = asarray([[-1.0, 1.0], [-1.0, 1.0]])
    # define the total iterations
    n_iter = 30
    # define the step size
    step_size = 0.1
    # define momentum
    momentum = 0.3
    # perform the gradient descent search with nesterov momentum
    best, score = nesterov(objective, derivative, bounds, n_iter, step_size, momentum)
    print('Done!')
    print('f(%s) = %f' % (best, score))

           运行示例将优化算法与Nesterov Momentum一起应用于我们的测试问题,并报告算法每次迭代的搜索性能。

          注意:由于算法或评估程序的随机性,或者数值精度的差异,您的结果可能会有所不同。 考虑运行该示例几次并比较平均结果。

          在这种情况下,我们可以看到,在大约15次搜索迭代后找到了接近最佳的解决方案,输入值接近0.0和0.0,评估为0.0。

    >0 f([-0.13276479 0.35251919]) = 0.14190
    >1 f([-0.09824595 0.2608642 ]) = 0.07770
    >2 f([-0.07031223 0.18669416]) = 0.03980
    >3 f([-0.0495457 0.13155452]) = 0.01976
    >4 f([-0.03465259 0.0920101 ]) = 0.00967
    >5 f([-0.02414772 0.06411742]) = 0.00469
    >6 f([-0.01679701 0.04459969]) = 0.00227
    >7 f([-0.01167344 0.0309955 ]) = 0.00110
    >8 f([-0.00810909 0.02153139]) = 0.00053
    >9 f([-0.00563183 0.01495373]) = 0.00026
    >10 f([-0.00391092 0.01038434]) = 0.00012
    >11 f([-0.00271572 0.00721082]) = 0.00006
    >12 f([-0.00188573 0.00500701]) = 0.00003
    >13 f([-0.00130938 0.0034767 ]) = 0.00001
    >14 f([-0.00090918 0.00241408]) = 0.00001
    >15 f([-0.0006313 0.00167624]) = 0.00000
    >16 f([-0.00043835 0.00116391]) = 0.00000
    >17 f([-0.00030437 0.00080817]) = 0.00000
    >18 f([-0.00021134 0.00056116]) = 0.00000
    >19 f([-0.00014675 0.00038964]) = 0.00000
    >20 f([-0.00010189 0.00027055]) = 0.00000
    >21 f([-7.07505806e-05 1.87858067e-04]) = 0.00000
    >22 f([-4.91260884e-05 1.30440372e-04]) = 0.00000
    >23 f([-3.41109926e-05 9.05720503e-05]) = 0.00000
    >24 f([-2.36851711e-05 6.28892431e-05]) = 0.00000
    >25 f([-1.64459397e-05 4.36675208e-05]) = 0.00000
    >26 f([-1.14193362e-05 3.03208033e-05]) = 0.00000
    >27 f([-7.92908415e-06 2.10534304e-05]) = 0.00000
    >28 f([-5.50560682e-06 1.46185748e-05]) = 0.00000
    >29 f([-3.82285090e-06 1.01504945e-05]) = 0.00000
    Done!
    f([-3.82285090e-06 1.01504945e-05]) = 0.000000

    内斯特罗夫动量的可视化

           我们可以在域的轮廓图上绘制Nesterov动量搜索的进度。这可以为算法迭代过程中的搜索进度提供直观的认识。我们必须更新nesterov()函数以维护在搜索过程中找到的所有解决方案的列表,然后在搜索结束时返回此列表。下面列出了具有这些更改的功能的更新版本。

    # gradient descent algorithm with nesterov momentum
    def nesterov(objective, derivative, bounds, n_iter, step_size, momentum):
    	# track all solutions
    	solutions = list()
    	# generate an initial point
    	solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
    	# list of changes made to each variable
    	change = [0.0 for _ in range(bounds.shape[0])]
    	# run the gradient descent
    	for it in range(n_iter):
    		# calculate the projected solution
    		projected = [solution[i] + momentum * change[i] for i in range(solution.shape[0])]
    		# calculate the gradient for the projection
    		gradient = derivative(projected[0], projected[1])
    		# build a solution one variable at a time
    		new_solution = list()
    		for i in range(solution.shape[0]):
    			# calculate the change
    			change[i] = (momentum * change[i]) - step_size * gradient[i]
    			# calculate the new position in this variable
    			value = solution[i] + change[i]
    			# store this variable
    			new_solution.append(value)
    		# store the new solution
    		solution = asarray(new_solution)
    		solutions.append(solution)
    		# evaluate candidate point
    		solution_eval = objective(solution[0], solution[1])
    		# report progress
    		print('>%d f(%s) = %.5f' % (it, solution, solution_eval))
    	return solutions

            然后,我们可以像以前一样执行搜索,这一次将检索解决方案列表,而不是最佳的最终解决方案。

    # seed the pseudo random number generator
    seed(1)
    # define range for input
    bounds = asarray([[-1.0, 1.0], [-1.0, 1.0]])
    # define the total iterations
    n_iter = 50
    # define the step size
    step_size = 0.01
    # define momentum
    momentum = 0.8
    # perform the gradient descent search with nesterov momentum
    solutions = nesterov(objective, derivative, bounds, n_iter, step_size, momentum)

             然后,我们可以像以前一样创建目标函数的轮廓图。

    # sample input range uniformly at 0.1 increments
    xaxis = arange(bounds[0,0], bounds[0,1], 0.1)
    yaxis = arange(bounds[1,0], bounds[1,1], 0.1)
    # create a mesh from the axis
    x, y = meshgrid(xaxis, yaxis)
    # compute targets
    results = objective(x, y)
    # create a filled contour plot with 50 levels and jet color scheme
    pyplot.contourf(x, y, results, levels=50, cmap='jet')

            最后,我们可以将在搜索过程中找到的每个解决方案绘制成一条由一条线连接的白点。

    # plot the sample as black circles
    solutions = asarray(solutions)
    pyplot.plot(solutions[:, 0], solutions[:, 1], '.-', color='w')

           综上所述,下面列出了对测试问题执行Nesterov动量优化并将结果绘制在轮廓图上的完整示例。

    # example of plotting the nesterov momentum search on a contour plot of the test function
    from math import sqrt
    from numpy import asarray
    from numpy import arange
    from numpy.random import rand
    from numpy.random import seed
    from numpy import meshgrid
    from matplotlib import pyplot
    from mpl_toolkits.mplot3d import Axes3D
    
    # objective function
    def objective(x, y):
    	return x**2.0 + y**2.0
    
    # derivative of objective function
    def derivative(x, y):
    	return asarray([x * 2.0, y * 2.0])
    
    # gradient descent algorithm with nesterov momentum
    def nesterov(objective, derivative, bounds, n_iter, step_size, momentum):
    	# track all solutions
    	solutions = list()
    	# generate an initial point
    	solution = bounds[:, 0] + rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0])
    	# list of changes made to each variable
    	change = [0.0 for _ in range(bounds.shape[0])]
    	# run the gradient descent
    	for it in range(n_iter):
    		# calculate the projected solution
    		projected = [solution[i] + momentum * change[i] for i in range(solution.shape[0])]
    		# calculate the gradient for the projection
    		gradient = derivative(projected[0], projected[1])
    		# build a solution one variable at a time
    		new_solution = list()
    		for i in range(solution.shape[0]):
    			# calculate the change
    			change[i] = (momentum * change[i]) - step_size * gradient[i]
    			# calculate the new position in this variable
    			value = solution[i] + change[i]
    			# store this variable
    			new_solution.append(value)
    		# store the new solution
    		solution = asarray(new_solution)
    		solutions.append(solution)
    		# evaluate candidate point
    		solution_eval = objective(solution[0], solution[1])
    		# report progress
    		print('>%d f(%s) = %.5f' % (it, solution, solution_eval))
    	return solutions
    
    # seed the pseudo random number generator
    seed(1)
    # define range for input
    bounds = asarray([[-1.0, 1.0], [-1.0, 1.0]])
    # define the total iterations
    n_iter = 50
    # define the step size
    step_size = 0.01
    # define momentum
    momentum = 0.8
    # perform the gradient descent search with nesterov momentum
    solutions = nesterov(objective, derivative, bounds, n_iter, step_size, momentum)
    # sample input range uniformly at 0.1 increments
    xaxis = arange(bounds[0,0], bounds[0,1], 0.1)
    yaxis = arange(bounds[1,0], bounds[1,1], 0.1)
    # create a mesh from the axis
    x, y = meshgrid(xaxis, yaxis)
    # compute targets
    results = objective(x, y)
    # create a filled contour plot with 50 levels and jet color scheme
    pyplot.contourf(x, y, results, levels=50, cmap='jet')
    # plot the sample as black circles
    solutions = asarray(solutions)
    pyplot.plot(solutions[:, 0], solutions[:, 1], '.-', color='w')
    # show the plot
    pyplot.show()

           运行示例将像以前一样执行搜索,但是在这种情况下,将创建目标函数的轮廓图。

           在这种情况下,我们可以看到在搜索过程中找到的每个解决方案都显示一个白点,从最优点开始,逐渐靠近图中心的最优点。

     

    展开全文
  • Nesterov加速算法

    2021-07-29 12:57:05
    8.2 最优化 Nesterov加速算法 理论介绍 Lipschitz 连续 Lipschitz 连续: 在一个连续函数fff上面额外施加了一个限制,要求存在一个常数K≥0K \geq 0K≥0使得定义域内的任意两个元素x1x_1x1​ 和 x2x_2x2​ 都满足 ∣...

    8.2 最优化 Nesterov加速算法

    理论介绍

    Lipschitz 连续

    Lipschitz 连续: 在一个连续函数 f f f上面额外施加了一个限制,要求存在一个常数 K ≥ 0 K \geq 0 K0使得定义域内的任意两个元素 x 1 x_1 x1 x 2 x_2 x2 都满足
    ∣ f ( x 1 ) − f ( x 2 ) ∣ ≤ K ∣ x 1 − x 2 ∣ |f(x_1) - f(x_2)| \leq K |x_1 - x_2| f(x1)f(x2)Kx1x2
    此时称函数 f f f的Lipschitz常数为 K

    简单理解,就是 f ′ ( x ) ≤ K , ∀ x ∈ R f'(x) \leq K, \forall x \in R f(x)K,xR R R R f f f的定义域

    梯度下降法:

    考虑以下线性转化问题:
    b = A x + w b = Ax + w b=Ax+w

    例如在图像模糊问题中, A为模糊模板(由未模糊图像通过转换而来), b为模糊图像, w为噪声。 并且, A 和 b已知, x为待求的系数。

    求解该问题的传统方法为最小二乘法,思想很简单,使得重构误差 ∣ ∣ A x − b ∣ ∣ 2 || Ax - b||^2 Axb2最小,即:
    x ^ = a r g min ⁡ x ∣ ∣ A x − b ∣ ∣ 2 \hat{x} = arg\min_x ||Ax- b||^2 x^=argxminAxb2
    f ( x ) = ∣ ∣ A x − b ∣ ∣ 2 f(x) = ||Ax - b||^2 f(x)=Axb2求导,可得其导数为: f ′ ( x ) = 2 A T ( A x − b ) f'(x) = 2A^T(Ax-b) f(x)=2AT(Axb)。 对于该问题,令导数为零即可以取得最小值(函数 f ( x ) f(x) f(x)为凸函数,其极小值为最小值)。

    1. 如果A为非奇异矩阵,即A可逆的话,那么可得该问题的精确解为 x = A − 1 b x = A^{-1}b x=A1b
    2. 如果A为奇异矩阵,即A不可逆,则该问题没有精确解。退而求其次,我们求一个近似解就好, ∣ ∣ A x − b ∣ ∣ 2 ≤ ϵ ||Ax-b||^2 \leq\epsilon Axb2ϵ

    m i n ∣ ∣ x ∣ ∣ 1 s . t . ∣ ∣ A x − b ∣ ∣ 2 ≤ ϵ min||x||_1 \\ s.t. ||Ax-b||^2 \leq \epsilon minx1s.t.Axb2ϵ

    其中, ∣ ∣ x ∣ ∣ 1 ||x||_1 x1为惩罚项,用以规范化参数 x x x。该例子使用L1范数作为惩罚项,是希望 x x x尽量稀疏(非零元素个数尽可能的少),即b是A的一个稀疏表示。 ∣ ∣ A x − b ∣ ∣ 2 ≤ ϵ ||Ax-b||^2 \leq \epsilon Axb2ϵ则为约束条件,即重构误差最小。问题(3)也可以描述为:
    min ⁡ x F ( x ) ≡ ∣ ∣ A x − b ∣ ∣ 2 + λ ∣ ∣ x ∣ ∣ 1 \min_x{F(x) \equiv ||Ax - b||^2 + \lambda||x||_1} xminF(x)Axb2+λx1
    式子(4)即为一般稀疏表示的优化问题。希望重构误差尽可能的小,同时参数的个数尽可能的少。

    注: 惩罚项也可以是L2或者其他范数。

    梯度下降法的缺陷

    考虑更为一般的情况,我们来讨论梯度下降法。有无约束的优化问题如下:
    min ⁡ x F ( x ) ≡ f ( x ) \min_x {F(x) \equiv f(x)} xminF(x)f(x)
    梯度下降法基于这样的观察:如果实值函数 F ( x ) F(x) F(x)在点 a a a处可微且有定义,那么函数 F ( x ) F(x) F(x)在点 a a a沿着梯度想反的方向 − ▽ F ( a ) -\triangledown F(a) F(a)下降最快。

    基于此,我们假设 f ( x ) f(x) f(x)连续可微。如果存在一个足够小的数值 t > 0 t>0 t>0使得 x 2 = x 1 − t ▽ F ( a ) x_2 = x_1 - t\triangledown F(a) x2=x1tF(a),那么:
    F ( x 1 ) ≥ F ( x 2 ) x 0 ∈ R n , x k = x k − 1 − t k ▽ f ( x k − 1 ) F(x_1) \geq F(x_2) \\ x_0 \in R^n, x_k = x_{k-1} - t_k \triangledown f(x_{k-1}) F(x1)F(x2)x0Rn,xk=xk1tkf(xk1)
    梯度下降法的核心就是通过式子(6)找到序列 x k {x_k} xk,使得 F ( x k ) ≥ F ( x k − 1 ) F(x_k) \geq F(x_{k-1}) F(xk)F(xk1)

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gpOl6ZTP-1627534604110)(E:\项目\8.2 最优化\梯度下降法.png)]

    从上图可以看出:初始点不同,获得的最小值也不同。因为梯度下降法求解的是局部最小值,受初值的影响较大。如果函数 f ( x ) f(x) f(x)为凸函数的话,则局部最小值亦为全局最小值。这时,初始点只对迭代速度有影响。

    再回头看一下式子(6),我们使用步长 t k t_k tk和倒数 ▽ F ( x k ) \triangledown F(x_k) F(xk)来控制每一次迭代时 x x x的变化量。再看一下上面的那张图,对于每一次迭代,我们当然希望 F ( x ) F(x) F(x)的值降得越快越好,这样我们就能更快速的获得函数的最小值。因此,步长 t k t_k tk的选择很重要。

    如果步长 t k t_k tk太小,则找到最小值的迭代次数非常多,即迭代速度非常慢,或者说收敛速度很慢;而步长太大的话,则会出现overshoot the minimum的现象,即不断在最小值左右徘徊,跳来跳去的。

    然而, t k t_k tk最后还是作用在 x k − 1 x_{k-1} xk1上,得到 x k x_k xk。因此,更为朴素的思想应该是:序列 x k {x_k} xk的个数尽可能小,即每一次迭代步伐尽可能大,函数值减少得尽可能的多。那么就是关于序列 x k {x_k} xk的选择了,如何更好的选择每一个点 x k x_k xk,使得函数值更快的趋紧其最小值。

    ISTA 算法

    ISTA(Iterative shrinkage-thresholding algorithm), 即 迭代阈值收缩算法。

    先从无约束优化问题开始, 即上面的式子(5):

    这时候,我们还假设 f ( x ) f(x) f(x)满足Lipschitz连续条件,即 f ( x ) f(x) f(x)的导数有下界,其最小下界称为Lipshitz常数 L ( f ) L(f) L(f)。这时,对于任意的 L ≥ L ( f ) L \geq L(f) LL(f), 有:
    f ( x ) ≤ f ( y ) + < x − y , ▽ f ( y ) > + L 2 ∣ ∣ x − y ∣ ∣ 2    ∀ x , y ∈ R n f(x) \leq f(y) + <x - y, \triangledown f(y)> + \frac L2||x-y||^2 \space \space \forall x,y \in R^n f(x)f(y)+<xy,f(y)>+2Lxy2  x,yRn
    基于此,在点 x k x_k xk附近可以把函数值近似为:
    f ^ ( x , x k ) = f ( x k ) + < ▽ f ( x k ) , x − x k > + L 2 ∣ ∣ x − x k ∣ ∣ 2 \hat{f}(x, x_k) = f(x_k) + <\triangledown f(x_k), x-x_k> + \frac L2 ||x-x_k||^2 f^(x,xk)=f(xk)+<f(xk),xxk>+2Lxxk2
    在梯度下降的每一步迭代中,将点 x k − 1 x_{k-1} xk1处的近似函数取得最小值的点作为下一次迭代的起始点 x k x_k xk,这就是所谓的Proximal Gradient Descent for L1 Regularization算法(其中, t k = 1 L t_k = \frac 1L tk=L1)。
    x k = a r g min ⁡ x { f ( x k − 1 + < x − x k − 1 , ▽ f ( x k − 1 ) > + 1 2 t k ∣ ∣ x − x k − 1 ∣ ∣ 2 ) } x_k = arg\min_x\{f(x_{k-1} + <x - x_{k-1}, \triangledown f(x_{k-1})> + \frac 1{2t_k}||x-x_{k-1}||^2)\} xk=argxmin{f(xk1+<xxk1,f(xk1)>+2tk1xxk12)}
    上面的方法只适合解决非约束问题。而ISTA要解决的是带惩罚项的优化问题,引入范数规范函数 g ( x ) g(x) g(x)对参数 x x x进行约束,如下:
    m i n { F ( x ) ≡ f ( x ) + g ( x ) : x ∈ R n } min\{F(x)\equiv f(x) + g(x): x\in R^n\} min{F(x)f(x)+g(x):xRn}
    使用更为一般的二次近似模型来求解上述的优化问题,在点 y , F ( x ) : = f ( x ) + g ( x ) y, F(x):=f(x) + g(x) y,F(x):=f(x)+g(x)的二次近似函数为:
    Q L ( x , y ) : = f ( y ) + < x − y , ▽ f ( y ) > + L 2 ∣ ∣ x − y ∣ ∣ 2 + g ( x ) Q_L(x, y) := f(y) + <x-y, \triangledown f(y)> + \frac L2||x-y||^2 + g(x) QL(x,y):=f(y)+<xy,f(y)>+2Lxy2+g(x)
    该函数的最小值表示为 : P L P_L PL是proximal(近端算子的简写形式)、
    P L ( y ) : = a r g min ⁡ x { Q L ( x , y ) : x ∈ R n } P_L(y) := arg\min_x\{Q_L(x,y): x\in R^n\} PL(y):=argxmin{QL(x,y):xRn}
    忽略其常数项 f ( y ) f(y) f(y) ▽ F ( y ) \triangledown F(y) F(y),这些有和没有对结果没有影响。再结合式子(11)和(12), P L ( y ) P_L(y) PL(y)可以写成:
    P L ( y ) = a r g min ⁡ x { g ( x ) + L 2 ∣ ∣ x − ( y − 1 L ▽ f ( y ) ) ∣ ∣ 2 } P_L(y) = arg\min_x\{g(x) + \frac L2||x-(y-\frac 1L \triangledown f(y))||^2\} PL(y)=argxmin{g(x)+2Lx(yL1f(y))2}
    显然,使用ISTA解决带约束的优化问题时的基本迭代步骤为:
    x k = P L ( x k − 1 ) x_k = P_L(x_k - 1) xk=PL(xk1)
    固定步长的ISTA的基本迭代步骤如下(步长 t = 1 / L ( f ) t = 1 / L(f) t=1/L(f)):

    ISTA with constant stepsize

    Input: $L := L(f) - A $ Lipschitz constant of ▽ f \triangledown f f.

    Step 0: Take x 0 ∈ R n x_0 \in R^n x0Rn

    Step k: (k >= 1) Compute
    x k = P L ( x k − 1 ) x_k = P_L(x_{k-1}) xk=PL(xk1)

    然而, 固定步长的ISTA的缺点是: Lipschitz常数 L ( f ) L(f) L(f)不一定可知或者计算。例如, L1范数约束的优化问题,其Lipschitz常数依赖于 A T A A^TA ATA的最大特征值。而对于大规模的问题,非常难计算。因此,使用以下带回溯(backtracking)的ISTA:

    ISTA with backtracking

    Step 0. Take L 0 > 0 L_0 > 0 L0>0,some η > 1 \eta > 1 η>1, and x 0 ∈ R n x_0 \in R^n x0Rn

    Step k. ( k ≥ 1 ) (k \geq 1) (k1) Find the smallest nonnegative intergers i k i_k ik such that with L ˉ = η i k L k − 1 \bar{L} = \eta^{i_k} L_{k-1} Lˉ=ηikLk1
    F ( P L ˉ ( x k − 1 ) ) ≤ Q L ˉ ( P L ˉ ( x k − 1 , x k − 1 ) ) F(P_{\bar{L}}(x_{k-1})) \leq Q_{\bar{L}}(P_{\bar{L}}(x_{k-1}, x_{k-1})) F(PLˉ(xk1))QLˉ(PLˉ(xk1,xk1))
    Set L k = η i k L k − 1 L_k = \eta ^ {i_k}L_{k-1} Lk=ηikLk1 and compute
    x k = P L k ( x k − 1 ) x_k = P_{L_k}(x_{k-1}) xk=PLk(xk1)

    FISTA (A fast iterative shrinkage-thresholding algorithm)是一种快速的迭代阈值收缩算法(ISTA)。

    FISTA 与 ISTA的区别在于迭代步骤中近似函数起始点y的选择。ISTA使用前一次迭代求得的近似函数最小值 x k − 1 x_{k-1} xk1,而FISTA则使用另一种方法来计算y的位置。

    FISTA with constant stepsize

    **Input: ** L = L ( f ) − A L = L(f) - A L=L(f)A Lipschitz constant of ▽ f \triangledown f f.

    Step 0. Take y 1 = x 0 ∈ R n y_1 = x_0 \in R^n y1=x0Rn t 1 = 1 t_1 = 1 t1=1.

    Step k. ( k ≥ 1 ) (k \geq 1) (k1) Compute
    x k = P L ( y k ) t k + 1 = 1 + 1 + 4 t k 2 2 , y k + 1 = x k + t k − 1 t k + ! ( x k − x k − 1 ) x_k = P_L(y_k) \\ t_{k+1} = \frac {1 + \sqrt{1+4t^2_k}}{2}, \\ y_{k+1} = x_k + \frac {t_k - 1}{t_{k+!}}(x_k - x_{k-1}) xk=PL(yk)tk+1=21+1+4tk2 ,yk+1=xk+tk+!tk1(xkxk1)

    当然,考虑到与ISTA同样的问题:问题规模大的时候,决定步长的Lipschitz常数计算复杂。FISTA与ISTA一样,亦有其回溯算法。在这个问题上,FISTA与ISTA并没有区别,上面也说了,FISTA与ISTA的区别仅仅在于每一步迭代时近似函数起始点的选择。更加简明的说:FISTA用一种更为聪明的办法选择序列 { x k } \{x_k\} {xk}, 使得其基于梯度下降思想的迭代过程更加快速地趋近问题函数 F ( x ) F(x) F(x)的最小值。

    第二类Nesterov加速算法

    对于 LASSO 问题:
    min ⁡ x 1 2 ∣ ∣ A x − b ∣ ∣ 2 + μ ∣ ∣ x ∣ ∣ 1 \min_x{ \frac 1 2||Ax - b||^2 + \mu||x||_1} xmin21Axb2+μx1
    利用第二类 Nesterov 加速的近似点梯度法进行优化。

    该算法被外层连续化策略调用,在连续化策略下完成某一固定正则化系数的内层迭代优化。第二类 Nesterov 加速算法的迭代格式如下:
    z k = ( 1 − γ k ) x k − 1 + γ k y k − 1 , y k = p r o x t k γ k h ( y k − 1 − t k γ k A T ( A z k − b ) ) , x k = ( 1 − γ k ) x k − 1 + γ k y k . z^{k} = (1-\gamma_k)x^{k-1} +\gamma_ky^{k-1}, \\ y^{k} = prox_{\frac{t_k}{\gamma_k}h}(y^{k-1}-\frac{t_k}{\gamma_k}A^T(Az^k-b)), \\ x^{k} = (1-\gamma_k)x^{k-1}+\gamma_ky^k. zk=(1γk)xk1+γkyk1,yk=proxγktkh(yk1γktkAT(Azkb)),xk=(1γk)xk1+γkyk.
    和经典FISTA算法的一个重要区别在于,第二类Nesterov加速算法中的三个序列{ x k x^k xk},{yk}和{zk}都可以保证在定义域内.而FISTA算法中的序列{ y k y^k yk}不一定在定义域内.
    y k = p r o x t k γ k h ( y k − 1 − t k γ k A T ( A z k − b ) ) y^{k} = prox_{\frac{t_k}{\gamma_k}h}(y^{k-1}-\frac{t_k}{\gamma_k}A^T(Az^k-b)) yk=proxγktkh(yk1γktkAT(Azkb))
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bFt5oq6d-1627534604113)(C:\Users\Maple\AppData\Roaming\Typora\typora-user-images\image-20210517192923458.png)]

    第三类Nesterov加速算法

    同样的,对于LASSO问题:
    min ⁡ x 1 2 ∣ ∣ A x − b ∣ ∣ 2 + μ ∣ ∣ x ∣ ∣ 1 \min_x{ \frac 1 2||Ax - b||^2 + \mu||x||_1} xmin21Axb2+μx1
    利用第三类 Nesterov 加速的近似点梯度法进行优化。其迭代格式如下:
    z k = ( 1 − γ k ) x k − 1 + γ k y k − 1 , y k = p r o x ( t k ∑ i = 1 k 1 γ i ) h ( − t k ∑ i = 1 k 1 γ i ∇ f ( z i ) , x k = ( 1 − γ k ) x k − 1 + γ k y k . z^{k} = (1-\gamma_k)x^{k-1} +\gamma_ky^{k-1}, \\ y^{k} = prox_{(t_k\sum_{i=1}^{k}{\frac{1}{\gamma_i}})h}(-t_{k}\sum_{i=1}^{k}{\frac{1}{\gamma_i}}\nabla{f(z^i)}, \\ x^{k} = (1-\gamma_k)x^{k-1}+\gamma_ky^k. zk=(1γk)xk1+γkyk1,yk=prox(tki=1kγi1)h(tki=1kγi1f(zi),xk=(1γk)xk1+γkyk.
    该算法和第二类Nesterov加速算法的区别仅仅在于 y k y^k yk的更新,第三类Nesterow加速算法计算 y k y^k yk时需要利用全部已有的 ∇ f ( z i ) , i = 1 , 2 , ⋯   , k \nabla{f(z^i)},i=1,2,\cdots,k f(zi),i=1,2,,k.

    比较

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-87bsvFfs-1627534604116)(C:\Users\Maple\AppData\Roaming\Typora\typora-user-images\image-20210517184956548.png)]

    可以看到:就固定步长而言,FISTA算法相较于第二类Nesterov加速算法收敛得略快一些,也可以注意到FISTA算法是非单调算法.同时,BB步长和线搜索技巧可以加速算法的收敛速度.此外,带线搜索的近似点梯度法可以比带线搜索的FISTA算法更加收敛.

    应用

    杂项

    梯度下降法中面临的挑战问题:

    1. 病态条件: 不同方向有不同的梯度, 学习率选择困难 (悬崖,跑到对面悬崖)
    2. 局部最小: 陷入局部最小点
    3. 鞍点:
      1. 梯度为0, Hessian矩阵同时存在正值和负值,
      2. Hessian矩阵的所有特征值为正值的概率很低
      3. 对于高维情况,鞍点和局部最小点的数量很多, 使用二阶优化算法会有问题。
    4. 平台区域, 梯度为0, Hessian矩阵也为0, 加入噪音使得从平台区域跳出

    动量法:

    • 主要想法:在参数更新时考虑历史梯度信息 保持惯性

    • 参数更新规则
      v t ← ρ v t − 1 − η ▽ J ( θ t ) θ t + 1 ← θ t + v t v_t \leftarrow \rho v_{t-1} - \eta \triangledown J(\theta_t) \\ \theta_{t+1} \leftarrow \theta_{t} +v_t vtρvt1ηJ(θt)θt+1θt+vt
      参数 ρ ∈ [ 0 , 1 ) \rho \in [0, 1) ρ[0,1)为历史梯度贡献的衰减速率,一般为 0.5、0.9或0.99

      η \eta η : 学习率

      ρ \rho ρ也可以随着迭代次数的增大而变大,随着时间推移调整 ρ \rho ρ比收缩 η \eta η更重要 , 动量法克制了SGD中的两个问题

      • Hessian矩阵的病态问题(右图图解)
      • 随机梯度的方差带来的不稳定

    Nesterov 动量法:

    • 受 Nesterov 加速梯度算法 NGA 的启发

    • 梯度计算在施加当前速度之后

    • 在动量法的基础上添加了一个校正因子(correction factor)
      v t ← ρ v t − 1 − η ▽ J ( θ t + ρ v t − 1 ) θ t + 1 ← θ t + v t v_t \leftarrow \rho v_{t-1} - \eta \triangledown J(\theta_t + \rho v_{t-1}) \\ \theta_{t+1} \leftarrow \theta_{t} +v_t vtρvt1ηJ(θt+ρvt1)θt+1θt+vt

    AdaGrad

    • 学习率自适应:与梯度历史平方值的综合的平方根成反比

    • 效果: 更为平缓的倾斜方向上回去的更大的进步,可能逃离鞍点

    • 问题:理解题都平方和增长过快,导致学习率较小,提前终止学习。
      s t ← s t − 1 + ▽ J ( θ t ) ∗ ▽ J ( θ t ) θ t + 1 ← θ t − η s t ▽ J ( θ t ) s_t \leftarrow s_{t-1} + \triangledown J(\theta_t) * \triangledown J(\theta_t) \\ \theta_{t+1} \leftarrow \theta_t - \frac \eta{\sqrt{s_t}}\triangledown J(\theta_t) stst1+J(θt)J(θt)θt+1θtst ηJ(θt)

    RMSProp

    • 在AdaGrad基础上,降低了对早期历史梯度的依赖

    • 通过设置衰减系数 β 2 \beta_2 β2实现

    • 建议 β 2 \beta_2 β2 = 0.9
      s t ← β 2 s t − 1 + ( 1 − β 2 ) θ t + 1 ← θ t − η s t ▽ J ( θ t ) s_t \leftarrow \beta_2 s_{t-1} + (1 - \beta_2) \\ \theta_{t+1} \leftarrow \theta_t - \frac {\eta}{\sqrt{s_t}} \triangledown J(\theta_t) stβ2st1+(1β2)θt+1θtst ηJ(θt)

    Adam

    • 同时考虑动量和学习率自适应

    • β 1 \beta_1 β1通常设置成0.9, β 2 \beta_2 β2设置成0.999
      v t ← β 1 v t − 1 − ( 1 − β 1 ) ▽ J ( θ t ) s t ← β 2 s t − 1 − ( 1 − β 2 ) ▽ J ( θ t ) ∗ ▽ J ( θ t ) θ t + 1 ← θ t − η v t s t v_t \leftarrow \beta_1 v_{t-1} - (1 - \beta_1)\triangledown J(\theta_t) \\ s_t \leftarrow \beta_2 s_{t-1} - (1 - \beta_2) \triangledown J(\theta_t) * \triangledown J(\theta_t) \\ \theta_{t+1} \leftarrow \theta_t - \eta \frac {v_t}{\sqrt{s_t}} vtβ1vt1(1β1)J(θt)stβ2st1(1β2)J(θt)J(θt)θt+1θtηst vt

    参考文献

    参考文献

    展开全文
  • Nesterov Accelerated Gradient Descent-Based Convolution Neural Network with Dropout for Facial Expression Recognition
  • 当动量梯度下降出来之后不久,就有大神再次提出nesterov梯度下降的方法,也是继承了动量梯度的思修,但是它认为,即使当前的梯度为0,由于动量的存在,更新梯度依然会存在并继续更新w。 而继续当前点w的梯度是不太有...

    对于梯度下降,只能说:没有最可怕,只有更可怕。
    当动量梯度下降出来之后不久,就有大神再次提出nesterov梯度下降的方法,也是继承了动量梯度的思修,但是它认为,即使当前的梯度为0,由于动量的存在,更新梯度依然会存在并继续更新w。

    而继续当前点w的梯度是不太有意义的,有意义的是,假设下一个点w(仅靠动量滚到下一个点的w)的梯度方向才是决定当前梯度的重要因素。

    举个通俗的例子就是,你在下坡时,如果在下坡快到底,但又未到底时,动量梯度下降会让你冲到坡的对面去Nesterov梯度下降会预知你的下一步将会时到坡的对面去,所以会提示你提前刹车,避免过度冲到坡的对面去。这包含了一种提前计算下一步的梯度,来指导当前梯度的想法。

    而这个怎么实现呢?先看公式:
    o l d w = w oldw=w oldw=w
    w = w − η ∗ l g ∗ d i s c o u n t w=w-\eta*lg*discount w=wηlgdiscount
    计算下一个 w w w的梯度
    w = o l d w w=oldw w=oldw
    l g = l g ∗ d i s c o u n t + g lg=lg*discount+g lg=lgdiscount+g
    w = w − η ∗ l g w=w-\eta*lg w=wηlg

    就是每次计算梯的时候用下一次的权重,这样下一次的变化就会反应在这次计算的梯度上,如果下一次权重计算的梯度很大,则说明更新权重的时候更应该把下一次的梯度给加上去。

    '''
    普通的全梯度下降方法
    '''
    import numpy as np
    import math 
    import time
    
    print(__doc__)
    
    sample = 10
    num_input = 5
    
    #加入训练数据
    np.random.seed(0)
    normalRand = np.random.normal(0,0.1,sample)      # 10个均值为0方差为0.1 的随机数  (b)
    weight = [5,100,-5,-400,0.02]                    # 1 * 5 权重
    x_train = np.random.random((sample, num_input))  # x 数据(10 * 5)
    y_train = np.zeros((sample,1))                   # y数据(10 * 1)
    
    for i in range (0,len(x_train)):
        total = 0
        for j in range(0,len(x_train[i])):
            total += weight[j]*x_train[i,j]
        y_train[i] = total+ normalRand[i]
    
    # 训练
    np.random.seed(0)
    weight = np.random.random(num_input+1)
    np.random.seed(0)
    recordGrade  = np.random.random(num_input+1)
    
    discount = 0.9
    rate = 0.02
    
    start = time.clock()
    for epoch in range(0,500):
        #预先走一步,计算下一个的权重w
        oldweight = np.copy(weight)
        for i in range(0,len(weight)):
            weight[i] = weight[i] - rate * discount *  recordGrade[i]
    
        # 计算loss
        predictY = np.zeros((len(x_train))) 
        for i in range(0,len(x_train)):
            predictY[i] = np.dot(x_train[i],weight[0:num_input])+ weight[num_input]
    
        loss = 0
    
    
        for i in range(0,len(x_train)):
            loss += (predictY[i]-y_train[i])**2     
        print("epoch: %d-loss: %f"%(epoch,loss))  #打印迭代次数和损失函数
    
        if loss < 0.1:
            end = time.clock()
            print("收敛时间:%s ms"%str(end-start))
            print("收敛成功%d-epoch"%epoch)
            break
    
        # 计算梯度并更新
        weight = oldweight
    
        for i in range(0,len(weight)-1):   #权重w
            grade = 0
            for j in range(0,len(x_train)):
                grade += 2*(predictY[j]-y_train[j])*x_train[j,i]
            #计算梯度用下一个权重,计算权重用原来的
            recordGrade[i] = recordGrade[i]*discount + grade
            weight[i] = weight[i] - rate*recordGrade[i]
    
        grade = 0
        for j in range(0,len(x_train)):    #偏差b
    
            grade += 2*(predictY[j]-y_train[j])
        recordGrade[num_input]   = recordGrade[num_input]*discount + grade
        weight[num_input] = weight[num_input] - rate*recordGrade[num_input]
    
    print(weight)
    
    
    展开全文
  • (由于Nesterov方法有多种不同的实现方法,这里我们采用的是PyTorch的官方文档中给出的公式,这个公式是我根据PyTorch中原始公式进行相应扩展得出的) 其公式如下: vt+1=μ∗vt+α∗gtpt+1=pt−lr∗(vt+1+α∗gt)...

    1 前言

    感谢网友“天泽28”的帮助,
    原文链接如下:
    https://blog.csdn.net/u012328159/article/details/80311892

    2 Nesterov方法的公式

    2.1 夏侯南溪采用的Nesterov公式

    这里我们最终选择的是根据 Neural Network Libraries文档中公式经过扩展,延伸得到的公式;
    我觉得这样的公式是最容易理解的,也是最符合我们的认知的,相应的公式为:
    v t + 1 = γ v t − η ∗ ∇ w t J ( w t ) w t + 1 = w t − γ v t + ( 1 + γ ) ∗ v t + 1 v_{t+1} = \gamma v_t - \eta*\nabla_{w_t}J(w_t)\\ w_{t+1} = w_t - \gamma v_t + (1 + \gamma)*v_{t+1} vt+1=γvtηwtJ(wt)wt+1=wtγvt+(1+γ)vt+1
    我们将梯度下降的过程想象为小球从斜坡上下降的过程,这里的 v t v_t vt指当前时刻t小球的速度, ∇ w t J ( w t ) \nabla_{w_t}J(w_t) wtJ(wt)为当前的梯度值、也是小球的外力(可以理解为是重力加速度在当前斜坡方向上的分力), w t w_t wt为小球在t时刻小球的参数超平面坐标, η \eta η为学习率;

    2.2 Sutskever论文中的公式

    原始公式出自于 Ilya Sutskever和 Geoffrey Hinton等人的文章《On the importance of initialization and momentum in deep learning》,
    在这里插入图片描述
    (这里我参阅了网友“天泽28”的博文《深度学习中优化方法——momentum、Nesterov Momentum、AdaGrad、Adadelta、RMSprop、Adam》,里面对Nesterov方法及相关资料分析的十分清晰);
    而由于这个公式难以实现,可以看到导数内部还存在一个因式“ θ t + μ v t \theta_t + \mu v_t θt+μvt”,所以在实现时,一般会采用其它的公式;

    2.3 PyTorch文档中使用的公式

    (由于Nesterov方法有多种不同的实现方法,下面列出的是PyTorch的官方文档中给出的公式,这个公式是我根据PyTorch中原始公式进行相应扩展得出的)
    其公式如下:
    v t + 1 = μ ∗ v t + α ∗ g t p t + 1 = p t − l r ∗ ( v t + 1 + α ∗ g t ) v_{t+1} = \mu*v_{t} + \alpha*g_{t}\\ p_{t+1} = p_t - lr*(v_{t+1} + \alpha*g_{t}) vt+1=μvt+αgtpt+1=ptlr(vt+1+αgt)

    仔细一看,我发现这个跟PyTorch中提供的公式还是有些区别,这里我们来进行一下推导和解释,
    首先,需要说明的是:
    PyTorch中的 v P v^P vP累积的是正梯度,所以最后在更新参数时是相减,用“ − - 号 ”;
    Sutskever等人的论文中 v S v^S vS累积的是负梯度,所以最后在更新参数时是相加,用“ + + +号 ”;
    所以有 v P = − v S v^P=-v^S vP=vS

    3 Nesterov南溪选择的公式与论文原始公式等价性的证明

    对于Nesterov原始公式与其等价公式的证明,之前我一直没有看懂,不太懂两个公式的条件和结论到底分别是什么,
    赵老师和其他同学在证明的时候,各种不同的带入推导看似很有道理,
    在我看来,却没有什么逻辑性:
    一个很重要的原因是,他们在推导的时候并没有明确证明的条件和结论,所以一直很难看懂;还有一点就是,他们选择的公式有点复杂,不容易理解,所以我们这里就不进行赘述了;
    这里我们对南溪选择的公式和原始论文公式的等价性进行证明,
    已知条件:
    我们已知Nesterov算法的两种递推公式,分别为:
    Sutskever原始论文的公式(“公式S”),
    v t + 1 = μ ∗ v t − ε ∇ f ( θ t + μ ∗ v t ) θ t + 1 = θ t + v t + 1 v_{t+1} = \mu*v_{t} - \varepsilon\nabla f\left ( \theta_t+ \mu*v_{t}\right )\\ \theta_{t+1} = \theta_t + v_{t+1} vt+1=μvtεf(θt+μvt)θt+1=θt+vt+1
    南溪选择的公式(“公式N”),
    v t + 1 = γ v t − η ∗ ∇ w t J ( w t ) w t + 1 = w t − γ v t + ( 1 + γ ) ∗ v t + 1 v_{t+1} = \gamma v_t - \eta*\nabla_{w_t}J(w_t)\\ w_{t+1} =w_t - \gamma v_t + (1 + \gamma)*v_{t+1} vt+1=γvtηwtJ(wt)wt+1=wtγvt+(1+γ)vt+1
    证明:
    两个公式是等价的;
    解:
    我们首先将原始公式进行一些改写,以方便我们进行理解,
    v t + 1 = γ ∗ v t − η Δ θ t + γ ∗ v t J ( θ t + γ ∗ v t ) θ t + 1 = θ t + v t + 1 v_{t+1} = \gamma*v_{t} - \eta\Delta_{ \theta_t+ \gamma*v_{t}}J\left ( \theta_t+ \gamma*v_{t}\right )\\ \theta_{t+1} = \theta_t + v_{t+1} vt+1=γvtηΔθt+γvtJ(θt+γvt)θt+1=θt+vt+1
    这里导数函数 ∇ f \nabla f f的自变量和求导变量都是因式 θ t + μ ∗ v t \theta_t+ \mu*v_{t} θt+μvt
    那么两个公式的等价性该如何证明呢,我们还是要回到问题的本身,
    这里的需求是找到一种形如“ θ j = θ j − α ∂ ∂ θ j J ( θ ) \theta_j = \theta_j - \alpha\frac{\partial}{\partial\theta_j}J\left(\theta\right) θj=θjαθjJ(θ)”形式的公式,因为原始公式难以实现的原因就是导函数的自变量和求导变量都是一个子式,这是比较麻烦的;
    为了能够简化计算,我们最好能将求导函数的自变量整合成一个变量,于是我们想到的方法就是换元;
    于是我们令 w t = θ t + γ ∗ v t w_t = \theta_t+ \gamma*v_{t} wt=θt+γvt
    但是还有一个问题,换元之后怎么办呢, θ t \theta_t θt w t w_t wt是什么关系呢,难道我们要使用 w t w_t wt替代参数 θ t \theta_t θt吗,但是我们本来要求的不是模型参数 θ t \theta_t θt的局部最优解吗,怎么可以使用另一个参数代替呢,
    别担心,答案是可以的;
    在0时刻,有 w 0 = θ 0 + γ ∗ v 0 w_0 = \theta_0+ \gamma*v_0 w0=θ0+γv0,而由于初始速度 v 0 = 0 v_0=0 v0=0,则有 w 0 = θ 0 w_0 = \theta_0 w0=θ0
    而当 t → + ∞ t \rightarrow +\infty t+时, v t v_t vt无限趋近于0,这一点是可以想到的是因为当小球达到谷底时(也就是无限趋近与当前的局部最优解时),速度会下降到几乎为0
    ∴有 lim ⁡ t → + ∞ v t = 0 \lim_{t\rightarrow+\infty}v_t=0 limt+vt=0,且 lim ⁡ t → + ∞ w t = θ t \lim_{t\rightarrow+\infty}w_t=\theta_t limt+wt=θt
    由此可知,我们可以使用 w t w_t wt来代替 θ t \theta_t θt进行迭代计算,
    于是我们将 w t = θ t + γ ∗ v t w_t = \theta_t + \gamma*v_t wt=θt+γvt带入公式S,则有
    v t + 1 = γ ∗ v t − η ∇ w t f ( w t ) w t + 1 − γ ∗ v t + 1 = w t − γ ∗ v t + v t + 1 v_{t+1} = \gamma*v_{t} - \eta\nabla _{w_t}f\left(w_t\right )\\ w_{t + 1} - \gamma*v_{t + 1} = w_t - \gamma*v_t + v_{t+1} vt+1=γvtηwtf(wt)wt+1γvt+1=wtγvt+vt+1
    化简得
    v t + 1 = γ ∗ v t − η ∇ w t f ( w t ) w t + 1 = w t + ( 1 + γ ) v t + 1 − γ ∗ v t v_{t+1} = \gamma*v_{t} - \eta\nabla _{w_t}f\left(w_t\right )\\ w_{t + 1} = w_t + (1+\gamma)v_{t+1} - \gamma*v_t vt+1=γvtηwtf(wt)wt+1=wt+(1+γ)vt+1γvt
    与公式N相同,所以原命题得证;

    展开全文
  • 初始化方式为: optimizer = torch.optim.SGD(model.parameters(), lr=1e-3, momentum=0.9, nesterov=True) 需要注意__init__处有这样的判断: if nesterov and (momentum != 0): raise ValueError("Nesterov ...
  • Nesterov动量更新方法理解要点

    千次阅读 2019-04-24 10:24:31
    为了解释Nesterov动量更新的原理,我们从速度更新表达式开始说起。 v = mu * v - learning_rate * dx (为了说明下面的推论还是需要一些前提的,为了不影响整体感,把这些放到本小节的后面) 其实这个式子背后提现...
  • GradientDescent、Momentum(动量)、Nesterov(牛顿动量)的直觉含义对比: Gradient Descent def gd(x_start, step, g):#gradient descent x = np.array(x_start, dtype='float64') # print(x) passing_...
  • —momentum、Nesterov Momentum、AdaGrad、Adadelta、RMSprop、Adam— &amp;amp;amp;nbsp;&amp;amp;amp;nbsp;&amp;amp;amp;nbsp;&amp;amp;amp;nbsp;&amp;amp;amp;nbsp;&amp;amp;amp;nbsp;&...
  • 入门神经网络优化算法(一):Gradient Descent,Momentum,Nesterov accelerated gradient 入门神经网络优化算法(二):Adaptive Optimization Methods:Adagrad,RMSprop,Adam 入门神经网络优化算法(三):待定...
  • 梯度下降、随机梯度下降、小批量梯度下降、动量梯度下降、Nesterov加速梯度下降法前言梯度下降法(Gradient Descent / GD)单变量线性回归模型(Univariate Linear Regression)批梯度下降法(Batch Gradient ...
  • 深度学习中常用的优化算法(SGD, Nesterov,Adagrad,RMSProp,Adam)总结 1. 引言 在深度学习中我们定义了损失函数以后,会采取各种各样的方法来降低损失函数,从而使模型参数不断的逼近于真实数据的表达。不过损失函数...
  • 文章目录一、一个框架回顾优化算法1、SGD算法:评价:2、SGDM (SGD with Momentum)算法:评价:3、SGD with Nesterov Acceleration4、AdaGrad5、AdaDelta / RMSProp6、Adam7、Nadam二、关于Adam的分析1、Adam存在的...
  • 使用动量(Momentum)的SGD、使用Nesterov动量的SGD 参考:使用动量(Momentum)的SGD、使用Nesterov动量的SGD 一. 使用动量(Momentum)的随机梯度下降 虽然随机梯度下降是非常受欢迎的优化方法,但其学习过程有时会很慢...
  • Nesterov's accelerated gradient descent https://blog.csdn.net/tsyccnh/article/details/76673073 看上面一张图仔细想一下就可以明白,Nesterov动量法和经典动量法的差别就在B点和C点梯度的不同。 公式推导...
  • Nesterov Accelerated Gradient 这篇文章主要介绍动量法以及Nesterov法,来源于: https://medium.com/konvergen/momentum-method-and-nesterov-accelerated-gradient-487ba776c987 之所以把这两个内容...
  • 于是一位大神(Nesterov)就开始思考,既然每一步都要将两个梯度方向(历史梯度、当前梯度)做一个合并再下降,那为什么不先按照历史梯度往前走那么一小步,按照前面一小步位置的“超前梯度”来做梯度合并呢?...
  • SGD/Momentum/Nesterov

    千次阅读 2018-10-20 22:20:09
    今天看pytorch的SGD发现了关于SGD的三种扩展,分别是SGD, Momentum, Nesterov 下面整理一下三个的原理和区别: SGD Stochastic Gradient Descent param -= lr * gradient Momentum 由于采用SGD时,使用mini-batch...
  • 文章的内容包括了Momentum、Nesterov Accelerated Gradient、AdaGrad、AdaDelta和Adam,在这么多个优化算法里面,一个妖艳的贱货(划去)成功地引起了我的注意——Nesterov Accelerated Gradient,简称NAG。...
  • Nesterov Momentum牛顿动量法

    千次阅读 2018-07-30 00:02:53
    Nesterov Momentum 这是对之前的Momentum的一种改进,大概思路就是,先对参数进行估计,然后使用估计后的参数来计算误差 具体实现:  需要:学习速率 ϵ, 初始参数 θ, 初始速率v, 动量衰减参数α 每步迭代过程:  1...
  • —momentum、Nesterov Momentum、AdaGrad、Adadelta、RMSprop、Adam—  我们通常使用梯度下降来求解神经网络的参数,关于梯度下降前面一篇博客已经很详细的介绍了(几种梯度下降方法对比)。我们在梯度下降时,...
  • Nesterov牛顿动量法

    2020-11-24 01:31:10
    1.Nesterov是Momentum的变种。 2.与Momentum唯一区别就是,计算梯度的不同,Nesterov先用当前的速度v更新一遍参数,在用更新的临时参数计算梯度。 3.相当于添加了矫正因子的Momentum。 4.在GD下,Nesterov将误差收敛...
  • Nesterov可将 θt−η∗μ∗mt−1\theta_{t}-\eta * \mu * m_{t-1}θt​−η∗μ∗mt−1​看做当前优化的一个“展望”项,对该项进行求导,让之前的动量直接影响当前梯度 gtg_{t}gt​。 gt=∇θtf(θt−η∗μ∗mt−...
  • NESTEROV ACCELERATED GRADIENT AND SCALE INVARIANCE FOR ADVERSARIAL ATTACKS(Nesterov 加速梯度和缩放不变性攻击) 摘要 深度学习模型对于在良性输入的运用人类不可察觉的扰动所构造的对抗样本具有脆弱性。然而...
  • “随机梯度下降、牛顿法、动量法、Nesterov、AdaGrad、RMSprop、Adam”随机梯度下降法牛顿法动量法Nesterov学习率应该慢慢减小的。AdaGradRMSpropAdamNadam 随机梯度下降法 怎么减小每次计算的参数量? 梯度下降法性...
  • Nesterov Momentum简介

    2021-04-07 11:38:29
    Nesterov Momentum Update:理论上受益于凸函数的收敛保证,实际中也往往较优于标准的动量更新。 其核心思想是,计算“预览”位置的梯度而不是当前位置的梯度。计算梯度之前,由于动量项的作用是轻推参数向量mu*v,...
  • 梯度下降(二):自适应学习率(AdaGrad)、均方根传递(RMSProp)、自适应增量(AdaDelta)、自适应性矩估计(Adam)Nesterov自适应性矩估计(Nadam)前言自适应梯度(AdaGrad / Adaptive Gradient)均方根传递...
  • 比Momentum更快:揭开Nesterov Accelerated Gradient的真面目 转自:https://zhuanlan.zhihu.com/p/22810533 作为一个调参狗,每天用着深度学习框架提供的各种优化算法如Momentum、AdaDelta、Adam等,却对其中的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,428
精华内容 2,971
关键字:

nesterov