نزول التدرج

جزء من سلسلة عن
التعلم الآلي واستخراج البيانات
النماذج التعلم تحت الإشراف التعلم غير الخاضع للإشراف التعلم شبه الخاضع للإشراف التعلم الذاتي التعلم التعزيزي التعلم الفوقي التعلم عبر الإنترنت التعلم الدفعي التعلم المنهجي التعلم المبني على القواعد الذكاء الاصطناعي الرمزي العصبي الهندسة العصبية التعلم الآلي الكمومي
المشاكل تصنيف النمذجة التوليدية الانحدار التجميع تخفيض الأبعاد تقدير الكثافة كشف الشذوذ تنظيف البيانات التعلم الآلي التلقائي قواعد الجمعية التحليل الدلالي التنبؤ المنظم هندسة المميزات ميزة التعلم تعلم الترتيب الاستدلال النحوي التعلم الأنطولوجيا التعلم المتعدد الوسائط
التعلم الخاضع للإشراف ( التصنيف  • الانحدار ) التعلم عن طريق التدريب أشجار القرار الفرق الموسيقية التعبئة في أكياس تعزيز غابة عشوائية ك -ن ن الانحدار الخطي بايز الساذج الشبكات العصبية الاصطناعية الانحدار اللوجستي بيرسيبترون آلة متجهات الصلة (RVM) آلة الدعم المتجهي (SVM)
التجميع البتولا دواء هرمي ك- يعني غامض التوقع - التعظيم (EM) دي بي إس أي إن بصريات متوسط ​​التحول
تخفيض الأبعاد تحليل العوامل سي سي ايه ايكا لدا ن م ف تحليل البيانات الشخصية التشخيص قبل الزرع تي-SNE إس دي إل
التنبؤ المنظم النماذج الرسومية شبكة بايز حقل عشوائي مشروط ماركوف المخفي
كشف الشذوذ رانساك ك -ن ن عامل الشذوذ المحلي غابة العزلة
الشبكة العصبية الاصطناعية مُشفِّر ذاتي التعلم العميق الشبكة العصبية التغذية الأمامية الشبكة العصبية المتكررة LSTM المخابرات العسكرية الروسية رقم ESN الحوسبة الخزانية آلة بولتزمان مقيد شبكة GAN نموذج الانتشار سوم الشبكة العصبية التلافيفية يو نت لينت أليكس نت ديب دريم مجال الإشعاع العصبي محول رؤية مامبا الشبكة العصبية المتصاعدة ميمترانزستور ذاكرة الوصول العشوائي الكهروكيميائية (ECRAM)
التعلم التعزيزي التعلم عن طريق Q سارسا الفرق الزمني (TD) متعدد الوكلاء اللعب الذاتي
التعلم مع البشر التعلم النشط التمويل الجماعي الإنسان في الحلقة مؤسسة ريل إتش إف
تشخيصات النموذج معامل التحديد مصفوفة الارتباك منحنى التعلم منحنى ROC
الأسس الرياضية آلات النواة المقايضة بين التحيز والتباين نظرية التعلم الحاسوبي التقليل من المخاطر التجريبية التعلم أوكام التعلم PAC التعلم الإحصائي نظرية رأس المال الاستثماري
المجلات والمؤتمرات ECML PKDD نيوريبس شهادة ICML اي سي ال ار اي جيه سي ايه اي مل جيه إم إل آر
مقالات ذات صلة Glossary of artificial intelligence List of datasets for machine-learning research List of datasets in computer vision and image processing Outline of machine learning
v t e

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

الفكرة هي اتخاذ خطوات متكررة في الاتجاه المعاكس لمنحدر ( أو منحدر تقريبي) الدالة عند النقطة الحالية، لأن هذا هو اتجاه أشد نزول. وعلى العكس من ذلك، فإن الخطوة في اتجاه المنحدر ستؤدي إلى مسار يزيد من تلك الدالة إلى أقصى حد؛ ومن ثم تُعرف هذه العملية باسم صعود التدرج . وهي مفيدة بشكل خاص في التعلم الآلي لتقليل دالة التكلفة أو الخسارة. ^[1] لا ينبغي الخلط بين نزول التدرج وخوارزميات البحث المحلية ، على الرغم من أن كلاهما طرق تكرارية للتحسين .

