Наверное, примерно правильное обучение - Probably approximately correct learning

В теории вычислительного обучения , вероятно, приблизительно правильное ( PAC ) обучение - это основа для математического анализа машинного обучения . Он был предложен в 1984 году Лесли Валиантом .

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

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

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

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

Чтобы дать определение чему-то, что можно изучить с помощью PAC, мы сначала должны ввести некоторую терминологию.

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

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

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

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

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

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

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

  1. Концептуальный класс C доступен для обучения PAC.
  2. Размерность ВК из C конечна.
  3. C - равномерный класс Гливенко – Кантелли .
  4. С является сжимаемым в смысле Littlestone и Warmuth

Смотрите также

использованная литература

  1. ^ Л. Вэлиант. Теория изучаемого. Сообщения ACM, 27, 1984.
  2. ^ Кернс и Вазирани, стр. 1-12,
  3. ^ Балас Каусик Натараджан, Машинное обучение, теоретический подход, издательство Morgan Kaufmann, 1991
  4. ^ Блюмер, Ансельм; Эренфойхт, Анджей; Дэвид, Хаусслер; Манфред, Вармут (октябрь 1989 г.). «Обучаемость и измерение Вапника-Червоненкиса». Журнал Ассоциации вычислительной техники . 36 (4): 929–965. DOI : 10.1145 / 76359.76371 . S2CID  1138467 .

https://users.soe.ucsc.edu/~manfred/pubs/lrnk-olivier.pdf

Моран, Шэй; Иегудаофф, Амир (2015). «Примеры схем сжатия для классов ВК». arXiv : 1503.06960 [ cs.LG ].

дальнейшее чтение