Введение

Рамки математического анализа машинного обучения

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

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

Чтобы дать определение тому, что можно изучить в рамках PAC-обучения, мы сначала должны ввести некоторую терминологию. Для следующих определений будут использованы два примера. Первый – это задача распознавания символов, заданная массивом битов, кодирующих изображение, принимающее двоичные значения. Второй пример – задача поиска интервала, который правильно классифицирует точки внутри интервала как положительные, а точки вне интервала – как отрицательные. Пусть – множество, называемое пространством экземпляров или кодировкой всех образцов. В задаче распознавания символов пространство экземпляров равно . В задаче с интервалами пространство экземпляров, , представляет собой множество всех ограниченных интервалов в , где обозначает множество всех действительных чисел. Концепция – это подмножество . Одна концепция – это множество всех шаблонов битов в , кодирующих изображение буквы "P". Примером концепции из второго примера является множество открытых интервалов, , каждый из которых содержит только положительные точки. Класс концепций – это коллекция концепций над . Это может быть множество всех подмножеств массива битов, имеющих скелетизированную 4-связность (ширина шрифта равна 1). Пусть – процедура, которая генерирует пример , используя распределение вероятностей и возвращает правильную метку , то есть 1, если и 0 в противном случае. Теперь, задано , предположим, что существует алгоритм и полином от (и других соответствующих параметров класса) такие, что, получив выборку размера , сформированную согласно , алгоритм с вероятностью не менее выдает гипотезу , имеющую среднюю ошибку не более на с тем же распределением . Более того, если вышеуказанное утверждение для алгоритма верно для каждой концепции и для каждого распределения над , и для всех , то (эффективно) PAC-обучаема (или PAC-обучаема без учета распределения). Мы также можем сказать, что является PAC-алгоритмом обучения для .