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

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Вероятно почти корректное обучение: дополнение)
(дополнение)
Строка 17: Строка 17:
* Ошибка гипотезы. <tex>err_{f,D}(h)</tex> — вероятность того, что гипотеза h не совпадает с целевой концепцией f на случайном значении x ~ D: <tex>err_{f,D}(h) = Pr_{x \sim D}[f(x) \neq h(x)]</tex>.
* Ошибка гипотезы. <tex>err_{f,D}(h)</tex> — вероятность того, что гипотеза h не совпадает с целевой концепцией f на случайном значении x ~ D: <tex>err_{f,D}(h) = Pr_{x \sim D}[f(x) \neq h(x)]</tex>.
-
=== * Алгоритм вероятно почти корректного обучения ===
+
=== Алгоритм вероятно почти корректного обучения ===
-
Алгоритм A называется алгоритмом вероятно почти корректного обучения для семейства концепций F, если выполнено следующее:
+
'''Определение:''' Алгоритм A называется алгоритмом вероятно почти корректного обучения для семейства концепций F, если выполнено следующее:
Для любого n,
Для любого n,
для любой функции <tex>f \in F_n</tex>,
для любой функции <tex>f \in F_n</tex>,
 +
для '''любого''' распределения <tex>D: X_n \rightarrow [0,1]</tex>
для любого параметра ошибки 0 < ε < 1,
для любого параметра ошибки 0 < ε < 1,
для любого параметра уверенности 0 < δ < 1,
для любого параметра уверенности 0 < δ < 1,
для обучающей выборки <tex>{<x^i,f(x^i)>}_{i=1}^{m}</tex> (обучающие примеры — независимые одинаково распределенные случайные величины с распределением D)
для обучающей выборки <tex>{<x^i,f(x^i)>}_{i=1}^{m}</tex> (обучающие примеры — независимые одинаково распределенные случайные величины с распределением D)
-
алгоритм A выдает гипотезу h такую, что
+
алгоритм A выдает гипотезу h такую, что:
<tex> Pr[err_{f,D}(h) < \epsilon] > 1 - \delta </tex>
<tex> Pr[err_{f,D}(h) < \epsilon] > 1 - \delta </tex>
-
где вероятность определяется распределением примеров D и случайными значениями, используемыми алгоритмом A (алгоритм может быть вероятностным).
+
где вероятность определяется распределением обучающих примеров D и случайными значениями, используемыми алгоритмом A (алгоритм может быть вероятностным).
 +
<tex>h = A(n,\epsilon,\delta,{<x^i,f(x^i)>}_{i=1}^{m})</tex>.
 +
В данном определении отражен один вариант обучения предложенный Валиантом — с использованием процедуры EXAMPLE(). Процедура EXAMPLE() не имеет входных значений, она возвращает пару <x,f(x)>, где x ~ D. Второй вариант — использование процедуры ORACLE(x). Процедура ORACLE(x) для входного значения x возвращает f(x).
 +
 +
Вопрос эффективности определяется двумя аспектами:
 +
# Вычислительная сложность алгоритма PAC learning. Будем считать, что алгоритм обучения эффективен, если он выполняется за время полиномиальное от n, 1/ε, 1/δ, size(f), где size(f) — длина описания <tex>f \in F_n</tex>. Заметим, что обычно size(f) имеет полиномиальный от n размер.
 +
# Сколько примеров требуется для обучения.
== Объем обучающей выборки (Sample complexity) ==
== Объем обучающей выборки (Sample complexity) ==
Определение, теоремы
Определение, теоремы

Версия 11:43, 2 января 2010

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

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

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


Теория вероятно почти корректного обучения (теория Валианта, probably approximately correct, 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)

Определение, теоремы

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

Связь PAC-learning с классами сложности (P \neq NP), математической криптографией (односторонние функции, криптосистемы)

Ссылки

  1. Valiant L.G. A theory of the learnable // Communications of the ACM. — 1984 T. 27. — С. 1134-1142.
Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%92%D0%B0%D0%BB%D0%B8%D0%B0%D0%BD%D1%82%D0%B0»