幾何 最適輸送 解析

C変換と最適輸送における交互最適化の限界

最適輸送問題は、数学や機械学習、経済学などの幅広い分野で重要な役割を果たしています。

 

本記事では、最適輸送問題を解くための手法として注目されたC変換交互最適化について詳しく解説します。

さらに、交互最適化が最適解に収束しない理由と、その限界を克服するために提案されたシンクホーンアルゴリズムの効果についても紹介します。

数式を使いながら丁寧に解説しますので、最適輸送問題や最適化手法に興味がある方は必見です。

 

最適輸送問題の双対問題と\(C\)変換

まず、最適輸送問題の双対問題の定式化を見てみましょう。双対問題の形式は以下のようになります。

最適輸送問題の双対問題の定式化

$$
\begin{array}{lll}
\underset{\boldsymbol{f} \in \mathbb{R}^n, \boldsymbol{g} \in \mathbb{R}^m}{\text{maximize}} & \sum_{i=1}^n \boldsymbol{a}_i \boldsymbol{f}_i-\sum_{j=1}^m \boldsymbol{b}_j \boldsymbol{g}_j & \\
\text { subject to } & \boldsymbol{f}_i-\boldsymbol{g}_j \leq \boldsymbol{C}_{i j} & (\forall i \in[n], \forall j \in[m])
\end{array}
$$

この式の中で、\(\boldsymbol{f}\)と\(\boldsymbol{g}\)は双対変数であり、\(\boldsymbol{C}\)はコスト行列です。各\(i\)と\(j\)の組み合わせについて制約が課されています。

\(C\)変換の定義

\(C\)変換は、上記の最適化問題において\(f\)を固定したときに、最適な\(g\)を求める方法です。この変換により、\(f\)が与えられたときに\(g\)がどのような値を取るべきかを決定できます。

入力の条件\(b \in \Sigma_m\)より\(\boldsymbol{b}_j \geq 0\)であるので、\(g_j\)は小さい値をとるほど目的関数の値が大きくなります。

さらに、\(g\)は次の制約を満たさなければなりません。

$$
\boldsymbol{f}_i-\boldsymbol{g}_j \leq \boldsymbol{C}_{i j} \quad(\forall i \in[n])
$$

また、\(\boldsymbol{g}_j, \boldsymbol{g}_k(j \neq k)\)は互いの実行可能性に影響を与えないので、各\(\boldsymbol{g}_j\)の最小値は次のように求められます。

$$
\boldsymbol{g}_j=\max _{i \in[n]}\left(\boldsymbol{f}_i-\boldsymbol{C}_{i j}\right)
$$

これを\(C\)変換と呼び、\(\boldsymbol{f}^C\)と表します。すなわち、

$$
\boldsymbol{f}_j^{\boldsymbol{C}} \stackrel{\text { def }}{=} \max _{i \in[n]}\left(\boldsymbol{f}_i-\boldsymbol{C}_{i j}\right)
$$

 

最適輸送の双対問題における\(C\)変換は、固定された\(f\)に対して最適な\(g\)を見つける手法であり、シンプルな形式ながら最適化問題の解法において重要な役割を果たします。これを理解することで、より効率的なアルゴリズムの設計や実装が可能になります。

物理的解釈

\(C\)変換は物理的には以下のように解釈できます。赤玉(\(f\)の各要素)がすべて釘で固定されているとします。そして、青玉(\(g\)の各要素)を糸が切れない範囲で限界まで引き下げる操作に相当します。この操作により青玉の位置が決定されます。

シンクホーンアルゴリズムとの関係

シンクホーンアルゴリズムは、この\(C\)変換をソフト化したもので、最適輸送問題の効率的な解法の一つです。具体的には、シンクホーンアルゴリズムでは\(C\)変換を何度も適用することで、最適な解に近づけます。

\(C\)変換の実行可能性の定理

定理の概要

最適輸送問題における\(C\)変換を用いると、任意の\(\boldsymbol{f} \in \mathbb{R}^n\)に対して、その\(C\)変換\(\boldsymbol{f}^C\)を求めることができます。ここで示す定理は、\(\boldsymbol{f}\)と\(\boldsymbol{f}^C\)の組み合わせが、常に最適輸送問題の制約を満たす「実行可能な解」を保証するものです。

【定理】C変換の実行可能性

任意の\(f \in \mathbb{R}^n\)について\(\left(f, f^C\right)\)は実行可能解である。

証明

この定理を証明するために、任意の\(i \in[n]\) と \(j \in[m]\)に対して次の不等式を示します。

