الهبوط التدرجي العشوائي

كما ذُكر سابقًا، فإنّ خوارزمية التدرج العشوائي الكلاسيكية حساسة عمومًا لمعدل التعلّم η . يتطلب التقارب السريع معدلات تعلّم عالية، ولكن هذا قد يؤدي إلى عدم استقرار عددي. يمكن حلّ هذه المشكلة إلى حد كبير ^{[ 29 ]} من خلال النظر في التحديثات الضمنية، حيث يتم تقييم التدرج العشوائي في التكرار التالي بدلًا من التكرار الحالي. $${\displaystyle w^{\text{new}}:=w^{\text{old}}-\eta \,\nabla Q_{i}(w^{\text{new}}).}$$

هذه المعادلة ضمنية لأن${\displaystyle w^{\text{new}}}$يظهر على جانبي المعادلة. وهو شكل عشوائي من طريقة التدرج التقريبي، حيث يمكن كتابة التحديث أيضًا على النحو التالي: $${\displaystyle w^{\text{new}}:=\arg \min _{w}\left\{Q_{i}(w)+{\frac {1}{2\eta }}\left\|w-w^{\text{old}}\right\|^{2}\right\}.}$$

على سبيل المثال، ضع في اعتبارك طريقة المربعات الصغرى مع الميزات${\displaystyle x_{1},\ldots ,x_{n}\in \mathbb {R} ^{p}}$والملاحظات ${\displaystyle y_{1},\ldots ,y_{n}\in \mathbb {R} }$نرغب في حل ما يلي: $${\displaystyle \min _{w}\sum _{j=1}^{n}\left(y_{j}-x_{j}'w\right)^{2},}$$ أين${\displaystyle x_{j}'w=x_{j1}w_{1}+x_{j,2}w_{2}+...+x_{j,p}w_{p}}$ يشير إلى الناتج الداخلي. لاحظ أن${\displaystyle x}$يمكن أن يكون العنصر الأول هو "1" ليتضمن نقطة تقاطع. تتم عملية التدرج العشوائي الكلاسيكي على النحو التالي: $${\displaystyle w^{\text{new}}=w^{\text{old}}+\eta \left(y_{i}-x_{i}'w^{\text{old}}\right)x_{i}}$$

أين${\displaystyle i}$يتم أخذ عينة بشكل منتظم بين 1 و${\displaystyle n}$على الرغم من أن التقارب النظري لهذه العملية يحدث في ظل افتراضات معتدلة نسبيًا، إلا أن العملية قد تكون غير مستقرة تمامًا في الواقع العملي. على وجه الخصوص، عندما${\displaystyle \eta }$تم تحديدها بشكل خاطئ بحيث${\displaystyle I-\eta x_{i}x_{i}'}$إذا كانت للمصفوفة قيم ذاتية مطلقة كبيرة باحتمالية عالية، فقد تتباعد العملية عدديًا خلال بضع تكرارات. في المقابل، يمكن حل خوارزمية التدرج العشوائي الضمني (ISGD) بصيغة مغلقة كما يلي: $${\displaystyle w^{\text{new}}=w^{\text{old}}+{\frac {\eta }{1+\eta \left\|x_{i}\right\|^{2}}}\left(y_{i}-x_{i}'w^{\text{old}}\right)x_{i}.}$$

ستظل هذه العملية مستقرة عدديًا بشكل شبه كامل للجميع${\displaystyle \eta }$بما أن معدل التعلم أصبح الآن مُعَيَّراً. هذه المقارنة بين التدرج العشوائي الكلاسيكي والضمني في مسألة المربعات الصغرى تُشبه إلى حد كبير المقارنة بين مرشح المربعات الصغرى المتوسطة (LMS) ومرشح المربعات الصغرى المتوسطة المُعَيَّر (NLMS) .

على الرغم من أن الحل المغلق لمسألة ISGD لا يمكن تحقيقه إلا باستخدام طريقة المربعات الصغرى، إلا أنه يمكن تطبيق هذه الطريقة بكفاءة في نطاق واسع من النماذج. على وجه التحديد، لنفترض أن${\displaystyle Q_{i}(w)}$يعتمد على${\displaystyle w}$فقط من خلال توليفة خطية مع الميزات${\displaystyle x_{i}}$حتى نتمكن من الكتابة${\displaystyle \nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i}}$، أين${\displaystyle q()\in \mathbb {R} }$قد يعتمد ذلك على${\displaystyle x_{i},y_{i}}$كذلك، ولكن ليس على${\displaystyle w}$باستثناء من خلال${\displaystyle x_{i}'w}$تخضع طريقة المربعات الصغرى لهذه القاعدة، وكذلك الانحدار اللوجستي ، ومعظم النماذج الخطية المعممة . على سبيل المثال، في طريقة المربعات الصغرى،${\displaystyle q(x_{i}'w)=y_{i}-x_{i}'w}$وفي الانحدار اللوجستي${\displaystyle q(x_{i}'w)=y_{i}-S(x_{i}'w)}$، أين${\displaystyle S(u)=e^{u}/(1+e^{u})}$هي الدالة اللوجستية . في انحدار بواسون ،${\displaystyle q(x_{i}'w)=y_{i}-e^{x_{i}'w}}$وهكذا دواليك.

في مثل هذه الحالات، يتم تطبيق ISGD ببساطة على النحو التالي. لنفترض${\displaystyle f(\xi )=\eta q(x_{i}'w^{\text{old}}+\xi \|x_{i}\|^{2})}$، أين${\displaystyle \xi }$إذا كان عدديًا، فإن ISGD يعادل: $${\displaystyle w^{\text{new}}=w^{\text{old}}+\xi ^{\ast }x_{i},~{\text{where}}~\xi ^{\ast }=f(\xi ^{\ast }).}$$

عامل القياس${\displaystyle \xi ^{\ast }\in \mathbb {R} }$يمكن إيجادها من خلال طريقة التنصيف، حيث أن الدالة في معظم النماذج المنتظمة، مثل النماذج الخطية المعممة المذكورة سابقًا،${\displaystyle q()}$يتناقص، وبالتالي تتناقص حدود البحث لـ${\displaystyle \xi ^{\ast }}$نكون${\displaystyle [\min(0,f(0)),\max(0,f(0))]}$.

تشمل المقترحات الأخرى طريقة الزخم أو طريقة الكرة الثقيلة ، والتي ظهرت في سياق التعلم الآلي في ورقة روميلهارت وهينتون وويليامز حول التعلم بالانتشار العكسي ^{[ 30 ]} ، واستعارت الفكرة من مقالة عالم الرياضيات السوفيتي بوريس بولياك عام 1964 حول حل المعادلات الوظيفية. [ 31 ^{] يحتفظ التدرج} العشوائي مع الزخم بالتحديث Δw في كل تكرار، ويحدد التحديث التالي كمزيج خطي من التدرج والتحديث السابق: ^{[ 32 ] [ 33 ]}$${\displaystyle \Delta w:=\alpha \Delta w-\eta \,\nabla Q_{i}(w)}$$$${\displaystyle w:=w+\Delta w}$$ وهذا يؤدي إلى: $${\displaystyle w:=w-\eta \,\nabla Q_{i}(w)+\alpha \Delta w}$$

حيث المعامل${\displaystyle w}$مما يقلل${\displaystyle Q(w)}$سيتم تقديره ،${\displaystyle \eta }$حجم الخطوة (يُسمى أحيانًا معدل التعلم في التعلم الآلي) و${\displaystyle \alpha }$هو عامل اضمحلال أسي بين 0 و 1 يحدد المساهمة النسبية للتدرج الحالي والتدرجات السابقة في تغيير الوزن.

يستمد اسم الزخم من تشبيهه بالزخم في الفيزياء: متجه الوزن${\displaystyle w}$يُنظر إلى الزخم، باعتباره جسيمًا يتحرك عبر فضاء المعاملات، ^{[ 30 ]} ويكتسب تسارعًا من تدرج دالة الخسارة (" القوة "). وخلافًا لخوارزمية التدرج العشوائي الكلاسيكية، فإنه يميل إلى الاستمرار في التحرك في نفس الاتجاه، مما يمنع التذبذبات. وقد استخدم علماء الحاسوب الزخم بنجاح في تدريب الشبكات العصبية الاصطناعية لعدة عقود. ^{[ 34 ]} وترتبط طريقة الزخم ارتباطًا وثيقًا بديناميكيات لانجفين المخمدة ، ويمكن دمجها مع التلدين المحاكي . ^{[ 35 ]}

في منتصف الثمانينيات، تم تعديل الطريقة بواسطة يوري نيستروف لاستخدام التدرج المتوقع عند النقطة التالية، وقد تم استخدام ما يسمى بتدرج نيستروف المتسارع الناتج في بعض الأحيان في التعلم الآلي في العقد الثاني من القرن الحادي والعشرين. ^{[ 36 ]}

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

$${\displaystyle {\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}.}$$عند إجراء عملية التحسين، يحل متجه المعلمات المتوسط ​​هذا محل w .

خوارزمية AdaGrad (اختصارًا لخوارزمية التدرج التكيفي) هي خوارزمية معدلة للتدرج العشوائي مع معدل تعلم لكل مُعامل ، نُشرت لأول مرة عام 2011. ^{[ 38 ]} ببساطة، تعمل هذه الخوارزمية على زيادة معدل التعلم للمُعاملات الأقل كثافة ، وتقليله للمُعاملات الأكثر كثافة. غالبًا ما تُحسّن هذه الاستراتيجية أداء التقارب مقارنةً بالتدرج العشوائي القياسي في الحالات التي تكون فيها البيانات قليلة، وتكون المُعاملات القليلة أكثر دلالة. من أمثلة هذه التطبيقات معالجة اللغة الطبيعية والتعرف على الصور. ^{[ 38 ]}

لا يزال لديه معدل تعلم أساسي η ، ولكن يتم ضرب هذا المعدل بعناصر المتجه { Gj _{, j} } الذي يمثل قطر مصفوفة الضرب الخارجي _.

$${\displaystyle G=\sum _{\tau =1}^{t}g_{\tau }g_{\tau }^{\mathsf {T}}}$$

أين${\displaystyle g_{\tau }=\nabla Q_{i}(w)}$، وهو التدرج، عند التكرار τ . ويُعطى القطر بواسطة

$${\displaystyle G_{j,j}=\sum _{\tau =1}^{t}g_{\tau ,j}^{2}.}$$يخزن هذا المتجه أساسًا مجموعًا تاريخيًا لمربعات التدرج حسب البُعد، ويتم تحديثه بعد كل تكرار. صيغة التحديث الآن هي ^{[ أ ]}$${\displaystyle w:=w-\eta \,\mathrm {diag} (G)^{-{\frac {1}{2}}}\odot g}$$ أو، مكتوبة كتحديثات لكل معلمة، $${\displaystyle w_{j}:=w_{j}-{\frac {\eta }{\sqrt {G_{j,j}}}}g_{j}.}$$ ينتج عن كل { G _{( i , i )} } عامل قياس لمعدل التعلم ينطبق على مُعامل واحد w _i . بما أن المقام في هذا العامل،${\textstyle {\sqrt {G_{i}}}={\sqrt {\sum _{\tau =1}^{t}g_{\tau }^{2}}}}$إذا كانت ℓ ₂ هي المعيار للمشتقات السابقة، فإن تحديثات المعلمات المتطرفة تتلاشى، بينما تحصل المعلمات التي تحصل على تحديثات قليلة أو صغيرة على معدلات تعلم أعلى. ^{[ 34 ]}

على الرغم من أن AdaGrad مصممة للمسائل المحدبة ، إلا أنها طُبقت بنجاح على التحسين غير المحدب. ^{[ 39 ]}

RMSProp (اختصارًا لـ Root Mean Square Propagation) هي طريقة ابتكرها جيمس مارتنز وإيليا سوتسكيفر عام 2012 ، وكانا حينها طالبين في برنامج الدكتوراه ضمن مجموعة جيفري هينتون. في هذه الطريقة، يتم تعديل معدل التعلم ، كما هو الحال في Adagrad، لكل مُعامل على حدة. وتتلخص الفكرة في قسمة معدل التعلم لوزن معين على المتوسط ​​المتحرك لقيم التدرجات الأخيرة لهذا الوزن. ^{[ 40 ]} ومن اللافت للنظر أنها لم تُنشر في مقال، بل وُصفت فقط في محاضرة على منصة Coursera . ^{[ 41 ] [ 42 ]}

لذا، يتم أولاً حساب المتوسط ​​المتحرك بدلالة متوسط ​​المربعات،

$${\displaystyle v(w,t):=\gamma v(w,t-1)+\left(1-\gamma \right)\left(\nabla Q_{i}(w)\right)^{2}}$$

أين،${\displaystyle \gamma }$يُعد عامل النسيان. تم استعارة مفهوم تخزين التدرج التاريخي كمجموع مربعات من خوارزمية أداغراد، ولكن تم إدخال "النسيان" لحل مشكلة تناقص معدلات التعلم في أداغراد في المسائل غير المحدبة عن طريق تقليل تأثير البيانات القديمة تدريجياً.

ويتم تحديث المعلمات على النحو التالي:

$${\displaystyle w:=w-{\frac {\eta }{\sqrt {v(w,t)}}}\nabla Q_{i}(w)}$$

أظهرت خوارزمية RMSProp قدرة جيدة على التكيف مع معدل التعلم في تطبيقات مختلفة. ويمكن اعتبارها تعميمًا لخوارزمية Rprop ، وهي قادرة على العمل مع الدفعات الصغيرة أيضًا، على عكس اقتصارها على الدفعات الكاملة فقط. ^{[ 40 ]}

آدم ^{[ 43 ]} (اختصارًا لـ Adaptive Moment Estimation) هو تحديث لعام 2014 لمُحسِّن RMSProp ، يجمعه مع الميزة الرئيسية لطريقة الزخم . ^{[ 44 ]} في خوارزمية التحسين هذه، تُستخدم المتوسطات المتحركة مع النسيان الأسي لكل من التدرجات والعزوم الثانية للتدرجات. مع الأخذ في الاعتبار المعلمات${\displaystyle w^{(t)}}$ودالة الخسارة${\displaystyle L^{(t)}}$، أين${\displaystyle t}$يُفهرس تكرار التدريب الحالي (المفهرس عند${\displaystyle 1}$يتم تحديد تحديث معلمات آدم من خلال:

$${\displaystyle m_{w}^{(t)}:=\beta _{1}m_{w}^{(t-1)}+\left(1-\beta _{1}\right)\nabla _{w}L^{(t-1)}}$$$${\displaystyle v_{w}^{(t)}:=\beta _{2}v_{w}^{(t-1)}+\left(1-\beta _{2}\right)\left(\nabla _{w}L^{(t-1)}\right)^{2}}$$

$${\displaystyle {\hat {m}}_{w}^{(t)}={\frac {m_{w}^{(t)}}{1-\beta _{1}^{t}}}}$$$${\displaystyle {\hat {v}}_{w}^{(t)}={\frac {v_{w}^{(t)}}{1-\beta _{2}^{t}}}}$$

$${\displaystyle w^{(t)}:=w^{(t-1)}-\eta {\frac {{\hat {m}}_{w}^{(t)}}{{\sqrt {{\hat {v}}_{w}^{(t)}}}+\varepsilon }}}$$ أين${\displaystyle \varepsilon }$هو عدد قياسي صغير (مثل${\displaystyle 10^{-8}}$) تُستخدم لمنع القسمة على صفر، و${\displaystyle \beta _{1}}$(مثلاً 0.9) و${\displaystyle \beta _{2}}$(على سبيل المثال، 0.999) هي عوامل النسيان للتدرجات والعزوم الثانية للتدرجات، على التوالي. يتم التربيع وإحداث الجذر التربيعي عنصرًا عنصرًا.

باعتبارها المتوسطات المتحركة الأسية للتدرج${\displaystyle m_{w}^{(t)}}$والتدرج التربيعي${\displaystyle v_{w}^{(t)}}$إذا تم تهيئة المصفوفة بمتجه من الأصفار، فسيكون هناك انحياز نحو الصفر في التكرارات التدريبية الأولى. عامل${\displaystyle {\tfrac {1}{1-\beta _{1/2}^{t}}}}$يتم إدخالها لتعويض هذا التحيز والحصول على تقديرات أفضل${\displaystyle {\hat {m}}_{w}^{(t)}}$و${\displaystyle {\hat {v}}_{w}^{(t)}}$.

كان البرهان الأولي الذي أثبت تقارب خوارزمية آدم غير مكتمل، وقد كشف التحليل اللاحق أن آدم لا تتقارب لجميع الأهداف المحدبة. ^{[ 45 ] [ 46 ]} على الرغم من ذلك، لا تزال خوارزمية آدم مستخدمة نظرًا لأدائها القوي في التطبيق العملي. ^{[ 47 ]}

على الرغم من أن التحسين القائم على الإشارة يعود إلى خوارزمية Rprop المذكورة سابقًا ، فقد حاول الباحثون في عام 2018 تبسيط خوارزمية Adam عن طريق إزالة قيمة التدرج العشوائي من الحسابات والاكتفاء بإشارته فقط. ^{[ 56 ] [ 57 ]} ينتج عن ذلك انخفاض ملحوظ في تكلفة نقل التدرجات من العمال إلى خادم المعلمات. وبهذا المعنى، يُسهم ذلك في ضغط معلومات التدرج بشكل أفضل، مع الحفاظ على تقارب مماثل لخوارزمية التدرج العشوائي القياسية. ^{[ 57 ]}

يُعدّ البحث الخطي التراجعي أحد أنواع خوارزمية التدرج الهبوطي. جميع المعلومات الواردة أدناه مأخوذة من الرابط المذكور. يعتمد هذا النوع على شرط يُعرف بشرط أرميجو-جولدشتاين. تسمح كلتا الطريقتين بتغيير معدلات التعلّم في كل تكرار، إلا أن طريقة التغيير تختلف. يستخدم البحث الخطي التراجعي تقييمات الدوال للتحقق من شرط أرميجو، ومن حيث المبدأ، يمكن أن تكون حلقة التكرار في الخوارزمية لتحديد معدلات التعلّم طويلة وغير معروفة مسبقًا. لا يحتاج التدرج الهبوطي التكيفي إلى حلقة تكرار لتحديد معدلات التعلّم. من ناحية أخرى، لا يضمن التدرج الهبوطي التكيفي "خاصية الهبوط" التي يتميز بها البحث الخطي التراجعي، وهي أن${\displaystyle f(x_{n+1})\leq f(x_{n})}$لجميع قيم n. إذا كان تدرج دالة التكلفة مستمرًا عالميًا وفقًا لشرط ليبشيتز، مع ثابت ليبشيتز L، وتم اختيار معدل التعلم من الرتبة 1/L، فإن النسخة القياسية من SGD هي حالة خاصة من البحث الخطي التراجعي.

يُقدّم نظيرٌ عشوائيٌّ لخوارزمية نيوتن-رافسون القياسية (الحتمية) (وهي طريقة من الدرجة الثانية) شكلاً أمثل أو شبه أمثل للتحسين التكراري في سياق التقريب العشوائي . وقد طوّر بيرد وهانسن ونوسيدال وسينغر طريقةً تستخدم القياسات المباشرة لمصفوفات هيسيان للمُجمّعات في دالة المخاطرة التجريبية. ^{[ 58 ]} مع ذلك، قد لا يكون تحديد مصفوفات هيسيان المطلوبة للتحسين مباشرةً ممكنًا عمليًا. وقدّم سبال وآخرون طرقًا عمليةً وسليمةً نظريًا لإصدارات الدرجة الثانية من خوارزمية التدرج العشوائي (SGD) التي لا تتطلب معلومات مباشرة عن مصفوفات هيسيان. ^{[ 59 ] [ 60 ] [ 61 ]} (يقدم روبرت طريقة أقل كفاءة تعتمد على الفروق المحدودة بدلاً من الاضطرابات المتزامنة. ^{[ 62 ]} ) ثمة نهج آخر لتقريب مصفوفة هيسيان، وهو استبدالها بمصفوفة معلومات فيشر، التي تحول التدرج المعتاد إلى تدرج طبيعي. ^{[ 63 ]} تعتمد هذه الطرق، التي لا تتطلب معلومات هيسيان مباشرة، إما على قيم الحدود في دالة المخاطرة التجريبية المذكورة أعلاه، أو على قيم تدرجات هذه الحدود (أي مدخلات SGD). على وجه الخصوص، يمكن تحقيق الأمثلية من الدرجة الثانية تقاربياً دون حساب مباشر لمصفوفات هيسيان للحدود في دالة المخاطرة التجريبية. عندما يكون الهدف هو خسارة المربعات الصغرى غير الخطية$${\displaystyle Q(w)={\frac {1}{n}}\sum _{i=1}^{n}Q_{i}(w)={\frac {1}{n}}\sum _{i=1}^{n}(m(w;x_{i})-y_{i})^{2},}$$ أين${\displaystyle m(w;x_{i})}$في النموذج التنبؤي (مثل الشبكة العصبية العميقة )، يمكن استغلال بنية الدالة الهدفية لتقدير معلومات الرتبة الثانية باستخدام التدرجات فقط. وتكون الطرق الناتجة بسيطة وفعالة في كثير من الأحيان ^{[ 64 ].}