Оккамово обучение в теории вычислительного обучения является моделью алгоритмического обучения [en] , где целью обучения является получение сжатого представления имеющихся тренировочных данных. Метод тесно связан с почти корректным обучением [en] (ПК обучение, англ. Probably Approximately Correct learning, PAC learning), где учитель оценивает прогнозирующую способность тестового набора.
Оккамова обучаемость влечёт ПК обучение и для широкого класса понятий обратное тоже верно — ПК обучаемость влечёт оккамову обучаемость.
Оккамово обучение названо по термину «бритва Оккама», который является принципом, утверждающим, что при предположении отсутствия дополнительных сущностей короткому объяснению наблюдений следует давать предпочтение по сравнению с более длинным объяснением (кратко: «Не следует множить сущее без необходимости»). Теория оккамова обучения является формальным и математическим уточнением этого принципа. Блюмер с соавторами первыми показали, что оккамово обучение влечёт ПК обучение, которое является стандартной моделью обучения в теории вычислительного обучения. Другими словами, бережливость (выходной гипотезы) влечёт прогнозирующую способность.
Лаконичность понятия в классе понятий можно выразить как длину самой короткой строки бит, которая может представить понятие в классе . Оккамово обучение соединяет лаконичность выхода алгоритма обучения с его прогнозирующей способностью.
Пусть и являются классами понятий, содержащих целевые понятия и гипотезы соответственно. Тогда, для констант и алгоритм обучения является -оккамовым алгоритмом для по гипотезам тогда и только тогда, когда, если дано множество , содержащее экземпляров, помеченных согласно понятию , выходом алгоритма является гипотеза , такая, что
где является максимальной длиной любого экземпляра . Алгоритм Оккама называется эффективным, если работает за полиномиальное от , и время. Мы говорим, что класс понятий оккамово обучаем по отношению к классу гипотез , если существует эффективный алгоритм Оккама для по гипотезам
Оккамова обучаемость влечёт ПК обучаемость, как показывает теорема Блюмера с соавторами:
Мы сначала докажем версию с длиной. Назовём гипотезу плохой, если , где снова учитывает истинное понятие и распределение . Вероятность, что множество согласуется с , не превосходит , согласно независимости выборок. Для полного множества вероятность, что существует плохая гипотеза в , не превосходит , что меньше, чем , если . Это завершает доказательство второй теоремы.
Используя вторую теорему, мы докажем первую. Поскольку мы имеем -оккамов алгоритм, это означает, любая выходная гипотеза алгоритма может быть представлена не более чем битами, а тогда . Это меньше, чем , если мы положим для некоторой константы . Тогда, по версии теоремы с длиной, даст согласованную гипотезу с вероятностью не менее . Это завершает доказательство первой теоремы.
Хотя оккамова обучаемость и ПК обучаемость эквивалентны, алгоритм Оккама может быть использован для получения более тесных границ сложности выборки для классических задач, включая логические умозаключения, умозаключения с несколькими переменными и списки решений.
Оккамовы алгоримы, как было показано, успешно работают для ПК обучения в присутствии ошибок, обучения вероятностных понятий, обучения функций и марковских примерах с отсутствием независимости.
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.
Aldous D., Vazirani U. A Markovian extension of Valiant's learning model // Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium. — IEEE, 1990.