Статистическая теория обучения
Расширения PAC-обучаемости
Стандартное PAC предполагает, что правильный ответ лежит в классе H. В реальности - нет. Агностическое PAC честно: гарантирует конкуренцию с лучшим в H, не больше.
- **Search ranking:** Google Search использует агностические PAC-гарантии при 10^9 примерах и VC-размерности 10^6 - реализуемость заведомо нарушена
- **Медицинская диагностика:** Обучение при неточных или спорных диагнозах - классическая агностическая постановка, где истинная метка неизвестна
- **AutoML:** Выбор модели из класса H без предположения реализуемости: агностическая граница направляет поиск архитектуры
- **Финансовые прогнозы:** Рынок не порождается ни одной моделью из H; агностический PAC формализует конкуренцию с лучшей доступной стратегией
Предварительные знания
- Стандартное PAC-обучение
- VC-размерность
- Онлайн-обучение и бандиты
Агностическое PAC-обучение
Google Search использует агностические PAC-гарантии для ранжирующих моделей: при 10^9 обучающих примеров и классе гипотез VC-размерности d = 10^6 ошибка обобщения не превысит ε = 0.01 с вероятностью 1 - δ = 0.95.
Чем агностическое PAC отличается от стандартного?
В реализуемом PAC: best-in-class имеет 0 ошибок (есть h* ∈ H с R(h*) = 0). В агностическом PAC: лучшая гипотеза h* = argmin R(h) может иметь ненулевую R(h*) > 0. ERM гарантирует R(ERM) <= R(h*) + sqrt(O(VC log(n))/n), что подходит для шумных или некорректно специфицированных моделей.
Равномерная сходимость и ERM
Какое свойство класса H гарантирует обучаемость через ERM в агностическом сеттинге?
Фундаментальная теорема статистического обучения (Vapnik-Chervonenkis): VC(H) < ∞ ↔ H агностически PAC-обучаем через ERM с sample complexity O((VC(H) + log(1/delta))/eps²). Радемахеровская сложность даёт более тонкие, нераспределённые границы.
Improper learning и расширения
Агностическое PAC похоже на соревнование с лучшим участником команды - Класс H - команда специалистов. Истинный ответ неизвестен никому. Задача - выступить не хуже лучшего члена команды, оцениваемого по его реальной (не выборочной) результативности. Нельзя гарантировать нулевую ошибку - но можно гарантировать конкуренцию с лучшим доступным инструментом. Это честная постановка для реального ML.
Что такое improper learning?
В proper learning A(S) ∈ H. В improper learning A(S) может быть вне H. Это часто даёт строго лучшие границы: например, для disjunctions с n переменными proper learning требует Θ(n/eps) примеров, а improper - O(log(n)/eps). DNN можно интерпретировать как improper learners для классов простых функций.
Связи с другими темами
Агностическое PAC соединяет классическую теорию обучаемости с современными гарантиями для нейросетей и онлайн-методов.
- VC-теория — Связанная тема
- Сложность Радемахера — Связанная тема
- Онлайн-обучение — Связанная тема
- Модели обучения с шумом — Связанная тема
Итоги
- Агностическое PAC не требует реализуемости: цель - конкурировать с opt_H, а не найти c*
- ERM-граница: L(h_S) не хуже opt_H + O(sqrt(log|H|/m)) для конечного H
- Равномерная сходимость - необходимое и достаточное условие агностической PAC-обучаемости
- Объём выборки: m = O((log|H| + log(1/δ)) / ε²) для (ε,δ)-агностической гарантии
- Шум Massart (η < 1/2) позволяет уменьшить сложность выборки по сравнению с полностью агностическим случаем
Какое ключевое отличие агностического PAC-обучения от стандартного PAC-обучения?
Агностическое PAC: истинная концепция может не лежать в H. Цель - найти h с ошибкой не хуже opt_H + ε, где opt_H = min_h L(h). Не предполагается реализуемость.