SciPy (تلفظ سائی پائی) Numpy Python توسیع پر مبنی ایک ریاضیاتی ایپلیکیشن پیکج ہے۔ SciPy کے ساتھ، آپ کا انٹرایکٹو Python سیشن وہی مکمل ڈیٹا سائنس اور پیچیدہ سسٹم پروٹو ٹائپنگ ماحول بن جاتا ہے جیسا کہ MATLAB، IDL، Octave، R-Lab، اور SciLab۔ آج میں مختصراً اس بارے میں بات کرنا چاہتا ہوں کہ scipy.optimize پیکیج میں کچھ معروف اصلاحی الگورتھم کیسے استعمال کیے جائیں۔ فنکشنز کے استعمال کے بارے میں مزید تفصیلی اور تازہ ترین مدد ہمیشہ ہیلپ() کمانڈ یا Shift+Tab استعمال کرکے حاصل کی جاسکتی ہے۔
تعارف
اپنے آپ کو اور قارئین کو بنیادی ذرائع کی تلاش اور پڑھنے سے بچانے کے لیے، طریقوں کی تفصیل کے لنکس بنیادی طور پر ویکیپیڈیا پر ہوں گے۔ ایک اصول کے طور پر، یہ معلومات عام اصطلاحات میں طریقوں اور ان کی درخواست کی شرائط کو سمجھنے کے لیے کافی ہے۔ ریاضی کے طریقوں کے جوہر کو سمجھنے کے لیے، مزید مستند اشاعتوں کے لنکس پر عمل کریں، جو ہر مضمون کے آخر میں یا آپ کے پسندیدہ سرچ انجن میں مل سکتے ہیں۔
لہذا، scipy.optimize ماڈیول میں درج ذیل طریقہ کار کا نفاذ شامل ہے:
- مختلف الگورتھم (نیلڈر میڈ سمپلیکس، بی ایف جی ایس، نیوٹن کنجوگیٹ گریڈیئنٹس، и )
- عالمی اصلاح (مثال کے طور پر: , )
- باقیات کو کم سے کم کرنا (least_squares) اور وکر فٹنگ الگورتھم غیر لکیری کم سے کم مربعوں کا استعمال کرتے ہوئے (کرو_فٹ)
- ایک متغیر (minim_scalar) کے اسکیلر افعال کو کم کرنا اور جڑوں کی تلاش (root_scalar)
- مختلف الگورتھم (ہائبرڈ پاول، یا بڑے پیمانے پر طریقے جیسے ).
اس مضمون میں ہم اس پوری فہرست میں سے صرف پہلی چیز پر غور کریں گے۔
متعدد متغیرات کے اسکیلر فنکشن کی غیر مشروط تخفیف
scipy.optimize پیکج سے کم سے کم فنکشن کئی متغیرات کے اسکیلر فنکشنز کے مشروط اور غیر مشروط مائنسائزیشن کے مسائل کو حل کرنے کے لیے ایک عمومی انٹرفیس فراہم کرتا ہے۔ یہ ظاہر کرنے کے لیے کہ یہ کیسے کام کرتا ہے، ہمیں کئی متغیرات کے ایک مناسب فنکشن کی ضرورت ہوگی، جسے ہم مختلف طریقوں سے کم کریں گے۔
ان مقاصد کے لیے، N متغیر کا روزن بروک فنکشن کامل ہے، جس کی شکل ہے:
اس حقیقت کے باوجود کہ Rosenbrock فنکشن اور اس کے Jacobi اور Hessian matrices (بالترتیب پہلے اور دوسرے مشتقات) پہلے ہی 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)وضاحت کے لیے، آئیے 3D میں دو متغیرات کے روزن بروک فنکشن کی قدریں کھینچتے ہیں۔
ڈرائنگ کوڈ
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 پر ہے۔ آئیے مثالیں دیکھتے ہیں کہ مختلف scipy.optimize طریقہ کار کا استعمال کرتے ہوئے Rosenbrock فنکشن کی کم از کم قیمت کا تعین کیسے کیا جائے۔
نیلڈر میڈ سمپلیکس طریقہ
0-جہتی جگہ میں ایک ابتدائی نقطہ x5 ہونے دیں۔ آئیے الگورتھم کا استعمال کرتے ہوئے اس کے قریب ترین روزن بروک فنکشن کا کم از کم نقطہ تلاش کریں۔ (الگورتھم کو طریقہ پیرامیٹر کی قدر کے طور پر بیان کیا گیا ہے):
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 طریقہ سادہ کم سے کم مسائل کے لیے ایک اچھا انتخاب ہے۔ تاہم، چونکہ یہ تدریجی تخمینے استعمال نہیں کرتا ہے، اس لیے کم از کم تلاش کرنے میں زیادہ وقت لگ سکتا ہے۔
پاول کا طریقہ
ایک اور اصلاحی الگورتھم جس میں صرف فنکشن کی قدروں کا حساب لگایا جاتا ہے۔ . اسے استعمال کرنے کے لیے، آپ کو کم سے کم فنکشن میں طریقہ = 'پاول' سیٹ کرنا ہوگا۔
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 طریقہ کو عام طور پر سمپلیکس طریقہ سے کم فنکشن کالز کی ضرورت ہوتی ہے۔
آئیے روزن بروک فنکشن کے مشتق کو تجزیاتی شکل میں تلاش کرتے ہیں:
یہ اظہار پہلے اور آخری کے علاوہ تمام متغیرات کے مشتقات کے لیے درست ہے، جن کی تعریف اس طرح کی گئی ہے:
آئیے 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 میٹرکس، Hessian)۔
اگر Hessian مثبت ہے، تو اس فنکشن کی مقامی کم از کم کو چوکور شکل کے صفر گریڈینٹ کو صفر کے برابر کر کے تلاش کیا جا سکتا ہے۔ نتیجہ یہ ہوگا:
الٹا ہیسیئن کو کنجوگیٹ گریڈینٹ طریقہ استعمال کرتے ہوئے شمار کیا جاتا ہے۔ روزن بروک فنکشن کو کم سے کم کرنے کے لیے اس طریقہ کو استعمال کرنے کی ایک مثال ذیل میں دی گئی ہے۔ نیوٹن-سی جی طریقہ استعمال کرنے کے لیے، آپ کو ایک فنکشن بتانا ہوگا جو ہیسیئن کا حساب لگاتا ہے۔
تجزیاتی شکل میں روزن بروک فنکشن کا ہیسین برابر ہے:
جہاں и ، میٹرکس کی وضاحت کریں۔ .
میٹرکس کے باقی غیر صفر عناصر برابر ہیں:
مثال کے طور پر، پانچ جہتی جگہ N = 5 میں، Rosenbrock فنکشن کے لیے Hessian میٹرکس ایک بینڈ کی شکل رکھتا ہے:
کوڈ جو کنجوگیٹ گریڈینٹ (نیوٹن) طریقہ استعمال کرتے ہوئے روزن بروک فنکشن کو کم سے کم کرنے کے لیے کوڈ کے ساتھ اس ہیسین کا حساب لگاتا ہے:
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 کی پیداوار کے برابر ہو۔ اس طرح، ایک کمپیوٹیشنل نقطہ نظر سے، فوری طور پر ایک فنکشن کی وضاحت کرنا زیادہ بہتر ہے جو ہیسیئن کے مصنوع کا نتیجہ ایک صوابدیدی ویکٹر کے ساتھ واپس کرتا ہے۔
ہیس فنکشن پر غور کریں، جو مائنسائزیشن ویکٹر کو پہلی دلیل کے طور پر لیتا ہے، اور ایک صوابدیدی ویکٹر کو دوسری دلیل کے طور پر (کم سے کم کرنے کے فنکشن کے دیگر دلائل کے ساتھ)۔ ہمارے معاملے میں، ایک صوابدیدی ویکٹر کے ساتھ Rosenbrock فنکشن کے Hessian کی پیداوار کا حساب لگانا زیادہ مشکل نہیں ہے۔ اگر p ایک صوابدیدی ویکٹر ہے، پھر مصنوع کی طرح لگتا ہے:
وہ فنکشن جو Hessian اور ایک صوابدیدی ویکٹر کی پیداوار کا حساب لگاتا ہے اسے minimize فنکشن میں 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 میٹرکس کی تعریف کے ساتھ مثال:
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.]کریلوف قسم کے طریقے
ٹرسٹ-این سی جی طریقہ کی طرح، کرائیلوف قسم کے طریقے بڑے پیمانے پر مسائل کو حل کرنے کے لیے موزوں ہیں کیونکہ وہ صرف میٹرکس ویکٹر پروڈکٹس استعمال کرتے ہیں۔ ان کا جوہر اعتماد کے علاقے میں کسی مسئلے کو حل کرنا ہے جو ایک کٹے ہوئے کرائیلوف ذیلی جگہ سے محدود ہے۔ غیر یقینی مسائل کے لیے، یہ طریقہ استعمال کرنا بہتر ہے، کیونکہ یہ ٹرسٹ-این سی جی طریقہ کے مقابلے میں، میٹرکس ویکٹر پروڈکٹس کی فی سب پرابلم کی کم تعداد کی وجہ سے نان لائنر تکرار کی ایک چھوٹی تعداد کا استعمال کرتا ہے۔ اس کے علاوہ، چوکور ذیلی مسئلے کا حل ٹرسٹ-این سی جی طریقہ استعمال کرنے سے زیادہ درست طریقے سے پایا جاتا ہے۔
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.]
اعتماد کے علاقے میں تخمینی حل کے لیے الگورتھم
تمام طریقے (نیوٹن-سی جی، ٹرسٹ-این سی جی اور ٹرسٹ-کریلوف) بڑے پیمانے پر مسائل (ہزاروں متغیرات کے ساتھ) کو حل کرنے کے لیے موزوں ہیں۔ یہ اس حقیقت کی وجہ سے ہے کہ بنیادی کنجوگیٹ گریڈینٹ الگورتھم معکوس ہیسیئن میٹرکس کا تخمینہ تعین کرتا ہے۔ حل ہیسیئن کی واضح توسیع کے بغیر، تکراری طور پر پایا جاتا ہے۔ چونکہ آپ کو صرف ایک ہیسیئن اور ایک صوابدیدی ویکٹر کی پیداوار کے لیے ایک فنکشن کی وضاحت کرنے کی ضرورت ہے، اس لیے یہ الگورتھم خاص طور پر اسپارس (بینڈ ڈائیگنل) میٹرکس کے ساتھ کام کرنے کے لیے اچھا ہے۔ یہ کم میموری کی قیمت اور اہم وقت کی بچت فراہم کرتا ہے۔
درمیانے درجے کے مسائل کے لیے، Hessian کو ذخیرہ کرنے اور فیکٹرنگ کی لاگت اہم نہیں ہے۔ اس کا مطلب یہ ہے کہ ٹرسٹ ریجن کے ذیلی مسائل کو تقریباً بالکل ٹھیک حل کرتے ہوئے، کم تکرار میں حل حاصل کرنا ممکن ہے۔ ایسا کرنے کے لیے، ہر چوکور ذیلی مسئلے کے لیے کچھ نان لائنر مساوات کو تکراری طور پر حل کیا جاتا ہے۔ اس طرح کے حل کے لیے عام طور پر Hessian میٹرکس کی 3 یا 4 Cholesky decompositions کی ضرورت ہوتی ہے۔ نتیجے کے طور پر، طریقہ کم تکرار میں بدل جاتا ہے اور دوسرے لاگو کردہ اعتماد والے علاقے کے طریقوں کے مقابلے میں کم معروضی فنکشن کیلکولیشن کی ضرورت ہوتی ہے۔ اس الگورتھم میں صرف مکمل Hessian میٹرکس کا تعین کرنا شامل ہے اور یہ Hessian کے پروڈکٹ فنکشن اور ایک صوابدیدی ویکٹر کو استعمال کرنے کی صلاحیت کی حمایت نہیں کرتا ہے۔
روزن بروک فنکشن کو کم سے کم کرنے کے ساتھ مثال:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimization terminated successfully.
Current function value: 0.000000
Iterations: 13
Function evaluations: 14
Gradient evaluations: 13
Hessian evaluations: 14
array([1., 1., 1., 1., 1.])ہم شاید وہیں رک جائیں گے۔ اگلے آرٹیکل میں میں مشروط مائنسائزیشن کے بارے میں سب سے دلچسپ باتیں بتانے کی کوشش کروں گا، قریب کے مسائل کو حل کرنے میں minimization کا اطلاق، ایک متغیر کے فنکشن کو کم سے کم کرنا، صوابدیدی minimizers، اور scipy.optimize کا استعمال کرتے ہوئے مساوات کے نظام کی جڑیں تلاش کرنا۔ پیکج
ماخذ:
ماخذ: www.habr.com