最適輸送本イベントに寄せて学ぶ

はじめに

Forkwell Libraryという書籍の著者が登壇するイベントにて、最適輸送の理論とアルゴリズム (機械学習プロフェッショナルシリーズ) の佐藤さん(@joisino_)と話す時間を頂いた。
forkwell.connpass.com

スライド
動画

その時に事前に学んだメモの公開と、当日のイベントの肌感を残す。

最適輸送の理論とアルゴリズム

MLPシリーズの書籍

最適輸送の理論とアルゴリズム (機械学習プロフェッショナルシリーズ)

最適輸送の理論的な背景から応用まで書かれている。
私個人としては、幾何や統計、測度についてお気持ちレイヤーまで分かる、機械学習、コンピュータサイエンスなら少しわかる、くらいの私でもちゃんと読めるように、深く入り込まず難しい所に例示を出して優しく書いてくれている上、応用事例まで付いてくるありがたい本。

サポートページとしてGitHubリポジトリも用意されている。
github.com
書籍内にあるアルゴリズム、最適輸送での画像操作事例など、jupyter notebookで各サンプルが動かせるようになっている。
一通り動かしたが、数式で分からない所は大体この例示で解決する気がする。ありがたい。

ざっくりこんな感じになっている。

1章　各種定義
2章　最適化問題としての定式化
    輸送計画とリサイクル業者のイメージ、双対問題
    ボールによる物理的解釈
    最適輸送問題の疎性
    組合せ最適化、線形計画法、最小費用流問題（minimum flow cost problem）
3章　エントロピー正則化、シンクホーンアルゴリズム
    エントロピー正則化つき問題は強凸、最適解が一意に定まる、微分可能
    シンクホーンアルゴリズムは「ソフトなC変換」であり「行列スケーリング」
    行列計算なのでGPU＋畳み込みで高速化できる
    シンクホーンは大域収束性、計算量
4章　GANと最適輸送
5章　スライス法、1次になおして貪欲法
    カーネル的、木による階層クラスタリング
6章　KL、JSダイバージェンス、MMD、ワッサースタイン距離
7,8章　不均衡最適輸送→ワッサースタイン重心
9章　グロモフワッサースタインで2つの異なる分布を比較

ML屋視点でしんどいのは2章の確率測度が関わる証明と3章の計算量の証明辺り。
イベント内で佐藤さんも「証明は全て読み込む必要はないので是非読み進めてもらって」と仰っていたので、そこを抜ければ4章以降は線形代数とMLでよく使われる知識があればスッと読み進める事が出来る。

7章で「不均衡最適輸送って応用があるのねふむふむ…」くらいに思ってたら、恐ろしくスムーズな流れで9章で「あれ、最適輸送めっちゃ便利じゃん…」ってなる。

ML屋がツールとしての最適輸送を学ぶ上で最良だと思う（宣伝）。

事前学習

何に使われているか。

「2つの分布の距離として使う、比較する」「2つの分布の中間状態を捉える」というツールと捉える事ができる。

Wasserstein GANでMLから着目を浴びたとされているが、WGANの話は書籍を読むと流れが把握できる。

• 生成以外でも例えばObject DetectionではOTA（Optimal Transport Assignment for Object Detection）が有名
• 【CVPR'22】物体検出アルゴリズムの新しい評価指標 | | AI tech studio
• 【論文5分まとめ】Ota: Optimal transport assignment for object detection

• YOLOv7からもOTAが使われている
• [2207.02696] YOLOv7: Trainable bag-of-freebies sets new state-of-the-art for real-time object detectors
  • いまいなアンカーに対して、アサインメントすることは悪影響を与える可能性がある
    • 局所的な視点ではなく、全体的な視点から処理する必要がある
  • 画像全体のすべての正解ボックス gt に対して最も信頼性の高くなるような全体的な視点からアサインメントできる手法が必要

• 書籍内にもある通り3次元点群
• [2105.08248] Self-Point-Flow: Self-Supervised Scene Flow Estimation from Point Clouds with Optimal Transport and Random Walk
  • 3次元点群の対応付けを最適輸送で解く
    • 疑似ラベルとして自己教師あり学習
    • 学習が進むにつれて疑似ラベルを更新もできる

• 画像以外だと言語が直感的に分かりやすい
• 構造を持った言語データと最適輸送, Sho Yokoi, NAIST DSC NLP Seminar 2022 Summer
  • 「全体として類似、部分のアラインメント」なのでNLPと相性がいい
  • Gromov-Wassersteinは”内部状態”に着目できる（点群が三角の形してるな的な）
    • 異なる空間のマッチングができる
    • NLPなら言語の翻訳とか

• 最適輸送によるテキスト要約
• OTExtSum: Extractive Text Summarisation with Optimal Transport - ACL Anthology
• OTExtSum(Optimal Transport Extractive Summariser): 最適輸送を利用した文書要約 – arXiv最新論文の紹介
  • テキスト要約を最適輸送(OT)問題として初めて定式化

• NLPではACL2021のベストペーパーが最適輸送を扱っている
• Vocabulary Learning via Optimal Transport for Neural Machine Translation
  • 機械翻訳ではvocabサイズによってコーパスのエントロピーが減少する
    • 代わりに類似の語彙を学習できなくなることもある
    • この現象はトレードオフである
    • MUVなる良い感じの語彙数の指標を最適輸送問題と捉え解く
  • ACL2021 best paper 紹介 - Qiita

