Теорема о бесплатном обеде не существует

Математический фольклор

В математическом фольклоре теорема « бесплатного обеда нет » ( NFL ) Дэвида Вулперта и Уильяма Макреди (иногда во множественном числе) намекает на высказывание « бесплатного обеда не бывает », то есть не существует легких путей к успеху. Она появилась в 1997 году в «Теоремах об отсутствии бесплатных обедов для оптимизации». ^[1] Ранее Вулперт вывел теоремы об отсутствии бесплатных обедов для машинного обучения (статистический вывод). ^[2]

В 2005 году Вулперт и Макреди сами указали, что первая теорема в их статье «утверждает, что любые два алгоритма оптимизации эквивалентны, если их производительность усредняется по всем возможным задачам» ^{[3] .}

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

В то время как некоторые ученые утверждают, что NFL передает важную информацию, другие утверждают, что NFL не имеет большого значения для исследований в области машинного обучения. ^{[5] [6] [7]}

Пример

Поставьте игрушечную вселенную, которая существует ровно два дня и в каждый день содержит ровно один объект: квадрат или треугольник. У вселенной есть ровно четыре возможных истории:

1. (квадрат, треугольник): вселенная содержит квадрат в первый день и треугольник во второй день
2. (квадрат, квадрат)
3. (треугольник, треугольник)
4. (треугольник, квадрат)

Любая стратегия прогнозирования, которая успешна для истории №2, предсказывая квадрат на 2-й день, если есть квадрат на 1-й день, потерпит неудачу для истории №1, и наоборот. Если все истории одинаково вероятны, то любая стратегия прогнозирования будет иметь одинаковый балл с той же степенью точности 0,5. ^[8]

Источник

Вулперт и Макреди приводят две теоремы НФЛ, тесно связанные с фольклорной теоремой. В своей статье они утверждают:

Мы назвали связанные с этим результаты теоремами NFL, поскольку они демонстрируют, что если алгоритм хорошо работает на определенном классе задач, то он обязательно расплачивается за это ухудшением производительности на множестве всех остальных задач. ^[1]

Первая теорема предполагает, что целевые функции не меняются в процессе оптимизации, а вторая предполагает, что целевые функции могут изменяться. ^[1]

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

Теорему можно эквивалентно сформулировать следующим образом:

Теорема  —  Дано конечное множество и конечное множество действительных чисел , предположим, что выбирается случайным образом в соответствии с равномерным распределением на множестве всех возможных функций от до . Для задачи оптимизации по множеству ни один алгоритм не работает лучше, чем слепой поиск. ${\displaystyle V}$ ${\displaystyle S}$ ${\displaystyle f:V\to S}$ ${\displaystyle S^{V\!}}$ ${\displaystyle V}$ ${\displaystyle S}$ ${\displaystyle f}$ ${\displaystyle V}$

Здесь слепой поиск означает, что на каждом шаге алгоритма элемент выбирается случайным образом с равномерным распределением вероятностей из элементов, которые ранее не выбирались. ${\displaystyle v\in V}$ ${\displaystyle V}$

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

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

Мотивация

Теоремы NFL явно не мотивировались вопросом о том, что можно вывести (в случае NFL для машинного обучения) или найти (в случае NFL для поиска), когда «среда является однородной случайной». Скорее однородная случайность использовалась в качестве инструмента для сравнения количества сред, для которых алгоритм A превосходит алгоритм B, с количеством сред, для которых B превосходит A. NFL говорит нам, что (соответствующим образом взвешено) ^{[ необходимо разъяснение ]} в обоих этих наборах одинаковое количество сред.

Это справедливо для многих определений того, что именно представляет собой «среда». В частности, существует столько же априорных распределений (соответствующим образом взвешенных), в которых алгоритм обучения A превосходит B (в среднем), сколько и наоборот. ^{[ необходима цитата ]} Это утверждение о наборах априорных распределений является наиболее важным в NFL, а не тот факт, что любые два алгоритма работают одинаково для одного конкретного априорного распределения, которое назначает равную вероятность всем средам.

Хотя NFL важен для понимания фундаментального ограничения для набора проблем, он ничего не говорит о каждом конкретном случае проблемы, которая может возникнуть на практике. То есть, NFL говорит о том, что содержится в его математических утверждениях, и это не более того. Например, он применяется к ситуациям, когда алгоритм фиксируется априори, а наихудшая проблема для фиксированного алгоритма выбирается апостериори. Поэтому, если у нас есть «хорошая» проблема на практике или если мы можем выбрать «хороший» алгоритм обучения для данного конкретного случая проблемы, то NFL не упоминает никаких ограничений относительно этого конкретного случая проблемы. Хотя NFL может показаться противоречивым результатам из других статей, предлагающих обобщение алгоритмов обучения или эвристики поиска, важно понимать разницу между точной математической логикой NFL и ее интуитивной интерпретацией. ^[9]

Подразумеваемое

Чтобы проиллюстрировать одно из контринтуитивных следствий NFL, предположим, что мы фиксируем два контролируемых алгоритма обучения, C и D. Затем мы выбираем целевую функцию f для создания набора пар вход-выход, d . Вопрос в том, как нам следует выбирать, обучать ли C или D на d , чтобы делать прогнозы относительно того, какой выход будет связан с точкой, лежащей за пределами d.

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

