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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 17: Строка 17:
Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения.
Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения.
Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки.
Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки.
 +
Первые оценки были получены [[Теория Вапника-Червоненкиса|Вапником и Червоненкисом]] в конце 60-х годов.
Во-вторых, процесс обучения должен завершиться за приемлемое время.
Во-вторых, процесс обучения должен завершиться за приемлемое время.
-
Обычно исследуются вопрос, является ли время обучения модели полиномиальным или экспоненциальным по длине выборки.
+
Обычно исследуется вопрос, является ли время обучения модели полиномиальным или экспоненциальным по длине выборки.
Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов.
Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов.
 +
 +
Впервые оба аспекта обучаемости были связаны воедино в теории [[Теория Валианта|вероятно почти корректного обучения]] (probably approximately correct, PAC-learning), предложенной Лесли Валиантом {{S|в работе}} 1984 года.
 +
{{S|В дальнейших}} исследованиях они, как правило, разделялись.
=== Направления теории вычислительного обучения ===
=== Направления теории вычислительного обучения ===
Строка 49: Строка 53:
== Литература ==
== Литература ==
#{{книга
#{{книга
-
|автор = Sally A. Goldman
+
|автор = Вапник В.Н., Червоненкис А.Я.
 +
|заглавие = Теория распознавания образов
 +
|год = 1974
 +
|место = М.
 +
|издательство = Наука
 +
}}
 +
#{{книга
 +
|автор = Valiant L.G.
 +
|часть = A theory of the learnable
 +
|заглавие = Communications of the ACM
 +
|год = 1984
 +
|том = 27
 +
|страницы = 1134-1142
 +
|ссылка = http://web.mit.edu/6.435/www/Valiant84.pdf
 +
}}
 +
#{{книга
 +
|автор = Goldman S.A.
|часть = Computational Learning Theory
|часть = Computational Learning Theory
|заглавие = Algorithms and Theory of Computation Handbook
|заглавие = Algorithms and Theory of Computation Handbook
Строка 57: Строка 77:
}}
}}
#{{книга
#{{книга
-
|автор = David MacKay
+
|автор = MacKay D.
|заглавие = On-line book: Information Theory, Inference, and Learning Algorithms
|заглавие = On-line book: Information Theory, Inference, and Learning Algorithms
|год = 2005
|год = 2005

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

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

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

Содержание

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

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

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

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

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

Впервые оба аспекта обучаемости были связаны воедино в теории вероятно почти корректного обучения (probably approximately correct, PAC-learning), предложенной Лесли Валиантом в работе 1984 года. В дальнейших исследованиях они, как правило, разделялись.

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

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

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

Ссылки


Литература

  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.



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