Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Если алгоритм хорошо справляется с одними задачами, то он расплачивается за это при решении других. – математический фольклор.
If an algorithm does well on some problems, then it pays for that on other problems
mathematical folklore
В математическом фольклоре теорема "нет бесплатного обеда" (NFL) (иногда употребляется во множественном числе) Дэвида Уолперта и Уильяма Макреди отсылает к поговорке "бесплатного сыра бывает только в мышеловке", то есть не существует простых путей к успеху. Она была опубликована в 1997 году в работе "Теоремы оптимизации без бесплатного обеда". Ранее Уолперт вывел теоремы "нет бесплатного обеда" для машинного обучения (статистического вывода). В 2005 году сами Уолперт и Макреди отметили, что первая теорема в их статье "утверждает, что любые два алгоритма оптимизации эквивалентны, если их производительность усредняется по всем возможным задачам". Теорема "нет бесплатного обеда" (NFL) – это легко сформулированное и понятное следствие теорем, которые Уолперт и Макреди на самом деле доказали. Она слабее доказанных теорем и, следовательно, не охватывает их полностью. Различные исследователи значительно расширили работу Уолперта и Макреди. С точки зрения применения теоремы NFL в контексте исследований, область "отсутствие бесплатного обеда" в поиске и оптимизации посвящена математическому анализу данных на предмет статистической идентичности, в частности, в задачах поиска и оптимизации. В то время как некоторые ученые считают, что NFL дает важные идеи, другие утверждают, что NFL имеет мало отношения к исследованиям в области машинного обучения.
In mathematical folklore, the "no free lunch" (NFL) theorem (sometimes pluralized) of David Wolpert and William Macready, alludes to the saying "no such thing as a free lunch", that is, there are no easy shortcuts to success. It appeared in the 1997 "No Free Lunch Theorems for Optimization". Wolpert had previously derived no free lunch theorems for machine learning (statistical inference). In 2005, Wolpert and Macready themselves indicated that the first theorem in their paper "state[s] that any two optimization algorithms are equivalent when their performance is averaged across all possible problems". The "no free lunch" (NFL) theorem is an easily stated and easily understood consequence of theorems Wolpert and Macready actually prove. It is weaker than the proven theorems, and thus does not encapsulate them. Various investigators have extended the work of Wolpert and Macready substantively. In terms of how the NFL theorem is used in the context of the research area, the no free lunch in search and optimization is a field that is dedicated for purposes of mathematically analyzing data for statistical identity, particularly search and optimization. While some scholars argue that NFL conveys important insight, others argue that NFL is of little relevance to machine learning research.
Происхождение
Вулперт и Макреди приводят две теоремы НФЛ, тесно связанные с фольклорной теоремой. В своей статье они утверждают: "Мы назвали связанные результаты теоремами НФЛ, поскольку они показывают, что если алгоритм хорошо работает на определенном классе задач, то он неизбежно расплачивается за это ухудшением производительности на всех остальных задачах."
Wolpert and Macready give two NFL theorems that are closely related to the folkloric theorem. In their paper, they state:
blockquote|We have dubbed the associated results NFL theorems because they demonstrate that if an algorithm performs well on a certain class of problems then it necessarily pays for that with degraded performance on the set of all remaining problems.