PAC-обучение

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

Статья написана с использованием LLM DeepSeek-V3 и проверена участником Д. Николаев 18:03, 6 июля 2026 (MSD)

Содержание

1 Определение
- 1.1 Формальное определение
- 1.2 Вычислительная эффективность
2 Свойства и фундаментальные результаты
3 Пример: обучение прямоугольникам
4 История
5 Варианты и обобщения
6 См. также
7 Литература

Вероятно приблизительно корректное обучение (англ. Probably Approximately Correct learning, PAC-обучение, теория Валианта) — раздел вычислительной теории обучения, представляющий собой математическую формализацию процесса обучения по примерам. Предложен Лесли Валиантом в 1984 году в статье «A Theory of the Learnable». PAC-обучение даёт строгие критерии, позволяющие ответить на вопрос, какие классы задач принципиально обучаемы с помощью эффективных алгоритмов, а какие — нет. В рамках этой модели алгоритм, получая случайные примеры, должен с высокой вероятностью построить гипотезу, ошибка которой на том же распределении не превосходит заданной малой величины.

Определение

В основе PAC-обучения лежат следующие объекты:

Пространство объектов $\mathcal{X}$ — множество всех возможных примеров.

Класс концептов $\mathcal{C}$ — множество целевых функций $c:\mathcal{X}\to{0,1}$ , которые алгоритм должен уметь изучать. Каждый концепт $c$ задает некоторое подмножество $\mathcal{X}$ (например, множество изображений, содержащих кошку).

Класс гипотез $\mathcal{H}$ — множество функций $h:\mathcal{X}\to{0,1}$ , которые алгоритм может выдавать в качестве результата обучения.

Распределение $\mathcal{D}$ — неизвестное вероятностное распределение на $\mathcal{X}$ , согласно которому генерируются примеры.

Оракул $\mathrm{EX}(c,\mathcal{D})$ — абстрактный механизм, который по запросу возвращает независимый пример $(x, c(x))$ , где $x \sim \mathcal{D}$ .

Ошибка гипотезы $h$ относительно целевого концепта $c$ и распределения $\mathcal{D}$ определяется как вероятность несовпадения их ответов на случайном примере:

$\operatorname{err}{\mathcal{D}}(h) = \Pr{x \sim \mathcal{D}}[h(x) \neq c(x)].$

Гипотеза называется $\varepsilon$ -приближённо корректной (или $\varepsilon$ -хорошей), если $\operatorname{err}_{\mathcal{D}}(h) \le \varepsilon$ .

Формальное определение

Пусть $\mathcal{C}$ — класс концептов, $\mathcal{H}$ — класс гипотез. Говорят, что $\mathcal{C}$ PAC-обучаем с помощью $\mathcal{H}$ , если существует алгоритм $A$ и функция $m_{\mathcal{H}}:(0,1)^2 \to \mathbb{N}$ такие, что для любых $\varepsilon, \delta \in (0,1)$ , любого распределения $\mathcal{D}$ на $\mathcal{X}$ и любого целевого концепта $c \in \mathcal{C}$ выполняется следующее: Алгоритм $A$ получает на вход $m \ge m_{\mathcal{H}}(\varepsilon, \delta)$ примеров, сгенерированных оракулом $\mathrm{EX}(c,\mathcal{D})$ . Алгоритм $A$ возвращает гипотезу $h \in \mathcal{H}$ . С вероятностью не менее $1-\delta$ (по случайности примеров) выполняется $\operatorname{err}_{\mathcal{D}}(h) \le \varepsilon$ .

Параметр $\varepsilon$ называется параметром точности (определяет допустимую ошибку), а $\delta$ — параметром надёжности (определяет допустимую вероятность неудачи). Таким образом, алгоритм должен быть вероятно ( $1-\delta$ ) приближённо ( $\varepsilon$ ) корректным.

Вычислительная эффективность

Ключевым вкладом Валианта было введение в теорию обучения понятий вычислительной сложности. Класс концептов называется полиномиально PAC-обучаемым, если существует PAC-алгоритм, время работы и количество запросов к оракулу которого ограничены полиномом от $1/\varepsilon$ , $1/\delta$ , размера концепта $n$ и размера примера. Именно это требование отличает PAC-обучение от чисто статистического подхода и делает его частью теоретической информатики. Как отмечается в современном обзоре Серведио (2025), фундаментальная исследовательская программа, естественным образом возникающая из базовой PAC-модели, заключается в точном delineation границы между тем, что обучаемо, а что — нет, с помощью вычислительно эффективных агентов.

