Вероятностно приблизительно корректное обучение

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