Prawidłowa nauka PAC 2-DNF w jednolitym rozkładzie

Jaki jest najnowszy wynik w zakresie złożoności zapytań dotyczących prawidłowych formuł uczenia się PAC 2-DNF z przykładowymi zapytaniami i w jednolitym rozkładzie ? A może jakieś nietrywialne ograniczenia?

Ponieważ w ogóle nie znam teorii uczenia się, a to pytanie jest motywowane inną dziedziną, odpowiedź może być oczywista. Sprawdziłem książkę Kearnsa i Vazirani, ale wydaje się, że nie biorą pod uwagę tego ustawienia.

aktualiz. Chociaż głównym parametrem będącym przedmiotem zainteresowania jest złożoność zapytań, ważny jest również czas działania. Jeśli to możliwe, czas pracy powinien najlepiej być mniej więcej taki sam jak złożoność zapytań lub co najwyżej wielomian.

aktualiz. Dodatek B (góra strony 18) artykułu „Uczenie się funkcji podmodularnych” autorstwa Balcana i Harveya wspomina, że ​​„dobrze wiadomo, że 2-DNF skutecznie można nauczyć się PAC”. Nie wspominają jednak o tym, czy ten wynik służy poprawnemu uczeniu się, czy zawierają jakieś odniesienia.

Nie wiem, czy uznasz to za nietrywialne podejście, ale proszę bardzo.

Po pierwsze, aby było jasne, abyśmy się nie mylili $c$-DNF z $k$-term DNF (co często robię), an $c$Formuła -DNF nad zmiennymi $x_1, \ldots, x_n$ ma formę $\vee_{i=1}^{k}(\ell_{i,1} \wedge \ell_{i,2} ... \ell_{i,c})$ gdzie $\forall 1 \le i \le k$ i $1 \le j \le c$, $\ell_{i,j} \in \{x_1, \ldots, x_n, \bar{x}_1, \ldots, \bar{x}_n \}$.

Możemy najpierw zapytać, ile różnych terminów może istnieć w $c$-DNF. Każdy termin będzie miał$c$ z $n$zmienne, każda zanegowana lub nie - co dla różnych możliwych terminów. W instancji 2-DNF każdy termin pojawi się albo nie, co oznacza możliwe „cele”, gdzie to przestrzeń hipotez.$2^c\binom{n}{c}$$|\mathcal{H}| = 2^{2^c\binom{n}{c}}$$\mathcal{H}$

Wyobraź sobie algorytm, który pobiera próbek, a następnie wypróbowuje wszystkiehipotez, dopóki nie znajdzie takiej, która doskonale przewiduje na próbkach. Twierdzenie Brzytwy Ockhama mówi, że wystarczy pobrać około próbek, aby znaleźć algorytm cel z błędem$m$$|\mathcal{H}|$$m = O(\frac{1}{\epsilon}|(\mathcal{H}|+\frac{1}{\delta})$$\le \epsilon$ z prawdopodobieństwem .$\ge 1-\delta$

W tym przypadku, dla , , co oznacza, że ​​będziesz potrzebować$c=2$$\lg|\mathcal{H}| = O(n^2)$$n^2$ próbek do (właściwego) uczenia się.

Ale cała gra w uczeniu się nie jest tak naprawdę próbką złożoności (choć jest to część gry, szczególnie w uczeniu się wydajnym atrybutami), ale raczej w próbie zaprojektowania algorytmów czasu wielomianowego. Jeśli nie zależy ci na wydajności, to$n^2$ jest najprostszą odpowiedzią na złożoność próbki PAC.

AKTUALIZACJA (ze względu na zmienione pytanie) :

Ponieważ wyraźnie stwierdziłeś, że zależy Ci tylko na złożoności próbki, przedstawiłem algorytm Occam Brute-Force, który jest prawdopodobnie najprostszym argumentem. Jednak moja odpowiedź była nieco nieśmiała. -DNF są faktycznie możliwe do nauczenia się w czasie wielomianowym! Jest to wynik oryginalnej pracy Valianta „ A Theory of the Learnable ”. W rzeczywistości -DNF można się nauczyć dla dowolnego .$2$$c$$c = O(1)$

Argument jest następujący. Możesz zobaczyć -DNF jako rozłączenie „meta-zmiennych” i spróbować nauczyć się tego rozłączenia, eliminując meta-zmienne niezgodne z przykładami. Takie rozwiązanie można łatwo przetłumaczyć z powrotem na „właściwe” rozwiązanie i zajmuje czasu. Na marginesie, wciąż pozostaje otwarte, czy istnieje algorytm czasu wielomianowego dla$c$$\approx n^c$$O(n^c)$$c = \omega(1)$ .

Jeśli chodzi o to, czy złożoność próbki jest również dolną granicą, odpowiedź jest prawie tak. Ten artykuł autorstwa Ehrenfeucht i in. pokazuje, że granica Occam jest prawie ciasna.$n^2$