¿Cómo se puede calcular numéricamente la Tierra de la empresa de mudanzas distancia (EMD)?

Question

Yo estaba tratando de calcular numéricamente (escribir un programa) en el que se calcula el EMD para dos de distribución de probabilidad de $p_X$$q_X$. Sin embargo, tuve un tiempo difícil encontrar un esquema de cómo exactamente calcular dicha distancia.

Me preguntaba si existía una forma cerrada ecuación para EMD o si existía un esquema de un algoritmo para calcular.

De igual manera, es muy compacto ecuación para decir, el KL-divergencia $D(p_X||q_X) = \sum_{x \in X}p_X(x) log\frac{p_X(x)}{q_X(x)}$

Hay una ecuación para EMD o un algoritmo para la EMD de tal manera que puede ser fácilmente calculada numéricamente?

Lo que me he encontrado hasta ahora es la siguiente, que $EMD(p_X,q_X)$ entre las distribuciones $p_X$ $q_X$ es:

$$EMD(P,Q) = \frac{\sum^m_{i=1}\sum^n_{j=1} f_{ij}d_{ij}}{\sum^m_{i=1}\sum^b_{j=1} f_{ij}}$$

Sin embargo, para encontrar $d_{ij}$ uno necesita definir la medida de distancia supongo y para encontrar $f_{ij}$ uno necesita para resolver el transporte de programación lineal se define en:

http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RUBNER/emd.htm#RUBNER98A

No hay una solución para el problema de transporte de tal manera que hay una manera fácil de evaluar EMD?

También, he encontrado una wikipedia sección para calcular pero, el pseudo-código era ambiguo para mí entender cómo calcular el EMD. Si alguien entiende que la sección mejor y se puede explicar, sería impresionante!

Aquí está el enlace

http://en.wikipedia.org/wiki/Earth_mover's_distance

o usted sólo puede ver el pseudo-código de derecho aquí:

El Pseudo-código/wikipedia sección:

Si el dominio D es discreto, el EMD puede ser calculada mediante la resolución de una instancia del problema del transporte, que puede ser resuelto por el llamado algoritmo húngaro. En particular, si D es una matriz unidimensional de "papeleras", el EMD puede ser calculada de manera eficiente mediante el escaneo de la matriz y mantener un seguimiento de la cantidad de tierra necesita ser transportado entre consecutivos papeleras. Por ejemplo:

$EMD_0 = 0 \\$

$EMD_{i+1} = ( A_i + EMD_i ) - B_i \\$

$TotalDistance = \sum | EMD_i | \\$

Supongo que lo que no entiendo es lo $A_i$ $B_i$ son y cuando el algoritmo incluso deja de funcionar. Solo para claro para mí lo que se va haciendo y supongo que no entiendo EMD lo suficientemente bien como para derivar a mí mismo (Si pudiera me haría!)

---

Como una extensión de mi pregunta, es un problema si el espacio muestral para las distribuciones de probabilidad es infinito?

---

Yo probablemente no va a aceptar la respuesta de que no son tan generales como sea posible, pero una respuesta que se aclare a qué artículo de la wikipedia está tratando de decir, definitivamente obtener una votación.

Answer 1

En el discreto algoritmo que usted cita, $A_i$ parece ser la cantidad "de la tierra" en la posición $i$ en la primera distribución y $B_i$ la cantidad "de la tierra" en la posición $i$ en el segundo de distribución, con $i$ toma los valores de los enteros no negativos. El algoritmo como se indicó necesidades de un solo paso, y mientras las dos cantidades totales "de la tierra" son los mismos, y los rangos de las distribuciones están delimitadas, el algoritmo terminará.

Para las dos distribuciones de probabilidad en los números reales, donde el total de las cantidades "de probabilidad" son cada una de las $1$, por definición, supongamos que sus funciones de distribución acumulativa se $F_a(x)$$F_b(x)$. A continuación, la Tierra de la empresa de Mudanzas Distancia se convierte en $$\int_{x=-\infty}^{\infty} |F_a(x) - F_b(x)|\, dx . $$

Si las dos distribuciones tienen densidades $f_a(x)$ $f_b(x)$ esto es equivalente a $$\int_{x=-\infty}^{\infty} \left|\int_{y=-\infty}^x(f_a(y) - f_b(y))\,dy\,\right|\, dx.$$

Como Niels Diepeveen dice en los comentarios, esto cambia con las distribuciones en otros espacios métricos, pero me da la impresión de que usted no se pregunta acerca de eso.