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

15

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 .) $1/\gamma^C = \log |C| = k$ $\Omega(k)$ $O(k^2)$ $\Omega(k)$ $O(k^2)$

reference-request machine-learning lg.learning

— Robin Kothari
źródło

1

„Wymiar stogu siana” charakteryzuje złożoność zapytań związanych z optymalizacją funkcji: cis.upenn.edu/~mkearns/papers/haystack.pdf , To jest inne niż chcesz, ale możesz cieszyć się powiązaną pracą, która omawia to, co wiadomo o charakteryzowaniu złożoność zapytania dokładnego uczenia się.

— Aaron Roth,

6

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.

— anonimowa gęś
źródło

1

Dzięki! Poszukiwanie wymiaru nauczania doprowadziło mnie do rozszerzonego wymiaru nauczania, który jest podobny do parametru kombinatorycznego, o którym wspomniałem w pytaniu, i który następnie doprowadził mnie do wielu innych interesujących artykułów na ten temat.

— Robin Kothari,

4

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).

— anonimowy łoś
źródło

1

Dzięki za odpowiedzi. Nawet jeśli prawdą jest, że prawie wszystkie klasy koncepcyjne (przy pewnym rozsądnym podziale na klasy) są trudne do nauczenia, niektóre klasy są łatwe do nauczenia się i byłoby interesujące mieć kombinatoryczny parametr, który to charakteryzuje. Nie mam nic przeciwko, jeśli parametr jest trudny do obliczenia. Nawet wymiar VC nie jest efektywnie obliczalny.

— Robin Kothari,

1

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 . Zestaw elementów jest nazywany zbiorze uczącym na koncepcji jeśli jest jedyną koncepcją zgodne z . $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$

— seteropere
źródło

f

$f$

f

$f$

f

$f$

@RobinKothari TD dolna granica minimalnej liczby zapytań w dowolnym algorytmie MQ. W praktyce może nie istnieć algorytm, który ślepo osiąga tę granicę bez oszukiwania i sztuczek w kodzie. W artykule „Queries Revisited” Angluin omówiła parametr o nazwie MQ, który reprezentuje liczbę zapytań potrzebnych przez najlepszy algorytm MQ w najgorszym przypadku. Nie pamiętam jego szczegółów, ale na pewno TD <= MQ.

— seteropere

1

To, co mnie interesowało (kiedy zadałem to pytanie), to parametr charakteryzujący dokładne uczenie się za pomocą zapytań członkowskich. Powinien być zarówno górną, jak i dolną granicą. W pytaniu podałem przykład parametru, który to osiąga (do współczynnika log | C |). Moje pytanie dotyczyło tego, czy wiadomo coś lepszego.

— Robin Kothari,