Теорема No Free Lunch

Материал из MachineLearning.

Статья написана с использованием LLM GPT-5.5 и проверена участником Nikolai Agafonov 21:12, 18 июля 2026 (MSD)

Содержание

1 Определение
- 1.1 Интуитивная интерпретация
- 1.2 История
2 Формальная постановка
- 2.1 Почему это так?
- 2.2 Эскиз доказательства
3 Теорема для оптимизации
4 Индуктивное смещение
5 Почему теорема не противоречит успеху глубокого обучения?
6 Практические следствия
7 См. также
8 Литература

Определение

Теорема No Free Lunch (англ. No Free Lunch theorem, NFL) — семейство теорем в машинном обучении, теории оптимизации и теории статистического обучения, утверждающих, что без априорных предположений о рассматриваемой задаче ни один алгоритм не может превосходить все остальные в среднем по всем возможным задачам. Теоремы были сформулированы Дэвидом Вольпертом (1996) для задач обучения и позднее совместно с Уильямом Макреди (1997) для задач оптимизации.

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

Интуитивная интерпретация

Предположим, необходимо выбрать лучший алгоритм среди деревьев решений, метода опорных векторов, нейронных сетей и градиентного бустинга.

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

Именно это и утверждает теорема No Free Lunch.

История

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

Первый строгий результат был получен американским исследователем Дэвидом Вольпертом. В статье The Lack of A Priori Distinctions Between Learning Algorithms, опубликованной в 1996 году в журнале Neural Computation, он доказал, что при отсутствии априорной информации о распределении задач средняя ошибка любого алгоритма обучения одинакова. Рассматривались конечные множества объектов и функций, а усреднение производилось по всем возможным отображениям $f:X\rightarrow Y$ . Полученный результат показал, что преимущество одного алгоритма на части функций неизбежно компенсируется его проигрышем на остальных.

В 1997 году Вольперт совместно с Уильямом Макреди распространил эти выводы на задачи глобальной оптимизации. В статье No Free Lunch Theorems for Optimization, опубликованной в IEEE Transactions on Evolutionary Computation, было доказано, что при равномерном распределении по множеству всех целевых функций любой алгоритм оптимизации — независимо от того, является ли он детерминированным, случайным или эволюционным — имеет одинаковую среднюю производительность. Эта работа оказала значительное влияние на развитие эволюционных алгоритмов, метаэвристик и методов глобального поиска.

В последующие годы теорема стала предметом активного обсуждения. Одним из наиболее распространённых заблуждений стало утверждение, что «все алгоритмы одинаково хороши». В действительности теорема относится только к случаю равномерного распределения по пространству всех возможных задач. Уже в начале 2000-х годов было показано, что если реальные задачи образуют лишь небольшое структурированное подмножество этого пространства, то некоторые алгоритмы могут иметь статистически значимое преимущество.

Формальная постановка

Рассмотрим множество объектов $X=\{x_1,\ldots,x_n\}$ , и множество возможных ответов $Y$ .

Любая задача обучения представляет собой неизвестную функцию: $f:X\rightarrow Y$

Алгоритм обучения наблюдает обучающую выборку $D=\{(x_i,f(x_i))\}_{i=1}^{m}$ , где $m<n$ ,

После чего строит гипотезу: $h:X\rightarrow Y$

Качество алгоритма определяется функцией потерь $L(f,h)$ .

Пусть множество всех функций обозначено через $\mathcal{F}=Y^X$

Если все функции $f\in\mathcal{F}$ считаются равновероятными, то для любых алгоритмов $A_1,\;A_2$ выполняется:

$\frac1{|\mathcal F|} \sum_{f\in\mathcal F} L(f,A_1(D)) = \frac1{|\mathcal F|} \sum_{f\in\mathcal F} L(f,A_2(D)).$

Иными словами, математическое ожидание ошибки одинаково независимо от выбора алгоритма.

Почему это так?

Ключевая идея состоит в количестве возможных функций.

Если $|X|=n,\qquad |Y|=k$ , то число всех отображений равно:

$|\mathcal F|=k^n.$

Например, $n=20,\qquad k=2$ , даёт $2^{20}=1\,048\,576$ различных функций.

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

Следовательно, без дополнительных предположений невозможно определить, какая из них является истинной.

Эскиз доказательства

Пусть алгоритм уже увидел множество $D$ .

Для любого ещё не наблюдавшегося объекта $x\notin D$ , существуют функции

$f_1,f_2,\ldots$

совпадающие на всей обучающей выборке, но принимающие различные значения в точке $x$ .

Поскольку все функции считаются равновероятными,

$P(f(x)=y)=\frac1{|Y|}.$

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

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

Именно это и составляет содержание теоремы.

Теорема для оптимизации

В задаче глобальной оптимизации необходимо найти

$x^*=\arg\min_{x\in X}f(x).$

Алгоритм последовательно выбирает точки $x_1,x_2,\ldots,x_t$ , получая значения $f(x_1),f(x_2),\ldots$ .

Пусть эффективность алгоритма определяется функционалом $P(A,f)$ .

Тогда

$\sum_{f}P(A_1,f) = \sum_{f}P(A_2,f),$

если суммирование производится по всем возможным функциям.

Следовательно, никакой алгоритм поиска (например, Генетический алгоритм, Имитация отжига, Рой частиц) не обладает универсальным преимуществом.

Индуктивное смещение

Практическое значение теоремы заключается в понятии индуктивного смещения.

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

$\mathcal H\subset\mathcal F.$

Например,

Линейная регрессия предполагает линейность;
Дерево решений предполагает возможность рекурсивного разбиения пространства признаков;
Свёрточная нейронная сеть предполагает локальность признаков;
Трансформер предполагает наличие зависимостей между элементами последовательности.

Именно эти предположения позволяют алгоритмам успешно обобщать данные.

Почему теорема не противоречит успеху глубокого обучения?

На первый взгляд теорема противоречит практическому превосходству современных моделей.

На самом деле противоречия нет.

Теорема предполагает равномерное распределение по множеству всех функций $\mathcal F$ .

Реальные задачи образуют чрезвычайно малое подмножество $\mathcal F_{\mathrm{real}}\subset\mathcal F$ , которое обладает сильной структурой:

изображения имеют пространственную корреляцию;
текст обладает синтаксисом и семантикой;
временные ряды характеризуются зависимостью соседних наблюдений.

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

Практические следствия

Из теоремы следуют несколько фундаментальных принципов современной разработки моделей:

не существует универсально лучшего алгоритма обучения;
выбор модели определяется предметной областью;
необходимы кросс-валидация и сравнение нескольких моделей;
качество модели определяется не только алгоритмом, но и соответствием его индуктивного смещения данным;
увеличение количества данных не устраняет необходимость выбора подходящей архитектуры.

См. также

Литература

Wolpert D. H. The Lack of A Priori Distinctions Between Learning Algorithms. Neural Computation. 1996.
Wolpert D. H., Macready W. G. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation. 1997.
Mitchell T. Machine Learning. McGraw-Hill, 1997.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. Springer, 2009.
Bishop C. M. Pattern Recognition and Machine Learning. Springer, 2006.
Shalev-Shwartz S., Ben-David S. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Wolpert D. H. What is Important About the No Free Lunch Theorems? arXiv:2007.10928, 2020.
Goldblum M. et al. The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning. arXiv:2304.05366, 2023.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_No_Free_Lunch»