Uzasadnianie naukowcom asymptotycznej analizy najgorszego przypadku

22

Pracowałem nad wprowadzeniem niektórych wyników złożoności obliczeniowej do biologii teoretycznej, zwłaszcza ewolucji i ekologii , aby być interesującym / użytecznym dla biologów. Jedną z największych trudności, jakie napotkałem, jest uzasadnienie przydatności asymptotycznej analizy najgorszego przypadku dla dolnych granic. Czy istnieją odniesienia do długości artykułów, które uzasadniają dolne granice i asymptotyczną analizę najgorszego przypadku dla odbiorców naukowych?

Naprawdę szukam dobrego odniesienia, do którego mógłbym się odnieść w swoim piśmie, zamiast konieczności przechodzenia przez uzasadnienia w ograniczonej przestrzeni, jaką mam dostępną (ponieważ nie jest to centralny punkt artykułu). Zdaję sobie również sprawę z innych rodzajów i modeli analizy, więc ja nie szukam odniesienia, który mówi najgorszy przypadek jest „najlepszy” analiza (ponieważ istnieją ustawienia kiedy bardzo dużo nie jest), ale że nie jest całkowicie bezużyteczne: wciąż daje nam teoretycznie użyteczny wgląd w zachowanie rzeczywistych algorytmów na rzeczywistych danych wejściowych. Ważne jest również, aby pisanie było skierowane do ogólnych naukowców a nie tylko inżynierowie, matematycy lub informatycy.

Na przykład esej Tima Roughgarden'a przedstawiający ekonomistom teorię złożoności jest na dobrej drodze do tego, czego chcę. Jednak istotne są tylko sekcje 1 i 2 (reszta jest zbyt specyficzna ekonomicznie), a docelowi odbiorcy są nieco bardziej zadowoleni z myślenia odpornego na twierdzenia lematyczne niż większość naukowców [1] .


Detale

W kontekście dynamiki adaptacyjnej w ewolucji spotkałem dwa specyficzne typy odporności biologów teoretycznych:

[A] „Dlaczego miałbym przejmować się zachowaniem dla dowolnego ? Wiem już, że genom ma n = 3 10 9 par zasad (a może n = 2 10 4 genów) i nie więcej.”nn=3109n=2104

Jest to stosunkowo łatwe do wytarcia z argumentem „możemy sobie wyobrazić czekanie na sekund, ale nie na 2 10 9 ”. Ale bardziej skomplikowany argument może brzmieć: „jasne, mówisz, że zależy ci tylko na konkretnym n , ale twoje teorie nigdy nie wykorzystują tego faktu, po prostu używają tego, że jest duży, ale skończony, i to jest twoja teoria, z którą studiujemy analiza asymptotyczna ”.1092109n

[B] „Ale pokazałeś tylko, że budowanie tego specyficznego krajobrazu za pomocą tych gadżetów jest trudne. Dlaczego miałbym się tym przejmować zamiast przeciętnego?”

Jest to trudniejsza krytyka, ponieważ wiele narzędzi powszechnie używanych w tej dziedzinie pochodzi z fizyki statystycznej, w której często bezpiecznie jest założyć jednolity (lub inny konkretny prosty) rozkład. Ale biologia to „fizyka z historią” i prawie wszystko nie jest w równowadze lub „typowe”, a wiedza empiryczna jest niewystarczającauzasadnić założenia dotyczące rozkładów nad danymi wejściowymi. Innymi słowy, chcę argumentu podobnego do argumentu zastosowanego przeciwko jednolitej analizie średnich przypadków w analizie średnich dystrybucji w inżynierii oprogramowania: „modelujemy algorytm, nie możemy skonstruować rozsądnego modelu interakcji użytkownika z algorytmem lub jego dystrybucji wejściowe będą; dotyczy to psychologów lub użytkowników końcowych, a nie nas ”. Z wyjątkiem tego przypadku, nauka nie znajduje się w sytuacji, w której istnieje odpowiednik „psychologów lub użytkowników końcowych”, aby dowiedzieć się, jakie są podstawowe dystrybucje (lub jeśli jest to nawet znaczące).

