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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: '''Теория вычислительного обучения''' (Computational Learning Theory, COLT) изучает методы построения и анализа алгорит...)
Строка 1: Строка 1:
-
'''Теория вычислительного обучения''' (Computational Learning Theory, COLT) изучает методы построения и анализа алгоритмов, обучаемых по прецедентам. Она сосредоточена на получении строгих математических результатов. Основные направления исследований — [[вычислительная сложность]] алгоритмов и [[переобучение|проблема переобучения]].
+
'''Теория вычислительного обучения''' (Computational Learning Theory, COLT) изучает методы построения и анализа алгоритмов, обучаемых по прецедентам. Она сосредоточена на получении строгих математических результатов. Основные направления исследований — [[переобучение|проблема переобучения]] и [[вычислительная сложность]] алгоритмов.
Основная международная конференция — [[Computational Learning Theory (конференция)|COLT]].
Основная международная конференция — [[Computational Learning Theory (конференция)|COLT]].
Проводятся также европейские конференции [[European Conference on Computational Learning Theory (конференция)|EuroCOLT]] и [[Algorithmic Learning Theory (конференция)|ALT]].
Проводятся также европейские конференции [[European Conference on Computational Learning Theory (конференция)|EuroCOLT]] и [[Algorithmic Learning Theory (конференция)|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)
 +
 
 +
== Ссылки ==
 +
 
 +
* [http://hunch.net hunch.net] — хорошо структурированный блог Джона Лангфорда (John Langford).
 +
* [http://www.learningtheory.org COLT] — сайт конференций COLT.
 +
* [http://research.microsoft.com/adapt/MSBNx/msbnx/Basics_of_Bayesian_Inference.htm Основы байесовского вывода].
 +
 
 +
 
 +
== Литература ==
 +
#{{книга
 +
|автор = Sally A. Goldman
 +
|часть = Computational Learning Theory
 +
|заглавие = Algorithms and Theory of Computation Handbook
 +
|год = 1999
 +
|издательство = CRC Press
 +
|ссылка = http://citeseer.ist.psu.edu/275016.html
 +
}}
 +
#{{книга
 +
|автор = David MacKay
 +
|заглавие = On-line book: Information Theory, Inference, and Learning Algorithms
 +
|год = 2005
 +
|ссылка = http://www.inference.phy.cam.ac.uk/mackay/itila
 +
}}
-
=== Теория Валианта ===
 
-
=== Теория PAC-Bayes ===
 

Версия 23:52, 29 марта 2008

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



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