メリー・クリスマス！！この記事は、「日曜数学Advent Calendar 2023」の24日目の記事です。

昨日23日目の記事は、Seiichi Manyamaさんの「n 次多項式の判別式の項数」でした。

manchanr6.blogspot.com

はじめに

　今年の日曜数学Advent Calendarは、最適輸送のお話をさせて頂きます。

最適輸送とは？

　最適輸送とは、その名の通り、複数の地点にある資源を、需要のある地点にいかに効率よく運ぶかを考える、物資輸送問題として１８世紀頃から研究されていたものだそうです。その後、経済資源の割当や、流体力学の理論に応用されるようになり、さらにはコンピュータサイエンスの世界でも登場するようになりました。

　特に、機械学習の世界では、確率分布と確率分布を比較するためのツールとして利用されています。ここで、確率分布としてはヒストグラム、点群、連続分布（経験分布で近似）などが扱われます。

KLダイバージェンスとの比較

　機械学習に詳しい方はご存知のとおり、確率分布と確率分布を比較するものとして有名なのはKL（カルバック＝ライブラー）ダイバージェンスです。参考までに離散分布におけるKLダイバージェンスについて下記します。KLダイバージェンスは、最尤推定を行う場面などで現れます。

離散分布におけるKLダイバージェンス　 $\displaystyle KL(a || b) := \sum_{i=1}^n a_i \log \frac{a_i}{b_i} - a_i + b_i$

ただし、 $0 \log 0 =0$ とし、ある $i \in \{1,2, \cdots , n \}$ において $a_i >0 \wedge b_i = 0$ である場合は $KL(a || b) = \infty$ とする。

　機械学習を行う場合、分布を近付けたい対象との比較方法として、このKLダイバージェンスにはない最適輸送の利点がいくつかあります。その中でも、「適切な仮定の下で距離の公理を満たす」というものがあります。ここで距離の公理を復習してみましょう。

距離の公理

$X$ を集合とする。関数 $d: X \times X \rightarrow \mathbb{R}$ が、任意の $x,y,z \in X$ に対して以下をすべて満たすとき、 $d$ は $X$ 上の距離であるという
- (1).（非負性） $d(x,y) \ge 0$
- (2).（同一性） $d(x,y) = 0 \Leftrightarrow x = y$
- (3).（対称性） $d(x,y)=d(y,x)$
- (4).（三角不等式） $d(x,z) + d(z,y) \ge d(x,y)$

これら４つの条件を距離の公理という（ただし、(1)は(2),(3),(4)から導くことができる）。

KLダイバージェンスは、上記の式を見て頂ければ明らかですが、一般には(3)対称性も、(4)三角不等式も満たさないので、距離の公理を満たしません。

最適輸送とWasserstein距離

点群の最適輸送問題を線型計画問題として定式化すると、 $OT( \alpha, \beta ,C) :=$ $\displaystyle \min_{P \in \mathcal{U} (a,b)}$ $\langle C,P \rangle$ と表される。ここで $a,b$ はそれぞれ輸送元と輸送先の点に対する重みベクトル、 $\alpha, \beta$ はそれぞれ $a,b$ の確率分布、 $\mathcal{U}(a,b)$ は実行可能解の集合、Cはコスト行列、Pは輸送行列で、 $\langle . \rangle$ は行列の要素同士を掛けた和である。

なお、輸送元の各点から輸送先の重みで輸送すれば制約を満たすので、 $a {b}^{T}$ は実行可能解になります。

最適輸送コスト自体は、最適輸送距離とも呼ばれますが、距離の公理を満たしません。例えば、コスト行列Cが0行列の場合には任意の輸送行列Pが解となり、同一性を満たさないからです。

そこで、距離の公理を満たす最適輸送距離として、以下のようなWasserstein距離を紹介します。

$\mathcal{X}$ 上の距離関数 $d: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ と実数 $p \ge 1$ について、 $C(x,y) = {d(x,y)}^p$ と定義する。このとき、 $\alpha, \beta \in \mathcal{P}( \mathcal{X})$ について $W_p(\alpha, \beta) := OT(\alpha, \beta ,C)^{1/p}$ を $\alpha$ と $\beta$ のp-Wasserstein距離といいます