Никаких бесплатных обедов в поиске и оптимизации - No free lunch in search and optimization

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

В вычислительная сложность и оптимизация то нет теоремы о бесплатном обеде результат, который утверждает, что для определенных типов математических задач вычислительная стоимость нахождения решения, усредненное по всем задачам в классе, одинаково для любого метода решения. Следовательно, никакое решение не предлагает "короткого пути". Это сделано в предположении, что пространство поиска является функцией плотности вероятности. Это не относится к случаю, когда пространство поиска имеет базовую структуру (например, является дифференцируемой функцией), которую можно использовать более эффективно (например, Метод Ньютона в оптимизации ), чем случайный поиск, или даже имеет решения в замкнутой форме (например, экстремумы квадратичного многочлена), которые могут быть определены вообще без поиска. Для таких вероятностных допущений результаты всех процедур, решающих конкретный тип проблемы, статистически идентичны. Красочный способ описания такого обстоятельства, введенный Дэвид Вольперт и Уильям Дж. Макреди в связи с проблемами поиска[1]и оптимизация,[2]это сказать, что нет бесплатного обеда. Вольперт ранее не выводил теоремы о бесплатном обеде для машинное обучение (статистические выводы ).[3] До того, как статья Вольперта была опубликована, Каллен Шаффер независимо доказал ограниченную версию одной из теорем Вольперта и использовал ее для критики текущего состояния исследований в области машинного обучения по проблеме индукции.[4]

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

Формально бесплатного обеда не бывает, когда распределение вероятностей на проблемных экземплярах такова, что все решатели задач имеют одинаково распределенные результаты. На случай, если поиск, проблемный экземпляр - это целевая функция, и в результате последовательность значений, полученных при оценке возможные решения в домен функции. Для типичной интерпретации результатов поиск - это оптимизация процесс. Бесплатного обеда в поиске нет тогда и только тогда, когда распределение по целевым функциям инвариантный под перестановка пространства возможных решений.[5][6][7] На практике это условие не выполняется,[6] но теорема "(почти) без бесплатного обеда" предполагает, что это приблизительно верно.[8]

Обзор

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

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

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

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

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

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

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

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

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

НФЛ и колмогоровская случайность

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

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

Практически все целевые функции имеют такие высокие Колмогоровская сложность что они не могут храниться на конкретном компьютере.[5][7][11] Точнее, если мы смоделируем данный физический компьютер как регистровую машину с памятью заданного размера порядка памяти современных компьютеров, то большинство объективных функций не могут быть сохранены в их памяти. Типичная целевая функция или алгоритм содержит больше информации, чем Сет Ллойд оценивает, что наблюдаемая Вселенная способна регистрировать.[12] Например, если каждое возможное решение закодировано как последовательность из 300 нулей и единиц, а значения качества равны 0 и 1, то большинство целевых функций имеют колмогоровскую сложность не менее 2300 биты[13] и это больше, чем оценка Ллойда 1090 ≈ 2299 биты. Отсюда следует, что исходная теорема «без бесплатного обеда» неприменима к тому, что может храниться на физическом компьютере; вместо этого нужно применять так называемые «ужесточенные» теоремы об отсутствии бесплатного обеда. Также было показано, что результаты NFL применимы к невычислимым функциям. [14].

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

это набор всех целевые функции ж:Икс→Y, где конечный пространство решений и конечный посеть. Набор всех перестановки из Икс является J. А случайная переменная F распространяется на . Для всех j в J, F о j случайная величина, распределенная на , причем P (F о j = ж) = P (F = ж о j−1) для всех ж в .

Позволять а(ж) обозначают вывод алгоритма поиска а на входе ж. Если а(F) и б(F) одинаково распределены для всех поисковых алгоритмов а и б, тогда F имеет Распределение НФЛ. Это условие выполняется тогда и только тогда, когда F и F о j одинаково распределяются для всех j в J.[6][7] Другими словами, для алгоритмов поиска нет бесплатного обеда тогда и только тогда, когда распределение целевых функций инвариантно относительно перестановки пространства решений.[15] Теоретико-множественные теоремы НФЛ недавно были обобщены на произвольную мощность. и .[16]

