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

Оккамово обучение названо по термину «бритва Оккама», который является принципом, утверждающим, что при предположении отсутствия дополнительных сущностей короткому объяснению наблюдений следует давать предпочтение по сравнению с более длинным объяснением (кратко: «Не следует множить сущее без необходимости»). Теория оккамова обучения является формальным и математическим уточнением этого принципа. Блюмер с соавторами первыми показали[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 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].

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