| dbo:abstract
|
- في التعقيد الحسابي والتحسين ، تنص نظرية لا غداء مجاني على أن التكلفة الحسابية لإيجاد حل والتي يتم حسابها عبر إيجاد المتوسط الحسابي لجميع المشكلات في الفئة، هي نفسها بالنسبة لأي طريقة حل. لذا لا يوجد حل مختصر. في الحوسبة، تحت ظروف معينة تكون المخرجات الناتجة من الإجراءات لحل نوع معين من المشاكل متطابقة إحصائياً. هناك طريقة لوصف ظرف كهذا، قدمه ديفيد ولبرت وويليام ج. ماكردي فيما يتعلق بمشاكل البحث والتحسين ، تتمثل بالقول بأنه لا يوجد غداء مجاني . استخلص ولبرت نظرية لا غداء مجاني للتعلم الآلي ( الاستدلال الإحصائي ). لكن قبله، أثبت كولين شافير (Cullen Schaffer) نسخة مقيدة لنظريات ولبرت واستخدمها في نقد الوضع الحالي لأبحاث التعلم الآلي حول مشكلة الاستقراء. في استعارة «لا غداء مجاني» ، تمثل اجراءات حل المشكلات بأنها مطاعم، لكل منها قائمة طعام، يكون الطعام هنا هو المشكلة، والسعر هو الكلفة الحاسوبية لحلها. قوائم المطاعم متطابقة إلا في جانب واحد - حيث تختلط الاسعار من مطعم إلى آخر. بالنسبة لمن يأكلون اللحوم، والذين يُمكن أن يطلبوا أي طبق من القائمة، فإن متوسط تكلفة الغداء لا تعتمد على اختيار المطعم. ولكن النباتيون الذين يذهبون لتناول الغداء بانتظام مع من يأكلون اللحوم (والذين ستكون خياراتهم أكثر اقتصادية) قد يدفع متوسط تكلفة عالية لتناول طعام الغداء. لتقليل متوسط التكلفة بشكل ممنهج، يجب استخدام المعرفة المسبقة عن أ) ما سيطلبه الشخص و ب) كلفة الطلب في المطاعم المختلفة. وهذا يعني أن تحسين الأداء في حل المشكلات يتوقف على استخدام المعلومات السابقة لمطابقة الإجراءات مع المشاكل. رسمياً، لا يوجد غداء مجاني عندما يكون توزيع الاحتمالية على المشاكل المماثلة بكيفية يكون لدى اجراءات حل المشاكل جميعها حلول متطابقة، حيث ستكون جميع الاجراءات متساوية. في حالة البحث ، تعد المشكلة دالة موضوعية ، والنتيجة هي سلسلة من القيم التي يتم الحصول عليها عبر تقييم الحلول المرشحة في مجال الدالة. (ar)
- Die No-free-Lunch-Theoreme („no free lunch“ ist englisch für „kein kostenloses Mittagessen“ bzw. sinngemäß „nichts ist umsonst“, daher auch Nichts-ist-umsonst-Theoreme) sind im Wesentlichen zwei mathematische Theoreme aus der Optimierung und Komplexitätstheorie über die Berechenbarkeit bestimmter mathematischer Problemstellungen. Die Theoreme zeigen Grenzen von Optimierungsalgorithmen bzw. Verfahren des maschinellen Lernens auf. Die Theoreme basieren auf der Prämisse, dass der Suchraum durch eine Wahrscheinlichkeitsfunktion gegeben ist. Vereinfacht sagen sie aus, dass kein universell gutes Verfahren zur Lösung eines Optimierungsproblems oder zum Abstrahieren von Datensätzen existiert, wenn die Menge aller Probleme bzw. Datensätze betrachtet wird. Ist eine bestimmte Strategie in einem Teilbereich besser als eine andere, so muss sie in einem anderen Teilbereich schlechter sein (Nichts ist umsonst). Insbesondere zeigt sich, dass keine Strategie, wenn sie auf die Grundgesamtheit aller Fälle angewandt wird, besser abschneidet als bloßes Raten. Es kann effiziente Algorithmen geben, wenn der Suchraum Struktur aufweist (z. B. eine stetige, differenzierbare Funktion darstellt), oder wenn sogar eine geschlossene Lösung existiert (z. B. Extremum einer quadratischen Funktion), die ganz ohne Suche bestimmbar ist. Es ist also durchaus möglich, für bestimmte Problemmengen Strategien zu entwickeln, die besser sind als andere. Im Alltag ist dem Suchraum in den meisten Fällen schon durch die Naturgesetze eine Struktur aufgeprägt, sodass meist effizient gesucht/optimiert werden kann. Die No-free-Lunch-Theoreme sind Unmöglichkeitssätze, wie auch der gödelsche Unvollständigkeitssatz in der Mathematik oder das Arrow-Theorem in der Sozialwahltheorie. Die Bezeichnung stammt von der englischen Redensart There ain’t no such thing as a free lunch. und entdeckten sie 1995. In einer verschärften Formulierung von 2001 gilt das No-free-Lunch-Theorem der Optimierung auch für Problemmengen, die unter Permutation abgeschlossen sind. (de)
- In computational complexity and optimization the no free lunch theorem is a result that states that for certain types of mathematical problems, the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method. The name alludes to the saying "there ain't no such thing as a free lunch", that is, no method offers a "short cut". This is under the assumption that the search space is a probability density function. It does not apply to the case where the search space has underlying structure (e.g., is a differentiable function) that can be exploited more efficiently (e.g., Newton's method in optimization) than random search or even has closed-form solutions (e.g., the extrema of a quadratic polynomial) that can be determined without search at all. For such probabilistic assumptions, the outputs of all procedures solving a particular type of problem are statistically identical. A colourful way of describing such a circumstance, introduced by David Wolpert and in connection with the problems of searchand optimization,is to say that there is no free lunch. Wolpert had previously derived no free lunch theorems for machine learning (statistical inference). Before Wolpert's article was published, Cullen Schaffer independently proved a restricted version of one of Wolpert's theorems and used it to critique the current state of machine learning research on the problem of induction. In the "no free lunch" metaphor, each "restaurant" (problem-solving procedure) has a "menu" associating each "lunch plate" (problem) with a "price" (the performance of the procedure in solving the problem). The menus of restaurants are identical except in one regard – the prices are shuffled from one restaurant to the next. For an omnivore who is as likely to order each plate as any other, the average cost of lunch does not depend on the choice of restaurant. But a vegan who goes to lunch regularly with a carnivore who seeks economy might pay a high average cost for lunch. To methodically reduce the average cost, one must use advance knowledge of a) what one will order and b) what the order will cost at various restaurants. That is, improvement of performance in problem-solving hinges on using prior information to match procedures to problems. In formal terms, there is no free lunch when the probability distribution on problem instances is such that all problem solvers have identically distributed results. In the case of search, a problem instance in this context is a particular objective function, and a result is a sequence of values obtained in evaluation of candidate solutions in the domain of the function. For typical interpretations of results, search is an optimization process. There is no free lunch in search if and only if the distribution on objective functions is invariant under permutation of the space of candidate solutions. This condition does not hold precisely in practice, but an "(almost) no free lunch" theorem suggests that it holds approximately. (en)
- ノーフリーランチ定理（ノーフリーランチていり、no-free-lunch theorem、NFLT）は、物理学者 David H. Wolpert と William G. Macready が生み出した組合せ最適化の領域の定理である。その定義は以下のようになる。 ……コスト関数の極値を探索するあらゆるアルゴリズムは、全ての可能なコスト関数に適用した結果を平均すると同じ性能となる — Wolpert and Macready、1995年 この定理の名称は、ハインラインのSF小説『月は無慈悲な夜の女王』（1966年）で有名になった格言の"There ain't no such thing as a free lunch."に由来する。 数学的にありうべき全ての問題の集合について、どの探索アルゴリズムも同じ平均性能を示すことを説明したものである。これは、探索アルゴリズムに必ず何らかの偏向があるため、そのアルゴリズムが前提としている事が問題に当てはまらないことがあるからである。 右の図はノーフリーランチ定理を視覚化した例である。 一方、この定理は「あらゆる問題で性能の良い汎用最適化戦略は理論上不可能であり、ある戦略が他の戦略より性能がよいのは、現に解こうとしている特定の問題に対して特殊化（専門化）されている場合のみである」ということを立証している（Ho and Pepyne、2002年）。 この定理は、問題領域に関する知識を使わずに遺伝的アルゴリズムや焼きなまし法などの汎用探索アルゴリズムを使うことに反対する論拠として使われる。他の汎用アルゴリズムにも適用されてきたが、一般にノーフリーランチ定理でカバーできない実世界の大きなサブセットを構築することも可能である。ノーフリーランチ定理は全てのコスト関数を対象として成立するものである。このため、コスト関数の真部分集合には適用できない。実際の問題解決への適用には、この点での制限をうける。 工学者や最適化の専門家にとって、この定理は、問題領域の知識を可能な限り使用して最適化すべきだということを示しており、領域を限定して特殊な最適化ルーチンを作成すべきであることを示している。 (ja)
- В обчислювальних процесах є обставини, за яких усі методи розв'язку однієї задачі виявляються статистично ідентичними. Мальовничим способом представлення таких обставин, запропонованим Девідом Вульпертом та Вільямом Дж. Маккріді в зв'язку з проблемами пошуку та оптимізації, є вислів — «Безкоштовних сніданків не існує». Перед цим Вульперт вивів цю теорему для машинного навчання (статистичного висновування). Перед публікацією роботи Вульперта, Каллен Шаффер підсумував переддруковану версію роботи Вульперта, але використав іншу термінологію. В розгорненні метафори про безкоштовні сніданки, кожен «ресторан» (процедура, що розв'язує проблему) має «меню», асоціюючи кожну «страву» (проблему) з ціною (продуктивністю процедури, що вирішує цю проблему). Меню ресторанів ідентичні за винятком однієї деталі — ціни перемішані від одного ресторану до іншого. Для всеядної істоти, яка буде куштувати будь-яку страву, середня вартість обіду не залежить від вибору ресторану. Але вегетаріанець, що регулярно снідає разом з плотоядним та бажає заощадити, платить високу середню ціну за один сніданок. Для поступового зниження середньої вартості, потрібно мати поглиблені знання про a) власне саме замовлення та b) вартість цієї страви в усіх ресторанах. Таким чином, підвищення продуктивності розв'язання проблем потребує використання попередньої інформації для зіставлення процедур і проблем. В формальному значенні, вільних сніданків не існує коли ймовірнісний розподіл випадків проблеми такий, що всі розв'язувані проблеми мають однаково розподілені результати. У випадку пошуку, кожен екземпляр проблеми є цільовою функцією, а результатом — послідовність значень, отриманих оцінкою допустимих розв'язків в області значень функції. В типовій інтерпретації результатів, пошук — це процес оптимізації. Безкоштовних сніданків у пошуку немає у випадку, коли і тільки коли розподіл цільової функції є константою з перестановок на множині допустимих розв'язків. Ця умова не виконується точно на практиці, але теорема про (майже) не існуючі безкоштовні сніданки пропонує її наближене виконання. (uk)
|
| rdfs:comment
|
- في التعقيد الحسابي والتحسين ، تنص نظرية لا غداء مجاني على أن التكلفة الحسابية لإيجاد حل والتي يتم حسابها عبر إيجاد المتوسط الحسابي لجميع المشكلات في الفئة، هي نفسها بالنسبة لأي طريقة حل. لذا لا يوجد حل مختصر. في الحوسبة، تحت ظروف معينة تكون المخرجات الناتجة من الإجراءات لحل نوع معين من المشاكل متطابقة إحصائياً. هناك طريقة لوصف ظرف كهذا، قدمه ديفيد ولبرت وويليام ج. ماكردي فيما يتعلق بمشاكل البحث والتحسين ، تتمثل بالقول بأنه لا يوجد غداء مجاني . استخلص ولبرت نظرية لا غداء مجاني للتعلم الآلي ( الاستدلال الإحصائي ). لكن قبله، أثبت كولين شافير (Cullen Schaffer) نسخة مقيدة لنظريات ولبرت واستخدمها في نقد الوضع الحالي لأبحاث التعلم الآلي حول مشكلة الاستقراء. (ar)
- Die No-free-Lunch-Theoreme („no free lunch“ ist englisch für „kein kostenloses Mittagessen“ bzw. sinngemäß „nichts ist umsonst“, daher auch Nichts-ist-umsonst-Theoreme) sind im Wesentlichen zwei mathematische Theoreme aus der Optimierung und Komplexitätstheorie über die Berechenbarkeit bestimmter mathematischer Problemstellungen. Die Theoreme zeigen Grenzen von Optimierungsalgorithmen bzw. Verfahren des maschinellen Lernens auf. (de)
- In computational complexity and optimization the no free lunch theorem is a result that states that for certain types of mathematical problems, the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method. The name alludes to the saying "there ain't no such thing as a free lunch", that is, no method offers a "short cut". This is under the assumption that the search space is a probability density function. It does not apply to the case where the search space has underlying structure (e.g., is a differentiable function) that can be exploited more efficiently (e.g., Newton's method in optimization) than random search or even has closed-form solutions (e.g., the extrema of a quadratic polynomial) that can be determined without searc (en)
- ノーフリーランチ定理（ノーフリーランチていり、no-free-lunch theorem、NFLT）は、物理学者 David H. Wolpert と William G. Macready が生み出した組合せ最適化の領域の定理である。その定義は以下のようになる。 ……コスト関数の極値を探索するあらゆるアルゴリズムは、全ての可能なコスト関数に適用した結果を平均すると同じ性能となる — Wolpert and Macready、1995年 この定理の名称は、ハインラインのSF小説『月は無慈悲な夜の女王』（1966年）で有名になった格言の"There ain't no such thing as a free lunch."に由来する。 数学的にありうべき全ての問題の集合について、どの探索アルゴリズムも同じ平均性能を示すことを説明したものである。これは、探索アルゴリズムに必ず何らかの偏向があるため、そのアルゴリズムが前提としている事が問題に当てはまらないことがあるからである。 右の図はノーフリーランチ定理を視覚化した例である。 一方、この定理は「あらゆる問題で性能の良い汎用最適化戦略は理論上不可能であり、ある戦略が他の戦略より性能がよいのは、現に解こうとしている特定の問題に対して特殊化（専門化）されている場合のみである」ということを立証している（Ho and Pepyne、2002年）。 (ja)
- В обчислювальних процесах є обставини, за яких усі методи розв'язку однієї задачі виявляються статистично ідентичними. Мальовничим способом представлення таких обставин, запропонованим Девідом Вульпертом та Вільямом Дж. Маккріді в зв'язку з проблемами пошуку та оптимізації, є вислів — «Безкоштовних сніданків не існує». Перед цим Вульперт вивів цю теорему для машинного навчання (статистичного висновування). Перед публікацією роботи Вульперта, Каллен Шаффер підсумував переддруковану версію роботи Вульперта, але використав іншу термінологію. (uk)
|