6
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

posted at

updated at

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 (何なら今回が記録最終回まである)
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
6
Help us understand the problem. What are the problem?