Оккамово обучение в теории вычислительного обучения является моделью алгоритмического обучения [en] , где целью обучения является получение сжатого представления имеющихся тренировочных данных. Метод тесно связан с почти корректным обучением [en] (ПК обучение, англ. Probably Approximately Correct learning, PAC learning), где учитель оценивает прогнозирующую способность тестового набора.

Оккамова обучаемость влечёт ПК обучение и для широкого класса понятий обратное тоже верно — ПК обучаемость влечёт оккамову обучаемость.

Введение

Оккамово обучение названо по термину «бритва Оккама», который является принципом, утверждающим, что при предположении отсутствия дополнительных сущностей короткому объяснению наблюдений следует давать предпочтение по сравнению с более длинным объяснением (кратко: «Не следует множить сущее без необходимости»). Теория оккамова обучения является формальным и математическим уточнением этого принципа. Блюмер с соавторами первыми показали, что оккамово обучение влечёт ПК обучение, которое является стандартной моделью обучения в теории вычислительного обучения. Другими словами, бережливость (выходной гипотезы) влечёт прогнозирующую способность.

Определение оккамова обучения

Лаконичность понятия в классе понятий можно выразить как длину самой короткой строки бит, которая может представить понятие в классе . Оккамово обучение соединяет лаконичность выхода алгоритма обучения с его прогнозирующей способностью.

Пусть и являются классами понятий, содержащих целевые понятия и гипотезы соответственно. Тогда, для констант и алгоритм обучения является -оккамовым алгоритмом для по гипотезам тогда и только тогда, когда, если дано множество , содержащее экземпляров, помеченных согласно понятию , выходом алгоритма является гипотеза , такая, что

  • согласуется с на (то есть )

где является максимальной длиной любого экземпляра . Алгоритм Оккама называется эффективным, если работает за полиномиальное от , и время. Мы говорим, что класс понятий оккамово обучаем по отношению к классу гипотез , если существует эффективный алгоритм Оккама для по гипотезам

Связь между оккамовым обучением и ПК обучением

Оккамова обучаемость влечёт ПК обучаемость, как показывает теорема Блюмера с соавторами:

Доказательство, что оккамово обучение влечёт ПК обучение

Мы сначала докажем версию с длиной. Назовём гипотезу плохой, если , где снова учитывает истинное понятие и распределение . Вероятность, что множество согласуется с , не превосходит , согласно независимости выборок. Для полного множества вероятность, что существует плохая гипотеза в , не превосходит , что меньше, чем , если . Это завершает доказательство второй теоремы.

Используя вторую теорему, мы докажем первую. Поскольку мы имеем -оккамов алгоритм, это означает, любая выходная гипотеза алгоритма может быть представлена не более чем битами, а тогда . Это меньше, чем , если мы положим для некоторой константы . Тогда, по версии теоремы с длиной, даст согласованную гипотезу с вероятностью не менее . Это завершает доказательство первой теоремы.

Улучшение сложности выборки для общих задач

Хотя оккамова обучаемость и ПК обучаемость эквивалентны, алгоритм Оккама может быть использован для получения более тесных границ сложности выборки для классических задач, включая логические умозаключения, умозаключения с несколькими переменными и списки решений.

Расширения

Оккамовы алгоримы, как было показано, успешно работают для ПК обучения в присутствии ошибок, обучения вероятностных понятий, обучения функций и марковских примерах с отсутствием независимости.

Литература

  • Kearns M. J., Vazirani U. V. chapter 2 // An introduction to computational learning theory. — MIT press, 1994. — ISBN 9780262111935.
  • Board R., Pitt L. On the necessity of Occam algorithms // Proceedings of the twenty-second annual ACM symposium on Theory of computing. — ACM, 1990.
  • Angluin D., Laird P. Learning from noisy examples // Machine Learning. — 1988. — Т. 2, вып. 4.
  • Kearns M., Li M. Learning in the presence of malicious errors // SIAM Journal on Computing,. — 1993. — Т. 22, вып. 4.

Kearns M. J., Schapire R. E. Efficient distribution-free learning of probabilistic concepts // Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium. — Los Alamitos, CA,: IEEE Computer Society Press, 1990.

    • Kearns M. J., Schapire R. E. Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium // JOURNAL OF COMPUTER AND SYSTEM SCIENCES. — 1994. — Вып. 48. — С. 464-497.
  • Natarajan B. K. Occam's razor for functions // Proceedings of the sixth annual conference on Computational learning theory. — ACM, 1993.

Aldous D., Vazirani U. A Markovian extension of Valiant's learning model // Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium. — IEEE, 1990.


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