Теория Валианта
Материал из MachineLearning.
м (→Ссылки: литература) |
(дополнение) |
||
Строка 1: | Строка 1: | ||
{{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}} | {{Задание|DmitryKonstantinov|Константин Воронцов|8 января 2010}} | ||
+ | |||
+ | '''Теория вероятно почти корректного обучения''' (теория Валианта, probably approximately correct, PAC-learning) — теория, предложенная Лесли Валиантом в 1984 году для математического анализа машинного обучения. Работа Валианта акцентирует внимание на том, что проблематика вычислительного обучения тесно связана также и с вопросам[[вычислительная сложность | вычислительной сложности алгоритмов]]. | ||
+ | |||
+ | В теории вероятно почти корректного обучения обучаемый (learner) получает некоторый набор примеров и должен выбрать некоторую функцию (гипотезу) из определенного класса функций. Цель обучаемого состоит в том, чтобы с высокой вероятностью выбранная функция была, в некотором смысле, «похожа» на истинную гипотезу. Обучаемый должен быть '''эффективным''' (то есть использовать в процессе работы приемлемое количество вычислительных ресурсов). | ||
+ | |||
== Вероятно почти корректное обучение == | == Вероятно почти корректное обучение == | ||
+ | ===Основные понятия === | ||
+ | * Обучаемый (learner) | ||
+ | * Пример, пространство примеров (instance space) | ||
+ | * Распределение примеров | ||
+ | * Концепция(concept) | ||
+ | * Класс концепций | ||
+ | * Гипотеза | ||
+ | * Ошибка гипотезы | ||
+ | * Алгоритм вероятно почти корректного обучения | ||
+ | |||
+ | === Пример === | ||
== Объем обучающей выборки (Sample complexity) == | == Объем обучающей выборки (Sample complexity) == | ||
+ | Определение, теоремы | ||
== Вычислительная сложность обучения == | == Вычислительная сложность обучения == | ||
+ | Связь PAC-learning с классами сложности (<tex>P \neq NP</tex>), математической криптографией (односторонние функции, криптосистемы) | ||
== Ссылки == | == Ссылки == | ||
- | #{{книга | + | # {{книга |
|автор = Valiant L.G. | |автор = Valiant L.G. | ||
|часть = A theory of the learnable | |часть = A theory of the learnable |
Версия 17:39, 1 января 2010
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}. См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе. |
Теория вероятно почти корректного обучения (теория Валианта, probably approximately correct, PAC-learning) — теория, предложенная Лесли Валиантом в 1984 году для математического анализа машинного обучения. Работа Валианта акцентирует внимание на том, что проблематика вычислительного обучения тесно связана также и с вопросам вычислительной сложности алгоритмов.
В теории вероятно почти корректного обучения обучаемый (learner) получает некоторый набор примеров и должен выбрать некоторую функцию (гипотезу) из определенного класса функций. Цель обучаемого состоит в том, чтобы с высокой вероятностью выбранная функция была, в некотором смысле, «похожа» на истинную гипотезу. Обучаемый должен быть эффективным (то есть использовать в процессе работы приемлемое количество вычислительных ресурсов).
Содержание |
Вероятно почти корректное обучение
Основные понятия
- Обучаемый (learner)
- Пример, пространство примеров (instance space)
- Распределение примеров
- Концепция(concept)
- Класс концепций
- Гипотеза
- Ошибка гипотезы
- Алгоритм вероятно почти корректного обучения
Пример
Объем обучающей выборки (Sample complexity)
Определение, теоремы
Вычислительная сложность обучения
Связь PAC-learning с классами сложности (), математической криптографией (односторонние функции, криптосистемы)
Ссылки
- Valiant L.G. A theory of the learnable // Communications of the ACM. — 1984 T. 27. — С. 1134-1142.