はじめに
- ワッサースタイン空間ってなんですか？
- Wasserstein距離ってなんですか？
- Sinkhorn divergenceってなんですか？
- Gromov-Wasserstein距離ってなんですか？
全然わかんないぜ。
ワッサースタイン空間とは
ワッサースタイン空間は、確率測度の空間に特殊な距離（ワッサースタイン距離）を導入することで得られるメトリック空間のことです。最適輸送理論で用いられます。
ユークリッド空間との比較
ワッサースタイン空間の要素は、確率測度（確率分布）です。
例えば、実数直線上の確率分布全体がワッサーシュタイン空間を形成します。
| 比較項目 | ユークリッド空間 | ワッサースタイン空間 |
|---|---|---|
| 定義 | 実数ベクトル空間に標準内積を導入した内積空間 | 確率測度の空間に特殊な距離を導入したメトリック空間 |
| 距離の定義 | ユークリッド距離 (2点間を結ぶ直線の長さ) | ワッサースタイン距離 (ある確率測度を別の確率測度に変換するために必要な最小コスト) |
| 応用分野 | 線形代数、関数解析、幾何学など数学の多くの分野 | 最適輸送理論、確率論、統計学、機械学習 (特に生成モデルの評価や訓練) |
| 幾何学的性質 | 直線、平面、超平面などの線形部分空間を含む整った幾何学的構造 | 測度の台の形状や測度の重なり具合などに依存する複雑な幾何学的構造 |
| 問題の解決アプローチ | ユークリッド空間の性質を直接利用 | ワッサースタイン空間上の問題をユークリッド空間に埋め込むことで解決するアプローチも提案されている |
ワッサースタイン空間の起源
1960年代にソビエト連邦の数学者レオニード・ワッサーシュタイン(Leonid Vaseršteĭn)によって導入された最適輸送問題に遡ります。
起源
- ワッサースタインは、1969年に論文 "Markov processes over denumerable products of spaces, describing large systems of automata" の中で、確率測度間の距離を定義
- この距離は、後にワッサーシュタイン距離と呼ばれるように
- もともとはマルコフ過程の研究において、状態空間上の確率測度間の距離を定義するために導入された
その後の展開
-
1970年代後半から1980年代にかけて、フランスの数学者ミシェル・タラグラン(Michel Talagrand)らによって、ワッサースタイン距離の性質が詳細に研究される
-
1990年代以降、ワッサースタイン距離は最適輸送問題との関連性が明らかになり、その応用範囲が拡大
- 特に、フェリックス・オットー(Felix Otto)らによる勾配流の理論との関連性が示された
-
2000年代に入ると、機械学習分野でワッサースタイン距離が注目を集めるように
- 生成モデルの評価や訓練において、ワッサースタイン距離を用いるWassersteinGANが提案され、大きな影響を与えた
Wasserstein距離 と Sinkhorn divergenceの違い
Sinkhorn divergenceはWasserstein距離を正則化し計算上扱いやすい形にしたものです。
| 比較項目 | Wasserstein距離 | Sinkhorn divergence |
|---|---|---|
| 定義 | 最適輸送問題に基づいて定義される | Wasserstein距離を正則化した形で定義される |
| 計算方法 | 大規模な問題に対して計算量が多くなる傾向がある | Sinkhornアルゴリズムを用いて反復的に計算される |
| 距離の性質 | 距離の公理を満たす真の距離尺度 | 正則化の影響により、厳密には距離の公理を満たさない擬距離 |
| 正則化の影響 | 正則化項は含まない | エントロピー項による正則化が含まれる |
| 計算の安定性と効率性 | 計算が不安定になりやすく、効率が悪い場合がある | 正則化項のおかげで、より高速で安定した計算が可能 |
| 応用上の特徴 | 確率分布間の幾何学的構造を捉えるのに適している | 機械学習におけるモデルの学習や評価に適している |
| 主な用途 | 確率分布の補間やバリエーションの分析 | 勾配ベースの最適化に組み込みやすい |
Sinkhorn divergenceの起源
Sinkhorn divergenceの起源は、1960年代のRichard Sinkhornによる二重確率行列の研究に遡ります。
起源
-
Richard Sinkhornの1960年代に二重確率行列 (doubly stochastic matrices) の研究
- 与えられた行列を二重確率行列に変換するアルゴリズム（Sinkhornアルゴリズム）を開発
-
1990年代後半から2000年代にかけて、Marco Cuturi、Arnaud Doucet、Gilles Barronらによって、最適輸送問題とSinkhornアルゴリズムの関連性が研究されました。彼らは、Sinkhornアルゴリズムを用いてWasserstein距離の近似計算を行う方法を提案しました。
その後の展開
-
2013年、論文 "Sinkhorn Distances: Lightspeed Computation of Optimal Transport"
- Sinkhorn距離という概念を導入
- Sinkhornアルゴリズムを用いてWasserstein距離を正則化する方法を提案
-
2015年、論文 "Sinkhorn Divergences for Unbalanced Optimal Transport"
- Sinkhorn divergenceの概念を導入
- Sinkhorn距離を一般化して、質量が保存されない場合にも適用できるように
-
その後、Sinkhorn divergenceは機械学習分野で注目を集める
- 生成モデルの学習や評価、ドメイン適応、テキスト分析などの様々なタスクに応用されるように
Gromov-Wasserstein距離
Gromov-Wasserstein距離は、異なる距離空間上で定義された確率測度間の距離を測る尺度です。これは、通常のWasserstein距離を一般化したものであり、測度がサポートされている空間自体の距離構造も考慮に入れています。
Wasserstein距離 と Gromov-Wasserstein距離の違い
| 比較項目 | Wasserstein距離 | Gromov-Wasserstein距離 |
|---|---|---|
| 測度の定義域 | 同一の距離空間上の確率測度を比較 | 異なる距離空間上の確率測度を比較 |
| 距離の定義 | 測度間の最適輸送コストに基づく | 測度間の最適輸送コストと空間の距離構造の類似性に基づく |
| 空間の構造 | 測度がサポートされている空間の距離構造は考慮しない | 測度がサポートされている空間の距離構造も考慮する |
| 計算の複雑さ | 比較的単純な最適輸送問題として定式化される | 測地線の対応関係を見つける必要があるため、より複雑 |
| 応用分野 | 主に同一の空間内での測度の比較に用いられる | 異なる空間間での測度の比較に用いられる |
| 主な用途 | 生成モデルの評価、ドメイン適応、テキスト分析など | 形状解析、グラフ解析、自然言語処理など |
| 理論的背景 | 最適輸送理論に基づく | 最適輸送理論とGromov-Hausdorff収束の概念に基づく |
Gromov-Wasserstein距離の起源
起源
-
Mikhail Gromov (1943-) は、1980年代に距離空間の幾何学的な性質を研究
- 距離空間間の類似性を測るための概念として、Gromov-Hausdorff収束を導入
-
2000年代初頭、Gromov-Hausdorff距離と最適輸送理論の関連性研究
- Gromov-Hausdorff距離を確率測度の設定に拡張する方法の提案
-
2011年、論文 "Gromov-Wasserstein Distances and the Metric Approach to Object Matching"
- Gromov-Wasserstein距離の概念を正式に導入し、その性質を詳細に分析
その後の発展
- 2016年、論文 "Entropic Metric Alignment for Correspondence Problems"
- Gromov-Wasserstein距離の計算を高速化するための手法が提案される
- その後、Gromov-Wasserstein距離は、機械学習や計算幾何学の分野で注目を集める
- 特に、形状解析、グラフ解析、自然言語処理などの問題に応用される
- 現在では、異なる距離空間上で定義された確率測度を比較するための重要な道具の一つとして認識
- 理論的な研究だけでなく、実用的な応用も活発に行われている
おわりに
Wasserstein距離、Sinkhorn divergence、Gromov-Wasserstein距離について、順にみていきました。まだまだ理解したとは言い難いですが、ワッサースタイン空間のことを少しは知ることができました。
精進します。