يُنسب الانحدار التدرجي عمومًا إلى أوغستين لويس كوشي ، الذي اقترحه لأول مرة في عام 1847. ^{[2] اقترح} جاك هادامارد بشكل مستقل طريقة مماثلة في عام 1907. ^{[3] [4]} تمت دراسة خصائص التقارب الخاصة به لمشاكل التحسين غير الخطية لأول مرة بواسطة هاسكل كاري في عام 1944، ^[5] حيث أصبحت الطريقة مدروسة بشكل متزايد ومستخدمة في العقود التالية. ^{[6] [7]}

يُعد الامتداد البسيط للانحدار التدرجي، الانحدار التدرجي العشوائي ، بمثابة الخوارزمية الأساسية الأكثر استخدامًا لتدريب معظم الشبكات العميقة اليوم.

يعتمد الانحدار المتدرج على الملاحظة التي مفادها أنه إذا تم تعريف الدالة متعددة المتغيرات وقابلة للاشتقاق في جوار نقطة ، فإنها تتناقص بشكل أسرع إذا انتقلت من اتجاه التدرج السالب عند . ويترتب على ذلك أنه إذا ${\displaystyle F(\mathbf {x} )}$${\displaystyle \mathbf {a} }$${\displaystyle F(\mathbf {x} )}$${\displaystyle \mathbf {a} }$${\displaystyle F}$${\displaystyle \mathbf {a} ,-\nabla F(\mathbf {a} )}$

${\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma \nabla F(\mathbf {a} _{n})}$

بالنسبة لحجم خطوة أو معدل تعلم صغير بما يكفي ، إذن . بعبارة أخرى، يتم طرح المصطلح من لأننا نريد التحرك ضد التدرج، نحو الحد الأدنى المحلي. مع وضع هذه الملاحظة في الاعتبار، يبدأ المرء بتخمين لحد أدنى محلي لـ ، وينظر في التسلسل بحيث ${\displaystyle \gamma \in \mathbb {R} _{+}}$${\displaystyle F(\mathbf {a_{n}} )\geq F(\mathbf {a_{n+1}} )}$${\displaystyle \gamma \nabla F(\mathbf {a} )}$${\displaystyle \mathbf {a} }$${\displaystyle \mathbf {x} _{0}}$${\displaystyle F}$${\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots }$

${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$

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

${\displaystyle F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,}$

وبالتالي، يتقارب التسلسل إلى الحد الأدنى المحلي المطلوب. لاحظ أنه يُسمح بتغيير قيمة حجم الخطوة في كل تكرار.${\displaystyle (\mathbf {x} _{n})}$ ${\displaystyle \gamma }$

من الممكن ضمان التقارب إلى حد أدنى محلي تحت افتراضات معينة للدالة (على سبيل المثال، محدب وليبشيتز ) واختيارات معينة لـ . وتشمل هذه الاختيارات التسلسل ${\displaystyle F}$${\displaystyle F}$ ${\displaystyle \nabla F}$ ${\displaystyle \gamma }$

${\displaystyle \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}}}}$

كما هو الحال في طريقة بارزيلاي-بوروين ، ^{[8] [9]} أو تسلسل يلبي شروط وولف (والتي يمكن العثور عليها باستخدام البحث الخطي ). عندما تكون الدالة محدبة ، فإن جميع الحدود الدنيا المحلية هي أيضًا حدود دنيا عالمية، لذلك في هذه الحالة يمكن أن يتقارب الانحدار المتدرج إلى الحل العالمي. ${\displaystyle \gamma _{n}}$${\displaystyle F}$

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

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

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

نظرًا لأن استخدام حجم خطوة صغير جدًا من شأنه أن يبطئ التقارب، وأن الحجم الكبير جدًا من شأنه أن يؤدي إلى تجاوز الحد والتباعد، فإن إيجاد إعداد جيد لـ يمثل مشكلة عملية مهمة. كما دعا فيليب وولف إلى استخدام "اختيارات ذكية لاتجاه [النزول]" في الممارسة العملية. ^[10] في حين أن استخدام اتجاه ينحرف عن اتجاه النزول الأكثر انحدارًا قد يبدو غير بديهي، فإن الفكرة هي أن المنحدر الأصغر قد يتم تعويضه من خلال الحفاظ عليه على مسافة أطول بكثير. ${\displaystyle \gamma }$${\displaystyle \gamma }$${\displaystyle \gamma }$

