图文详解牛顿迭代算法原理及Python实现

目录
  • 1.引例
  • 2.牛顿迭代算法求根
  • 3.牛顿迭代优化
  • 4 代码实战:Logistic回归

1.引例

给定如图所示的某个函数,如何计算函数零点x0

在数学上我们如何处理这个问题?

最简单的办法是解方程f(x)=0,在代数学上还有著名的零点判定定理

如果函数y=f(x)在区间[a,b]上的图象是连续不断的一条曲线,并且有f(a)⋅f(b)<0,那么函数y=f(x)在区间(a,b)内有零点,即至少存在一个c∈(a,b),使得f(c)=0,这个c也就是方程f(x)=0的根。

然而,数学上的方法并不一定适合工程应用,当函数形式复杂,例如出现超越函数形式;非解析形式,例如递推关系时,精确的方程解析一般难以进行,因为代数上还没发展出任意形式的求根公式。而零点判定定理求解效率也较低,需要不停试错。

因此,引入今天的主题——牛顿迭代法,服务于工程数值计算。

2.牛顿迭代算法求根

记第k轮迭代后,自变量更新为xk,令目标函数f(x)在x=xk泰勒展开:

f(x)=f(xk​)+f′(xk​)(x−xk​)+o(x)

我们希望下一次迭代到根点,忽略泰勒余项,令f(xk+1)=0,则

xk+1​=xk​−f(xk​)/f'(xk​)​

不断重复运算即可逼近根点。

在几何上,上面过程实际上是在做f(x)在x=xk处的切线,并求切线的零点,在工程上称为局部线性化。如图所示,若xk在x0的左侧,那么下一次迭代方向向右。

若xk在x0的右侧,那么下一次迭代方向向左。

3.牛顿迭代优化

将优化问题转化为求目标函数一阶导数零点的问题,即可运用上面说的牛顿迭代法。

具体地,记第k轮迭代后,自变量更新为xk ,令目标函数f(x)在x=xk泰勒展开:

f(x)=f(xk​)+f′(xk​)(x−xk​)+1/2​f′′(xk​)(x−xk​)2+o(x)

两边求导得

f′(x)=f′(xk​)+f′′(xk​)(x−xk​)

令f′(xk+1​)=f′(xk​)+f′′(xk​)(xk+1​−xk​)=0,从而得到

xk+1​=xk​−f′(xk​)/f'′(xk​)​

对于向量x=[x1​​ x2​​⋯​xd​​]T,将上述迭代公式推广为

xk+1​=xk​−[∇2f(xk​)]−1∇f(xk​)

其中∇2f(xk​)是Hessian矩阵,当其正定时可以保证牛顿优化算法往 减小的方向迭代

牛顿法的特点如下:

① 以二阶速率向最优点收敛,迭代次数远小于梯度下降法,优化速度快;

梯度下降法的解析参考图文详解梯度下降算法的原理及Python实现

②学习率为[∇2f(xk​)]−1 ,包含更多函数本身的信息,迭代步长可实现自动调整,可视为自适应梯度下降算法;

③ 耗费CPU计算资源多,每次迭代需要计算一次Hessian矩阵,且无法保证Hessian矩阵可逆且正定,因而无法保证一定向最优点收敛。

在实际应用中,牛顿迭代法一般不能直接使用,会引入改进来规避其缺陷,称为拟牛顿算法簇,其中包含大量不同的算法变种,例如共轭梯度法、DFP算法等等,今后都会介绍到。

4 代码实战:Logistic回归

import pandas as pd
import numpy as np
import os
import matplotlib.pyplot as plt
import matplotlib as mpl
from Logit import Logit

'''
* @breif: 从CSV中加载指定数据
* @param[in]: file -> 文件名
* @param[in]: colName -> 要加载的列名
* @param[in]: mode -> 加载模式, set: 列名与该列数据组成的字典, df: df类型
* @retval: mode模式下的返回值
'''
def loadCsvData(file, colName, mode='df'):
    assert mode in ('set', 'df')
    df = pd.read_csv(file, encoding='utf-8-sig', usecols=colName)
    if mode == 'df':
        return df
    if mode == 'set':
        res = {}
        for col in colName:
            res[col] = df[col].values
        return res

if __name__ == '__main__':
    # ============================
    # 读取CSV数据
    # ============================
    csvPath = os.path.abspath(os.path.join(__file__, "../../data/dataset3.0alpha.csv"))
    dataX = loadCsvData(csvPath, ["含糖率", "密度"], 'df')
    dataY = loadCsvData(csvPath, ["好瓜"], 'df')
    label = np.array([
        1 if i == "是" else 0
        for i in list(map(lambda s: s.strip(), list(dataY['好瓜'])))
    ])

    # ============================
    # 绘制样本点
    # ============================
    line_x = np.array([np.min(dataX['密度']), np.max(dataX['密度'])])
    mpl.rcParams['font.sans-serif'] = [u'SimHei']
    plt.title('对数几率回归模拟\nLogistic Regression Simulation')
    plt.xlabel('density')
    plt.ylabel('sugarRate')
    plt.scatter(dataX['密度'][label==0],
                dataX['含糖率'][label==0],
                marker='^',
                color='k',
                s=100,
                label='坏瓜')
    plt.scatter(dataX['密度'][label==1],
                dataX['含糖率'][label==1],
                marker='^',
                color='r',
                s=100,
                label='好瓜')

    # ============================
    # 实例化对数几率回归模型
    # ============================
    logit = Logit(dataX, label)

    # 采用牛顿迭代法
    logit.logitRegression(logit.newtomMethod)
    line_y = -logit.w[0, 0] / logit.w[1, 0] * line_x - logit.w[2, 0] / logit.w[1, 0]
    plt.plot(line_x, line_y, 'g-', label="牛顿迭代法")

    # 绘图
    plt.legend(loc='upper left')
    plt.show()