$$
\boldsymbol{f}_i-\boldsymbol{f}_j^C \leq \boldsymbol{C}_{i j}
$$

 

任意の\(i \in[n], j \in[m]\)について

$$
\begin{aligned}
f_i-f_j^C & =f_i-\max _{k \in[n]}\left(f_k-C_{k j}\right) \\
& \leq f_i-\left(f_i-C_{i j}\right) \\
& =C_{i j}
\end{aligned}
$$

以上により、任意の\(i \in[n]\) と \(j \in[m]\)に対して\(\left(f, f^C\right)\)は制約を満たし、実行可能解であることが証明されました。

これで、任意の\(f \in \mathbb{R}^n\)に対して\(\left(f, f^C\right)\)が常に最適輸送問題の実行可能な解となることが確認できました。

 

\(C\)変換の最小性の定理

定理の概要

この定理は、任意の実行可能解\((\boldsymbol{f}, \boldsymbol{g})\)と任意の\(j \in[m]\)について、\(\boldsymbol{f}_j^C \leq \boldsymbol{g}_j\)が成り立つということを示しています。つまり、\(C\)変換によって得られる値\(\boldsymbol{f}_j^C\)は、常にほかの実行可能解\(g_j\)よりも小さいか等しいという性質をもっています。

【定理】C変換の最小性

任意の実行可能解\((\boldsymbol{f}, \boldsymbol{g})\)と任意の\(j \in[m]\)について、\(\boldsymbol{f}_j^C \leq \boldsymbol{g}_j\)が成り立つ

 

証明

この定理を証明するためには\(\boldsymbol{f}_j^C-\boldsymbol{g}_j \leq 0\)であることを示します。

定義より

$$
\boldsymbol{f}_j^C=\max _{i \in[n]}\left(\boldsymbol{f}_i-\boldsymbol{C}_{i j}\right)
$$

$$
\boldsymbol{f}_j^C-\boldsymbol{g}_j=\max _{i \in[n]}\left(\boldsymbol{f}_i-\boldsymbol{C}_{i j}\right)-\boldsymbol{g}_j
$$

双対問題の制約条件により、次の不等式が任意の\(i \in[n]\) と \(j \in[m]\)に対して成り立ちます。

$$
\begin{gathered}
\boldsymbol{f}_i-\boldsymbol{g}_j \leq \boldsymbol{C}_{i j} \\
\boldsymbol{f}_i-\boldsymbol{g}_j-\boldsymbol{C}_{i j} \leq 0
\end{gathered}
$$

これは任意の\( i \in [n]\)に対して、次の不等式が成り立つのでその最大値もまた同じ不等式を満たします。すなわち

$$
\max _{i \in[n]}\left(\boldsymbol{f}_i-\boldsymbol{C}_{i j}\right)-\boldsymbol{g}_j \leq 0
$$

これにより、次の不等式が示されました

$$
\boldsymbol{f}_j^C-\boldsymbol{g}_j \leq 0
$$

よって定理が示されました□

 

変換の最適性の系

系の概要

この系は、任意の実行可能解\((f,g)\)について、\((f,f^C)\)の目的関数値が\((f,g)\)の目的関数値以上であることを示しています。これは\(C\)変換が最適化問題の解として優れていることを意味します。

【系】C変換の最適性

任意の実行可能解\((f, g)\)について、\(\left(f, f^C\right)\)の目的関数値は\((f, g)\)の目的関数値以上である。

証明

目的関数は次の形をとるものでした

$$
\sum_{i=1}^n a_i f_i-\sum_{j=1}^m b_j g_j
$$

\(\boldsymbol{a}\)と\(\boldsymbol{b}\)は重みベクトル、\(\boldsymbol{f}\)と\(\boldsymbol{g}\)はそれぞれ双対変数です。

目的関数の差を計算します。

$$
\left(\boldsymbol{a}^{\top} \boldsymbol{f}-\boldsymbol{b}^{\top} \boldsymbol{g}\right)-\left(\boldsymbol{a}^{\top} \boldsymbol{f}-\boldsymbol{b}^{\top} \boldsymbol{f}^C\right)
$$

この差を整理すると、

$$
\boldsymbol{b}^{\top}\left(\boldsymbol{f}^C-\boldsymbol{g}\right)
$$

内積を展開すると

$$
\sum_{j=1}^m b_j\left(\boldsymbol{f}_j^C-\boldsymbol{g}_j\right)
$$

ここで、前に示した\(C\)変換の最小性の定理を利用します。これにより

$$
\sum_{j=1}^m b_j\left(\boldsymbol{f}_j^C-\boldsymbol{g}_j\right) \leq 0
$$

