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

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

(Различия между версиями)

Перейти к: навигация, поиск

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

Данная статья является непроверенным учебным заданием.

Студент: Участник:DmitryKonstantinov

Преподаватель: Участник:Константин Воронцов

Срок: 8 января 2010

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

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

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

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

Содержание

1 Вероятно почти корректное обучение
- 1.1 Основные понятия
- 1.2 Алгоритм вероятно почти корректного обучения
2 Объем обучающей выборки (Sample complexity)
3 Пример: протокол обучения для булевых функций
4 Вычислительная сложность обучения
5 Ссылки

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

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

Обучаемый (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).

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

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

Объем обучающей выборки (Sample complexity)

Определение

Связь с параметрами обучения для конечных классов концепций.

Связь с параметрами обучения для беcконечных классов концепций с конечной размерностью Вапника-Червонескиса.

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

Мы хотим изучить некоторую (неизвестную) булеву функцию. Для решения задачи в общем виде требуется протестировать $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 такова, что:

всегда, если g(v) = 1, то $F_t(v) = 1$ ;
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 (конъюнкт  не равен 1 на v) then удалить конъюнкт  из 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})$ .

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

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

Ссылки

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.

Источник — «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»

Категория: Непроверенные учебные задания

@@ Строка 39: / Строка 39: @@
 # Сколько примеров требуется для обучения.
 == Объем обучающей выборки (Sample complexity) ==
-Определение, теоремы
+Определение
+Связь с параметрами обучения для конечных классов концепций.
+Связь с параметрами обучения для беcконечных классов концепций с конечной [[Размерность Вапника-Червоненкиса | размерностью Вапника-Червонескиса]].
+==Пример: протокол обучения для булевых функций==
+Мы хотим изучить некоторую (неизвестную) булеву функцию. Для решения задачи в общем виде требуется протестировать <tex>2^n</tex> наборов для n-арной функции. Ограничим класс возможных функций до класса функций, представимых в конъюктивной нормальной форме с ограниченным числом слагаемых в каждом конъюнкте и попробуем добиться приемлемой сложности обучения.
+Пусть имеется t булевых переменных: <tex>p_1 \dots p_t</tex>. Значения переменных будем задавать вектором вида <tex>\{0,1,*\}^t</tex>, где <tex>*</tex> - означает неопределенное значение. Вектор назовем полным, если в нем отсутствуют неопределенные значения. Булева функция F_t отображает двоичные вектора длины t на множество {0,1}. Расширим определение функции на неполные вектора, будем считать, что <tex>F_t(v) = 1</tex> тогда и только когда F(u) = 1  для всех векторов u, полученных дополнением вектора v до полного. Пусть EXAMPLE() выдает наборы, на которых функция <tex>F_t</tex> равна 1. Например, для функции <tex>F_3(p) = p_1p_2+p_3</tex>: EXAMPLE() → (*, *, 1); EXAMPLE() → (1, 1, 0).
+Будем считать, что функция изучаема, если существует алгоритм, который работает за полиномиальное от t и h время с параметром уверенности δ > 1 - 1/h и параметром ошибки следующего вида. Выдаваемая функция g такова, что:
+# всегда, если g(v) = 1, то <tex>F_t(v) = 1</tex>;
+# cумма вероятностей D[v] по всем v таким, что <tex>F_t(v) = 1</tex>, но <tex>g(v) \neq 1</tex>, не превосходит 1/h.
+Для функций, представимых в конъюктивной нормальной форме с числом слагаемых равным k можно предложить следующий тривиальный алгоритм нахождения целевой функции.
+'''Алгоритм:'''
+<code>
+ g = произведение всех возможных конъюнктов длины k; //инициализация
+ for(i = 0; i < L; i++) // L — число раудов
+   v = EXAMPLE();
+   for (j = 0; j < m; j++) // m —- число конъюнктов в g
+   if (конъюнкт <tex>c_j</tex> не равен 1 на v) then удалить конъюнкт <tex>c_j</tex> из g;
+ return g;
+</code>
+<tex>L(h,s)</tex> — минимальное целое число такое, что вероятность события: среди <tex>L(h,s)</tex> независимых испытаний по Бернулли с вероятностью успеха h будет меньше чем s успешных, меньше чем 1/h. Верхняя оценка: <tex>L(h,s) \leq 2h(s + \ln h)</tex>
+'''Теорема''' Для любого k функция от t переменных, представимая в конъюктивной нормальной форме с числом слагаемых равным k, изучаема через предложенный алгоритм с числом раудов <tex>L = L(h, (2t)^{k+1})</tex>.
 == Вычислительная сложность обучения ==
 Связь PAC-learning с классами сложности (<tex>P \neq NP</tex>), математической криптографией (односторонние функции, криптосистемы)

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

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

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

Содержание

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

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

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

Объем обучающей выборки (Sample complexity)

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

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

Ссылки

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты