Статистическая теория обучения

Realizable learning и ERM: когда правильный ответ точно есть

Число-шок: если в классе гипотез $2^{1000}$ функций - это больше атомов во Вселенной - нужно около 70 000 примеров чтобы гарантировать точность 1% с вероятностью 99%. Не экспоненциальный взрыв. Логарифм укрощает размер класса. Это и есть главный результат realizable PAC.

**SVM с линейным ядром в linearly separable данных**: классический realizable случай. Данные линейно разделимы - значит линейный классификатор с нулевой ошибкой существует. ERM в виде max-margin SVM находит его с PAC-гарантией. Sample complexity: $O(d / \varepsilon)$ где $d$ - размерность.
**Деревья решений без pruning**: если данные реализуемы (нет противоречивых примеров), дерево достаточной глубины даёт $\hat{R} = 0$. Класс конечен при фиксированных признаках - PAC напрямую применим. Отсутствие pruning = overfitting: реализуемость не означает обобщение без достаточного $m$.
**Конъюнкции Валианта 1984**: оригинальный пример из статьи. Класс мономиальных функций над $\{0,1\}^n$: $|H| = 3^n$, sample complexity $O(n \log n / \varepsilon)$. Спам-фильтр 1984 года.
**Логистическая регрессия на сепарабельных данных**: при линейной разделимости SGD с достаточным числом шагов находит $\hat{R} = 0$. Теоретическая гарантия PAC работает - но на практике без регуляризации веса уходят в бесконечность.
**Double descent парадокс**: современные overparameterized сети формально находятся в realizable случае (интерполируют тренировочные данные), но generalization не ломается. Это разрушает наивную realizable-логику и мотивирует implicit regularization - тема lt-13.

Валиант 1984: алгоритм как доказательство

Статья 'A Theory of the Learnable' (Communications of the ACM, 11 страниц) появилась когда ML не существовал как дисциплина. Statisticians делали MLE и не думали про алгоритмы. Computer scientists изучали сложность вычислений, но не probabilistic guarantees. Валиант объединил: learner - это алгоритм с sample complexity как мерой вычислительной сложности. Realizable case был его стартовой точкой: самый чистый сценарий, где можно доказать первый результат. Первый пример - конъюнкции над булевым кубом. |H| = 3^n (для n переменных: каждая входит с позитивным литералом, отрицательным или не входит). ERM-алгоритм находит верную конъюнкцию за O(nm) времени. Тьюринг 2010 - через 26 лет. Комитет назвал PAC 'одним из наиболее влиятельных результатов в theoretical computer science'.

Концепт 1: realizability и что она даёт

Realizable case - это предположение $c \in H$: истинная концепция лежит внутри класса гипотез. Это сильное допущение. В реальности данные шумные, признаки неполны, природа не линейна. Но именно realizable case даёт первое доказательство и показывает механику PAC в чистом виде.

**SVM и realizable case**: при линейной сепарабельности данных задача hard-margin SVM - это ERM в realizable случае. Max-margin hyperplane минимизирует $\hat{R} = 0$ с дополнительным критерием (максимальный margin). PAC-bound для SVM в этом случае: $m = O(d/\varepsilon)$ где $d$ - размерность. Margin-based bounds дают лучшую оценку - тема lt-11.

Класс $H$ - все линейные классификаторы в $\mathbb{R}^2$. Данные линейно разделимы. Что гарантирует realizability assumption?

Realizability гарантирует существование h* с нулевой true error. PAC-bound говорит: при $m \geq (1/\varepsilon) \ln(|H|/\delta)$ ERM вернёт гипотезу с ошибкой $\leq \varepsilon$ с вероятностью $\geq 1 - \delta$. ERM не гарантирует $R(h_S)=0$ - только малость. И max-margin SVM - лишь один из возможных ERM-ответов с дополнительным критерием.

Концепт 2: union bound и доказательство sample complexity

Доказательство - техника, используемая во всей статистической теории обучения. Центральный вопрос: какова вероятность, что ERM провалится? Провал - найти гипотезу с нулевой тренировочной ошибкой, которая плохо обобщается. Ответ через union bound: суммируем риск по всем потенциально плохим гипотезам.

Здесь скрыта интуиция: union bound пессимистичен. Суммируем вероятности по всем $|H|$ гипотезам, хотя большинство из них далеки от того чтобы иметь нулевую ошибку. Это и объясняет логарифм - реальная зависимость от $|H|$ может быть лучше. VC-dimension (lt-04) - более точная мера, заменяющая $\log|H|$ на 'эффективную' сложность класса.

