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

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

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

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

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

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

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

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

Позволять ${ displaystyle X}$ быть набором, называемым пространство экземпляра или кодирование всех образцов. В задаче распознавания символов пространство экземпляра ${ Displaystyle Х = {0,1 } ^ {п}}$ . В задаче об интервале пространство экземпляров, ${ displaystyle X}$ , - множество всех ограниченных интервалов в ${ Displaystyle mathbb {R}}$ , где ${ Displaystyle mathbb {R}}$ обозначает набор всех действительных чисел.

А концепция это подмножество ${ displaystyle c subset X}$ . Одна концепция - это набор всех комбинаций битов в ${ Displaystyle Х = {0,1 } ^ {п}}$ которые кодируют изображение буквы «П». Пример концепции из второго примера - это набор открытых интервалов, ${ displaystyle {(a, b) mid 0 leq a leq pi / 2, pi leq b leq { sqrt {13}} }}$ , каждая из которых содержит только положительные точки. А концептуальный класс ${ displaystyle C}$ это собрание концепций над ${ displaystyle X}$ . Это может быть набор всех подмножеств массива битов, которые скелетонизированный 4-связный (ширина шрифта 1).

Позволять ${ displaystyle EX (c, D)}$ быть процедурой, которая рисует пример, ${ displaystyle x}$ , используя распределение вероятностей ${ displaystyle D}$ и дает правильный ярлык ${ Displaystyle с (х)}$ , то есть 1, если ${ displaystyle x in c}$ и 0 в противном случае.

Теперь, учитывая ${ Displaystyle 0 < epsilon, delta <1}$ , предположим, что есть алгоритм ${ displaystyle A}$ и многочлен ${ displaystyle p}$ в ${ displaystyle 1 / epsilon, 1 / delta}$ (и другие соответствующие параметры класса ${ displaystyle C}$ ) такой, что, учитывая размер выборки ${ displaystyle p}$ нарисованный в соответствии с ${ displaystyle EX (c, D)}$ , то с вероятностью не менее ${ displaystyle 1- delta}$ , ${ displaystyle A}$ выводит гипотезу ${ displaystyle h in C}$ со средней погрешностью меньше или равной ${ displaystyle epsilon}$ на ${ displaystyle X}$ с таким же распределением ${ displaystyle D}$ . Далее, если приведенное выше утверждение для алгоритма ${ displaystyle A}$ верно для любой концепции ${ displaystyle c in C}$ и для каждого распределения ${ displaystyle D}$ над ${ displaystyle X}$ , и для всех ${ displaystyle 0 < epsilon, delta <1}$ тогда ${ displaystyle C}$ (эффективно) PAC обучаемый (или без распространения PAC обучаемый). Мы также можем сказать, что ${ displaystyle A}$ это Алгоритм обучения PAC для ${ displaystyle C}$ .

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

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

Концептуальный класс C можно ли выучить PAC.
В Размер ВК из C конечно.
C униформа Класс Гливенко-Кантелли.^{[требуется разъяснение ]}
C является сжимаемый в смысле Литтлстоуна и Вармута

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

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

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

[valiant-1] Л. Валиант. Теория изучаемого. Сообщения ACM, 27, 1984.

[2] Кирнс и Вазирани, стр. 1-12,

[3] Балас Каусик Натараджан, Машинное обучение, теоретический подход, издательство Morgan Kaufmann, 1991

[4] Блумер, Ансельм; Эренфойхт, Анджей; Дэвид, Хаусслер; Манфред, Вармут (октябрь 1989 г.). «Обучаемость и измерение Вапника-Червоненкиса». Журнал Ассоциации вычислительной техники. 36 (4): 929–965. Дои:10.1145/76359.76371. S2CID 1138467.

[1]

[2]

[3]

[4]