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

Обзор

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

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

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

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

  • Вычислительная сложность – P ≠ NP;
  • КриптографияОдносторонние функции существуют.

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

  • Точное обучение, предложенное Даной Англуин;
  • Вероятностно приблизительно корректное обучение (ВПК обучение), предложенное Лесли Вэлиантом;
  • Теория Вапника — Червоненкиса, предложенная Владимиром Вапником и Алексеем Червоненкисом;
  • Байесовский вывод;
  • Алгоритмическая теория обучения [en] из работы Е. Марка Голда;
  • Онлайновое обучение машин из работы Ника Литтлстоуна.

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

Обзоры

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

  • 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.

Индуктивное умозаключение

    Оптимальное 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.

          Эта статья использует материал из статьи Wikipedia Теория вычислительного обучения, которая выпущена под Creative Commons Attribution-Share-Alike License 3.0.