Rozważ następujący problem.
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.
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).
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 .
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 .
źródło
Odpowiedzi:
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,…,n−1nB,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ń.B n−1nB
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ć.B−1
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ć!
źródło