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

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

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

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

Лаконичность понятия ${\displaystyle c}$ в классе понятий ${\displaystyle {\mathcal {C}}}$ можно выразить как длину ${\displaystyle size(c)}$ самой короткой строки бит, которая может представить понятие ${\displaystyle c}$ в классе ${\displaystyle {\mathcal {C}}}$. Оккамово обучение соединяет лаконичность выхода алгоритма обучения с его прогнозирующей способностью.

Пусть ${\displaystyle {\mathcal {C}}}$ и ${\displaystyle {\mathcal {H}}}$ являются классами понятий, содержащих целевые понятия и гипотезы соответственно. Тогда, для констант ${\displaystyle \alpha \geqslant 0}$ и ${\displaystyle 0\leqslant \beta <1}$ алгоритм обучения ${\displaystyle L}$ является ${\displaystyle (\alpha ,\beta )}$-оккамовым алгоритмом для ${\displaystyle {\mathcal {C}}}$ по гипотезам ${\displaystyle {\mathcal {H}}}$ тогда и только тогда, когда, если дано множество ${\displaystyle S=\{x\}}$, содержащее ${\displaystyle m}$ экземпляров, помеченных согласно понятию ${\displaystyle c(x)\in {\mathcal {C}}}$, выходом алгоритма ${\displaystyle L}$ является гипотеза ${\displaystyle h\in {\mathcal {H}}}$, такая, что

• ${\displaystyle h}$ согласуется с ${\displaystyle c}$ на ${\displaystyle S}$ (то есть ${\displaystyle h(x)=c(x),\forall x\in S}$)
• ${\displaystyle size(h)\leqslant (n\cdot size(c))^{\alpha }m^{\beta }}$^[2][1]

где ${\displaystyle n}$ является максимальной длиной любого экземпляра ${\displaystyle x\in S}$. Алгоритм Оккама называется эффективным, если работает за полиномиальное от ${\displaystyle n}$, ${\displaystyle m}$ и ${\displaystyle size(c)}$ время. Мы говорим, что класс понятий ${\displaystyle {\mathcal {C}}}$ оккамово обучаем по отношению к классу гипотез ${\displaystyle {\mathcal {H}}}$, если существует эффективный алгоритм Оккама для ${\displaystyle {\mathcal {C}}}$ по гипотезам ${\displaystyle {\mathcal {H}}.}$

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

