Теория Валианта
Материал из MachineLearning.
![]() | Данная статья является непроверенным учебным заданием.
До указанного срока статья не должна редактироваться другими участниками проекта 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.