طريقتا نيوتن وشبه نيوتن

استخدام الانحناء

لا يعرف الانحدار التدريجي إلا الميل. أما طريقة نيوتن فتستعمل الانحناء أيضًا: تستبدل $f$ قرب النقطة الحالية بالدالة التربيعية التي لها القيمة والتدرج والهسيان نفسها، وتقفز مباشرة إلى نهايتها الصغرى. والخطوة $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$ . وفي دالة تربيعية تمامًا تقع على النهاية الصغرى في خطوة واحدة مهما كان رقم الشرط. وقرب النهاية الصغرى لأي دالة ملساء يكون التقارب تربيعيًا: يتربع الخطأ تقريبًا في كل خطوة فيتضاعف عدد الأرقام الصحيحة تقريبًا.

\mathbf w_{k+1}=\mathbf w_k-H(\mathbf w_k)^{-1}\nabla f(\mathbf w_k),\qquad \lVert\mathbf w_{k+1}-\mathbf w^{*}\rVert\ \lesssim\ C\,\lVert\mathbf w_k-\mathbf w^{*}\rVert^{2}

(1)

نيوتن على e^x − 2xلنصغّر

f(x)=e^x-2x

التي نهايتها الصغرى عند

x^{*}=\ln2=0.693147

. هنا

f'=e^x-2

f''=e^x

. من

x_0=0

x_1=0-(-1)/1=1

ثم

x_2=1-0.7183/2.7183=0.7358

x_3=0.6940

x_4=0.693148

. تتناقص الأخطاء

0.307،\ 0.0426،\ 0.0009،\ 4\cdot10^{-7}

أسرع من أي عامل ثابت. وفي متغيرين، من أجل

f=(x-1)^2+2(y+2)^2

عند

(3,0)

لدينا

\mathbf g=(4,8)

H=\mathrm{diag}(2,4)

فتكون الخطوة

-H^{-1}\mathbf g=(-2,-2)

وتبلغ خطوة واحدة النهاية الصغرى

(1,-2)

لطريقة نيوتن ثمن. فمع $n$ معاملًا يكون للهسيان $n^2$ مدخلًا ويكلف الحل به نحو $n^3$ عملية، وهذا مقبول لمئات المعاملات ومستحيل لملايينها. وبعيدًا عن النهاية الصغرى أو حيث لا يكون $H$ موجب التعريف قد تتجه خطوة نيوتن صعودًا، ولذلك تخمّد النسخ العملية الخطوة ببحث خطي. وتحتفظ طرق شبه نيوتن بمعظم السرعة دون الكلفة. فـ BFGS يبني تقريبًا لمقلوب الهسيان من التغيرات المرصودة $\mathbf s=\mathbf w_{k+1}-\mathbf w_k$ و $\mathbf y=\mathbf g_{k+1}-\mathbf g_k$ بفرض شرط القاطع $B\mathbf s=\mathbf y$ . لا يحتاج إلا إلى التدرجات وكلفته $O(n^2)$ للخطوة ويتقارب فوق الخطي. أما L-BFGS فيخزن آخر $m$ زوجًا فقط وعادةً من 5 إلى 20، فالذاكرة $O(mn)$ . وهو الحصان المعتاد في المعايرات الملساء وتقديرات الإمكان الأعظم، مثل المحسّنات الافتراضية في SciPy.

نيوتن: $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$ ؛ خطوة واحدة على التربيعية وتقارب تربيعي قرب النهاية الصغرى.
BFGS: يتعلم تقريبًا لمقلوب الهسيان من فروق التدرج فلا يحتاج مشتقات ثانية.
L-BFGS: يحتفظ بآخر أزواج قليلة فقط فيتسع لمعاملات كثيرة.

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

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

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

استخدام الانحناء

\mathbf w_{k+1}=\mathbf w_k-H(\mathbf w_k)^{-1}\nabla f(\mathbf w_k),\qquad \lVert\mathbf w_{k+1}-\mathbf w^{*}\rVert\ \lesssim\ C\,\lVert\mathbf w_k-\mathbf w^{*}\rVert^{2}

(1)

نيوتن على e^x − 2xلنصغّر

f(x)=e^x-2x

التي نهايتها الصغرى عند

x^{*}=\ln2=0.693147

. هنا

f'=e^x-2

f''=e^x

. من

x_0=0

x_1=0-(-1)/1=1

ثم

x_2=1-0.7183/2.7183=0.7358

x_3=0.6940

x_4=0.693148

. تتناقص الأخطاء

0.307،\ 0.0426،\ 0.0009،\ 4\cdot10^{-7}

أسرع من أي عامل ثابت. وفي متغيرين، من أجل

f=(x-1)^2+2(y+2)^2

عند

(3,0)

لدينا

\mathbf g=(4,8)

H=\mathrm{diag}(2,4)

فتكون الخطوة

-H^{-1}\mathbf g=(-2,-2)

وتبلغ خطوة واحدة النهاية الصغرى

(1,-2)

نيوتن: $\mathbf w\leftarrow\mathbf w-H^{-1}\mathbf g$ ؛ خطوة واحدة على التربيعية وتقارب تربيعي قرب النهاية الصغرى.
BFGS: يتعلم تقريبًا لمقلوب الهسيان من فروق التدرج فلا يحتاج مشتقات ثانية.
L-BFGS: يحتفظ بآخر أزواج قليلة فقط فيتسع لمعاملات كثيرة.

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

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

طريقتا نيوتن وشبه نيوتن

استخدام الانحناء

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

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

طريقتا نيوتن وشبه نيوتن

استخدام الانحناء

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

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