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

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

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

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

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

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

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

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

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

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

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

1. Класс понятий $C$ является ВПК-обучаемым.
2. Размерность Вапника — Червоненкиса класса $C$ конечна.
3. $C$ является однородным классом Гливенко — Кантелли.

См. также

• Шаблон:Не переведено 5
• Шаблон:Не переведено 5

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• D. Haussler. Overview of the Probably Approximately Correct (PAC) Learning Framework Шаблон:Wayback. An introduction to the topic.
• L. Valiant. Probably Approximately Correct. Basic Books, 2013. В книге Вэлиант обсуждает, как ВПК-обучение описывает, каким образом организмы развиваются и учатся.