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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Литература: дополнение)
 
(3 промежуточные версии не показаны)
Строка 17: Строка 17:
Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения.
Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения.
Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки.
Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки.
 +
Первые оценки были получены [[Теория Вапника-Червоненкиса|Вапником и Червоненкисом]] в конце 60-х годов.
Во-вторых, процесс обучения должен завершиться за приемлемое время.
Во-вторых, процесс обучения должен завершиться за приемлемое время.
-
Обычно исследуются вопрос, является ли время обучения модели полиномиальным или экспоненциальным по длине выборки.
+
Обычно исследуется вопрос, является ли время обучения модели полиномиальным или экспоненциальным по длине выборки.
Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов.
Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов.
 +
 +
Впервые оба аспекта обучаемости были связаны воедино в теории [[Теория Валианта|вероятно почти корректного обучения]] (probably approximately correct, PAC-learning), предложенной Лесли Валиантом {{S|в работе}} 1984 года.
 +
{{S|В дальнейших}} исследованиях они, как правило, разделялись.
=== Направления теории вычислительного обучения ===
=== Направления теории вычислительного обучения ===
Строка 32: Строка 36:
* [[Байесовский вывод]] (bayesian inference)
* [[Байесовский вывод]] (bayesian inference)
-
=== Связные области ===
+
=== Смежные области ===
-
''Теория вычислительного обучения'' черпает вдохновение во многих разделах современной математики.
+
''Теория вычислительного обучения'' черпает идеи во многих разделах современной математики.
* [[Теория игр]] (game theory)
* [[Теория игр]] (game theory)
* [[Теория аппроксимации]] (approximation theory)
* [[Теория аппроксимации]] (approximation theory)
Строка 44: Строка 48:
* [http://hunch.net hunch.net] — хорошо структурированный блог Джона Лангфорда (John Langford).
* [http://hunch.net hunch.net] — хорошо структурированный блог Джона Лангфорда (John Langford).
* [http://www.learningtheory.org COLT] — сайт конференций COLT.
* [http://www.learningtheory.org COLT] — сайт конференций COLT.
 +
* [http://www.gaussianprocess.org Гауссовские процессы].
* [http://research.microsoft.com/adapt/MSBNx/msbnx/Basics_of_Bayesian_Inference.htm Основы байесовского вывода].
* [http://research.microsoft.com/adapt/MSBNx/msbnx/Basics_of_Bayesian_Inference.htm Основы байесовского вывода].
-
 
== Литература ==
== Литература ==
#{{книга
#{{книга
-
|автор = 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
 +
}}
 +
#{{книга
 +
|автор = Rasmussen C.E., Williams C.K.I.
 +
|заглавие = Gaussian Processes for Machine Learning
 +
|год = 2006
 +
|издательство = MIT Press
 +
|ссылка = http://www.gaussianprocess.org/gpml/chapters/
 +
|isbn = 0-262-18253-X
 +
}}
 +
#{{книга
 +
|автор = Goldman S.A.
|часть = Computational Learning Theory
|часть = Computational Learning Theory
|заглавие = Algorithms and Theory of Computation Handbook
|заглавие = Algorithms and Theory of Computation Handbook
Строка 57: Строка 85:
}}
}}
#{{книга
#{{книга
-
|автор = David MacKay
+
|автор = MacKay D.
|заглавие = On-line book: Information Theory, Inference, and Learning Algorithms
|заглавие = On-line book: Information Theory, Inference, and Learning Algorithms
|год = 2005
|год = 2005

Текущая версия

Теория вычислительного обучения (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. Rasmussen C.E., Williams C.K.I. Gaussian Processes for Machine Learning. — MIT Press, 2006. — ISBN 0-262-18253-X
  4. Goldman S.A. Computational Learning Theory // Algorithms and Theory of Computation Handbook. — CRC Press, 1999.
  5. MacKay D. On-line book: Information Theory, Inference, and Learning Algorithms. — 2005.



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