アースムーバー距離

アースムーバー距離（アースムーバーきょり、英: Earth Mover's Distance, EMD）は、密度関数、度数分布、または測度の間の類似度を評価するための距離関数であり、計量空間 D 上に定義される。  

直感的には、分布を「土を積み上げた山」と見なすとき、一方の分布からもう一方を作るのに必要な最小の「労力」を表す。ここでの労力は、移動させた土の量と、それを動かした距離の積として定義される^[1]。

確率分布間におけるEMDは、ワッサースタイン距離 ${\displaystyle W_{1}}$、カントロヴィッチ-ルビンシュタイン距離、またはモローズ距離（Mallows distance）としても知られている^[2]。

これは最適輸送問題の解として定式化されており、モンジュ-カントロヴィッチ問題とも呼ばれる。また、離散的な要素の上で定義される場合、最小重み二部マッチング問題と等価である^[3]。

定義

確率分布 ${\displaystyle P}$, ${\displaystyle Q}$ に対し、EMDは以下のように定義される：

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

ここで ${\displaystyle \Pi (P,Q)}$ は、${\displaystyle P}$ および ${\displaystyle Q}$ を周辺分布とする結合分布全体の集合である。

カントロヴィッチ-ルビンシュタイン双対性を用いると、以下のようにも表せる：

${\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)]\,}$

ここで上限は全ての1-リプシッツ連続関数 ${\displaystyle f}$ にわたって取られる（すなわち ${\displaystyle \|\nabla f(x)\|\leq 1\quad \forall x}$.）

シグネチャ間のEMD

一部の応用では、分布${\textstyle P}$を「シグネチャ」すなわち質量付きクラスタの集合として表現するのが便利である。たとえば：${\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 p_{i}}$ と${\textstyle q_{j}}$の距離を ${\textstyle D=[d_{i,j}]}$ とすると、全体のコストを最小化するようなフロー ${\textstyle F=[f_{i,j}]}$ を求めて次のように定義する：

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

制約条件は：

${\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\}}$

EMDは以下のように定義される：

${\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}}}}$

拡張と変種

質量が異なる場合

${\displaystyle P}$ と ${\displaystyle Q}$ の全体質量が異なる場合、部分一致を許すことで対応できる^[1]。

以下のように定式化される：

${\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)}$

ここで ${\displaystyle \Pi _{\geq }(P,Q)}$ は、${\displaystyle P}$ および ${\displaystyle Q}$ 以上の測度を持つ結合測度全体。 また、土の「生成・消失」を許し、その際にペナルティコスト ${\displaystyle \alpha }$ を加えることで、真の距離関数を定義できる^[4]。

多分布間のEMD

EMDは2つ以上の分布に拡張することもできる。このとき、複数分布の「距離」は線形計画問題の最適解として定義され、Minkowski加法性と単調性を持つことが知られている^[5]。

EMDの計算

EMDは輸送問題として定式化され、最小費用流問題のアルゴリズム（たとえばネットワーク単体法）で解ける。

特別な場合として、1次元のヒストグラムにおけるEMDは以下のように効率的に計算できる：

${\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}}}$

応用

EMDは画像検索における類似度計算や、パターン認識でのシグネチャ間の比較に用いられる。^[1]  

また、フローサイトメトリーなどのバイオマーカー比較にも応用されている^[6]。