La distancia del motor de tierra.

Distancia entre distribuciones de probabilidad

En informática, la distancia del motor de tierra ( EMD ) ^[1] es una medida de disimilitud entre dos distribuciones de frecuencia , densidades o medidas , en un espacio métrico D. Informalmente, si las distribuciones se interpretan como dos formas diferentes de amontonar tierra (tierra) sobre D , la DME captura el costo mínimo de construir la pila más pequeña usando tierra extraída de la más grande, donde el costo se define como la cantidad de tierra movida multiplicada por la distancia que se recorre.

La distancia del motor de tierra también se conoce como métrica de Wasserstein , métrica de Kantorovich - Rubinstein o distancia de Mallow . ^[2] Es la solución del problema de transporte óptimo , que a su vez también se conoce como problema de Monge - Kantorovich , o en ocasiones problema de transporte de Hitchcock - Koopmans ; ^[3] cuando las medidas son uniformes sobre un conjunto de elementos discretos, el mismo problema de optimización se conoce como emparejamiento bipartito de peso mínimo . ${\displaystyle W_{1}}$

Definiciones formales

La DME entre distribuciones de probabilidad y se puede definir como un mínimo sobre probabilidades conjuntas: ${\textstyle P}$ ${\textstyle Q}$

${\displaystyle {\text{EMD}}(P,Q)=\inf \limits _{\gamma \in \Pi (P,Q)}\mathbb {E} _{(x,y)\sim \gamma }\left[d(x,y)\right]\,}$

donde es el conjunto de todas las distribuciones conjuntas cuyos marginales son y . ${\displaystyle \Pi (P,Q)}$ ${\displaystyle P}$ ${\displaystyle Q}$

Por dualidad Kantorovich-Rubinstein , esto también se puede expresar como:

${\displaystyle {\text{EMD}}(P,Q)=\sup \limits _{\|f\|_{L}\leq 1}\,\mathbb {E} _{x\sim P}[f(x)]-\mathbb {E} _{y\sim Q}[f(y)]\,}$

donde el supremum se toma sobre todas las funciones continuas de 1-Lipschitz , es decir . ${\displaystyle \|\nabla f(x)\|\leq 1\quad \forall x}$

EMD entre firmas

En algunas aplicaciones, es conveniente representar una distribución como una firma o grupos de colección , donde el -ésimo grupo representa una masa centrada en . En esta formulación, considere firmas y . Sea la distancia del suelo entre grupos y . Entonces la DME entre y viene dada por el flujo óptimo , con el flujo entre y , que minimiza el costo total. ${\textstyle P}$ ${\textstyle i}$ ${\textstyle w_{i}}$ ${\textstyle p_{i}}$ ${\textstyle P=\{(p_{1},w_{p1}),(p_{2},w_{p2}),...,(p_{m},w_{pm})\}}$ ${\textstyle Q=\{(q_{1},w_{q1}),(q_{2},w_{q2}),...,(q_{n},w_{qn})\}}$ ${\textstyle D=[d_{i,j}]}$ ${\textstyle p_{i}}$ ${\textstyle q_{j}}$ ${\textstyle P}$ ${\textstyle Q}$ ${\textstyle F=[f_{i,j}]}$ ${\textstyle f_{i,j}}$ ${\textstyle p_{i}}$ ${\textstyle q_{j}}$

${\displaystyle \min \limits _{F}{\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}}$

sujeto a las restricciones:

${\displaystyle f_{i,j}\geq 0,1\leq i\leq m,1\leq j\leq n}$

${\displaystyle \sum _{j=1}^{n}{f_{i,j}}\leq w_{pi},1\leq i\leq m}$

${\displaystyle \sum _{i=1}^{m}{f_{i,j}}\leq w_{qj},1\leq j\leq n}$

${\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}=\min \left\{\ \sum _{i=1}^{m}w_{pi},\quad \sum _{j=1}^{n}w_{qj}\ \right\}}$

El flujo óptimo se encuentra resolviendo este problema de optimización lineal. La distancia del movimiento de tierras se define como el trabajo normalizado por el flujo total: ${\textstyle F}$

${\displaystyle {\text{EMD}}(P,Q)={\frac {\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}{\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}}}}$

Variantes y ampliaciones

Masa de probabilidad desigual

Algunas aplicaciones pueden requerir la comparación de distribuciones con diferentes masas totales. Un enfoque es permitir una coincidencia parcial , donde la suciedad de la distribución más masiva se reorganiza para hacer la menos masiva, y cualquier "suciedad" sobrante se descarta sin costo alguno. Formalmente, sea el peso total de y sea el peso total de . Tenemos: ${\textstyle w_{P}}$ ${\textstyle P}$ ${\textstyle w_{Q}}$ ${\textstyle Q}$

${\displaystyle {\text{EMD}}(P,Q)={\tfrac {1}{\min(w_{P},w_{Q})}}\inf \limits _{\gamma \in \Pi _{\geq }(P,Q)}\int d(x,y)\,\mathrm {d} \gamma (x,y)}$