للتفكير في هذا رياضيًا، ضع في اعتبارك الاتجاه وحجم الخطوة وفكر في التحديث الأكثر عمومية: ${\displaystyle \mathbf {p} _{n}}$${\displaystyle \gamma _{n}}$

${\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma _{n}\,\mathbf {p} _{n}}$.

إن إيجاد إعدادات جيدة لـ و يتطلب بعض التفكير. أولاً وقبل كل شيء، نود أن يشير اتجاه التحديث إلى أسفل. رياضيًا، نسمح للدلالة على الزاوية بين و ، وهذا يتطلب أن لكي نقول أكثر، نحتاج إلى مزيد من المعلومات حول دالة الهدف التي نقوم بتحسينها. تحت الافتراض الضعيف إلى حد ما وهو قابل للاشتقاق بشكل مستمر، يمكننا إثبات أن: ^[11]${\displaystyle \mathbf {p} _{n}}$${\displaystyle \gamma _{n}}$${\displaystyle \theta _{n}}$${\displaystyle -\nabla F(\mathbf {a_{n}} )}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \cos \theta _{n}>0.}$${\displaystyle F}$

${\displaystyle F(\mathbf {a} _{n+1})\leq F(\mathbf {a} _{n})-\gamma _{n}\|\nabla F(\mathbf {a} _{n})\|_{2}\|\mathbf {p} _{n}\|_{2}\left[\cos \theta _{n}-\max _{t\in [0,1]}{\frac {\|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}}{\|\nabla F(\mathbf {a} _{n})\|_{2}}}\right]}$

( 1 )

تشير هذه التفاوتات إلى أن المقدار الذي يمكننا التأكد به من تناقص الدالة يعتمد على التوازن بين الحدين الموجودين بين قوسين مربعين. يقيس الحد الأول الموجود بين قوسين مربعين الزاوية بين اتجاه الانحدار والتدرج السالب. يقيس الحد الثاني مدى سرعة تغير التدرج على طول اتجاه الانحدار. ${\displaystyle F}$

من حيث المبدأ، يمكن تحسين التباين ( 1 ) على واختيار حجم واتجاه الخطوة الأمثل. تكمن المشكلة في أن تقييم الحد الثاني بين قوسين مربعين يتطلب تقييم ، وتقييمات التدرج الإضافية مكلفة وغير مرغوب فيها بشكل عام. بعض الطرق للتغلب على هذه المشكلة هي: ${\displaystyle \mathbf {p} _{n}}$${\displaystyle \gamma _{n}}$${\displaystyle \nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})}$

• تنازل عن فوائد اتجاه النزول الذكي من خلال الضبط ، واستخدم البحث الخطي للعثور على حجم خطوة مناسب ، مثل الذي يلبي شروط وولف . هناك طريقة أكثر اقتصادية لاختيار معدلات التعلم وهي البحث الخطي العكسي ، وهي طريقة تحتوي على ضمانات نظرية جيدة ونتائج تجريبية. لاحظ أنه لا يلزم اختيار التدرج؛ أي اتجاه له حاصل ضرب داخلي موجب مع التدرج سيؤدي إلى تقليل قيمة الدالة (لقيمة صغيرة بدرجة كافية لـ ).${\displaystyle \mathbf {p} _{n}=\nabla F(\mathbf {a_{n}} )}$${\displaystyle \gamma _{n}}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \gamma _{n}}$
• بافتراض أن قابل للاشتقاق مرتين، استخدم هسيان الخاص به لتقدير ثم اختر و من خلال تحسين التباين ( 1 ).${\displaystyle F}$${\displaystyle \nabla ^{2}F}$${\displaystyle \|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}\approx \|t\gamma _{n}\nabla ^{2}F(\mathbf {a} _{n})\mathbf {p} _{n}\|.}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \gamma _{n}}$
• بافتراض أن هو Lipschitz ، استخدم ثابت Lipschitz الخاص به لتحديد ثم اختر و عن طريق تحسين المتباينة ( 1 ).${\displaystyle \nabla F}$${\displaystyle L}$${\displaystyle \|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}\leq Lt\gamma _{n}\|\mathbf {p} _{n}\|.}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \gamma _{n}}$
• قم ببناء نموذج مخصص لـ . ثم اختر و من خلال تحسين التفاوت ( 1 ).${\displaystyle \max _{t\in [0,1]}{\frac {\|\nabla F(\mathbf {a} _{n}-t\gamma _{n}\mathbf {p} _{n})-\nabla F(\mathbf {a} _{n})\|_{2}}{\|\nabla F(\mathbf {a} _{n})\|_{2}}}}$${\displaystyle F}$${\displaystyle \mathbf {p} _{n}}$${\displaystyle \gamma _{n}}$
• في ظل افتراضات أقوى بشأن الوظيفة مثل التحدب ، قد يكون من الممكن استخدام تقنيات أكثر تقدمًا.${\displaystyle F}$

