¿Por qué es el desorden problema intratable para grandes tamaños de muestra?

Question

Supongamos que tenemos un conjunto de puntos de $\mathbf{y} = \{y_1, y_2, \ldots, y_N \}$. Cada punto de $y_i$ es generado utilizando la distribución $$ p(y_i| x) = \frac12 \mathcal{N}(x, 1) + \frac12 \mathcal{N}(0, 10). $$ Para obtener posterior para $x$ escribimos $$ p(x| \mathbf{y}) \propto p(\mathbf{y}| x) p(x) = p(x) \prod_{i = 1}^N p(y_i | x). $$ De acuerdo a Minka del papel en la Expectativa de Propagación necesitamos $2^N$ cálculos para obtener posterior $p(x| \mathbf{y})$ y, así, el problema se vuelve intratable para grandes tamaños de muestra $N$. Sin embargo, no puedo entender por qué tenemos tal cantidad de cálculos en este caso, porque para una sola $y_i$ de probabilidad tiene la forma $$ 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). $$

El uso de esta fórmula obtenemos posterior por una simple multiplicación de $p(y_i| x)$, por lo que sólo necesitamos $N$ operaciones, y, por lo que podemos resolver este problema para grandes tamaños de muestra exactamente.

Yo numéricos experimento para comparar lo que realmente conseguir el mismo posterior en caso de que se me calcular cada término por separado y en caso de que use el producto de las densidades para cada una de las $y_i$. Posteriores son los mismos. Ver Donde estoy equivocado? Cualquiera puede hacer claro para mí por qué necesitamos la $2^N$ operaciones para calcular posterior para determinado $x$ y la muestra $\mathbf{y}$?

Answer 1

Te perdiste el punto de que la distribución es una mezcla de Gaussianas: cada muestra $y_i$ es distribuido como por $p(y_i | x)$ con una probabilidad de $1-w$ y $p_c(y)$ (el desorden de distribución para $y$, independiente de $x$) con una probabilidad de $w$.

Deje $c_i$ ser el indicador de la variable que indica que la muestra $i$ fue sacar de el desorden de distribución; por lo tanto, si es $0$ indica que la muestra fue tomada de $p(y|x)$. Obviamente, si la muestra fue tomada de la complejidad de la distribución del valor es irrelevante para la estimación de $x$.

Es la presencia de la $2^N$ posible conjunta de los estados para estas variables indicadoras que causa el problema.

Answer 2

Tienes razón en que el papel está diciendo algo equivocado. Ciertamente, usted puede evaluar la distribución posterior de los $x$ en una ubicación conocida del uso de $O(n)$ operaciones. El problema es cuando se desea calcular los momentos de la parte posterior. Para calcular la parte posterior de la media de $x$ exactamente, usted necesitaría $2^N$ operaciones. Este es el problema de que el papel está tratando de resolver.