Теория Валианта
Материал из MachineLearning.
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Теория вероятно почти корректного обучения (теория Валианта, probably approximately correct, PAC-learning) — теория, предложенная Лесли Валиантом в 1984 году для математического анализа машинного обучения. Работа Валианта акцентирует внимание на том, что проблематика вычислительного обучения тесно связана также и с вопросам вычислительной сложности алгоритмов.
В теории вероятно почти корректного обучения обучаемый (learner) получает некоторый набор примеров и должен выбрать некоторую функцию (гипотезу) из определенного класса функций. Цель обучаемого состоит в том, чтобы с высокой вероятностью выбранная функция была, в некотором смысле, «похожа» на истинную гипотезу. Обучаемый должен быть эффективным (то есть использовать в процессе работы приемлемое количество вычислительных ресурсов).
Содержание |
Вероятно почти корректное обучение
Основные понятия
- Обучаемый (learner) — объект, участвующий в процессе обучения. В данном контексте обучаемый — алгоритм.
- Объекты на которых выполняется обучение назовём примерами. Поскольку нам будет важна вычислительная сложность, будем считать, что примеры задаются некоторым описанием — булевым вектором.
-
— множество примеров с описанием длины n.
-
— пространство примеров (instance space), множество всех возможных примеров.
-
— (неизвестное) вероятностное распределение на пространстве примеров. x ~ D — означает, что x - случайная величина с распределением D.
- Каждый пример имеет одну пометку, для простоты будем считать, что множество пометок состоит из двух элементов: {0,1}. Концепция(concept) — это функция, отображающая примеры на пометки.
— семейство концепций, подмножество множества всех булевых функций, определенных на множестве X.
-
— целевая концепция: то, что мы ищем в процессе обучения.
- Гипотеза h — некоторая булева функция на множестве
, которую выдает обучаемый. Гипотеза является предсказанием целевой концепции.
- Ошибка гипотезы.
— вероятность того, что гипотеза h не совпадает с целевой концепцией f на случайном значении x ~ D:
.
Алгоритм вероятно почти корректного обучения
Определение: Алгоритм A называется алгоритмом вероятно почти корректного обучения для семейства концепций F, если выполнено следующее:
Для любого n,
для любой функции ,
для любого распределения
для любого параметра ошибки 0 < ε < 1,
для любого параметра уверенности 0 < δ < 1,
для обучающей выборки
(обучающие примеры — независимые одинаково распределенные случайные величины с распределением D)
алгоритм A выдает гипотезу h такую, что:
где вероятность определяется распределением обучающих примеров D и случайными значениями, используемыми алгоритмом A (алгоритм может быть вероятностным).
.
В данном определении отражен один вариант обучения предложенный Валиантом — с использованием процедуры EXAMPLE(). Процедура EXAMPLE() не имеет входных значений, она возвращает пару <x,f(x)>, где x ~ D. Второй вариант — использование процедуры ORACLE(x). Процедура ORACLE(x) для входного значения x возвращает f(x).
Вопрос эффективности определяется двумя аспектами:
- Вычислительная сложность алгоритма PAC learning. Будем считать, что алгоритм обучения эффективен, если он выполняется за время полиномиальное от n, 1/ε, 1/δ, size(f), где size(f) — длина описания
. Заметим, что обычно size(f) имеет полиномиальный от n размер.
- Сколько примеров требуется для обучения.
Объем обучающей выборки (Sample complexity)
Определение
Связь с параметрами обучения для конечных классов концепций.
Связь с параметрами обучения для беcконечных классов концепций с конечной размерностью Вапника-Червонескиса.
Пример: протокол обучения для булевых функций
Мы хотим изучить некоторую (неизвестную) булеву функцию. Для решения задачи в общем виде требуется протестировать наборов для n-арной функции. Ограничим класс возможных функций до класса функций, представимых в конъюктивной нормальной форме с ограниченным числом слагаемых в каждом конъюнкте и попробуем добиться приемлемой сложности обучения.
Пусть имеется t булевых переменных: . Значения переменных будем задавать вектором вида
, где
- означает неопределенное значение. Вектор назовем полным, если в нем отсутствуют неопределенные значения. Булева функция F_t отображает двоичные вектора длины t на множество {0,1}. Расширим определение функции на неполные вектора, будем считать, что
тогда и только когда F(u) = 1 для всех векторов u, полученных дополнением вектора v до полного. Пусть EXAMPLE() выдает наборы, на которых функция
равна 1. Например, для функции
: EXAMPLE() → (*, *, 1); EXAMPLE() → (1, 1, 0).
Будем считать, что функция изучаема, если существует алгоритм, который работает за полиномиальное от t и h время с параметром уверенности δ > 1 - 1/h и параметром ошибки следующего вида. Выдаваемая функция g такова, что:
- всегда, если g(v) = 1, то
;
- cумма вероятностей D[v] по всем v таким, что
, но
, не превосходит 1/h.
Для функций, представимых в конъюктивной нормальной форме с числом слагаемых равным k можно предложить следующий тривиальный алгоритм нахождения целевой функции.
Алгоритм:
g = произведение всех возможных конъюнктов длины k; //инициализация for(i = 0; i < L; i++) // L — число раудов v = EXAMPLE(); for (j = 0; j < m; j++) // m —- число конъюнктов в g if (конъюнктне равен 1 на v) then удалить конъюнкт
из g; return g;
— минимальное целое число такое, что вероятность события: среди
независимых испытаний по Бернулли с вероятностью успеха h будет меньше чем s успешных, меньше чем 1/h. Верхняя оценка:
Теорема Для любого k функция от t переменных, представимая в конъюктивной нормальной форме с числом слагаемых равным k, изучаема через предложенный алгоритм с числом раудов .
Вычислительная сложность обучения
Связь PAC-learning с классами сложности (), математической криптографией (односторонние функции, криптосистемы)
Ссылки
- Valiant L.G. A theory of the learnable // Communications of the ACM. — 1984 T. 27. — С. 1134-1142.
- Goldreich O. Introduction to Complexity Theory // The Weizmann Institute of Science, lecture Notes for a Two-Semester course. — 1999.
- Goldman S.A. Computational Learning Theory // Washington University, lecture Notes. — 1991.
- Anthony M., Biggs N. Computational Learning Theory: An Introduction // Cambridge. University Press. — 1992.