Вероятно приближённо корректное обучение

Для формального определения используется некоторое заданное множество ${\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. В книге Вэлиант обсуждает, как ВПК-обучение описывает, каким образом организмы развиваются и учатся.