Elegir la distribución de probabilidad para maximizar la función de evaluación (para el concurso de previsión de la gripe de los CDC)

Question

Suponga que tiene una variable aleatoria discreta $X$ con función de masa de probabilidad $p(x) = P(X=x)$ en el soporte $0,\ldots,n$ . Qué función $q(x)\ge 0$ tal que $\sum_{x=0}^n q(x) = 1$ maximiza $$ E(\log[q(X-1)+q(X)+q(X+1)])? $$ Para no tener que lidiar con los casos límite, se supone que $P(X=0)=P(X=n)=0$ .

Preguntas relacionadas:

• Creo que el $q(x)$ que maximiza la expectativa anterior también maximiza $E[q(X-1)+q(X)+q(X+1)]$ desde $\log$ es monótona. ¿Es eso correcto?
• ¿Puede algo vencer a $p(x)=q(x)$ ?

Para aquellos que estén interesados, esta pregunta surge de la Concurso de previsión de la gripe de los CDC donde utilizan el logaritmo de la suma de las probabilidades para el valor objetivo y los valores vecinos como función de utilidad para evaluar las previsiones.

Answer 1

Desde $\mathbf{q}=\mathbf{p}$ resuelve $$\arg\min_\mathbf{q} \sum p_i\log\{ p_i\big/q_i\}$$ ¿qué tal si sólo resolvemos $$q_{i-1}+q_i+q_{i+1}=3p_i\qquad i=1,\ldots,n-1$$ para encontrar la solución a $$\arg\max_\mathbf{q} \sum p_i\log\{ p_i\big/(q_{i-1}+q_i+q_{i+1})\}$$ Si la solución de este sistema de ecuaciones no pertenece al $\mathbb{R}^{n+1}$ simplex entonces el argumento se encontrará en una cara del simplex.

Answer 2

¡Un problema genial! Como muestra la derivación de Xi'an, está relacionado con la minimización del Divergencia KL de Q a P. Cliff también proporciona un contexto importante.

El problema puede resolverse de forma trivial utilizando un software de optimización, pero no veo la forma de escribir una fórmula de forma cerrada para la solución general. Si $q_i \geq 0 $ nunca se une, entonces hay una fórmula intuitiva.

Casi seguro que es óptimo $\mathbf{q} \neq \mathbf{p}$ (aunque vea mis gráficos de ejemplo al final, podría estar cerca). Y $\max \mathrm{E}[x]$ no es el mismo problema que $\max \mathrm{E}[\log(x)]$ . Observar $x + y$ no es un objetivo equivalente como $\log(x) + \log(y)$ . No es una transformación monótona. La expectativa es una suma y el logaritmo va dentro de la suma, por lo que no es una transformación monótona de la función objetivo.

Condiciones KKT (es decir, condiciones necesarias y suficientes) para una solución:

Definir $q_0 = 0$ y $q_{n+1} = 0$ . El problema es: \begin {Ecuación} \begin {array}{*2{>{} \displaystyle }r}} \mbox {maximizar (sobre $q_i$ )} & \sum_ {i=1}^n p_i \log \left ( q_{i-1} + q_i + q_{i+1} \right ) \\ \mbox {sujeto a} & q_i \geq 0 \\ & \sum_ {i=1}^n q_i = 1 \end {array} \end {Ecuación}

Lagrangiano: $$ \mathcal{L} = \sum_i p_i \log \left( q_{i-1} + q_i + q_{i+1} \right) + \sum_i \mu_i q_i -\lambda \left( \sum_i q_i - 1\right) $$ Se trata de un problema de optimización convexo en el que La condición de Slater tiene por lo tanto el Condiciones KKT son condiciones necesarias y suficientes para un óptimo. Condición de primer orden: $$ \frac{p_{i-1}}{q_{i-2} + q_{i-1} + q_{i}} + \frac{p_i}{q_{i-1} + q_i + q_{i+1}} + \frac{p_{i+1}}{q_{i} + q_{i+1} + q_{i+2}} = \lambda - \mu_i $$

Flojedad complementaria: $$\mu_i q_i = 0 $$ Y por supuesto $\mu_i \geq 0$ . (Según mis pruebas, parece que $\lambda = 1$ pero no veo inmediatamente por qué). $\mu_i$ y $\lambda$ son multiplicadores de Lagrange.

Solución si $q_i \geq 0$ nunca se vincula.

Entonces considere la solución

$$ p_i = \frac{q_{i-1} + q_i + q_{i+1}}{3} \quad \quad \mu_i = 0 \quad \quad \lambda = 1$$ Introduciendo la condición de primer orden, obtenemos $\frac{1}{3} + \frac{1}{3} + \frac{1}{3} = 1$ . Así que funciona (siempre y cuando $\sum_i q_i = 1$ y $q_i \geq 0$ también se satisfacen).