よってまとめると

$$
\begin{aligned}
\left(a^{\top} f-b^{\top} g\right)-\left(a^{\top} f-b^{\top} f^C\right) & =b^{\top}\left(f^C-g\right) \\
& =\sum_{j=1}^m b_j\left(f_j^C-g_j\right) \leq 0
\end{aligned}
$$

したがって、\(\left(\boldsymbol{a}^{\top} \boldsymbol{f}-\boldsymbol{b}^{\top} \boldsymbol{g}\right) \leq\left(\boldsymbol{a}^{\top} \boldsymbol{f}-\boldsymbol{b}^{\top} \boldsymbol{f}^C\right)\)となり、\((\boldsymbol{f},\boldsymbol{f}^C)\)の目的関数値が、\((\boldsymbol{f},\boldsymbol{g})\)の目的関数値以上であることが示されました。

\(C\)変換と\(\bar{C}\)変換

これまでの議論で、最適輸送問題において\(\boldsymbol{f}\)を定めると、最適な\(\boldsymbol{g}\)は次のように計算できるのでした。

$$
\boldsymbol{f}_j^{\boldsymbol{C}} \stackrel{\text { def }}{=} \max _{i \in[n]}\left(\boldsymbol{f}_i-\boldsymbol{C}_{i j}\right)
$$

これは、与えられた\(\boldsymbol{f}\)に対して各\(\boldsymbol{g}_j\)を独立に計算する方法です。つまり、\(\boldsymbol{f}_i - \boldsymbol{C}_{ij}\)の中で最大の値を取ります。

 

また、\(\boldsymbol{f}\)を最適化の過程で探索し、その都度\(\boldsymbol{f}^C\)を計算して目的関数を

$$
\boldsymbol{a}^{\top} \boldsymbol{f}-\boldsymbol{b}^{\top} \boldsymbol{f}^C
$$

とすれば、実質的に双対問題の決定変数は\(\boldsymbol{f}\)だけとなります。これにより、問題は\(n\)次元の空間で解くことができます。

ここで、入力の条件\(a \in \Sigma_n\)より、\(a_i \geq 0\)であるので、\(f_i\)は大きい値をとるほど目的関数の値が大きくなります。

\(C\)変換と同様の考えより、\(g\)を固定したときの\(f\)の最適解\(g^{\bar{C}} \in \mathbb{R}^n\)も次のように定められます。

$$
\boldsymbol{g}_i^{\bar{C}} \stackrel{\text { def }}{=} \min _{j \in[m]} \boldsymbol{C}_{i j}+\boldsymbol{g}_j
$$

これを\(\bar{C}\)変換と言います。

物理的解釈

\(\bar{C}\)変換の物理的な解釈としては、青玉をすべて釘で固定し、各赤玉を糸が切れない範囲で引き上げる操作に対応します。これは、青玉(\(g\))が固定されている状態で、赤玉(\(f\))を可能な限り引き上げることを意味します。

まとめ

  • 最適な\(\boldsymbol{g}\)は\(\boldsymbol{f}\)を固定して\(C\)変換を用いて計算できます。
  • 最適化の過程で\(\boldsymbol{f}\)を探索し、\(\boldsymbol{f}^C\)をその都度計算することで、双対問題の決定変数を\(\boldsymbol{f}\)のみに絞ることができます。
  • \(\bar{C}\)変換を用いると、\(\boldsymbol{g}\)を固定したときの\(\boldsymbol{f}\)の最適解を求めることができる。

 

 

\(\bar{C}\)変換の実行可能性の定理

【定理】C~変換の実行可能性

任意の\(g \in \mathbb{R}^m\)について、\(\left(g^{\bar{C}}, g\right)\)は実行可能解である。

証明

任意の\(i \in[n], j \in[m]\)について

$$
\begin{aligned}
g_i^{\bar{C}}-g_j & =\left(\min _{k \in[m]} C_{i k}+g_k\right)-g_j \\
& \leq C_{i j}+g_j-g_j \\
& =C_{i j}
\end{aligned}
$$

 

\(\bar{C}\)変換の最小性の定理

【定理】C~変換の最小性の定理

任意の実行可能解\((f, g)\) と \(i \in[n]\)について、\(g_i^{\bar{C}} \geq f_i\)が成り立つ。

証明

$$
\begin{aligned}
g_i^{\bar{C}}-f_i & =\min _{j \in[m]} C_{i j}+g_j-f_i \\
& \geq 0
\end{aligned}
$$

 

\(\bar{C}\)変換の最適性の系

【系】C~変換の最適性

