Sinkhornアルゴリズムにおける重要度スパージファイケーションの重要性

arXiv stat.ML / 2026/4/7

💬 オピニオンIdeas & Deep AnalysisModels & Research

共有:

要点

本論文では、エントロピー正則化最適輸送（OT）および非釣り合いOT（UOT）のためのSinkhornアルゴリズム計算を高速化する重要度スパージファイケーション手法であるSpar-Sinkを提案する。
Spar-Sinkは、未知の最適輸送プランに対するサンプリング確率を導出するために自然な上界を用い、疎なカーネル行列を構築することで、反復あたりの計算量をO(n^2)からおよそO(n)へと削減する。
提案する推定量が、穏やかな正則性条件のもとで一貫性（consistent）を満たすことを証明し、理論的保証を与える。
合成ベンチマークでの実験により、主流の競合手法と比べて推定誤差と実行時間の両方が改善されており、精度と効率の向上が示される。
実データとしての心エコー図のケーススタディでは、Spar-Sinkが心周期を推定・可視化し、古典的なSinkhornと同等の精度で収縮終期の時刻を予測できる一方、計算量を大幅に削減できることが示される。

Abstract

Sinkhornアルゴリズムは、最適輸送（OT）および不均衡最適輸送（UOT）問題の解を近似するために、広く用いられてきました。しかし、その実運用における適用は計算複雑性が高いために限られています。計算負荷を軽減するために、エントロピー正則化OTおよびUOT解を効率的に近似する、新しい重要度スパーシファイ（重要度間引き）手法であるSpar-Sinkを提案します。具体的には、本手法は、未知の最適輸送計画に対する自然な上界を用いて効果的なサンプリング確率を構築し、さらに疎なカーネル行列を構成してSinkhorn反復を高速化します。これにより、サンプルサイズ

n

に対する各反復あたりの計算コストを

O(n^2)

から

ilde{O}(n)

へと削減します。理論的には、正則化OTおよびUOT問題に対する提案推定量が、穏やかな正則性条件の下で一貫性（consistent）を持つことを示します。さまざまな合成データに関する実験では、Spar-Sinkが推定誤差と速度の両面で主流の競合手法を上回ることが示されます。実世界の心エコー図データの解析では、Spar-Sinkが心臓サイクルを効果的に推定し可視化できることが示され、そこから心不全や不整脈を同定できます。心臓サイクル予測の数値精度を評価するために、終収縮期（end-systole）の時点を、終拡張期（end-diastole）を用いて予測するタスクを考えます。その結果、Spar-Sinkは従来のSinkhornアルゴリズムと同程度の性能を示し、計算時間は大幅に少なくて済むことが分かりました。