Jakieś klasy hipotez inne niż parzystość w hałaśliwym PAC, ale nie w SQ?

Angluin i Laird ('88) sformalizowali uczenie się z przypadkowo uszkodzonymi danymi w modelu „PAC z losowym szumem klasyfikacyjnym” (lub hałaśliwym PAC). Model ten jest podobny do PAC uczenia , z wyjątkiem etykiet z przykładów podanych w uczącej są uszkodzone (grzbiet), niezależnie w sposób losowy, z prawdopodobieństwem .$\eta < 1/2$

Aby pomóc scharakteryzować to, co jest do nauczenia się w hałaśliwym modelu PAC, Kearns ('93) wprowadzono do modelu zapytania statystyczne (SQ) dla uczenia się. W tym modelu uczeń może zapytać wyrocznię statystyczną o właściwości rozkładu docelowego i wykazał, że każda klasa, którą można się nauczyć SQ, można się nauczyć w hałaśliwym PAC. Kearns udowodnił również, że parytety na zmiennych nie można się nauczyć w czasie szybciej niż 2 n / c dla pewnej stałej c .$n$$2^{n/c}$$c$

Następnie Blum i in. ('00) oddzieliło zaszumiony PAC od SQ, pokazując, że parzystości w pierwszym są wielomianowe w czasie w modelu HAS, ale nie w modelu SQ.$(\log(n) \log\log(n))$

Moje pytanie brzmi:

Parzystości (w pierwszej zmiennej ) można odczytać w hałaśliwym modelu PAC, ale nie w modelu SQ. Czy są jakieś inne konkretne klasy, wystarczająco różniące się od parzystości, o których wiadomo, że można je nauczyć w hałaśliwym PAC, ale nie w SQ?$(\log(n) \log\log(n))$

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

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