Поскольку C и D фиксированы, это использование перекрестной проверки для выбора между ними само по себе является алгоритмом, т. е. способом обобщения произвольного набора данных. Назовем этот алгоритм A. (Возможно, A — это упрощенная модель самого научного метода.)

Мы также могли бы использовать анти -перекрестную проверку, чтобы сделать свой выбор. Другими словами, мы могли бы выбирать между C и D на основе того, у кого худшая производительность вне выборки в пределах d . Опять же, поскольку C и D фиксированы, это использование анти-перекрестной проверки само по себе является алгоритмом. Назовем этот алгоритм B.

NFL говорит нам (грубо говоря), что B должен победить A по стольким же целевым функциям (и связанным с ними наборам данных d ), по скольким A побеждает B. В этом весьма специфическом смысле научный метод проиграет «антинаучному» методу так же легко, как и победит. ^[10]

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

В то время как некоторые ученые утверждают, что NFL передает важную информацию, другие утверждают, что NFL не имеет большого значения для исследований машинного обучения. ^{[5] [6] [7]} Если бритва Оккама верна, например, если последовательности с более низкой сложностью Колмогорова более вероятны, чем последовательности с более высокой сложностью, то (как это наблюдается в реальной жизни) некоторые алгоритмы, такие как перекрестная проверка, в среднем работают лучше при решении практических задач (по сравнению со случайным выбором или с анти-перекрестной проверкой). ^[11]

Однако существуют серьезные формальные проблемы в использовании аргументов, основанных на сложности Колмогорова, для установления свойств реального мира, поскольку она невычислима и не определена с точностью до произвольной аддитивной константы. Отчасти в знак признания этих проблем, недавно было высказано мнение, что существуют способы обойти теоремы об отсутствии бесплатных обедов без привлечения машин Тьюринга, используя «метаиндукцию». ^{[12] [13]} Более того, сложность Колмогорова моделей машинного обучения может быть ограничена сверху посредством сжатия их маркировки данных, и возможно получить непустые границы междоменного обобщения с помощью сложности Колмогорова. ^[7]

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

• Бизнес-портал

• Внешние эффекты
• Скрытая стоимость

Примечания

1. Wolpert, DH; Macready, WG (1997). «Теоремы о бесплатном обеде для оптимизации не существуют». Труды IEEE по эволюционным вычислениям . 1 : 67–82. CiteSeerX  10.1.1.138.6606 . doi :10.1109/4235.585893. S2CID  5553697.
2. Wolpert, David (1996), «Отсутствие априорных различий между алгоритмами обучения», Neural Computation , стр. 1341–1390. Архивировано 20 декабря 2016 г. на Wayback Machine
3. Wolpert, DH; Macready, WG (декабрь 2005 г.). «Коэволюционные бесплатные обеды». IEEE Transactions on Evolutionary Computation . 9 (6): 721–735. doi :10.1109/TEVC.2005.856205. hdl : 2060/20050082129 . ISSN  1089-778X.
4. Вулперт, Д. Х.; Макреди, В. Г. (1995). «Теоремы о бесплатном обеде для поиска». Технический отчет SFI-TR-95-02-010 . Институт Санта-Фе. S2CID  12890367.
5. Whitley, Darrell; Watson, Jean Paul (2005). Burke, Edmund K.; Kendall, Graham (ред.). Complexity Theory and the No Free Lunch Theorem. Бостон, Массачусетс: Springer US. стр. 317–339. doi :10.1007/0-387-28356-0_11. ISBN 978-0-387-23460-1.
6. Жиро-Карриер, Кристоф и Фостер Провост. «К обоснованию метаобучения: является ли теорема об отсутствии бесплатных обедов препятствием для шоу». В трудах семинара ICML-2005 по метаобучению, стр. 12–19. 2005.
7. Голдблюм, М., Финци, М., Кифер, Р. и Уилсон, А. Г. «Теорема об отсутствии бесплатных обедов, сложность Колмогорова и роль индуктивных смещений в машинном обучении». В трудах Международной конференции по машинному обучению, 2024.
8. Форстер, Малкольм Р. (1999). «Как простые правила «соответствуют реальности» в сложном мире?». Minds and Machines . 9 (4): 543–564. doi :10.1023/A:1008304819398. S2CID  8802657.
9. Кавагучи, К., Кэлблинг, Л.П. и Бенгио, Й. (2017) «Обобщение в глубоком обучении», https://arxiv.org/abs/1710.05468
10. Wolpert, David H. (декабрь 2013 г.). «Симпозиум Ubiquity: Эволюционные вычисления и процессы жизни: что на самом деле означают теоремы об отсутствии бесплатных обедов: как улучшить алгоритмы поиска». Ubiquity . 2013 (декабрь): 1–15. doi :10.1145/2555235.2555237. ISSN  1530-2180.
11. Латтимор, Тор и Маркус Хаттер. «Никакого бесплатного обеда против бритвы Оккама в контролируемом обучении». В Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence, стр. 223–235. Springer, Берлин, Гейдельберг, 2013.
12. Шурц, Г. (2019). Проблема Юма решена: оптимальность метаиндукции . MIT Press.
13. Wolpert, DH (2023). «Следствия теорем об отсутствии бесплатных обедов для метаиндукции». Журнал общей философии науки . 54 : 421–432. arXiv : 2103.11956 . doi : 10.1007/s10838-022-09609-2.

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

• Теоремы о бесплатном обеде отсутствуют
• Графика, иллюстрирующая теорему