Теорема «Нет бесплатного обеда»

Эта статья о математическом фольклоре. Подробнее о математике см. в разделе «Бесплатный обед в поиске и оптимизации» .

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

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

Теорема «без бесплатного обеда» (НФЛ) — это легко формулируемое и легко понимаемое следствие теорем, которые на самом деле доказывают Уолперт и Макреди. Он слабее доказанных теорем и, следовательно, не инкапсулирует их. Различные исследователи существенно расширили работу Уолперта и Макреди. С точки зрения того, как теорема НФЛ используется в контексте области исследований, бесплатный обед в поиске и оптимизации — это область, предназначенная для целей математического анализа данных для статистической идентичности, в частности поиска. и оптимизация.

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

Пример

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

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

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

Источник

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

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

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

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

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

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

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

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

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

Мотивация

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

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

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

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

Дополнительная информация: Проблема индукции.

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

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

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

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

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

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

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

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

См. также

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

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

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