تكمن المشكلة في إيجاد حل سريع بين المرشحين (أ) و (ب) و (ج) الذين يستويان فيما بينهم، حيث يكون الصواب إما 0 أو 1. هناك ثماني حالات ("أطباق الغداء") من دالة المشكلة لـ xyz، حيث يشير كل من x وy و z إلى صلاحية كل من a و b و c على التوالي. المطعم هنا سيكون هو آلية التقييم، وسيكون هناك المطعم A والمطعم B حيث سيقيم كل منهما المرشحين بعكس الآخر، لكن لكل من المطعمين كلفة متساوية في النهاية من ناحية أحكامهما على المرشحين (المطعم هنا استعارة فقط وهو يشير إلى كونه دالة لتقييم المرشحين)
في التعقيد الحسابيوالتحسين ، تنص نظرية لا غداء مجاني على أن التكلفة الحسابية لإيجاد حل والتي يتم حسابها عبر إيجاد المتوسط الحسابي لجميع المشكلات في الفئة، هي نفسها بالنسبة لأي طريقة حل. لذا لا يوجد حل مختصر. في الحوسبة، تحت ظروف معينة تكون المخرجات الناتجة من الإجراءات لحل نوع معين من المشاكل متطابقة إحصائياً. هناك طريقة لوصف ظرف كهذا، قدمه ديفيد ولبرت وويليام ج. ماكردي فيما يتعلق بمشاكل البحث [1] والتحسين ، [2] تتمثل بالقول بأنه لا يوجد غداء مجاني . استخلص ولبرت نظرية لا غداء مجاني للتعلم الآلي ( الاستدلال الإحصائي ).[3] لكن قبله، أثبت كولين شافير (Cullen Schaffer) نسخة مقيدة لنظريات ولبرت واستخدمها في نقد الوضع الحالي لأبحاث التعلم الآلي حول مشكلة الاستقراء.[4]
في استعارة «لا غداء مجاني» ، تمثل اجراءات حل المشكلات بأنها مطاعم، لكل منها قائمة طعام، يكون الطعام هنا هو المشكلة، والسعر هو الكلفة الحاسوبية لحلها. قوائم المطاعم متطابقة إلا في جانب واحد - حيث تختلط الاسعار من مطعم إلى آخر. بالنسبة لمن يأكلون اللحوم، والذين يُمكن أن يطلبوا أي طبق من القائمة، فإن متوسط تكلفة الغداء لا تعتمد على اختيار المطعم. ولكن النباتيون الذين يذهبون لتناول الغداء بانتظام مع من يأكلون اللحوم (والذين ستكون خياراتهم أكثر اقتصادية) قد يدفع متوسط تكلفة عالية لتناول طعام الغداء. لتقليل متوسط التكلفة بشكل ممنهج، يجب استخدام المعرفة المسبقة عن أ) ما سيطلبه الشخص و ب) كلفة الطلب في المطاعم المختلفة. وهذا يعني أن تحسين الأداء في حل المشكلات يتوقف على استخدام المعلومات السابقة لمطابقة الإجراءات مع المشاكل.[2][4]
رسمياً، لا يوجد غداء مجاني عندما يكون توزيع الاحتمالية على المشاكل المماثلة بكيفية يكون لدى اجراءات حل المشاكل جميعها حلول متطابقة، حيث ستكون جميع الاجراءات متساوية. في حالة البحث ، تعد المشكلة دالة موضوعية ، والنتيجة هي سلسلة من القيم التي يتم الحصول عليها عبر تقييم الحلول المرشحة في مجال الدالة.
نظرة عامة
تحل بعض المشكلات الحسابية من خلال البحث عن حلول جيدة من بين الحلول المرشحة . يسمى وصف كيفية اختيار الحلول المرشحة للتقييم بشكل متكرر بخوارزمية البحث . قد تحصل خوارزميات البحث المختلفة لمشكلة معينة على نتائج مختلفة، ولكن بأخذ جميع المشكلات في نظر الاعتبار، لا يمكن تمييز الخوارزميات المختلفة. ويترتب على ذلك أنه إذا حققت خوارزمية معينة نتائج متفوقة في بعض المشكلات، فيجب أن تحصل على نتائج اسوء في المشكلات الأخرى. بذلك، نفهم أنه لا يوجد غداء مجاني في البحث.[1] بدلا من ذلك، ووفقاً لشافر، [4] فإن أداء البحث محفوظ. عادة ما يُفهم البحث على أنه عملية تحسين، وهذا يؤدي إلى ملاحظة أنه لا يوجد غداء مجاني في التحسين.[2]
مراجع
^ ابWolpert، DH، Macready، WG (1995)، No Free Lunch Theorems for Search، Technical Report SFI-TR-95-02-010 (Santa Fe Institute).
^Wolpert ، ديفيد (1996) ، "The Aack of A Priori التمييز بين خوارزميات التعلم" ، الحوسبة العصبية ، ص. 1341-1390.
^ ابجشافير ، كولين (1994) ، "قانون الحفاظ على أداء التعميم" ، المؤتمر الدولي للتعلم الآلي ، H. Willian و W. Cohen ، محررين. سان فرانسيسكو: مورغان كوفمان ، ص. 259-265.
