Теорема об отсутствии бесплатного обеда в вычислительной сложности

Введение

Средняя стоимость решения одинакова для любого метода. Математический анализ вычислений.

В вычислительной сложности и оптимизации теорема о бесплатном обеде – это результат, утверждающий, что для определенных типов математических задач вычислительная стоимость поиска решения, усредненная по всем задачам в классе, одинакова для любого метода решения. Название отсылает к поговорке "бесплатного сыра бывает только в мышеловке", то есть ни один метод не предлагает "короткого пути". Это справедливо при условии, что пространство поиска представляет собой функцию плотности вероятности. Теорема не применима в случае, когда пространство поиска имеет внутреннюю структуру (например, является дифференцируемой функцией), которую можно использовать более эффективно (например, метод Ньютона в оптимизации), чем случайный поиск, или даже имеет аналитические решения (например, экстремумы квадратичного многочлена), которые можно определить без поиска вовсе. Для таких вероятностных предположений результаты всех процедур, решающих определенный тип задачи, статистически идентичны. Яркий способ описания подобной ситуации, предложенный Дэвидом Уолпертом и Уильямом Г. Макреди в связи с проблемами поиска и оптимизации, заключается в том, что бесплатного обеда не бывает. Ранее Уолперт вывел теоремы о бесплатном обеде для машинного обучения (статистического вывода). До публикации статьи Уолперта Каллен Шаффер независимо доказал ограниченную версию одной из теорем Уолперта и использовал ее для критики текущего состояния исследований в области машинного обучения по проблеме индукции. В метафоре "бесплатного обеда" у каждого "ресторана" (процедуры решения проблем) есть "меню", связывающее каждую "позицию в меню" (задачу) с "ценой" (эффективностью процедуры при решении задачи). Меню ресторанов идентичны, за исключением одного – цены перемешаны от одного ресторана к другому. Для всеядного человека, который с одинаковой вероятностью может заказать любое блюдо, средняя стоимость обеда не зависит от выбора ресторана. Однако вегетарианец, регулярно обедающий с плотоядным, стремящимся к экономии, может заплатить высокую среднюю стоимость за обед. Чтобы методично снизить среднюю стоимость, необходимо заранее знать а) что вы будете заказывать и б) сколько это будет стоить в разных ресторанах. То есть, улучшение эффективности решения проблем зависит от использования априорной информации для сопоставления процедур с задачами. Это условие не всегда точно соблюдается на практике.

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 "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 William G. Macready in connection with the problems of search and 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. This condition does not hold precisely in practice,

Обзор

Некоторые вычислительные задачи решаются путем поиска хороших решений в пространстве кандидатов в решения. Описание того, как последовательно выбирать кандидаты в решения для оценки, называется алгоритмом поиска. Для конкретной задачи различные алгоритмы поиска могут давать разные результаты, но в целом, по всем задачам, они неотличимы друг от друга. Следовательно, если алгоритм демонстрирует превосходные результаты для некоторых задач, он должен компенсировать это худшими результатами для других задач. В этом смысле в поиске не бывает бесплатных решений. Результаты теоремы "нет бесплатного обеда" указывают на то, что подбор алгоритмов к задачам обеспечивает более высокую среднюю производительность, чем применение фиксированного алгоритма ко всем задачам. Игель и Туссент.

Вулперт и Макреди утверждают, что алгоритм никогда не переоценивает кандидата в решение, и что производительность алгоритма измеряется по выходным данным. Например, если каждый кандидат в решение кодируется как последовательность из 300 нулей и единиц, а значения пригодности – 0 и 1, то сложность Колмогорова большинства целевых функций составляет не менее 2300 бит, что превышает предел Ллойда в 1090 ≈ 2299 бит. Следовательно, исходная теорема "нет бесплатного обеда" неприменима к тому, что может быть сохранено в физическом компьютере; вместо этого необходимо применять так называемые "уточненные" теоремы "нет бесплатного обеда". Также было показано, что результаты теоремы "нет бесплатного обеда" применимы к невычислимым функциям.

Формальный обзор

является множеством всех целевых функций f:X→Y, где X – конечное пространство решений, а Y – конечный частично упорядоченный набор. Множество всех перестановок X обозначается J. Случайная величина F распределена на . Для всех j из J, F o j является случайной величиной, распределенной на , с P(F o j = f) = P(F = f o j⁻¹) для всех f из . Пусть a(f) обозначает выход поискового алгоритма a при входных данных f. Если a(F) и b(F) имеют одинаковое распределение для всех поисковых алгоритмов a и b, то F имеет NFL-распределение. Это условие выполняется тогда и только тогда, когда F и F o j имеют одинаковое распределение для всех j из J. Теоретические теоремы NFL о множествах недавно были обобщены на произвольную кардинальность X и Y.

Происхождение

Вулперт и Макреди формулируют две основные теоремы НФЛ: первая относится к объективным функциям, которые не изменяются в процессе поиска, а вторая – к объективным функциям, которые могут изменяться. Необходимо сделать несколько замечаний: теоретически существует почти универсальный оптимизатор общего назначения. Каждый алгоритм поиска хорошо работает почти на всех объективных функциях.

Соэволюция

Вулперт и Макреди доказали, что в коэволюционной оптимизации существуют ситуации, когда все выигрывают. Их анализ охватывает проблемы "игры с самим собой". В этих задачах группа игроков совместно работает над созданием чемпиона, который затем соревнуется с одним или несколькими противниками в последующей многопользовательской игре. Иными словами, цель состоит в получении сильного игрока, но без наличия целевой функции. Эффективность каждого игрока (кандидата в решения) оценивается по результатам его игры против других. Алгоритм стремится использовать игроков и их игровые показатели для получения еще более сильных игроков. Игрок, признанный алгоритмом лучшим, становится чемпионом. Вулперт и Макреди показали, что некоторые коэволюционные алгоритмы в целом превосходят другие по качеству получаемых чемпионов. Создание чемпиона посредством игры с самим собой представляет интерес для эволюционных вычислений и теории игр. Полученные результаты неприменимы к коэволюции биологических видов, поскольку она не предполагает выявления победителей.