Теория вычислительного обучения

Теория вычислительного обучения (англ. computational learning theory, или просто теория обучения) — это подобласть теории искусственного интеллекта, посвящённая разработке и анализу алгоритмов машинного обучения^[1].

Обзор

Теоретические результаты в машинном обучении главным образом имеют дело с индуктивным обучением, которое называется обучением с учителем. При таком подходе алгоритму даются образцы, помеченные неким образом. Например, образцы могут быть описаниями грибов, а метка определяет, съедобен гриб или нет. Алгоритм берёт эти помеченные образцы и использует их для получения Классификатора. Классификатором является функция, которая назначает образцам метки, включая образцы, которые не были просмотрены алгоритмом ранее. Целью обучения с учителем является оптимизация некоторой меры эффективности, такой как минимизации числа ошибок, сделанных на новых образцах.

Кроме границ эффективности, теория вычислительного обучения изучает сложность по времени и реализуемость алгоритма. В теории вычислительного обучения вычисление считается реализуемым, если оно может быть осуществлено за полиномиальное время. Есть два вида временно́й сложности результатов:

• Положительные результаты показывают, что некоторый класс функций обучаем за полиномиальное время.
• Отрицательные результаты показывают, что некоторый класс функций не может быть обучен за полиномиальное время.

Отрицательные результаты часто опираются на некоторые положения, в которые верят, но они остаются недоказанными, такие как:

• Вычислительная сложность — P ≠ NP;
• Криптография — Односторонние функции существуют.

Есть несколько различных подходов к теории вычислительного обучения. Эти различия основываются на сделанных предположениях относительно принципов вывода, используемых для обобщения ограниченных данных. Эти принципы включают определение вероятности (см. Частотная вероятность, Байесовская вероятность) и различные предположения о генерации образцов. Различные подходы включают:

• Точное обучение, предложенное Даной Англуин^[англ.];
• Вероятностно приблизительно корректное обучение (ВПК обучение), предложенное Лесли Вэлиантом;
• Теория Вапника — Червоненкиса, предложенная Владимиром Вапником и Алексеем Червоненкисом;
• Байесовский вывод;
• Алгоритмическая теория обучения^[англ.] из работы Е. Марка Голда;
• Онлайновое машинное обучение из работы Ника Литтлстоуна.

Теория вычислительного обучения приводит к некоторым практическим алгоритмам. Например, ВПК теория породила бустинг, Теория Вапника — Червоненкиса привела к методам опорных векторов, а байесовский вывод привёл к байесовским сетям (автор — Джуда Перл).

См. также

• Грамматический вывод
• Теория информации
• Стабильность (теория обучения)^[англ.]
• Отказоустойчивость (ВПК-обучение)^[англ.]
• Размерность Вапника — Червоненкиса
• Отбор признаков
• Индуктивное умозаключение
• Оптимальное O-обучение
• Бустинг
• Оккамово обучение
• Вероятно приближённо корректное обучение
• Теория распределённого обучения^[англ.]