عادةً، باتباع إحدى الوصفات المذكورة أعلاه، يمكن ضمان التقارب إلى الحد الأدنى المحلي. عندما تكون الدالة محدبة ، تكون جميع الحدود الدنيا المحلية أيضًا حدودًا دنيا عالمية، لذا في هذه الحالة يمكن أن يتقارب الانحدار المتدرج إلى الحل العالمي. ${\displaystyle F}$

يمكن استخدام الانحدار المتدرج لحل نظام المعادلات الخطية

${\displaystyle A\mathbf {x} -\mathbf {b} =0}$

تمت إعادة صياغتها كمشكلة تقليل تربيعية. إذا كانت مصفوفة النظام متماثلة حقيقية ومحددة بشكل موجب ، يتم تعريف دالة الهدف على أنها دالة تربيعية، مع تقليل ${\displaystyle A}$

${\displaystyle F(\mathbf {x} )=\mathbf {x} ^{T}A\mathbf {x} -2\mathbf {x} ^{T}\mathbf {b} ,}$

لهذا السبب.

${\displaystyle \nabla F(\mathbf {x} )=2(A\mathbf {x} -\mathbf {b} ).}$

بالنسبة لمصفوفة حقيقية عامة ، تحدد المربعات الصغرى الخطية${\displaystyle A}$

${\displaystyle F(\mathbf {x} )=\left\|A\mathbf {x} -\mathbf {b} \right\|^{2}.}$

في المربعات الصغرى الخطية التقليدية للأعداد الحقيقية ، يتم استخدام القاعدة الإقليدية ، وفي هذه الحالة ${\displaystyle A}$${\displaystyle \mathbf {b} }$

${\displaystyle \nabla F(\mathbf {x} )=2A^{T}(A\mathbf {x} -\mathbf {b} ).}$

يمكن إجراء تقليل البحث الخطي ، وإيجاد حجم الخطوة الأمثل محليًا في كل تكرار، تحليليًا للوظائف التربيعية، ومن المعروف وجود صيغ صريحة للحجم الأمثل محليًا. ^{[6] [13]}${\displaystyle \gamma }$${\displaystyle \gamma }$

على سبيل المثال، بالنسبة للمصفوفة الحقيقية المتماثلة والمحددة بشكل إيجابي ، يمكن أن تكون الخوارزمية البسيطة على النحو التالي، ^[6]${\displaystyle A}$

${\displaystyle {\begin{aligned}&{\text{repeat in the loop:}}\\&\qquad \mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}}$

لتجنب الضرب مرتين في كل تكرار، نلاحظ أن يعني ، مما يعطي الخوارزمية التقليدية، ^[14]${\displaystyle A}$${\displaystyle \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} }$${\displaystyle \mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar} }$

${\displaystyle {\begin{aligned}&\mathbf {r} :=\mathbf {b} -\mathbf {Ax} \\&{\text{repeat in the loop:}}\\&\qquad \gamma :={\mathbf {r} ^{\mathsf {T}}\mathbf {r} }/{\mathbf {r} ^{\mathsf {T}}\mathbf {Ar} }\\&\qquad \mathbf {x} :=\mathbf {x} +\gamma \mathbf {r} \\&\qquad {\hbox{if }}\mathbf {r} ^{\mathsf {T}}\mathbf {r} {\text{ is sufficiently small, then exit loop}}\\&\qquad \mathbf {r} :=\mathbf {r} -\gamma \mathbf {Ar} \\&{\text{end repeat loop}}\\&{\text{return }}\mathbf {x} {\text{ as the result}}\end{aligned}}}$