donde es el conjunto de todas las medidas cuyas proyecciones son y . Tenga en cuenta que esta generalización de la DME no es una distancia real entre distribuciones, ya que no satisface la desigualdad del triángulo. ${\displaystyle \Pi _{\geq }(P,Q)}$ ${\displaystyle \geq P}$ ${\displaystyle \geq Q}$

Un enfoque alternativo es permitir la creación o destrucción de masa, a nivel global o local, como alternativa al transporte, pero con una penalización de costos. En ese caso hay que especificar un parámetro real , la relación entre el coste de crear o destruir una unidad de "suciedad" y el coste de transportarla por una unidad de distancia. Esto equivale a minimizar la suma del costo de movimiento de tierras más veces la distancia L ¹ entre la pila reordenada y la segunda distribución. La medida resultante es una función de distancia verdadera. ^[4] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle {\widehat {EMD}}_{\alpha }}$

Más de dos distribuciones

La DME puede extenderse naturalmente al caso en el que se comparan más de dos distribuciones. En este caso, la "distancia" entre las muchas distribuciones se define como el valor óptimo de un programa lineal. Esta DME generalizada se puede calcular exactamente utilizando un algoritmo codicioso, y se ha demostrado que el funcional resultante es aditivo de Minkowski y monótono convexo. ^[5]

Calcular la DME

La DME se puede calcular resolviendo una instancia de problema de transporte , utilizando cualquier algoritmo para el problema de flujo de costo mínimo , por ejemplo, el algoritmo simplex de red .

Se puede utilizar el algoritmo húngaro para obtener la solución si el dominio D es el conjunto {0, 1}. Si el dominio es integral, se puede traducir para el mismo algoritmo representando contenedores integrales como múltiples contenedores binarios.

Como caso especial, si D es una matriz unidimensional de "contenedores" de longitud n , la DME se puede calcular de manera eficiente escaneando la matriz y realizando un seguimiento de cuánta suciedad debe transportarse entre contenedores consecutivos. Aquí los contenedores están indexados a cero :

${\displaystyle {\begin{aligned}{\text{EMD}}_{0}&=0\\{\text{EMD}}_{i+1}&=P_{i}+{\text{EMD}}_{i}-Q_{i}\\{\text{Total Distance}}&=\sum _{i=0}^{n}|{\text{EMD}}_{i}|\end{aligned}}}$

Análisis de similitud basado en EMD

El análisis de similitud basado en EMD (EMDSA) es una herramienta importante y eficaz en muchas aplicaciones de recuperación de información multimedia ^[6] y reconocimiento de patrones ^[7] . Sin embargo, el costo computacional de EMD es supercúbico al número de "contenedores" dado un "D" arbitrario. Se han investigado técnicas de cálculo EMD eficientes y escalables para datos a gran escala utilizando MapReduce , ^{[8] [9]} , así como conjuntos de datos distribuidos resistentes, paralelos y síncronos en masa . ^[10]

Aplicaciones

Una de las primeras aplicaciones de EMD en informática fue comparar dos imágenes en escala de grises que pueden diferir debido a difuminado , desenfoque o deformaciones locales. ^[11] En este caso, la región es el dominio de la imagen y la cantidad total de luz (o tinta) es la "suciedad" que se va a reorganizar.

El EMD se utiliza ampliamente en la recuperación de imágenes basada en contenido para calcular distancias entre los histogramas de color de dos imágenes digitales . ^{[ cita necesaria ]} En este caso, la región es el cubo de color RGB y cada píxel de la imagen es una parcela de "suciedad". La misma técnica se puede utilizar para cualquier otro atributo cuantitativo de un píxel , como luminancia , gradiente , movimiento aparente en un fotograma de vídeo , etc.

De manera más general, el EMD se utiliza en el reconocimiento de patrones para comparar resúmenes genéricos o sustitutos de registros de datos llamados firmas. ^[1] Una firma típica consta de una lista de pares (( x ₁ , m ₁ ), ... ( x _n , m _n )), donde cada x _i es una determinada "característica" (por ejemplo, color en una imagen, letra en un texto, etc.), y m _i es "masa" (cuántas veces aparece esa característica en el registro). Alternativamente, x _i puede ser el centroide de un grupo de datos y m _i el número de entidades en ese grupo. Para comparar dos de estas firmas con el EMD, se debe definir una distancia entre características, que se interpreta como el costo de convertir una unidad de masa de una característica en una unidad de masa de la otra. La DME entre dos firmas es entonces el coste mínimo de convertir una de ellas en la otra.

El análisis EMD se ha utilizado para cuantificar cambios multivariados en biomarcadores medidos mediante citometría de flujo , con aplicaciones potenciales a otras tecnologías que informan distribuciones de mediciones. ^[12]

Historia

El concepto fue introducido por primera vez por Gaspard Monge en 1781, ^[13] en el contexto de la teoría del transporte . El uso del EMD como medida de distancia para imágenes monocromáticas fue descrito en 1989 por S. Peleg, M. Werman y H. Rom. ^[11] El nombre "distancia del movimiento de tierras" fue propuesto por J. Stolfi en 1994, ^[14] y fue utilizado en forma impresa en 1998 por Y. Rubner, C. Tomasi y LG Guibas . ^[15]

