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

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

Версия от 21:39, 1 января 2010; DmitryKonstantinov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

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

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

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

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

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

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

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

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

Содержание

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

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

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

Обучаемый (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$ , для любого параметра ошибки 0 < ε < 1, для любого параметра уверенности 0 < δ < 1, для обучающей выборки ${<x^i,f(x^i)>}_{i=1}^{m}$ (обучающие примеры — независимые одинаково распределенные случайные величины с распределением D) алгоритм A выдает гипотезу h такую, что