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

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

Введение

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

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

Лаконичность понятия ${\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 }}$

где ${\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}}.}$

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

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

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

Пусть ${\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 }$ .

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

Класс понятий ${\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 }$ . Это завершает доказательство первой теоремы.

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

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

Расширения

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

См. также

• Теория вычислительного обучения

Примечания

Литература