PAC framework: формализация 'обучения по примерам'

1984 год: Лесли Валиант публикует 'A Theory of the Learnable' - первая формальная модель машинного обучения. За неё он получит Тьюринговую премию в 2010. Деплоят модель. Точность на тесте - 92%. Менеджер: 'будет ли 92% на проде?' Хороший инженер говорит: 'скорее всего да'. Великий достаёт PAC-bound и называет конкретное число: 'с вероятностью 95% ошибка <= 13.4%'. Разница - в знании теоремы.

• Spam-фильтры (пример Валианта): сколько писем нужно показать алгоритму, чтобы он работал на новых?
• A/B-тестирование: сколько показов нужно до статистически значимого результата - тот же sample complexity
• Random forests: sample complexity растёт логарифмически по $|H|$, объясняя стабильность ансамблей
• Deep learning paradox: сети с $|H| \to \infty$ обобщают - PAC в чистом виде не работает, lt-13
• Active learning: как минимизировать число labeled examples - прямое следствие PAC

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

• Базовая теорвер: распределение, IID-выборка, вероятность события
• Неравенство Хёфдинга (интуиция): среднее по выборке близко к матожиданию
• Что такое классификатор: $h: X \to Y$, бинарная классификация

Что значит 'обучаться': сетап PAC

1984 год: Лесли Валиант публикует 'A Theory of the Learnable' - первая формальная модель машинного обучения. За неё он получит Тьюринговую премию в 2010. До этой статьи ML было ремеслом. Никто не мог сформулировать вопрос: 'когда мы имеем право утверждать, что обучение успешно?' Валиант формулирует. Его определение: PAC - Probably Approximately Correct.

**Сетап PAC.** $X$ - пространство объектов. $Y = \{0,1\}$ - метки. $D$ - неизвестное распределение на $X$ (природа генерирует данные, мы не контролируем как). $c: X \to Y$ - target concept (то, что хотим выучить). $H \subseteq \{h: X \to Y\}$ - hypothesis class. Sample $S = \{(x_i, c(x_i))\}_{i=1}^m$, $x_i \sim D$ IID. Цель: найти $h \in H$ с малым **true error** $R(h) = \Pr_{x \sim D}[h(x) \neq c(x)]$. Ключевое: $D$ неизвестно, доступ только через $S$.

**Разрыв true/empirical error - центральный объект.** $R(h) = \Pr_{x \sim D}[h(x) \neq c(x)]$ (недоступно, $D$ неизвестно). $\hat{R}(h) = \frac{1}{m}\sum_{i=1}^m \mathbb{1}[h(x_i) \neq c(x_i)]$ (считаем по выборке). Обучение успешно, если $R(h)$ мало. ERM минимизирует $\hat{R}$. Всё обучение с учителем - ERM в скрытом виде. PAC отвечает: когда малый $\hat{R}$ гарантирует малый $R$?

Sample complexity: сколько данных нужно?

Главная формула. Для **конечного** $H$ и **realizable case** ($c \in H$): ERM-learner с вероятностью $\geq 1 - \delta$ возвращает гипотезу с $R(h_S) \leq \varepsilon$, если $m \geq \frac{1}{\varepsilon} \ln \frac{|H|}{\delta}$. Три параметра: $\varepsilon$ (допустимая ошибка), $\delta$ (допустимая вероятность неудачи), $|H|$ (размер класса).

**Идея доказательства (union bound):** обозначим $H_{\text{bad}} = \{h \in H : R(h) > \varepsilon\}$. В realizable case ERM найдёт $h_S$ с $\hat{R}(h_S) = 0$. Чтобы плохая $h$ не ошиблась ни на одном из $m$ примеров: $\Pr[\hat{R}(h) = 0] \leq (1-\varepsilon)^m \leq e^{-\varepsilon m}$. Union bound по всем плохим: $\Pr[\exists h \in H_{\text{bad}}: \hat{R}(h)=0] \leq |H| e^{-\varepsilon m}$. Чтобы это было $\leq \delta$: $m \geq \frac{1}{\varepsilon} \ln \frac{|H|}{\delta}$.

