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

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

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

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

Текущая версия

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

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

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

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

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

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

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

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

Содержание

1 Вероятно почти корректное обучение
- 1.1 Основные понятия
- 1.2 Алгоритм вероятно почти корректного обучения
2 Пример: протокол обучения для булевых функций
3 Направления исследований
4 Проблемы модели вероятно почти корректного обучения
5 Ссылки
- 5.1 Материалы
6 Литература

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

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

Обучаемый (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) и параметрами алгоритма вероятно почти корректного обучения характеризуют теоремы бритвы Оккама.

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

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

Направления исследований

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

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

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

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

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

Объем тестовой выборки

Выводятся верхние оценки на объем тестовой выборки в различных моделях для различных классов алгоритмов(концепций)^[1], ^[1].

Зашумленная обучающая выборка

В реальном мире в обучающую выборку часто попадают ошибки, поэтому как расширение базовой модели вероятно почти корректного обучения появились модели с зашумленной обучающей выборкой. Вводится вероятность того, что обучающий пример ошибочен. Такие модели называются зашумленными моделями вероятно почти корректного обучения (noisy PAC model). Как подход борьбы с зашумленными данными вводится модель со статистическим оракулом^[1] (statistical oracle), в которой входные данные представляются не в виде обучающих примеров, а в виде запросов о некоторых статистических свойствах обучающей выборки. Модели с зашумленной обучающей выборкой широко исследуются^[1]^[1]^[1].

PAC свойства практических алгоритмов

Изучаются свойства в модели вероятно почти корректного обучения различных практических алгоритмов машинного обучения (например: решающие списки^[1], решающие деревья^[1], нейронные сети^[1], машины опорных векторов^[1]).

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

Основная критика модели вероятно почти корректного обучения касается того, что модель акцентирует внимание на худшем случае. В результате, оценки получаются неоправданно оторванными от реальных приложений. Первая аспект проблемы — теоретико-сложностной. То, что алгоритм работает полиномиальное время — не означает, что он будет удобен на практике. Степень полинома может оказаться слишком большой (особенно при современных значительных объемах данных). В результате то, что эффективно в теории может оказаться непрактичным. Второй аспект проблемы касается завышенности оценок на объем тестовой выборки. Причина — в модели вероятно почти корректного обучения объем тестовой выборки является нижней оценкой для всёх возможных распределений данных. На практике же, многие «экзотические» распределения не встречаются и алгоритмам обучения требуется намного меньше тестовых данных для достижения требуемого качества обучения.

Ссылки

Материалы

Литература

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»

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

@@ Строка 64: / Строка 64: @@
 '''Теорема''' Для любого k функция от t переменных, представимая в конъюктивной нормальной форме с числом слагаемых равным k, изучаема через предложенный алгоритм с числом раундов <tex>L = L(h, (2t)^{k+1})</tex>.
-== Вычислительная сложность обучения ==
+== Направления исследований ==
-Если класс концепции конечен или имеет конечную [[Размерность Вапника-Червоненкиса | размерность Вапника-Червоненкиса]], то после получения достаточного количества учебных примеров можно «предсказывать будущее», просто находя гипотезу удовлетворяющую учебным примерам ([[Бритва Оккама]]). Но какова [[вычислительная сложность]] задачи поиска гипотезы, удовлетворяющей обучающей выборке? Такая задача вполне может быть NP-полной. В частности, она напоминает вопрос выполнимости булевой функции, хотя, это и не совсем то же самое.
+=== Вычислительная сложность обучения ===
+Если класс концепций конечен или имеет конечную [[Размерность Вапника-Червоненкиса | размерность Вапника-Червоненкиса]], то после получения достаточного количества учебных примеров можно «предсказывать будущее», просто находя гипотезу удовлетворяющую учебным примерам ([[Бритва Оккама]]). Но какова [[вычислительная сложность]] задачи поиска гипотезы, удовлетворяющей обучающей выборке? Такая задача вполне может быть NP-полной. В частности, она напоминает вопрос выполнимости булевой функции, хотя, это и не совсем то же самое.
 Тут следует рассмотреть два варианта. Надлежащее обучение (proper learning) — когда гипотеза выдается в некотором фиксированном формате (например, в виде дизъюнктивной нормальной формы). В таком случае возможно доказать, что в некоторых случаях задача нахождения гипотезы, удовлетворяющей обучающей выборке, является NP-полной. При ненадлежащем обучении (improper learning) гипотеза является произовольным алгоритмом, работающим за полиномиальное время и удовлетворяющим обучающей выборке. На сегодняшний день ничего не известно о NP-полноте задачи поиска гипотезы в такой форме.