نادرًا ما تُستخدم هذه الطريقة لحل المعادلات الخطية، حيث تُعَد طريقة التدرج المترافق واحدة من أكثر البدائل شيوعًا. عادةً ما يكون عدد تكرارات الانحدار المتدرج متناسبًا مع رقم الحالة الطيفية لمصفوفة النظام (نسبة القيم الذاتية القصوى إلى الدنيا لـ ) ، بينما يتم تحديد تقارب طريقة التدرج المترافق عادةً من خلال الجذر التربيعي لرقم الحالة، أي أسرع بكثير. يمكن أن تستفيد كلتا الطريقتين من التكييف المسبق ، حيث قد يتطلب الانحدار المتدرج افتراضات أقل على المُكيف المسبق. ^[14]${\displaystyle \kappa (A)}$${\displaystyle A}$${\displaystyle A^{T}A}$

يمكن أيضًا استخدام الانحدار المتدرج لحل نظام من المعادلات غير الخطية . يوجد أدناه مثال يوضح كيفية استخدام الانحدار المتدرج لحل ثلاثة متغيرات غير معروفة، x ₁ و x ₂ و x _3. يوضح هذا المثال تكرارًا واحدًا للانحدار المتدرج.

ضع في اعتبارك النظام غير الخطي للمعادلات

${\displaystyle {\begin{cases}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}=0\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1=0\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}=0\end{cases}}}$

دعونا نقدم الوظيفة المرتبطة

${\displaystyle G(\mathbf {x} )={\begin{bmatrix}3x_{1}-\cos(x_{2}x_{3})-{\tfrac {3}{2}}\\4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\\\exp(-x_{1}x_{2})+20x_{3}+{\tfrac {10\pi -3}{3}}\\\end{bmatrix}},}$

أين

${\displaystyle \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\end{bmatrix}}.}$

يمكننا الآن تعريف دالة الهدف

${\displaystyle {\begin{aligned}F(\mathbf {x} )&={\frac {1}{2}}G^{\mathrm {T} }(\mathbf {x} )G(\mathbf {x} )\\&={\frac {1}{2}}\left[\left(3x_{1}-\cos(x_{2}x_{3})-{\frac {3}{2}}\right)^{2}+\left(4x_{1}^{2}-625x_{2}^{2}+2x_{2}-1\right)^{2}+\right.\\&{}\qquad \left.\left(\exp(-x_{1}x_{2})+20x_{3}+{\frac {10\pi -3}{3}}\right)^{2}\right],\end{aligned}}}$

والتي سنحاول التقليل منها. كتخمين أولي، دعنا نستخدم

${\displaystyle \mathbf {x} ^{(0)}=\mathbf {0} ={\begin{bmatrix}0\\0\\0\\\end{bmatrix}}.}$

نحن نعلم ذلك

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\gamma _{0}\nabla F(\mathbf {0} )=\mathbf {0} -\gamma _{0}J_{G}(\mathbf {0} )^{\mathrm {T} }G(\mathbf {0} ),}$

حيث يتم إعطاء مصفوفة جاكوبيان بواسطة ${\displaystyle J_{G}}$

${\displaystyle J_{G}(\mathbf {x} )={\begin{bmatrix}3&\sin(x_{2}x_{3})x_{3}&\sin(x_{2}x_{3})x_{2}\\8x_{1}&-1250x_{2}+2&0\\-x_{2}\exp {(-x_{1}x_{2})}&-x_{1}\exp(-x_{1}x_{2})&20\\\end{bmatrix}}.}$

نحن نحسب:

${\displaystyle J_{G}(\mathbf {0} )={\begin{bmatrix}3&0&0\\0&2&0\\0&0&20\end{bmatrix}},\qquad G(\mathbf {0} )={\begin{bmatrix}-2.5\\-1\\10.472\end{bmatrix}}.}$

هكذا

${\displaystyle \mathbf {x} ^{(1)}=\mathbf {0} -\gamma _{0}{\begin{bmatrix}-7.5\\-2\\209.44\end{bmatrix}},}$

