No-Free-Lunch: невозможность универсального learner

2009 год. Netflix Prize. Команда BellKor's Pragmatic Chaos собрала ансамбль из 800 с лишним моделей и обошла Netflix на 10.06% - ровно столько нужно для приза в 1 млн долларов. Победители решили: найден универсальный рецепт. Комбинируй достаточно разных алгоритмов - и выиграешь на любом датасете. Год спустя те же методы провалились на задачах из Twitter и Hulu. Не потому что реализация была плохой. Потому что задача была другой. Wolpert и Macready доказали это в 1996-1997 году строго: для любых двух алгоритмов $\mathcal{A}_1$ и $\mathcal{A}_2$, усреднённых по всем возможным задачам $f$, средняя производительность одинакова. Алгоритм, побеждающий на одном распределении задач, проигрывает на другом ровно на столько же. Нет бесплатного обеда.

• **AutoML (Google Vizier, H2O AutoML):** перебирает сотни алгоритмов и гиперпараметров - но не потому что ищет 'лучший', а потому что ищет лучший для данного распределения задач. NFL говорит: на другом распределении победитель будет другим
• **CNN и translation invariance:** свёрточные слои - не просто удобный трюк. Это hard-coded inductive bias: 'признаки инвариантны к сдвигу'. Без этого prior на ImageNet сеть не обобщается. NFL объясняет зачем архитектура вообще существует
• **Transformer и attention pattern:** softmax attention предполагает, что релевантность вычисляется через dot-product similarity. Это prior о структуре зависимостей. Поэтому Transformer работает на текстах и не работает на регулярных таблицах без доработки
• **Meta-learning (MAML):** вместо одного алгоритма учится prior над алгоритмами - как именно инициализировать веса чтобы быстро адаптироваться. NFL-aware подход: не 'один универсальный', а 'хороший для семейства задач'

Предварительные знания

• Empirical и expected Rademacher complexity как мера сложности класса
• Концепция inductive bias: класс гипотез $\mathcal{H}$ как ограничение пространства поиска
• Generalization bound: $R(h) \leq \hat{R}(h) + \text{complexity}(\mathcal{H})$

• Rademacher complexity: data-dependent bound
• Uniform convergence: почему ERM работает

NFL-теорема: формулировка через суммирование по функциям

NFL-теорема: формулировка через суммирование по функциям

Пусть $\mathcal{X} = \{1, \ldots, n\}$ - конечное пространство входов, $\mathcal{Y}$ - пространство выходов. Задача - целевая функция $f: \mathcal{X} \to \mathcal{Y}$, выбранная из множества всех возможных $\mathcal{F} = \mathcal{Y}^{\mathcal{X}}$. Алгоритм $\mathcal{A}$ получает обучающую выборку $S = \{(x_i, f(x_i))\}_{i=1}^m$ и возвращает гипотезу $h = \mathcal{A}(S)$.

**No-Free-Lunch теорема (Wolpert & Macready 1997).** Для любых двух алгоритмов $\mathcal{A}_1$ и $\mathcal{A}_2$ и любого фиксированного способа выбирать обучающую выборку $S$ из $\mathcal{X}$: $$\sum_{f \in \mathcal{F}} \mathbb{P}[\mathcal{A}_1 \text{ лучше } | f] = \sum_{f \in \mathcal{F}} \mathbb{P}[\mathcal{A}_2 \text{ лучше } | f]$$ Усреднённая по всем $f \in \mathcal{F}$ ошибка не зависит от выбора алгоритма. Эквивалентно: для равномерного распределения по $\mathcal{F}$ матожидание ошибки одинаково для любого $\mathcal{A}$.

Ключевое слово - "усреднённая". NFL не говорит, что нет хороших алгоритмов. Он говорит, что алгоритм, хороший на одном подмножестве задач, плохой на другом - и при равномерном весе эти вклады компенсируют друг друга. Число задач в $\mathcal{F} = \mathcal{Y}^{\mathcal{X}}$ экспоненциально: для $|\mathcal{X}| = 100$ и $|\mathcal{Y}| = 2$ это $2^{100}$ функций.

Средняя ошибка одинакова: 0.5. Постоянная функция и эвристика "голосование большинством" равны на множестве всех бинарных функций. Это не патология: это математическая необходимость. Для каждой задачи где алгоритм 2 выигрывает, найдётся симметричная задача где он проигрывает.

