عرض مصدر خوارزمية أصل التدرج

{{مقالة غير مراجعة|تاريخ = أبريل 2020}}

'''أصل التدرج''' أو '''النزول الاشتقاقي<ref>{{استشهاد بويكي بيانات|Q111421033|صفحة=72}}</ref>''' هو [[خوارزمية]] [[استمثال (رياضيات)|تحسين]] [[طريقة تكرارية|تكرارية من]] الدرجة الأولى للعثور على [[النقاط الحدية|الحد الأدنى المحلي]] لدالة قابلة للاشتقاق. للعثور على الحد الأدنى المحلي للدالة باستخدام منحدر التدرج، نتخذ خطوات تتناسب مع ''سلبية'' [[تدرج (رياضيات)|التدرج]] (أو التدرج التقريبي) للدالة عند النقطة الحالية. ولكن إذا اتخذنا بدلاً من ذلك خطوات تتناسب مع ''إيجابية'' التدرج، فإننا نقترب من [[النقاط الحدية|الحد الأقصى المحلي]] لهذه الدالة؛ يُعرف الإجراء بعد ذلك '''بصعود متدرج''' . تم اقتراح خوارزمية أصل التدرج من قبل العالم الرياضي [[أوغستين لوي كوشي]] في عام 1847.<ref>{{استشهاد بدورية محكمة|الأول=C.|الأخير=Lemaréchal|مؤلف-وصلة=Claude Lemaréchal|عنوان=Cauchy and the Gradient Method|صحيفة=Doc Math Extra|صفحات=251–254|سنة=2012|مسار=https://www.math.uni-bielefeld.de/documenta/vol-ismp/40_lemarechal-claude.pdf| مسار أرشيف = https://web.archive.org/web/20181229073335/https://www.math.uni-bielefeld.de/documenta/vol-ismp/40_lemarechal-claude.pdf | تاريخ أرشيف = 29 ديسمبر 2018 }}</ref>

== وصف ==
[[ملف:Gradient_descent.svg|تصغير|375x375بك| رسم توضيحي لأصل التدرج على سلسلة من مجموعات المستويات]]
يعتمد أصل التدرج على الملاحظة أنه إذا كانت [[دالة متعددة المتغيرات الحقيقية|الدالة متعددة المتغيرات]] <math>F(\mathbf{x})</math> معرفة وقابلة للاشتقاق في جوار النقطة <math>\mathbf{a}</math> ، فإن<math>F(\mathbf{x})</math> ينخفض بسرعة أكبرإذا ذهبنا من <math>\mathbf{a}</math> في اتجاه التدرج السلبي لـ <math>F</math> في <math>\mathbf{a}, -\nabla F(\mathbf{a})</math> .

و يتبع ذلك أنه إذا كان

: <math> \mathbf{a}_{n+1} = \mathbf{a}_n-\gamma\nabla F(\mathbf{a}_n)</math>

فإنه لكل <math>\gamma \in \R_{+}</math> صغيرة بما يكفي، <math>F(\mathbf{a_n})\geq F(\mathbf{a_{n+1}})</math> . وبعبارة أخرى، الحد<math>\gamma\nabla F(\mathbf{a})</math> يطرح من <math>\mathbf{a}</math> لأننا نريد التحرك ضد التدرج نحو الحد الأدنى المحلي. مع أخذ هذه الملاحظة في الاعتبار، يبدأ المرء باختيار <math>\mathbf{x}_0</math> كنقطة بداية <math>F</math> (يمكن اختيارها عشوائيا)، ويعتبر بعد ذلك التسلسل <math>\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \ldots</math> , بحيث:

: <math>\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0.</math>

لدينا تسلسل [[دالة رتيبة|رتيب]]

: <math>F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \cdots,</math>

لذا نأمل أن يكون التسلسل <math>(\mathbf{x}_n)</math> يتقارب نحو الحد الأدنى المحلي المطلوب. لاحظ أن قيمة ''حجم الخطوة'' <math>\gamma</math> يسمح بالتغيير في كل تكرار. مع بعض الافتراضات على الدالة <math>F</math> (فمثلا، <math>F</math> [[دالة محدبة|محدبة]] و <math>\nabla F</math> ليبشيتزية) وخيارات معينة من <math>\gamma</math> (على سبيل المثال، يتم اختياره إما عن طريق البحث الخطي الذي يلبي شروط وولفه، أو طريقة بارزيلاي - بوروين <ref>{{استشهاد بدورية محكمة|الأول=Jonathan|الأخير=Barzilai|الأول2=Jonathan M.|الأخير2=Borwein|عنوان=Two-Point Step Size Gradient Methods|صحيفة=IMA Journal of Numerical Analysis|المجلد=8|العدد=1|سنة=1988|صفحات=141–148|DOI=10.1093/imanum/8.1.141}}</ref><ref>{{استشهاد بكتاب|مؤلف1=Fletcher|الأول=R.|سنة=2005|الفصل=On the Barzilai–Borwein Method|محرر1=Qi|محرر2=Teo|محرر2-الأول=K.|محرر3-الأخير=Yang|محرر3-الأول=X.|عنوان=Optimization and Control with Applications|سلسلة=Applied Optimization|المجلد=96|ناشر=Springer|مكان=Boston|صفحات=235–256|ISBN=0-387-24254-6}}</ref> الموضحة على النحو التالي):

: <math>\gamma_{n} = \frac{ \left | \left (\mathbf x_{n} - \mathbf x_{n-1} \right )^T \left [\nabla F (\mathbf x_{n}) - \nabla F (\mathbf x_{n-1}) \right ] \right |}{\left \|\nabla F(\mathbf{x}_{n}) - \nabla F(\mathbf{x}_{n-1}) \right \|^2}</math>

يمكن ضمان [[متسلسلة متقاربة|التقارب]] إلى الحد الأدنى المحلي.

عندما تكون الدالة <math>F</math> [[دالة محدبة|محدبة]]، كل الحدود الدنيا المحلية هي أيضًا حد أدنى عام، لذلك في هذه الحالة يمكن أن يتقارب أصل التدرج إلى الحل العام.

هذه العملية موضحة في الصورة المجاورة. هنا <math>F</math> من المفترض أن يتم تعريفها على المستوى، وأن الرسم البياني له شكل [[سلطانية (وعاء)|وعاء]]. المنحنيات الزرقاء هي [[خط منسوب|الخطوط المنسوبية]]، أي المناطق التي تكون فيها قيمة <math>F</math> ثابتة. يظهر سهم أحمر ينشأ عند نقطة اتجاه التدرج السلبي في تلك النقطة. لاحظ أن التدرج (السلبي) عند نقطة ما هو [[تعامد (جبر خطي)|متعامد]] مع خط الكفاف الذي يمر عبر تلك النقطة. نرى أن ''أصل'' التدرج يقودنا إلى قاع الوعاء، أي إلى النقطة التي تكون فيها قيمة الدالة <math>F</math> هي الحد الأدنى.

=== أمثلة ===
يعاني أصل التدرج من مشاكل في الدوال «المرضية» مثل [[دالة روزين بروك]] الموضحة هنا.

: <math>f(x_1, x_2) = (1-x_1)^2 + 100(x_2-{x_1}^2)^2.</math>

تحتوي دالة روزين بروك على واد منحني ضيق يحتوي على الحد الأدنى. الجزء السفلي من الوادي مسطح للغاية. بسبب الوادي المسطح المنحني يكون التحسين متعرجًا ببطء مع أحجام خطوات صغيرة نحو الحد الأدنى.

[[ملف:Banana-SteepDesc.gif|400x400بك]]

يمكننا رؤية مثال آخر على الطبيعة المتعرجة لهذه الطريقة: فلنطبق خوارزمية أصل التدرج على الدالة التالية:

: <math>F(x,y)=\sin\left(\frac{1}{2} x^2 - \frac{1}{4} y^2 + 3 \right)\cos\left(2 x+1-e^y\right).</math>

[[ملف:Gradient_ascent_(contour).png|350x350بك|خوارزمية أصل التدرج في العمل. (1: كفاف)]][[ملف:Gradient_ascent_(surface).png|450x450بك|خوارزمية أصل التدرج في العمل. (2: السطح)]]

== استعمال أصل التدرج في خوارزميات [[تعلم الآلة|التعلم الآلي]] ==

يعتبر أصل التدرج هو أساس خوارزميات التحسين المستخدمة في ميدان [[تعلم الآلة|التعلم الآلي]]
حيث تتكون شبكات التعلم الآلي من عدد من [[عصب اصطناعي|العصبونات الاصطناعية]]، لكل منها وزن وانحياز <br />
فشبكة التعلم الآلي تشكل في الحقيقة دالة متعددة المتغيرات، متغيراتها هي الأوزان والانحيازات التي تخضع للتدريب
<br />
يتلخص تدريب الشبكات العصبية في الخطوات التالية: <br />
1) حساب دالة «الخسارة»: وهي الدالة الناتجة عن حساب الفرق بين قيم مخارج الشبكة العصبية عندما تطبق على مجموعة التدريب، والنتائج الحقيقية المنتظرة من مجموعة التدريب <br />
2) حساب المشتقات الجزئية لدالة الخسارة، بالنسبة لمجموعة الأوزان والانحيازات <br />
3) تطبيق [[انتشار خلفي|الانتشار الخلفي]] عبر خوارزمية '''أصل التدرج'''، وذلك عن طريق طرح المشتقات الجزئية لدالة الخسارة من الأوزان والانحيازات (بعد ضربها بمعامل التعلم)، وإعادة الخطوات 1) و 2) و 3) في طريق التدرج نحو الحد الأدنى لدالة الخسارة
<ref>{{استشهاد ويب|مسار= https://towardsdatascience.com/gradient-descent-3a7db7520711|عنوان=Gradient Descent<!-- عنوان مولد بالبوت -->|تاريخ الوصول=2020-05-01|لغة=en|مسار أرشيف= https://web.archive.org/web/20200501004256/https://towardsdatascience.com/gradient-descent-3a7db7520711|تاريخ أرشيف=2020-05-01}}</ref>

== تعليقات ==
يعمل أصل التدرج في فضاءَات متعددة الأبعاد وحتى في الأبعاد اللانهائية.<br />
في حالة الأبعاد اللانهائية، تكون مساحة البحث عادةً عبارة عن [[فضاء دالي]]، ونحسب [[مشتقة فريشيه]] الخاصة بالدالة التي سيتم تصغيرها لتحديد اتجاه الهبوط.<ref>{{استشهاد بكتاب|الأول=G. P.|مؤلف1=Akilov|الأول2=L. V.|مؤلف2=Kantorovich|مؤلف2-وصلة=Leonid Kantorovich|عنوان=Functional Analysis|ناشر=Pergamon Press|طبعة=2nd|ISBN=0-08-023036-9|سنة=1982}}</ref>

يمكن أن يستغرق أصل التدرج العديد من التكرارات لحساب الحد الأدنى المحلي [[الدقة والضبط|بالدقة]] المطلوبة إذا كان [[انحناء (رياضيات)|انحناء]] الدالة مختلفا اختلافا كبيرا حسب الاتجاهات. لمثل هذه الدوال، فإن التهيئة المسبقة، التي تغير هندسة المساحة لتشكيل مجموعات مستوى الدالة مثل [[اتحاد مركزي|الدوائر المتحدة المركز]]، تعالج التقارب البطيء. ومع ذلك، يمكن أن يكون إنشاء وتطبيق الشروط المسبقة مكلفًا من الناحية الحسابية.

يمكن دمج أصل التدرج مع بحث خطي، للعثور على حجم الخطوة الأمثل محليًا <math>\gamma</math> في كل تكرار. يمكن أن يستغرق إجراء البحث الخطي وقتًا طويلاً.

على العكس من ذلك، باستخدام ثابتة صغيرة <math>\gamma</math> يمكن أن يسفر عن تقارب ضعيف.

يمكن أن تكون الطرق المستندة إلى [[طريقة نيوتن]] وانقلاب [[مصفوفة هيسية|الهسيان]] باستخدام تقنيات التدرج المترافق بدائل أفضل.<ref>{{استشهاد بكتاب|الأول=W. H.|مؤلف1=Press|الأول2=S. A.|مؤلف2=Teukolsky|الأول3=W. T.|الأخير3=Vetterling|الأول4=B. P.|الأخير4=Flannery|عنوان=Numerical Recipes in C: The Art of Scientific Computing|مسار=https://archive.org/details/numericalrecipes00pres_0|طبعة=2nd|ناشر=Cambridge University Press|مكان=New York|سنة=1992|ISBN=0-521-43108-5| مسار أرشيف = https://web.archive.org/web/20200430204740/https://archive.org/details/numericalrecipes00pres_0 | تاريخ أرشيف = 30 أبريل 2020 }}</ref><ref>{{استشهاد بكتاب|الأول=T.|مؤلف1=Strutz|عنوان=Data Fitting and Uncertainty: A Practical Introduction to Weighted Least Squares and Beyond|طبعة=2nd|ناشر=Springer Vieweg|سنة=2016|ISBN=978-3-658-11455-8}}</ref> بشكل عام، تتقارب هذه الأساليب في عدد أقل من التكرارات، ولكن تكلفة كل تكرار أعلى. ومن الأمثلة على ذلك طريقة BFGS التي تتكون من حساب مصفوفة في كل خطوة يتم من خلالها ضرب متجهة التدرج للذهاب إلى اتجاه «أفضل»، مقترنًا بخوارزمية بحث خطي أكثر تعقيدًا، للعثور على القيمة «الأفضل» لـ <math>\gamma.</math>

بالنسبة للمسائل الكبيرة للغاية، حيث تهيمن مشاكل ذاكرة الكمبيوتر، يجب استخدام طريقة محدودة الذاكرة مثل L-BFGS بدلاً من BFGS أو أصل التدرج.

يمكن النظر إلى أصل التدرج على أنه تطبيق [[طريقة أويلر]] لحل [[معادلة تفاضلية عادية|المعادلات التفاضلية العادية]] <math>x'(t)=-\nabla f(x(t))</math> [[حقل متجهات|لتدفق متدرج]].

== أمثلة حسابية ==
تطبق أمثلة التعليمات البرمجية التالية خوارزمية أصل التدرج للعثور على الحد الأدنى للدالة <math>f(x) = x^4-3x^3 + 2,</math> مع مشتقة:<math>f'(x) = 4x^{3} - 9x^{2}.</math>

حل ل <math>4x^{3} - 9x^{2} = 0</math> وتقييم المشتق الثاني عند الحلول يبين أن الدالة لها نقطة هضبة عند 0 والحد الأدنى العام عند <math>x = \tfrac{9}{4}.</math>

=== بيثون ===
فيما يلي تطبيق [[بايثون (لغة برمجة)|بلغة برمجة Python]] : <syntaxhighlight lang="python">
next_x = 6 # We start the search at x=6
gamma = 0.01 # Step size multiplier
precision = 0.00001 # Desired precision of result
max_iters = 10000 # Maximum number of iterations

# Derivative function
def df(x):
  return 4 * x ** 3 - 9 * x ** 2

for _ in range(max_iters):
  current_x = next_x
  next_x = current_x - gamma * df(current_x)

  step = next_x - current_x
  if abs(step) <= precision:
    break

print("Minimum at ", next_x)

# The output for the above will be something like
# "Minimum at 2.2499646074278457"
</syntaxhighlight>

=== سكالا ===
هنا تنفيذ في [[سكالا (لغة برمجة)|لغة برمجة سكالا]] <syntaxhighlight lang="scala">
import math._
 
val curX = 6
val gamma = 0.01
val precision = 0.00001
val previousStepSize = 1 / precision

def df(x: Double): Double = 4 * pow(x, 3) - 9 * pow(x, 2)

def gradientDescent(precision: Double, previousStepSize: Double, curX: Double): Double = {
 if (previousStepSize > precision) {
  val newX = curX + -gamma * df(curX)	
  println(curX)
  gradientDescent(precision, abs(newX - curX), newX)
 } else curX	 
}

val ans = gradientDescent(precision, previousStepSize, curX)
println(s"The local minimum occurs at $ans")
</syntaxhighlight>

=== جافا ===
<syntaxhighlight lang="java">

import java.util.function.Function;
import static java.lang.Math.pow;
import static java.lang.Math.abs

double gamma = 0.01;
double precision = 0.00001;

Function<Double,Double> df = x -> 4 * pow(x, 3) - 9 * pow(x, 2);

double gradientDescent(Function<Double,Double> f) {

	double curX = 6.0;
	double previousStepSize = 1.0;

	while (previousStepSize > precision) {
 double prevX = curX;
 curX -= gamma * f.apply(prevX);
 previousStepSize = abs(curX - prevX);
	}
	return curX;
}

double res = gradientDescent(df);
System.out.println(String.format("The local minimum occurs at %f", res));

</syntaxhighlight>

== مراجع ==
{{مراجع}}
{{روابط شقيقة}}

{{خوارزميات التحسين}}
{{شريط سفلي حوسبة تفاضلية}}
{{شريط سفلي ذكاء اصطناعي}}
{{شريط بوابات|تحليل رياضي|رياضيات|علم الحاسوب}}

[[تصنيف:استمثال رياضي]]
[[تصنيف:طرق الدرجة الأولى]]