Вероятно приближённо корректное обучение (ВПК-обучение, англ. Probably Approximately Correct learning, PAC learning) — схема машинного обучения, использующая понятия асимптотической достоверности и вычислительной сложности. Предложена в 1984 году Лесли Вэлиантом^[1].

В этой схеме учитель получает выборки и должен выбрать обобщающую функцию (называемую гипотезой) из определённого класса возможных функций. Целью является функция, которая с большой вероятностью (откуда «вероятно» в названии) будет иметь низкую ошибку обобщения^[англ.] (откуда «приближенно корректное» в названии). Учитель должен быть способен обучить концепт^[2], дающее произвольный коэффициент аппроксимации, вероятность успеха или распределения выборок.

Модель была позднее расширена для обработки шума (некорректно классифицируемых выборок).

Важным нововведением схемы ВПК является использование понятия о вычислительной сложности машинного обучения. В частности, ожидается, что учитель находит эффективные функции (которые ограничены по времени выполнения и требуемому пространству многочленом от размера выборки), и учитель должен реализовать эффективную процедуру (запрашивая размер примера, ограниченный многочленом от размера концепта, модифицированного границами приближения и правдоподобия).

Для формального определения используется некоторое заданное множество ${\displaystyle X}$, называемое признаковым пространством или кодировкой всех выборок. Например, в задаче оптического распознавания символов признаковым пространством является ${\displaystyle X=\{0,1\}^{n))$, а в задаче нахождения интервала (корректно классифицирующей точки внутри интервала как положительные и вне интервала как отрицательные) признаковым пространством является множество всех ограниченных интервалов в ${\displaystyle \mathbb {R} }$.

Ещё одно понятие, используемое в схеме — концепт — подмножество ${\displaystyle c\subset X}$. Например, множество всех последовательностей бит в ${\displaystyle X=\{0,1\}^{n))$, которые кодируют рисунок буквы «P» является одним из концептов в задаче оптического распознавание символов. Примером концепта для задачи нахождения интервала служит множество открытых интервалов ${\displaystyle \{(a,b)\mid 0\leqslant a\leqslant \pi /2,\pi \leqslant b\leqslant {\sqrt {13))\))$, каждый из которых содержит только положительные точки. Класс концептов^[англ.] ${\displaystyle C}$ — множество концептов над ${\displaystyle X}$. Это может быть множество всех подмножеств каркасного^[англ.] 4-связного^[англ.] массива бит (ширина шрифта равна 1).

Пусть ${\displaystyle EX(c,D)}$ будет процедурой, которая формирует пример ${\displaystyle x}$ с помощью вероятностного распределения ${\displaystyle D}$ и даёт правильную метку ${\displaystyle c(x)}$, которая равна 1, если ${\displaystyle x\in c}$ и 0 в противном случае. Теперь, если дано ${\displaystyle 0<\epsilon ,\delta <1}$, предположим, что есть алгоритм ${\displaystyle A}$ и многочлен ${\displaystyle p}$ от ${\displaystyle 1/\epsilon ,1/\delta }$ (и другие относящиеся к делу параметры класса ${\displaystyle C}$) такие, что, если дана выборка размера ${\displaystyle p}$, нарисованный согласно ${\displaystyle EX(c,D)}$, то с вероятностью по меньшей мере ${\displaystyle 1-\delta }$ выход алгоритма ${\displaystyle A}$ является гипотеза ${\displaystyle h\in C}$, которая имеет среднюю ошибку, меньшую или равную ${\displaystyle \epsilon }$ на ${\displaystyle X}$ для одного и того же распределения ${\displaystyle D}$. Далее, если утверждение выше для алгоритма ${\displaystyle A}$ верно для любого концепта ${\displaystyle c\in C}$ и для любого распределения ${\displaystyle D}$ над ${\displaystyle X}$ и для всех ${\displaystyle 0<\epsilon ,\delta <1}$, тогда ${\displaystyle C}$ является (эффективно) ВПК-обучаемым (или свободным от распределения ВПК-обучаемым). В этом случае считается, что ${\displaystyle A}$ является алгоритмом ВПК-обучения для ${\displaystyle C}$.

При определённых условиях регулярности эти три условия эквивалентны:

1. Класс понятий ${\displaystyle C}$ является ВПК-обучаемым.
2. Размерность Вапника — Червоненкиса класса ${\displaystyle C}$ конечна.
3. ${\displaystyle C}$ является однородным классом Гливенко — Кантелли.

• Отказоустойчивость (ВПК-обучение)^[англ.]
• Сложность выборки^[англ.]

• Valiant L. A theory of the learnable // Communications of the ACM. — 1984. — Вып. 27.
• Kearns M., Vazirani U. An Introduction to Computational Learning Theory. — MIT Press, 1994. — ISBN 9780262111935.
• Balas Kausik Natarajan. Machine Learning. A Theoretical Approach. — Morgan Kaufmann Publishers, 1991. — ISBN 1-55860-148-1.
• D. Haussler. Overview of the Probably Approximately Correct (PAC) Learning Framework Архивная копия от 28 сентября 2011 на Wayback Machine. An introduction to the topic.
• L. Valiant. Probably Approximately Correct. Basic Books, 2013. В книге Вэлиант обсуждает, как ВПК-обучение описывает, каким образом организмы развиваются и учатся.

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамблевое обучение Бэггинг Бустинг Метод случайного леса Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Размерность Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG