En límites de probabilidad de error en la prueba de hipótesis de Bayesiano

Question

En el Bayesiano versión de (binario) de la prueba de hipótesis que uno tiene que decidir a cual de las dos hipótesis de $A$ $B$ es cierto. Las dos hipótesis son dadas antes de probabilidad $p(A)$$p(B)$, que se suma a 1. $A$ $B$ inducir dos distribuciones de probabilidad sobre un conjunto de posibles observaciones $X$, decir $p(x|A)$$p(x|B)$. Uno de ellos tiene dos decidir entre el $A$ $B$ después de mirar una observación $x$.

Se sabe que la mejor estrategia, que es la que minimiza la probabilidad de uncorrect adivinar, es elegir la hipótesis de $H\in\{A,B\}$ que maximiza el $p(H|x)$ donde $x$ es la observación. La probabilidad de error de la media en todas las $x$$H$) puede ser expresado

$$P_e = 1-\sum_x \max( p(x|A)p(A), p(x|B)p(B))\tag{1}$$

La expresión (1) se considera a menudo como 'intratables', debido a la presencia de la máxima operador. Por lo tanto manejable límites son los que buscas. Un ejemplo es el armónico más bajo-bound

$$P_e \geq E_x[P(A|x)P(B|x)]\tag{2}$$

($E_x$ es la expectativa sobre $x$; véase por ejemplo : Routtenberg, Tabrikian, "Una Clase General de los Límites Inferiores de la Probabilidad de Error en Múltiples Pruebas de Hipótesis", http://arxiv.org/abs/1005.2880de Mayo de 2010, y referencias incluidas).

Mis preguntas:

1) ¿En qué sentido son expresiones como el lado derecho de (2) "más manejable" que (1)? Computacionalmente, que todavía requieren de la integración (funciones) de los PMF$p(x|A)$$p(x|B)$. Tal vez la más conveniente desde el punto de vista analítico?

2) Una exacta y expresiones simples para $P_e$ es:

$$P_e = 1-\frac{||p(\cdot|A)p(A) - p(\cdot|B)p(B)||_1 + 1}2\tag{3}$$

(Aquí se $p(\cdot|H)$ es visto como un vector en un $R^{|X|}$, e $||\cdot||_1$ denota la norma-1).

Esto es conceptualmente interesante porque relaciona la probabilidad de error a una distancia entre PMF. Es esta expresión considerado como "intratables" en el mismo sentido de (1)?

M.

Answer 1

Se sabe que la mejor estrategia, que es la que minimiza la probabilidad de uncorrect adivinar, es elegir la hipótesis de $H \in \{A,B\}$ que maximiza el $p(H|x)$ donde $x$ es la observación.

Como pone de mal humor, no me gusta esta declaración en particular porque en mi la mente oculta lo que realmente está pasando, y hace lo que debería ser obvio en lugar oscuro. Por desgracia, tales Olímpico pronunciamientos son lo un montón de gente a tomar distancia de un curso de métodos Bayesianos....

Supongamos que la observación de $X$ es una variable aleatoria discreta. Observamos que, en el caso de $\{X = x\}$ se ha producido y la necesidad de decidir elegir entre $A$ o $B$. Pero el evento observado puede ser con particiones en $\{X = x, A\}$ $\{X = x, B\}$ y tenemos que $$p(x) = p(X=x, A) + p(X=x, B).$$ Ahora, uno de los dos eventos, $\{X = x, A\}$ $\{X = x, B\}$ ha se ha producido. Claramente si elegimos $A$ tras la observación de $\{X = x\}$, estamos correcta con probabilidad de $p(X=x, A)$ e incorrecta con probabilidad de $p(X=x, B)$, mientras que si elegimos $B$ tras la observación de $\{X = x\}$, estamos correcta con probabilidad de $p(X=x, B)$ e incorrecta con probabilidad de $p(X=x, A)$. Así, la probabilidad de ser incorrecta en esta instancia se minimiza si elegimos $A$ si $p(X=x, B) < p(X=x, A)$ y elija $B$ si $p(X=x, B) > p(X=x, A)$. Por lo tanto, si $E$ $C$ el valor de los acontecimientos de la decisión de estar en error y de ser correcto, respectivamente, tenemos que si el óptimo (mínima probabilidad de error) decisión se toma después de observar $\{X=x\}$, tales ocurrencias contribuir $\max\{p(X=x, A), p(X=x, B)\}$$P(C)$, y $\min\{p(X=x, A), p(X=x, B)\}$ $P(E)$. Tenemos $$\begin{align*} P(E) &= \sum_x \min\{p(X=x, A), p(X=x, B)\}\\ &= 1 - P(C)\\ &= 1 - \sum_x \max\{p(X=x, A), p(X=x, B)\} \end{align*}$$ Desde $p(X=x, A) = p(x|A)P(A)$$p(X=x, B) = p(x|B)P(B)$, se puede escribir $$\begin{align*} P(E) &= 1 - \sum_x \max\{p(x|A)P(A), p(x|B)P(B)\}\\ &= 1 - \sum_x \max\left\{\frac{p(x|A)P(A)}{p(x)}, \frac{p(x|B)P(B)}{p(x)}\right\}p(x)\\ &= 1 - E_x\left[\max\{P(A|x),P(B|x)\}\right]\\ &= E_x\left[\min\{P(A|x),P(B|x)\}\right] \end{align*}$$ donde $E_x$ denota la expectativa con respecto a $x$. Como alternativa, desde $$ \max\{p,q\} = \frac{p+p+|p-q|}{2}, $$ tenemos $$\begin{align*} P(E) &= 1 - \sum_x \max\{p(x,A), p(x,B)\}\\ &= 1 - \sum_x \frac{p(x,A) + p(x,B)+ |p(x,A) - p(x,B)|}{2}\\ &= 1 -\frac{P(A) + P(B)}{2} - \sum_x \frac{|p(x,A) - p(x,B)|}{2}\\ &= 1 - \frac{1 + \sum_x |p(x|A)P(A) - p(x|B)P(B)|}{2}\\ &= 1 - \frac{||p(\cdot|A)p(A) - p(\cdot|B)p(B)||_1 + 1}2 \end{align*}$$ como OP Michele escribe. Finalmente, para $p, q \in [0,1]$, $\min\{p, q\} \geq pq$ , por lo que $$\begin{align*} P(E) &= E_x\left[\min\{P(A|x),P(B|x)\}\right]\\ &\geq E_x\left[P(A|x)P(B|x)\right]. \end{align*}$$

