Правильное PAC обучение 2-DNF при равномерном распределении

10

Каков современный уровень сложности запросов для правильных формул PAC, изучающих 2-DNF с типовыми запросами и при равномерном распределении ? Или какие-нибудь нетривиальные ограничения на это?

Поскольку я совсем не знаком с теорией обучения, и этот вопрос мотивирован другой областью, ответ может быть очевидным. Я проверил книгу Кернса и Вазирани, но они явно не рассматривают эту настройку явно.

UPD. Хотя основной интересующий параметр - сложность запроса, время выполнения также важно. Если возможно, время выполнения должно быть примерно таким же, как сложность запроса, или не более чем полиномиальным.

UPD. В приложении B (вверху страницы 18) к статье «Изучение субмодульных функций» Балкана и Харви упоминается, что «Хорошо известно, что 2-DNF эффективно изучаются PAC». Тем не менее, они не упоминают, является ли этот результат для правильного обучения или дают какие-либо ссылки.

Григорий Ярославцев
источник
Что за запросы?
Тимоти Сан
Просто образцы. Также, я думаю, мне следует четко указать, что вопрос касается сложности запроса, а не времени выполнения (отредактировано).
Григорий Ярославцев
Я ответил на ваш вопрос, предполагая, что примеры запросов - это просто случайные примеры (а не запросы членства).
Лев Рейзин
1
Да, запросы - это просто случайные примеры из равномерного распределения.
Григорий Ярославцев

Ответы:

14

Я не знаю, будете ли вы считать следующее нетривиальным ограничением, но здесь я иду.

Во-первых, чтобы быть ясно, чтобы мы не путали c-DNF с kсрок DNF (который я часто делаю), c-DNF формула над переменными x1,,xn имеет форму i=1k(i,1i,2...i,c) где 1ik а также 1jc, 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=2lg|H|=O(n2)n2

Но вся игра в обучении - это не просто сложность образца (хотя это и есть часть игры, особенно в обучении с использованием атрибутов), а скорее попытка разработать алгоритмы за полиномиальное время. Если вы не заботитесь об эффективности, тогда - самый простой ответ для сложности образца PAC.n2

ОБНОВЛЕНИЕ (учитывая измененный вопрос) :

Поскольку вы прямо заявили, что заботитесь только о сложности примеров, я представил алгоритм Occam с грубой силой, который, вероятно, является самым простым аргументом. Тем не менее, мой ответ был немного застенчивым. ДНФ действительно изучаемы за полиномиальное время! Это результат оригинальной статьи Валианта « Теория обучения ». На самом деле -DNF могут быть изучены для любого .2cc=O(1)

Аргумент заключается в следующем. Вы можете рассматривать -DNF как дизъюнкцию от «метапеременных» и пытаться изучить дизъюнкцию, удаляя метапеременные, несовместимые с примерами. Такое решение может быть легко переведено обратно в «правильное» решение и занимает времени. Как примечание, все еще открыто, есть ли алгоритм полиномиального времени для .cncO(nc)c=ω(1)

Что касается того, является ли сложность выборки также нижней границей, ответ в значительной степени да. Эта статья Ehrenfeucht et al. показывает, что граница Оккама почти жесткая.n2

Лев Рейзин
источник
1
Спасибо! Это нетривиальный результат - я не осознавал, что показательное время работы будет полезным. Тем не менее, для приложения, которое я имею в виду, на самом деле полиномиальное время гораздо более желательно (обновленный вопрос). Является ли описанный вами подход наиболее известным для этой проблемы? Есть ли нижние границы сложности запросов (даже для неограниченного времени выполнения)?
Григорий Ярославцев
Обновил вопрос со ссылкой, которая мотивировала вопрос.
Григорий Ярославцев
1
обновил ответ с учетом вашего обновленного вопроса
Лев Рейзин
Кроме того - в этом случае я не думаю, что экспоненциальное время работы полезно. Но в целом похоже. Обучение (с оптимальной сложностью выборки) обычно легко, когда у вас экспоненциальное время.
Лев Рейзин
2
Большое спасибо! Мне понадобится некоторое время, чтобы проверить ссылки, но пока это кажется полным ответом.
Григорий Ярославцев