Co rozumiemy przez heurystyczne argumenty fizyki statystycznej?

29

Słyszałem, że w fizyce statystycznej istnieją heurystyczne argumenty, które dają wyniki w teorii prawdopodobieństwa, dla których rygorystyczne dowody są albo nieznane, albo bardzo trudne do uzyskania. Jaki jest prosty zabawkowy przykład takiego zjawiska?

Byłoby dobrze, gdyby odpowiedź obejmowała niewielkie podstawy fizyki statystycznej i mogła wyjaśnić, czym są te tajemnicze heurystyki i jak można je nieformalnie uzasadnić. Być może ktoś może wskazać szeroki obraz tego, jak wiele z tych heurystyk może być rygorystycznie uzasadnione i jak pasuje do tego program Lawlera, Schramma i Wernera.

arnab
źródło
Z góry przepraszamy za „początkujący” charakter tego pytania!
arnab
1
Miałem podobne pytanie - na przykład formuła dotycząca tempa wzrostu liczby samowystarczalnych spacerów w sieci 4d jest uzasadniona „podejściem do grupy renormalizacji”, mimo że nie ma ścisłego dowodu
Jarosław Bułatow
maksymalna entropia (a-la Jaynes i powiązane relacje) jest najczęściej używana (w taki czy inny sposób)
Nikos M.

Odpowiedzi:

22

Drugi akapit odpowiedzi RJK zasługuje na więcej szczegółów.

Niech będzie formułą w spójnej postaci normalnej, z m klauzulami, n zmiennymi i co najwyżej k zmiennymi na klauzulę. Załóżmy, że chcemy ustalić, czy ma zadowalające zadanie. Formula jest przykładem problemu decyzyjnego k-SAT.ϕ ϕϕϕϕ

Kiedy klauzul jest niewiele (więc m jest dość małe w porównaniu do n), prawie zawsze można znaleźć rozwiązanie. Prosty algorytm znajdzie rozwiązanie w przybliżeniu liniowym czasie w rozmiarze formuły.

Kiedy jest wiele klauzul (więc m jest dość duży w porównaniu do n), prawie zawsze jest tak, że nie ma rozwiązania. Można to pokazać argumentem liczącym. Jednak podczas wyszukiwania prawie zawsze możliwe jest przycinanie dużych części przestrzeni wyszukiwania za pomocą technik spójności, ponieważ wiele klauzul oddziałuje tak intensywnie. Stwierdzenie niezadowolenia można wówczas zwykle zrobić skutecznie.

W 1986 Fu i Anderson przypuszczali, że istnieje związek między problemami optymalizacyjnymi a fizyką statystyczną, oparty na systemach ze spinu. Chociaż używali zdań takich jak

Intuicyjnie system musi być wystarczająco duży, ale trudno jest sprecyzować.

faktycznie dają konkretne prognozy.

  • Y Fu i PW Anderson. Zastosowanie mechaniki statystycznej do problemów NP-zupełnych w optymalizacji kombinatorycznej , J. Phys. A. 19 1605, 1986. doi: 10.1088 / 0305-4470 / 19/9/033

Na podstawie argumentów fizyki statystycznej Zecchina i współpracownicy wysunęli hipotezę, że k-SAT powinien stać się trudny, gdy jest bliski wartości krytycznej. Dokładna wartość krytyczna zależy od k, ale mieści się w zakresie od 3,5 do 4,5 dla 3-SAT.α=m/n

  • Rémi Monasson, Riccardo Zecchina, Scott Kirkpatrick, Bart Selman, Lidror Troyansky. Określanie złożoności obliczeniowej na podstawie charakterystycznych „przejść fazowych” , Nature 400 133–137, 1999. ( doi: 10.1038 / 22055 , wersja bezpłatna )

