🥇SciPy การเพิ่มประสิทธิภาพ

SciPy (ออกเสียงว่า sai pie) เป็นแพ็คเกจแอปพลิเคชันทางคณิตศาสตร์ที่ใช้ส่วนขยาย Numpy Python ด้วย SciPy เซสชัน Python แบบโต้ตอบของคุณจะกลายเป็นวิทยาศาสตร์ข้อมูลที่สมบูรณ์และสภาพแวดล้อมการสร้างต้นแบบระบบที่ซับซ้อนเช่นเดียวกับ MATLAB, IDL, Octave, R-Lab และ SciLab วันนี้ฉันต้องการพูดสั้น ๆ เกี่ยวกับวิธีใช้อัลกอริธึมการปรับให้เหมาะสมที่รู้จักกันดีในแพ็คเกจ scipy.optimize สามารถรับความช่วยเหลือโดยละเอียดและอัปเดตเพิ่มเติมเกี่ยวกับการใช้ฟังก์ชันต่างๆ ได้เสมอโดยใช้คำสั่ง help() หรือใช้ Shift+Tab

การแนะนำ

เพื่อช่วยตัวคุณเองและผู้อ่านจากการค้นหาและอ่านแหล่งข้อมูลหลัก ลิงก์ไปยังคำอธิบายวิธีการต่างๆ ส่วนใหญ่จะอยู่ในวิกิพีเดีย ตามกฎแล้วข้อมูลนี้เพียงพอที่จะเข้าใจวิธีการในข้อกำหนดทั่วไปและเงื่อนไขในการสมัคร เพื่อทำความเข้าใจสาระสำคัญของวิธีการทางคณิตศาสตร์ ให้ทำตามลิงก์ไปยังสิ่งพิมพ์ที่เชื่อถือได้ซึ่งสามารถพบได้ในตอนท้ายของแต่ละบทความหรือในเครื่องมือค้นหาที่คุณชื่นชอบ

ดังนั้น โมดูล scipy.optimize จึงรวมการดำเนินการตามขั้นตอนต่อไปนี้:

การลดขนาดฟังก์ชันสเกลาร์แบบมีเงื่อนไขและไม่มีเงื่อนไขของตัวแปรหลายตัว (ขั้นต่ำ) โดยใช้อัลกอริธึมต่างๆ (Nelder-Mead simplex, BFGS, การไล่ระดับสีคอนจูเกตของนิวตัน, โคบีล่า и SLSQP)
การเพิ่มประสิทธิภาพระดับโลก (ตัวอย่าง: กระโดดน้ำ, diff_evolution)
การลดปริมาณสารตกค้าง บรรษัทข้ามชาติ (least_squares) และอัลกอริธึมการปรับเส้นโค้งโดยใช้กำลังสองน้อยที่สุดแบบไม่เชิงเส้น (curve_fit)
การลดฟังก์ชันสเกลาร์ของตัวแปรหนึ่งตัว (minim_scalar) และการค้นหาราก (root_scalar)
ตัวแก้ระบบสมการหลายมิติ (รูท) โดยใช้อัลกอริธึมต่างๆ (ไฮบริดพาวเวลล์ เลเวนเบิร์ก-มาร์ควาร์ด หรือวิธีการขนาดใหญ่เช่น นิวตัน-ไครลอฟ).

ในบทความนี้เราจะพิจารณาเฉพาะรายการแรกจากรายการทั้งหมดนี้

การลดฟังก์ชันสเกลาร์ของตัวแปรหลายตัวให้เหลือน้อยที่สุดโดยไม่มีเงื่อนไข

ฟังก์ชันย่อขนาดจากแพ็คเกจ scipy.optimize จัดเตรียมอินเทอร์เฟซทั่วไปสำหรับการแก้ปัญหาการลดขนาดแบบมีเงื่อนไขและแบบไม่มีเงื่อนไขของฟังก์ชันสเกลาร์ของตัวแปรหลายตัว เพื่อสาธิตวิธีการทำงาน เราจำเป็นต้องมีฟังก์ชันที่เหมาะสมของตัวแปรหลายตัว ซึ่งเราจะย่อให้เล็กสุดในรูปแบบต่างๆ

เพื่อวัตถุประสงค์เหล่านี้ ฟังก์ชัน Rosenbrock ของตัวแปร N จึงสมบูรณ์แบบซึ่งมีรูปแบบดังนี้

