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版のリンク)](https://arxiv.org/abs/1803.00567)」を精読するという闇の集いがあるので，自分用のメモを取っておく（飽きるまで続ける）．

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

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

# 内容

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

## §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 (何なら今回が記録最終回まである）