Najgorsza liczba pytań potrzebna do nauczenia się monotonicznego orzeczenia nad zestawem

Rozważmy skończoną posetę ponad elementów, a nieznany monotoniczny predykat nad (tj. Dla dowolnego , , jeśli i to ) . Mogę ocenić , podając jeden węzeł i sprawdzając, czy utrzymuje, czy nie. Moim celem jest określenie dokładnie zestawu węzłów tak, że P (x) utrzymuje, przy użyciu jak najmniejszej liczby ocen P$(X, \leq)$$n$$P$$X$$x$$y \in X$$P(x)$$x \leq y$$P(y)$$P$$x \in X$$P(x)$$x \in X$$P(x)$$P$jak to możliwe. (Mogę wybrać moje zapytania w zależności od odpowiedzi na wszystkie poprzednie zapytania, nie muszę wcześniej planować wszystkich zapytań).

Strategia $S$ over $(X, \leq)$ to funkcja, która mówi mi, jako funkcję zapytań, które uruchomiłem do tej pory i ich odpowiedzi, który węzeł zapytać i który zapewnia to w dowolnym predykacie $P$ , postępując zgodnie ze strategią , Osiągnę stan, w którym znam wartość $P$ we wszystkich węzłach. Bieg czasu $r(S, P)$ z $S$ na predykatu $P$ jest liczbą zapytań muszą znać wartość $P$ na wszystkich węzłach. Najgorszy czas działania $S$ to $wr(S) = \max_P r(S, P)$ . Optymalna strategia $S'$ jest taka, że $wr(S') = \min_S wr(S)$ .

Moje pytanie brzmi: jak podać dane wejściowe $(X, \leq)$ , jak mogę określić najgorszy czas działania optymalnych strategii?

[Oczywiste jest, że dla pustego zestawu potrzebnych będzie $n$ zapytań (musimy zapytać o każdy pojedynczy węzeł) i że dla całkowitego zamówienia wokół $\lceil \log_2 n \rceil$ będą potrzebne zapytania (wyszukiwanie binarne w celu znalezienia granica). Bardziej ogólnym rezultatem jest następująca teoretyczna informacja dolna granica: liczba możliwych wyborów dla predykatu $P$ jest liczbą $N_X$ antychain $(X, \leq)$ (ponieważ istnieje odwzorowanie jeden do jednego między predykatami monotonicznymi i antichains interpretowane jako maksymalne elementy $P$ ), więc ponieważ każde zapytanie daje nam jeden bit informacji, potrzebujemy co najmniej $\lceil \log_2 N_X \rceil$zapytania, z uwzględnieniem dwóch poprzednich przypadków. Czy to jest ściśle związane, czy też są to pewne zestawy, których struktura jest taka, że ​​uczenie się może wymagać asymptotycznie więcej zapytań niż liczby antichains?]

To nie jest pełna odpowiedź, ale jest zbyt długo, aby być komentarzem.

Myślę, że znalazłem przykład, dla którego związany nie jest ciasny.$\lceil \log_2 N_X \rceil$

Rozważ następujący zestaw. Podstawą jest , a jest mniejsze niż dla wszystkich . Pozostałe pary są nieporównywalne. (Schemat Hassego to cykl).a i b j i , j ∈ { 1 , 2 } $X=\{a_1, a_2, b_1, b_2\}$$a_i$$b_j$$i,j\in\{1,2\}$$4$

Pozwól mi zidentyfikować właściwości monotoniczne ze zdenerwowaniem poety. Ten zestaw ma siedem ustawień: , , , , , , , a ten zestaw ma siedem antichains, ponieważ antichains są w korespondencji jeden-do-jednego z zaburzeniami. Więc dla tego zestawu.{ b 1 } { b 2 } { b 1 , b 2 } { a 1 , b 1 , b 2 } { a 2 , b 1 , b 2 } { a 1 , a 2 , b 1 , b 2 } ⌈ log 2 N X ⌉ = ⌈ log 2 7 $\emptyset$$\{b_1\}$$\{b_2\}$$\{b_1,b_2\}$$\{a_1,b_1,b_2\}$$\{a_2,b_1,b_2\}$$\{a_1,a_2,b_1,b_2\}$$\lceil \log_2 N_X \rceil=\lceil \log_2 7 \rceil = 3$

Teraz, argumentując przeciwnika, pokażę, że każda strategia wymaga co najmniej czterech zapytań (więc musi wysłać zapytanie do wszystkich elementów). Naprawmy dowolną strategię.

