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

В теории вычислительного обучения вероятно приблизительно правильное ( 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 \operatorname {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 \operatorname {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)
• Сложность образца

• М. Кернс, У. Вазирани. Введение в теорию вычислительного обучения. 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