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

النزول مع المنحدر

يكرّر الانحدار التدريجي حركة واحدة: خطوة عكس التدرج، $\mathbf w_{k+1}=\mathbf w_k-\eta\,\nabla f(\mathbf w_k)$ . والعدد $\eta>0$ هو حجم الخطوة ويسمى غالبًا معدل التعلم. $\eta$ الصغير آمن لكنه بطيء، و $\eta$ الكبير يتجاوز قاع الوادي وقد تبتعد التكرارات أكثر في كل مرة.

f(w)=\tfrac12 a\,w^{2}\ \Rightarrow\ w_{k+1}=(1-\eta a)\,w_k,\qquad |1-\eta a|<1\iff 0<\eta<\frac{2}{a}

(1)

في أبسط وعاء تضرب الخطوة $w$ في $1-\eta a$ كل مرة، فتؤول التكرارات إلى الصفر تمامًا حين $|1-\eta a|<1$ أي $\eta<2/a$ . والاختيار $\eta=1/a$ يصل إلى النهاية الصغرى في خطوة واحدة، وأي $\eta$ بين $1/a$ و $2/a$ يتقارب أيضًا لكن بتبدل الإشارة في الطريق. وبعد $2/a$ يتجاوز العامل الواحد في القيمة المطلقة وتنفجر التكرارات.

ثلاث خطوات على f = 3x²هنا

f'(x)=6x

فـ

a=6

. نبدأ من

x_0=4

مع

\eta=0.1

: العامل

1-0.6=0.4

فنحصل على

x_1=1.6

x_2=0.64

x_3=0.256

. وحد الاستقرار

2/6=0.333

. ومع

\eta=0.5

يكون العامل

1-3=-2

فتكون التكرارات

4,-4,8,\dots

ويتضاعف حجمها في كل خطوة.

في عدة متغيرات يختلف الانحناء حسب الاتجاه. فأكبر قيمة ذاتية للهسيان $L$ تحدّ الخطوة المستعملة ( $\eta<2/L$ )، وأصغرها $\mu$ تحدد بطء عبور الاتجاه الأكثر تسطحًا. ونسبتهما $\kappa=L/\mu$ هي رقم الشرط. وبأفضل خطوة ثابتة $\eta=2/(L+\mu)$ يتقلص الخطأ بنحو العامل $(\kappa-1)/(\kappa+1)$ في كل خطوة، فالـ $\kappa$ الكبير يعني عاملًا قريبًا من الواحد وتعرجًا بطيئًا في وادٍ طويل ضيق. وفي مصفوفة تباين اثني عشر سهمًا أمريكيًا كبيرًا منذ 2010 يبلغ $\kappa$ نحو $33$ : العامل $0.941$ وتقليل الخطأ مئة ضعف يحتاج نحو 76 خطوة.

\eta^{*}=\frac{2}{L+\mu},\qquad \lVert\mathbf w_k-\mathbf w^{*}\rVert\ \lesssim\ \Big(\frac{\kappa-1}{\kappa+1}\Big)^{k}\lVert\mathbf w_0-\mathbf w^{*}\rVert,\qquad \kappa=\frac{L}{\mu}

(2)

خطوة آمنة: $\eta<2/L$ حيث $L$ أكبر قيمة ذاتية للهسيان، وإلا تباعدت التكرارات.
السرعة: يحددها رقم الشرط $\kappa=L/\mu$ ؛ وكلما كبر أبطأ الهبوط.
التوقف: توقف حين يقل $\lVert\nabla f\rVert$ عن حد التسامح مع سقف لعدد التكرارات.

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

\kappa

وقد تحوّل آلاف التكرارات إلى عشرات. والتهيئة المسبقة هي الصيغة العامة لهذه الفكرة نفسها.

المختبر: ما الذي يُقيَّم

الخطوة الأولى15 نقطة
الخطوة الثانية10 نقطة
أكبر خطوة مستقرة15 نقطة
خطوة كبيرة جدًا15 نقطة
رقم شرط15 نقطة
أفضل عامل انكماش15 نقطة
لماذا يكون سوء الشرط بطيئًا15 نقطة

النزول مع المنحدر

f(w)=\tfrac12 a\,w^{2}\ \Rightarrow\ w_{k+1}=(1-\eta a)\,w_k,\qquad |1-\eta a|<1\iff 0<\eta<\frac{2}{a}

(1)

ثلاث خطوات على f = 3x²هنا

f'(x)=6x

فـ

a=6

. نبدأ من

x_0=4

مع

\eta=0.1

: العامل

1-0.6=0.4

فنحصل على

x_1=1.6

x_2=0.64

x_3=0.256

. وحد الاستقرار

2/6=0.333

. ومع

\eta=0.5

يكون العامل

1-3=-2

فتكون التكرارات

4,-4,8,\dots

ويتضاعف حجمها في كل خطوة.

\eta^{*}=\frac{2}{L+\mu},\qquad \lVert\mathbf w_k-\mathbf w^{*}\rVert\ \lesssim\ \Big(\frac{\kappa-1}{\kappa+1}\Big)^{k}\lVert\mathbf w_0-\mathbf w^{*}\rVert,\qquad \kappa=\frac{L}{\mu}

(2)

خطوة آمنة: $\eta<2/L$ حيث $L$ أكبر قيمة ذاتية للهسيان، وإلا تباعدت التكرارات.
السرعة: يحددها رقم الشرط $\kappa=L/\mu$ ؛ وكلما كبر أبطأ الهبوط.
التوقف: توقف حين يقل $\lVert\nabla f\rVert$ عن حد التسامح مع سقف لعدد التكرارات.

\kappa

وقد تحوّل آلاف التكرارات إلى عشرات. والتهيئة المسبقة هي الصيغة العامة لهذه الفكرة نفسها.

المختبر: ما الذي يُقيَّم

الخطوة الأولى15 نقطة
الخطوة الثانية10 نقطة
أكبر خطوة مستقرة15 نقطة
خطوة كبيرة جدًا15 نقطة
رقم شرط15 نقطة
أفضل عامل انكماش15 نقطة
لماذا يكون سوء الشرط بطيئًا15 نقطة

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

النزول مع المنحدر

المختبر: ما الذي يُقيَّم

سجّل الدخول لتشغيل الكود الخاص بك.

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

النزول مع المنحدر

المختبر: ما الذي يُقيَّم

سجّل الدخول لتشغيل الكود الخاص بك.