Теория Валианта

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
м (категория)
м (оформление)
Строка 1: Строка 1:
{{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}}
{{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}}
-
'''Теория вероятно почти корректного обучения''' (теория Валианта, probably approximately correct, PAC-learning) — теория, предложенная Лесли Валиантом в 1984 году для математического анализа машинного обучения. Работа Валианта акцентирует внимание на том, что проблематика вычислительного обучения тесно связана также и с вопросам[[вычислительная сложность | вычислительной сложности алгоритмов]].
+
'''Теория вероятно почти корректного обучения''' (теория Валианта, probably approximately correct learning, PAC-learning) — теория, предложенная Лесли Валиантом в 1984 году для математического анализа машинного обучения. Работа Валианта акцентирует внимание на том, что проблематика вычислительного обучения тесно связана также и с вопросам[[вычислительная сложность | вычислительной сложности алгоритмов]].
В теории вероятно почти корректного обучения обучаемый (learner) получает некоторый набор примеров и должен выбрать некоторую функцию (гипотезу) из определенного класса функций. Цель обучаемого состоит в том, чтобы с высокой вероятностью выбранная функция была, в некотором смысле, «похожа» на истинную гипотезу. Обучаемый должен быть '''эффективным''' (то есть использовать в процессе работы приемлемое количество вычислительных ресурсов).
В теории вероятно почти корректного обучения обучаемый (learner) получает некоторый набор примеров и должен выбрать некоторую функцию (гипотезу) из определенного класса функций. Цель обучаемого состоит в том, чтобы с высокой вероятностью выбранная функция была, в некотором смысле, «похожа» на истинную гипотезу. Обучаемый должен быть '''эффективным''' (то есть использовать в процессе работы приемлемое количество вычислительных ресурсов).

Версия 22:17, 2 января 2010

Данная статья является непроверенным учебным заданием.
Студент: Участник:DmitryKonstantinov
Преподаватель: Участник:Константин Воронцов
Срок: 8 января 2010

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.


Теория вероятно почти корректного обучения (теория Валианта, probably approximately correct learning, PAC-learning) — теория, предложенная Лесли Валиантом в 1984 году для математического анализа машинного обучения. Работа Валианта акцентирует внимание на том, что проблематика вычислительного обучения тесно связана также и с вопросам вычислительной сложности алгоритмов.

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

Содержание

Вероятно почти корректное обучение

Основные понятия

  • Обучаемый (learner) — объект, участвующий в процессе обучения. В данном контексте обучаемый — алгоритм.
  • Объекты на которых выполняется обучение назовём примерами. Поскольку нам будет важна вычислительная сложность, будем считать, что примеры задаются некоторым описанием — булевым вектором.
  • X_n — множество примеров с описанием длины n.
  • X = \bigcup_{n \geq 1} X_n — пространство примеров (instance space), множество всех возможных примеров.
  • D: X_n \rightarrow [0,1] — (неизвестное) вероятностное распределение на пространстве примеров. x ~ D — означает, что x - случайная величина с распределением D.
  • Каждый пример имеет одну пометку, для простоты будем считать, что множество пометок состоит из двух элементов: {0,1}. Концепция(concept) — это функция, отображающая примеры на пометки. F = \bigcup_{n \geq 1} F_n — семейство концепций, подмножество множества всех булевых функций, определенных на множестве X.
  • f \in F_n — целевая концепция: то, что мы ищем в процессе обучения.
  • Гипотеза h — некоторая булева функция на множестве X_n, которую выдает обучаемый. Гипотеза является предсказанием целевой концепции.
  • Ошибка гипотезы. err_{f,D}(h) — вероятность того, что гипотеза h не совпадает с целевой концепцией f на случайном значении x ~ D: err_{f,D}(h) = Pr_{x \sim D}[f(x) \neq h(x)].

Алгоритм вероятно почти корректного обучения

Определение: Алгоритм A называется алгоритмом вероятно почти корректного обучения для семейства концепций F, если выполнено следующее:

Для любого n, для любой функции f \in F_n, для любого распределения D: X_n \rightarrow [0,1] для любого параметра ошибки 0 < ε < 1, для любого параметра уверенности 0 < δ < 1, для обучающей выборки {<x^i,f(x^i)>}_{i=1}^{m} (обучающие примеры — независимые одинаково распределенные случайные величины с распределением D) алгоритм A выдает гипотезу h такую, что:

 Pr[err_{f,D}(h) < \epsilon] > 1 - \delta

где вероятность определяется распределением обучающих примеров D и случайными значениями, используемыми алгоритмом A (алгоритм может быть вероятностным). h = A(n,\epsilon,\delta,{<x^i,f(x^i)>}_{i=1}^{m}).

В данном определении отражен один вариант обучения предложенный Валиантом — с использованием процедуры EXAMPLE(). Процедура EXAMPLE() не имеет входных значений, она возвращает пару <x,f(x)>, где x ~ D. Второй вариант — использование процедуры ORACLE(x). Процедура ORACLE(x) для входного значения x возвращает f(x).

