co rozumie się przez integrację numeryczną jest zbyt droga?

12

Czytam o wnioskowaniu bayesowskim i natknąłem się na frazę „numeryczna integracja marginalnego prawdopodobieństwa jest zbyt droga”

Nie mam doświadczenia w matematyce i zastanawiałem się, co dokładnie oznacza tutaj droga ? Czy chodzi tylko o moc obliczeniową, czy może jest coś więcej.

discretetimeisnice
źródło
6
Oznacza to, że wymaga zbyt dużej mocy obliczeniowej, prawdopodobnie pod względem czasu procesora (ponieważ wszystkie zasoby obliczeniowe są zasadniczo albo pamięcią, albo procesorem).
Sycorax mówi Przywróć Monikę
3
W rzeczywistości przepustowość komunikacji może czasem stanowić problem (np. Szeregowo pamięć podręczna / pamięć RAM / dysk lub równolegle między węzłami obliczeniowymi).
GeoMatt22,
Oznacza to, że wykonanie tego obliczenia zajmuje zbyt wiele czasu, aby pojedynczy komputer, a nasz sieć komputerów, wykonał obliczenia.
Jack Maddington,
2
A jeśli w jakiejś pętli potrzebne jest krańcowe prawdopodobieństwo, to, co uważa się za zbyt drogie, jest znacznie mniejsze. Na przykład. 1-sekundowa procedura integracji brzmi szybko, ale może być „zbyt droga”, jeśli trzeba to zrobić milion razy ...
Matthew Gunn,
Kosztowne pod względem wysiłku obliczeniowego, ponieważ wymaga więcej wysiłku, aby go obliczyć, niż możesz sobie pozwolić, ponieważ zajmuje to zbyt dużo czasu lub wymaga zbyt wielu procesorów, aby zrobić to w rozsądnym czasie.
user253751,

Odpowiedzi:

16

W kontekście problemów obliczeniowych, w tym metod numerycznych do wnioskowania bayesowskiego, zwrot „zbyt drogi” ogólnie może odnosić się do dwóch kwestii

  1. szczególności problemem jest zbyt „duże”, aby obliczyć dla konkretnego „ budżet
  2. ogólne podejście źle się skaluje , tj. ma wysoką złożoność obliczeniową

W obu przypadkach zasoby obliczeniowe składające się z „budżetu” mogą składać się z takich elementów, jak cykle procesora ( złożoność czasu ), pamięć ( złożoność przestrzeni ) lub przepustowość komunikacji ( w obrębie lub między węzłami obliczeniowymi). W drugim przypadku „zbyt drogi” oznaczałoby trudność .

W kontekście obliczeń Bayesa, cytat jest prawdopodobne, odnosząc się do problemów z marginalizacją na dużą liczbę zmiennych .

Na przykład zaczyna się streszczenie tego ostatniego artykułu

Na integrację wpływa klątwa wymiarowości i szybko staje się ona trudna w miarę wzrostu wymiarów problemu.

i mówi dalej

Proponujemy algorytm randomizowany, który ... może z kolei zostać użyty, na przykład, do obliczeń marginalnych lub wyboru modelu.

(Dla porównania, ten ostatni rozdział książki omawia metody uważane za „niezbyt drogie”).

GeoMatt22
źródło
4
To świetna odpowiedź. Dodam tylko, że „kosztowne” można coraz częściej traktować dosłownie. - można znacznie zwiększyć moc obliczeniową i pojemność pamięci (do poziomu superkomputera, tak długo, jak długo trzeba), bardzo łatwo w dzisiejszych czasach (i dość tanio) ... ale w przypadku dużych problemów nadal będzie to zbyt kosztowne - - w ten sposób dosłownie będzie kosztować więcej rzeczywistych pieniędzy niż masz do dyspozycji.
Glen_b
1
@Glen_b to dobra uwaga! Wyobrażam sobie, że to znaczenie jest mniej powszechne w opublikowanej literaturze ... ale bardziej powszechne w propozycjach (i ich recenzjach!)
GeoMatt22,
@ GeoMatt22 To właściwie inny sposób wyrażenia tego samego znaczenia, jeśli się nad tym zastanowić.
user253751,
@ GeoMatt22 Dziękujemy! Teraz doskonale rozumiem, co oznacza koszt w kontekście bayesowskim.
discretetimeisnice
10

Dam ci przykład na dyskretnym przypadku, aby pokazać, dlaczego integracja / sumowanie jest bardzo kosztowne.

Załóżmy, że mamy losowych zmiennych binarnych i mamy wspólny rozkład . (W rzeczywistości nie można przechowywać wspólnej dystrybucji w tabeli, ponieważ istnieją wartości . Załóżmy, że mamy ją teraz w tabeli i w pamięci RAM.)P ( X 1 , X 2 , , X 100 ) 2 100100P(X1,X2,,X100)2100

Aby uzyskać rozkład krańcowy na , musimy zsumować inne zmienne losowe. (W przypadku ciągłym integracja jest zakończona.)P(X1)

P(X1)=X2X3X100P(X1,X2,,X100)

Sumujemy ponad zmiennych, dlatego jest liczba wykładnicza operacji, w tym przypadku jest to , co jest ogromną liczbą, której wszystkie komputery na ziemi nie są w stanie wykonać.2 9999299

W literaturze dotyczącej modeli graficznych probabilistycznych taki sposób obliczania rozkładu krańcowego nazywany jest podejściem „brutalnej siły” w celu wykonania „wnioskowania”. Z nazwy możemy wiedzieć, że jest drogi. I ludzie używają wielu innych sposobów przeprowadzenia wnioskowania, np. Skutecznego uzyskania rozkładu krańcowego. „Inne sposoby”, w tym wnioskowanie przybliżone itp.

Haitao Du
źródło
3
Być może mógłbyś również skomentować, dlaczego podejście bayesowskie jest tutaj pomocne, jako pytanie postawione w tym kontekście.
Tim
5

Zwykle podczas przeprowadzania wnioskowania bayesowskiego łatwo jest na przykład spotkać ciężką integrację z uciążliwymi zmiennymi. Innym przykładem może być próbkowanie numeryczne, jak w tym przypadku z funkcji prawdopodobieństwa, co oznacza wykonanie losowego próbkowania z danego rozkładu. Wraz ze wzrostem liczby parametrów modelu, próbkowanie staje się niezwykle ciężkie i opracowano różne metody obliczeniowe w celu przyspieszenia procedury i umożliwienia bardzo szybkich implementacji, przy zachowaniu oczywiście wysokiego poziomu dokładności. Te techniki to na przykład MC, MCMC, Metropolis ecc. Zobacz analizę danych bayesowskich autorstwa Gelmana i in. al powinien dać ci szerokie wprowadzenie! powodzenia

Lcol
źródło
3
Ta odpowiedź nie wydaje się odpowiadać na główne pytanie PO dotyczące znaczenia słowa „drogi” w tym kontekście. A przynajmniej niezbyt wyraźnie.
Shufflepants
Krótkie wyjaśnienie ma na celu przybliżenie czytelnikowi znaczenia zapotrzebowania obliczeniowego podczas wykonywania konkretnej analizy w statystyce bayesowskiej, ponieważ nie jest matematykiem. W każdym razie mam nadzieję, że dla kogoś było to jasne
Lcol