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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Теория вычислительного обучения (англ. computational learning theory, или просто теория обучения), это подобласть теории искусственного интеллекта, посвящённая разработке и анализу алгоритмов обучения машин.[1]

Обзор[править | править код]

Теоретические результаты в обучении машин главным образом имеют дело с индуктивным обучением, которое называется обучением с учителем. При обучении с учителем алгоритму даются образцы, помеченные неким образом. Например, образцы могут быть описаниями грибов, а метка определяет, съедобен гриб или нет. Алгоритм берёт эти помеченные образцы и использует их для получения классификатора. Классификатором является функция, которая назначает образцам метки, включая образцы, которые не были просмотрены алгоритмом ранее. Целью обучения с учителем является оптимизация некоторой меры эффективности, такой как минимизации числа ошибок, сделанных на новых образцах.

Кроме границ эффективности, теория вычислительного обучения изучает сложность по времени и реализуемость алгоритма. В теории вычислительного обучения вычисление считается реализуемым, если оно может быть осуществлено за полиномиальное время. Есть два вида временно́й сложности результатов:

  • Положительные результаты показывают, что некоторый класс функций обучаем за полиномиальное время.
  • Отрицательные результаты показывают, что некоторый класс функций не может быть обучен за полиномиальное время.

Отрицательные результаты часть опираются на некоторые положения, в которые верят, но они остаются недоказанными, такие как:

Есть несколько различных подходов к теории вычислительного обучения. Эти различия основываются на сделанных предположениях относительно принципов вывода, используемых для обобщения ограниченных данных. Эти принципы включают определение вероятности (см. Частотная вероятность, Байесовская вероятность) и различные предположения о генерации образцов. Различные подходы включают

Теория вычислительного обучения приводит к некоторым практическим алгоритмам. Например, ВПК теория породила бустинг, Теория Вапника — Червоненкиса привела к методам опорных векторов, а байесовский вывод привёл к байесовским сетям (автор — Джуда Перл).

См. также[править | править код]

References[править | править код]

Обзоры[править | править код]

Размерность Вапника — Червоненкиса[править | править код]

  • Vapnik V., Chervonenkis A. On the uniform convergence of relative frequencies of events to their probabilities // Theory of Probability and its Applications. — 1971. — Т. 16, вып. 2. — С. 264–280.

Отбор признаков[править | править код]

  • Dhagat A., Hellerstein L. PAC learning with irrelevant attributes // Proceedings of the IEEE Symp. on Foundation of Computer Science. — 1994.

Индуктивное умозаключение[править | править код]

  • E. Mark Gold. Language identification in the limit // Information and Control. — 1967. — Т. 10, вып. 5. — С. 447–474. — DOI:10.1016/S0019-9958(67)91165-5.

Оптимальное O-обучение[править | править код]

Отрицательные результаты[править | править код]

Бустинг (обучение машин)[править | править код]

Оккамово обучение[править | править код]

  • Blumer A., Ehrenfeucht A., Haussler D., Warmuth M. K. Occam's razor // Inf.Proc.Lett.. — 1987. — Т. 24. — С. 377–380.
  • Blumer A., Ehrenfeucht A., Haussler D., Warmuth M. K. Learnability and the Vapnik-Chervonenkis dimension // Journal of the ACM. — 1989. — Т. 36, вып. 4. — С. 929–865.

Вероятностно приблизительно корректное обучение[править | править код]

  • Valiant L. A Theory of the Learnable // Communications of the ACM. — 1984. — Т. 27, вып. 11. — С. 1134–1142.

Устойчивость к ошибкам[править | править код]

Эквивалентность[править | править код]

  • Haussler D., Kearns M., Littlestone N., Warmuth M. Equivalence of models for polynomial learnability // Proc. 1st ACM Workshop on Computational Learning Theory. — 1988. — С. 42-55.
  • Pitt L., Warmuth M. K. Prediction-Preserving Reducibility // Journal of Computer and System Sciences. — 1990. — Т. 41, вып. 3. — С. 430–467. — DOI:10.1016/0022-0000(90)90028-J.

Теория распределённого обучения[en][править | править код]

Ссылки[править | править код]