обучение по методу Оккама

Модель алгоритмического обучения

В теории вычислительного обучения обучение по методу Оккама — это модель алгоритмического обучения, где целью обучающегося является выдача краткого представления полученных обучающих данных. Это тесно связано с обучением «вероятно приблизительно правильно» (PAC) , где обучающийся оценивается по его предсказательной силе тестового набора.

Обучаемость по Оккаму подразумевает обучение по PAC, а для широкого спектра классов понятий обратное также верно: обучаемость по PAC подразумевает обучаемость по Оккаму.

Введение

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

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

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

Пусть и будут классами концепций, содержащими целевые концепции и гипотезы соответственно. Тогда для констант и алгоритм обучения является -алгоритмом Оккама для использования тогда и только тогда, когда задан набор образцов , помеченных в соответствии с концепцией , выводит гипотезу, такую ​​что ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle \alpha \geq 0}$ ${\displaystyle 0\leq \beta <1}$ ${\displaystyle L}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle S=\{x_{1},\dots ,x_{m}\}}$ ${\displaystyle m}$ ${\displaystyle c\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)\leq (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}}.}$

Связь между Оккамом и обучением PAC

Обучаемость Оккама подразумевает обучаемость PAC, как показывает следующая теорема Блумера и др. ^[2] :

Теорема (Обучение Оккама подразумевает обучение PAC)

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

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

Теорема (Обучение Оккама подразумевает обучение PAC, версия с кардинальностью)

Пусть . Пусть будет алгоритмом, таким, что, учитывая выборки, взятые из фиксированного, но неизвестного распределения и помеченные в соответствии с концепцией длины бит каждая, выводит гипотезу , которая согласуется с помеченными выборками. Тогда существует константа такая, что если , то гарантированно выводит гипотезу такую, что с вероятностью по крайней мере . ${\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}|\leq b\epsilon m-\log {\frac {1}{\delta }}}$ ${\displaystyle L}$ ${\displaystyle h\in {\mathcal {H}}_{n,m}}$ ${\displaystyle error(h)\leq \epsilon }$ ${\displaystyle 1-\delta }$

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

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

Доказательство того, что изучение Оккама подразумевает изучение PAC

Сначала мы докажем версию Кардинальности. Назовем гипотезу плохой , если , где снова по отношению к истинной концепции и лежащему в основе распределению . Вероятность того, что набор образцов согласуется с , не превышает , в силу независимости образцов. По границе объединения вероятность того, что существует плохая гипотеза в , не превышает , что меньше, чем если . Это завершает доказательство второй теоремы выше. ${\displaystyle h\in {\mathcal {H}}}$ ${\displaystyle error(h)\geq \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}|\leq 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}|\leq (n\cdot size(c))^{\alpha }m^{\beta }}$ ${\displaystyle O(\epsilon m)-\log {\frac {1}{\delta }}}$ ${\displaystyle m\geq 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 }$

Повышение сложности выборки для решения распространенных проблем

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

Расширения

Алгоритмы Оккама также показали свою эффективность для обучения PAC при наличии ошибок ^{[6] [7]} вероятностных концепций ^[8] обучения функций ^[9] и марковских ненезависимых примеров ^{[10] .}

Смотрите также

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

Ссылки

1. Блюмер А., Эренфойхт А., Хаусслер Д. и Вармут М.К. (1987). Бритва Оккама . Письма об обработке информации, 24(6), 377-380.
2. Кернс, М. Дж. и Вазирани, У. В. (1994). Введение в теорию вычислительного обучения, глава 2. MIT press.
3. Борд, Р. и Питт, Л. (1990, апрель). О необходимости алгоритмов Оккама. В трудах двадцать второго ежегодного симпозиума ACM по теории вычислений (стр. 54-63). ACM.
4. Хаусслер, Д. (1988). Количественная оценка индуктивного смещения: алгоритмы обучения ИИ и структура обучения Valiant Архивировано 12 апреля 2013 г. в Wayback Machine . Искусственный интеллект, 36(2), 177-221.
5. Ривест, Р. Л. (1987). Обучение спискам решений. Машинное обучение , 2(3), 229-246.
6. Angluin, D., & Laird, P. (1988). Обучение на зашумленных примерах. Machine Learning, 2(4), 343-370.
7. Кернс, М. и Ли, М. (1993). Обучение при наличии вредоносных ошибок. Журнал SIAM по вычислениям, 22(4), 807-837.
8. Кернс, М. Дж. и Шапир, Р. Э. (октябрь 1990 г.). Эффективное обучение вероятностных концепций без распределения . В «Основах компьютерной науки», 1990 г. Труды., 31-й ежегодный симпозиум по (стр. 382-391). IEEE.
9. Натараджан, Б.К. (1993, август). Бритва Оккама для функций. В трудах шестой ежегодной конференции по теории вычислительного обучения (стр. 370-376). ACM.
10. Олдос, Д. и Вазирани, У. (1990, октябрь). Марковское расширение модели обучения Валианта . В «Основах компьютерной науки», 1990. Труды., 31-й ежегодный симпозиум по (стр. 392-396). IEEE.

Дальнейшее чтение

• Блумер, А.; Эренфойхт, А.; Хаусслер, Д.; Вармут, М. К. Обучаемость и измерение Вапника-Червоненкиса. Журнал ACM, 36(4):929–865, 1989.