Ver también

• Ecuación de Monge-Ampere

Referencias

1. Rubner, Y.; Tomasi, C.; Guibas, LJ (1998). "Una métrica para distribuciones con aplicaciones a bases de datos de imágenes". Sexta Conferencia Internacional sobre Visión por Computadora (IEEE Cat. No.98CH36271) . Editorial Narosa. págs. 59–66. doi :10.1109/iccv.1998.710701. ISBN 81-7319-221-9. S2CID  18648233.
2. CL Malvas (1972). "Una nota sobre la normalidad articular asintótica". Anales de estadística matemática . 43 (2): 508–515. doi : 10.1214/aoms/1177692631 .
3. Singiresu S. Rao (2009). Optimización de ingeniería: teoría y práctica (4ª ed.). John Wiley e hijos. pag. 221.ISBN​ 978-0-470-18352-6.
4. Pelé, Ofir; Werman, Michael (2008). "Una métrica de histograma de tiempo lineal para mejorar la coincidencia SIFT". Visión por Computador – ECCV 2008 . Apuntes de conferencias sobre informática. vol. 5304. Springer Berlín Heidelberg. págs. 495–508. doi :10.1007/978-3-540-88690-7_37. eISSN  1611-3349. ISBN 978-3-540-88689-1. ISSN  0302-9743.
5. Kline, Jeffery (2019). "Propiedades del problema del motor de tierra d-dimensional". Matemática Aplicada Discreta . 265 : 128-141. doi : 10.1016/j.dam.2019.02.042 . S2CID  127962240.
6. Mark A. Ruzón; Carlo Tomasi (2001). "Detección de bordes, cruces y esquinas mediante distribuciones de color". Transacciones IEEE sobre análisis de patrones e inteligencia artificial .
7. Kristen Grauman; Trevor Darrel (2004). "Coincidencia rápida de contornos utilizando la distancia aproximada del transportador". Actas de CVPR 2004 .
8. Jin Huang; Rui Zhang; Rajkumar Buyya; Jian Chen (2014). "MELODY-Join: uniones de similitud de distancia de Earth Mover eficiente utilizando MapReduce". Actas de la Conferencia Internacional IEEE sobre Ingeniería de Datos .
9. Jia Xu; Bin Lei; Yu Gu; Winslett, M.; Ge Yu; Zhenjie Zhang (2015). "Unión de similitud eficiente basada en la distancia de Earth Mover utilizando MapReduce". Transacciones IEEE sobre conocimiento e ingeniería de datos .
10. Jin Huang; Rui Zhang; Rajkumar Buyya; Jian Chen, M.; Yongwei Wu (2015). "Heads-Join: Unión a distancia de Earth Mover eficiente en Hadoop". Transacciones IEEE en sistemas paralelos y distribuidos .
11. S. Peleg; M. Werman; H. Rom (1989). "Un enfoque unificado para el cambio de resolución: espacio y nivel de grises". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 11 (7): 739–742. doi :10.1109/34.192468. S2CID  18415340.
12. Orlova, DY; Zimmerman, N; Meehan, C; Meehan, S; Aguas, J; Ghosn, EEB (23 de marzo de 2016). "Distancia del Earth Mover (EMD): una verdadera métrica para comparar los niveles de expresión de biomarcadores en poblaciones celulares". Más uno . 11 (3): e0151859. Código Bib : 2016PLoSO..1151859O. doi : 10.1371/journal.pone.0151859 . PMC 4805242 . PMID  27008164. 
13. "Mémoire sur la théorie des déblais et des remblais". Histoire de l'Académie Royale des Science, Année 1781, con les Mémoires de Mathématique et de Physique . 1781.
14. J. Stolfi, comunicación personal a LJ Guibas, 1994, citado por Rubner, Yossi; Tomasi, Carlo; Guibas, Leónidas J. (2000). "La distancia del transportador de tierras como métrica para la recuperación de imágenes" (PDF) . Revista Internacional de Visión por Computadora . 40 (2): 99-121. doi :10.1023/A:1026543900054. S2CID  14106275.
15. Yossi Rubner; Carlos Tomasi; Leónidas J. Guibas (1998). "Una métrica para distribuciones con aplicaciones a bases de datos de imágenes". Sexta Conferencia Internacional sobre Visión por Computadora (IEEE Cat. No.98CH36271) . págs. 59–66. doi :10.1109/ICCV.1998.710701. ISBN 81-7319-221-9. S2CID  18648233.{{cite book}}: Mantenimiento CS1: fecha y año ( enlace )

enlaces externos

• Código C para la distancia del Earth Mover (archivado aquí)
• Implementación de Python con referencias.
• Envoltorio Python2 para la implementación en C de Earth Mover's Distance
• Código contenedor C++, Matlab y Java para Earth Mover's Distance, especialmente eficiente para distancias terrestres con umbrales
• Implementación en Java de un generador genérico para evaluar el análisis de similitud basado en la distancia de Earth Mover a gran escala
• Demostración de la aditividad de Minkowski, la monotonicidad convexa y otras propiedades de la distancia de los Earth Movers