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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Valiant1984.
  2. Концептами называют собственные подмножества множества допустимых признаков.

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

  • 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. An introduction to the topic.
  • L. Valiant. Probably Approximately Correct. Basic Books, 2013. В книге Вэлиант обсуждает, как ВПК-обучение описывает, каким образом организмы развиваются и учатся.