最適輸送の高速解法 —— シンクホーンアルゴリズムと行列スケーリング

前章では、最適輸送問題にエントロピー正則化を加えることで、強凸問題へ変換し解きやすくするアプローチを学びました。 本章では、そのエントロピー正則化された最適輸送問題の「双対問題」を導出します。そこから生まれる「シンクホーンアルゴリズム（Sinkhorn Algorithm）」が、実は行列の掛け算だけで実装できる極めて高速な手法であること、そして正則化パラメータを極限まで小さくすると、それが以前学んだ「C変換」にピタリと一致するという数理の繋がりを解説します。

1. エントロピー正則化の双対問題

エントロピー正則化項を加えた最適輸送のラグランジュ関数 は以下のようになります（非負制約はエントロピーの によって自然に満たされるため省きます）。

（※ ）

まず、このラグランジュ関数を各輸送量 について最小化します。偏微分して と置きます。

これを について解くと、最適輸送プランの具体的な形が得られます。

この を元のラグランジュ関数に代入して整理すると、双対変数 のみを変数とする双対問題（最大化問題）が導かれます。

元の厳密な双対問題にあった「」という厄介な不等式制約が消え、単なる制約なしの最適化問題に変化しました。これがエントロピー正則化の絶大な効果です。

2. 交互最適化による更新式の導出

この双対関数を最大化するため、 と についてそれぞれ偏微分して と置き、極値条件を求めます。

• についての偏微分：

これを について解き直します（ を の外に出して対数をとります）。

同様に、 についても対称な更新式が得られます。

この2つの式を交互に計算して と を更新していく手法こそが、**シンクホーンアルゴリズム（Sinkhorn Algorithm）**のベースとなる計算です。

3. Log-Sum-Exp と C変換の美しい繋がり

ここで、更新式に現れた という形に注目してください。 これは機械学習で「ソフトマックス」としても知られる Log-Sum-Exp関数 です。この関数は、最大値関数（）を滑らかに近似する性質（Soft-max）を持っています。

もし、エントロピー正則化の強さ をゼロの極限（）に近づけていくとどうなるでしょうか。

これを先ほどの の更新式に当てはめると、次のようになります（ の項はゼロに近づきます）。

なんと、これは以前の章で学んだ、厳密な最適輸送の双対解法である 変換 の式そのものです！同様に の更新式は C変換 に一致します。 エントロピー正則化による滑らかな Log-Sum-Exp の更新式は、温度パラメータ を下げることで、厳密な C変換・変換へと美しく帰着するのです。

4. 行列スケーリングとGPUによる高速化

シンクホーンアルゴリズムの実用的な驚異は、変数を指数変換することで現れます。 次のように、変数を置き換えてみます。

• ギブスカーネル：

この置き換えを用いて先ほどの更新式（対数をとる前の形）を書き換えると、信じられないほどシンプルな形になります。

これは要素ごとの割り算で表現されていますが、分母の部分は完全な**行列とベクトルの掛け算（ および ）**です。

2. （※ は要素ごとの割り算）

このように、ある行列 の左右から対角行列（ベクトル ）を掛けて行和と列和を指定した値（）に合わせる問題を行列スケーリング問題と呼びます。 シンクホーンアルゴリズムは、最適輸送問題を「単なる行列の掛け算と要素ごとの割り算の反復」へと変換しました。これにより、現代のGPUを用いた並列計算のパワーをフルに活用できるようになり、数万×数万といった巨大な次元の最適輸送問題であっても一瞬で解けるようになったのです。