Каков современный уровень сложности запросов для правильных формул PAC, изучающих 2-DNF с типовыми запросами и при равномерном распределении ? Или какие-нибудь нетривиальные ограничения на это?
Поскольку я совсем не знаком с теорией обучения, и этот вопрос мотивирован другой областью, ответ может быть очевидным. Я проверил книгу Кернса и Вазирани, но они явно не рассматривают эту настройку явно.
UPD. Хотя основной интересующий параметр - сложность запроса, время выполнения также важно. Если возможно, время выполнения должно быть примерно таким же, как сложность запроса, или не более чем полиномиальным.
UPD. В приложении B (вверху страницы 18) к статье «Изучение субмодульных функций» Балкана и Харви упоминается, что «Хорошо известно, что 2-DNF эффективно изучаются PAC». Тем не менее, они не упоминают, является ли этот результат для правильного обучения или дают какие-либо ссылки.
источник
Ответы:
Я не знаю, будете ли вы считать следующее нетривиальным ограничением, но здесь я иду.
Во-первых, чтобы быть ясно, чтобы мы не путалиc -DNF с k срок DNF (который я часто делаю), c -DNF формула над переменными x1,…,xn имеет форму ∨ki=1(ℓi,1∧ℓi,2...ℓi,c) где ∀1≤i≤k а также 1≤j≤c , ℓi,j∈{x1,…,xn,x¯1,…,x¯n} ,
Сначала мы можем спросить, сколько разных терминов может существовать вc -DNF. Каждый член будет иметьc из n переменные, каждая из которых либо отрицается, либо нет - что делает для разные возможные термины. В экземпляре 2-DNF каждый термин будет появляться или не появляться, что делает для возможных «целей», где - пространство гипотез.2c(nc) |H|=22c(nc) H
Представьте себе алгоритм, который берет выборок, а затем пробует всегипотезы, пока он не найдет тот, который идеально предсказывает на выборках. Теорема Оккама о бритве говорит, что вам нужно всего лишь взять для этого алгоритма, чтобы найти цель с ошибкой с вероятностью .m |H| m=O(1ϵ|(H|+1δ) ≤ϵ ≥1−δ
В нашем случае, , , что означает, что вам потребуется выборки для (правильного) обучения.c=2 lg|H|=O(n2) n2
Но вся игра в обучении - это не просто сложность образца (хотя это и есть часть игры, особенно в обучении с использованием атрибутов), а скорее попытка разработать алгоритмы за полиномиальное время. Если вы не заботитесь об эффективности, тогда - самый простой ответ для сложности образца PAC.n2
ОБНОВЛЕНИЕ (учитывая измененный вопрос) :
Поскольку вы прямо заявили, что заботитесь только о сложности примеров, я представил алгоритм Occam с грубой силой, который, вероятно, является самым простым аргументом. Тем не менее, мой ответ был немного застенчивым. ДНФ действительно изучаемы за полиномиальное время! Это результат оригинальной статьи Валианта « Теория обучения ». На самом деле -DNF могут быть изучены для любого .2 c c=O(1)
Аргумент заключается в следующем. Вы можете рассматривать -DNF как дизъюнкцию от «метапеременных» и пытаться изучить дизъюнкцию, удаляя метапеременные, несовместимые с примерами. Такое решение может быть легко переведено обратно в «правильное» решение и занимает времени. Как примечание, все еще открыто, есть ли алгоритм полиномиального времени для .c ≈nc O(nc) c=ω(1)
Что касается того, является ли сложность выборки также нижней границей, ответ в значительной степени да. Эта статья Ehrenfeucht et al. показывает, что граница Оккама почти жесткая.n2
источник