Теория вычислительного обучения
Материал из MachineLearning.
Строка 17: | Строка 17: | ||
Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения. | Оценки обобщающей способности, как правило, основываются на гипотезе, что прошлые и будущее прецеденты поступают случайно и независимо из одного и того же неизвестного вероятностного распределения. | ||
Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки. | Эта гипотеза позволяет применить статистические методы для получения верхних оценок ожидаемой в будущем ошибки. | ||
+ | Первые оценки были получены [[Теория Вапника-Червоненкиса|Вапником и Червоненкисом]] в конце 60-х годов. | ||
Во-вторых, процесс обучения должен завершиться за приемлемое время. | Во-вторых, процесс обучения должен завершиться за приемлемое время. | ||
- | Обычно | + | Обычно исследуется вопрос, является ли время обучения модели полиномиальным или экспоненциальным по длине выборки. |
Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов. | Таким образом, проблематика вычислительного обучения тесно связана также и с вопросами вычислительной сложности алгоритмов. | ||
+ | |||
+ | Впервые оба аспекта обучаемости были связаны воедино в теории [[Теория Валианта|вероятно почти корректного обучения]] (probably approximately correct, PAC-learning), предложенной Лесли Валиантом {{S|в работе}} 1984 года. | ||
+ | {{S|В дальнейших}} исследованиях они, как правило, разделялись. | ||
=== Направления теории вычислительного обучения === | === Направления теории вычислительного обучения === | ||
Строка 49: | Строка 53: | ||
== Литература == | == Литература == | ||
#{{книга | #{{книга | ||
- | |автор = | + | |автор = Вапник В.Н., Червоненкис А.Я. |
+ | |заглавие = Теория распознавания образов | ||
+ | |год = 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: | ||
}} | }} | ||
#{{книга | #{{книга | ||
- | |автор = | + | |автор = 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 года. В дальнейших исследованиях они, как правило, разделялись.
Направления теории вычислительного обучения
- Теория Вапника-Червоненкиса (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.
- Основы байесовского вывода.
Литература
- Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. — М.: Наука, 1974.
- Valiant L.G. A theory of the learnable // Communications of the ACM. — 1984 T. 27. — С. 1134-1142.
- Goldman S.A. Computational Learning Theory // Algorithms and Theory of Computation Handbook. — CRC Press, 1999.
- MacKay D. On-line book: Information Theory, Inference, and Learning Algorithms. — 2005.