Теория вычислительного обучения (, или просто теория обучения) — это подобласть теории искусственного интеллекта, посвящённая разработке и анализу алгоритмов машинного обучения.
Обзор Теоретические результаты в машинном обучении главным образом имеют дело с индуктивным обучением, которое называется обучением с учителем. При таком подходе алгоритму даются образцы, помеченные неким образом. Например, образцы могут быть описаниями грибов, а метка определяет, съедобен гриб или нет. Алгоритм берёт эти помеченные образцы и использует их для получения Классификатора. Классификатором является функция, которая назначает образцам метки, включая образцы, которые не были просмотрены алгоритмом ранее. Целью обучения с учителем является оптимизация некоторой меры эффективности, такой как минимизации числа ошибок, сделанных на новых образцах.
Кроме границ эффективности, теория вычислительного обучения изучает сложность по времени и реализуемость алгоритма. В теории вычислительного обучения вычисление считается реализуемым, если оно может быть осуществлено за полиномиальное время. Есть два вида временно́й сложности результатов: Положительные результаты показывают, что некоторый класс функций обучаем за полиномиальное время. Отрицательные результаты показывают, что некоторый класс функций не может быть обучен за полиномиальное время.
Отрицательные результаты часто опираются на некоторые положения, в которые верят, но они остаются недоказанными, такие как: Вычислительная сложность — P ≠ NP; Криптография — Односторонние функции существуют.
Есть несколько различных подходов к теории вычислительного обучения. Эти различия основываются на сделанных предположениях относительно принципов вывода, используемых для обобщения ограниченных данных. Эти принципы включают определение вероятности (см. Частотная вероятность, Байесовская вероятность) и различные предположения о генерации образцов. Различные подходы включают: Точное обучение, предложенное ; Вероятностно приблизительно корректное обучение (ВПК обучение), предложенное Лесли Вэлиантом; Теория Вапника — Червоненкиса, предложенная Владимиром Вапником и Алексеем Червоненкисом; Байесовский вывод; из работы Е. Марка Голда; Онлайновое машинное обучение из работы Ника Литтлстоуна.
Теория вычислительного обучения приводит к некоторым практическим алгоритмам. Например, ВПК теория породила бустинг, Теория Вапника — Червоненкиса привела к методам опорных векторов, а байесовский вывод привёл к байесовским сетям (автор — Джуда Перл).
См. также Грамматический вывод Теория информации
Размерность Вапника — Червоненкиса Отбор признаков Индуктивное умозаключение Оптимальное O-обучение Бустинг Оккамово обучение Вероятно приближённо корректное обучение
Примечания
Литература
summary
Ссылки Basics of Bayesian inference
Категория:Теоретическая информатика Категория:Машинное обучение Категория:Теория вычислительного обучения