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

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.

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”).

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 $100$$P(X_1, X_2, \cdots, X_{100})$$2^{100}$

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

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 $99$$2^{99}$

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.

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