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

Часть серии по
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Разработка функций Особенности обучения Онлайн обучение Полу-контролируемое обучение Обучение без учителя Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k- означает Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор локального выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Глоссарий искусственного интеллекта Глоссарий искусственного интеллекта
Статьи по Теме Список наборов данных для исследований в области машинного обучения Схема машинного обучения
v т е

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

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

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

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

Определения и терминология [ править ]

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

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

Позвольте быть набором, называемым пространством экземпляров или кодировкой всех образцов. В задаче распознавания символов пространство экземпляра равно . В задаче об интервале пространство экземпляров , является набором всех ограниченных интервалов в , где обозначает набор всех действительных чисел.${\ displaystyle X}$${\ Displaystyle Х = \ {0,1 \} ^ {п}}$${\ 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 изучаемый ). Мы также можем сказать, что это${\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}$Алгоритм обучения PAC для .${\displaystyle C}$

Эквивалентность [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

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 описывает, как организмы развиваются и обучаются.