Jeśli strategia najpierw zapyta , wówczas przeciwnik odpowiada: „ się nie trzyma”. Pozostaje nam pięć możliwości: , , , , . Tak więc, aby ustalić, co się dzieje, potrzebujemy co najmniej więcej zapytań. W sumie potrzebujemy czterech zapytań. Ten sam argument ma zastosowanie, jeśli pierwsze zapytanie to . P ( a 1 ) ∅ { b 1 } { b 2 } { b 1 , b 2 } { a 2 , b 1 , b 2 } ⌈ log 2 5 ⌉ = 3 a $a_1$$P(a_1)$$\emptyset$$\{b_1\}$$\{b_2\}$$\{b_1,b_2\}$$\{a_2,b_1,b_2\}$$\lceil \log_2 5\rceil = 3$$a_2$

Jeśli strategia najpierw , wówczas przeciwnik odpowiada „ trzyma”. Następnie mamy pięć możliwości: , , , , . Dlatego potrzebujemy co najmniej trzech dodatkowych zapytań, jak poprzednio. W sumie potrzebujemy czterech zapytań. Ten sam argument ma zastosowanie, gdy pierwsze zapytanie to .$b_1$$P(b_1)$$\{b_1\}$$\{b_1,b_2\}$$\{a_1,b_1,b_2\}$$\{a_2,b_1,b_2\}$$\{a_1,a_2,b_1,b_2\}$$b_2$

Jeśli weźmiemy równoległych kopii tego zestawu, to ma on antichains, a zatem proponowane ograniczenie to . Ponieważ jednak każda kopia wymaga czterech zapytań, potrzebujemy co najmniej . Zapytań.$k$$7^k$$\lceil \log_2 7^k \rceil = 3k$$4k$

Prawdopodobnie istnieje większy zestaw z większą przerwą. Ale ten argument może jedynie poprawić współczynnik.

W tym przypadku problemem jest sytuacja, w której żadne zapytanie nie dzieli równomiernie przestrzeni wyszukiwania. W takim przypadku przeciwnik może zmusić większą połowę do pozostania.

W swoim artykule Każdy zestaw ma element centralny , liniowy i Saksa (Twierdzenie 1), że liczba zapytań potrzebnych do rozwiązania idealnego problemu identyfikacji w zestawie wynosi co najwyżej , gdzie a oznacza liczbę idei . To, co nazywają „ideałem”, jest w rzeczywistości niższym zestawem i istnieje oczywista zależność jeden do jednego między predykatami monotonicznymi a niższym zestawem punktów, w których nie utrzymują, poza ich „problemem identyfikacyjnym” jest identyfikacja poprzez zapytanie węzły tak jak w moim ustawieniu, więc myślę, że zajmują się problemem, który mnie interesuje i że$X$$K_0 \log_2 i(X)$$K_0 = 1/(2 - \log_2(1 + \log_2 5))$$i(X)$$X$$i(X) = N_X$.

Tak więc, zgodnie z ich wynikiem, dolna granica teoretycznej informacji jest ścisła do względnie małej stałej multiplikatywnej. To w zasadzie rozwiązuje pytanie o liczbę wymaganych pytań, w funkcji i do stałej multiplikatywnej: jest to między a .$N_X$$\log_2 N_X$$K_0 \log_2 N_X$

Linial i Saks cytują osobistą komunikację Shearera, aby powiedzieć, że istnieją znane zamówienia, dla których możemy udowodnić dolną granicę dla niektórych która jest tylko nieco mniejsza niż (jest to w duchu odpowiedzi Yoshio Okamoto, kto: wypróbowałem to podejście dla mniejszej wartości ).$K_1 \log_2 N_X$$K_1$$K_0$$K_1$

To nie w pełni odpowiada na moje pytanie dotyczące obliczenia liczby pytań wymaganych od , jednak ponieważ obliczenie z jest zakończone # P , mam wrażenie, że nie ma nadziei. (Komentarze na ten temat są mile widziane.) Mimo to ten wynik Linial i Saksa jest pouczający.$X$$N_X$$X$

Dla logicznej n-kostki (lub, równoważnie, dla zestawu wszystkich podzbiorów zestawu n-elementów), odpowiedź brzmi: podane przez twierdzenia Korobkowa i Jaśla (odpowiednio z 1963 i 1966 r.). Twierdzenie Hansela [1] stwierdza, że ​​nieznanej monotonicznej funkcji boolowskiej (tj. Nieznanego predykatu monotonicznego na tym zestawie) można się nauczyć za pomocą algorytmu deterministycznego co najwyżej zapytań (czyli w najgorszym przypadku zadaje pytania ). Algorytm ten odpowiada dolnej granicy twierdzenia Korobkowa [2], które mówi, że$(\{0, 1\}^n, \leq)$$(2^S, \subseteq)$$\phi(n) = \binom{n}{\lfloor n/2 \rfloor} + \binom{n}{\lfloor n/2 \rfloor + 1}$$\phi(n)$$\phi(n) - 1$zapytania nie wystarczą. (Tak więc algorytm Hansela jest optymalny w najgorszym przypadku.) Algorytm w obu instrukcjach jest rozumiany jako deterministyczne drzewo decyzyjne.

