Znajdź przybliżony argmax, używając tylko przybliżonych maksymalnych zapytań

10

Rozważ następujący problem.

nv1,,vnRS{1,,n}maxiSvi

Ten problem jest prosty: możemy użyć wyszukiwania binarnego, aby znaleźć argmax z zapytaniami . tj. Zbuduj kompletne drzewo binarne z liści odpowiadających indeksom. Zacznij od korzenia i zejdź do liścia w następujący sposób. W każdym węźle zapytaj o maksymalną wartość w prawym i lewym poddrzewie, a następnie przejdź do strony podrzędnej z większą odpowiedzią. Po osiągnięciu liścia wypisz jego indeks.O(logn)n

W moich badaniach pojawiła się następująca głośna wersja tego problemu.

Istnieje nieznanych wartości . Można do nich uzyskać dostęp za pomocą zapytań, w których określono zestaw i próbkę z . Celem jest zidentyfikowanie taki sposób, aby przy użyciu jak najmniejszej liczby zapytań. (Oczekiwanie jest niż wybór , który zależy zarówno od monet algorytmu, jak i od hałaśliwych odpowiedzi na zapytania).nv1,,vnS{1,,n}N(maxiSvi,1)i{1,,n}E[vi]maxivi1i

Załóżmy, że próbujemy rozwiązać ten problem przy użyciu tej samej strategii wyszukiwania binarnego, co wcześniej (ale z głośnymi odpowiedziami). łatwo można wykazać, że osiąga to i że jest to w najgorszym przypadku. Możemy zredukować błąd do pożądanego , powtarzając każde zapytanie razy i używając średniej (która zmniejsza wariancję). Daje to algorytm wykorzystujący zapytania .E[vi]maxiviO(logn)1O(log2n)O(log3n)

Czy istnieje lepszy algorytm? Przypuszczam, że zapytania wystarczające. I wierzę, że mogę udowodnić dolną granicę . Problem staje się również łatwy - tzn. Zapytania poprzez wyszukiwanie binarne - pod obietnicą, że istnieje różnica między największą wartością a drugą co do wielkości wartością. Jeśli to pomoże, możesz założyć, że wszystkie wartości mieszczą się w zakresie od do .O(log2n)Ω(log2n)O~(logn)Ω(1)0O(logn)

Tomasz
źródło
Co z wyszukiwaniem binarnym, które na każdym poziomie tworzy pary zapytań O (log n) (jedna dla maks. Lewej strony, druga dla maks. Prawej strony) i zapisuje, kto wygrywa. Następnie po rundach O (log n) algorytm postępuje rekurencyjnie po stronie, która „wygrała” najwięcej razy. Krótka kalkulacja w mojej głowie zdawała się wskazywać, że zadziałało to z prawdopodobieństwem w ustawieniu, w którym jedno wejście to a wszystkie inne są ... ale może być daleko. 11/nc20
daniello
@daniello Działa, gdy istnieje różnica między największymi a drugimi co do wielkości wartościami. Ogólny przypadek wydaje się jednak trudniejszy.
Thomas
uwaga do siebie: przeczytaj całe pytanie przed komentarzem
daniello

Odpowiedzi:

1

Rozszerzony komentarz pomysłu lub dwóch w kierunku dolnej granicy. Niech , powiedzmy (chociaż najlepszy wybór może być inny) i niech . Rozważ narysowanie danych wejściowych, wybierając losowo permutację tych wartości.B=Θ(logn){v1,,vn}={1nB,,n1nB,B}

Pomysł powinien polegać na tym, że jeśli naprawimy wskaźniki wszystkich wartości z wyjątkiem wartości i , wówczas powinniśmy być w stanie pokazać różnicę w prawdopodobieństwie wyboru jednego algorytmu względem drugiego bardzo mała: odległość wariancji między wynikami zapytań algorytmów jest bardzo mała, biorąc pod uwagę rozkład 50-50 przypisań tych wartości do dwóch dostępnych wskaźników oraz wyniki dowolnej sekwencji zapytań.Bn1nB

Ten argument dotyczy każdej pary sąsiednich wartości, więc otrzymujemy łańcuch ograniczeń prawdopodobieństwa, że ​​algorytm wybierze najwyższe, drugie co do wielkości, ... wartości. Daje to górną granicę oczekiwanej wartości algorytmu, więc ustawiamy tę górną granicę na i sprawdzamy, jaka liczba zapytań musi być.B1

Nie mogłem jeszcze ulepszyć z powyższym podejściem, ale myślę, że możesz dostać jeśli możesz wykorzystać fakt, że zapytania nie mogą pomóc w wielu krokach na raz. To znaczy, jeśli zapytanie zmienia się, gdy przenosimy najwyższą wartość do innego indeksu, to jeden z tych przypadków nie zmienia się, gdy przenosimy dowolną inną wartość do innego indeksu.logn(logn)2

Różnicowa prywatność może być pomocna w jednym z tych kroków, np. Jeśli pomyślimy tylko o przypadku, w którym zamienimy lokalizację dwóch najwyższych wartości, „czułość” tego zapytania jest po prostu a następnie zaawansowana kompozycja może być pomocna.Bn

Przykro mi, ale jest na wpół upieczony, ale mam nadzieję, że może się przydać!

usul
źródło
Tak naprawdę nie myślałem o dolnych granicach, ponieważ liczę na górną granicę. :) utrzymuje się nawet w bezszumowej obudowie. Myślę, że powinniśmy być w stanie udowodnić dolną granicę . Ω(logn)Ω(log2n)
Thomas
OK. Mam szkic dolnej granicy , ale jest to trochę skomplikowane. Ω(log2n)
Thomas