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 jest generowany przy użyciu rozkładu $\mathbf{y} = \{y_1, y_2, \ldots, y_N \}$ $y_i$ Aby uzyskać posteriori dlanapisać Zgodnie z pracą Minki na tematpropagacji oczekiwańpotrzebujemyobliczeń, aby uzyskać wynik tylny

p (y_{i} | x) = \frac{1}{2} N (x, 1) + \frac{1}{2} N (0, 10) .

$p(y_i| x) = \frac12 \mathcal{N}(x, 1) + \frac12 \mathcal{N}(0, 10).$

x

$x$

p (x | y) \propto p (y | x) p (x) = p (x) \prod_{i = 1}^{N} p (y_{i} | x) .

$p(x| \mathbf{y}) \propto p(\mathbf{y}| x) p(x) = p(x) \prod_{i = 1}^N p(y_i | x).$

2^{N}

$2^N$

, a więc, problem staje się trudny do dużych rozmiarów próbki

. Jednak nie mogę dowiedzieć się, dlaczego potrzebujemy takiej ilości obliczeń w tym przypadku, ponieważ dla pojedynczego

prawdopodobieństwa ma postać

p (x | y)

$p(x| \mathbf{y})$

N

$N$

y_{i}

$y_i$

p (y_{i} | x) = \frac{1}{2 \sqrt{2 π}} (\exp {- \frac{1}{2} (y_{i} - x)^{2}} + \frac{1}{\sqrt{10}} \exp {- \frac{1}{20} y_{i}^{2}}) .

$p(y_i| x) = \frac{1}{2 \sqrt{2 \pi}} \left( \exp \left\{-\frac12 (y_i - x)^2\right\} + \frac{1}{\sqrt{10}} \exp \left\{-\frac1{20} y_i^2\right\} \right).$

Stosując tę formułę, uzyskujemy wynik tylny poprzez proste pomnożenie , więc potrzebujemy tylko operacji, i możemy dokładnie rozwiązać ten problem dla dużych próbek. $p(y_i| 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 operacji, aby obliczyć w późniejszym przypadku dla danego i próbki ? $y_i$ wprowadź opis zdjęcia tutaj $2^N$ $x$ $\mathbf{y}$

bayesian mixture posterior

— Aleksiej Zajcew
źródło

N

$N$

O (N)

$O(N)$

x

$x$

y_{i}

$y_i$

O (n \log (n))

$O(n\log(n))$

n

$n$

1

2^{N}

$2^N$ $x$ $2^N$

1

2^{N}

$2^N$

1

N

$N$

2^{N}

$2^N$

x

$x$

N

$N$

x

$x$

4

$x$ $O(n)$ $x$ $2^N$

— Tom Minka
źródło

2

$y_i$ $p(y_i | x)$ $1-w$ $p_c(y)$ $y$ $x$ $w$

$c_i$ $i$ $0$ $p(y|x)$ $x$

$2^N$

— Dave
źródło

c_{i}

$c_i$

x

$x$

2^{N}

$2^N$

c

$c$

c_{i}

$c_i$

c_{i}

$c_i$

2^{N}

$2^N$

O (n)

$O(n)$

O (2^{n})

$O(2^n)$