Оккамово обучение

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

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

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

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

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

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

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

  • согласуется с на (то есть )
  • [2][1]

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

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

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

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

Теорема (Оккамово обучение влечёт ПК обучение)

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

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

. Здесь учитывает понятие и распределение . Отсюда следует, что алгоритм является ПК учителем класса понятий при классе гипотез . Слегка более общая формулировка:

Теорема (Оккамово обучение влечёт ПК обучение, версия с длиной)

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

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

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

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

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

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

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

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

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

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

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

Расширения

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

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

Примечания

[править | править код]
  1. 1 2 Blumer, Ehrenfeucht, Haussler, Warmuth, 1987, с. 377—380.
  2. 1 2 3 Kearns, Vazirani, 1994.
  3. Board, Pitt, 1990, с. 54—63.
  4. Haussler, 1988, с. 177—221.
  5. Rivest, 1987, с. 229—246.
  6. Angluin, Laird, 1988, с. 343—370.
  7. Kearns, Li, 1993, с. 807—837.
  8. Kearns, Schapire, 1990, с. 382—391.
  9. Natarajan, 1993, с. 370—376.
  10. Aldous, Vazirani, 1990, с. 392—396.

Литература

[править | править код]
  • Kearns M. J., Vazirani U. V. chapter 2 // An introduction to computational learning theory. — MIT press, 1994. — ISBN 9780262111935.
  • Blumer A., Ehrenfeucht A., Haussler D., Warmuth M. K. Occam's razor. — 1987. — Т. 24, вып. 6. — doi:10.1016/0020-0190(87)90114-1.
  • Board R., Pitt L. On the necessity of Occam algorithms // Proceedings of the twenty-second annual ACM symposium on Theory of computing. — ACM, 1990.
  • Haussler D. Quantifying inductive bias: AI learning algorithms and Valiant's learning framework // Artificial intelligence. — 1988. — Т. 36, вып. 2. Архивировано 12 апреля 2013 года.
  • Rivest R. L. Learning decision lists // Machine learning. — 1987. — Т. 2, вып. 3.
  • 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.