Dlaczego problem bałaganu jest trudny do rozwiązania w przypadku dużych próbek?

13

Załóżmy, że mamy zbiór punktów . Każdy punkt y i jest generowany przy użyciu rozkładu p ( y i | x ) = 1y={y1,y2,,yN}yi Aby uzyskać posteriori dlaxnapisać p(x|y)αP(r|x)p(x)=t(x) N Π i=1s(Yı|X). Zgodnie z pracą Minki na tematpropagacji oczekiwańpotrzebujemy2Nobliczeń, aby uzyskać wynik tylny

p(yi|x)=12N(x,1)+12N(0,10).
x
p(x|y)p(y|x)p(x)=p(x)i=1Np(yi|x).
2N , a więc, problem staje się trudny do dużych rozmiarów próbki N . Jednak nie mogę dowiedzieć się, dlaczego potrzebujemy takiej ilości obliczeń w tym przypadku, ponieważ dla pojedynczego y í prawdopodobieństwa ma postać p ( y i | x ) = 1p(x|y)Nyi
p(yi|x)=122π(exp{12(yix)2}+110exp{120yi2}).

Stosując tę ​​formułę, uzyskujemy wynik tylny poprzez proste pomnożenie , więc potrzebujemy tylko N operacji, i możemy dokładnie rozwiązać ten problem dla dużych próbek.p(yi|x)N

Robię eksperyment numeryczny porównać mogę naprawdę uzyskać taką samą posterior w przypadku obliczyć każdy termin oddzielnie iw przypadku użycia I iloczyn gęstości dla każdego . Tylne ściany są takie same. Zobacz, gdzie się mylę? Czy ktoś może mi wyjaśnić, dlaczego potrzebujemy 2 N operacji, aby obliczyć w późniejszym przypadku dla danego x i próbki y ?yiwprowadź opis zdjęcia tutaj2Nxy

Aleksiej Zajcew
źródło
NO(N)x
yiO(nlog(n))n
1
2Nx2N
1
2N
1
N2NxNx

Odpowiedzi:

4

xO(n)x2N

Tom Minka
źródło
2

yip(yi|x)1wpc(y)yxw

cii0p(y|x)x

2N

Dave
źródło
cix2N
c
cici
2N
O(n)O(2n)