و

${\displaystyle F(\mathbf {0} )=0.5\left((-2.5)^{2}+(-1)^{2}+(10.472)^{2}\right)=58.456.}$

الآن، يجب إيجاد حل مناسب بحيث ${\displaystyle \gamma _{0}}$

${\displaystyle F\left(\mathbf {x} ^{(1)}\right)\leq F\left(\mathbf {x} ^{(0)}\right)=F(\mathbf {0} ).}$

يمكن القيام بذلك باستخدام أي من خوارزميات البحث عن الخطوط المتنوعة . قد يخمن المرء أيضًا ببساطة أي الخطوط تعطي ${\displaystyle \gamma _{0}=0.001,}$

${\displaystyle \mathbf {x} ^{(1)}={\begin{bmatrix}0.0075\\0.002\\-0.20944\\\end{bmatrix}}.}$

تقييم دالة الهدف عند هذه القيمة، يعطي

${\displaystyle F\left(\mathbf {x} ^{(1)}\right)=0.5\left((-2.48)^{2}+(-1.00)^{2}+(6.28)^{2}\right)=23.306.}$

الانخفاض من قيمة الخطوة التالية ${\displaystyle F(\mathbf {0} )=58.456}$

${\displaystyle F\left(\mathbf {x} ^{(1)}\right)=23.306}$

هو انخفاض كبير في دالة الهدف. وسوف تؤدي الخطوات الإضافية إلى تقليل قيمتها بشكل أكبر حتى يتم العثور على حل تقريبي للنظام.

يعمل الانحدار المتدرج في المساحات ذات أي عدد من الأبعاد، حتى في المساحات ذات الأبعاد اللانهائية. في الحالة الأخيرة، تكون مساحة البحث عادةً مساحة دالة ، ويتم حساب مشتق فريشيه للدالة المراد تقليلها لتحديد اتجاه الانحدار. ^[7]

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

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

يمكن تعديل نزول التدرج من خلال الزخم ^[15] ( Nesterov وPolyak ^[16] وFrank-Wolfe ^[17] ) ومعلمات الكرة الثقيلة (المتوسطات المتحركة الأسيّة ^[18] والزخم الإيجابي السلبي ^[19] ). الأمثلة الرئيسية لمثل هذه المحسنات هي Adam وDiffGrad وYogi وAdaBelief وما إلى ذلك.

يمكن أن تكون الطرق القائمة على طريقة نيوتن وعكس الهسيان باستخدام تقنيات التدرج المترافق بدائل أفضل. ^{[20] [21]} بشكل عام، تتقارب مثل هذه الطرق في عدد أقل من التكرارات، ولكن تكلفة كل تكرار أعلى. ومن الأمثلة على ذلك طريقة BFGS التي تتكون من حساب مصفوفة في كل خطوة يتم بها ضرب متجه التدرج للدخول في اتجاه "أفضل"، جنبًا إلى جنب مع خوارزمية بحث خطية أكثر تطورًا ، للعثور على "أفضل" قيمة لـ بالنسبة للمشكلات الكبيرة للغاية، حيث تهيمن مشكلات ذاكرة الكمبيوتر، يجب استخدام طريقة ذاكرة محدودة مثل L-BFGS بدلاً من BFGS أو الانحدار الأكثر حدة. ${\displaystyle \gamma .}$

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

يمكن النظر إلى الانحدار المتدرج باعتباره تطبيقًا لطريقة أويلر لحل المعادلات التفاضلية العادية على تدفق التدرج . في المقابل، يمكن اشتقاق هذه المعادلة كمتحكم مثالي ^[22] لنظام التحكم مع إعطاء شكل ردود الفعل . ${\displaystyle x'(t)=-\nabla f(x(t))}$${\displaystyle x'(t)=u(t)}$${\displaystyle u(t)}$${\displaystyle u(t)=-\nabla f(x(t))}$

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