**Три зависимости, три урока:** (1) $m$ **линейно** по $1/\varepsilon$ - хочешь ошибку в 10 раз меньше - данных в 10 раз больше. (2) $m$ **логарифмически** по $|H|$ - класс в миллион раз больше, данных нужно только в 14 раз больше (ln $10^6 \approx 14$). (3) $m$ **логарифмически** по $1/\delta$ - confidence почти бесплатна. Вторая зависимость - главный результат: можно работать с огромными классами гипотез.

Realizable case и Occam's Razor bound

**Realizable case:** $c \in H$ - target concept лежит в нашем классе гипотез. ERM может найти гипотезу с нулевой ошибкой на трейне. **Agnostic case:** $c \notin H$ - идеальной гипотезы нет. ERM целится в лучшую возможную: $R(h_S) \leq \min_{h \in H} R(h) + \varepsilon$. Цена: sample complexity растёт **квадратично** по $1/\varepsilon$: $m \geq O(\frac{1}{\varepsilon^2} \ln \frac{|H|}{\delta})$.

**Occam's Razor bound:** для realizable case - consistent learner (нулевая трейн-ошибка) из меньшего класса генерализует лучше. Формально: $R(h_S) \leq \frac{1}{m}(\ln |H| + \ln \frac{1}{\delta})$ с вероятностью $\geq 1-\delta$. Меньший класс - меньший $\ln|H|$ - меньший true error при том же $m$. Это теоретическая база regularization: inductive bias (ограничение $H$) помогает обобщению.

**PAC сегодня:** оригинальный PAC 1984 года редко применяется напрямую (конечные классы - редкость). Но идея выжила и расширилась: VC-теория (Vapnik-Chervonenkis) - $\log|H|$ заменяется VC-размерностью для бесконечных классов; Rademacher complexity - data-dependent версия; PAC-Bayes - posterior над $H$; margin bounds - для SVM и AdaBoost. Всё растёт из 11 страниц Валианта 1984 года.

Итог

• PAC = Probably Approximately Correct: с вероятностью $\geq 1-\delta$, ошибка $\leq \varepsilon$, для любого $D$
• Словарь: $X, Y, D, c, H, S, R(h), \hat{R}(h)$ - покрывает любую supervised-задачу
• ERM: $h_S = \arg\min_{h \in H} \hat{R}(h)$ - все ML-алгоритмы в скрытом виде. Работает при ограниченной сложности $H$
• Sample complexity (realizable, конечный $H$): $m \geq \frac{1}{\varepsilon} \ln \frac{|H|}{\delta}$ - логарифмически по $|H|$, линейно по $1/\varepsilon$
• Realizable ($c \in H$): $O(1/\varepsilon)$ примеров. Agnostic ($c \notin H$): $O(1/\varepsilon^2)$ - квадратичная цена
• Occam's Razor: меньший класс гипотез - лучше обобщение при фиксированном $m$ (теоретическая база regularization)
• Эволюция PAC: VC-теория, Rademacher, PAC-Bayes, margin bounds - всё из 11 страниц Валианта 1984

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

PAC - корень всего курса. Прямые продолжения:

• Agnostic PAC — Что меняется, когда $c \notin H$: квадратичная sample complexity, lower bounds
• VC dimension — Замена $\log |H|$ на конечную меру для бесконечных классов
• Online learning — PAC без IID: regret bounds, sequential prediction
• Generalization paradox в deep learning — Почему классический PAC ломается на нейросетях - и что приходит на смену

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

• Если PAC требует IID-выборки, какие production-сценарии нарушают это чаще всего? Что делать инженеру?
• Sample complexity растёт логарифмически по $|H|$. Почему deep nets с миллиардами параметров не требуют экспоненциальных датасетов?
• В realizable case bound в $\varepsilon$ раз лучше, чем в agnostic. Какая интуиция скрыта за этим квадратом?
• PAC - frequentist. PAC-Bayes - параллельная попытка использовать prior. Где грань: что одно делает лучше другого?

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

• stat-28-vc-theory