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

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

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

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

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

Для формального определения используется некоторое заданное множество ${\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}$ . Это может быть множество всех подмножеств массива бит (ширина шрифта равна 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. . — Morgan Kaufmann Publishers, 1991. — ISBN 1-55860-148-1 .
• D. Haussler. от 28 сентября 2011 на Wayback Machine . An introduction to the topic.
• L. Valiant. Basic Books, 2013. В книге Вэлиант обсуждает, как ВПК-обучение описывает, каким образом организмы развиваются и учатся.