アースムーバー距離

アースムーバー距離（Earth Mover's Distance, EMD）は、確率分布や度数分布、さらには測度間の類似性を評価するために使用される距離関数です。広く受け入れられている直感的な理解として、EMDは、分布を「土を積み上げた山」と捉え、一方の分布から他方の分布を形成する際に必要な最小の「労力」を表します。この場合の労力は、動かした土の量とその移動距離の積として定義されます。

EMDは、ワッサースタイン距離の一種とされ、カントロヴィッチ-ルビンシュタイン距離やモローズ距離（Mallows distance）とも関連付けられています。これは、最適輸送問題に基づくもので、モンジュ-カントロヴィッチ問題とも呼ばれています。また、離散的なデータに対しては、最小重み二部マッチング問題としても表現されます。

定義

EMDは、確率分布PとQに対して次のように定義されます。EMD(P,Q)は、PとQを周辺分布とする結合分布の間で最小化される期待値を求めるものです。この式を用いて、分布間の距離を計算することができます。

```math
ext{EMD}(P,Q)= ext{inf}_{ ext{γ} ext{ in } ext{Π}(P,Q)}[ ext{E}_{(x,y) ext{ from } γ}[d(x,y)]]
```

ここで、Π(P,Q)はPとQの間に存在する結合分布を示します。さらに、カントロヴィッチ-ルビンシュタインの双対性を利用することで、EMDは次のように表現することも可能です。

```math
ext{EMD}(P,Q)= ext{sup}_{ ext{f} ext{ with } ext{L-norm} ext{ ≤ 1}}[ ext{E}_{x ext{ from } P}[f(x)] - ext{E}_{y ext{ from } Q}[f(y)]]
```

ここで、上限は全ての1-リプシッツ連続関数fに対して取られます。

シグネチャ間のEMD

一部の応用において、分布Pを質量付きクラスタの集合として扱うことが有用です。この場合、分布PとQはそれぞれのクラスタ(ピース)における位置pとq、そしてその質量wを持つペアとして表されます。クラスタ間の距離をDとして、全体のコストを最小化するフローFを求めることができます。

拡張と変種

異なる質量のPとQが存在する場合、部分一致を許すことでEMDを定義することができます。このバージョンは次のように記述されます。

```math
ext{EMD}(P,Q)={ frac {1}{ ext{min}(w_{P},w_{Q})}} ext{inf}_{ ext{γ in } ext{Π}_ ext{≥}(P,Q)} ext{∫ d(x,y) dγ(x,y)}
```

EMDの計算

EMDは輸送問題として構成されており、最小費用流のアルゴリズムを用いれば解決できます。特に、1次元のヒストグラムにおけるEMDは、特定の効率的な方法によって計算でき、全体の距離が明示的に求められます。

応用

EMDは、画像検索やパターン認識において広く利用されており、シグネチャ間の比較やフローサイトメトリーによるバイオマーカーの評価など、さまざまな分野で応用されています。これにより、分布間の有意な差異を把握し、データを有効に活用することが可能になります。

EMDは、異なる分布間の関係性を理解するための強力なツールであり、今後の研究や応用が期待されます。

もう一度検索