Złożoność obliczeniowych zapytań w uczeniu się SQ

Wiadomo, że do uczenia się PAC istnieją naturalne klasy pojęć (np. Podzbiory list decyzji), w których występują wielomianowe luki między złożonością próby potrzebną do teoretycznego uczenia się informacji przez uczonego bez ograniczeń obliczeniowych a złożonością próby potrzebną przez wielomian uczący się czasu. (patrz np. http://portal.acm.org/citation.cfm?id=267489&dl=GUIDE lub http://portal.acm.org/citation.cfm?id=301437 )

Wyniki te wydają się jednak zależeć od zakodowania sekretu w poszczególnych przykładach, a zatem nie przekładają się naturalnie na model uczenia się w SQ, w którym uczeń po prostu pyta o właściwości statystyczne rozkładu.

Czy wiadomo, czy istnieją klasy koncepcyjne, dla których uczenie teoretyczne w modelu SQ jest możliwe przy zapytaniach O (f (n)), ale uczenie się wydajne obliczeniowo jest możliwe tylko przy zapytaniach Omega (g (n)) dla g (n ) >> f (n)?

Zadałem sobie to pytanie jakiś czas temu. Przynajmniej do uczenia się w odniesieniu do konkretnego rozkładu istnieje dość prosty przykład klasy koncepcyjnej, która jest teoretycznie możliwa do nauczenia w SQ, ale trudna do nauczenia w NP. Niech \ phi binarne kodowanie instancji SAT, a y będzie jej pierwszym zadawaniem leksykograficznym (lub 0 ^ n jest instancją niezadowalającą). Teraz niech f (\ phi) będzie funkcją, że ponad połowa domeny to MAJ (\ phi), a ponad druga połowa domeny jest równa PAR (y). Tutaj MAJ jest funkcją większości nad zmiennymi, które są ustawione na 1 w ciągu \ phi, a PAR (y) jest funkcją parzystości nad zmiennymi, które są ustawione na 1 w ciągu y. Niech F będzie klasą funkcji uzyskanych w ten sposób. Aby SQ nauczyć się F przez rozkład równomierny U wystarczy nauczyć się większości (co jest łatwe), aby znaleźć \ phi, a następnie znaleźć y. Z drugiej strony dość łatwo jest zredukować uczenie się F przez SAT do SQ (do dowolnej dokładności zauważalnie większej niż 3/4) w całym rozkładzie równomiernym. Powodem tego jest oczywiście to, że parytety są zasadniczo „niewidoczne” dla SQ, a zatem konieczne jest rozwiązanie SAT, aby nauczyć się F.

To miłe pytanie. Mocą statystycznego modelu zapytań jest właśnie zdolność do udowodnienia bezwarunkowych dolnych granic uczenia się za pomocą SQ - na przykład, parzystości nie można się nauczyć przy zapytaniach statystycznych o liczbie wielomianowej.

Nie znam wyników formularza, o który pytasz, ale być może brakuje nam czegoś oczywistego ...