Теория вычислительного обучения
Материал из MachineLearning.
Теория вычислительного обучения (Computational Learning Theory, COLT) изучает методы построения и анализа алгоритмов, обучаемых по прецедентам. Она сосредоточена на получении строгих математических результатов. Основные направления исследований — проблема переобучения и вычислительная сложность алгоритмов.
Основная международная конференция — COLT. Проводятся также европейские конференции EuroCOLT и ALT.
Содержание |
Задачи и направления
Теория COLT претендует на роль теоретического базиса всего машинного обучения. Основная задача теории вычислительного обучения — дать строгие обоснования алгоритмов обучения по прецедентам.
Алгоритм обучения принимает на входе конечную обучающую выборку прецедентов и настраивает модель. Настроенная (обученная) модель затем используется для предсказания будущих прецедентов. Алгоритм должен обладать свойством обучаемости в следующих двух смыслах.
Во-первых, алгоритм обучения должен обладать способностью к обобщению данных. Построенная им модель должна выдавать в среднем достаточно точные предсказания будущих прецедентов. Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения. Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки.
Во-вторых, процесс обучения должен завершиться за приемлемое время. Обычно исследуются вопрос, является ли время обучения модели полиномиальным или экспоненциальным по длине выборки. Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов.
Направления теории вычислительного обучения
- Теория Вапника-Червоненкиса (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.
- Основы байесовского вывода.
Литература
- Sally A. Goldman Computational Learning Theory // Algorithms and Theory of Computation Handbook. — CRC Press, 1999.
- David MacKay On-line book: Information Theory, Inference, and Learning Algorithms. — 2005.
