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

Обзор

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

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

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

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

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

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

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

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

См. также

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

Примечания

Литература

• Angluin D. Computational learning theory: Survey and selected bibliography // . — 1992. — С. 351–369.
• Haussler D. Probably approximately correct learning // . — American Association for Artificial Intelligence, 1990. — С. 1101–1108.
• Vapnik V., Chervonenkis A. On the uniform convergence of relative frequencies of events to their probabilities // Theory of Probability and its Applications. — 1971. — Т. 16 , вып. 2 . — С. 264–280 .
• Dhagat A., Hellerstein L. PAC learning with irrelevant attributes // . — 1994.
• E. Mark Gold. // Information and Control. — 1967. — Т. 10 , вып. 5 . — С. 447–474 . — doi : .
• Oded Goldreich, Dana Ron. .
• Kearns M., Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata // . — New York: ACM, 1989. — С. 433–444.
• Robert E. Schapire. // Machine Learning. — 1990. — Т. 5 , вып. 2 . — С. 197–227 .
• Blumer A., Ehrenfeucht A., Haussler D., Warmuth M. K. Occam's razor // Inf.Proc.Lett.. — 1987. — Т. 24 . — С. 377–380 .
• Blumer A., Ehrenfeucht A., Haussler D., Warmuth M. K. Learnability and the Vapnik-Chervonenkis dimension // Journal of the ACM. — 1989. — Т. 36 , вып. 4 . — С. 929–865 .
• Valiant L. A Theory of the Learnable // Communications of the ACM. — 1984. — Т. 27 , вып. 11 . — С. 1134–1142 .
• Michael Kearns, Ming Li. // SIAM Journal on Computing. — 1993. — Август ( т. 22 , вып. 4 ). — С. 807–837 .
• Michael Kearns. Efficient noise-tolerant learning from statistical queries // . — 1993. — С. 392–401.
• Haussler D., Kearns M., Littlestone N., Warmuth M. Equivalence of models for polynomial learnability // Proc. 1st ACM Workshop on Computational Learning Theory. — 1988. — С. 42—55.
• Pitt L., Warmuth M. K. // Journal of Computer and System Sciences. — 1990. — Т. 41 , вып. 3 . — С. 430–467 . — doi : .

Ссылки