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

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

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

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

تقنية عريقة

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

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

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