Никакого бесплатного обеда в поиске и оптимизации

редактировать

Стоимость решения, усредненная по всем задачам в классе, одинакова для любого метода решения

проблема состоит в том, чтобы быстро найти решение среди кандидатов a, b и c, которое было бы таким же хорошим, как и любое другое, где качество равно 0 или 1. Существует восемь экземпляров («обеденных тарелок») fxyz проблемы, где x, y, и z указывают на качество a, b и c соответственно. Процедура («ресторан») A оценивает кандидатов в порядке a, b, c, а B оценивает кандидатов в обратном порядке, но каждый «взимает» 1 оценку в 5 случаях, 2 оценки в 2 случаях и 3 оценки в 1 случае..

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

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

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

Содержание

1 Обзор
2 Нет бесплатного обеда (NFL)
- 2.1 NFL и случайность Колмогорова
3 Формальный синопсис НФЛ
4 Исходные теоремы НФЛ
5 Интерпретации результатов НФЛ
6 Коэволюционные бесплатные обеды
7 См. также
8 Примечания
9 Внешние ссылки

Обзор

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

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

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

Нет бесплатного обеда (NFL)

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

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

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

Исходные теоремы о запрете на бесплатный обед (NFL) предполагают, что все целевые функции с одинаковой вероятностью будут входить в алгоритмы поиска. С тех пор было установлено, что NFL существует тогда и только тогда, когда, грубо говоря, "перемешивание" целевых функций не влияет на их вероятности. Хотя это условие для НФЛ физически возможно, утверждалось, что оно определенно не выполняется точно.

Очевидная интерпретация «не НФЛ» - это «бесплатный обед», но это вводит в заблуждение. НФЛ - это вопрос степени, а не принцип «все или ничего». Если условие для NFL выполняется приблизительно, то все алгоритмы дают примерно одинаковые результаты по всем целевым функциям. «Не NFL» означает только то, что алгоритмы в целом неэквивалентны по некоторой степени производительности. Для интересующей меры производительности алгоритмы могут оставаться эквивалентными или почти эквивалентными.

NFL и случайность Колмогорова

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

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

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

Формальный синопсис NFL

$YX {\ displaystyle Y ^ {X}}$ $Y ^ X$ - это набор всех целевых функций f: X → Y, где $X {\ displaystyle X}$ $X$ - это конечное пространство решений, а $Y {\ displaystyle Y}$ $Y$ - конечное poset. Набор всех перестановок X равен J. случайная величина F распределяется по $Y X {\ displaystyle Y ^ {X}}$ $Y ^ X$ . Для всех j в J, F oj является случайной величиной, распределенной на $YX {\ displaystyle Y ^ {X}}$ $Y ^ X$ , причем P (F oj = f) = P (F = foj) для все f в $YX {\ displaystyle Y ^ {X}}$ $Y ^ X$ .

Пусть a (f) обозначает выход алгоритма поиска a на входе f. Если a (F) и b (F) одинаково распределены для всех поисковых алгоритмов a и b, то F имеет распределение NFL. Это условие выполняется тогда и только тогда, когда F и F o j одинаково распределены для всех j в J. Другими словами, нет бесплатного обеда для алгоритмов поиска тогда и только тогда, когда распределение целевых функций инвариантно относительно перестановки пространства решений. Теоретико-множественные теоремы НФЛ недавно были обобщены на произвольную мощность $X {\ displaystyle X}$ $X$ и $Y {\ displaystyle Y}$ $Y$ .

Исходные теоремы НФЛ

Вольперт и Макреди приводят две основные теоремы NFL: первая касается целевых функций, которые не меняются во время поиска, а вторая - целевых функций, которые могут измениться.

Теорема 1: Для любой пары алгоритмов a 1 и a 2

∑ е P (dmy | f, m, a 1) = ∑ f P (dmy | f, m, a 2), {\ displaystyle \ sum _ {f} P (d_ {m} ^ {y} | f, m, a_ {1}) = \ sum _ {f} P (d_ {m} ^ {y} | f, m, a_ {2}),}

\ sum _ {f} P (d_ {m} ^ {y} | f, m, a_ {1}) = \ sum _ {f} P (d_ {m} ^ {y} | f, m, a_ {2}),

где $dmy {\ displaystyle d_ {m} ^ {y}}$ $d_ {m} ^ {y}$ обозначает упорядоченный набор размеров $m {\ displaystyle m}$ $m$ значений затрат $y ∈ Y {\ displaystyle y \ in Y}$ $y \ in Y$ , связанный с входными значениями $x ∈ X {\ displaystyle x \ in X}$ $x \ in X$ , $f: X → Y {\ displaystyle f: X \ rightarrow Y}$ $f: X \ rightarrow Y$ - оптимизируемая функция и $P (dmy | f, m, a) {\ displaystyle P (d_ {m} ^ {y} | f, m, a)}$ $P (d_ {m} ^ {y} | f, m, a)$ - условная вероятность получения заданной последовательности значений стоимости из алгоритма $a {\ displaystyle a}$ $a$ run $m {\ displaystyle m}$ $m$ раз для функции $f {\ displaystyle f}$ $f$ .

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

Интерпретации результатов НФЛ

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

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

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

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

Практически для всех целевых функций специализация по существу случайна. Несжимаемые, или случайные по Колмогорову, целевые функции не имеют регулярности, которую мог бы использовать алгоритм, что касается универсальной обработки Тьюринга, используемой для определения случайности Колмогорова. Итак, предположим, что есть один, явно лучший выбор - универсальная машина Тьюринга. Тогда при заданной целевой функции, несжимаемой для этой машины Тьюринга, нет оснований для выбора между двумя алгоритмами, если оба являются сжимаемыми, как измерено с помощью этой машины Тьюринга. Если выбранный алгоритм работает лучше большинства, результат - случайность. Случайная функция Колмогорова не имеет представления меньше, чем таблица поиска, которая содержит (случайное) значение, соответствующее каждой точке в пространстве поиска; любая функция, которую можно выразить более компактно, по определению не является случайностью Колмогорова.

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

Результаты НФЛ не указывают на то, что бесполезно пытаться решать проблемы с неспециализированными алгоритмами. Никто не определил долю практических задач, для которых алгоритм быстро дает хорошие результаты. И есть практический бесплатный обед, нисколько не противоречащий теории. Выполнение алгоритма на компьютере стоит очень мало по сравнению с человеческими затратами и преимуществом хорошего решения. Если алгоритму удается найти удовлетворительное решение за приемлемое время, небольшие вложения принесут большую отдачу. Если алгоритм не работает, то мало что теряется.

Коэволюционные бесплатные обеды

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

См. Также

Примечания

Внешние ссылки