مرجع
آخر الزيارات

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

1٬059 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: أصل التدرج أو النزول الاشتقاقي هو خوارزمية تحسين تكرارية من الدرجة الأولى للعثور على الحد الأدنى المحلي لدالة قابلة للاشتقاق. تجد هنا «break»، «استعمال أصل التدرج في خوارزميات التعلم الآلي» و«step = next_x - current_x» ضمن 19 قسماً.
المحتويات
  1. break
  2. استعمال أصل التدرج في خوارزميات التعلم الآلي
  3. step = next_x - current_x
  4. # Derivative function
  5. if (previousStepSize > precision) {
  6. current_x = next_x
  7. أمثلة حسابية
  8. val previousStepSize = 1 / precision
  9. بيثون
  10. تعليقات
  11. أمثلة
  12. double precision = 0.00001;
  13. لدينا تسلسل رتيب
  14. سكالا
  15. }
  16. وصف
  17. gamma = 0.01 # Step size multiplier
  18. double res = gradientDescent(df);
  19. و يتبع ذلك أنه إذا كان

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

break

  • print("Minimum at ", next_x)
  • # The output for the above will be something like
  • # "Minimum at 2.2499646074278457"

استعمال أصل التدرج في خوارزميات التعلم الآلي

يتلخص تدريب الشبكات العصبية في الخطوات التالية:

وعلى صعيد آخر، 2) حساب المشتقات الجزئية لدالة الخسارة، بالنسبة لمجموعة الأوزان والانحيازات

ومن جهة أخرى، 3) تطبيق الانتشار الخلفي عبر خوارزمية أصل التدرج، وذلك عن طريق طرح المشتقات الجزئية لدالة الخسارة من الأوزان والانحيازات (بعد ضربها بمعامل التعلم)، وإعادة الخطوات 1) و 2) و 3) في طريق التدرج نحو الحد الأدنى لدالة الخسارة

وفي هذا السياق، حيث تتكون شبكات التعلم الآلي من عدد من العصبونات الاصطناعية، لكل منها وزن وانحياز

إضافةً إلى ذلك، يعتبر أصل التدرج هو أساس خوارزميات التحسين المستعملة في ميدان التعلم الآلي

وفي هذا الصدد، 1) حساب دالة «الخسارة»: وهي الدالة الناتجة عن حساب الفرق بين قيم مخارج الشبكة العصبية عندما تطبق على مجموعة التدريب، والنتائج الحقيقية المنتظرة من مجموعة التدريب

من جانب آخر، فشبكة التعلم الآلي تشكل في الحقيقة دالة متعددة المتغيرات، متغيراتها هي الأوزان والانحيازات التي تخضع للتدريب

step = next_x - current_x

if abs(step) <= precision:

# Derivative function

  • def df(x):
  • return 4 * x ** 3 - 9 * x ** 2
  • for _ in range(max_iters):

if (previousStepSize > precision) {

  • val newX = curX + -gamma * df(curX)
  • println(curX)
  • gradientDescent(precision, abs(newX - curX), newX)
  • } else curX

current_x = next_x

next_x = current_x - gamma * df(current_x)

أمثلة حسابية

ومن جهة أخرى، تطبق أمثلة التعليمات البرمجية التالية خوارزمية أصل التدرج للعثور على الحد الأدنى للدالة مع مشتقة:

من جانب آخر، حل ل وتقييم المشتق الثاني عند الحلول يبين أن الدالة لها نقطة هضبة عند 0 والحد الأدنى العام عند

val previousStepSize = 1 / precision

وعلى صعيد آخر، def gradientDescent(precision: Double, previousStepSize: Double, curX: Double): Double = {

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

بيثون

وفي السياق ذاته، فيما يلي تطبيق بلغة برمجة Python : next_x = 6 # We start the search at x=6

تعليقات

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

في هذا الإطار، يمكن أن تكون الطرق المستندة إلى طريقة نيوتن وانقلاب الهسيان باستخدام تقنيات التدرج المترافق بدائل أفضل. بشكل عام، تتقارب هذه الأساليب في عدد أقل من التكرارات، ولكن تكلفة كل تكرار أعلى. ومن الأمثلة على ذلك طريقة BFGS التي تتكون من حساب مصفوفة في كل خطوة يتم من خلالها ضرب متجهة التدرج للذهاب إلى اتجاه «أفضل»، مقترنًا بخوارزمية بحث خطي أكثر تعقيدًا، للعثور على القيمة «الأفضل» لـ

وعلى صعيد آخر، يمكن النظر إلى أصل التدرج على أنه تطبيق طريقة أويلر لحل المعادلات التفاضلية العادية لتدفق متدرج.

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

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

وفي هذا السياق، يعمل أصل التدرج في فضاءَات متعددة الأبعاد وحتى في الأبعاد اللانهائية.

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

علاوةً على ذلك، على العكس من ذلك، باستخدام ثابتة صغيرة يمكن أن يسفر عن تقارب ضعيف.

أمثلة

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

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

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

double precision = 0.00001;

  • Function df = x -> 4 * pow(x, 3) - 9 * pow(x, 2);
  • double gradientDescent(Function 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;
  • }

لدينا تسلسل رتيب

كذلك، عندما تكون الدالة محدبة، كل الحدود الدنيا المحلية هي كذلك حد أدنى عام، لذلك في هذه الحالة يمكن أن يتقارب أصل التدرج إلى الحل العام.

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

يمكن ضمان التقارب إلى الحد الأدنى المحلي.

وفي السياق ذاته، لذا نأمل أن يكون التسلسل يتقارب نحو الحد الأدنى المحلي المطلوب. لاحظ أن قيمة حجم الخطوة يسمح بالتغيير في كل تكرار. مع بعض الافتراضات على الدالة (فمثلا، محدبة و ليبشيتزية) وخيارات معينة من (مثلًا، يتم اختياره إما عن طريق البحث الخطي الذي يلبي شروط وولفه، أو طريقة بارزيلاي - بوروين الموضحة على النحو التالي):

سكالا

  • هنا تنفيذ في لغة برمجة سكالا import math._
  • val curX = 6
  • val gamma = 0.01
  • val precision = 0.00001

}

  • val ans = gradientDescent(precision, previousStepSize, curX)
  • println(s"The local minimum occurs at $ans")
  • جافا
  • import java.util.function.Function;
  • import static java.lang.Math.pow;
  • import static java.lang.Math.abs
  • double gamma = 0.01;

وصف

ومن ناحية أخرى، يعتمد أصل التدرج على الملاحظة أنه إذا كانت الدالة متعددة المتغيرات معرفة وقابلة للاشتقاق في جوار النقطة ، فإن ينخفض بسرعة أكبرإذا ذهبنا من في اتجاه التدرج السلبي لـ في .

gamma = 0.01 # Step size multiplier

max_iters = 10000 # Maximum number of iterations

precision = 0.00001 # Desired precision of result

double res = gradientDescent(df);

كذلك، System.out.println(String.format("The local minimum occurs at %f", res));

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.