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

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

Перейти к: навигация, поиск

Теория вычислительного обучения (Computational Learning Theory, COLT) изучает методы построения и анализа алгоритмов, обучаемых по прецедентам. Она сосредоточена на получении строгих математических результатов. Основные направления исследований — проблема переобучения и вычислительная сложность алгоритмов.

Основная международная конференция — COLT. Проводятся также европейские конференции EuroCOLT и ALT.

Содержание

Задачи и направления

Теория COLT претендует на роль теоретического базиса всего машинного обучения. Основная задача теории вычислительного обучения — дать строгие обоснования алгоритмов обучения по прецедентам.

Алгоритм обучения принимает на входе конечную обучающую выборку прецедентов и настраивает модель. Настроенная (обученная) модель затем используется для предсказания будущих прецедентов. Алгоритм должен обладать свойством обучаемости в следующих двух смыслах.

Во-первых, алгоритм обучения должен обладать способностью к обобщению данных. Построенная им модель должна выдавать в среднем достаточно точные предсказания будущих прецедентов. Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения. Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки.

Во-вторых, процесс обучения должен завершиться за приемлемое время. Обычно исследуются вопрос, является ли время обучения модели полиномиальным или экспоненциальным по длине выборки. Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов.

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

Связные области

Теория вычислительного обучения черпает вдохновение во многих разделах современной математики.

Ссылки


Литература

  1. Sally A. Goldman Computational Learning Theory // Algorithms and Theory of Computation Handbook. — CRC Press, 1999.
  2. David MacKay On-line book: Information Theory, Inference, and Learning Algorithms. — 2005.



Личные инструменты