点間の距離がグラフの最短経路距離である場合の，最適輸送の効率的な定式化

はじめに

　この記事では，分布の近さの尺度である最適輸送を扱いますが，純粋な（制約なしの）最適輸送のアルゴリズムには触れません．
　最適輸送を目的関数とする，制約付き最適化問題の定式化の話をします．

背景

　こちら記事では学校のクラス分けを数理最適化を用いて決定するという例を扱っています．
　各クラスの学力の分布をなるべく近くしたいという目的に対して，各クラスの学力の累積分布関数と全体の累積分布関数の差の $l_1$ ノルムを最小化するという方法で良い結果が得られているのですが，「累積分布関数の差の $l_1$ ノルムの最小化」という（個人的にはかなり）不思議な目的関数を定義しています．

　本記事では「累積分布関数の差の $l_1$ ノルムの最小化」について考えたことを，少し一般化して順に説明していきます．

何らかの制約のもとで 2 つの分布をなるべく近づけたい

問題設定

　$I$ を有限集合とし，変数 $p \in \mathbb{R}^{|I|}$ と $q \in \mathbb{R}^{|I|}$ を，確率変数 $P, Q$ が値 $i \in I$ をとる確率を表しているとします．
　$p$ , $q$ はなんらかの制約条件 $(p, q) \in A $ によって制限されていますが，制限の範囲内で自由に動かすことができ，なるべく P と Q の分布が近くなるように決めたいという最適化問題を考えます．

　最適化問題の制約条件だけを書くと以下になります．

\begin{align}
\text{s.t.} \ & \ (p, q) \in A \\
& \ \sum_{i \in I} p_i = 1 \\
& \ \sum_{i \in I} q_i = 1 \\
& \ p_i \geq 0, \ \forall i \in I \\
& \ q_i \geq 0, \ \forall i \in I
\end{align}

　このような問題の具体例としては，

• 上に挙げた記事で扱っている，生徒のクラス分け
  • 各クラスの成績の分布を揃えたい
• レジ・清掃・陳列などの店舗業務の従業員への割り当て
  • 従業員ごとに，ある分布に近くなるように割り当てたい
  • 同じ立場の従業員同士への各業務の割り当てがなるべく近くなるようにしたい

といったことが考えられます．¹

素朴な方法

　2 つの分布をなるべく近づけたいという状況でまず思いつく方法は， $p - q$ の $l_1$ または $l_2$ または $l_\infty$ ノルムの最小化です．
　$A$ が多面体であれば， $l_1$ , $l_\infty$ ノルムの最小化は線形計画問題， $l_2$ ノルムの最小化は二次計画問題として定式化することができます．

　ただし，上に挙げた記事でも述べられているように，この方法では感覚的な分布の近さとノルムの小ささとが一致しないことがあります．
　例えば， $I= \lbrace 0, 1, 2, 3, 4 \rbrace $ として，以下の a 〜 e の 5 つのケースで分布を比べてみると，感覚的にはケース a よりもケース b の方が $p$ と $q$ が近いように思えますが， $p - q$ の $l_1$, $l_2$, $l_\infty$ ノルムは同じ値になっています．

最適輸送

　より人間の感覚に近い²分布間の距離として最適輸送が知られており，最適化問題の目的関数として最適輸送コスト最小化を定式化すると以下になります．

\begin{align}
\text{min} \ & \ \sum_{ij \in I \times I} d(i, j) x_{ij} \\
\text{s.t.} \ & \ p_i = \sum_{j \in I} x_{ij}, \ \forall i \in I \\
& \ \sum_{i \in I} x_{ij} = q_j, \ \forall j \in I \\
& \ (p, q) \in A \\
& \ \sum_{i \in I} p_i = 1 \\
& \ \sum_{i \in I} q_i = 1 \\
& \ p_i \geq 0, \ \forall i \in I \\
& \ q_i \geq 0, \ \forall i \in I \\
& \ x_{ij} \geq 0, \ \forall ij \in I \times I
\end{align}

　$d(i, j)$ は二点 $i, j$ 間の距離で，入力として与える必要があります．

　さきほどの簡単な例では，例えば $d(i, j)=|i - j|$ という距離が考えられ，その場合の最適輸送コストは以下のようになります．
　$p - q$ の素朴なノルムでは a, b, d, e を区別できていませんでしたが，最適輸送コストでは a は b よりも大きく， e は d よりも大きいコストとなっており，最適輸送コストは人間の感覚に近い指標であることがわかります．

距離がグラフの最短経路距離である場合の，最適輸送の効率的な定式化

　最適輸送を目的関数とした最適化問題を解くことで，分布をいい感じに近づけられそうですが，上記の定式化では変数 $x_{ij}$ の数が $|I|^2$ 個とかなり多くなるため， $I$ が大きいと汎用ソルバーなどでは解くことが難しいという問題があります．³

　 $d(i, j)$ になにも仮定を置かない場合には前述の定式化から改善の余地がないのですが，

$I$ がグラフのノードに対応していて，$d(i, j)$ がグラフ上の最短経路距離である

場合には，最適輸送をグラフ上のフローとして定式化することができます．⁴

\begin{align}
\text{min} \ & \ \sum_{ij \in E} d(i, j) x_{ij} \\
\text{s.t.} \ & \ p_i + \sum_{j \in I^+_i} x_{ji} = \sum_{j \in I^-_i} x_{ij} + q_i, \ \forall i \in I \\
& \ (p, q) \in A \\
& \ \sum_{i \in I} p_i = 1 \\
& \ \sum_{i \in I} q_i = 1 \\
& \ p_i \geq 0, \ \forall i \in I \\
& \ q_i \geq 0, \ \forall i \in I \\
& \ x_{ij} \geq 0, \ \forall ij \in E
\end{align}