แม้ว่าฟังก์ชัน Rosenbrock และเมทริกซ์ Jacobi และ Hessian (อนุพันธ์ตัวแรกและตัวที่สองตามลำดับ) จะถูกกำหนดไว้แล้วในแพ็คเกจ scipy.optimize แต่เราจะกำหนดมันเอง

import numpy as np

def rosen(x):
    """The Rosenbrock function"""
    return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)

เพื่อความชัดเจน เรามาวาดค่าของฟังก์ชัน Rosenbrock ของตัวแปรสองตัวในแบบสามมิติกัน

รหัสการวาด

from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter

# Настраиваем 3D график
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')

# Задаем угол обзора
ax.view_init(45, 30)

# Создаем данные для графика
X = np.arange(-2, 2, 0.1)
Y = np.arange(-1, 3, 0.1)
X, Y = np.meshgrid(X, Y)
Z = rosen(np.array([X,Y]))

# Рисуем поверхность
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()

รู้ล่วงหน้าว่าขั้นต่ำคือ 0 ที่ มาดูตัวอย่างวิธีการกำหนดค่าต่ำสุดของฟังก์ชัน Rosenbrock โดยใช้ขั้นตอนต่างๆ ของ scipy.optimize

วิธีเนลเดอร์มี้ดซิมเพล็กซ์

ให้มีจุดเริ่มต้น x0 ในปริภูมิ 5 มิติ มาหาจุดต่ำสุดของฟังก์ชัน Rosenbrock ที่ใกล้เคียงที่สุดโดยใช้อัลกอริทึม เนลเดอร์มี้ดซิมเพล็กซ์ (อัลกอริทึมถูกระบุเป็นค่าของพารามิเตอร์วิธีการ):

