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

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

В этой схеме учитель получает выборки и должен выбрать обобщающую функцию (называемую гипотезой) из определённого класса возможных функций. Целью является функция, которая с большой вероятностью (откуда «вероятно» в названии) будет иметь низкую ошибку обобщения^[en] (откуда «приближенно корректное» в названии). Учитель должен быть способен обучить концепт^[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}}\}}$, каждый из которых содержит только положительные точки. Класс концептов^[en] ${\displaystyle C}$ — множество концептов над ${\displaystyle X}$. Это может быть множество всех подмножеств каркасного^[en] 4-связного^[en] массива бит (ширина шрифта равна 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}$ является однородным классом Гливенко — Кантелли.

См. также

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

Примечания

Литература

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

Эта страница в последний раз была отредактирована 25 сентября 2023 в 07:33.