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

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

Обучаемость по Оккаму подразумевает обучение с помощью PAC, а для широкого спектра концептуальных классов верно и обратное: обучаемость с помощью PAC подразумевает обучаемость по Оккаму.

Введение

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

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

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

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

$h$ соответствует $c$ на $S$ (то есть, $h(x)=c(x),\forall x\in S$ ), и
$size(h)\leq (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}}.$

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

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

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

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

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

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

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

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

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

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

Сначала мы докажем версию кардинальности. Вызов гипотезы $h\in {\mathcal {H}}$ плохо, если $error(h)\geq \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}|\leq O(\epsilon m)-\log {\frac {1}{\delta }}$ . На этом завершается доказательство второй теоремы, приведенной выше.

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

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

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

Расширения

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

См. также

Ссылки

^ Перейти обратно: ^а ^б Блюмер А., Эренфойхт А., Хаусслер Д. и Вармут М.К. (1987). Бритва Оккама . Письма об обработке информации, 24(6), 377-380.
^ Перейти обратно: ^а ^б ^с Кернс, М.Дж., и Вазирани, У.В. (1994). Введение в теорию компьютерного обучения , глава 2. MIT Press.
^ Борд Р. и Питт Л. (1990, апрель). О необходимости алгоритмов Оккама. В материалах двадцать второго ежегодного симпозиума ACM по теории вычислений (стр. 54–63). АКМ.
^ Хаусслер, Д. (1988). Количественная оценка индуктивной предвзятости: алгоритмы обучения ИИ и система обучения Valiant. Архивировано 12 апреля 2013 г. в Wayback Machine . Искусственный интеллект, 36(2), 177-221.
^ Ривест, РЛ (1987). Списки учебных решений. Машинное обучение , 2(3), 229-246.
^ Англуин Д. и Лэрд П. (1988). Обучение на шумных примерах. Машинное обучение, 2(4), 343–370.
^ Кернс, М., и Ли, М. (1993). Обучение при наличии вредоносных ошибок. SIAM Journal on Computing, 22 (4), 807–837.
^ Кернс, MJ, и Шапир, RE (1990, октябрь). Эффективное изучение вероятностных концепций без распределения . В «Основах информатики», 1990. Труды 31-го ежегодного симпозиума (стр. 382–391). IEEE.
^ Натараджан, Б.К. (1993, август). Бритва Оккама для функций. В материалах шестой ежегодной конференции по теории вычислительного обучения (стр. 370–376). АКМ.
^ Олдос Д. и Вазирани У. (1990, октябрь). Марковское расширение модели обучения Valiant . В «Основах информатики», 1990. Труды 31-го ежегодного симпозиума (стр. 392–396). IEEE.

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

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

[def-1] Перейти обратно: ^а ^б Блюмер А., Эренфойхт А., Хаусслер Д. и Вармут М.К. (1987). Бритва Оккама . Письма об обработке информации, 24(6), 377-380.

[kv-2] Перейти обратно: ^а ^б ^с Кернс, М.Дж., и Вазирани, У.В. (1994). Введение в теорию компьютерного обучения , глава 2. MIT Press.

[3] Борд Р. и Питт Л. (1990, апрель). О необходимости алгоритмов Оккама. В материалах двадцать второго ежегодного симпозиума ACM по теории вычислений (стр. 54–63). АКМ.

[4] Хаусслер, Д. (1988). Количественная оценка индуктивной предвзятости: алгоритмы обучения ИИ и система обучения Valiant. Архивировано 12 апреля 2013 г. в Wayback Machine . Искусственный интеллект, 36(2), 177-221.

[5] Ривест, РЛ (1987). Списки учебных решений. Машинное обучение , 2(3), 229-246.

[6] Англуин Д. и Лэрд П. (1988). Обучение на шумных примерах. Машинное обучение, 2(4), 343–370.

[7] Кернс, М., и Ли, М. (1993). Обучение при наличии вредоносных ошибок. SIAM Journal on Computing, 22 (4), 807–837.

[8] Кернс, MJ, и Шапир, RE (1990, октябрь). Эффективное изучение вероятностных концепций без распределения . В «Основах информатики», 1990. Труды 31-го ежегодного симпозиума (стр. 382–391). IEEE.

[9] Натараджан, Б.К. (1993, август). Бритва Оккама для функций. В материалах шестой ежегодной конференции по теории вычислительного обучения (стр. 370–376). АКМ.

[10] Олдос Д. и Вазирани У. (1990, октябрь). Марковское расширение модели обучения Valiant . В «Основах информатики», 1990. Труды 31-го ежегодного симпозиума (стр. 392–396). IEEE.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]