Me encontré con la siguiente simulación problema: dado un conjunto $\{\omega_1,\ldots,\omega_d\}$ de los conocidos números reales, una distribución en $\{-1,1\}^d$ está definido por $$\mathbb{P}(X=(x_1,\ldots,x_d))\propto (x_1\omega_1+\ldots+x_d\omega_d)_+$$ donde $(z)_+$ denota la parte positiva de $z$. Mientras yo pueda pensar en una Metropolis-Hastings sampler dirigidos a esta distribución, me pregunto si existe una eficiente directa sampler, aprovechando la gran cantidad de cero probabilidades para disminuir la orden del algoritmo de$O(2^d)$$O(d)$.
Respuesta
¿Demasiados anuncios?
Bauna
Puntos
176
He aquí una bastante obvia recursiva sampler que s $O(d)$ en el mejor de los casos (en términos de pesos $\omega_i$), pero exponencial en el peor de los casos.
Supongamos que ya hemos seleccionado $x_1, \dots, x_{i-1}$, y desea elegir a $x_{i}$. Tenemos que calcular el $$w(x_1, \dots, x_{i-1}, x_i) = \sum_{x_{i+1} \in \{-1, 1\}} \cdots \sum_{x_{i+1} \in \{-1, 1\}} \left( \sum_{j=1}^d \omega_j x_j \right)_+$$ y elija $x_i = 1$ con una probabilidad de $$\frac{w(x_1, \dots, x_{i-1}, 1)}{w(x_1, \dots, x_{i-1}, 1) + w(x_1, \dots, x_{i-1}, -1)}.$$ El denominador será distinto de cero para cualquier elección válida de muestras $x_1, \dots, x_{i-1}$.
Ahora, por supuesto, la pregunta es cómo calcular $w(x_1, \dots, x_i)$.
Si tenemos que $C := \sum_{j=1}^{i} \omega_j x_j \ge \sum_{j=i+1}^{d} \lvert \omega_j \rvert$, $\omega \cdot x \ge 0$ cualquier $x$ con las principales entradas de la $x_{1:i}$, y por lo $w$ se convierte en: \begin{align} \sum_{x_{i+1}} \cdots \sum_{x_d} \omega \cdot x &= \omega \cdot \left( \sum_{x_{i+1}} \cdots \sum_{x_d} x \right) \\&= \sum_{j=1}^i \omega_j \underbrace{\left( \sum_{x_{i+1}} \cdots \sum_{x_d} x_j \right)}_{2^{d-i} x_j} + \sum_{j=i+1}^d \omega_j \underbrace{\left( \sum_{x_{i+1}} \cdots \sum_{x_d} x_j \right)}_{0} \\&= 2^{d-i} C .\end{align}
En el caso opuesto, $C \le - \sum_{j=i+1}^{d} \lvert \omega_j \rvert$, tenemos que $\omega \cdot x \le 0$$w(x_1, \dots, x_i) = 0$.
De lo contrario, debemos recurse, el uso de $w(x_1, \dots, x_i) = w(x_1, \dots, x_i, 1) + w(x_1, \dots, x_i, -1)$.
Suponga que la memoria no es un problema y que podemos almacenar en caché todos los sub-cálculos en $w(1)$, $w(-1)$ en un árbol – hasta el punto de que llegamos a uno de los "buenos" de los casos, después de que ninguna de las llamadas constantes de tiempo. (Tendremos que calcular todo este árbol de todos modos para seleccionar $x_1$.) Luego, una vez que este árbol de la $w$ los cálculos, está construido, el sampler solo tomará $O(d)$ del tiempo. La pregunta es ¿cuánto tiempo se necesita para construir el árbol, o, equivalentemente, cuán grande es.
Por supuesto, vamos a llegar a la "bonita" de los casos más rápido si el $\omega_i$ son ordenados, $\omega_1 \ge \omega_2 \ge \dots \ge \omega_d$.
En el mejor de los casos, $\lvert \omega_1 \rvert > \sum_{j=2}^d \lvert \omega_j \rvert$. Luego nos topamos con un "bonito" caso de inmediato, ya sea para $w(1)$ o $w(-1)$, lo $w$ árbol de la construcción se lleva a la constante de tiempo, y todo el sampler tarda $O(d)$ del tiempo.
En el peor de los (ordenadas), $\omega_1 = \omega_2 = \dots = \omega_d$. Entonces la pregunta es: ¿cómo de grande es el total del árbol?
Así, la primera caminos para terminar son de curso $(1, 1, \dots, 1)$ $(-1, -1, \dots, -1)$ de la longitud de la $\lceil d/2 \rceil$. El árbol es, por tanto, completar hasta esa profundidad, y por tanto contiene, al menos, $O(2^{d/2})$ nodos. (Tiene más; usted probablemente puede encontrar con un argumento como las que se usan en el jugador de la ruina de los problemas, pero no lo pude encontrar en dos minutos de Googlear y no le preocupa – $2^{d/2}$ es bastante malo....)
Si su configuración sólo tiene un par muy grande $\omega_i$, esto es probablemente un razonablemente enfoque práctico. Si el $\omega_i$ son de magnitud similar, es probable que aún exponencial y demasiado caro para un gran $d$.