Пусть ${\displaystyle L}$ является эффективным ${\displaystyle (\alpha ,\beta )}$-оккамовым алгоритмом для ${\displaystyle {\mathcal {C}}}$ по гипотезам ${\displaystyle {\mathcal {H}}}$. Тогда существует константа ${\displaystyle a>0}$, такая что для любых ${\displaystyle 0<\epsilon ,\delta <1}$ для любого распределения ${\displaystyle {\mathcal {D}}}$, если дано ${\displaystyle m\geqslant a\left({\frac {1}{\epsilon }}\log {\frac {1}{\delta }}+\left({\frac {(n\cdot size(c))^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)}$ экземпляров, извлечённых из ${\displaystyle {\mathcal {D}}}$ и помеченных согласно понятию ${\displaystyle c\in {\mathcal {C}}}$ каждый ${\displaystyle n}$ битами, алгоритм ${\displaystyle L}$ даст гипотезу ${\displaystyle h\in {\mathcal {H}}}$, такую что ${\displaystyle error(h)\leqslant \epsilon }$ с вероятностью по меньшей мере ${\displaystyle 1-\delta }$

. Здесь ${\displaystyle error(h)}$ учитывает понятие ${\displaystyle c}$ и распределение ${\displaystyle {\mathcal {D}}}$. Отсюда следует, что алгоритм ${\displaystyle L}$ является ПК учителем класса понятий ${\displaystyle {\mathcal {C}}}$ при классе гипотез ${\displaystyle {\mathcal {H}}}$. Слегка более общая формулировка:

Пусть ${\displaystyle 0<\epsilon ,\delta <1}$. Пусть ${\displaystyle L}$ будет алгоритмом, таким что при заданном наборе из ${\displaystyle m}$ экземпляров, извлечённых из фиксированного, но неизвестного распределения ${\displaystyle {\mathcal {D}}}$ и помеченных согласно понятия ${\displaystyle c\in {\mathcal {C}}}$ строкой бит длиной ${\displaystyle n}$ каждый, выходом будет гипотеза ${\displaystyle h\in {\mathcal {H}}_{n,m}}$, согласующаяся с помеченными экзмеплярами. Тогда существует константа ${\displaystyle b}$, такая что в случае ${\displaystyle \log |{\mathcal {H}}_{n,m}|\leqslant b\epsilon m-\log {\frac {1}{\delta }}}$ ${\displaystyle L}$ гарантированно даёт гипотезу ${\displaystyle h\in {\mathcal {H}}_{n,m}}$, такую что ${\displaystyle error(h)\leqslant \epsilon }$ с вероятностью по меньшей мере ${\displaystyle 1-\delta }$.

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

Класс понятий ${\displaystyle {\mathcal {C}}}$ полиномиально замкнут по спискам исключений, если существует алгоритм полиномиального времени выполнения ${\displaystyle A}$, такой, что, если задано представление понятия ${\displaystyle c\in {\mathcal {C}}}$ и конечный список ${\displaystyle E}$ исключений, выходом алгоритма будет представление понятия ${\displaystyle c'\in {\mathcal {C}}}$, такое, что понятия ${\displaystyle c}$ и ${\displaystyle c'}$ согласуются за исключение элементов множества ${\displaystyle E}$.

Мы сначала докажем версию с длиной. Назовём гипотезу ${\displaystyle h\in {\mathcal {H}}}$ плохой, если ${\displaystyle error(h)\geqslant \epsilon }$, где снова ${\displaystyle error(h)}$ учитывает истинное понятие ${\displaystyle c}$ и распределение ${\displaystyle {\mathcal {D}}}$. Вероятность, что множество ${\displaystyle S}$ согласуется с ${\displaystyle h}$, не превосходит ${\displaystyle (1-\epsilon )^{m}}$, согласно независимости выборок. Для полного множества вероятность, что существует плохая гипотеза в ${\displaystyle {\mathcal {H}}_{n,m}}$, не превосходит ${\displaystyle |{\mathcal {H}}_{n,m}|(1-\epsilon )^{m}}$, что меньше, чем ${\displaystyle \delta }$, если ${\displaystyle \log |{\mathcal {H}}_{n,m}|\leqslant O(\epsilon m)-\log {\frac {1}{\delta }}}$. Это завершает доказательство второй теоремы.

Используя вторую теорему, мы докажем первую. Поскольку мы имеем ${\displaystyle (\alpha ,\beta )}$-оккамов алгоритм, это означает, любая выходная гипотеза алгоритма ${\displaystyle L}$ может быть представлена не более чем ${\displaystyle (n\cdot size(c))^{\alpha }m^{\beta }}$ битами, а тогда ${\displaystyle \log |{\mathcal {H}}_{n,m}|\leqslant (n\cdot size(c))^{\alpha }m^{\beta }}$. Это меньше, чем ${\displaystyle O(\epsilon m)-\log {\frac {1}{\delta }}}$, если мы положим ${\displaystyle m\geqslant a\left({\frac {1}{\epsilon }}\log {\frac {1}{\delta }}+\left({\frac {(n\cdot size(c))^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)}$ для некоторой константы ${\displaystyle a>0}$. Тогда, по версии теоремы с длиной, ${\displaystyle L}$ даст согласованную гипотезу ${\displaystyle h}$ с вероятностью не менее ${\displaystyle 1-\delta }$. Это завершает доказательство первой теоремы.

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

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

• Минимизация структурного риска^[англ.]
• Теория вычислительного обучения

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.