Обучение Оккама - 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 бета <1}$ , алгоритм обучения ${ displaystyle L}$ является ${ Displaystyle ( альфа, бета)}$ -Алгоритм Оккама за ${ 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 час (х) = с (х), 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 ( альфа, бета)}$ -Алгоритм Оккама для ${ 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 (с) ) ^ { 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 ( альфа, бета)}$ -Алгоритм Оккама, это означает, что любая гипотеза выводится ${ displaystyle L}$ может быть представлено не более чем ${ Displaystyle (п размер компакт-диска (с)) ^ { альфа} м ^ { бета}}$ биты, и таким образом ${ displaystyle log | { mathcal {H}} _ {n, m} | leq (n размер CDOT (c)) ^ { alpha} m ^ { beta}}$ . Это меньше чем ${ Displaystyle О ( эпсилон м) - log { frac {1} { delta}}}$ если мы установим ${ displaystyle m geq a left ({ frac {1} { epsilon}} log { frac {1} { delta}} + left ({ frac {(n размер CDOT (с) ) ^ { 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]