Вопрос эффективности определяется двумя аспектами:

  1. Вычислительная сложность алгоритма PAC learning. Будем считать, что алгоритм обучения эффективен, если он выполняется за время полиномиальное от n, 1/ε, 1/δ, size(f), где size(f) — длина описания f \in F_n. Заметим, что обычно size(f) имеет полиномиальный от n размер.
  2. Сколько примеров требуется для обучения. Связь между объемом обучающей выборки (Sample complexity) и параметрами алгоритма вероятно почти корректного обучения характеризуют теоремы бритвы Оккама.

Пример: протокол обучения для булевых функций

Мы хотим изучить некоторую (неизвестную) булеву функцию. Для решения задачи в общем виде требуется протестировать 2^n наборов для n-арной функции. Ограничим класс возможных функций до класса функций, представимых в конъюктивной нормальной форме с ограниченным числом слагаемых в каждом конъюнкте и попробуем добиться приемлемой сложности обучения.

Пусть имеется t булевых переменных: p_1 \dots p_t. Значения переменных будем задавать вектором вида \{0,1,*\}^t, где * - означает неопределенное значение. Вектор назовем полным, если в нем отсутствуют неопределенные значения. Булева функция F_t отображает двоичные вектора длины t на множество {0,1}. Расширим определение функции на неполные вектора, будем считать, что F_t(v) = 1 тогда и только когда F(u) = 1 для всех векторов u, полученных дополнением вектора v до полного. Пусть EXAMPLE() выдает наборы, на которых функция F_t равна 1. Например, для функции F_3(p) = p_1p_2+p_3: EXAMPLE() → (*, *, 1); EXAMPLE() → (1, 1, 0).

Будем считать, что функция изучаема, если существует алгоритм, который работает за полиномиальное от t и h время с параметром уверенности δ > 1 - 1/h и параметром ошибки следующего вида. Выдаваемая функция g такова, что:

  1. всегда, если g(v) = 1, то F_t(v) = 1;
  2. cумма вероятностей D[v] по всем v таким, что F_t(v) = 1, но g(v) \neq 1, не превосходит 1/h.

Для функций, представимых в конъюктивной нормальной форме с числом слагаемых равным k можно предложить следующий тривиальный алгоритм нахождения целевой функции.

Алгоритм:

g = произведение всех возможных конъюнктов длины k; //инициализация
for(i = 0; i < L; i++) // L — число раудов
  v = EXAMPLE();
  for (j = 0; j < m; j++) // m —- число конъюнктов в g
  if (конъюнкт c_j не равен 1 на v) then удалить конъюнкт c_j из g;
return g;

L(h,s) — минимальное целое число такое, что вероятность события: среди L(h,s) независимых испытаний по Бернулли с вероятностью успеха h будет меньше чем s успешных, меньше чем 1/h. Верхняя оценка: L(h,s) \leq 2h(s + \ln h)

Теорема Для любого k функция от t переменных, представимая в конъюктивной нормальной форме с числом слагаемых равным k, изучаема через предложенный алгоритм с числом раундов L = L(h, (2t)^{k+1}).

Вычислительная сложность обучения

Если класс концепции конечен или имеет конечную размерность Вапника-Червоненкиса, то после получения достаточного количества учебных примеров можно «предсказывать будущее», просто находя гипотезу удовлетворяющую учебным примерам (Бритва Оккама). Но какова вычислительная сложность задачи поиска гипотезы, удовлетворяющей обучающей выборке? Такая задача вполне может быть NP-полной. В частности, она напоминает вопрос выполнимости булевой функции, хотя, это и не совсем то же самое.

Тут следует рассмотреть два варианта. Надлежащее обучение (proper learning) — когда гипотеза выдается в некотором фиксированном формате (например, в виде дизъюнктивной нормальной формы). В таком случае возможно доказать, что в некоторых случаях задача нахождения гипотезы, удовлетворяющей обучающей выборке, является NP-полной. При ненадлежащем обучении (improper learning) гипотеза является произовольным алгоритмом, работающим за полиномиальное время и удовлетворяющим обучающей выборке. На сегодняшний день ничего не известно о NP-полноте задачи поиска гипотезы в такой форме.

С другой стороны, задача поиска подходящей гипотезы лежит в классе NP, поскольку для данной гипотезы легко проверить удовлетворяет ли она обучающей выборке. Таким образом в случае, если P = NP — любая задача обучения является полиномиальной. Сложность и разнообразность задач такого типа — это еще один аргумент в пользу того, что P \neq NP.

Cуществуют некоторые аналогии между криптографией и вычислительным обучением.

Ссылки

  1. Valiant L.G. A theory of the learnable // Communications of the ACM. — 1984 T. 27. — С. 1134-1142.
  2. Goldreich O. Introduction to Complexity Theory // The Weizmann Institute of Science, lecture Notes for a Two-Semester course. — 1999.
  3. Goldman S.A. Computational Learning Theory // Washington University, lecture Notes. — 1991.
  4. Anthony M., Biggs N. Computational Learning Theory: An Introduction // Cambridge. University Press. — 1992.
Личные инструменты