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

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

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

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

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

Определения и терминология

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

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

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

Эквивалентность

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

1. Класс понятий $C$ является ВПК-обучаемым.
2. Размерность Вапника — Червоненкиса класса $C$ конечна.
3. $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. В книге Вэлиант обсуждает, как ВПК-обучение описывает, каким образом организмы развиваются и учатся.