Kombinatoryczna charakterystyka nauki ścisłej z zapytaniami członkowskimi

Edycja: Ponieważ od tygodnia nie otrzymałem żadnych odpowiedzi / komentarzy, chciałbym dodać, że cieszę się, że słyszę cokolwiek o problemie. Nie pracuję w okolicy, więc nawet jeśli jest to prosta obserwacja, mogę tego nie wiedzieć. Pomocny byłby nawet komentarz typu „Pracuję w okolicy, ale nie widziałem takiej charakterystyki”!

Tło:

Istnieje kilka dobrze zbadanych modeli uczenia się w teorii uczenia się (np. Nauka PAC, nauka online, nauka dokładna z pytaniami dotyczącymi członkostwa / równoważności).

Na przykład w uczeniu się PAC złożoność przykładowa klasy koncepcyjnej ma niezłą kombinatoryczną charakterystykę pod względem wymiaru klasy VC. Jeśli więc chcemy nauczyć się klasy ze stałą dokładnością i pewnością, można to zrobić za pomocą próbek , gdzie jest wymiarem VC. (Zauważ, że mówimy o złożoności próbki, a nie o złożoności czasowej.) Istnieje również bardziej wyrafinowana charakterystyka pod względem dokładności i pewności. Podobnie, związany z błędami model uczenia się online ma ładną kombinatoryczną charakterystykę.$\Theta(d)$$d$

Pytanie:

Chcę wiedzieć, czy podobny model jest znany z modelu dokładnej nauki z zapytaniami o członkostwo. Model jest zdefiniowany w następujący sposób: Mamy dostęp do czarnej skrzynki, która na wejściu daje ci . Wiemy pochodzi z jakiejś klasy pojęcie . Chcemy określić przy jak najmniejszej liczbie zapytań.$x$$f(x)$$f$$C$$f$

Czy istnieje parametr kombinatoryczny klasy koncepcyjnej który charakteryzuje liczbę zapytań potrzebnych do nauczenia się koncepcji w modelu nauki ścisłej z zapytaniami członkostwa?$C$

Co wiem:

Najlepszą taką charakterystykę, jaką znalazłem, znajduje się w tym artykule Servedio i Gortlera , używając parametru, który przypisują Bshouty, Cleve, Gavaldà, Kannan i Tamon . Definiują parametr kombinatoryczny o nazwie , gdzie jest klasą koncepcji, która ma następujące właściwości. (Niech będzie optymalną liczbą zapytań potrzebnych do nauki języka w tym modelu).$\gamma^C$$C$$Q_C$$C$

$Q_C = \Omega(1/\gamma^C)\qquad Q_C = \Omega(\log |C|) \qquad Q_C = O(\log |C|/\gamma^C)$

Ta charakterystyka jest prawie ścisła. Jednak może istnieć kwadratowa przerwa między górną i dolną granicą. Na przykład, jeśli , wówczas dolna granica to , ale górna granica to . (Myślę również, że ta luka jest możliwa do osiągnięcia, tzn. Istnieje klasa koncepcji, dla której obie dolne granice to , ale górna granica to .)Ω ( k ) O ( k 2 ) Ω ( k ) O ( k 2$1/\gamma^C = \log |C| = k$$\Omega(k)$$O(k^2)$$\Omega(k)$$O(k^2)$

Aby wprowadzić do domu punkt anonimowego łosia, rozważ klasę koncepcyjną, która składa się z funkcji, które generują 1 tylko w jednym punkcie w {0,1} ^ n. Klasa ma rozmiar 2 ^ n, aw najgorszym przypadku potrzebne są 2 ^ n zapytania. Spójrz na najgorszy przypadek nauczania (Goldman & Schapire), który zapewnia coś podobnego do tego, czego szukasz.

Nie znam takiej charakterystyki. Warto jednak zauważyć, że w przypadku prawie każdej klasy koncepcyjnej należy sprawdzić wszystkie punkty. Aby to zobaczyć, rozważ klasę koncepcji, która składa się ze wszystkich n-wymiarowych wektorów boolowskich o wadze Hamminga 1. Ta klasa koncepcji oczywiście wymaga nauki n zapytań, co jest równe jej liczności. Prawdopodobnie możesz uogólnić to spostrzeżenie, aby uzyskać, że prawie każda klasa koncepcji wymaga również wykonania wszystkich zapytań.

Podejrzewam, że biorąc pod uwagę dane wejściowe klasy koncepcyjnej C, trudne jest określenie złożoności dokładnego uczenia się klasy koncepcyjnej za pomocą zapytań członkowskich, a nawet przybliżenie jej do wartości stałej. Dałoby to pewne wskazówki, że „dobra” charakterystyka kombinatoryczna nie istnieje. Jeśli chcesz udowodnić taki wynik twardości NP, ale spróbuj i nie opublikuj tutaj, zobaczę, czy uda mi się to rozgryźć (mam kilka pomysłów).

Chociaż inni wskazali odpowiedź. Pomyślałem, że mogę zrobić to samowystarczalnym i pokazać, dlaczego odpowiedzią jest wymiar nauczania .

Rozważmy pojęcie klasy nad wejściem przestrzeni X . Zestaw elementów S ⊆ X jest nazywany zbiorze uczącym na koncepcji f jeśli f jest jedyną koncepcją C zgodne z S .$C$$X$$S\subseteq X$$f$$f$$C$$S$

$\mathcal{T}(f)$$f$$(f,C)=min\{\ |S|\ | \ S\in \mathcal{T}(f) \}$$f$$_{min}(f)$$\mathcal{T}(f)$$(C)=$$_{f\in C}$$(f,C)$$C$

$f$$(f,C)$$_{min}(f)$$(C)$$f$