圖文詳解牛頓迭代算法原理及Python實(shí)現(xiàn)
1.引例
給定如圖所示的某個(gè)函數(shù)，如何計(jì)算函數(shù)零點(diǎn)x0
在數(shù)學(xué)上我們?nèi)绾翁幚磉@個(gè)問題？
最簡(jiǎn)單的辦法是解方程f(x)=0，在代數(shù)學(xué)上還有著名的零點(diǎn)判定定理
如果函數(shù)y=f(x)在區(qū)間[a,b]上的圖象是連續(xù)不斷的一條曲線，并且有f(a)⋅f(b)<0,那么函數(shù)y=f(x)在區(qū)間(a,b)內(nèi)有零點(diǎn)，即至少存在一個(gè)c∈(a,b),使得f(c)=0,這個(gè)c也就是方程f(x)=0的根。
然而，數(shù)學(xué)上的方法并不一定適合工程應(yīng)用，當(dāng)函數(shù)形式復(fù)雜，例如出現(xiàn)超越函數(shù)形式；非解析形式，例如遞推關(guān)系時(shí)，精確的方程解析一般難以進(jìn)行，因?yàn)榇鷶?shù)上還沒發(fā)展出任意形式的求根公式。而零點(diǎn)判定定理求解效率也較低，需要不停試錯(cuò)。
因此，引入今天的主題——牛頓迭代法，服務(wù)于工程數(shù)值計(jì)算。
2.牛頓迭代算法求根
記第k輪迭代后，自變量更新為xk，令目標(biāo)函數(shù)f(x)在x=xk泰勒展開：
f(x)=f(xk?)+f′(xk?)(x−xk?)+o(x)
我們希望下一次迭代到根點(diǎn)，忽略泰勒余項(xiàng)，令f(xk+1)=0，則
xk+1?=xk?−f(xk?)/f'(xk?)?
不斷重復(fù)運(yùn)算即可逼近根點(diǎn)。
在幾何上，上面過程實(shí)際上是在做f(x)在x=xk處的切線，并求切線的零點(diǎn)，在工程上稱為局部線性化。如圖所示，若xk在x0的左側(cè)，那么下一次迭代方向向右。
若xk在x0的右側(cè)，那么下一次迭代方向向左。
3.牛頓迭代優(yōu)化
將優(yōu)化問題轉(zhuǎn)化為求目標(biāo)函數(shù)一階導(dǎo)數(shù)零點(diǎn)的問題，即可運(yùn)用上面說的牛頓迭代法。
具體地，記第k輪迭代后，自變量更新為xk ，令目標(biāo)函數(shù)f(x)在x=xk泰勒展開：
f(x)=f(xk?)+f′(xk?)(x−xk?)+1/2?f′′(xk?)(x−xk?)2+o(x)
兩邊求導(dǎo)得
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?)?
對(duì)于向量x=[x1?? x2????xd??]T，將上述迭代公式推廣為
xk+1?=xk?−[∇2f(xk?)]−1∇f(xk?)
其中∇2f(xk?)是Hessian矩陣，當(dāng)其正定時(shí)可以保證牛頓優(yōu)化算法往 減小的方向迭代
牛頓法的特點(diǎn)如下：
① 以二階速率向最優(yōu)點(diǎn)收斂，迭代次數(shù)遠(yuǎn)小于梯度下降法，優(yōu)化速度快；
梯度下降法的解析參考圖文詳解梯度下降算法的原理及Python實(shí)現(xiàn)
②學(xué)習(xí)率為[∇2f(xk?)]−1 ，包含更多函數(shù)本身的信息，迭代步長(zhǎng)可實(shí)現(xiàn)自動(dòng)調(diào)整，可視為自適應(yīng)梯度下降算法；
③ 耗費(fèi)CPU計(jì)算資源多，每次迭代需要計(jì)算一次Hessian矩陣，且無法保證Hessian矩陣可逆且正定，因而無法保證一定向最優(yōu)點(diǎn)收斂。
在實(shí)際應(yīng)用中，牛頓迭代法一般不能直接使用，會(huì)引入改進(jìn)來規(guī)避其缺陷，稱為擬牛頓算法簇，其中包含大量不同的算法變種，例如共軛梯度法、DFP算法等等，今后都會(huì)介紹到。
4 代碼實(shí)戰(zhàn)：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中加載指定數(shù)據(jù)
* @param[in]: file -> 文件名
* @param[in]: colName -> 要加載的列名
* @param[in]: mode -> 加載模式, set: 列名與該列數(shù)據(jù)組成的字典, 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數(shù)據(jù)
# ============================
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['好瓜'])))
])
# ============================
# 繪制樣本點(diǎn)
# ============================
line_x = np.array([np.min(dataX['密度']), np.max(dataX['密度'])])
mpl.rcParams['font.sans-serif'] = [u'SimHei']
plt.title('對(duì)數(shù)幾率回歸模擬\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='好瓜')
# ============================
# 實(shí)例化對(duì)數(shù)幾率回歸模型
# ============================
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()
其中更新權(quán)重代碼為
'''
* @breif: 牛頓迭代法更新權(quán)重
* @param[in]: None
* @retval: 優(yōu)化參數(shù)的增量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
到此這篇關(guān)于圖文詳解牛頓迭代算法原理及Python實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Python牛頓迭代算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
python在回調(diào)函數(shù)中獲取返回值的方法
今天小編就為大家分享一篇python在回調(diào)函數(shù)中獲取返回值的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-02-02
python 動(dòng)態(tài)生成變量名以及動(dòng)態(tài)獲取變量的變量名方法
今天小編就為大家分享一篇python 動(dòng)態(tài)生成變量名以及動(dòng)態(tài)獲取變量的變量名方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-01-01
python實(shí)現(xiàn)windows壁紙定期更換功能
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)windows壁紙定期更換功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-01-01
詳解使用 pyenv 管理多個(gè)版本 python 環(huán)境
本篇文章主要介紹了詳解使用 pyenv 管理多個(gè)版本 python 環(huán)境，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-10-10
基于TensorFlow常量、序列以及隨機(jī)值生成實(shí)例
今天小編就為大家分享一篇基于TensorFlow常量、序列以及隨機(jī)值生成實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-01-01
這篇文章主要為大家詳細(xì)介紹了用python實(shí)現(xiàn)打磚塊小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
python包裝和授權(quán)學(xué)習(xí)教程
包裝是指對(duì)一個(gè)已經(jīng)存在的對(duì)象進(jìn)行系定義加工,實(shí)現(xiàn)授權(quán)是包裝的一個(gè)特性,下面這篇文章主要給大家介紹了關(guān)于python包裝和授權(quán)的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2023-06-06
python批量合成bilibili的m4s緩存文件為MP4格式 ver2.5
這篇文章主要介紹了python批量合成bilibili的m4s緩存文件為MP4格式 ver2.5的相關(guān)知識(shí)，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12
Python collections中的雙向隊(duì)列deque簡(jiǎn)單介紹詳解
這篇文章主要介紹了Python collections中的雙向隊(duì)列deque簡(jiǎn)單介紹詳解，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-11-11
這篇文章主要介紹了詳解python中的index函數(shù)用法，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-08-08