В доказательстве sample complexity основной приём - union bound. Почему зависимость от $|H|$ получается логарифмической, а не линейной?

Union bound даёт линейный рост с $|H|$, но экспоненциальное затухание с $m$ его компенсирует. При решении для $m$ линейность $|H|$ уходит под логарифм. Класс в $10^6$ раз больше требует всего $\ln(10^6) \approx 14$ дополнительных примеров.

Концепт 3: примеры realizable PAC - от конъюнкций до нейросетей

Абстрактная теория становится интересной через конкретные классы гипотез. Три примера - от исходного Валианта до современных систем - показывают, что именно считается через формулу.

Пример 1: конъюнкции Валианта (1984)

Исходный пример из статьи

Пространство объектов: X = {0, 1}^n (бинарные векторы длины n). Таргет: конъюнкция некоторых переменных и их отрицаний. Например: c(x) = x₁ ∧ ¬x₃ ∧ x₅. Класс H: все такие конъюнкции. |H| = 3^n (каждая переменная: входит, входит отрицанием, не входит). ERM-алгоритм: начинаем с полной конъюнкции x₁ ∧ ¬x₁ ∧ x₂ ∧... Для каждого положительного примера удаляем литералы, которые принимают значение 0. O(n·m) времени. Sample complexity: m ≥ (1/ε) · ln(3^n / δ) = (n · ln 3) / ε + (1/ε) · ln(1/δ) ≈ (1.1 · n) / ε (доминирующий член) Для n = 100, ε = 0.05, δ = 0.05: m ≥ 20 · (100 · 1.1 + 3) = 20 · 113 ≈ 2260 примеров. Spam-фильтр 1984: спам - конъюнкция ключевых слов. Это и был первый PAC-learnable класс.

Пример 2: линейные классификаторы в realizable случае

SVM как ERM

Данные: m точек в R^d, линейно сепарабельные. c - истинная разделяющая гиперплоскость (c ∈ H). Hard-margin SVM - это ERM с дополнительным критерием: minimize (1/2)||w||² subject to yᵢ(wᵀxᵢ + b) ≥ 1 для всех i R(h_SVM) = 0 на тренировочных данных (realizable). PAC bound через VC-dimension (не |H|, так как H бесконечен): VC-dim линейных классификаторов в R^d = d + 1 m ≥ O((d + 1) / ε) (realizable, через VC) Margin bounds дают лучшее: m ≥ O(R² / (γ² · ε)) где γ - margin, R - радиус данных. Если margin большой (данные хорошо разделены), нужно меньше примеров. Интуиция: "чем уверенней SVM, тем быстрее учится".

Третий пример - modern neural nets. На первый взгляд они далеки от realizable case: классы бесконечны, VC-dim астрономическая, bound из PAC бесполезен. Но на практике overparameterized сети интерполируют тренировочные данные ($\hat{R} = 0$) - формально realizable! Только generalization при этом не ломается. Это и есть double descent парадокс: классический PAC предсказывает катастрофу при большом $|H|$, а нейросети опровергают предсказание. Причина - implicit regularization через архитектуру и SGD. Подробности - lt-13.

$\hat{R}(h) = 0$ в realizable случае - достаточное условие хорошей генерализации

Нулевая тренировочная ошибка необходима, но не достаточна. PAC-bound добавляет: нужно достаточно большое $m$ и ограниченная сложность $H$.

Класс всех функций $X \to \{0,1\}$ всегда realizable (любую метку можно запомнить). ERM найдёт $\hat{R} = 0$ при $m < |X|$ - просто запомнив sample. Но $R(h_S) \approx 1/2$. Без ограничения сложности $H$ realizability ничего не гарантирует. Именно поэтому в формуле стоит $\ln|H|$ - это плата за то, что ищем среди большого класса.

Класс $H$ из $|H| = 1024 = 2^{10}$ гипотез, $\varepsilon = 0.1$, $\delta = 0.05$. Минимальное $m$ по PAC-формуле для realizable случая?

Концепт 4: конечный H - ограничение и путь вперёд

Вся механика выше работала для конечного $H$. Это сильное ограничение: линейные классификаторы, нейросети, деревья произвольной глубины - все имеют $|H| = \infty$. Как быть?

