Русская Википедия:Оккамово обучение
Оккамово обучение в теории вычислительного обучения является моделью Шаблон:Не переведено 5, где целью обучения является получение сжатого представления имеющихся тренировочных данных. Метод тесно связан с почти корректным обучением (ПК обучение, Шаблон:Lang-en, PAC learning), где учитель оценивает прогнозирующую способность тестового набора.
Оккамова обучаемость влечёт ПК обучение и для широкого класса понятий обратное тоже верно — ПК обучаемость влечёт оккамову обучаемость.
Введение
Оккамово обучение названо по термину «бритва Оккама», который является принципом, утверждающим, что при предположении отсутствия дополнительных сущностей короткому объяснению наблюдений следует давать предпочтение по сравнению с более длинным объяснением (кратко: «Не следует множить сущее без необходимости»). Теория оккамова обучения является формальным и математическим уточнением этого принципа. Блюмер с соавторами первыми показалиШаблон:Sfn, что оккамово обучение влечёт ПК обучение, которое является стандартной моделью обучения в теории вычислительного обучения. Другими словами, бережливость (выходной гипотезы) влечёт прогнозирующую способность.
Определение оккамова обучения
Лаконичность понятия <math>c</math> в классе понятий <math>\mathcal{C}</math> можно выразить как длину <math>size(c)</math> самой короткой строки бит, которая может представить понятие <math>c</math> в классе <math>\mathcal{C}</math>. Оккамово обучение соединяет лаконичность выхода алгоритма обучения с его прогнозирующей способностью.
Пусть <math>\mathcal{C}</math> и <math>\mathcal{H}</math> являются классами понятий, содержащих целевые понятия и гипотезы соответственно. Тогда, для констант <math>\alpha \geqslant 0</math> и <math>0 \leqslant \beta <1</math> алгоритм обучения <math>L</math> является <math>(\alpha,\beta)</math>-оккамовым алгоритмом для <math>\mathcal{C}</math> по гипотезам <math>\mathcal{H}</math> тогда и только тогда, когда, если дано множество <math>S = \{ x \}</math>, содержащее <math>m</math> экземпляров, помеченных согласно понятию <math>c(x) \in \mathcal{C}</math>, выходом алгоритма <math>L</math> является гипотеза <math>h \in \mathcal{H}</math>, такая, что
- <math>h</math> согласуется с <math>c</math> на <math>S</math> (то есть <math> h(x)=c(x),\forall x \in S </math>)
- <math>size(h) \leqslant (n \cdot size(c))^\alpha m^\beta </math>Шаблон:SfnШаблон:Sfn
где <math>n</math> является максимальной длиной любого экземпляра <math>x \in S</math>. Алгоритм Оккама называется эффективным, если работает за полиномиальное от <math>n</math>, <math>m</math> и <math>size(c)</math> время. Мы говорим, что класс понятий <math>\mathcal{C}</math> оккамово обучаем по отношению к классу гипотез <math>\mathcal{H}</math>, если существует эффективный алгоритм Оккама для <math>\mathcal{C}</math> по гипотезам <math>\mathcal{H}.</math>
Связь между оккамовым обучением и ПК обучением
Оккамова обучаемость влечёт ПК обучаемость, как показывает теорема Блюмера с соавторамиШаблон:Sfn:
Теорема (Оккамово обучение влечёт ПК обучение)
Пусть <math>L</math> является эффективным <math>(\alpha,\beta)</math>-оккамовым алгоритмом для <math>\mathcal{C}</math> по гипотезам <math>\mathcal{H}</math>. Тогда существует константа <math>a > 0</math>, такая что для любых <math>0 < \epsilon, \delta < 1</math> для любого распределения <math>\mathcal{D} </math>, если дано <math>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)</math> экземпляров, извлечённых из <math>\mathcal{D}</math> и помеченных согласно понятию <math>c \in \mathcal{C} </math> каждый <math>n</math> битами, алгоритм <math>L</math> даст гипотезу <math>h \in \mathcal{H} </math>, такую что <math>error(h)\leqslant \epsilon</math> с вероятностью по меньшей мере <math>1-\delta</math>
. Здесь <math>error(h)</math> учитывает понятие <math>c</math> и распределение <math>\mathcal{D} </math>. Отсюда следует, что алгоритм <math>L</math> является ПК учителем класса понятий <math>\mathcal{C}</math> при классе гипотез <math>\mathcal{H}</math>. Слегка более общая формулировка:
Теорема (Оккамово обучение влечёт ПК обучение, версия с длиной)
Пусть <math>0 < \epsilon, \delta < 1</math>. Пусть <math>L</math> будет алгоритмом, таким что при заданном наборе из <math>m</math> экземпляров, извлечённых из фиксированного, но неизвестного распределения <math>\mathcal{D}</math> и помеченных согласно понятия <math>c \in \mathcal{C} </math> строкой бит длиной <math>n</math> каждый, выходом будет гипотеза <math>h \in \mathcal{H}_{n,m} </math>, согласующаяся с помеченными экзмеплярами. Тогда существует константа <math>b</math>, такая что в случае <math>\log |\mathcal{H}_{n,m}| \leqslant b \epsilon m - \log \frac{1}{\delta}</math> <math>L</math> гарантированно даёт гипотезу <math>h \in \mathcal{H}_{n,m} </math>, такую что <math>error(h)\leqslant \epsilon</math> с вероятностью по меньшей мере <math>1-\delta</math>.
Хотя приведённые теоремы показввают, что оккамово обучение достаточно для ПК обучения, они ничего не говорят о необходимости. Боард и Питт показали, что для широкого класс понятий оккамово обучение является необходимым для ПК обученияШаблон:Sfn. Они показали, что для любого класса понятий, который полиномиально замкнут по спискам исключений, ПК обучаемость влечёт существование оккамова алгоритма для этого класса понятий. Классы понятий, полиномиально замкнутые по спискам исключений, включают булевские формулы, суммирующие цепи, детерминированные конечные автоматы, списки решений, деревья решений и другие классы понятий на геометрической основе.
Класс понятий <math>\mathcal{C}</math> полиномиально замкнут по спискам исключений, если существует алгоритм полиномиального времени выполнения <math>A</math>, такой, что, если задано представление понятия <math>c \in \mathcal{C} </math> и конечный список <math>E</math> исключений, выходом алгоритма будет представление понятия <math>c' \in \mathcal{C}</math>, такое, что понятия <math>c</math> и <math>c'</math> согласуются за исключение элементов множества <math>E</math>.
Доказательство, что оккамово обучение влечёт ПК обучение
Мы сначала докажем версию с длиной. Назовём гипотезу <math>h\in \mathcal{H} </math> плохой, если <math>error(h) \geqslant \epsilon</math>, где снова <math>error(h)</math> учитывает истинное понятие <math>c</math> и распределение <math>\mathcal{D}</math>. Вероятность, что множество <math>S</math> согласуется с <math>h</math>, не превосходит <math>(1 - \epsilon)^m</math>, согласно независимости выборок. Для полного множества вероятность, что существует плохая гипотеза в <math>\mathcal{H}_{n,m}</math>, не превосходит <math> | \mathcal{H}_{n,m} | (1 - \epsilon)^m</math>, что меньше, чем <math>\delta </math>, если <math>\log | \mathcal{H}_{n,m} | \leqslant O(\epsilon m) - \log \frac{1}{\delta}</math>. Это завершает доказательство второй теоремы.
Используя вторую теорему, мы докажем первую. Поскольку мы имеем <math>(\alpha,\beta)</math>-оккамов алгоритм, это означает, любая выходная гипотеза алгоритма <math>L</math> может быть представлена не более чем <math> (n \cdot size(c))^\alpha m^\beta</math> битами, а тогда <math> \log |\mathcal{H}_{n,m}| \leqslant (n \cdot size(c))^\alpha m^\beta</math>. Это меньше, чем <math>O(\epsilon m) - \log \frac{1}{\delta}</math>, если мы положим <math> 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)</math> для некоторой константы <math>a > 0</math>. Тогда, по версии теоремы с длиной, <math>L</math> даст согласованную гипотезу <math>h</math> с вероятностью не менее <math>1 - \delta</math>. Это завершает доказательство первой теоремы.
Улучшение сложности выборки для общих задач
Хотя оккамова обучаемость и ПК обучаемость эквивалентны, алгоритм Оккама может быть использован для получения более тесных границ сложности выборки для классических задач, включая логические умозаключенияШаблон:Sfn, умозаключения с несколькими переменными Шаблон:Sfn и списки решенийШаблон:Sfn.
Расширения
Оккамовы алгоримы, как было показано, успешно работают для ПК обучения в присутствии ошибокШаблон:SfnШаблон:Sfn, обучения вероятностных понятийШаблон:Sfn, обучения функцийШаблон:Sfn и марковских примерах с отсутствием независимостиШаблон:Sfn.
См. также
Примечания
Литература
Шаблон:Refend Шаблон:Машинное обучение Шаблон:Rq
