Computational Optimal Transport 精読会 記録 (#1: 2.1-2.3)

目的

職場で「Gabriel Peyré, Marco Cuturi. Computational Optimal Transport, Foundations and Trends in Machine Learning, vol. 11, no. 5-6, pp. 355-607, 2019 (arXiv版のリンク)」を精読するという闇の集いがあるので，自分用のメモを取っておく（飽きるまで続ける）．

主に以下のような目的で書いている．

• 自己満足のため
• 自分自信の復習のため
• 将来(もしくは過去に)この本を読んだ人に何らかの影響があれば良いな，と思ったため
• 自分たちで数学的に詰まっちゃった場合，誰か強い人に助けて欲しいため

内容

• ヒストグラムと割当問題に関わる最適化問題の概要

§2.1 ヒストグラムと測度

• $n$次元のヒストグラムと確率ベクトルを交互に使っていくという話

  • 数学的な難易度として，ヒストグラム→離散測度→(一般)測度と上がっていく
  • 特に測度論が必要な部分は(一応)濃いグレーのボックスに囲まれている
    • 飛ばして良い事になっているので飛ばしていく方針でやっている(離散測度の部分は読む)

• $\Sigma_n = \{\mathbf{a}\in \mathbb{R}_+^n \mid \sum_{i} a_i = 1\}$

  • 本文では$a_i$を$\mathbf{a}_i$のように書く流派になっているが
    • イマイチ表記に馴染まなかったので，記録では適当に直している（はず）　
  • 通常の(正規化された)ヒストグラム(ビンの個数$n$)をイメージすれば良い
  • 本書では値が$0$のビンが存在しないとして議論している（余計な自由度は削除）

• 離散測度の場合，格子的なビンではなく，位置 $x_i\in \mathcal{X}$ に重み $a_i$ が乗っているイメージの砂山

  • $\alpha = \sum_{i=1}^n a_i \delta_{x_i}$
  • 特に説明がないが，中心が$0$ではなく$x_i$に設定されているディラック関数が$\delta_{x_i}$

§2.2 割当とMonge問題

• 2つのヒストグラムや砂山を持ってきて，ある位置の山を別の山に移動させるような問題(輸送問題)を考える
• $i$番目の山と$j$番目の山を輸送するコストを$C_{i,j}$で表す

• $n$個ずつの山と山の対応関係は，順列$\mathrm{Perm}(n)$で表現される

  • 例: $n=3$のとき，$123 \mapsto 231$ は $1$の山を$2$の山へ，$2$の山を$3$の山へ，$3$の山を$1$の山へ対応付ける
  • 補足: これは$[n]$から$[n]$への全単射である

• 割当問題の目的関数として以下を導入する

  • この解はユニークではない（図2.2左）

$$\min_{\sigma \in \mathrm{Perm}(n)} \frac{1}{n} \sum_{i=1}^n C_{i,\sigma(i)}$$

• 割当問題では「ある山全て」を「別の山」に移動させるような輸送を考えた

• Monge問題ではこれを一般化して，写像 $T: \mathcal{X} \to \mathcal{Y}$ を用いて，以下の制約を課す．

  • メモ: $\mathcal{X}$側は$n$個の山，$\mathcal{Y}$側は$m$個の山を持っている
  • 任意の$j\in [m]$について，$b_j = \sum_{i\text{ s.t.} T(x_i)=y_j} a_i$
    • $T$によって行先が$j$であるような $\mathcal{X}$側の山に積まれている量の和が，輸送された先の量になっている
  • 山の砂総量が保存されることを $T_{\sharp} \alpha = \beta$ で記す

• Monge問題の目的関数は以下で表される

  • 意味: 山の砂総量を保存するような写像のうち，各ペア $(x_i, T(x_i))$ のコスト総和を最小にする輸送割当 $T$ を求める $$\min_{T} \left\{\sum_{i} c(x_i, T(x_i)) \mid T_{\sharp}\alpha=\beta\right\}$$

§2.3 Kantrovich緩和

• 割当問題では1対1の割当を，Monge問題では多対位置の固い割当を求めた
  • 固い割当: ある砂を分割して輸送できない
• Kantrovichの最適輸送問題では，ある山の砂量 $a_i$ を複数の山に分割輸送しても良い
• これを特徴つけるため，写像$T$ を coupling matrix として一般化する

$U(a, b) = \{\mathrm{P}\in \mathbb{R}_+^{n\times m}\mid \mathrm{P} \mathbb{1}_m = \mathbf{a}, \mathbf{P}^T \mathbb{1}_n = \mathbf{b} \}$

• 行列$\mathrm{P}\in U(a, b)$の解釈

  • 列方向に和を取るとき$a$になる (制約1)
    • ある$i$行目のベクトルは，山の砂量$a_i$が，どういう割り合いで$\mathbf{b}$側に割り振られるのか，が書かれている確率ベクトルになっている
  • 行方向に和を取るとき$b$になる (制約2．同上)

• 今まで$T$や$\mathrm{Perm}(n)$となっていた部分をcoupling matrixで置き換えた最適化問題が，Kantrovichの最適輸送問題

• 目的関数

$$L_C(\mathbf{a,b}) = \min_{\mathrm{P}\in U(\mathbf{a, b})} \langle C, P \rangle$$

• Kantrovichの輸送問題が，割当問題を含むことを確認する

  • 置換$\sigma$を想定
  • 割当ペア$(i, \sigma(i))$に対して，$(P_\sigma){i,\sigma(i)} = \frac{1}{n}$となる行列$P\sigma$を定義する
  • このとき $\langle C, P_\sigma\rangle = \frac{1}{n}\sum_{i} C_{i,\sigma(i)}$ である

• 今$U(1_n/n, 1_n/n)$をBirkhoff polytopeと呼ぶ．Birkhoff polytopeと置換の関係を見ていく

  • 実は$P_\sigma 1_n/n = 1_n/n$であり，$P_\sigma^T 1_n = 1_n$である（arXiv版は数式で$1/n$がない）
  • よって$P_\sigma\in U(1_n/n, 1_n/n)$であり，置換に基づく割当問題は，Birkoff polytope上の最適化問題（の特殊ケース）である
  • 置換ではないような例として，全ての要素が$1/n^2$であるような行列を考える（全ての山を均等に分割する輸送を意味する）
    • これは置換行列$P_\sigma$では表せないが，定義よりBirkoff polytopeに含まれる行列である

• これらの考察より，以下が成り立つ

$$L_C(1_n/n, 1_n/n) \leq \min_{\sigma\in\mathrm{Perm}(n)} \langle C, P_\sigma \rangle$$

• Prop 2.1について
  • 上の線形計画問題は，多面体のextremal pointsに解がある
  • extremal pointsはこの章では定義されていないけど，精読会では強い人が教えてくれた．簡単なメモだけ残しておく:
    • extremal points: 凸集合の二点の中点を取ったとき，extremal pointであれば3点（2点と中点）が一致するような点 = 多角形の角の部分（イメージ）
  • (イメージのみ) 係数 $C$によれば，多角形の線分がまるごと解になることがあるかもしれないが，その両端はextremal pointsになっているので，Prop 2.1 (exists an optimal solution) が成り立つ

次回

• 数式展開が多く行間が広い§2.4 (何なら今回が記録最終回まである）