Logarytm liczby antichains w jest asymptotycznie równy , więc istnieje różnica współczynnika między a optymalną wydajnością algorytmu dla tego zestawu.$(\{0, 1\}^n, \le)$$\binom{n}{\lfloor n/2 \rfloor} \sim 2^n / \sqrt{\pi n / 2}$$\log N_X$$\phi(n) \sim 2 \binom{n}{\lfloor n/2 \rfloor}$

Niestety nie udało mi się znaleźć w Internecie dobrego traktowania algorytmu Jaśla w języku angielskim. Opiera się na lemacie, który dzieli n-kostkę na łańcuchy o specjalnych właściwościach. Niektóre opisy można znaleźć w [3]. Jeśli chodzi o dolną granicę, nie znam żadnego odniesienia do opisu w języku angielskim.$\phi(n)$

Ponieważ jestem zaznajomiony z tymi wynikami, mogę zamieścić opis na arXiv, jeśli leczenie w pracy Kovalerchuka nie jest wystarczające.

Jeśli się nie mylę, podjęto próby uogólnienia podejścia Jaśla, przynajmniej do posetu , gdzie to łańcuch , chociaż nie mogę od razu podać żadnego odniesienia. W przypadku boolowskim ludzie badali także pojęcia złożoności inne niż najgorsze w przypadku tego problemu.$(E_k^n, \le)$$(E_k, \le)$$0 < 1 < \ldots < k - 1$

[1] G. Hansel, Sur le nombre des fonctions booléennes monotones de n zmiennych. CR Acad. Sci. Paris, 262 (20), 1088-1090 (1966)

[2] VK Korobkov. Szacowanie liczby funkcji monotonicznych algebry logiki i złożoności algorytmu do znajdowania zbioru rezolwentów dla dowolnej funkcji monotonicznej algebry logiki. Radziecka matematyka. Doklady 4, 753-756 (1963) (tłumaczenie z rosyjskiego)

[3] B. Kovalerchuk, E. Triantaphyllou, AS Deshpande, E. Vityaev. Interaktywne uczenie monotonicznych funkcji boolowskich. Information Sciences 94 (1), 87-118 (1996) ( link )

[ UWAGA: Poniższy argument nie działa, ale zostawiam go tutaj, aby inni nie popełnili tego samego błędu / na wypadek, gdyby ktoś mógł go naprawić. Problem polega na tym, że wykładnicza dolna granica uczenia się / identyfikowania funkcji monotonicznej, jak poniżej, niekoniecznie jest sprzeczna z algorytmem przyrostowo wielomianowym dla problemu. I ta ostatnia jest równoważna sprawdzeniu wzajemności dualności dwóch funkcji monotonicznych w czasie wieloczłonowym.]

Uważam, że twoje przypuszczenie dotyczące jest ogólnie fałszywe. Jeśli rzeczywiście jest tak , że potrzebne są zapytania log N X , oznacza to dość silną dolną granicę uczenia się funkcji monotonicznych przy użyciu zapytań członkowskich . W szczególności, niech poset X jest logiczna modułu ze zwykłymi kolejności (jeśli chce, X jest PowerSet z { 1 , . . . , N } z ⊆ jako częściowe kolejności). Liczba M maksymalnych antichains w X spełnia log M $\log N_X$$\log N_X$$X$$X$$\{1,...,n\}$$\subseteq$$M$$X$ [1]. Jeśli twój pomysł nalogNXjest poprawny, to istnieje predykat monotoniczny naX,który wymaga zasadniczo ( n-$\log M = (1 + o(1))\binom{n-1}{\lfloor n/2 \rfloor}$$\log N_X$$X$zapytań. W szczególności implikuje to dolną granicę zasadniczo2ndla złożoności dowolnego algorytmu rozwiązującego ten problem.$\binom{n-1}{n/2} \approx 2^n$$2^n$

Jednak, jeśli dobrze zrozumiałem [ czego teraz nie wiem ], twój problem jest równoznaczny ze sprawdzeniem wzajemności dualności dwóch funkcji monotonicznych, co można zrobić w quasi-wielomianowym czasie (patrz wprowadzenie do tego artykułu przez Bioch i Ibaraki , które cytują Fredmana i Khachiyana), co jest sprzeczne z czymkolwiek zbliżonym do dolnej granicy .$2^n$

[1] Liviu Ilinca i Jeff Kahn. Liczenie maksymalnych antichains i niezależnych zestawów . arXiv: 1202,4427