[정리] Earth mover's distance

Earth mover's distance는 여기저기서 은근히 많이 나오네요. Wasserstein distance랑 혼용되기도 하는데, 정확히 말하면 같지는 않습니다.

 

우선 earth mover's distance는 두 개의 분포 사이의 거리를 측정하는 함수입니다 (하지만 metric / distance function이 되려면 조건이 붙습니다). Earth mover's distance라고 불리는 유례는 대략적으로 다음과 같습니다. Earth (흙)을 두 가지 분포로 쌓는 방법이 있다고 하면 분포 1에서 분포 2로 흙을 옮길 때 드는 노력을 (흙의 양) x (흙을 옮긴 거리)의 합이라고 합시다. Earth mover's distance는 이런 경우 최소의 노력이 됩니다. 

 

이제 수학적으로 정의를 적어봅시다

m개의 점 \( p_i \)가 각각 무게 \( w_i \)를 갖고 는 분포를 P 라고 하자 (signature이라고 부른다): \( P={(p_1,w_{p1}), ..., (p_m,w_{pm})} \). 비슷하게 n개의 점을 갖는 분포 \( Q={(q_1,w_{q1}), ..., (q_n,w_{qn})} \) 가 있다고 하자. 참고로 여기서 P와 Q의 총 무게와 점의 수가 달라도 상관없다. 점 \( p_i\)와 \( q_j\)의 거리를 \(d_{ij}\)라고 하자 (행렬로 표현하면 D라고 표기). 이 두 분포의 earth mover's distance는 다음과 같이 정의된다. (밑에서 \( F\) 는 \( f_{ij}\)로 이뤄진 행렬):

우선 \( \min_{F} \sum_{i,j} f_{ij} d_{ij} \)을  만족시키는 \(F \)를 찾는다.  여기서 몇 가지 조건을 만족해야 한다:

(i) \( f_{ij} \ge0 \) for all i, j. f는 flow라고 부르며 무게를 \( p_i \)에서 \( q_j \)로 얼마나 옮겼는지로 해석할 수 있다

(ii) \(\sum_j f_{ij} \le w_{pi} \) for all i. \( p_i \)에서 빠져나가는 flow는 \( p_i \)의 무게를 초과하지 않는다.

(iii)  \(\sum_i f_{ij} \le w_{qj} \) for all j. \( q_j \)로 공급되는 flow는 \( q_j\)의 무게를 초과하지 않는다.

(iv)  \( \sum_{ij} f_{ij} = \min( \sum_i w_{pi}, \sum_j w_{qj}) \). 총 flow는 P의 무게와 Q의 무게 중 적은 쪽과 같다.

이런 \( F \)를 구하면  earth mover's distance는 다음과 같이 정의된다:

\[ EMD(P,Q) = \frac{\sum_{ij} f_{ij} d_{ij}}{\sum_{ij}f_{ij}}\]

 

이제 여기서 P와 Q의 무게가 서로 같고 편의상 이 무게가 1이라고 가정하자. 그러면 (iv)는 

(iv')  \( \sum_{ij} f_{ij} = \sum_i w_{pi} = \sum_j w_{qj} = 1\)

로 바뀐다. 조금 생각해 보면 이것이 만족되려면 (ii)와 (iii)도 부등호가 아니라 등호여야하는 것을 알 수 있다. 이런 상황에서는 earth mover's distance는 Wasserstein-1 distance  \( W_1\) 와 같다:

\[ W_1(P,Q) = \min_F \sum_{i,j} f_{ij} d_{ij}\]

여기서 다음을 만족한다:

(i') \( f_{ij} \ge0 \) 

(ii') \(\sum_j f_{ij} = w_{pi} \) for all i

(iii')  \(\sum_i f_{ij} = w_{qj} \) for all j

(iv')  \( \sum_{ij} f_{ij} = \sum_i w_{pi} = \sum_j w_{qj} = 1\)

여기서 추가로 D가 metric distance matrix(https://en.wikipedia.org/wiki/Distance_matrix)이면 \( W_1 \)도 metric의  조건을 만족한다 (https://en.wikipedia.org/wiki/Metric_space)

참고 자료:

Levina et al "The Earth Mover's Distance is the Mallows Distance: Some insights from Statistics"

Rubner et al "The Earth Mover's Distance as a Metric for Image Retrieval"