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

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

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

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

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

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

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

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

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

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

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

• Angluin D. Computational learning theory: Survey and selected bibliography // Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (May 1992. — 1992. — С. 351–369.
• Haussler D. Probably approximately correct learning // AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA. — 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 // Proceedings of the IEEE Symp. on Foundation of Computer Science. — 1994.
• E. Mark Gold. Language identification in the limit // Information and Control. — 1967. — Т. 10, вып. 5. — С. 447–474. — doi:10.1016/S0019-9958(67)91165-5.
• Oded Goldreich, Dana Ron. On universal learning algorithms. summary
• Kearns M., Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata // Proceedings of the 21st Annual ACM Symposium on Theory of Computing. — New York: ACM, 1989. — С. 433–444.
• Robert E. Schapire. The strength of weak learnability // 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. Learning in the presence of malicious errors // SIAM Journal on Computing. — 1993. — Август (т. 22, вып. 4). — С. 807–837.
• Michael Kearns. Efficient noise-tolerant learning from statistical queries // Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. — 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. Prediction-Preserving Reducibility // Journal of Computer and System Sciences. — 1990. — Т. 41, вып. 3. — С. 430–467. — doi:10.1016/0022-0000(90)90028-J.

• Basics of Bayesian inference