シンクホーンアルゴリズムは、最適輸送問題にエントロピー正則化を導入し、行列の行と列の正規化（スケーリング）を交互に繰り返すことで、確率分布間の距離（シンクホーン距離）を高速に計算する手法です。従来の線形計画法に比べて計算量が劇的に削減され、GPUによる並列化も容易なため、機械学習や画像処理分野における大規模データ解析に広く応用されています。
シンクホーンアルゴリズムとは
シンクホーンアルゴリズムとは、最適輸送問題における「エントロピー正則化」を伴う最適輸送コスト（シンクホーン距離）を、行列の行と列の正規化（スケーリング）を交互に繰り返すことで極めて高速に計算する反復アルゴリズムです。一言で言えば、大規模なデータの確率分布同士を、高速かつ滑らかにマッチングするための最適化手法です。
詳しく解説
近年、確率分布間の距離を測定する「最適輸送」の概念が機械学習において重要視されています。しかし、伝統的な最適輸送（ワッサースタイン距離）の計算は線形計画法を用いるため、データ量に対して計算量が非常に大きく、大規模データへの適用が困難でした。これに対し、目的関数に「エントロピー正則化」項を加えることで、問題が強凸な最適化問題に変換されます。このエントロピー正則化された最適輸送問題を解くために、シンクホーンアルゴリズムが用いられます。このアルゴリズムは、行列の行と列を交互にスケーリングして特定の確率制約を満たすように変形する「行列スケーリング」の繰り返しだけで構成されているため、GPU等を用いた並列計算が極めて容易であり、計算時間を大幅に短縮できます。
具体例・使われ方
具体的な利用例として、画像処理における「画像のアライメント」や、異なる言語間の単語の埋め込みベクトルを対応付ける「教師なし機械翻訳」などが挙げられます。また、生成敵対ネットワーク（GAN）などの深層学習モデルにおいて、生成されたデータ分布と実データの分布の間の「ワッサースタイン距離」を近似計算する際の損失関数としても利用されています。
似た用語との違い
伝統的な「ワッサースタイン距離」の厳密な計算では、ネットワークフローアルゴリズムや線形計画法が用いられますが、これらは計算量がデータの3乗オーダー以上と大きく実用性に難があります。一方、シンクホーンアルゴリズムは「エントロピー正則化」を導入することで、厳密な最短距離を求める代わりに実用的な精度での近似計算を行い、行列演算による超高速な最適輸送計算を可能にしています。
注意点
シンクホーンアルゴリズムにおける「エントロピー正則化」のパラメータ（正則化の強さ）の調整は非常に重要です。正則化を強くしすぎると、近似の誤差が大きくなり最適輸送の解が平均化されてぼやけた結果になってしまいます。逆に正則化を弱くしすぎると、計算が数値的に不安定になりアンダーフローなどが発生してしまい、収束が遅くなったり計算に失敗したりするリスクがあります。