Доказательство через симметрию: почему математика неизбежна

Доказательство через симметрию: почему математика неизбежна

Доказательство использует один элегантный факт: для любой обучающей выборки $S$ с фиксированными $(x_i, y_i)$ существует ровно столько функций $f \in \mathcal{F}$, согласных с $S$, для которых гипотеза $h = \mathcal{A}(S)$ даёт ошибку $k$ на тестовых точках, сколько функций, для которых ошибка равна $|T| - k$ - где $T$ - тестовое множество.

Интуиция: алгоритм видит $S$. На точках вне $S$ - без дополнительных предположений - всё что он делает, это угадывает. Любое предположение о структуре $f$ вне $S$ не может быть обоснованным из данных: данные на этих точках просто не видены. Для равномерного распределения по $\mathcal{F}$ все такие предположения в среднем бесполезны.

**Следствие для PAC-learning.** Теорема Вольперта дополняет PAC-framework критически важным выводом: PAC-bounds гарантируют обобщение только для фиксированного класса $\mathcal{H}$. Они молчат о том, почему выбран именно этот $\mathcal{H}$. NFL говорит: без prior о структуре задачи выбор $\mathcal{H}$ произволен - а значит и гарантии относительны. Learnability требует одновременно и finite complexity $\mathcal{H}$, и правильности prior о распределении задач.

Inductive bias как единственный выход

Inductive bias как единственный выход

Если NFL закрывает дверь в универсальность, то inductive bias открывает боковую. Реальные задачи - не равномерное распределение по $\mathcal{F}$. Изображения не случайные матрицы пикселей. Языковые тексты не случайные последовательности токенов. Природа структурирована - и алгоритм, который знает эту структуру заранее, выигрывает.

CNN предполагает: признаки локальны и инвариантны к сдвигу. Это prior, встроенный в архитектуру. На ImageNet этот prior правилен - и CNN обобщается. На задаче предсказания финансовых рядов этот prior неверен - и CNN проигрывает простым линейным моделям. XGBoost доминирует на табличных данных из-за prior о независимости признаков и кусочно-постоянных функциях. LLM доминируют на тексте из-за prior об авторегрессии и attention over context. Один и тот же алгоритм, разные домены - разные победители.

**Taxonomy inductive biases в современном ML:** - **Архитектурные:** CNN (locality + equivariance), Transformer (attention = soft lookup), GNN (permutation invariance на графах), RNN (sequential inductive bias) - **Оптимизационные:** SGD с маленьким learning rate находит flat minima - implicit bias в сторону low-complexity решений (Keskar 2017) - **Регуляризационные:** L2 (prior о малых весах = гауссовский prior), dropout (prior о независимости нейронов), weight decay - **Data augmentation:** переводит геометрические предположения в prior (rotational invariance, color invariance) - **Transfer learning:** prior из большого корпуса - самый мощный источник inductive bias в 2020-х

Ridge с R2=0.97 на гладкой функции и R2=0.35 на кусочно-постоянной. GBM - ровно наоборот. Это NFL в численном виде: не существует модели, доминирующей по всей сетке задач. Bias-variance tradeoff - частный случай этого принципа: уменьшение дисперсии достигается ценой смещения, и правильный баланс зависит от prior.

ML-приложения: AutoML, transfer learning, архитектурный поиск

ML-приложения: AutoML, transfer learning, архитектурный поиск

AutoML - не опровержение NFL. Это его прикладная форма. Google Vizier, H2O AutoML, AutoSklearn ищут лучший алгоритм для конкретного датасета - то есть оценивают, какой inductive bias согласуется с данными. По факту это и есть prior matching: находим алгоритм, чьи предположения лучше всего соответствуют структуре конкретной задачи.

Transfer learning идёт дальше: вместо поиска по алгоритмам - прямой перенос prior. GPT-4 обучен на 13 триллионах токенов. Этот prior - дистилляция структуры человеческого языка. Fine-tuning на конкретной задаче - это не 'обучение с нуля', это корректировка prior. NFL это допускает: если prior истинен для нового домена, обобщение гарантировано. Если нет - transfer learning провалится. Именно поэтому перенос из текста в молекулярную биологию работает хуже, чем из текста в код.

