Вероятно, приблизительно правильное обучение

Фреймворк для математического анализа машинного обучения

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

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

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

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

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

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

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

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

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

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

Теперь, учитывая , предположим, что существует алгоритм и полином в (и другие соответствующие параметры класса ), такие, что, учитывая выборку размера, составленную в соответствии с , то с вероятностью не менее , выводит гипотезу , которая имеет среднюю ошибку, меньшую или равную на с тем же распределением . Далее, если приведенное выше утверждение для алгоритма верно для каждой концепции и для каждого распределения по , и для всех , то (эффективно) PAC-обучаемый (или PAC-обучаемый без распределения ). Мы также можем сказать, что является алгоритмом обучения PAC для . ${\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}$ ${\displaystyle A}$ ${\displaystyle C}$

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

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

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

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

• обучение по методу Оккама
• Сбор данных
• Устойчивость к ошибкам (обучение PAC)
• Сложность образца

Ссылки

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

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

• М. Кернс, У. Вазирани. Введение в теорию вычислительного обучения. MIT Press, 1994. Учебник.
• M. Mohri, A. Rostamizadeh и A. Talwalkar. Основы машинного обучения . MIT Press, 2018. Глава 2 содержит подробное рассмотрение PAC-обучаемости. Читается через открытый доступ от издателя.
• Д. Хаусслер. Обзор Вероятно Приблизительно Правильной (PAC) Структуры Обучения. Введение в тему.
• Л. Вэлиант. Вероятно, приблизительно верно. Basic Books, 2013. В котором Вэлиант утверждает, что обучение PAC описывает, как организмы развиваются и обучаются.
• Littlestone, N.; Warmuth, MK (10 июня 1986 г.). "Связь сжатия данных и обучаемости" (PDF) . Архивировано из оригинала (PDF) 2017-08-09.
• Моран, Шай; Йехудайофф, Амир (2015). «Примеры схем сжатия для классов VC». arXiv : 1503.06960 [cs.LG].

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

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