Adakah Kelas Hipotesis Selain Paritas di PAC Bising tetapi tidak di SQ?

Angluin dan Laird ('88) memformalkan pembelajaran dengan data yang rusak secara acak dalam model "PAC dengan noise klasifikasi acak" (atau PAC berisik). Model ini mirip dengan pembelajaran PAC , kecuali untuk label contoh yang diberikan kepada pelajar rusak (terbalik), secara independen secara acak, dengan probabilitas .$\eta < 1/2$

Untuk membantu mengkarakterisasi apa yang bisa dipelajari dalam model PAC yang bising, Kearns ('93) memperkenalkan model Statistik Query (SQ) untuk pembelajaran. Dalam model ini, seorang pelajar dapat meminta oracle statistik untuk properti dari distribusi target, dan dia menunjukkan bahwa setiap kelas yang dipelajari SQ dapat dipelajari dalam PAC berisik. Kearns juga membuktikan bahwa paritas pada variabel tidak dapat dipelajari dalam waktu lebih cepat dari 2 n / c untuk beberapa konstanta c .$n$$2^{n/c}$$c$

Kemudian Blum et al. ('00) dipisahkan berisik PAC dari SQ dengan menunjukkan bahwa paritas pada pertama adalah polinomial-waktu dipelajari dalam model PAC bising tapi tidak dalam model SQ.$(\log(n) \log\log(n))$

Pertanyaan saya adalah ini:

Paritas (pada pertama variabel) yang dipelajari dalam model PAC bising tapi tidak dalam model SQ. Apakah ada kelas khusus lainnya, cukup berbeda dari paritas, yang diketahui dapat dipelajari dalam PAC berisik tetapi tidak dalam SQ?$(\log(n) \log\log(n))$

$d/\epsilon^2$$1/\epsilon$

$1/2-n^{-\epsilon}$