PROFILPELAJAR.COM

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Расширения

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

См. также

Примечания

↑ ¹ ² Blumer, Ehrenfeucht, Haussler, Warmuth, 1987, с. 377—380.
↑ ¹ ² ³ Kearns, Vazirani, 1994.
↑ Board, Pitt, 1990, с. 54—63.
↑ Haussler, 1988, с. 177—221.
↑ Rivest, 1987, с. 229—246.
↑ Angluin, Laird, 1988, с. 343—370.
↑ Kearns, Li, 1993, с. 807—837.
↑ Kearns, Schapire, 1990, с. 382—391.
↑ Natarajan, 1993, с. 370—376.
↑ 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.