Главное наблюдение: не весь $H$ одинаково 'информативен'. Линейный классификатор в $\mathbb{R}^2$ имеет бесконечно много параметров, но на $m$ точках он может реализовать не более $O(m^3)$ различных разбиений (по теореме о росте). Это число - не $|H|$, но конечное. Заменив $\log|H|$ на логарифм числа различимых гипотез, получаем bounds для бесконечных $H$.

**Agnostic PAC (lt-03)**: убираем $c \in H$. Sample complexity растёт как $1/\varepsilon^2$. Это реалистичный случай для практики.
**VC-dimension (lt-04)**: заменяем $\log|H|$ на $d$. Работает для бесконечных классов. Вапник и Червоненкис 1971.
**Uniform convergence (lt-07)**: доказываем, что $\hat{R}(h) \approx R(h)$ одновременно для всех $h \in H$ - не только для одной. Это усиление, из которого следует realizable PAC как частный случай.
**Margin bounds (lt-11)**: для SVM и классификаторов с отступом. Bound не через $d$, а через margin $\gamma$ - может быть лучше VC-bound.
**Deep generalization (lt-13)**: почему современные нейросети с $|H| = \infty$ и формально realizable ($\hat{R} = 0$) обобщают вопреки bound.

**Realizable case - не реалистичный.** В продакшне данные всегда шумные ($c \notin H$ почти наверняка), распределение нестационарно, IID нарушено. Realizable PAC ценен не как прикладная теорема, а как строительный блок: на его доказательстве строятся все дальнейшие результаты. Понимание union bound и логарифма по $|H|$ - необходимое условие для agnostic PAC, VC, Rademacher и PAC-Bayes.

Самопроверка: что лучше всего обобщает раздел "Концепт 4: конечный H - ограничение и путь вперёд"?

Ключевые идеи

**Realizability ($c \in H$)**: идеализированный сценарий - правильная гипотеза существует в классе. ERM находит $\hat{R} = 0$ и PAC-гарантирует малую true error.
**Sample complexity**: $m \geq (1/\varepsilon) \ln(|H|/\delta)$. Линейно по $1/\varepsilon$, логарифмически по $|H|$. Удвоение $|H|$ добавляет $\ln 2 / \varepsilon$ примеров.
**Union bound**: центральная техника доказательства. Суммируем риск по плохим гипотезам, каждая убивается экспоненциально быстро с ростом $m$. Отсюда логарифм.
**Конечный vs бесконечный H**: конечный - bound через $\log|H|$. Бесконечный - через VC-dimension $d$. Та же структура доказательства.
**SVM, деревья, конъюнкции**: три конкретных класса, где realizable PAC применим напрямую. Double descent нейросетей - граница где теория ломается и нужна lt-13.
**Realizable vs agnostic**: первый - $O(1/\varepsilon)$, второй - $O(1/\varepsilon^2)$. Разрыв объясняет, почему знание $c \in H$ вдвое дешевле по данным.

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

Realizable case предполагает $c \in H$. В каких реальных задачах это разумное допущение, а в каких - явно нет?
Sample complexity логарифмична по $|H|$. Почему тогда при обучении LLM с $|H| \approx 10^{10^{12}}$ нужны петабайты данных - разве логарифм от этого не мал?
Union bound пессимистичен: суммируем по всем $|H|$ гипотезам, не только по $|H_{bad}|$. Где эта пессимистичность сильнее всего ослабляет bound?
SVM в realizable случае - ERM с дополнительным критерием (максимальный margin). Зачем нужен этот дополнительный критерий, если PAC уже даёт гарантию?

Что разблокирует этот урок

Realizable PAC - фундамент, на котором строятся следующие результаты:

Agnostic PAC — Убираем $c \in H$: квадратичная зависимость от $1/\varepsilon$, реалистичный сценарий
VC dimension — Заменяем $\log|H|$ на VC-dim: работает для бесконечных классов
Uniform convergence — Усиление: $\hat{R} \approx R$ для всех $h \in H$ одновременно
Margin bounds — Realizable SVM - частный случай; margin дает лучший bound
Generalization paradox в deep learning — Нейросети нарушают realizable-логику: hat-R=0 не означает плохую генерализацию

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

lt-03-agnostic-pac — Agnostic - следующий шаг: убираем допущение c ∈ H
lt-04-vc-dimension — VC-dim обобщает log|H| на бесконечные классы
lt-11-margin-bounds — Margin bounds объясняют SVM через PAC-realizable идею
prob-22-concentration — Union bound и неравенство Маркова - фундамент доказательства
lt-13-deep-generalization — Double descent ломает realizable-логику на нейросетях
stat-01-sampling