Friedgut przedstawił rygorystyczny dowód na te heurystyczne argumenty. Dla każdej stałej wartości k istnieją dwa progi . Dla poniżej istnieje zadowalające przypisanie z dużym prawdopodobieństwem. Dla wartości powyżej formuła jest niezadowalająca z dużym prawdopodobieństwem. α α 1 α α 2 ϕα1<α2αα1αα2ϕ

  • Ehud Friedgut (z dodatkiem Jeana Bourgaina), ostre progi właściwości grafu i problem satak , J. Amer. Matematyka Soc. 12 1017–1054, 1999. ( PDF )

Dimitris Achlioptas pracował nad wieloma pozostałymi zagadnieniami i wykazał, że powyższy argument dotyczy również problemów związanych z satysfakcją z ograniczeń. Dozwolone jest użycie więcej niż dwóch wartości dla każdej zmiennej. Jeden kluczowy artykuł pokazuje rygorystycznie, dlaczego algorytm propagacji ankiety działa tak dobrze do rozwiązywania losowych instancji k-SAT.

  • A. Braunstein, M. Mézard, R. Zecchina, Propagacja badania: algorytm satysfakcji , Struktury losowe i algorytmy 27 201–226, 2005. doi: 10.1002 / rsa.20057
  • D. Achlioptas i F. Ricci-Tersenghi, O geometrii rozwiązanie-przestrzeń losowych problemów z ograniczeniami losowymi, STOC 2006, 130–139. ( preprint )
András Salamon
źródło
Dziękuję za referencje! Przyjmuję tę odpowiedź, ponieważ jest ona najbardziej wyczerpująca. Nadal byłbym zainteresowany nieformalnym opisem programu Lawlera, Schramma i Wernera.
arnab
11

Istnieje bardzo niedawna ankieta przeprowadzona przez Lawlera na temat SLE . Musisz znać trochę złożonej analizy.

Chociaż nie jest to bezpośrednio związane z twoim pytaniem, być może mógłbyś zapoznać się z kilkoma artykułami Achlioptas, które również mieszczą się pod parasolem „formalizacji heurystyk fizyków”, choć z punktu widzenia teoretycznego informatyka. A może głębiej w perspektywie statphys możesz przejrzeć niektóre prace Zecchiny .

Myślę, że warto dodać, że tak zwane „wyniki” fizyków - z których większość należy nazwać przypuszczeniami - w tej bardzo szerokiej kategorii problemów polegają prawie w takim samym stopniu (lub nawet więcej) na eksperymentach numerycznych, jak ( niż) na heurystycznych argumentach.

RJK
źródło
Dziękujemy za link do ankiety! Czy możesz bardziej rozwinąć te eksperymenty obliczeniowe? Jakie spostrzeżenia z fizyki statystycznej są wykorzystywane? Szukałem prostego przykładu zabawki (powiedzmy z teorii perkolacji), w którym można nieformalnie wysunąć argument oparty na fizyce statystycznej.
arnab
Zasadniczo, Monte Carlo / eksperymenty statystyczne, które są również
szeroko
2

(rozwinięcie mojego komentarza)

„Fizyczną intuicją” kryjącą się za metodami statystycznymi stosowanymi w obliczeniach jest Maximum Entropia (a-la Jaynes) oraz powiązane metody stochastyczne, takie jak Symulowane Wyżarzanie lub Wyżarzanie Deterministyczne . Jaynes sformułował podejście oparte na maksymalnej entropii (bezpośrednie uogólnienie fizyki statystycznej) w celu rozwiązania problemów odwrotnych (w kategoriach obliczeniowych obejmują one problemy twarde )NP

Przegląd „ heurystyki z natury ” można znaleźć tutaj (około 95)

Inne heurystyki dotyczą uogólnionych langrangianów (inaczej algorytmy pierwotny podwójny / maksymalizacja oczekiwań)

Jednak to nie nie wyczerpują wszystkich „ heurystyki z natury ”, jak w rzeczywistości od 2003 roku nowych heurystyk opartych na electromargnetism zostały wykorzystane do przeciwdziałania zarówno ciągłych i dyskretnych / kombinatoryczne metody optymalizacji (jak wielowymiarowej plecaka , lub TSP , około 2012 roku)

Nikos M.
źródło