Оригинальные теоремы NFL

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

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

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

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

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

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

  • Теоретически существует универсальный оптимизатор общего назначения. Каждый алгоритм поиска хорошо работает практически со всеми целевыми функциями.[11] Так что, если вас не беспокоят «относительно небольшие» различия между алгоритмами поиска, например, из-за того, что компьютерное время дешево, то вам не следует беспокоиться о бесплатном обеде.
  • Алгоритм может превзойти другой алгоритм, если ни один из них не специализируется на решении этой проблемы. Действительно, может оказаться, что оба алгоритма являются одними из худших для решения проблемы. В более общем плане Вольперт и Макреди разработали меру степени «согласованности» между алгоритмом и распределением проблем (строго говоря, внутренним продуктом).[2] Сказать, что один алгоритм соответствует распределению лучше, чем другой, не означает, что любой из них был сознательно специализирован для этого распределения; у алгоритма может быть хорошее согласование просто по счастливой случайности.
  • На практике некоторые алгоритмы переоценивают возможные решения. Причина, по которой следует учитывать производительность только кандидатов, никогда ранее не оценивавшихся, состоит в том, чтобы убедиться, что при сравнении алгоритмов сравниваются яблоки с яблоками. Более того, любое превосходство алгоритма, который никогда не переоценивает кандидатов, над другим алгоритмом, который делает это для конкретной проблемы, может не иметь ничего общего со специализацией этой проблемы.
  • Практически для всех целевых функций специализация по сути случайна. Несжимаемый, или Колмогоров случайный, целевые функции не имеют регулярности, которую мог бы использовать алгоритм, что касается универсальной обработки Тьюринга, используемой для определения случайности Колмогорова. Итак, предположим, что есть один, явно лучший выбор - универсальная машина Тьюринга. Тогда при заданной целевой функции, несжимаемой для этой машины Тьюринга, нет оснований для выбора между двумя алгоритмами, если оба являются сжимаемыми, как измерено с помощью этой машины Тьюринга. Если выбранный алгоритм работает лучше, чем большинство, результат - случайность.[11] Случайная функция Колмогорова не имеет представления меньше, чем таблица поиска, которая содержит (случайное) значение, соответствующее каждой точке в пространстве поиска; Любые Функция, которую можно выразить более компактно, по определению не является случайной по Колмогорову.

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

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

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

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

Смотрите также

Примечания

  1. ^ а б Wolpert, D. H .; Макреди, В. Г. (1995). «Теоремы о запрете бесплатного обеда для поиска» (PDF). Технический отчет SFI-TR-95-02-010. Институт Санта-Фе.
  2. ^ а б c d е ж г Wolpert, D. H .; Макреди, В. Г. (1997). «Теоремы об отсутствии бесплатного обеда для оптимизации» (PDF). IEEE Transactions по эволюционным вычислениям. 1: 67.
  3. ^ Вольперт, Дэвид (1996). «Отсутствие априорных различий между алгоритмами обучения» (PDF). Нейронные вычисления. С. 1341–1390.
  4. ^ а б c Шаффер, Каллен (1994). «Закон сохранения для обобщения производительности» (PDF). В Willian, H .; Коэн, У. (ред.). Международная конференция по машинному обучению. Сан-Франциско: Морган Кауфманн. С. 259–265.
  5. ^ а б Стритер, М. (2003) "Два широких класса функций, для которых не действует результат без бесплатного обеда," Генетические и эволюционные вычисления - GECCO 2003С. 1418–1430.
  6. ^ а б c d е ж г Игель, К., и Туссент, М. (2004) "Теорема об отсутствии бесплатного обеда для неравномерного распределения целевых функций," Журнал математического моделирования и алгоритмов 3С. 313–322.
  7. ^ а б c d е ж г час я Инглиш, Т. (2004) Нет больше обеда: анализ последовательного поиска, Материалы Конгресса IEEE 2004 г. по эволюционным вычислениямС. 227–234.
  8. ^ а б c С. Дросте, Т. Янсен, И. Вегенер. 2002. "Оптимизация с помощью эвристики рандомизированного поиска: (A) теорема NFL, реалистичные сценарии и сложные функции," Теоретическая информатика, т. 287, нет. 1. С. 131–144.
  9. ^ а б c d Wolpert, D.H., and Macready, W.G. (2005) "Коэволюционные бесплатные обеды," IEEE Transactions по эволюционным вычислениям, 9(6): 721–735
  10. ^ Алгоритм поиска также выводит последовательность оцененных возможных решений, но этот вывод не используется в этой статье.
  11. ^ а б c d е Английский, Т. М. (2000). «Оптимизация - это просто, а обучение типичной работе - трудное дело». Труды Конгресса 2000 г. по эволюционным вычислениям: CEC00: 924–931. Дои:10.1109 / CEC.2000.870741.
  12. ^ Ллойд, С. (2002). «Вычислительная мощность Вселенной». Письма с физическими проверками. 88: 237901–237904. arXiv:Quant-ph / 0110141. Дои:10.1103 / PhysRevLett.88.237901.
  13. ^ Li, M .; Витани, П. (1997). Введение в колмогоровскую сложность и ее приложения (2-е изд.). Нью-Йорк: Спрингер. ISBN  0-387-94868-6.
  14. ^ Вудворд, Джон Р. (2009). «Вычислимые и невычислимые функции и алгоритмы поиска». Международная конференция IEEE по интеллектуальным вычислениям и интеллектуальным системам, 2009 г.. 1. IEEE. С. 871–875.
  15. ^ Часть «только если» была впервые опубликована Шумахер, К. В. (2000). Поиск в черном ящике: структура и методы (Кандидатская диссертация). Университет Теннесси, Ноксвилл. ProQuest  304620040.
  16. ^ Роу; Восе; Райт. «Новая интерпретация отсутствия бесплатного обеда». Эволюционные вычисления. 17 (1): 117–129.
  17. ^ Ho, Y.C .; Пепайн, Д. Л. (2002). «Простое объяснение теоремы об отсутствии бесплатного обеда и ее последствия». Журнал теории оптимизации и приложений. 115: 549–570. Дои:10.1023 / А: 1021251113462.

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