Теорема «Бесплатных обедов не бывает» в поиске и оптимизации

Теорема «Бесплатных обедов не бывает» — это утверждение, что для определённого типа математических задач средняя нахождения решения, рассчитанная по всем задачам данного класса, одинакова для любого метода решения. Название отсылает к высказыванию «Бесплатных обедов не бывает», подразумевая, что ни один метод не предоставляет «короткого пути». Это справедливо при условии, что пространство поиска представляет собой функцию плотности вероятности. Однако теорема не применима в случаях, когда пространство поиска обладает внутренней структурой (например, является дифференцируемой функцией), которую можно использовать (например, ) более эффективно, чем случайный поиск, или даже имеет аналитические решения (например, экстремумы квадратичного многочлена), которые можно определить без какого-либо поиска. При таких вероятностных допущениях результаты всех процедур, решающих конкретный тип проблемы, статистически идентичны. Красочное описание таких обстоятельств дали Дэвид Волперт и Уильям Джю Макреди в связи с задачами поиска и оптимизации, сказав: «бесплатных обедов не бывает». Ранее Уолперт уже выводил теоремы «бесплатных обедов не бывает» для машинного обучения (статистический вывод). До появления статья Волпета Каллен Шаффер независимо доказал ограниченную версию одной из теорем Вольперта и использовал её для критики текущего состояния исследований в области машинного обучения по проблеме индукции.

В метафоре «бесплатных обедов не бывает» каждый «ресторан» (процедура решения задачи) имеет «меню», которое связывает каждое «блюдо» (задачу) с «ценой» (эффективностью процедуры при решении этой задачи). Меню ресторанов идентичны, за исключением одного аспекта – цены на блюда в разных ресторанах перетасованы. всеядного человека, который с равной вероятностью выберет любое блюдо, средняя стоимость обеда не зависит от выбора ресторана. Однако веган, который регулярно обедает с экономным любителем мяса, может заплатить высокую среднюю стоимость за обед. Чтобы методично снизить среднюю стоимость, необходимо использовать предварительные знания о том a) что будет заказано и b) сколько это будет стоить в различных ресторанах. Иными словами, улучшение эффективности решения задач зависит от использования предыдущей информации для сопоставления процедур с задачами.

На формальном языке, бесплатных обедов не бывает, когда распределение вероятностей на экземплярах задач таково, что все решатели задач получают идентично распределённые результаты. В контексте поиска экземпляром задачи является конкретная целевая функция, а результатом является последовательность значений, полученных при оценке кандидатов на решение из область определения функции. При типичных интерпретациях результатов поиск представляет собой процесс оптимизации. бесплатных обедов не бывает тогда и только тогда, когда распределение целевых функций инвариантно относительно перестановок пространства возможных решений. Это условие на практике не выполняется в точности, однако теорема об «(почти) отсутствии бесплатного обеда» предполагает, что оно выполняется приблизительно.

Обзор

Некоторые вычислительные задачи решаются путём поиска оптимальных решений в пространстве возможных вариантов. Описание того, как последовательно выбирать эти варианты для оценки, называется алгоритмом поиска. На конкретной задаче различные алгоритмы поиска могут дать различные результаты, но в целом, если рассматривать все задачи, они неотличимы друг от друга. Отсюда следует, что если алгоритм показывает превосходные результаты в одних задачах, то он неизбежно будет уступать в других. В этом смысле в поиске нет бесплатных обедов. Шаффер выражает это, говоря о сохранении производительности поиска. Обычно поиск интерпретируется как оптимизация, что приводит к выводу о том, что в оптимизации также не бывает «бесплатного обеда».

Теорема Вольперта и Макриди «бесплатных обедов не бывает», как они сами её сформулировали простым языком, гласит, что «любые два алгоритма эквивалентны, если их производительность усредняется по всем возможным задачам». Это означает, что подбор алгоритмов под конкретные задачи обеспечивает более высокую среднюю производительность, чем применение одного и того же алгоритма ко всем задачам. Игель и Туссен, а также Инглиш установили общее условие, при котором нет бесплатного обеда. Хотя это физически возможно, на практике оно не выполняется в точности. Дросте, Янсен и Вегенер доказали теорему, которую они интерпретируют как указание на то, что на практике «бесплатного обеда (почти) не бывает».

Чтобы сделать это более наглядным, рассмотрим специалиста по оптимизации, столкнувшегося с проблемой. Обладая некоторыми знаниями о происхождении проблемы, он может использовать их при выборе алгоритма, который хорошо справится с её решением. Если же специалист не понимает, как использовать эти знания, или вовсе их не имеет, то перед ним встаёт вопрос: лучше ли одни алгоритмы по сравнению с другими при решении реальных задач в целом? Авторы теоремы «(почти) нет бесплатного обеда» утверждают, что ответ, по сути, отрицательный, но признают некоторые оговорки относительно того, применима ли теорема на практике.

Теоремы

«Задача», если говорить более формально, представляет собой целевую функцию, которая отображает варианты решений в значения полезности. Алгоритм поиска принимает целевую функцию в качестве входа и оценивает варианты решений поочерёдно. Результатом работы является последовательность наблюдаемых значения полезности

Вольперт и Макриди оговаривают, что алгоритм никогда не оценивает повторно вариант решения, а производительность алгоритма измеряется по выходным данным. Для простоты мы запрещаем случайность в алгоритмах. При таких условиях, когда алгоритм поиска запускается на каждом возможном входе, он генерирует каждый возможный выход ровно один раз. Поскольку производительность измеряется по выходным данным, алгоритмы неотличимы по тому, как часто они достигают определённых уровней производительности.

