Теория Валианта
Материал из 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, если выполнено следующее: | ||
| + | |||
| + | Для любого n, | ||
| + | для любой функции <tex>f \in F_n</tex>, | ||
| + | для любого параметра ошибки 0 < ε < 1, | ||
| + | для любого параметра уверенности 0 < δ < 1, | ||
| + | для обучающей выборки <tex>{<x^i,f(x^i)>}_{i=1}^{m}</tex> (обучающие примеры — независимые одинаково распределенные случайные величины с распределением D) | ||
| + | алгоритм A выдает гипотезу h такую, что | ||
| + | |||
| + | <tex> Pr[err_{f,D}(h) < \epsilon] > 1 - \delta </tex> | ||
| + | |||
| + | где вероятность определяется распределением примеров D и случайными значениями, используемыми алгоритмом A (алгоритм может быть вероятностным). | ||
| + | |||
== Объем обучающей выборки (Sample complexity) == | == Объем обучающей выборки (Sample complexity) == | ||
Определение, теоремы | Определение, теоремы | ||
Версия 21:39, 1 января 2010
| Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Теория вероятно почти корректного обучения (теория Валианта, probably approximately correct, PAC-learning) — теория, предложенная Лесли Валиантом в 1984 году для математического анализа машинного обучения. Работа Валианта акцентирует внимание на том, что проблематика вычислительного обучения тесно связана также и с вопросам вычислительной сложности алгоритмов.
В теории вероятно почти корректного обучения обучаемый (learner) получает некоторый набор примеров и должен выбрать некоторую функцию (гипотезу) из определенного класса функций. Цель обучаемого состоит в том, чтобы с высокой вероятностью выбранная функция была, в некотором смысле, «похожа» на истинную гипотезу. Обучаемый должен быть эффективным (то есть использовать в процессе работы приемлемое количество вычислительных ресурсов).
Содержание |
Вероятно почти корректное обучение
Основные понятия
- Обучаемый (learner) — объект, участвующий в процессе обучения. В данном контексте обучаемый — алгоритм.
- Объекты на которых выполняется обучение назовём примерами. Поскольку нам будет важна вычислительная сложность, будем считать, что примеры задаются некоторым описанием — булевым вектором.
-
— множество примеров с описанием длины n.
-
— пространство примеров (instance space), множество всех возможных примеров.
-
— (неизвестное) вероятностное распределение на пространстве примеров. x ~ D — означает, что x - случайная величина с распределением D.
- Каждый пример имеет одну пометку, для простоты будем считать, что множество пометок состоит из двух элементов: {0,1}. Концепция(concept) — это функция, отображающая примеры на пометки.
— семейство концепций, подмножество множества всех булевых функций, определенных на множестве X.
-
— целевая концепция: то, что мы ищем в процессе обучения.
- Гипотеза h — некоторая булева функция на множестве
- Ошибка гипотезы.
— вероятность того, что гипотеза h не совпадает с целевой концепцией f на случайном значении x ~ D:
.
* Алгоритм вероятно почти корректного обучения
Алгоритм A называется алгоритмом вероятно почти корректного обучения для семейства концепций F, если выполнено следующее:
Для любого n,
для любой функции ,
для любого параметра ошибки 0 < ε < 1,
для любого параметра уверенности 0 < δ < 1,
для обучающей выборки
(обучающие примеры — независимые одинаково распределенные случайные величины с распределением D)
алгоритм A выдает гипотезу h такую, что
где вероятность определяется распределением примеров D и случайными значениями, используемыми алгоритмом A (алгоритм может быть вероятностным).
Объем обучающей выборки (Sample complexity)
Определение, теоремы
Вычислительная сложность обучения
Связь PAC-learning с классами сложности (), математической криптографией (односторонние функции, криптосистемы)
Ссылки
- Valiant L.G. A theory of the learnable // Communications of the ACM. — 1984 T. 27. — С. 1134-1142.
