الانحدار العشوائي التدرجي

كما ذُكر سابقًا، فإن الانحدار التدرجي العشوائي التقليدي حساس عمومًا لمعدل التعلم ${\displaystyle \eta }$. فالتقارب السريع يتطلب معدلات تعلم كبيرة، لكن هذا قد يسبب عدم استقرار عددي. يمكن حل هذه المشكلة إلى حد كبير^[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 }$، لأن معدل التعلم أصبح الآن مُطَبّعًا. هذه المقارنة بين الطريقة التقليدية وطريقة التحديثات الضمنية في مشكلة المربعات الصغرى مشابهة جدًا للمقارنة بين مرشح المربعات الصغرى الأقل ومرشح إل إم إس المطبع.

على الرغم من أن الحل المغلق للتحديثات الضمنية ممكن فقط في حالة المربعات الصغرى، إلا أنه يمكن تنفيذ هذه الطريقة بكفاءة في مجموعة واسعة من النماذج. تحديدًا، لنفترض أن ${\displaystyle Q_{i}(w)}$ تعتمد على ${\displaystyle w}$ فقط من خلال توليفة خطية مع الميزات ${\displaystyle x_{i}}$، بحيث يمكننا كتابة ${\displaystyle \nabla _{w}Q_{i}(w)=-q(x_{i}'w)x_{i}}$، حيث ${\displaystyle q()}$ دالة حقيقية وقد تعتمد على ${\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)={\frac {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{حيث}}~\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]

في منتصف الثمانينيات، عدّل يوري نيستيروف الطريقة لاستخدام التدرج المتوقع عند النقطة التالية، والطريقة الناتجة التي تسمى "تدرج نيستروف المسرع" استُخدمت أحيانًا في التعلم الآلي في العقد 2010.^[36]

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

$${\displaystyle {\bar {w}}={\frac {1}{t}}\sum _{i=0}^{t-1}w_{i}.}$$

عند الانتهاء من عملية التحسين، يحل هذا المتجه المتوسط مكان w.

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

يبقى هناك معدل تعلم أساسي η، لكنه يُضرب في عناصر متجه {G_j,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}}}}$ هو معيار التدرجات السابقة، يتم تخفيف التحديثات الكبيرة ويتم زيادة معدلات التعلم للمعاملات التي تحصل على تحديثات قليلة أو صغيرة.

بالرغم من تصميمه للاستمثال المحدب، تم تطبيق أداجراد بنجاح في تحسينات غير محدبة.

آر إم إس بروب (اختصارًا لـ Root Mean Square Propagation) هو طريقة اخترعها جيمس مارتينز وإيليا سوتسكيفر عام 2012، حين كانا طلاب دكتوراه في مجموعة جيفري هينتون، حيث يُكيف معدل التعلم لكل معامل كما في أداجراد. الفكرة هي قسمة معدل التعلم لوزن ما على متوسط متحرك لمقدار التدرجات الأخيرة لذلك الوزن. تُحسب المتوسطات المتحركة بتربيع القيم كما يلي:

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

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

أدام (اختصارًا لـ Adaptive Moment Estimation) هو تحديث عام 2014 لمحسّن RMSProp يجمعه مع الخاصية الرئيسية لطريقة الزخم. يستخدم متوسطات متحركة ذات نسيان أسي لكل من التدرجات واللحظات الثانية للتدرجات.

لتحديث المعامل ${\displaystyle w^{(t)}}$ في التكرار ${\displaystyle t}$ مع دالة الخسارة ${\displaystyle L^{(t)}}$:

$${\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}}}}$ لتعويض هذا الانحياز والحصول على تقديرات أفضل.

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

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

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

يشكل التناظر العشوائي لخوارزمية نيوتن–رافسون القياسية (طريقة "الرتبة الثانية") شكلاً مثاليًا أو شبه مثالي من التحسين التكراري في إعداد التقريب العشوائي^{[بحاجة لمصدر]}. تم تطوير طريقة تستخدم قياسات مباشرة لمصفوفة هيسية لمجاميع دالة المخاطر التجريبية بواسطة بيرد، هانسن، نوكدال وسينغر.^[49] لكن تحديد مصفوفات هيسية المطلوبة مباشرةً قد لا يكون عملياً. توجد طرق عملية ونظرية سليمة لنسخ الرتبة الثانية من SGD لا تتطلب معلومات هيسية مباشرة بواسطة سبال وآخرين.^[50][51][52] (طريقة أقل كفاءة تعتمد على الفروقات المنتهية بدلاً من التشويش المتزامن مقدمة من روبيرت.^[53]) طريقة أخرى لتقريب مصفوفة هيسية هي استبدالها بمصفوفة معلومات فيشر، التي تحول التدرج العادي إلى تدرج طبيعي.^[54] هذه الطرق التي لا تتطلب معلومات هيسية مباشرة تعتمد إما على قيم المجاميع في دالة المخاطر التجريبية أو على قيم تدرجات المجاميع (أي مدخلات 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})}$ هو النموذج التنبؤي (مثل شبكة عصبونية اصطناعية), يمكن استغلال هيكل الهدف لتقدير معلومات الرتبة الثانية باستخدام التدرجات فقط. الطرق الناتجة بسيطة وغالبًا فعالة.^[55]