Теория вычислительного обучения
Материал из MachineLearning.
Теория вычислительного обучения (Computational Learning Theory, COLT) изучает методы построения и анализа алгоритмов, обучаемых по прецедентам. Она сосредоточена на получении строгих математических результатов. Основные направления исследований — проблема переобучения и вычислительная сложность алгоритмов.
Основная международная конференция — COLT. Проводятся также европейские конференции EuroCOLT и ALT.
Содержание |
Задачи и направления
Теория COLT претендует на роль теоретического базиса всего машинного обучения. Основная задача теории вычислительного обучения — дать строгие обоснования алгоритмов обучения по прецедентам.
Алгоритм обучения принимает на входе конечную обучающую выборку прецедентов и настраивает модель. Настроенная (обученная) модель затем используется для предсказания будущих прецедентов. Алгоритм должен обладать свойством обучаемости в следующих двух смыслах.
Во-первых, алгоритм обучения должен обладать способностью к обобщению данных. Построенная им модель должна выдавать в среднем достаточно точные предсказания будущих прецедентов. Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения. Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки. Первые оценки были получены Вапником и Червоненкисом в конце 60-х годов.
Во-вторых, процесс обучения должен завершиться за приемлемое время. Обычно исследуется вопрос, является ли время обучения модели полиномиальным или экспоненциальным по длине выборки. Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов.
Впервые оба аспекта обучаемости были связаны воедино в теории вероятно почти корректного обучения (probably approximately correct, PAC-learning), предложенной Лесли Валиантом в работе 1984 года. В дальнейших исследованиях они, как правило, разделялись.
Направления теории вычислительного обучения
- Теория Вапника-Червоненкиса (VC theory)
- Теория Валианта (probably approximately correct learning, PAC theory)
- Теория PAC-Bayes (PAC-Bayesian theory)
- Оценки обобщающей способности для различных алгоритмов обучения (generalization bounds)
- Теория эмпирических процессов (empirical processes)
- Теория концентрации вероятностной меры (concentration inequalities)
- Сложность данных (sample complexity)
- Байесовский вывод (bayesian inference)
Смежные области
Теория вычислительного обучения черпает идеи во многих разделах современной математики.
- Теория игр (game theory)
- Теория аппроксимации (approximation theory)
- Вычислительная сложность (computational complexity)
- Теория информации (information theory)
- Криптография (cryptography)
Ссылки
- hunch.net — хорошо структурированный блог Джона Лангфорда (John Langford).
- COLT — сайт конференций COLT.
- Гауссовские процессы.
- Основы байесовского вывода.
Литература
- Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. — М.: Наука, 1974.
- Valiant L.G. A theory of the learnable // Communications of the ACM. — 1984 T. 27. — С. 1134-1142.
- Rasmussen C.E., Williams C.K.I. Gaussian Processes for Machine Learning. — MIT Press, 2006. — ISBN 0-262-18253-X
- Goldman S.A. Computational Learning Theory // Algorithms and Theory of Computation Handbook. — CRC Press, 1999.
- MacKay D. On-line book: Information Theory, Inference, and Learning Algorithms. — 2005.
