Теория Валианта
Материал из 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.
