Теория вычислительного обучения
Теория вычислительного обучения (англ. 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.