任意の実行可能解\((f,g)\)について、\(\left(g^{\bar{C}}, g\right)\)の目的関数値は\((f,g)\)の目的関数値以上である。

証明

$$
\begin{aligned}
\left(a^{\top} g^{\bar{C}}-b^{\top} g\right)-\left(a^{\top} f-b^{\top} g\right) & =a^{\top}\left(g^{\bar{C}}-f\right) \\
& =\sum_{i=1}^n a_i\left(g_i^{\bar{C}}-f_i\right) \geq 0
\end{aligned}
$$

 

ブロック座標上昇法

最適化問題を解く際に、複数の決定変数を持つ場合、それらを一度に最適化するのは難しいことがあります。そこで、一部の変数を固定して残りの変数を最適化し、その後固定した変数を更新する手法が有効です。このような手法をブロック座標上昇法と呼びます。

\(\boldsymbol{f}\)と\(\boldsymbol{g}\)の交互最適化

上記の性質を利用すると、以下の手順で最適化が可能です。

  1. \(\boldsymbol{f}\)を固定して\(\boldsymbol{g}\)を最適化:
    まず現在の\(\boldsymbol{f}\)を固定し、その\(\boldsymbol{f}\)に対して最適な\(\boldsymbol{g}\)を求めます。これは\(C\)変換を用いて計算されます。
    $$
    \boldsymbol{f}_j^{\boldsymbol{C}}=\max _{i \in[n]}\left(\boldsymbol{f}_i-\boldsymbol{C}_{i j}\right)
    $$
  2. \(\boldsymbol{g}\)を固定して\(\boldsymbol{f}\)を最適化:
    次に、更新された\(\boldsymbol{g}\)を固定し、その\(\boldsymbol{g}\)に対して最適な\(\boldsymbol{f}\)を求めます。これは\(\bar{C}\)変換を用いて計算されます。
  3. 上記手順を繰り返す:
    これらの手順を交互に繰り返すことで、\(\boldsymbol{f}\)と\(\boldsymbol{g}\)の組み合わせを次第に最適化していきます。

このように、決定変数を複数の部分(ブロック)に分けて、各部分を順番に最適化する手法を「ブロック座標上昇法」と言います。この手法の利点は、各ステップで解くべき最適化問題が単純化されるため、全体の最適化が効率的に進められることです。

しかし、これから示す定理で分かるように、適輸送問題においてブロック座標上昇法はうまくいきません

 

交互最適化は2回で収束する

【定理】交互最適化は2回で収束する

任意の\(f\)について、\(f^{C \bar{C} C}=f^C\)となる。すなわち、\(C\)変換と\(\bar{C}\)変換は高々2回の反復で収束する

 

証明

【定理】(C)変換の実行可能性

任意の\(f \in \mathbb{R}^n\)について\(\left(f, f^C\right)\)は実行可能解である。

【定理】(ar{C})変換の実行可能性

任意の\(g \in \mathbb{R}^m\)について、\(\left(g^{\bar{C}}, g\right)\)は実行可能解である。

より、\(\left(f, f^C\right),\left(f^{C \bar{C}}, f^C\right),\left(f^{C \bar{C}}, f^{C \bar{C} C}\right)\)はいずれも実行可能解である。\(\left(f, f^C\right)\) と \(\left(f^{C \bar{C}}, f^C\right)\)を比較すると、

【定理】(ar{C})変換の最小性

任意の実行可能解\((f, g)\) と \(i \in[n]\)について、\(g_i^{\bar{C}} \geq f_i\)が成り立つ。

より、すべての\(i\)に対して

$$
f_i^{C \bar{C}} \geq f_i
$$

となり、\(\left(f^{C \bar{C}}, f^C\right)\) と \(\left(f^{C \bar{C}}, f^{C \bar{C} C}\right)\)を比較すると、

【定理】(C)変換の最小性

任意の実行可能解\((f, g)\)と\(j \in[m]\)について、\(f_j^C \leq g_j\)が成り立つ

より、すべての\(j\)に対して

$$
f_j^{C \bar{C} C} \leq f_j^C
$$

となる。一方

$$
\begin{aligned}
f_j^{C \bar{C} C} & \stackrel{(\mathrm{a})}{=} \max _{i \in[n]} f_i^{C \bar{C}}-C_{i j} \\
& \stackrel{(\mathrm{b})}{\geq} \max _{i \in[n]} f_i-C_{i j} \\
& \stackrel{(\mathrm{c})}{=} f_j^C
\end{aligned}
$$

となる。ここで、(a),(c)は\(C\)変換の定義より、(b)はこの証明の一つ目の不等式より従う。二つ目の不等式と併せると\(f_j^{C \bar{C} C}=f_j^C\)となる。

