牛顿迭代法的可视化详解

2024-04-13 18:58

本文主要是介绍牛顿迭代法的可视化详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

b6c7f9bf7ed112d7aafe0159a810c17b.png

来源:DeepHub IMBA
本文约1800字,建议阅读10分钟
本文利用可视化方法,为你直观地解析牛顿迭代法。

牛顿迭代法(Newton's method)又称为牛顿-拉夫逊(拉弗森)方法(Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

以 Isaac Newton 和 Joseph Raphson 命名的 Newton-Raphson 方法在设计上是一种求根算法,这意味着它的目标是找到函数 f(x)=0 的值 x。在几何上可以将其视为 x 的值,这时函数与 x 轴相交。

Newton-Raphson 算法也可以用于一些简单的事情,例如在给定之前的连续评估成绩的情况下,找出预测需要在期末考试中获得 A 的分数。其实如果你曾经在 Microsoft Excel 中使用过求解器函数,那么就使用过像 Newton-Raphson 这样的求根算法。另外一个复杂用例是使用 Black-Scholes 公式反向求解金融期权合约的隐含波动率。

Newton-Raphson公式

1432e8b450bd192cf16a8f3c1da24e70.png

虽然公式本身非常简单,但如果想知道它实际上在做什么就需要仔细查看。

首先,让我们回顾一下整体方法:

1. 初步猜测根可能在哪里?

a5a39604026c80ba80298dbbe27506ee.png

2. 应用 Newton-Raphson 公式获得更新后的猜测,该猜测将比初始猜测更接近根。

3. 重复步骤 2,直到新的猜测足够接近真实值。

这样就足够了吗?Newton-Raphson 方法给出了根的近似值,尽管通常它对于任何合理的应用都足够接近!但是我们如何定义足够接近?什么时候停止迭代?

一般情况下Newton-Raphson 方法有两种处理何时停止的方法。1、如果猜测从一个步骤到下一步的变化不超过阈值,例如 0.00001,那么算法将停止并确认最新的猜测足够接近。2、如果我们达到一定数量的猜测但仍未达到阈值,那么我们就放弃继续猜测。

b3cc316b88e5a13d02dfd793d97e6aaf.png

从公式中我们可以看到,每一个新的猜测都是我们之前的猜测被某个神秘的数量调整了🔮。如果我们通过一个例子来可视化这个过程,它很快就会清楚发生了什么!

9a2b7ff270088cc8e9b9d52025d3fef6.png

0a287e723d229dbad7d0e26de591265e.png

作为一个例子,让我们考虑上面的函数,并做一个 x=10 的初始猜测(注意这里实际的根在 x=4)。Newton-Raphson 算法的前几个猜测在下面的 GIF 中可视化👇

e76f7ddeb7e2e6febec0828e54e7f0cb.gif

我们最初的猜测是 x=10。为了计算我们的下一个猜测,我们需要评估函数本身及其在 x=10 处的导数。在 10 处求值的函数的导数只是简单地给出了该点切线曲线的斜率。该切线在 GIF 中绘制为 Tangent 0。

看下一个猜测相对于前一个切线出现的位置,你注意到什么了吗?下一个猜测出现在前一个切线与 x 轴相交的位置。这就是 Newton-Raphson 方法的亮点!

e5f49adad3658b95fca6f0eef9539cf7.png

事实上, f(x)/f'(x) 只是给出了我们当前猜测与切线穿过 x 轴的点之间的距离(在 x 方向上)。正是这个距离告诉我们每次更新的猜测是多少,正如我们在 GIF 中看到的那样,随着我们接近根本身,更新变得越来越小。

b29567e6e68952aedf3eb782b8108860.png


如果函数无法手动微分怎么办?

上面的例子中是一个很容易用手微分的函数,这意味着我们可以毫无困难地计算 f'(x)。然而,实际情况可能并非如此,并且有一些有用的技巧可以在不需要知道其解析解的情况下逼近导数。

这些导数逼近方法超出了本文的范围,可以查找有关有限差分方法的更多信息。

问题

敏锐的读者可能已经从上面的示例中发现了一个问题,示例函数有两个根(x=-2 和 x=4),Newton-Raphson 方法也只能识别一个根。牛顿迭代会根据初值的选择向某个值收敛,所以只能求出一个值来。如果需要别的值,是要把当前求的根带入后将方程降次,然后求第二个根。这当然是一个问题,并不是这种方法的唯一缺点:

  • 牛顿法是一种迭代算法,每一步都需要求解目标函数的Hessian矩阵的逆矩阵,计算比较复杂。

  • 牛顿法收敛速度为二阶,对于正定二次函数一步迭代即达最优解。

  • 牛顿法是局部收敛的,当初始点选择不当时,往往导致不收敛;

  • 二阶Hessian矩阵必须可逆,否则算法进行困难。


与梯度下降法的对比

梯度下降法和牛顿法都是迭代求解,不过梯度下降法是梯度求解,而牛顿法/拟牛顿法是用二阶的Hessian矩阵的逆矩阵或伪逆矩阵求解。从本质上去看,牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。如果更通俗地说的话,比如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步,牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。可以说牛顿法比梯度下降法看得更远一点,能更快地走到最底部。(牛顿法目光更加长远,所以少走弯路;相对而言,梯度下降法只考虑了局部的最优,没有全局思想)。

那为什么不用牛顿法替代梯度下降呢?

  • 牛顿法使用的是目标函数的二阶导数,在高维情况下这个矩阵非常大,计算和存储都是问题。

  • 在小批量的情况下,牛顿法对于二阶导数的估计噪声太大。

  • 目标函数非凸的时候,牛顿法容易受到鞍点或者最大值点的吸引。

实际上目前深度神经网络算法的收敛性本身就是没有很好的理论保证的,用深度神经网络只是因为它在实际应用上有较好的效果,但在深度神经网络上用梯度下降法是不是能收敛,收敛到的是不是全局最优点目前还都是无法确认的。并且二阶方法可以获得更高精度的解,但是对于神经网络这种参数精度要求不高的情况下反而成了问题,深层模型下如果参数精度太高,模型的泛化性就会降低,反而会提高模型过拟合的风险。

作者:Rian Dolphin

编辑:黄继彦

d068f5d08e56c97ea7f22a1b15e4c9c8.png

这篇关于牛顿迭代法的可视化详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/900952

相关文章

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Redis Pipeline(管道) 详解

《RedisPipeline(管道)详解》Pipeline管道是Redis提供的一种批量执行命令的机制,通过将多个命令一次性发送到服务器并统一接收响应,减少网络往返次数(RTT),显著提升执行效率... 目录Redis Pipeline 详解1. Pipeline 的核心概念2. 工作原理与性能提升3. 核

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Nginx location匹配模式与规则详解

《Nginxlocation匹配模式与规则详解》:本文主要介绍Nginxlocation匹配模式与规则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、环境二、匹配模式1. 精准模式2. 前缀模式(不继续匹配正则)3. 前缀模式(继续匹配正则)4. 正则模式(大

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J