• 分布の比較であればデータセット比較、Domain Adaptation、距離としても使える
• [2111.12292] Improved Fine-Tuning by Better Leveraging Pre-Training Data
  • データのサンプル選択に最適輸送を利用
• [1507.00504] Optimal Transport for Domain Adaptation
  • Domain適合に最適輸送を利用
• Learning Wasserstein Embeddings
  • Wasserstein空間にEmbeddingする

つまり色々使える。
KLダイバージェンスの強い版、教師なしアラインメントな損失関数と捉える事もできる。
直近スケーリング則より良い学習データをサンプルした方が良いという動きもあり、分布を利用したSamplerにもなり得る。
複数のDNNモデルのタスクを複合的に扱ったり、埋め込み空間としての活用も進んでいきそう。

何が嬉しくて使われているのか

端的にMLにとって嬉しい点をまとめる

• 複数の問題を並列に扱える
• データが少ない、教師なしでも扱える
• コストが微分可能
• 分布の全体の状態、内部の状態を上手く扱える
• 2つの分布に重なりが無くても近似できる
  • 数理最適化では計算量が大きくなる
  • 最適輸送におけるシンクホーンアルゴリズムやスライス法が良い
    • これらが行列計算なのでGPU上で扱える

事前、並行して読むと良いもの

大まかにまとめてくれているもの

• 最適輸送の解き方, Ryuma Sato
  • 最適輸送の解き方
  • 今回のイベントスピーカーでもある佐藤さんのスライド
  • それぞれの手法のメリデメが端的かつ分かりやすくまとめられている

• 最適輸送入門, Ryuma Sato, IBIS 2021 チュートリアル
  • https://www.slideshare.net/joisino/ss-251328369
  • 今回のイベントスピーカーでもある佐藤さんのスライド

• How to leverage optimal transport（最適輸送の使い方）, Sho Yokoi, 0xセミナー
  • https://speakerdeck.com/eumesy/how-to-leverage-optimal-transport

• 最適輸送の計算アルゴリズムの研究動向, Ohno Kentaro
  • https://www.slideshare.net/KentaroOhno1/ss-241141892

• ICML 2020 最適輸送まとめ, Ohno Kentaro
  • https://www.slideshare.net/KentaroOhno1/icml-2020-236823095

• 最適輸送理論の解説論文とか書籍へのリンクのまとめ
  • 最適輸送理論の解説論文とか書籍へのリンクのまとめ - 備忘録

触ってみる

• POT
  • POT: Python Optimal Transport — POT Python Optimal Transport 0.8.2 documentation
  • いちばん簡単に使える
• OTT with JAX
  • GitHub - ott-jax/ott: Optimal Transport tools implemented with the JAX framework, to get auto-diff, parallel and jit-able computations.
• GeomLoss
  • Geometric Loss functions between sampled measures, images and volumes — GeomLoss
  • PyTorch APIをサポートしてる
  • PyTorch API — GeomLoss

[Package] 最適輸送問題のパッケージを試す | POT, OTT-jax, OptimalTransport.jl

イベント当日のQ&A

いくつか良かったQ&Aのメモ、順不同

• KLダイバージェンスと比較していたが、f-divergence、Bregman divergence、integral probability metricsと比較すると
  • 最適輸送はIPMの一種、クロスエントロピーはf-divergenceの一種
  • 最適輸送はカスタマイズ性と一般性が良いよ
  • 6章読むといいぞ！

• 競プロで使える？
  • 最小費用流問題なので知っておいて損はないよ
  • ICPCの後ろの方とかでは出てくるよ！

• 最適輸送で分かってないトピックはある？
  • 連続分布をサンプリングしたら点の集合が得られるが、その時に精度良く近似になっているかとか
  • 分布の最悪ケースとか
    • 最悪ケースとは？
    • いわゆる意地悪な分布に対してどこまで出来るのか、定式化

• 時系列では扱える？
  • 時系列でDTWっぽいことをやる、も研究されてるよ
  • 物理とか生物では、細胞の動きのモデリング等で大昔から使われている

• 広義の拡散モデルと言えたりする？
  • 拡散モデルとの繋がりは指摘されている
  • フォッカー・プランク方程式 (Fokker–Planck equation)とかで検索すると良いよ

• 最適輸送という訳が「輸送コスト最適化」のようなイメージを植え付けるのでは？「分布の比較」としての名前を付けるとしたら？
  • 難しい、そもそも英語がOptimal Transportなので
  • 古い論文ではOptimal Transportionだった、MLブームにつれてOptimal Transportに

• 理論をプログラムに落とすの難しい、という人が多そうだけどどう思う？
  • シンクホーンなど理論の割にはコードが簡単になるのが人気の理由の1つではないか
  • 最適輸送に関しては簡単というのが印象

• 基礎、応用で読むべき本はある？
  • 「最適輸送の理論とアルゴリズム」をまず読んでみて欲しい
  • Computational Optimal Transport
    • ちょっと広い範囲、応用も含まれている
    • 公式pdfがarXivに公開されてるので是非
  • Optimal transport, old and new
    • 数学者が書いた1000ページある本
    • 数学的な細かい定義、どういう条件が揃ったら使えるか等

おわりに

Forkwellの人がお手上げになり、最適輸送本の回はモデレータ出来ないかもという事で1週間程前にお話を頂いて、最適輸送をツールとして何となく知っているくらいから一気に学習したので、学部のゼミの気分だった。

難しい。

イベントでは、かなり優しく最適輸送の事例を紹介して頂いて、ありがたかった。

ありがて〜