　$E \subset I \times I$ はグラフの枝の集合で， $I_i^+$ はノード $i$ に流入する方向の枝で隣接しているノードの集合， $I_i^-$ はノード $i$ から流出する方向の枝で隣接しているノードの集合とします．

　もとの定式化は $i$ と $j$ の全ての組み合わせについての輸送量を考えているのに対し，この定式化ではグラフ上で隣接するノード間の輸送量だけを考えており，隣接していないノード間では複数の枝を辿って輸送していると解釈できます．（下図では枝 $(i,j)$ と $(j,i)$ を 1 本の線で描いていますが，両方向の枝があると考えてください）

　最適輸送をグラフ上のフローとして定式化した際の変数 $x_{ij}$ の数は $|E|$ であり，グラフが疎( $|E| \ll |I|^2$ )である場合には，もとの定式化よりも高速に解けることを期待できます．

グラフを意識せずに定義した点間の距離をグラフの最短経路距離に帰着できるのか

一次元の場合

　$I$ が一次元上の点の集合 $I \subset \mathbb{R}$ で，点間の距離が差の絶対値⁵ $d(i, j) = |i - j|$ である場合には，点を昇順にソートしたものを $i_1, i_2, i_3, \cdots$ とし， $(i_k, i_{k+1})$ を枝とする鎖状のグラフを考えることで，$d(i, j)$ をグラフの最短経路距離とみなすことができます．

　多くの場合に一次元上の距離は絶対値で定義されると思われるので，$I$ が一次元上の点の集合であれば，大抵グラフの最短経路距離に帰着できると言えます．

冒頭で紹介した記事との関連

　一次元の場合のグラフ上のフローの定式化では，枝 $(i_k, i_{k+1})$ の流量を $p$, $q$ を使って
$$x_{i_k i_{k+1}} - x_{i_{k+1} i_k} = \sum_{l=1}^k p_{i_l} - \sum_{l=1}^k q_{i_l}$$
と $P$ と $Q$ の累積分布関数の差で表すことができます．
　よって，最初に紹介した記事での「累積分布関数の差の $l_1$ ノルムの最小化」は最適輸送コストの最小化と等価かつ，グラフの構造を使った効率的な定式化であると解釈することができます．

【ポエム】

　数式として最適輸送コストの最小化と解釈できるということは，実務的に最適輸送コストの最小化として解釈したほうがよいということではありません．

　例えば，クラス分けについてヒアリング・調査を進めたところ，試験の点数の累積分布関数は「ある難しさの説明をしたときに理解できる生徒の割合」とみなせることが判明し，教師からは「ある難しさの説明をしたときに理解できる生徒の割合が各クラスで同じであってほしい（理解できる生徒の割合が異なると授業の進捗に差がついて準備が大変になる，あるいは，理解できなかった生徒へのサポート体制を構築しづらくなるから）」という要望があったとします．
　この場合には，要望を素直に定式化したものが累積分布関数の差の最小化だといえます．

　一方で，十分なヒアリング・調査を行わないまま「分布を近づけたいなら最適輸送を使おう」などと天下り的に考えてしまうと，

• そもそもなぜ最適輸送を使うのか
• （何らかの輸送コストを定義したとして）なぜその輸送コストなのか

を説明することが難しく，要件化・定式化の妥当性を判断することができなくなってしまいます．

二次元以上の場合

　点間の距離が $l_1$ ノルム $d(i, j)=||i - j||_1$ と定義されていれば，グリッド状のグラフを考えることで，グラフ上の最短経路距離とみなすことが一応は可能です．
　特に $i \in I$ が格子点である場合には，グラフの枝の数は $|I|$ の定数倍になります．（図が見づらくなるので各ノードの流入 $p$ と流出 $q$ は省略しています）

　ただし，二次元以上ではそもそも $|I|$ が大きくなりがちなので，特殊なケースを除き，点間の距離をグラフ上の最短経路に帰着させたとしても効率的に解くことは難しいだろうと思います．

まとめ

• 一般の最適輸送の定式化では点の数の二乗個の変数が必要になる
• 点間の距離がグラフの最短経路距離である最適輸送は，グラフが疎であれば効率の良い定式化が可能
  • グラフ上の最小費用流問題として定式化
  • グラフの枝数程度の変数で定式化できる
• 点の集合が一次元（ $\mathbb{R}$ の部分集合）で，点間の距離が座標の差の絶対値である場合には，距離を鎖状のグラフ上の最短経路距離とみなすことができる
  • 冒頭で紹介した記事での「累積分布関数の差の最小化」は，本記事で紹介した「グラフ上のフローとしての定式化」の一次元の場合と同じ
• 点の集合が二次元以上である場合には，点間の距離をグラフ上の最短経路距離とみなして効率良く解ける状況はあまりなさそう

さらにまとめ

• 一次元の最適輸送を最適化問題として定式化する場合には，二部グラフを使わず，鎖状のグラフ上のフローとして定式化すると効率的

1. その他にもきっと様々な応用例があるのですが，よい具体例を思いつきませんでした． ↩

2. 人間の感覚に近いだけではなく理論的な背景もあるのだろうと思いますが，著者はよく知りません． ↩

3. 個人的な感覚では，汎用ソルバーを使う場合， $|I|=100$ ならある程度の時間で解けそうですが，$|I|=1000$ になると相当厳しいと思います． ↩

4. 物流問題などを考えている場合には，グラフ上のフローとしての定式化はほぼ当たり前のものですが，分布間の距離としての最適輸送を考えている場合には，この定式化はやや気づきづらいように思います． ↩

5. 一次元では $l_p$ ノルム（ $p \geq 1$ ）はすべて絶対値と同じです． ↩