علماء الكمبيوتر يجدون حدود خوارزمية بحث أساسية

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

يمكنك التفكير في الوظيفة على أنها منظر طبيعي حيث يكون ارتفاع الأرض مساويًا لقيمة (أو ربح) الوظيفة في ذلك الموقع المحدد. يجد Descent Gradient حدًا أدنى محليًا لدالة من خلال إيجاد اتجاه الارتفاع الحاد في موقع معين والبحث عن اتجاه المنحدر بعيدًا عنه. يُطلق على منحدر المناظر الطبيعية اسم المنحدر، لذلك يُطلق على المنحدر اسم المنحدر.

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

يقول كوستيس داسكالاكيس Kostis Daskalakis من معهد ماساتشوستس للتكنولوجيا، إنه لم يتم الحديث كثيرًا عن منحدرات التدرج عن نظرية التعقيد.

التعقيد الحسابي هو دراسة الموارد (عادة وقت الحساب) المطلوبة لحل أو التحقق من الحلول لمختلف المشاكل الحسابية. يقوم الباحثون بتجميع المشكلات في فئات مختلفة، وجميع المشكلات في نفس الفئة تشترك في بعض الخصائص الحسابية الأساسية.

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

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

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

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

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

يشكل تقاطع فئتي PLS و PPAD نفسه فئة من المشكلات تسمى PLS int PPAD. يحتوي على العديد من المشاكل الطبيعية التي تهم الباحثين في مجال التعقيد. ومع ذلك، لم يتمكن الباحثون حتى الآن من العثور على مشكلة طبيعية كاملة لـ PLS INT PPAD، مما يعني أنها مثال على أصعب مشكلة ممكنة في هذه الفئة.

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

[طبيعة الحوسبة] شيء يجب علينا كجنس أن نحاول فهمه بعمق في جميع أشكاله. قال تيم روجاردن من جامعة كولومبيا: "أعتقد أن هذا يكفي لإثارة حماستنا بشأن هذا الاكتشاف".

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

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

لكن النتائج لا تعني أن الباحثين التطبيقيين يجب ألا يتوقعوا انحدار التدرج لتقديم حلول دقيقة لبعض المشكلات التي تكون الدقة فيها مهمة.

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

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

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

قال داسكالاكيس إن هذا يحد من الأهداف التي يمكنهم إطلاق النار عليها.

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

لكن هذا لا يعني عدم وجود خوارزميات سريعة للنسب المتدرج. ربما. لكن النتيجة لا تعني أن أي خوارزمية من هذا القبيل تعني على الفور أن هناك خوارزميات سريعة لجميع المشكلات الأخرى في PLS int PPAD، وهي أعلى بكثير من مجرد إيجاد خوارزميات سريعة للانحدار المقارب نفسه.

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