点群の最適輸送アルゴリズムで遊んでみた

この記事は、「最適輸送の理論とアルゴリズム」を読んでいて気になった部分を自分で実装して試してみたものを雑にまとめたものです。今回は点群の最適輸送について、実際にPythonで実装をして実験してみた結果を書きます。最適輸送理論は機械学習においてロス関数の設計に役立つらしい(本をまだ全部読んでない...)ので、シンプルな線形計画問題で解ける簡単なアルゴリズムを一度実装してみました。 最適輸送問題とは まず、そもそも最適輸送問題って何？という話なのですが、 2つの分布D_1, D_2がある 分布を移動させるときのコストが定義されている という状況でD_1をD_2に総コストを最小にして移動させるためにはどのようにしたらよいか、という問題だと理解しています。一般の連続分布ではなく点群の話に言い換えると、点群に含まれる点を移動コストを最小にして別の点に移動させるためにはどの点をどこの点に移動させればい