from scipy.optimize import minimize
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='nelder-mead',
    options={'xtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 339
         Function evaluations: 571
[1. 1. 1. 1. 1.]

วิธีซิมเพล็กซ์เป็นวิธีที่ง่ายที่สุดในการลดฟังก์ชันที่กำหนดไว้อย่างชัดเจนและราบรื่น ไม่จำเป็นต้องคำนวณอนุพันธ์ของฟังก์ชัน เพียงระบุเฉพาะค่าเท่านั้นก็เพียงพอแล้ว วิธี Nelder-Mead เป็นทางเลือกที่ดีสำหรับปัญหาการลดขนาดแบบง่ายๆ อย่างไรก็ตาม เนื่องจากไม่ได้ใช้การประมาณค่าความชัน จึงอาจใช้เวลานานกว่าในการค้นหาค่าต่ำสุด

วิธีพาวเวลล์

อัลกอริธึมการปรับให้เหมาะสมอื่นที่คำนวณเฉพาะค่าฟังก์ชันเท่านั้นคือ วิธีการของพาวเวลล์. หากต้องการใช้งาน คุณต้องตั้งค่า method = 'powell' ในฟังก์ชัน minim

x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='powell',
    options={'xtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 19
         Function evaluations: 1622
[1. 1. 1. 1. 1.]

อัลกอริทึม Broyden-Fletcher-Goldfarb-Shanno (BFGS)

เพื่อให้การลู่เข้าของโซลูชันเร็วขึ้น จะต้องดำเนินการตามขั้นตอน บีเอฟจีเอส ใช้การไล่ระดับสีของฟังก์ชันวัตถุประสงค์ การไล่ระดับสีสามารถระบุเป็นฟังก์ชันหรือคำนวณโดยใช้ผลต่างลำดับแรกได้ ไม่ว่าในกรณีใด โดยทั่วไปวิธี BFGS ต้องการการเรียกใช้ฟังก์ชันน้อยกว่าวิธี simplex

ให้เราค้นหาอนุพันธ์ของฟังก์ชัน Rosenbrock ในรูปแบบการวิเคราะห์:

นิพจน์นี้ใช้ได้กับอนุพันธ์ของตัวแปรทั้งหมด ยกเว้นตัวแรกและตัวสุดท้าย ซึ่งถูกกำหนดเป็น:

มาดูฟังก์ชัน Python ที่คำนวณการไล่ระดับสีนี้:

def rosen_der (x):
    xm = x [1: -1]
    xm_m1 = x [: - 2]
    xm_p1 = x [2:]
    der = np.zeros_like (x)
    der [1: -1] = 200 * (xm-xm_m1 ** 2) - 400 * (xm_p1 - xm ** 2) * xm - 2 * (1-xm)
    der [0] = -400 * x [0] * (x [1] -x [0] ** 2) - 2 * (1-x [0])
    der [-1] = 200 * (x [-1] -x [-2] ** 2)
    return der

ฟังก์ชันการคำนวณการไล่ระดับสีถูกระบุเป็นค่าของพารามิเตอร์ jac ของฟังก์ชันขั้นต่ำ ดังที่แสดงด้านล่าง

res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 25
         Function evaluations: 30
         Gradient evaluations: 30
[1.00000004 1.0000001  1.00000021 1.00000044 1.00000092]

อัลกอริธึมการไล่ระดับสีคอนจูเกต (นิวตัน)

ขั้นตอนวิธี การไล่ระดับสีคอนจูเกตของนิวตัน เป็นวิธีของนิวตันที่ถูกดัดแปลง
วิธีการของนิวตันขึ้นอยู่กับการประมาณฟังก์ชันในพื้นที่ท้องถิ่นด้วยพหุนามของดีกรีที่สอง:

ที่ไหน คือเมทริกซ์ของอนุพันธ์อันดับสอง (Hessian matrix, Hessian)
ถ้า Hessian เป็นค่าแน่นอนที่เป็นบวก ค่าต่ำสุดเฉพาะจุดของฟังก์ชันนี้สามารถหาได้โดยการปรับความชันของค่าความชันเป็นศูนย์ของรูปแบบกำลังสองให้เป็นศูนย์ ผลลัพธ์จะเป็นนิพจน์:

Hessian แบบผกผันคำนวณโดยใช้วิธีการไล่ระดับคอนจูเกต ตัวอย่างของการใช้วิธีนี้เพื่อลดฟังก์ชัน Rosenbrock ให้เหลืออยู่ด้านล่าง หากต้องการใช้วิธี Newton-CG คุณต้องระบุฟังก์ชันที่คำนวณ Hessian
ฟังก์ชัน Hessian ของ Rosenbrock ในรูปแบบการวิเคราะห์เท่ากับ:

ที่ไหน и ให้กำหนดเมทริกซ์ .

องค์ประกอบที่ไม่ใช่ศูนย์ที่เหลือของเมทริกซ์จะเท่ากับ:

ตัวอย่างเช่น ในปริภูมิห้ามิติ N = 5 เมทริกซ์ Hessian สำหรับฟังก์ชัน Rosenbrock มีรูปแบบของแถบ:

โค้ดที่คำนวณ Hessian นี้พร้อมกับโค้ดสำหรับย่อฟังก์ชัน Rosenbrock ให้เล็กสุดโดยใช้วิธีการไล่ระดับสีแบบคอนจูเกต (นิวตัน):

def rosen_hess(x):
    x = np.asarray(x)
    H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1)
    diagonal = np.zeros_like(x)
    diagonal[0] = 1200*x[0]**2-400*x[1]+2
    diagonal[-1] = 200
    diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:]
    H = H + np.diag(diagonal)
    return H

