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

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

Проблема состоит в том, чтобы быстро найти решение среди кандидатов a, b и c, которое не хуже любого другого, где качество равно 0 или 1. Существует восемь случаев («обеденных тарелок») f xyz задачи, где x , y и 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]

Теоремы

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

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

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

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

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

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

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

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

Почти все целевые функции имеют настолько высокую колмогоровскую сложность , что их невозможно хранить в конкретном компьютере. ^{[5] [7] [11]} Точнее, если мы моделируем данный физический компьютер как регистровую машину с заданным размером памяти порядка памяти современных компьютеров, то большинство целевых функций не могут храниться в их памяти. В типичной целевой функции или алгоритме содержится больше информации, чем, по оценкам Сета Ллойда, способна зарегистрировать наблюдаемая Вселенная. ^[12] Например, если каждое возможное решение закодировано как последовательность из 300 0 и 1, а значения качества равны 0 и 1, то большинство целевых функций имеют колмогоровскую сложность не менее 2300 ^бит , ^[13] и это больше границы Ллойда, равной 10 ⁹⁰ ≈ 2 ²⁹⁹ бит. Отсюда следует, что первоначальная теорема «без бесплатного обеда» не применима к тому, что может храниться на физическом компьютере; вместо этого необходимо применять так называемые «ужесточенные» теоремы об отсутствии бесплатных обедов. Также было показано, что результаты НФЛ применимы к невычислимым функциям. ^[14]

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

${\displaystyle Y^{X}}$— множество всех целевых функций f : X → Y , где — конечное пространство решений , а — конечное частично упорядоченное множество . Множество всех перестановок X — это J. Случайная величина F распределена на . Для всех j в J F o j является случайной величиной, распределенной на , причем P( F o j = f ) = P ( F = f o j ⁻¹ ) для всех f в . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y^{X}}$ ${\displaystyle Y^{X}}$ ${\displaystyle Y^{X}}$

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

Источник

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

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

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

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

Вторая теорема устанавливает «более тонкий» результат НФЛ для изменяющихся во времени целевых функций. ^[2]

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

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

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

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

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

Недавно некоторые философы науки заявили, что существуют способы обойти теорему о бесплатном обеде, используя «метаиндукцию». Вулперт обращается к этим аргументам в ^[18] .

Коэволюция

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

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

• Индуктивное смещение
• бритва Оккама
• Простота
• Теорема о гадком утенке

Примечания

1. Вулперт, Д.Х.; Макреди, WG (1995). «Теоремы о бесплатном обеде для поиска отсутствуют». Технический отчет СФИ-ТР-95-02-010 . Институт Санта-Фе. S2CID  12890367.
2. Вулперт, DH; Макриди, WG (1997). «Теоремы об оптимизации не требуют бесплатного обеда». Транзакции IEEE в эволюционных вычислениях . 1 : 67–82. CiteSeerX 10.1.1.138.6606 . дои : 10.1109/4235.585893. S2CID  5553697. 
3. Вулперт, Дэвид (1996). «Отсутствие априорных различий между алгоритмами обучения». Нейронные вычисления . Том. 8. стр. 1341–1390. дои : 10.1162/neco.1996.8.7.1341. S2CID  207609360.
4. Шаффер, Каллен (1994). «Закон сохранения эффективности обобщения» (PDF) . В Виллиане, Х.; Коэн, В. (ред.). Международная конференция по машинному обучению . Сан-Франциско: Морган Кауфманн. стр. 259–265.
5. Стритер, М. (2003) «Два широких класса функций, для которых не справедлив результат отсутствия бесплатного обеда», Генетические и эволюционные вычисления – GECCO 2003 , стр. 1418–1430.
6. Игель, К., и Туссен, М. (2004) «Теорема об отсутствии бесплатного обеда для неравномерных распределений целевых функций», Журнал математического моделирования и алгоритмов 3 , стр. 313–322.
7. English, T. (2004) No More Lunch: Анализ последовательного поиска, Труды Конгресса IEEE 2004 года по эволюционным вычислениям , стр. 227–234.
8. С. Дросте, Т. Янсен и И. Вегенер. 2002. «Оптимизация с помощью эвристики рандомизированного поиска: теорема (A) НФЛ, реалистичные сценарии и сложные функции», Theoretical Computer Science, vol. 287, нет. 1, стр. 131–144.
9. Wolpert, DH, и Macready, WG (2005) «Коэволюционные бесплатные обеды», IEEE Transactions on Evolutionary Computation , 9 (6): 721–735.
10. Алгоритм поиска также выводит последовательность оцененных возможных решений, но этот вывод не используется в этой статье.
11. English, TM (2000). «Оптимизация обычной функции проста, а обучение сложно». Материалы Конгресса 2000 г. по эволюционным вычислениям. CEC00 (Кат. номер 00TH8512) . Том. 2. С. 924–931. дои : 10.1109/CEC.2000.870741. ISBN 0-7803-6375-2. S2CID  11295575.
12. Ллойд, С. (2002). «Вычислительная мощность Вселенной». Письма о физических отзывах . 88 (23): 237901–237904. arXiv : Quant-ph/0110141 . Бибкод : 2002PhRvL..88w7901L. doi : 10.1103/PhysRevLett.88.237901. PMID  12059399. S2CID  6341263.
13. Ли, М.; Витаньи, П. (1997). Введение в колмогоровскую сложность и ее приложения (2-е изд.). Нью-Йорк: Спрингер. ISBN 0-387-94868-6.
14. Вудворд, Джон Р. (2009). «Вычислимые и невычислимые функции и алгоритмы поиска». Международная конференция IEEE по интеллектуальным вычислениям и интеллектуальным системам, 2009 г. Том. 1. ИИЭР. стр. 871–875. CiteSeerX 10.1.1.158.7782 . 
15. Часть «только если» была впервые опубликована Шумахером, CW (2000). Поиск в черном ящике: рамки и методы (кандидатская диссертация). Университет Теннесси, Ноксвилл. ПроКвест  304620040.
16. Роу; Восе; Райт (2009). «Переосмысление отсутствия бесплатных обедов». Эволюционные вычисления . 17 (1): 117–129. дои : 10.1162/evco.2009.17.1.117. PMID  19207090. S2CID  6251842.
17. Хо, YC; Пепин, Д.Л. (2002). «Простое объяснение теоремы об отсутствии бесплатных обедов и ее последствий». Журнал теории оптимизации и приложений . 115 (3): 549–570. дои : 10.1023/А: 1021251113462. S2CID  123041865.
18. Вулперт, Д.Х. (2023). «Следствие теорем об отсутствии бесплатного обеда для метаиндукции». Журнал общей философии науки . 1 : 67–82. дои : 10.1109/4235.585893. S2CID  5553697.

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

• http://www.no-free-lunch.org
• Рэдклифф и Сарри, 1995, «Фундаментальные ограничения поисковых алгоритмов: эволюционные вычисления в перспективе» (ранняя опубликованная статья о НФЛ, появившаяся вскоре после статьи Шаффера ICML, которая, в свою очередь, была основана на препринте Вулперта; доступна в различных форматах)
• Публикации НФЛ Томаса Инглиша
• Публикации НФЛ Кристиана Игеля и Марка Туссена
• Публикации НФЛ и "бесплатных обедов" Даррелла Уитли
• Старый список публикаций Дэвида Вулперта, Уильяма Макреди и Марио Кеппена по оптимизации и поиску.