En resumen, las tres expresiones para $P(E)$ aparecen diferentes, pero están basados en la misma idea fundamental. Los tres requieren el cálculo de una expectativa con respecto a $x$, y se diferencian muy poco computacional de la complejidad. Simplificaciones puede ser hecho, si algo específico es lo que se sabe acerca de las variables, por ejemplo, $X$ es un geométrica variable aleatoria con diferentes parámetros en las dos hipótesis, en cuyo caso se podría calcular algunas sumas analíticamente en lugar de numéricamente, pero parecería que se aplican igualmente en los tres casos. Veo muy poca diferencia en términos de tratabilidad computacional en (1)-(3) como se muestra en el OP pregunta.

Answer 2

Al $p(A) = p(B) = 1/2$, la ecuación de $(3)$ es básicamente calcular el total de la variación de la distancia (también conocida como la variación de la distancia, para abreviar). La variación de la distancia es un ${\cal L}_1$ distancia entre dos medidas de probabilidad, que es la razón por la ${\cal L}_1$ norma aparece en la ecuación de $(3)$.

Es bien sabido que la variación de la distancia representa un límite inferior en la suma de $\Pr[\text{type I error}] + \Pr[\text{type II error}]$ para las pruebas de hipótesis método, y este límite estricto para la prueba de hipótesis el método que se describe. Por lo tanto, la variación de las medidas de distancia el mínimo alcanzable de la tasa de error de la prueba de hipótesis (de nuevo, al $p(A) = p(B) = 1/2$).

Sin embargo, como se indicó, la variación de la distancia puede ser difícil de calcular. Es particularmente molesto para lidiar con ellos, si podemos tener varias observaciones independientes de la distribución subyacente. Imagina que un árbitro secreto tira una moneda para decidir si usar o $A$ o $B$; luego le da $n$ independiente se nutre de $p(x|A)$ (si se está utilizando un $A$) o $n$ independiente se nutre de $p(x|B)$ (si se está utilizando un $B$), sin contar que. Su trabajo es decidir si está usando $A$ o $B$. ¿Cuál es la tasa de error de la decisión óptima procedimiento para $n>1$, y en relación a la tasa de error para el caso de que $n=1$? Esta pregunta es de difícil respuesta. No es fácil relacionar la variación de la distancia de la $n$-observación problema (el producto de la medida, donde $n>1$) a la variación de la distancia de la sola observación de casos.

Una manera en que las personas a lidiar con esto en la práctica es buscar en otra parte la distancia métrica, como la divergencia KL o $\chi^2$ o algo, que se comporta bien con medidas del producto: es decir, a cierta distancia métrica donde podemos limpiamente se refieren a la distancia por el $n$-observación de caso para la $1$-observación de casos (donde podemos limpiamente relacionan la medida de distancia de un producto a medida para el pie para la distribución subyacente). A continuación, utilizamos algunos obligado que se refiere que la distancia métrica a la variación de la distancia, y Bob nuestro tío.

Para más información sobre este tema, lea la prueba de Hipótesis y el total de la variación de la distancia frente de Kullback-Leibler divergencia y ¿Cuál es la relación de ${\cal L}_1$ (la variación total) distancia a la prueba de hipótesis?