Свойства и фундаментальные результаты

Выборочная сложность

Центральный вопрос PAC-теории — сколько примеров необходимо для обучения? Ответ даёт фундаментальная теорема PAC-обучения, которая связывает выборочную сложность с VC-размерностью класса гипотез. Для класса гипотез $\mathcal{H}$ с конечной VC-размерностью $d$ существует PAC-алгоритм (эмпирическая минимизация риска), для которого достаточно

$m_{\mathcal{H}}(\varepsilon,\delta) = O!\left(\frac{d \log(1/\varepsilon) + \log(1/\delta)}{\varepsilon}\right)$

примеров. Более того, любое PAC-обучение требует $\Omega(d/\varepsilon)$ примеров, то есть эта оценка является оптимальной с точностью до логарифмических множителей.

В последнее время внимание исследователей сместилось в сторону анализа поведения алгоритмов в режиме малой ошибки ( $\tau = \operatorname{err}(h^*_{\mathcal{D}}) \to 0$ ). В работе Ханеке, Ларсена и Животовского (FOCS 2024) было показано, что оптимальные агностические алгоритмы могут допускать избыточную ошибку на распределениях, которые легче обучить (когда $\tau$ мало). Асилис и соавторы (NeurIPS 2025) решили открытый вопрос из этой работы, предложив вычислительно эффективный алгоритм, достигающий ошибки $c \cdot \tau + O!\left(\sqrt{\frac{\tau (d + \log(1 / \delta))}{m}} + \frac{d + \log(1 / \delta)}{m}\right)$ с константой $c \le 2.1$ , что соответствует нижней границе в режиме $\tau \approx d/m$ . Кроме того, была показана субоптимальность эмпирической минимизации риска (ERM) в агностическом PAC-обучении при параметризации по $\tau$ — ERM уступает оптимальным алгоритмам на множитель $\sqrt{\ln(1/\tau)}$ .

Собственное и несобственное обучение

Если алгоритм вынужден выдавать гипотезу из того же класса, что и целевой концепт ( $\mathcal{H} = \mathcal{C}$ ), говорят о собственном PAC-обучении (proper learning). Если же $\mathcal{H}$ может быть шире $\mathcal{C}$ , это несобственное обучение (improper learning). Несобственное обучение часто оказывается более гибким: например, класс ДНФ-формул может быть эффективно изучен с помощью класса КНФ-формул. В современных работах несобственные методы продолжают играть ключевую роль. Например, в задаче адаптивно устойчивого PAC-обучения (adversarially robust PAC learning) впервые был предложен простой («почти собственный») алгоритм, достигающий сложности выборки, линейной по VC-размерности, без дополнительных предположений о классе гипотез.

Обучение при наличии шума

Исходная модель предполагала, что все примеры размечены корректно (realizable case). Впоследствии были разработаны обобщения на случай, когда метки могут быть испорчены шумом (agnostic PAC learning). В этой постановке алгоритм не обязан точно воспроизводить целевой концепт, а должен приближать наилучшую гипотезу из класса $\mathcal{H}$ .

Современные исследования активно изучают агностическое обучение в различных постановках. В частности, установлена тесная связь между PAC-обучением и трансдуктивным обучением (transductive learning) — показано, что для агностического обучения с ограниченными потерями эти две модели по существу эквивалентны с точностью до членов младшего порядка в ошибке и выборочной сложности. Другое важное направление — воспроизводимость (replicability) в агностическом PAC-обучении. Недавно было доказано, что в агностической постановке только конечные классы гипотез являются глобально устойчиво обучаемыми, что потребовало введения ослабленных определений устойчивости.

Пример: обучение прямоугольникам

Классический пример, иллюстрирующий PAC-обучение, — изучение осе-выровненных прямоугольников на плоскости $\mathbb{R}^2$ . Пространство объектов $\mathcal{X} = \mathbb{R}^2$ . Целевой концепт $c$ — прямоугольник со сторонами, параллельными осям координат. Положительные примеры — точки внутри прямоугольника, отрицательные — снаружи. Алгоритм после получения выборки строит гипотезу $h$ — минимальный прямоугольник, содержащий все положительные примеры. Можно показать, что для достижения точности $\varepsilon$ с надёжностью $1-\delta$ достаточно $m = O!\left(\frac{1}{\varepsilon} \log \frac{1}{\delta}\right)$ примеров. Этот пример демонстрирует, как геометрическая простота класса концептов позволяет получить эффективный алгоритм с малой выборочной сложностью.

История

