Обучение Оккама - Occam learning

В теория вычислительного обучения, Обучение Оккама представляет собой модель алгоритмического обучения, в которой цель обучаемого - получить сжатое представление полученных данных обучения. Это тесно связано с возможно приблизительно правильное (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 }$ .

Здесь, ${\displaystyle error(h)}$ по отношению к концепции ${\displaystyle c}$ и распространение ${\displaystyle {\mathcal {D}}}$. Это означает, что алгоритм ${\displaystyle L}$ также является учеником PAC для концептуального класса ${\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

Сначала докажем версию Cardinality. Назовите гипотезу ${\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 В архиве 2013-04-12 в 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. Кирнс, М. Дж., И Шапир, Р. Э. (1990, октябрь). Эффективное изучение вероятностных концепций без распределения. В «Основах компьютерных наук», 1990. Труды, 31-й ежегодный симпозиум по (стр. 382-391). IEEE.
9. Натараджан, Б. К. (1993, август). Бритва Оккама для функций. В материалах шестой ежегодной конференции по теории вычислительного обучения (стр. 370-376). ACM.
10. Олдос Д. и Вазирани У. (1990, октябрь). Марковское расширение модели обучения Valiant. В «Основах компьютерных наук», 1990. Труды, 31-й ежегодный симпозиум по (стр. 392–396). IEEE.