最適輸送について

最適輸送とは、ある分布から別の分布へ輸送するとき、ある点から別の点へ輸送するとき、コストが最小になるようにどう運べばいいのかを解く問題である。

離散については、以下のように定める。

運ぶもとは $\{\mathbf{x}_i \}_{i=1}^n$ 個存在する。
運ぶ先には、 $\{ \mathbf{y}_j \}_{j=1}^m$ 個存在する。
与えられたデータの $\{\mathbf{x}_i \}_{i=1}^n, \{\mathbf{x}_j \}_{j=1}^m$ について、ヒストグラムによる経験分布となる $\mathbf{p}, \mathbf{q}$ は、ディラックのデルタ関数を用いて以下のように定めることができる。

\mathbf{p} = \sum_{i=1}^n p_i \delta_{\mathbf{x}_i}, \mathbf{p} = \sum_{j=1}^m p_j \delta_{\mathbf{y}_j}

輸送行列 $T$ は、 $n \times m$ の行列で、 $T_{ij}$ とは、 $\mathbf{x}_i$ のデータを $\mathbf{y}_i$ へ運ぶ量のことを指す。
- この行列はカップリング行列ともいう。
コスト行列 $C$ は、同様に $n \times m$ の行列で、 $C_{ij}$ とは、 $\mathbf{x}_i$ のデータを $\mathbf{y}_i$ へ運ぶとき、1単位当たりのデータにかかるコスト。

つまり、最適輸送は、以下の最適化問題である。1行目はすべてのpから出る輸送計画の合計はpの各要素と等しくないといけないし、すべてのqに入る輸送計画についても同様である。

\forall b, \sum_{i=1}^n T \mathbf{1}_m = \mathbf{p}, \sum_{i=1}^m T^T \mathbf{1}_n = \mathbf{q} \\ \min_T \sum_{i=1}^n \sum_{j=1}^m C_{ij} T_{ij}

しかし、ものによってはPartial Optimal Transportといい、全部運ばなくてよく、運びやすい一部だけ運べばいいという制約がある。

現実では、誤差によって外れ値まで運んでほしくない、計算コストの低減などの需要がある。

この時、以下のように、 $0 \leq s \leq \min(n, m)$ として、合計 $s$ の量だけ運ぶ。

\forall b, \sum_{i=1}^n T \mathbf{1}_m \leq \mathbf{p}, \sum_{i=1}^m T^T \mathbf{1}_n \leq \mathbf{q} \\ \mathbf{1}_n^T T \mathbf{1}_m = s \\ \min_T \sum_{i=1}^n \sum_{j=1}^m C_{ij} T_{ij}

これを解くとき、dummy pointを割り当てるという操作が一般的である。

以下がくわしい。

以下のように定義されるのがp-Wassertein距離である。

さきほどの最適輸送のコストの部分について、 $p$ 乗となり、全体で $1/p$ 乗される。

W_p(\mathbf{p, q}) = (\min_T \sum_{i=1}^n \sum_{j=1}^m C_{ij}^p T_{ij} )^{1/p}

この $p$ の選び方について、以下のような基準がある。

$p=1$ の場合、一次モーメントに敏感で、分布の位置のズレをよく合わせようとする。
- 具体的には、実際の物理的な最適な輸送計画や、変形していくときによく合う。
- 特に何も考えていない場合、 $p=1$ となる。
$p=2$ の場合、二次モーメントに敏感で、分布の広がりやばらつきにより注目する。
- 生成モデルやクラスタリング、Domain Adaptationなどで使われるらしい。
さらに大きくしていくと外れ値や極端な差異に対してより敏感になる。
$p<1$ にすると、距離関数が満たすべき距離の公理が崩れてしまう。三角不等式が成り立たない。

2つの分布が同じ基底空間に存在しない(Domain Adaptationでよくある)場合、Gromov-Wassertein距離を使う。

通常、Domainが違うので、 $C_{ij}$ は計算できない。その代わりに、各Domain内で(運ぶ元同士、運ぶ先同士)で距離行列からコストを計算し、その分布の形状の違いをできるだけ合わせようとする。

なので、まずSource Domain間の点 $\{\mathbf{x}_i \}_{i=1}^n$ について、距離行列 $C_{ik}^{s}$ を作り、Target Domain間の点についても $C_{jl}^t$ を作る。

以下のものが、Gromov-Wasserstein距離である。

GW_p^p(\mathbf{p}, \mathbf{q}) = \min_{T} \sum_{i, k=1}^n \sum_{j, l=1}^m |C_{ik}^s - C_{jl}^t|T_{ij}T_{kl}

この測度は、形状を比較するのでDomainが違く手も対応できるし、回転や平行移動やスケーリングにたいしても不変性がある。

しかし、実際の計算では非凸の最適化が必要で厳密解は計算できない。一般的にはSinkhornのアルゴリズムで解く。

Sen(Qian)’s Memo