Наверное примерно правильное обучение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

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

М. Кернс, У. Вазирани. Введение в теорию вычислительного обучения . MIT Press, 1994. Учебник.
М. Мори, А. Ростамизаде и А. Талвалкар. Основы машинного обучения . MIT Press, 2018. Глава 2 содержит подробное описание обучаемости PAC. Читается в открытом доступе от издателя.
Д. Хаусслер. Обзор системы обучения «вероятно приблизительно правильно» (PAC) . Введение в тему.
Л. Валиант. Наверное, примерно правильно. Basic Books, 2013. В котором Валиант утверждает, что обучение PAC описывает, как организмы развиваются и обучаются.
Литлстоун, Н.; Вармут, МК (10 июня 1986 г.). «Связь между сжатием данных и обучаемостью» (PDF) . Архивировано из оригинала (PDF) 9 августа 2017 г.
Моран, Шей; Иегудаофф, Амир (2015). «Примеры схем сжатия для классов VC». arXiv : 1503.06960 [ cs.LG ].

Внешние ссылки

Интерактивное объяснение обучения PAC

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

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

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

[ 1 ]

[ 2 ]

[ 3 ]