res = minimize(rosen, x0, method='Newton-CG', 
               jac=rosen_der, hess=rosen_hess,
               options={'xtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 24
         Function evaluations: 33
         Gradient evaluations: 56
         Hessian evaluations: 24
[1.         1.         1.         0.99999999 0.99999999]

ตัวอย่างที่มีคำจำกัดความของฟังก์ชันผลคูณของ Hessian และเวกเตอร์ที่กำหนดเอง

ในปัญหาในโลกแห่งความเป็นจริง การคำนวณและการจัดเก็บเมทริกซ์ Hessian ทั้งหมดอาจต้องใช้เวลาและทรัพยากรหน่วยความจำจำนวนมาก ในกรณีนี้ จริงๆ แล้วไม่จำเป็นต้องระบุเมทริกซ์ Hessian เอง เพราะว่า ขั้นตอนการย่อขนาดต้องใช้เพียงเวกเตอร์เท่ากับผลคูณของ Hessian กับเวกเตอร์อื่นตามอำเภอใจ ดังนั้น จากมุมมองของการคำนวณ เป็นการดีกว่ามากที่จะกำหนดฟังก์ชันที่ส่งคืนผลลัพธ์ของผลคูณของ Hessian ด้วยเวกเตอร์ที่กำหนดเองในทันที

พิจารณาฟังก์ชัน hess ซึ่งใช้เวกเตอร์การย่อขนาดเป็นอาร์กิวเมนต์แรก และเวกเตอร์ที่กำหนดเองเป็นอาร์กิวเมนต์ที่สอง (พร้อมกับอาร์กิวเมนต์อื่นๆ ของฟังก์ชันที่ต้องการย่อให้เล็กสุด) ในกรณีของเรา การคำนวณผลคูณของฟังก์ชัน Hessian ของฟังก์ชัน Rosenbrock ด้วยเวกเตอร์ใดๆ นั้นไม่ใช่เรื่องยาก ถ้า p เป็นเวกเตอร์ใดๆ ก็ได้ แล้วจึงเป็นผลคูณ ดูเหมือนกับ:

ฟังก์ชันที่คำนวณผลคูณของ Hessian และเวกเตอร์ที่กำหนดเองจะถูกส่งผ่านเป็นค่าของอาร์กิวเมนต์ hessp ไปยังฟังก์ชันย่อเล็กสุด:

def rosen_hess_p(x, p):
    x = np.asarray(x)
    Hp = np.zeros_like(x)
    Hp[0] = (1200*x[0]**2 - 400*x[1] + 2)*p[0] - 400*x[0]*p[1]
    Hp[1:-1] = -400*x[:-2]*p[:-2]+(202+1200*x[1:-1]**2-400*x[2:])*p[1:-1] 
    -400*x[1:-1]*p[2:]
    Hp[-1] = -400*x[-2]*p[-2] + 200*p[-1]
    return Hp

res = minimize(rosen, x0, method='Newton-CG',
               jac=rosen_der, hessp=rosen_hess_p,
               options={'xtol': 1e-8, 'disp': True})

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 24
         Function evaluations: 33
         Gradient evaluations: 56
         Hessian evaluations: 66

อัลกอริธึมขอบเขตการไล่ระดับสีแบบคอนจูเกต (นิวตัน)

การปรับสภาพเมทริกซ์ Hessian ที่ไม่ดีและทิศทางการค้นหาที่ไม่ถูกต้องอาจทำให้อัลกอริทึมการไล่ระดับสีคอนจูเกตของนิวตันไม่มีประสิทธิภาพ ในกรณีเช่นนี้ จะมีการมอบสิทธิพิเศษให้กับ วิธีภูมิภาคที่เชื่อถือได้ (เขตความเชื่อถือ) ผสานการไล่ระดับสีของนิวตัน

ตัวอย่างที่มีคำจำกัดความของเมทริกซ์ Hessian:

res = minimize(rosen, x0, method='trust-ncg',
               jac=rosen_der, hess=rosen_hess,
               options={'gtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 20
         Function evaluations: 21
         Gradient evaluations: 20
         Hessian evaluations: 19
[1. 1. 1. 1. 1.]

ตัวอย่างฟังก์ชันผลคูณของ Hessian และเวกเตอร์ที่กำหนดเอง:

res = minimize(rosen, x0, method='trust-ncg', 
                jac=rosen_der, hessp=rosen_hess_p, 
                options={'gtol': 1e-8, 'disp': True})
print(res.x)

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 20
         Function evaluations: 21
         Gradient evaluations: 20
         Hessian evaluations: 0
[1. 1. 1. 1. 1.]

วิธีการประเภท Krylov

เช่นเดียวกับวิธี trust-ncg วิธีแบบ Krylov เหมาะอย่างยิ่งสำหรับการแก้ปัญหาขนาดใหญ่ เนื่องจากใช้เฉพาะผลคูณเมทริกซ์-เวกเตอร์ สาระสำคัญของพวกเขาคือการแก้ปัญหาในภูมิภาคความเชื่อมั่นที่ถูกจำกัดโดยสเปซย่อย Krylov ที่ถูกตัดทอน สำหรับปัญหาที่ไม่แน่นอน ควรใช้วิธีนี้ดีกว่า เนื่องจากจะใช้จำนวนการวนซ้ำแบบไม่เชิงเส้นน้อยลง เนื่องจากจำนวนผลคูณของเมทริกซ์-เวกเตอร์ต่อปัญหาย่อยน้อยกว่า เมื่อเปรียบเทียบกับวิธี trust-ncg นอกจากนี้ วิธีแก้ไขปัญหาย่อยกำลังสองยังพบได้แม่นยำกว่าการใช้วิธี trust-ncg
ตัวอย่างที่มีคำจำกัดความของเมทริกซ์ Hessian:

res = minimize(rosen, x0, method='trust-krylov',
               jac=rosen_der, hess=rosen_hess,
               options={'gtol': 1e-8, 'disp': True})

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 19
         Function evaluations: 20
         Gradient evaluations: 20
         Hessian evaluations: 18

print(res.x)

    [1. 1. 1. 1. 1.]

ตัวอย่างฟังก์ชันผลคูณของ Hessian และเวกเตอร์ที่กำหนดเอง:

res = minimize(rosen, x0, method='trust-krylov',
               jac=rosen_der, hessp=rosen_hess_p,
               options={'gtol': 1e-8, 'disp': True})

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 19
         Function evaluations: 20
         Gradient evaluations: 20
         Hessian evaluations: 0

print(res.x)

    [1. 1. 1. 1. 1.]

อัลกอริทึมสำหรับการแก้ปัญหาโดยประมาณในภูมิภาคความเชื่อมั่น

วิธีการทั้งหมด (Newton-CG, trust-ncg และ trust-krylov) เหมาะอย่างยิ่งสำหรับการแก้ปัญหาขนาดใหญ่ (ที่มีตัวแปรนับพันตัว) นี่เป็นเพราะความจริงที่ว่าอัลกอริธึมการไล่ระดับสีคอนจูเกตพื้นฐานแสดงถึงการกำหนดโดยประมาณของเมทริกซ์เฮสเซียนผกผัน วิธีแก้ปัญหาจะพบซ้ำๆ โดยไม่มีการขยาย Hessian อย่างชัดเจน เนื่องจากคุณเพียงแค่ต้องกำหนดฟังก์ชันสำหรับผลคูณของ Hessian และเวกเตอร์ใดๆ ก็ตาม อัลกอริธึมนี้จึงดีเป็นพิเศษสำหรับการทำงานกับเมทริกซ์แบบกระจัดกระจาย (แถบแนวทแยง) ทำให้ต้นทุนหน่วยความจำต่ำและประหยัดเวลาได้มาก

สำหรับปัญหาขนาดกลาง ค่าใช้จ่ายในการจัดเก็บและการแยกตัวประกอบของ Hessian นั้นไม่สำคัญ ซึ่งหมายความว่า มีความเป็นไปได้ที่จะได้รับวิธีแก้ปัญหาด้วยการวนซ้ำน้อยลง โดยสามารถแก้ไขปัญหาย่อยของขอบเขตความน่าเชื่อถือได้แทบจะทุกประการ เมื่อต้องการทำเช่นนี้ สมการไม่เชิงเส้นบางสมการจะถูกแก้ไขซ้ำๆ สำหรับแต่ละปัญหาย่อยกำลังสอง วิธีแก้ปัญหาดังกล่าวมักจะต้องใช้การสลายตัวของ Cholesky 3 หรือ 4 ครั้งของเมทริกซ์ Hessian เป็นผลให้วิธีการมาบรรจบกันในการวนซ้ำน้อยลงและต้องการการคำนวณฟังก์ชันวัตถุประสงค์น้อยกว่าวิธีขอบเขตความเชื่อมั่นอื่นๆ ที่นำมาใช้ อัลกอริธึมนี้แสดงถึงการกำหนดเมทริกซ์ Hessian ที่สมบูรณ์เท่านั้น และไม่สนับสนุนความสามารถในการใช้ฟังก์ชันผลคูณของ Hessian และเวกเตอร์ที่กำหนดเอง

ตัวอย่างการย่อฟังก์ชัน Rosenbrock ให้เหลือน้อยที่สุด:

res = minimize(rosen, x0, method='trust-exact',
               jac=rosen_der, hess=rosen_hess,
               options={'gtol': 1e-8, 'disp': True})
res.x

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 13
         Function evaluations: 14
         Gradient evaluations: 13
         Hessian evaluations: 14

array([1., 1., 1., 1., 1.])

เราคงจะหยุดอยู่แค่นั้น ในบทความถัดไป ฉันจะพยายามบอกสิ่งที่น่าสนใจที่สุดเกี่ยวกับการย่อเล็กสุดแบบมีเงื่อนไข การประยุกต์ใช้การย่อเล็กสุดในการแก้ปัญหาการประมาณ การลดฟังก์ชันของตัวแปรตัวหนึ่งให้เหลือน้อยที่สุด ตัวย่อแบบไม่มีเงื่อนไข และการค้นหารากของระบบสมการโดยใช้ scipy.optimize บรรจุุภัณฑ์.

ที่มา: https://docs.scipy.org/doc/scipy/reference/

ที่มา: will.com

SciPy การเพิ่มประสิทธิภาพ