Cómo escribir el problema con matrices:

Dejemos que $\mathbf{p}$ y $\mathbf{q}$ sean vectores. Sea $A$ sea una matriz diagonal trilateral de unos. Por ejemplo, para $n = 5$

$$A = \left[\begin{array}{ccccc} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0& 0 \\ 0 & 1 & 1 & 1 & 0 \\0 &0 & 1 & 1&1\\ 0 &0 &0 & 1 & 1 \end{array} \right] $$

El problema se puede escribir con más notación matricial:

\begin {Ecuación} \begin {array}{*2{>{} \displaystyle }r}} \mbox {maximizar (sobre $\mathbf{q}$ )} & \mathbf {p}' \log\left (A \mathbf {q} \right ) \\ \mbox {sujeto a} & q_i \geq 0 \\ & \sum_i q_i = 1 \end {array} \end {Ecuación}

Esto se puede resolver rápidamente de forma numérica, pero no veo la manera de obtener una solución limpia de forma cerrada.

La solución se caracteriza por: $$A\mathbf{y} = \lambda - \mathbf{u} \quad \quad \mathbf{x} = A \mathbf{q} \quad \quad y_i = \frac{p_i}{x_i} $$ pero no veo cómo eso es terriblemente útil más allá de comprobar su software de optimización.

Código para resolverlo usando CVX y MATLAB

A = eye(n) + diag(ones(n-1,1),1) + diag(ones(n-1,1),-1);

cvx_begin
 variable q(n)
 dual variable u;
 dual variable l;
 maximize(p'*log(A*q))

 subject to:
  u: q >= 0;
  l: sum(q) <= 1;
cvx_end

Por ejemplo, las entradas:

p = 0.0724    0.0383    0.0968    0.1040    0.1384    0.1657    0.0279    0.0856    0.2614    0.0095

tiene solución:

q = 0.0000    0.1929    0.0000    0.0341    0.3886    0.0000    0.0000    0.2865    0.0979    0.0000

Solución que obtengo (azul) cuando tengo una tonelada de contenedores siguiendo básicamente el pdf normal (rojo): Otro problema más arbitrario:

Muy vagamente, para $p_{i-1} \approx p_i \approx p_{i+1}$ se obtiene $q_i \approx p_i$ pero si $p_i$ se mueve mucho, y se producen algunas cosas complicadas en las que la optimización trata de poner la masa en $q_i$ en la vecindad de $p_i$ masa, colocándola estratégicamente entre $p_i$ con masa.

Otro punto conceptual es que la incertidumbre en su previsión suavizará efectivamente su estimación de $p$ y una mayor suavidad $p$ tendrá una solución $q$ que está más cerca de $p$ . (Creo que es correcto.)

Answer 3

Si lo entiendo bien, no creo que esto tenga una solución de forma cerrada. O más aún, es al menos una especialización de un problema que no tiene forma cerrada.

La razón por la que digo esto es que es exactamente la probabilidad que aparece en el NPMLE para datos censurados por intervalos, siendo la especialización que todos los intervalos son de la forma $[X-1, X+1]$ . En general, el NPMLE es el maximizador de la función

$ \sum_{i = 1}^n \log(P(t_i \in [L_i, R_i]) )$

donde $t_i$ es el tiempo del evento para el sujeto $i$ donde todo lo que se sabe es que el evento ocurrió dentro del intervalo $[L_i, R_i]$ . Esto equivale exactamente a su problema, con $L_i = X_i-1$ y $R_i = X_i + 1$ .

En general, no se trata de una forma cerrada. Sin embargo, al menos un caso especial lo es; el de datos del estado actual o cuando todos los intervalos son de la forma $[0, c_i]$ o $[c_i, \infty)$ .

Dicho esto, ¡hay muchos algoritmos para resolver el NPMLE! Puedes ajustarlo usando R 's icenReg con el paquete ic_np (nota: soy el autor). Asegúrese de establecer la opción B = c(1,1) declarando que los intervalos están cerrados.

Tenga en cuenta que es no el caso de que la función $q$ que maximiza $E[q(X-1)+ ...]$ también maximiza $E[\log(q(X-1) + ...]$ . Como ejemplo trivial, supongamos $X_1 = 1, X_2 = 1, X_3 = 10$ . Entonces $q(1) = 1$ y 0 en caso contrario maximiza $E[q(X-1)+ ...]$ pero no está definido para $E[\log(q(X-1) + ...]$ .