Distancia de la excavadora

Distancia entre distribuciones de probabilidad

En informática, la distancia del movimiento de tierra ( EMD ) ^[1] es una medida de disimilitud entre dos distribuciones de frecuencia , densidades o medidas , sobre un espacio métrico D. De manera informal, si las distribuciones se interpretan como dos formas diferentes de apilar tierra (suciedad) sobre D , la EMD captura el costo mínimo de construir la pila más pequeña usando tierra tomada de la más grande, donde el costo se define como la cantidad de tierra movida multiplicada por la distancia sobre la que se mueve.

En distribuciones de probabilidad, la distancia del movimiento de tierra también se conoce como métrica de Wasserstein , métrica de Kantorovich - Rubinstein o distancia de Mallows . ^[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 EMD entre distribuciones de probabilidad y puede definirse como un ínfimo 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 la 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 supremo 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 una colección de grupos , donde el -ésimo grupo representa una característica de masa centrada en . En esta formulación, considere las firmas y . Sea la distancia terrestre entre los grupos y . Entonces, la EMD entre y está dada por el flujo óptimo , con el flujo entre y , que minimiza el costo general. ${\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 caudal óptimo se obtiene resolviendo este problema de optimización lineal. La distancia recorrida por la excavadora se define como el trabajo normalizado por el caudal 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 extensiones

Masa de probabilidad desigual

Algunas aplicaciones pueden requerir la comparación de distribuciones con diferentes masas totales. Un enfoque es permitir la coincidencia parcial , ^[1] donde la suciedad de la distribución más masiva se reorganiza para hacer la menos masiva, y cualquier "suciedad" restante se descarta sin costo. 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 . Nótese que esta generalización de EMD no es una distancia verdadera entre distribuciones, ya que no satisface la desigualdad triangular. ${\displaystyle \Pi _{\geq }(P,Q)}$ ${\displaystyle \geq P}$ ${\displaystyle \geq Q}$

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

Más de dos distribuciones

La EMD se puede extender naturalmente al caso en 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 EMD generalizada se puede calcular exactamente utilizando un algoritmo voraz, y se ha demostrado que la función resultante es aditiva de Minkowski y monótona convexa. ^[5]

Cálculo del EMD

La EMD 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 .

El algoritmo húngaro se puede utilizar 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 los intervalos integrales como intervalos binarios múltiples.

Como caso especial, si D es una matriz unidimensional de "contenedores" de longitud n , la EMD se puede calcular de manera eficiente escaneando la matriz y haciendo un seguimiento de la cantidad de suciedad que se debe transportar entre contenedores consecutivos. Aquí, los contenedores tienen un índice 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 "bins" dado un "D" arbitrario. Se han investigado técnicas de cálculo de EMD eficientes y escalables para datos a gran escala utilizando MapReduce ^{[8] [9]} así como conjuntos de datos distribuidos , síncronos, paralelos y resilientes en masa ^[10] .

Aplicaciones

Una de las primeras aplicaciones del EMD en la informática fue comparar dos imágenes en escala de grises que pueden diferir debido al tramado , el desenfoque o las 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 debe 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 requerida ]} 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 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 consiste en una lista de pares (( x ₁ , m ₁ ), ... ( x _n , m _n )), donde cada x _i es una cierta "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 esas firmas con el EMD, uno debe definir una distancia entre las 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. El EMD entre dos firmas es entonces el costo mínimo de convertir una de ellas en la otra.

El análisis EMD se ha utilizado para cuantificar cambios multivariados en biomarcadores medidos por citometría de flujo , con posibles aplicaciones 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 de la máquina excavadora" fue propuesto por J. Stolfi en 1994, ^[14] y fue utilizado en forma impresa en 1998 por Y. Rubner, C. Tomasi y LG Guibas . ^[1]

Véase también

• Ecuación de Monge-Ampère

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 Computador (IEEE Cat. No.98CH36271) . Narosa Publishing House. págs. 59–66. doi :10.1109/iccv.1998.710701. ISBN 81-7319-221-9. Número de identificación del sujeto  18648233.
2. CL Mallows (1972). "Una nota sobre normalidad conjunta 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 & Sons. pág. 221. ISBN 978-0-470-18352-6.
4. Pele, Ofir; Werman, Michael (2008). "Una métrica de histograma de tiempo lineal para mejorar la correspondencia SIFT". Visión artificial – ECCV 2008. Apuntes de clase en informática. Vol. 5304. Springer Berlin 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 movimiento de tierra de dimensión d". Matemáticas Aplicadas Discretas . 265 : 128–141. doi : 10.1016/j.dam.2019.02.042 . S2CID  127962240.
6. Mark A. Ruzon; Carlo Tomasi (2001). "Detección de bordes, uniones y esquinas mediante distribuciones de color". Transacciones IEEE sobre análisis de patrones e inteligencia artificial .
7. Kristen Grauman; Trevor Darrel (2004). "Correspondencia rápida de contornos utilizando la distancia aproximada de la excavadora". Actas de CVPR 2004 .
8. Jin Huang; Rui Zhang; Rajkumar Buyya; Jian Chen (2014). "MELODY-Join: uniones por similitud de distancias de máquinas de movimiento de tierras eficientes mediante 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 la excavadora 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 eficiente de Earth Mover en Hadoop". Transacciones IEEE sobre 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 gris". IEEE Transactions on Pattern Analysis and Machine Intelligence . 11 (7): 739–742. doi :10.1109/34.192468. S2CID  18415340.
12. Orlova, DY; Zimmerman, N; Meehan, C; Meehan, S; Waters, J; Ghosn, EEB (23 de marzo de 2016). "Distancia de la excavadora (EMD): una verdadera métrica para comparar los niveles de expresión de biomarcadores en poblaciones celulares". PLOS One . 11 (3): e0151859. Bibcode :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 con LJ Guibas, 1994, citado por Rubner, Yossi; Tomasi, Carlo; Guibas, Leonidas J. (2000). "La distancia de la excavadora como métrica para la recuperación de imágenes" (PDF) . Revista Internacional de Visión por Computador . 40 (2): 99–121. doi :10.1023/A:1026543900054. S2CID  14106275.

Enlaces externos

• Código C para la distancia del Earth Mover (archivado aquí)
• Implementación de Python con referencias
• Envoltorio de Python2 para la implementación en C de la distancia de Earth Mover
• Código de envoltura C++, Matlab y Java para la distancia del Earth Mover, especialmente eficiente para distancias terrestres con umbral
• Implementación en Java de un generador genérico para evaluar el análisis de similitud basado en la distancia de una máquina de movimiento de tierras a gran escala
• Demostración de la aditividad de Minkowski, la monotonía convexa y otras propiedades de la distancia de Earth Movers