Некоторые показатели производительности демонстрируют, насколько хорошо поисковые алгоритмы справляются с оптимизацией целевой функции. Действительно, в рассматриваемом классе интересных применений для поисковых алгоритмов, кроме задач оптимизации, не наблюдается. Распространённой мерой производительности является наименьший индекс наименьшего значения в выходной последовательности. Это количество вычислений, необходимых для минимизации целевой функции.

Теоремы об отсутствии бесплатного обеда (ОБО) изначально предполагали, что все целевые функции имеют одинаковую вероятность быть входными данными для алгоритмов поиска. С тех пор было установлено, что ОБО существует тогда и только тогда, когда, грубо говоря, «перемешивание» целевых функций не влияет на их вероятности. Хотя это условие для ОБО физически возможно, утверждается, что оно, безусловно, не выполняется точно.

Очевидная интерпретация «не ОБО» как «бесплатного обеда» ошибочна, но вводит в заблуждение. ОБО — это вопрос степени, а не констатация «всё или ничего». Если условия ОБО приблизительно выполняются, то все алгоритмы дают примерно одинаковые результаты для всех целевых функций. «Не ОБО» означает лишь, что алгоритмы в целом неравноценны по некоторой мере производительности. Однако для конкретной интересующей меры производительности алгоритмы могут оставаться эквивалентными или почти таковыми.

Колмогоровская случайность

Почти все элементы множества всех возможных функций (в теоретико-множественном смысле) являются колмогоровски случайными, а значит, теоремы ОБО применимы к множеству функций, почти все из которых не могут быть выражены более компактно, чем в виде таблицы поиска, содержащей отдельную (и случайную) запись для каждой точки в пространстве поиска. Функции, которые могут быть выражены более компактно (например, математическим выражением разумного размера) по определению не являются колмогоровски случайными.

Кроме того, в множестве всех возможных целевых функций уровни «хорошести» равномерно распределены среди потенциальных решений, поэтому хорошие решения разбросаны по всему пространству кандидатов. Следовательно, алгоритм поиска редко будет оценивать малую долю кандидатов, прежде чем найти очень хорошее решение.

Почти все целевые функции обладают настолько высокой колмогоровской сложностью, что их невозможно сохранить на конкретном компьютере. Точнее, если мы моделируем физический компьютер как регистровую машину с заданным объёмом памяти, сопоставимым с современными компьютерами, то большинство целевых функций невозможно разместить в его памяти. В типичной целевой функции или алгоритме имеется больше информации, чем, по оценкам Сета Ллойда способна зарегистрировать наблюдаемая Вселенная. Например, если каждый вариант решения кодируется как последовательность из 300 нулей и единиц, а значения «хорошести» равны 0 и 1, то большинство целевых функций имеют колмогоровскую сложность по меньшей мере 2300 бит, и это больше чем оценка Ллойда 1090 ≈ 2299 бит. Отсюда следует, что исходная теорема «бесплатных обедов не бывает» не применима к тому, что может быть сохранено на физическом компьютере. Вместо этого необходимо применять так называемые «уточнённые» теоремы «бесплатного обеда не бывает». Также было показано, что результаты ОБО применимы и к невычислимым функциям.

Формальное изложение

— это множество всех целевых функций целевых функций f:X→Y, где конечное пространство решений, а — конечное частично упорядоченное множество. J — это множество всех перестановок X. Случайная величина F распределена на . Для любого j из J F o j является случайной величиной, распределённой на , причём P(F o j = f) = P(F = f o j−1) для всех f в .

Пусть a(f) обозначает выход алгоритма поиска a на входе f. Если a(F) и b(F) одинаково распределены для всех алгоритмов поиска a и b, тогда F имеет ОБО распределение. Это условие выполняется тогда и только тогда, когда F и F o j одинаково распределены для всех . Другими словами, «бесплатных обедов не бывает» для алгоритмов поиска тогда и только тогда, когда распределение целевых функций инвариантно относительно перестановок области допустимых решений. Теоретико-множественные теоремы ОБО были недавно обобщены на произвольные мощности и .

Истоки

Вольперт и Макриди дали две основные теоремы ОБО («бесплатных обедов не бывает»). Первая касается целевых функций которые не изменяются в процессе поиска, а вторая — целевых функций, которые меняться могут.

Теорема 1: Для любой пары алгоритмов a1 и a2 , где означает упорядоченное множество размера значений стоимости , ассоциированных с входными значениями , — оптимизируемая функция, а — условная вероятность получения заданной последовательности значений стоимости из алгоритма выполненного раз на функции .

По сути, это означает, что когда все функции f равновероятны, вероятность наблюдения произвольной последовательности из m значений в ходе поиска не зависит от алгоритма поиска.

Второй теоремой устанавливается «более тонкий» результат ОБО для зависящих от времени целевых функций.

Интерпретация результатов

Распространённое, хотя и не совсем точное, толкование результатов ОБО заключается в том, что «универсальная стратегия оптимизации общего назначения теоретически невозможна, и единственный способ, которым одна стратегия может превзойти другую, — это если она специализирована для конкретной рассматриваемой проблемы». Здесь уместно несколько замечаний:

Теоретически существует почти универсальный оптимизатор общего назначения. Любой алгоритм поиска хорошо работает почти на всех целевых функциях. Таким образом, если вас не беспокоят «относительно небольшие» различия между алгоритмами поиска, из-за дешевизны компьютерного времени, то вам не стоит беспокоиться о принципе «бесплатного обеда не бывает».