В теории вычислительного обучения , вероятно, приблизительно правильное ( PAC ) обучение - это основа для математического анализа машинного обучения . Он был предложен в 1984 году Лесли Валиантом . [1]
В этой структуре учащийся получает образцы и должен выбрать функцию обобщения (называемую гипотезой ) из определенного класса возможных функций. Цель состоит в том, чтобы с высокой вероятностью (часть "вероятно") выбранная функция имела низкую ошибку обобщения (часть "приблизительно правильная"). Учащийся должен уметь усвоить концепцию с учетом любого произвольного коэффициента приближения, вероятности успеха или распределения выборок .
Позже модель была расширена для обработки шума (неправильно классифицированные образцы).
Важным нововведением структуры PAC является введение концепций теории сложности вычислений в машинное обучение. В частности, ожидается, что учащийся найдет эффективные функции (требования по времени и пространству ограничены полиномом размера примера), а сам учащийся должен реализовать эффективную процедуру (требующую, чтобы количество примеров ограничивалось полиномом размера концепции, измененным оценками аппроксимации и правдоподобия ).
Определения и терминология
Чтобы дать определение чему-то, что можно изучить с помощью PAC, мы сначала должны ввести некоторую терминологию. [2] [3]
Для следующих определений будут использованы два примера. Первая - это проблема распознавания символов по массивубиты, кодирующие двоичное изображение. Другой пример - проблема поиска интервала, который правильно классифицирует точки в пределах интервала как положительные, а точки вне диапазона как отрицательные.
Позволять быть набором, называемым пространством экземпляров, или кодировкой всех образцов. В задаче распознавания символов пространство экземпляра. В задаче об интервале пространство экземпляров,, - множество всех ограниченных интервалов в , где обозначает набор всех действительных чисел .
Концепция является подмножеством. Одна концепция - это набор всех комбинаций битов вкоторые кодируют изображение буквы «П». Пример концепции из второго примера - это набор открытых интервалов,, каждая из которых содержит только положительные точки. Класс концепция это собрание концепций над . Это может быть набор всех подмножеств массива битов, скелетонизированных 4-связными (ширина шрифта равна 1).
Позволять быть процедурой, которая рисует пример, , используя распределение вероятностей и дает правильный ярлык , то есть 1, если и 0 в противном случае.
Теперь, учитывая , предположим, что есть алгоритм и многочлен в (и другие соответствующие параметры класса ) такой, что, учитывая размер выборки нарисованный в соответствии с , то с вероятностью не менее , выводит гипотезу со средней ошибкой меньше или равной на с таким же распределением . Кроме того, если приведенное выше утверждение для алгоритма верно для любой концепции и для каждого распределения над , и для всех тогда является (эффективно) обучаемым PAC (или обучаемым PAC без распространения ). Мы также можем сказать, чтоявляется алгоритм обучения PAC для.
Эквивалентность
При некоторых условиях регулярности эти условия эквивалентны: [4]
- Концептуальный класс C доступен для обучения PAC.
- Размерность ВК из C конечна.
- C - равномерный класс Гливенко – Кантелли . [ требуется разъяснение ]
- С является сжимаемым в смысле Littlestone и Warmuth
Смотрите также
Рекомендации
- ^ Л. Вэлиант. Теория изучаемого. Сообщения ACM, 27, 1984.
- ^ Кернс и Вазирани, стр. 1-12,
- ^ Балас Каусик Натараджан, Машинное обучение, теоретический подход, издательство Morgan Kaufmann, 1991
- ^ Блюмер, Ансельм; Эренфойхт, Анджей; Дэвид, Хаусслер; Манфред, Вармут (октябрь 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 ].
дальнейшее чтение
- М. Кернс, У. Вазирани. Введение в теорию вычислительного обучения . MIT Press, 1994. Учебник.
- М. Мохри, А. Ростамизаде, А. Талвалкар. Основы машинного обучения . MIT Press, 2018. Глава 2 содержит подробное рассмотрение PAC-обучаемости. Доступно для чтения через открытый доступ от издателя.
- Д. Хаусслер. Обзор схемы обучения «Вероятно приблизительно правильное» (PAC) . Введение в тему.
- Л. Валиант. Наверное, примерно правильно. Basic Books, 2013. В этой статье Valiant утверждает, что обучение PAC описывает, как организмы развиваются и учатся.