其中更新权重代码为

    '''
    * @breif: 牛顿迭代法更新权重
    * @param[in]: None
    * @retval: 优化参数的增量dw
    '''
    def newtomMethod(self):
        wTx = np.dot(self.w.T, self.X).reshape(-1, 1)
        p = Logit.sigmod(wTx)
        dw_1 = -self.X.dot(self.y - p)
        dw_2 = self.X.dot(np.diag((p * (1 - p)).reshape(self.N))).dot(self.X.T)
        dw = np.linalg.inv(dw_2).dot(dw_1)
        return dw

到此这篇关于图文详解牛顿迭代算法原理及Python实现的文章就介绍到这了,更多相关Python牛顿迭代算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2022-08-10

Gauss-Seidel迭代算法的Python实现详解

import numpy as np import time 1.1 Gauss-Seidel迭代算法 def GaussSeidel_tensor_V2(A,b,Delta,m,n,M): start=time.perf_counter() find=0 X=np.ones(n) d=np.ones(n) m1=m-1 m2=2-m for i in range(M): print('X',X) x=np.copy(X) #迭代更新 for j in range(n): a=np.copy(A

Python编程实现二分法和牛顿迭代法求平方根代码

求一个数的平方根函数sqrt(int num) ,在大多数语言中都提供实现.那么要求一个数的平方根,是怎么实现的呢? 实际上求平方根的算法方法主要有两种:二分法(binary search)和牛顿迭代法(Newton iteration) 1:二分法 求根号5 a:折半: 5/2=2.5 b:平方校验: 2.5*2.5=6.25>5,并且得到当前上限2.5 c:再次向下折半:2.5/2=1.25 d:平方校验:1.25*1.25=1.5625<5,得到当前下限1.25 e:再次折半:2.5-(

图文详解梯度下降算法的原理及Python实现

目录 1.引例 2.数值解法 3.梯度下降算法 4.代码实战:Logistic回归 1.引例 给定如图所示的某个函数,如何通过计算机算法编程求f(x)min? 2.数值解法 传统方法是数值解法,如图所示 按照以下步骤迭代循环直至最优: ① 任意给定一个初值x0: ② 随机生成增量方向,结合步长生成Δx: ③ 计算比较f(x0)与f(x0+Δx)的大小,若f(x0+Δx)<f(x0)则更新位置,否则重新生成Δx: ④ 重复②③直至收敛到最优f(x)min. 数值解法最大的优点是编程简明,但缺陷也很

python计算牛顿迭代多项式实例分析

本文实例讲述了python计算牛顿迭代多项式的方法.分享给大家供大家参考.具体实现方法如下: ''' p = evalPoly(a,xData,x). Evaluates Newton's polynomial p at x. The coefficient vector 'a' can be computed by the function 'coeffts'. a = coeffts(xData,yData). Computes the coefficients of Newton's po

Jacobi迭代算法的Python实现详解

import numpy as np import time 1.1 Jacobi迭代算法 def Jacobi_tensor_V2(A,b,Delta,m,n,M): start=time.perf_counter()#开始计时 find=0#用于标记是否在规定步数内收敛 X=np.ones(n)#迭代起始点 x=np.ones(n)#用于存储迭代的中间结果 d=np.ones(n)#用于存储Ax**(m-2)的对角线部分 m1=m-1 m2=2-m for i in range(M): pr

图文详解感知机算法原理及Python实现

目录 写在前面 1.什么是线性模型 2.感知机概述 3.手推感知机原理 4.Python实现 4.1 创建感知机类 4.2 更新权重与偏置 4.3 判断误分类点 4.4 训练感知机 4.5 动图可视化 5.总结 写在前面 机器学习强基计划聚焦深度和广度,加深对机器学习模型的理解与应用.“深”在详细推导算法模型背后的数学原理:“广”在分析多个机器学习模型:决策树.支持向量机.贝叶斯与马尔科夫决策.强化学习等. 本期目标:实现这样一个效果 1.什么是线性模型 线性模型的假设形式是属性权重.偏置与属性

详解堆排序算法原理及Java版的代码实现

概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

机器学习之KNN算法原理及Python实现方法详解

本文实例讲述了机器学习之KNN算法原理及Python实现方法.分享给大家供大家参考,具体如下: 文中代码出自<机器学习实战>CH02,可参考本站: 机器学习实战 (Peter Harrington著) 中文版 机器学习实战 (Peter Harrington著) 英文原版 [附源代码] KNN算法介绍 KNN是一种监督学习算法,通过计算新数据与训练数据特征值之间的距离,然后选取K(K>=1)个距离最近的邻居进行分类判(投票法)或者回归.若K=1,新数据被简单分配给其近邻的类. KNN算法

详解K-means算法在Python中的实现

K-means算法简介 K-means是机器学习中一个比较常用的算法,属于无监督学习算法,其常被用于数据的聚类,只需为它指定簇的数量即可自动将数据聚合到多类中,相同簇中的数据相似度较高,不同簇中数据相似度较低. K-MEANS算法是输入聚类个数k,以及包含 n个数据对象的数据库,输出满足方差最小标准k个聚类的一种算法.k-means 算法接受输入量 k :然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高:而不同聚类中的对象相似度较小. 核心思想 通过迭代寻找

SSH原理及两种登录方法图文详解

SSH(Secure Shell)是一套协议标准,可以用来实现两台机器之间的安全登录以及安全的数据传送,其保证数据安全的原理是非对称加密. 传统的对称加密使用的是一套秘钥,数据的加密以及解密用的都是这一套秘钥,可想而知所有的客户端以及服务端都需要保存这套秘钥,泄露的风险很高,而一旦秘钥便泄露便保证不了数据安全. 非对称加密解决的就是这个问题,它包含两套秘钥 - 公钥以及私钥,其中公钥用来加密,私钥用来解密,并且通过公钥计算不出私钥,因此私钥谨慎保存在服务端,而公钥可以随便传递,即使泄露也无风险.

Python Django的安装配置教程图文详解

Django 教程 Python下有许多款不同的 Web 框架.Django是重量级选手中最有代表性的一位.许多成功的网站和APP都基于Django. Django是一个开放源代码的Web应用框架,由Python写成. Django遵守BSD版权,初次发布于2005年7月, 并于2008年9月发布了第一个正式版本1.0 . Django采用了MVC的软件设计模式,即模型M,视图V和控制器C. 学习Django前,我们要确定电脑上是否已经安装了Python,目前Python有两个版本,不过这两个版

python安装virtualenv虚拟环境步骤图文详解

一.安装virtualenv 点击左下角最边上菜单栏输入cmd,打开命令行 2.根据版本的不同输入命令pip install virtualenv(或者pip3 install virtualenv ) 3.进入你想创建的虚拟环境空间的路径,然后创建一个文件,(注释:我在我的E盘的python文件下建立了一个文件叫dcjvirtual) 4.进入dcjvirtual文件,用dir命令(虚拟机是ls)列出所有文件 5.进入dcjvirtual文件下的Scripts文件,用dir命令打开如下图所示:

python实现连续变量最优分箱详解--CART算法

关于变量分箱主要分为两大类:有监督型和无监督型 对应的分箱方法: A. 无监督:(1) 等宽 (2) 等频 (3) 聚类 B. 有监督:(1) 卡方分箱法(ChiMerge) (2) ID3.C4.5.CART等单变量决策树算法 (3) 信用评分建模的IV最大化分箱 等 本篇使用python,基于CART算法对连续变量进行最优分箱 由于CART是决策树分类算法,所以相当于是单变量决策树分类. 简单介绍下理论: CART是二叉树,每次仅进行二元分类,对于连续性变量,方法是依次计算相邻两元素值的中位

Python和Anaconda和Pycharm安装教程图文详解

Anaconda 是一个基于 Python 的数据处理和科学计算平台,它已经内置了许多非常有用的第三方库,装上Anaconda,就相当于把 Python 和一些如 Numpy.Pandas.Scrip.Matplotlib 等常用的库自动安装好了,使得安装比常规 Python 安装要容易.如果选择安装Python的话,那么还需要 pip install 一个一个安装各种库,安装起来比较痛苦,还需要考虑兼容性,非如此的话,就要去Python官网(https://www.python.org/dow

Python解释器以及PyCharm的安装教程图文详解

本文给大家分享Python解释器安装以及PyCharm安装过程.很多朋友问小编要完整的安装教程,现分享给大家. 一.Python解释器安装 解释器(英语:Interpreter),又译为直译器,是一种电脑程序能够把高级编程语言一行一行直接转译运行.解释器不会一次把整个程序转译出来,只像一位"中间人",每次运行程序时都要先转成另一种语言再作运行,因此解释器的程序运行速度比较缓慢.它每转译一行程序叙述就立刻运行,然后再转译下一行,再运行,如此不停地进行下去. Python的下载网站:Pyt

Python 开发工具PyCharm安装教程图文详解(新手必看)

PyCharm是由JetBrains打造的一款Python IDE,VS2010的重构插件Resharper就是出自JetBrains之手. 同时支持Google App Engine,PyCharm支持IronPython.这些功能在先进代码分析程序的支持下,使 PyCharm 成为 Python 专业开发人员和刚起步人员使用的有力工具. PyCharm是一种Python IDE,带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具,比如调试.语法高亮.Project管理.代码跳