Uwagi i powiązane pytania

  1. Link omawia nauki kognitywne, ale sposób myślenia jest podobny w biologii. Jeśli przejrzysz Evolution lub Journal of Theoretical Biology , rzadko zobaczysz dowód na twierdzenie-lemma, a kiedy to zrobisz, zwykle będzie to tylko obliczenie zamiast czegoś w rodzaju dowodu istnienia lub skomplikowanej konstrukcji.
  2. Paradygmaty analizy złożoności algorytmów
  3. Inne rodzaje analizy czasu pracy oprócz najgorszego przypadku, średniego przypadku itp.?
  4. Ekologia i ewolucja poprzez soczewkę algorytmiczną
  5. Dlaczego ekonomiści powinni dbać o złożoność obliczeniową
Artem Kaznatcheev
źródło
23
Niemożliwe jest zachowanie w najgorszym przypadku… algorytm simpleks ma wykładnicze zachowanie w gorszym przypadku, a jedynymi osobami, które kiedykolwiek się tym przejmowały, są teoretycy. Należy argumentować: (a) ważne jest zachowanie asymptotyczne w przeciętnym przypadku; (b) zachowanie asymptotyczne w przeciętnym przypadku i zachowanie asymptotyczne w najgorszym przypadku są dość często podobne; (c) zachowanie asymptotyczne w najgorszym przypadku jest często znacznie łatwiejsze do obliczenia niż zachowanie asymptotyczne w przeciętnym przypadku (zwłaszcza, że ​​nikt nie wie, jaki jest odpowiedni rozkład prawdopodobieństwa).
Peter Shor
5
Asymptotyka jest już aspektem problematycznym. Wszyscy znamy historię algorytmów mnożenia macierzy (asymptotyczne górne granice są w praktyce bez znaczenia), a być może także historię o wyborze parametrów w kryptografii (asymptotyczne dolne granice są w praktyce bez znaczenia; algorytmy wykładnicze są czasami wykonalne [DES]). Jeśli twoja analiza ma rzeczywiste stałe, jest bardziej przekonująca.
Yuval Filmus
6
Jeśli myślisz o obliczeniach jako grze (tj. Wojnie) między dostawcą danych wejściowych a algorytmem, to najgorszym przypadkiem jest standardowe podejście wojskowe - chcesz wiedzieć, jak źle może być. Po drugie i, co ważniejsze, analiza najgorszego przypadku nie pozwala ci być leniwym intelektualnie i akceptować rozwiązań, które mogą być dobre dla tego, co według ciebie jest światem (a nie tym, czym naprawdę jest świat). Wreszcie, a może przede wszystkim, zapewnia jednolity sposób porównywania algorytmów w nadziei, że w znaczący sposób. Krótko mówiąc, jest to najgorsze podejście, z wyjątkiem wszystkich innych.
Sariel Har-Peled
6
Myślę, że dolną granicę najgorszego przypadku należy postrzegać jako oddawanie piłki z powrotem na boisko. Pokazałeś, że nie ma algorytmu, który mógłby rozwiązać ich problem we wszystkich instancjach w rozsądnych ramach czasowych. Mogą mieć uzasadnione przekonanie, że ich instancje są łatwe - ale właśnie pokazałeś, że jeśli tak, to nie jest to trywialny fakt. Ich model jest zatem niekompletny, chyba że wyjaśnią, dlaczego tak jest.
Aaron Roth
3
(Takie podejście wydaje się sprawdzać w rozmowach z teoretykami gier. Rodzi to pytanie - czy rynki naprawdę szybko osiągają równowagę - jakie specjalne nieruchomości mają rynki rzeczywiste, które omijają najgorsze przypadki? Prawdopodobnie możliwe jest określenie prawdopodobnego taka własność, a dolne granice tylko sugerują, że jest to ważny kierunek badań)
Aaron Roth

Odpowiedzi:

8

Moim osobistym (i stronniczym) podejściem jest to, że asymptotyczna analiza najgorszego przypadku jest historycznym krokiem w kierunku bardziej praktycznych analiz. Dlatego wydaje się trudne do uzasadnienia dla praktyków.

Ustalenie granic dla najgorszego przypadku jest często łatwiejsze niż udowodnienie granic nawet dla „ładnych” definicji przeciętnego przypadku. Analiza asymptotyczna jest również często o wiele łatwiejsza niż wykazanie dość ciasnych granic. Dlatego analiza asymptotyczna w najgorszym przypadku jest doskonałym miejscem na rozpoczęcie.

