مزالق اللاتحدب وإعادة التشغيل

حين يوجد أكثر من وادٍ

معظم النماذج المهمة غير محدبة. لأهدافها عدة نهايات صغرى محلية ونقاط سرج وهضاب مسطحة، ويتدحرج الانحدار التدريجي ببساطة إلى الوادي الذي بدأ فيه. خذ $f(x)=x^4-3x^2+x$. تنعدم مشتقتها $4x^3-6x+1$ عند $x=-1.301$ و$x=0.170$ و$x=1.131$. الأولى والأخيرة نهايتان صغريان بقيمتي $f=-3.514$ و$f=-1.070$ والوسطى حدبة بينهما. والنزول بخطوة صغيرة من $x_0=2$ ينتهي عند $1.131$ وهي نهاية صغرى محلية فقط، ومن $x_0=-2$ ينتهي عند $-1.301$ وهي العامة. وبدايتان متقاربتان مثل $x_0=0.1$ و$x_0=0.2$ على جانبي الحدبة عند $0.170$ تنتهيان في واديين مختلفين.

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

العلاج المعتاد هو إعادة التشغيل. شغّل المحسِّن من $K$ نقطة بدء مختلفة واحتفظ بالنتيجة ذات أدنى قيمة للهدف. فإذا كانت كل بداية تقع بصورة مستقلة في الوادي العام باحتمال $p$ فإن واحدة على الأقل من $K$ بداية تقع فيه باحتمال $1-(1-p)^K$. من أجل $p=0.2$ و$K=10$ يساوي $0.893$، والوصول إلى $99\%$ يتطلب $K\ge\ln0.01/\ln0.8=20.6$ أي 21 بداية. وتفيد نقاط البدء الأفضل أيضًا: حل من تخفيف محدب أو معايرة الأمس أو بحث شبكي على المعاملات القليلة الأهم.

• نهايات صغرى محلية: ينتهي النزول في الوادي الذي بدأ فيه فنقطة البدء تحدد الجواب.
• أسراج وهضاب: تدرج صفري أو ضئيل بلا نهاية صغرى؛ يساعد الزخم والضجيج.
• إعادة التشغيل: تنجح $K$ بداية باحتمال $1-(1-p)^K$؛ احتفظ بأفضل قيمة للهدف.

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

• قيمة النهاية الصغرى العامة15 نقطة
• البدء من x = 215 نقطة
• بدايتان متقاربتان15 نقطة
• نجاح إعادة التشغيل العشوائية15 نقطة
• كم إعادة تشغيل15 نقطة
• قرب نقطة سرج10 نقطة
• مقارنة نتائج إعادة التشغيل15 نقطة