@@ Строка 72: / Строка 73: @@
 Cуществуют некоторые аналогии между [[Cryptography and Machine Learning | криптографией и вычислительным обучением]].
+=== Объем тестовой выборки ===
+Выводятся верхние оценки на объем тестовой выборки в различных моделях для различных классов алгоритмов(концепций)<ref>David Haussler Quantifying Inductive Bias: AI Learning Algorithms and Valiant's Learning Framework. Artif. Intell. 36(2): 177-221 (1988)</ref>, <ref>Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4): 929-965 (1989)</ref>.
+=== Зашумленная обучающая выборка ===
+В реальном мире в обучающую выборку часто попадают ошибки, поэтому как расширение базовой модели вероятно почти корректного обучения появились модели с зашумленной обучающей выборкой. Вводится вероятность того, что обучающий пример ошибочен. Такие модели называются зашумленными моделями вероятно почти корректного обучения (noisy PAC model). Как подход борьбы с зашумленными данными вводится модель со статистическим оракулом<ref>M. Kearns Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983 — 1006, 1998.</ref> (statistical oracle), в которой входные данные представляются не в виде обучающих примеров, а в виде запросов о некоторых статистических свойствах обучающей выборки. Модели с зашумленной обучающей выборкой широко исследуются<ref>Dana Angluin, Philip Laird Learning From Noisy Examples, Machine Learning, v.2 n.4, p.343-370, April 1988</ref><ref>J. Aslam and S. Decatur Specification and simulation of statistical query algorithms for effciency and noise tolerance. Journal of Computer and System Sciences, 56:191 — 208, 1998.</ref><ref>A. Blum, A. Kalai, and H. Wasserman Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM, 50(4):506 — 519, 2003.</ref>.
+=== PAC свойства практических алгоритмов ===
+Изучаются свойства в модели вероятно почти корректного обучения различных практических алгоритмов машинного обучения (например: [[Решающий список|решающие списки]]<ref>Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987</ref>, [[Решающее дерево|решающие деревья]]<ref>Auer, P., Holte, R. Maass, W. Theory and applications of agnostic PAC-learning with small decision trees,  in A. Prieditis S. Russell, eds, Machine Learning: Proceedings of the Twelfth International Conference — 1995</ref>, [[Нейронная сеть|нейронные сети]]<ref>David Haussler Decision Theoretic Generalizations of the PAC Model for Neural Net and Other Learning Applications Information and Computation, 100(1): 78-150 (1992)</ref>, [[Машина опорных векторов|машины опорных векторов]]<ref>Bernhard Schölkopf, Christopher J.C. Burges, and Alexander J. Smola (editors). "Advances in Kernel Methods: Support Vector Learning". MIT Press, Cambridge, MA, 1999. ISBN 0-262-19416-3</ref>).
+== Проблемы модели вероятно почти корректного обучения ==
+Основная критика модели вероятно почти корректного обучения касается того, что модель акцентирует внимание на худшем случае. В результате, оценки получаются неоправданно оторванными от реальных приложений. Первая аспект проблемы — теоретико-сложностной.  То, что алгоритм работает полиномиальное время — не означает, что он будет удобен на практике. Степень полинома может оказаться слишком большой (особенно при современных значительных объемах данных). В результате то, что эффективно в теории может оказаться непрактичным. Второй аспект проблемы касается завышенности оценок на объем тестовой выборки. Причина — в модели вероятно почти корректного обучения объем тестовой выборки является нижней оценкой для ''всёх возможных'' распределений данных. На практике же, многие «экзотические» распределения не встречаются и  алгоритмам обучения требуется ''намного'' меньше тестовых данных для достижения требуемого качества обучения.
 == Ссылки ==
+<references/>
+=== Материалы ===
+* [http://www.svms.org/pac/ Подборка материалов по PAC learning]
+* [https://csel.cs.colorado.edu/~strohman/pac.pdf T. R. Strohmann Survey on PAC (Probably Approximately Correct) Learning, 2002]
+* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.915 David Haussler Overview of the Probably Approximately Correct (PAC) Learning Framework, 1995]
+== Литература ==
 # {{книга
 |автор        = Valiant L.G.
@@ Строка 103: / Строка 120: @@
 |ссылка       = http://books.google.ru/books?id=t0DDr5Ihf28C&lpg=PP1&ots=V-QvydpvR_&dq=An%20Introduction%20to%20Computational%20%20Learning%20Theory&pg=PP1#v=onepage&q=&f=false
 }}
-[[Категория:Машинное обучение]]
 [[Категория:Теория вычислительного обучения]]