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

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

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

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

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

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

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

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