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

Материал из MachineLearning.

Версия 00:27, 30 марта 2008

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

Литература

1. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. — М.: Наука, 1974.
2. Valiant L.G. A theory of the learnable // Communications of the ACM. — 1984 T. 27. — С. 1134-1142.
3. Goldman S.A. Computational Learning Theory // Algorithms and Theory of Computation Handbook. — CRC Press, 1999.
4. MacKay D. On-line book: Information Theory, Inference, and Learning Algorithms. — 2005.