Теория вычислительного обучения
Материал из 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 | ||
| + | }} | ||
| - | |||
| - | |||
Версия 23:52, 29 марта 2008
Теория вычислительного обучения (Computational Learning Theory, COLT) изучает методы построения и анализа алгоритмов, обучаемых по прецедентам. Она сосредоточена на получении строгих математических результатов. Основные направления исследований — проблема переобучения и вычислительная сложность алгоритмов.
Основная международная конференция — COLT. Проводятся также европейские конференции EuroCOLT и 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)
Ссылки
- hunch.net — хорошо структурированный блог Джона Лангфорда (John Langford).
- COLT — сайт конференций COLT.
- Основы байесовского вывода.
Литература
- Sally A. Goldman Computational Learning Theory // Algorithms and Theory of Computation Handbook. — CRC Press, 1999.
- David MacKay On-line book: Information Theory, Inference, and Learning Algorithms. — 2005.