Neural Architecture Search (NAS) - автоматический поиск inductive bias через метаоптимизацию архитектуры. EfficientNet найден через NAS. DARTS оптимизирует операции дифференцируемо. По NFL: NAS находит архитектуру с правильным prior для конкретного семейства задач - не универсальную. EfficientNet оптимален для ImageNet-подобных задач и не обязательно для медицины или спутниковых снимков.

**Почему AutoML не убил специалистов по ML.** НФЛ предсказывает это точнее любой интуиции: специалист несёт ручной prior - знание о доменной структуре задачи. AutoML оптимизирует по стандартным пространствам гиперпараметров. Для задачи из знакомого семейства (таблица, изображения, текст) AutoML конкурентоспособен. Для задачи с нестандартной структурой (геопространственные аномалии, молекулярное моделирование, HFT-сигналы) специалист с правильным prior выигрывает. NFL гарантирует: пока существуют задачи с нестандартной структурой, специалисты нужны.

Что забрать из урока

• **No-Free-Lunch (Wolpert & Macready 1997):** $\sum_{f} \mathbb{P}[\mathcal{A}_1 \text{ лучше} | f] = \sum_{f} \mathbb{P}[\mathcal{A}_2 \text{ лучше} | f]$ - усреднённая по всем задачам производительность одинакова для любых двух алгоритмов
• **Доказательство через симметрию:** для каждой задачи где $\mathcal{A}$ выигрывает, есть симметричная задача где проигрывает - при равномерном весе по $\mathcal{F}$ вклады компенсируются
• **Практический вывод:** хороший алгоритм предполагает prior о структуре задачи. Без prior - случайный поиск. Inductive bias - не недостаток, а единственный источник обобщения
• **Inductive bias taxonomy:** архитектурный (CNN locality, Transformer attention), оптимизационный (SGD flat minima), регуляризационный (L2 = gaussian prior), data augmentation, transfer learning
• **AutoML и специалисты:** AutoML ищет правильный prior для стандартных семейств задач. Специалист несёт prior для нестандартных. NFL гарантирует: пока задачи разнообразны - специалисты нужны
• **Transfer learning как NFL-ответ:** GPT-4 prior из 13T токенов корректен для задач с языковой структурой. Провалится там, где структура другая - NFL это предсказывает

Что дальше

NFL - теоретическое обоснование центральных инструментов теории обобщения:

• PAC-Bayes — Формализует prior как распределение над гипотезами - ответ на NFL через bayesian подход
• Margin bounds — Margin - конкретный вид inductive bias; NFL объясняет зачем ограничение нормы необходимо
• Generalization paradox в deep learning — Implicit bias SGD как практическое воплощение NFL-требования к prior
• Rademacher complexity — Измеряет сложность конкретного класса - NFL объясняет зачем класс ограничивать

Вопросы для размышления

• XGBoost побеждает на tabular данных на Kaggle, LLM - на NLP. NFL говорит что они равны в среднем. Как примирить это с практикой? Какой prior у каждого из алгоритмов, и почему Kaggle-задачи несут именно такое распределение?
• MAML (Model-Agnostic Meta-Learning) учит prior над инициализациями весов, чтобы быстро адаптироваться к новым задачам. Это нарушает NFL? Или это легальный способ использовать prior о структуре семейства задач?
• Solomonoff induction формально является 'лучшим' prior в смысле Колмогоровской сложности. NFL применима к нему? Где граница между 'универсальным prior' и 'prior о конкретном семействе задач'?

Связанные уроки

• lt-06-rademacher — Rademacher complexity показывает сложность конкретного класса - NFL объясняет зачем класс нужно ограничивать
• lt-07-uniform-convergence — Uniform convergence работает внутри фиксированного класса - NFL объясняет почему класс не может быть универсальным
• lt-09-pac-bayes — PAC-Bayes формализует prior как решение NFL: не один алгоритм, а распределение алгоритмов
• lt-11-margin-bounds — Margin - конкретный вид inductive bias; NFL объясняет зачем он нужен
• lt-13-deep-generalization — Implicit bias SGD и архитектурные inductive biases CNN/Transformer как ответ на NFL
• prob-22-concentration — Концентрационные неравенства используются для усреднения по функциям в доказательстве NFL
• stat-01-sampling