Любые классы гипотез, кроме четности в шумном PAC, но не в SQ?

11

Angluin и Laird ('88) формализовали обучение со случайно искаженными данными в модели «PAC со случайным классификационным шумом» (или с шумным PAC). Эта модель аналогична обучению PAC , за исключением того, что метки примеров, данных учащемуся, искажены (перевернуты) независимо друг от друга наугад, с вероятностью .η<1/2

Чтобы помочь охарактеризовать то, что можно изучить в модели PAC с шумом, Kearns ('93) ввел модель статистического запроса (SQ) для обучения. В этой модели учащийся может запросить у статистического оракула свойства целевого распределения, и он показал, что любой класс, пригодный для SQ, может быть изучен в шумном PAC. Кернс также доказал, что четности по n переменным не могут быть изучены во времени быстрее, чем 2n/c для некоторой константы c .

Затем Blum et al. ('00) отделил зашумленный PAC от SQ, показав, что четности на первом (log(n)loglog(n)) можно узнать за полиномиальное время в модели с зашумленным PAC, но не в модели SQ.

У меня вопрос такой:

Четности (по первым (log(n)loglog(n)) переменным) можно узнать в модели PAC с шумом, но не в модели SQ. Существуют ли какие-либо другие конкретные классы, достаточно отличающиеся от четности, которые, как известно, могут быть изучены в шумном PAC, но не в SQ?

Лев Рейзин
источник

Ответы:

6

Я думаю, что ответ «нет», хотя я не уверен и также был бы заинтересован в других примерах. Одна вещь, которая известна, состоит в том, что агностическое обучение значительно сложнее с точки зрения теории информации в модели SQ. Для распознавания монотонных дизъюнкций с ошибкой epsilon требуется только примера в настройке PAC (хотя задача обучения может оказаться сложной в вычислительном отношении ...). В модели SQ отсутствует алгоритм агностического обучения для монотонных дизъюнкций, который имеет полиномиальную зависимость от с точки зрения количества запросов, которые он делает, даже игнорируя вычислительные соображения.d/ϵ21/ϵ

Аарон Рот
источник
Спасибо, Аарон - это было мое понимание положения вещей, но я не был уверен. Если никто не даст мне пример в ближайшее время, я отмечу ваш как принятый ответ.
Лев Рейзин
6

Это хороший вопрос. Я предполагаю, что вы ищете другую технику разделения, а не просто другой класс функций (поскольку легко привести естественные и искусственные примеры концептуальных классов, которые все еще полагаются на результат BKW для разделения). Я бы пошел дальше и сказал, что даже пример четности не является решающим разделением, так как модель SQ дает обучение с частотой, обратной полиномиально близкой к 1/2, тогда как BKW не допускает шум со скоростью . Думаю, было бы интересно найти «чистое» разделение. Кажется, что это также потребует новой техники, отвечая на ваш первоначальный вопрос.1/2nϵ

Виталий
источник
Да, верно, я хочу другую технику разделения, а не то, что зависит от BKW. Ваш дополнительный вопрос чистого разделения также интересен.
Лев Рейзин