اقترح يوري نيستيروف ^[23] تعديلاً بسيطًا يتيح تقاربًا أسرع للمشكلات المحدبة وتم تعميمه منذ ذلك الحين. بالنسبة للمشكلات السلسة غير المقيدة، تسمى الطريقة طريقة التدرج السريع (FGM) أو طريقة التدرج المتسارع (AGM). على وجه التحديد، إذا كانت الدالة القابلة للتفاضل محدبة وهي Lipschitz ، ولم يُفترض أنها محدبة بشدة ، فإن الخطأ في القيمة الموضوعية الناتجة عن طريقة الانحدار التدرجي في كل خطوة سيكون محدودًا بـ . باستخدام تقنية تسريع نيستيروف، ينخفض ​​الخطأ عند . ^{[24] [25]} ومن المعروف أن معدل انخفاض دالة التكلفة هو الأمثل لطرق التحسين من الدرجة الأولى. ومع ذلك، هناك فرصة لتحسين الخوارزمية عن طريق تقليل العامل الثابت. تقلل طريقة التدرج المُحسَّن (OGM) ^[26] ذلك الثابت بعامل اثنين وهي طريقة مثالية من الدرجة الأولى للمشكلات واسعة النطاق. ^[27]${\displaystyle F}$${\displaystyle \nabla F}$${\displaystyle F}$${\displaystyle k}$ ${\textstyle {\mathcal {O}}\left({\tfrac {1}{k}}\right)}$${\textstyle {\mathcal {O}}\left({\tfrac {1}{k^{2}}}\right)}$${\displaystyle {\mathcal {O}}\left({k^{-2}}\right)}$

بالنسبة للمشكلات المقيدة أو غير السلسة، يطلق على FGM لنستيروف اسم طريقة التدرج القريب السريع (FPGM)، وهي عبارة عن تسريع لطريقة التدرج القريب .

في محاولة لكسر نمط متعرج من الانحدار التدريجي، تستخدم طريقة الزخم أو الكرة الثقيلة مصطلح الزخم على غرار كرة ثقيلة تنزلق على سطح قيم الدالة التي يتم تقليلها، ^[6] أو لحركة الكتلة في ديناميكيات نيوتن عبر وسط لزج في مجال قوة محافظ . ^[28] يتذكر الانحدار التدريجي مع الزخم تحديث الحل في كل تكرار، ويحدد التحديث التالي كتركيبة خطية من التدرج والتحديث السابق. بالنسبة للتقليل التربيعي غير المقيد، يكون حد معدل التقارب النظري لطريقة الكرة الثقيلة مقاربًا لحدود طريقة التدرج المترافق الأمثل . ^[6]

تُستخدم هذه التقنية في الانحدار التدرجي العشوائي وكامتداد لخوارزميات الانتشار الخلفي المستخدمة لتدريب الشبكات العصبية الاصطناعية . ^{[29] [30]} وفي اتجاه التحديث، يضيف الانحدار التدرجي العشوائي خاصية عشوائية. ويمكن استخدام الأوزان لحساب المشتقات.

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

الانحدار المتدرج هو حالة خاصة من الانحدار المرآوي باستخدام المسافة الإقليدية التربيعية كتباعد بريجمان المعطى . ^[32]

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

• بويد، ستيفن ؛ فاندنبرغ، ليفين (2004). "التقليل غير المقيد" (PDF) . التحسين المحدب . نيويورك: مطبعة جامعة كامبريدج. ص 457-520. ISBN 0-521-83378-7.
• تشونج، إدوين كيه بي؛ زاك، ستانيسلاف إتش. (2013). "طرق التدرج". مقدمة في التحسين (الطبعة الرابعة). هوبوكين: وايلي. ص 131-160. رقم ISBN 978-1-118-27901-4.
• Himmelblau, David M. (1972). "Unconstrained Minimization Procedures Using Derivatives". Applied Nonlinear Programming . New York: McGraw-Hill. pp. 63–132. ISBN 0-07-028921-2.

• استخدام الانحدار التدرجي في C++ وBoost وUblas للانحدار الخطي
• سلسلة من مقاطع فيديو أكاديمية خان تناقش الصعود التدريجي
• كتاب تعليمي على الإنترنت حول الانحدار التدريجي في سياق الشبكة العصبية العميقة
• تم أرشفته في Ghostarchive وWayback Machine: "Gradient Descent, How Neural Networks Learn". 3Blue1Brown . 16 أكتوبر 2017 – عبر YouTube .
• دليل نظريات التقارب لطرق التدرج (العشوائية)