الانحدار التدريجي

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

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

يُعدّ التدرج الهبوطي مفيدًا بشكل خاص في مجال التعلم الآلي والذكاء الاصطناعي لتقليل دالة التكلفة أو الخسارة. ^{[ 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} ,ie,-\nabla f(\mathbf {a} )}$ويترتب على ذلك أنه إذا

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

لحجم خطوة صغير بما فيه الكفاية أو معدل تعلم صغير بما فيه الكفاية${\displaystyle \eta \in \mathbb {R} _{+}}$، ثم ${\displaystyle f(\mathbf {a_{n}} )\geq f(\mathbf {a_{n+1}} )}$بعبارة أخرى، المصطلح${\displaystyle \eta \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}-\eta _{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 \eta }$يُسمح بتغييره في كل تكرار.

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

${\displaystyle \eta _{n}={\frac {\left|\left(\mathbf {x} _{n}-\mathbf {x} _{n-1}\right)^{\top }\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 \eta _{n}}$تحقيق شروط وولف (التي يمكن إيجادها باستخدام البحث الخطي ). عندما تكون الدالة${\displaystyle f}$إذا كانت محدبة ، فإن جميع القيم الصغرى المحلية هي أيضًا قيم صغرى عالمية، لذلك في هذه الحالة يمكن أن يتقارب انحدار التدرج إلى الحل العالمي.

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

تشبيه لفهم انحدار التدرج

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

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

اختيار حجم الخطوة واتجاه النزول

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

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

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

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

${\displaystyle f(\mathbf {a} _{n+1})\leq f(\mathbf {a} _{n})-\eta _{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\eta _{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 \eta _{n}}$لاختيار حجم الخطوة الأمثل واتجاهها. تكمن المشكلة في أن حساب الحد الثاني بين قوسين مربعين يتطلب حساب${\displaystyle \nabla f(\mathbf {a} _{n}-t\eta _{n}\mathbf {p} _{n})}$وتُعدّ عمليات حساب التدرج الإضافية مكلفة وغير مرغوب فيها عمومًا. ومن بين الحلول الممكنة لهذه المشكلة ما يلي:

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

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

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

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

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

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

لهذا السبب.

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}&{\text{repeat in the loop:}}\\&\qquad \mathbf {r}$ :=\mathbf {b} -\mathbf {Ax} \\&\qquad \eta  :={\mathbf {r} ^{\top }\mathbf {r} }/{\mathbf {r} ^{\top }\mathbf {Ar} }\\&\qquad \mathbf {x}  :=\mathbf {x} +\eta \mathbf {r} \\&\qquad {\hbox{إذا كانت }}\mathbf {r} ^{\top }\mathbf {r} {\text{ صغيرة بما يكفي، فاخرج من الحلقة}}\\&{\text{أكمل حلقة التكرار}}\\&{\text{أرجع }}\mathbf {x} {\text{ كنتيجة}}\end{aligned}}}

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

${\displaystyle {\begin{aligned}&\mathbf {r}$ :=\mathbf {b} -\mathbf {Ax} \\&{\text{كرر في الحلقة:}}\\&\qquad \eta  :={\mathbf {r} ^{\top }\mathbf {r} }/{\mathbf {r} ^{\top }\mathbf {Ar} }\\&\qquad \mathbf {x}  :=\mathbf {x} +\eta \mathbf {r} \\&\qquad {\hbox{إذا كانت }}\mathbf {r} ^{\top }\mathbf {r} {\text{ صغيرة بما يكفي، فاخرج من الحلقة}}\\&\qquad \mathbf {r}  :=\mathbf {r} -\eta \mathbf {Ar} \\&{\text{نهاية حلقة التكرار}}\\&{\text{إرجاع }}\mathbf {x} {\text{ كنتيجة}}\end{aligned}}}

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

يمكن استخدام خوارزمية التدرج الهبوطي لحل نظام من المعادلات غير الخطية . فيما يلي مثال يوضح كيفية استخدام هذه الخوارزمية لإيجاد قيم ثلاثة متغيرات مجهولة، _x1 و x2 _و x3 . يوضح _هذا المثال دورة واحدة من خوارزمية التدرج الهبوطي.

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

${\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^{\top }(\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} -\eta _{0}\nabla f(\mathbf {0} )=\mathbf {0} -\eta _{0}J_{G}(\mathbf {0} )^{\top }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} -\eta _{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 \eta _{0}}$يجب إيجادها بحيث

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

يمكن القيام بذلك باستخدام أي من خوارزميات البحث الخطي المتنوعة . وقد يقوم المرء أيضاً بالتخمين ببساطة.${\displaystyle \eta _{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 ]}

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

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

يمكن تعديل خوارزمية التدرج الهبوطي باستخدام الزخم ^{[ 16 ]} ( نيستيروف ، بولياك ^{[ 17 ]} ، وفرانك-وولف ^{[ 18 ]} ) ومعاملات الكرة الثقيلة (المتوسطات المتحركة الأسية ^{[ 19 ]} والزخم الموجب-السالب ^{[ 20 ]} ). ومن أبرز الأمثلة على هذه الخوارزميات المُحسِّنة: آدم، وديفغراد، ويوجي، وآدا بيليف، وغيرها.

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

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

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

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

يمكن توسيع خوارزمية التدرج الهبوطي لتشمل التعامل مع القيود عن طريق تضمين إسقاط على مجموعة القيود. لا تكون هذه الطريقة مجدية إلا عندما يكون حساب الإسقاط فعالاً على الحاسوب. في ظل افتراضات مناسبة، تتقارب هذه الطريقة. تُعد هذه الطريقة حالة خاصة من خوارزمية التقديم-التراجع للتضمينات الرتيبة (والتي تشمل البرمجة المحدبة والمتباينات التغيرية ). ^{[ 32 ]}

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

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

• تدفق يانغ-ميلز
• تدفق يانغ-ميلز-هيغز
• تدفق سيبرغ-ويتن

• بويد، ستيفن ؛ فاندنبيرغ، ليفين (2004). "التقليل غير المقيد" (ملف PDF) . التحسين المحدب . نيويورك: مطبعة جامعة كامبريدج. الصفحات 457-520 . ISBN  0-521-83378-7.
• تشونغ، إدوين كيه بي؛ زاك، ستانيسلاف إتش. (2013). "طرق التدرج" . مقدمة في التحسين (  الطبعة الرابعة). هوبوكين: وايلي. ص 131-160 . ISBN  978-1-118-27901-4.
• هيملبلاو، ديفيد م. (1972). "إجراءات التصغير غير المقيدة باستخدام المشتقات". البرمجة غير الخطية التطبيقية . نيويورك: ماكجرو هيل. ص 63-132 . ISBN  0-07-028921-2.

• استخدام خوارزمية التدرج الهبوطي في لغة C++، وBoost، وUBlas للانحدار الخطي
• تتناول سلسلة من فيديوهات أكاديمية خان موضوع الصعود التدريجي
• كتاب إلكتروني يشرح خوارزمية التدرج الهبوطي في سياق الشبكات العصبية العميقة
• مؤرشف في أرشيف الأشباحوآلة Wayback" الانحدار التدريجي، كيف تتعلم الشبكات العصبية" . 3Blue1Brown . 16 أكتوبر 2017 - عبر يوتيوب .
• غاريغوس، غيوم؛ غاور، روبرت م. (2023). "دليل نظريات التقارب لطرق التدرج (العشوائية)". arXiv : 2301.11235 [ math.OC ].