بعد ثلاثمائة عام، أصبح من الممكن تطبيق أداة اسحق نيوتن على مشاكل معقدة لا حدود لها.

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

خوارزمية نيوتن

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

أكثر من 300 عام

رغم عمرها الطويل، لا تزال طريقة نيوتن من أكثر أدوات التحسين تأثيرًا في التطبيقات الحديثة.

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

تقنية عريقة

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

كيف تعمل طريقة نيوتن عمليًا

1

اختيار نقطة بداية

تبدأ الخوارزمية من نقطة يُعتقد أنها قريبة من الحد الأدنى الحقيقي للدالة.

2

حساب المشتقات

يُحسب الميل عند النقطة المختارة، ثم يُحسب معدل تغير هذا الميل عبر المشتقة الثانية.

3

بناء تقريب تايلور

تُستخدم هذه المعلومات لصنع معادلة تربيعية تشبه الدالة الأصلية بالقرب من تلك النقطة.

4

إيجاد حد أدنى أسهل

بدلًا من تصغير الدالة الأصلية مباشرة، يُحسب الحد الأدنى للمعادلة الأبسط.

5

تكرار التحديث

تُعاد الإحداثيات الجديدة إلى الدالة الأصلية، ثم تتكرر العملية حتى الاقتراب من القيمة الدنيا الحقيقية.

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

إيجاد مجال للتذبذب

يركز العمل الجديد على تعديل تقريب تايلور بحيث يصبح أسهل في التصغير من دون أن يفقد صلته الوثيقة بالدالة الأصلية.

مقارنة بين الطريقة الأصلية والتوسيع الجديد

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

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