划重点!十分钟掌握牛顿法凸优化

简介: 之前,我发过一篇文章,通俗地解释了梯度下降算法的数学原理和推导过程,推荐一看。链接如下:简单的梯度下降算法,你真的懂了吗?

我们知道,梯度下降算法是利用梯度进行一阶优化,而今天我介绍的牛顿优化算法采用的是二阶优化。本文将重点讲解牛顿法的基本概念和推导过程,并将梯度下降与牛顿法做个比较。


1   牛顿法求解方程的根


有时候,在方程比较复杂的情况下,使用一般方法求解它的根并不容易。牛顿法通过迭代的方式和不断逼近的思想,可以近似求得方程较为准确的根。


牛顿法求根的核心思想是泰勒一阶展开。例如对于方程 f(x) = 0,我们在任意一点 x0 处,进行一阶泰勒展开:

image.png

image.png

image.png

image.png


2   牛顿法凸优化


上一部分介绍牛顿法如何求解方程的根,这一特性可以应用在凸函数的优化问题上。


机器学习、深度学习中,损失函数的优化问题一般是基于一阶导数梯度下降的。现在,从另一个角度来看,想要让损失函数最小化,这其实是一个最值问题,对应函数的一阶导数 f'(x) = 0。也就是说,如果我们找到了能让 f'(x) = 0 的点 x,损失函数取得最小值,也就实现了模型优化目标。


现在的目标是计算 f'(x) = 0 对应的 x,即 f'(x) = 0 的根。转化为求根问题,就可以利用上一节的牛顿法了。


与上一节有所不同,首先,对 f(x) 在 x0 处进行二阶泰勒展开:

image.png

image.png

3  梯度下降 VS 牛顿法


现在,分别写出梯度下降和牛顿法的更新公式:

image.png


梯度下降算法是将函数在 xn 位置进行一次函数近似,也就是一条直线。计算梯度,从而决定下一步优化的方向是梯度的反方向。而牛顿法是将函数在 xn 位置进行二阶函数近似,也就是二次曲线。计算梯度和二阶导数,从而决定下一步的优化方向。一阶优化和二阶优化的示意图如下所示:

image.png


以上所说的是梯度下降和牛顿法的优化方式差异。那么谁的优化效果更好呢?


首先,我们来看一下牛顿法的优点。第一,牛顿法的迭代更新公式中没有参数学习因子,也就不需要通过交叉验证选择合适的学习因子了。第二,牛顿法被认为可以利用到曲线本身的信息, 比梯度下降法更容易收敛(迭代更少次数)。如下图是一个最小化一个目标方程的例子, 红色曲线是利用牛顿法迭代求解, 绿色曲线是利用梯度下降法求解。显然,牛顿法最优化速度更快一些。


image.png


然后,我们再来看一下牛顿法的缺点。我们注意到牛顿法迭代公式中除了需要求解一阶导数之外,还要计算二阶导数。从矩阵的角度来说,一阶导数和二阶导数分别对应雅可比矩阵(Jacobian matrix)和海森矩阵(Hessian matrix)。

image.png


牛顿法不仅需要计算 Hessian 矩阵,而且需要计算 Hessian 矩阵的逆。当数据量比较少的时候,运算速度不会受到大的影响。但是,当数据量很大,特别在深度神经网络中,计算 Hessian 矩阵和它的逆矩阵是非常耗时的。从整体效果来看,牛顿法优化速度没有梯度下降算法那么快。所以,目前神经网络损失函数的优化策略大多都是基于梯度下降。


值得一提的是,针对牛顿法的缺点,目前已经有一些改进算法。这类改进算法统称拟牛顿算法。比较有代表性的是 BFGS 和 L-BFGS。


BFGS 算法使用近似的方法来计算 Hessian 矩阵的逆,有效地提高了运算速度。但是仍然需要将整个 Hessian 近似逆矩阵存储起来,空间成本较大。


L-BFGS 算法是对BFGS 算法的改进,不需要存储 Hessian 近似逆矩阵, 而是直接通过迭代算法获取本轮的搜索方向,空间成本大大降低。


总的来说,基于梯度下降的优化算法,在实际应用中更加广泛一些,例如 RMSprop、Adam等。但是,牛顿法的改进算法,例如 BFGS、L-BFGS 也有其各自的特点,也有很强的实用性。

相关文章
|
7月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-基础练习 圆的面积
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-基础练习 圆的面积
69 0
|
7月前
最大流圆桌问题(二分图多重匹配问题)
最大流圆桌问题(二分图多重匹配问题)
56 0
|
4月前
|
人工智能 算法 新能源
【2023高教社杯】A题 定日镜场的优化设计 问题分析及数学模型
本文介绍了2023年高教社杯数学建模竞赛A题的定日镜场优化设计问题,涉及问题分析和数学模型构建,旨在提高太阳能光热发电效率并实现电力系统的新能源转型。
104 1
【2023高教社杯】A题 定日镜场的优化设计 问题分析及数学模型
|
7月前
|
机器学习/深度学习 算法 测试技术
青蛙跳台阶:我如何得知它是一道斐波那契数列题?——应用题破题“三板斧”(二)
这篇内容是关于解题策略的,主要介绍了在面对应用题时可以采用的“三板斧”方法:举例、模拟和找规律。通过一个走楼梯的例子详细解释了这三个步骤如何运用。首先,举例将抽象问题具体化,比如走5级台阶有几种方式。其次,通过模拟不同情况,例如思考走每一步的可能,发现递归或循环的模式。最后,通过找规律归纳出一般性的解决方案,这里发现走台阶问题与斐波那契数列相关。文章还提到了一个拓展案例——矩形覆盖问题,同样可以用类似的方法分析。总的来说,文章强调了解题过程中理解和转化问题的重要性,以及通过训练提升这方面能力。
62 0
|
7月前
|
C语言
青蛙跳台阶:我如何得知它是一道斐波那契数列题?——应用题破题“三板斧”(一)
这篇内容介绍了C语言学习中的经典例题——斐波那契数列,强调了解题思路的重要性。斐波那契数列是一个数列,其中每个数是前两个数的和。文章指出,很多类似题目,如“青蛙跳台阶”,实质上都在考察斐波那契数列的实现。文中提供了斐波那契数列的定义、代码实现和递归与非递归的思路,并鼓励读者从问题中分析出解题模型,而非直接套用已知方法。此外,还提及了一道相关题目“矩形覆盖问题”,以供进一步练习。
62 0
|
7月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-436 算法训练 正六边形
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-436 算法训练 正六边形
51 1
|
7月前
|
算法 Java C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-6 算法训练 安慰奶牛 最小生成树
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-6 算法训练 安慰奶牛 最小生成树
50 0
|
机器学习/深度学习 人工智能 自然语言处理
扩散模型背后数学太难了,啃不动?谷歌用统一视角讲明白了
扩散模型背后数学太难了,啃不动?谷歌用统一视角讲明白了
250 0
|
存储 算法 C++