つまり、二回交互最適化を行うだけでループしてしまいます。これでもし、一回の交互最適化でうまくいくならいいのですが、そうではない最適輸送の例が存在してしまったら、交互最適化はダメです。最適輸送においては使えません。

果たしてそんな例があるのでしょうか?

最適解ではない\(f\)が存在してしまう例

命題

\(\left(f^{C \bar{C}}, f^C\right)\)が最適解とはならない\(f\)が存在する

 

証明

次のような行列\(\boldsymbol{C}\)とベクトル\(\boldsymbol{a}\)と\(\boldsymbol{b}\)を考えます。

$$
\boldsymbol{C}=\left(\begin{array}{cc}
10 & 1 \\
1 & 1
\end{array}\right), \quad \boldsymbol{a}=\binom{1}{0}, \quad \boldsymbol{b}=\binom{1}{0}
$$

ここで行列\(\boldsymbol{C}\)はコスト行列、\(\boldsymbol{a}\)と\(\boldsymbol{b}\)は重みベクトルです。

 

まず、\(\boldsymbol{f}=(1,1)^{\top}\)とします。この\(\boldsymbol{f}\)に対して\(\boldsymbol{f}^C\)を計算します。

\(\boldsymbol{f}^C\)は次のように計算されます。

$$
\boldsymbol{f}_j^C=\max _{i \in[n]}\left(\boldsymbol{f}_i-\boldsymbol{C}_{i j}\right)
$$

各\(j\)に対して計算すると

\(j=1\) の場合:
$$
\boldsymbol{f}_1^C=\max (1-10,1-1)=\max (-9,0)=0
$$
\(j=2\) の場合 :
$$
\boldsymbol{f}_2^C=\max (1-1,1-1)=\max (0,0)=0
$$

従って、\(\boldsymbol{f}^C=(0,0)^{\top}\)となります。

 

つぎに、\(\boldsymbol{f}^{C \bar{C}}\)を計算します。

$$
\boldsymbol{f}_i^{C \bar{C}}=\min _{j \in[m]}\left(\boldsymbol{C}_{i j}+\boldsymbol{f}_j^C\right)
$$

各\(i\)に対して計算すると

\(i=1\) の場合:
$$
\boldsymbol{f}_1^{C \bar{C}}=\min (10+0,1+0)=\min (10,1)=1
$$
\(i=2\) の場合 :
$$
\boldsymbol{f}_2^{C \bar{C}}=\min (1+0,1+0)=\min (1,1)=1
$$

従って、\(\boldsymbol{f}^{C \bar{C}}=(1,1)^{\top}\)となります。

 

これらの結果を用いて、\(\left(\boldsymbol{f}^{C \bar{C}}, \boldsymbol{f}^C\right)\)の目的関数値を計算します。

$$
\boldsymbol{a}^{\top} \boldsymbol{f}^{C \bar{C}}-\boldsymbol{b}^{\top} \boldsymbol{f}^C
$$

各成分を代入して計算すると

$$
\begin{gathered}
\boldsymbol{a}^{\top} \boldsymbol{f}^{C \bar{C}}=(1,0) \cdot(1,1)^{\top}=1 \\
\boldsymbol{b}^{\top} \boldsymbol{f}^C=(1,0) \cdot(0,0)^{\top}=0
\end{gathered}
$$

従って目的関数値は

$$
1-0=1
$$

この例の最適値は10であるので、\(\left(\boldsymbol{f}^{C \bar{C}}, \boldsymbol{f}^C\right)\)の目的関数値1は最適値10よりも低いことが分かります。□

 

 

ありました。あってしまいました。

以上より、交互最適化により最適解を求めることはできません。この事実は、制約つき問題では一般にブロック座標上昇法が収束しないことに対応しています。制約も含めて目的関数を滑らかにすることで、ブロック座標上昇法を収束するように修正したものがシンクホーンアルゴリズムです。

まとめ

最適輸送問題におけるC変換と交互最適化は、効率的な解法として重要な役割を果たします。しかし、具体例を通じて示したように、交互最適化は必ずしも最適解に収束しない場合があります。

この問題を解決するためにシンクホーンアルゴリズムが導入され、収束性と最適解への到達が大幅に改善されました。

シンクホーンアルゴリズムのエントロピー正則化による滑らかな解の特性は、最適輸送問題において特に有効です。最適輸送問題の理解と解法の選択肢を広げることで、より複雑な問題にも対応できるようになるでしょう

 

参考文献

 

 

-幾何, 最適輸送, 解析