Randomize or Not?

To pytanie jest inspirowane koszulką Georgia Tech Al Algorytmy i Randomness Center , która pyta „Randomize or not ?!”

Istnieje wiele przykładów, w których randomizacja pomaga, szczególnie podczas działania w środowiskach przeciwnych. Istnieją również ustawienia, w których losowanie nie pomaga ani nie boli. Moje pytanie brzmi:

Jakie są ustawienia, kiedy losowanie (w jakiś pozornie rozsądny sposób) faktycznie boli?

Nie krępuj się definiować „ustawień” i „boli” w szerokim zakresie, czy to pod względem złożoności problemu, możliwych do udowodnienia gwarancji, współczynników aproksymacyjnych czy czasu działania (spodziewam się, że czas działania będzie zawierał bardziej oczywiste odpowiedzi). Im ciekawszy przykład, tym lepiej!

randomness big-picture randomized-algorithms Lew Reyzin
źródło

Doceniony. To pytanie wydaje mi się pytaniem o retorykę, ponieważ wydaje się, że w centrum uwagi znajduje się sposób argumentowania, że konkretny fakt można nazwać „losowymi ranami”.

Tsuyoshi Ito,

Słusznie. Ale dam wam przykład tego, co miałem na myśli. Powiedzmy, że mamy algorytm uczenia się, który ma działania, które może podjąć, i na etapie uczenia się omija je. Załóżmy, że ma jakąś gwarancję. Załóżmy, że zamiast tego rozważamy losowe ujednolicenie działań i stwierdzimy, że gwarancja została utracona. Trudno argumentować, że nie jest to przypadek losowego „ranienia”. I nie krępuj się zdefiniować „boli” dla siebie! Chociaż może to być częścią twojej krytyki ...

Lew Reyzin

niech się rozegra: może przeprowadzimy ciekawą dyskusję. Znam co najmniej jeden przypadek, w którym prosta randomizowana strategia jest w rzeczywistości gorsza niż ostrożny deterministyczny algorytm

Suresh Venkat

Powodem, dla którego nie podoba mi się to pytanie, jest powiedziane prawdopodobnie dlatego, że oczekuję, że większość głosowanych odpowiedzi będzie „interesujących” tylko w ich interpretacji pytania. Pytanie wydaje się zachęcać do twórczych i retorycznych interpretacji. Jeśli nie tego chcesz i możesz wymyślić lepszy sposób sformułowania pytania, popraw je (ale nie mogę wymyślić żadnego).

Tsuyoshi Ito,

Eek Nie spodziewałem się, że to pytanie będzie tak kontrowersyjne :) W każdym razie nie mam nic przeciwko interesującym interpretacjom! Myślę, że w tym przypadku będziemy musieli się nie zgodzić. Btw, jeśli niejasność pytania jest uciążliwa, zupełnie nie mam nic przeciwko @Suresh, dzięki czemu jest CW ...

Lev Reyzin

Odpowiedzi:

Oto prosty przykład z teorii gier. W grach, w których istnieją zarówno czyste, jak i mieszane równowagi Nasha, mieszane są często znacznie mniej naturalne i znacznie „gorsze”.

$\log(n)/\log\log(n)$

Wiadomość na wynos: randomizacja może zaszkodzić koordynacji.

Aaron Roth
źródło

fajnie - podoba mi się ta interpretacja piłek i koszy jako gry dwuosobowej. Oto odpowiedź, o której myślałem!

Lew Reyzin

Czasami jest dyskutowany w swojej ukrytej formie jako „gra równoważenia obciążenia na identycznych komputerach” :-)

Aaron Roth

Oto prosty przykład z dziedziny algorytmów rozproszonych.

Zazwyczaj przypadkowość bardzo pomaga. Randomizowane algorytmy rozproszone są często łatwiejsze do zaprojektowania i są szybsze.

Jeśli jednak masz szybki deterministyczny algorytm rozproszony, możesz mechanicznie przekonwertować go [ 1 , 2 ] na szybki algorytm samostabilizujący się . Zasadniczo otrzymasz bardzo silną wersję odporności na uszkodzenia za darmo (przynajmniej jeśli wąskim gardłem jest liczba rund komunikacji). Możesz uprościć projektowanie algorytmu, koncentrując się na bezbłędnych synchronicznych sieciach statycznych, a konwersja da Ci odporny na błędy algorytm, który może obsługiwać asynchroniczne sieci dynamiczne.

Ogólnie taka konwersja nie jest znana w przypadku randomizowanych algorytmów rozproszonych.

Jukka Suomela
źródło

Pozwól mi najpierw wprowadzić problem dotyczący losowości:

Czy we wszechświecie istnieje przypadkowość, czy wszystko jest deterministyczne?

To pytanie filozoficzne jest zarówno kontrowersyjne, jak i niezwiązane z kontekstem tutaj. Użyłem go jednak jako ostrzeżenia, ponieważ nadchodząca odpowiedź będzie kontrowersyjna, jeśli ktoś zagłębi się zbyt głęboko w powyższe pytanie.

Twierdzenie Shannona – Hartleya opisuje pojemność kanału komunikacyjnego w obecności hałasu. Szum zmienia się z 0 na 1 i odwrotnie, z pewnym z góry określonym prawdopodobieństwem.

Gdyby kanał zachowywał się w sposób deterministyczny --- To znaczy, gdybyśmy mogli modelować szum w taki sposób, abyśmy byli w stanie określić, które bity by się zmieniły --- Pojemność kanału byłaby nieskończenie duża. Bardzo pożądane!

Lubię analogizować losowość do tarcia: przeciwstawia się ruchowi, ale ruch bez niego jest niemożliwy.

MS Dousti
źródło