Praca Daniela Spielmana i Shanghua Tenga nad płynną analizą Simplex wydaje mi się zwiastunem tego, co może się zdarzyć, gdy zaczniemy lepiej rozumieć kształt problemu: najpierw zajęcie się najgorszym przypadkiem pozwala na bardziej precyzyjne zrozumienie rozwinięty. Co więcej, jak zasugerował Aaron Roth w komentarzach, jeśli „zwykłe” zachowanie systemu znacznie różni się od jego najgorszego przypadku, to system nie jest jeszcze w pełni określony i potrzeba więcej pracy, aby ulepszyć model. Zatem wyjście poza najgorszy przypadek na ogół wydaje się ważne jako cel długoterminowy.

Jeśli chodzi o analizę asymptotyczną, zwykle służy ona do trzymania długiego i niechlujnego dowodu z dala od rozpraszających szczegółów. Niestety, obecnie wydaje się, że nie ma sposobu na nagrodzenie żmudnej pracy polegającej na wypełnianiu szczegółów w celu uzyskania rzeczywistych stałych, tak że rzadko wydaje się, że jest to zrobione. (Ograniczenia strony również działają przeciwko temu.) Staranna analiza szczegółów asymptotycznej granicy doprowadziła do faktycznych algorytmów, z dobrymi granicami stałych, więc osobiście chciałbym zobaczyć więcej tego rodzaju pracy. Być może jeśli sformalizowanych zostanie więcej dowodów za pomocą systemów asystenta dowodów, wówczas stałe można oszacować przy mniejszym wysiłku. (Lub granice stałych, zgodnie z linią Gowersa związaną z Szemerédi Regularity Lemma, mogą stać się bardziej rutynowe.) Istnieją również sposoby udowodnienia dolnych granic, które są wolne od stałych, za pomocą bardziej wyraźnych modeli maszyn (takich jak deterministyczne automaty skończone). Jednak takie (prawie) dokładne dolne granice dla bardziej ogólnych modeli obliczeń mogą wymagać dużo pracy lub być całkowicie poza zasięgiem. Wydaje się, że zostało to zrealizowane w latach ~ 1958–73 podczas pierwszego rozkwitu teorii automatów, ale o ile wiem, w dużej mierze pozostawiono je w spokoju.

O(nk)

András Salamon
źródło
Nie podzielam twojego entuzjazmu dla porzucania asymptotyków na rzecz precyzyjnych granic z określonymi stałymi. Asymptotyki mogą być nieprecyzyjne - ale są użyteczne nieprecyzyjne. Wyjaśniają różnice w implementacji dla tego samego modelu maszyny. Na przykład algorytm sortowania, który był kwadratowy na sprzęcie z lat 50., nadal będzie kwadratowy na dzisiejszym sprzęcie. Ponadto asymptotyczne formuły ładnie komponują się. Liniowe i wielomianowe są na przykład zamknięte w składzie. (Zwróć uwagę, że argumentowanie za lepszymi granicami przeciętnego przypadku w porównaniu z najgorszym przypadkiem jest ortogonalne od argumentów przeciwko asymptotykom.)
brandjon
Masz ogólnie rację, ale istnieje duża różnica między małą stałą a tą, która jest nie elementarną funkcją odpowiedniego parametru.
András Salamon
Ogólnie podoba mi się ta odpowiedź, ale zgadzam się z @brandjon, że ukrywanie stałych jest kluczowe. Dla mnie powodem, dla którego TCS jest przydatny w biologii, jest fakt, że musi on przyjmować znacznie mniej założeń dotyczących mikro dynamiki niż fizyki. Jeśli jednak nie przyjmujesz założeń dotyczących mikro dynamiki (tj. Dokładnej specyfikacji modelu obliczeniowego), nie możesz uzyskać stałych czynników. Inną przydatną funkcją TCS są rygorystyczne dychotomie jakościowe (coś łatwiejszego do porównania z bardziej jakościowymi obserwacjami w biografii), zwykle aby je uzyskać, musisz również porzucić stałe.
Artem Kaznatcheev
O~(nO~(1/ϵ))
1
Na marginesie, istnieją przykłady, w których analiza najgorszego przypadku ma sens. Na przykład, gdy tworzysz bibliotekę podprogramów ogólnego zastosowania i nie wiesz, w których domenach aplikacji będą one przydatne: nie możesz przewidzieć wszystkich przypadków, kiedy i dlaczego ktoś będzie chciał obliczyć, na przykład, dopasowanie dwustronne dla minimalnego kosztu. Ustawienia przeciwników, takie jak kryptografia, są jeszcze bardziej wyraźne (jednak w kryptografii naprawdę chcesz znać stałe, jeśli chodzi o parametry bezpieczeństwa).
Sasho Nikolov
4