Статья Лесли Валианта «A Theory of the Learnable» (1984) стала одной из основополагающих работ, заложивших вычислительную теорию обучения. В ней была предложена строгая математическая модель, позволяющая изучать процесс обучения с позиций теории алгоритмов и сложности вычислений. Термин «Probably Approximately Correct» был предложен Даной Англуин. Работа Валианта оказала огромное влияние не только на теоретическую информатику, но и на развитие машинного обучения в целом. В 2010 году Лесли Валиант был удостоен премии Тьюринга, в том числе за вклад в создание PAC-теории. Как подчёркивается в современном обзоре, эта работа «изменила ход развития нескольких научных дисциплин».

В последующие годы теория PAC-обучения была значительно расширена. Были установлены связи с теорией статистического обучения В. Н. Вапника и А. Я. Червоненкиса, введены понятия бустинга (преобразование слабого обучения в сильное) и изучены различные варианты модели, включая обучение с шумом и активное обучение. Как отмечает Серведио (2025), «исследовательское сообщество значительно продвинулось в понимании эффективной PAC-обучаемости» с момента публикации работы Валианта.

Варианты и обобщения

Агностическое PAC-обучение (agnostic PAC learning) — отказ от предположения, что целевая функция принадлежит классу $\mathcal{H}$ . В этой области активно исследуются точные границы ошибок в режиме малой ошибки, а также связь с устойчивостью и воспроизводимостью.

Слабое PAC-обучение (weak PAC learning) — алгоритм должен выдавать гипотезу с ошибкой не более $1/2 - \gamma$ . Теория бустинга показывает, что слабое обучение эквивалентно сильному при определённых условиях.

Обучение с запросами (query learning) — алгоритм может активно запрашивать метки для конкретных объектов. Недавние работы исследуют фундаментальные вопросы эффективного PAC-обучения с оракулами, отвечающими только «да» или «нет».

Распределённо-специфическое обучение — вместо требования обучаемости для любого распределения $\mathcal{D}$ , изучаются алгоритмы, эффективные для конкретных распределений.

Контрастивное PAC-обучение (contrastive PAC learning) — новое направление, в котором PAC-гарантии изучаются для контрастивных методов обучения представлений. В работе Шена (2025) предложен первый эффективный PAC-алгоритм для контрастивного обучения линейных представлений.

PAC-Bayes обучение — мощное расширение, позволяющее получать нетривиальные (невакуумные) границы обобщения для глубоких нейронных сетей. Современные разработки включают DPI-PAC-Bayesian фреймворк, который объединяет неравенство обработки данных и PAC-Байесов подход для получения более точных границ, а также мета-обучение с PAC-Bayes гарантиями.

Монотонное PAC-обучение — исследует процессы, в которых ожидаемая ошибка алгоритма монотонно убывает с ростом объёма обучающей выборки.

См. также

Вычислительная теория обучения

VC-размерность

Эмпирическая минимизация риска

Бустинг

Обобщающая способность

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

Литература

Valiant, L. G. A Theory of the Learnable // Communications of the ACM. — 1984. — Т. 27. — № 11. — С. 1134–1142.

Shalev-Shwartz, S.; Ben-David, S. Understanding Machine Learning: From Theory to Algorithms // Cambridge University Press. — 2014. — С. 22–30.

Kearns, M. J.; Vazirani, U. V. An Introduction to Computational Learning Theory // MIT Press. — 1994. — С. 1–19, 45–70 (главы 1 и 3).

Mohri, M.; Rostamizadeh, A.; Talwalkar, A. Foundations of Machine Learning // 2-е изд.. — 2018. — С. 13–78 (главы 2–3).

Haussler, D. Probably Approximately Correct Learning // Proceedings of the 8th National Conference on Artificial Intelligence (AAAI-90). — 1990. — С. 1101–1108.

Asilis, J.; Høgsgaard, M. M.; Velegkas, G. On Agnostic PAC Learning in the Small Error Regime // Advances in Neural Information Processing Systems (NeurIPS). — 2025.

Larsen, K. G. Revisiting Agnostic PAC Learning // arXiv. — 2024.

Blondal, A.; Gao, S.; Hatami, H.; Hatami, P. Stability and List-Replicability for Agnostic Learners // arXiv. — 2025.

Pathak, V. Simplifying Adversarially Robust PAC Learning with Tolerance // arXiv. — 2025.

Shen, J. Towards Efficient Contrastive PAC Learning // arXiv. — 2025.

Guan, M.; et al. A DPI-PAC-Bayesian Framework for Generalization Bounds // IEEE ITW. — 2025.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=PAC-%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5»