Вероятностно приблизительно корректное обучение

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Определения и терминология[править | править код]

Чтобы дать определение для объекта, который является ВПК-обучаемым, нам сначала следует ввести некоторые термины[3][4].

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

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

Концепт — подмножество . Один из концептов — множество всех последовательностей бит в , которые кодируют рисунок буквы «P». Примером концепта для второго примера служит множество открытых интервалов, , каждый из которых содержит только положительные точки. Класс концептов[en] — это множество концептов над . Это может быть множество всех подмножеств каркасного[en] 4-связного[en] массива бит (ширина фонта равна 1).

Пусть будет процедурой, которая рисует пример с помощью вероятностного распределения и даёт правильную метку , которая равна 1, если и 0 в противном случае.

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

Эквивалентность[править | править код]

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

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

См. также[править | править код]

Примечания[править | править код]

  1. Valiant1984.
  2. Концептами называют собственные подмножества множества допустимых признаков.
  3. Kearns, Vazirani, 1994, с. 1-12.
  4. Natarajan, 1991.

Литература[править | править код]

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.

Литература для дальнейшего чтения[править | править код]