Dolne granice i analiza najgorszego przypadku zwykle nie idą w parze. Nie twierdzisz, że algorytm zajmie co najmniej wykładniczy czas w najgorszym przypadku, dlatego jest zły. Mówisz, że w najgorszym przypadku może to zająć maksymalnie czas liniowy, a zatem jest dobre. Ten pierwszy jest użyteczny tylko wtedy, gdy zamierzasz uruchomić algorytm na wszystkich możliwych wejściach, a nie tylko na średnich danych wejściowych.

Jeśli chcesz użyć dolnych granic w celu wykazania złości, potrzebujesz analizy najlepszych przypadków lub analizy średnich przypadków. Możesz uprościć te rzeczy, opierając się na stwierdzeniu @ PeterShor, że najgorsze i średnie są często bardzo podobne, i podaje listę prania algorytmów, dla których jest to prawdą. (Np .: wszystkie klasyczne rodzaje oprócz szybkiego sortowania.)

Jeśli chodzi o wykazanie, że asymptotyki mają znaczenie w porównaniu ze stałymi danymi wejściowymi i stałymi czynnikami, moim ulubionym artykułem na ten temat jest „Perły programowania: techniki projektowania algorytmów” Jona Bentleya. Przedstawia cztery różne rozwiązania prostego problemu macierzowego i pokazuje, w jaki sposób podejście liniowe unicestwia podejście sześcienne. Swoją tabelę nazywa „Tyranią Asymptotyków”, po tym, jak fizycy używali terminu „równanie rakiety”. Korzystam z tego przykładu, aby motywować do poszukiwania lepszych algorytmów studentom w wieku przedszkolnym.

Czy nie-informatyk zapozna się z artykułem zawierającym kod i będzie wiedział, jak pominąć szczegóły niskiego poziomu, aby uzyskać ogólny obraz? Nie wiem Być może gdzieś jest lepsza prezentacja. Ale myślę, że jest to przyzwoity zasób do cytowania.

A jeśli twierdzą, że nie dbają o arbitralnie duże n, niech uruchomią rekurencyjne niezapamiętywane Fibonacciego na 3 * 10 9 parach zasad i powiedz im, że to O (1), ponieważ wielkość sekwencji DNA jest ustalona. ;)

brandjon
źródło
1
Podoba mi się przykład Fibonacciego :)
Suresh Venkat
3
Re: Twój pierwszy akapit: właściwie to właśnie robi wiele teorii złożoności. Jeśli problem jest zakończony EXP, oznacza to, że wymaga on wykładniczego czasu na wejściach w najgorszym przypadku. Zasadniczo jest to traktowane jako wskaźnik jego ogólnej trudności (co, mówiąc szczerze, w praktyce często nie jest tak złe, jak ogólny wskaźnik). Jest to de facto standard, nazywany „nieskończenie często” lub „dolną granicą”; Osiągnięcie dolnych granic średniej lub prawie wszędzie (to znaczy dla wszystkich, ale nieskończenie wielu danych wejściowych) jest czasem celem, który jest często realizowany, ale często daleko poza zasięgiem w porównaniu do dolnych granic.
Joshua Grochow
2
Zaznaczę, że nie tylko możesz podać listę algorytmów prania, dla których analiza najgorszych i średnich przypadków jest taka sama, ale możesz także podać liczne przykłady, w których są one bardzo różne (algorytm simpleks jest po prostu najbardziej znany tych). Naprawdę trzeba jakoś argumentować, że są one takie same dla konkretnego zastosowania; testowanie eksperymentalne jest dobrym sposobem na to.
Peter Shor
1
@JoshuaGrochow Wystarczająco. A może zmienimy zdanie w następujący sposób: Dolne granice w najgorszych przypadkach są ważne, gdy chcesz wykazać brak matematycznej gwarancji braku okropności. ;)
brand
-3

wielu zgodziło się, że jest to ważny temat do zbadania / omówienia, ale wydaje się, że nie było to jeszcze wiele. kilka bibl o różnym stylu / WYDAJNOŚĆ / widzów / formalności nie dokładnie zgodnie z wnioskiem, ale raczej blisko (najlepiej widoczne w Internecie do tej pory na średnim wyszukiwania, nadzieję usłyszeć dodatkowo żadnej lepszych; więcej uwagi poniżej):

  • Złożoność algorytmów Atkinsona (niestety tylko jeden odnośnik do biologii w artykule, ale może wystarczyć na bardziej ogólnych terminach nauki / inżynierii)

    Współczesna teoria algorytmów pochodzi z późnych lat 60. XX wieku, kiedy zaczęto stosować metodę asymptotycznego pomiaru czasu wykonania. Argumentuje się, że przedmiot ma zarówno skrzydła inżynierskie, jak i naukowe. Skrzydło inżynierskie składa się z dobrze zrozumiałych metodologii projektowania, podczas gdy skrzydło naukowe zajmuje się podstawami teoretycznymi. Kluczowe problemy obu skrzydeł są badane. Na koniec podaje się kilka osobistych opinii na temat tego, gdzie temat pójdzie dalej.

  • Złożoność i algorytmy J. Diaz. 100 slajdów. szeroki; można w szczególności wyciąć odpowiednie.

  • Delikatne wprowadzenie do analizy złożoności algorytmów Dioniza „dionyziz” Zindros

innymi słowy, czy istnieje coś w rodzaju wstępu / badania / przeglądu soczewki teoretycznej złożoności w ścisłej kombinacji / koniunkcji / towarzysza z postępującą soczewką algorytmiczną w nauce, coś w rodzaju „teorii złożoności dla naukowców, inżynierów i badaczy” ?

istnieją dobre referencje na temat poprzedniej „soczewki algorytmicznej”, którą zacytowałeś, np. Papadimitriou, ale nie wydaje się, aby wysoce zadowalająca referencja od eksperta w tej dziedzinie została napisana na tej ostatniej „soczewce złożoności”… jeszcze (może niektóre „elitarne” „ członek tej witryny uzna to za następny projekt książkowy lub papierowy).

należy również zauważyć, że istnieje wiele odniesień do trafności P w porównaniu do NP poza teorią złożoności oraz w innych dziedzinach naukowych, które można by w pewnym stopniu wykorzystać do tych celów. doda je w komentarzach, jeśli będzie jakieś zainteresowanie.

vzn
źródło
3
Nie sądzę, że to naprawdę odpowiada na pytanie.
Huck Bennett
1
huh, czy spojrzałeś na którykolwiek z referencji? częścią mojej odpowiedzi jest to, że nie ma (jeszcze) żadnej idealnej / idealnej odpowiedzi: |
vzn
1
Zdają się raczej definiować asymptotyczną i najgorszą analizę przypadków niż skupiać się na jej uzasadnieniu, ale może coś przeoczyłem?
Huck Bennett
7
Właściwie uważam, że badacze spoza TCS mogliby z łatwością odrzucić najgorszy przypadek jako „sztucznie skonstruowane przykłady, które nigdy nie wystąpiłyby w praktyce” i byliby (bez wyraźnego przekonania inaczej) o wiele bardziej zainteresowani przeciętnym przypadkiem (pomimo faktu, że nie jest jasne, że przeciętny przypadek jest o wiele bliższy rzeczywistym instancjom).
Joshua Grochow
1
@vzn: Asymptotyczne (np. duże-Oh) i najgorsze są nieco ortogonalne. Można przeprowadzić asymptotyczną analizę najgorszego przypadku, asymptotyczną analizę średniego przypadku, a nawet asymptotyczną analizę najprostszego przypadku (choć przyznaję, że ta ostatnia wydaje się nieco przewrotna). Zamiast tego można przeprowadzić dokładną analizę najgorszego przypadku lub dokładną analizę średniego przypadku i tak dalej, chociaż byłyby one znacznie bardziej zależne od modelu i mniej niezawodne. Usprawiedliwienie użycia asymptotyków (i ukrywanie rzeczy takich jak stałe czynniki) jest całkowicie odrębne od uzasadnienia przypadku najgorszego w porównaniu do przypadku przeciętnego lub „rzeczywistego” (cokolwiek to może oznaczać ...).
Joshua Grochow