技術的概要：教師なしによる構造からの順列学習

問題定義

多くの学習タスクでは、観測時点でデータが自然に順序付けられておらず、潜在的な構造を明らかにするために隠れた順列の回復が必要となる。例としては、ソート（単調性の回復）、ジグソーパズルの再構築（空間的連続性の回復）、および巡回セールスマン問題（TSP）などの経路探索問題が含まれる。これらの設定では、真の順列（ground-truth permutations）がしばしば利用不可能であり、直接的なラベルによる教師信号ではなく、滑らかさ、単調性、幾何学的整合性などのタスク固有の構造的性質に駆動された教師なし学習が必要となる。

微分可能な順列学習、特に Gumbel–Sinkhorn 法における最近の進展により、順列を連続的な緩和を通じて最適化される潜在演算子として扱うことが可能となった。これらの手法は、Birkhoff 多面体内の二重確率行列を用いて離散的な順列行列を近似するものであり、グローバルな温度パラメータ $\tau$（または逆温度 $\beta$）によって制御される。しかし、問題の規模と曖昧さが増大するにつれて、決定的な制限が生じる：アサインメント行列の異なる部分が異なる速度で解決されるのである。訓練の初期段階ですでに確定的となる行/列がある一方で、対称性や弱い構造的手がかりのために他の行/列は曖昧なまま残る。単一のグローバル温度は、すべてのアサインメントを同時に鋭くするか拡散させることを強制し、安定性と離散化の間の避けられないトレードオフを生み出す。過激なアニーリングは早期の誤りを固定してしまう一方、保守的なアニーリングは、大規模で曖昧な順列の収束を妨げてしまう。

手法

著者らは、単一のグローバル温度を、アサインメントの不確実性に基づいて局所的に変化する行および列依存の逆温度場と置き換える、エントロピー適応型 Gumbel–Sinkhorn 定式化を提案する。このアプローチは、現在のソフト順列アサインメントの不確実性に基づいて温度を調節する。

中核メカニズム

1. エントロピー推定: 各訓練ステップにおいて、基本逆温度 $\beta_0(t)$ を用いて決定論的なソフトアサインメント $Q$ が計算される：
   $$Q = \text{Sinkhorn}(\beta_0(t) \cdot \text{stopgrad}(S))$$
   ここで $S$ は適合性スコアを表す。stop-gradient は、エントロピー制御器が温度推定そのものを通じた逆伝播を行わないようにする。
2. 不確実性の計算: $Q$ から正規化された行および列のエントロピー（$H^{\text{row}}_i$ および $H^{\text{col}}_j$）が計算される。ゼロに近い値は確信度の高いアサインメントを示し、1 に近い値は高い不確実性を示す。
3. 適応型温度場: 要素ごとの逆温度場 $\beta \in \mathbb{R}^{n \times n}$ が構築される。高エントロピーの行または列に対しては、探索を維持するために逆温度が低下（実効温度の増加）される。低エントロピー領域では、離散化を促進するために逆温度は基本レベルのまま維持される。
   $$\beta^{\text{row}}_i = \frac{\beta_0(t)}{1 + b(H^{\text{row}}_i)}, \quad \beta^{\text{col}}_j = \frac{\beta_0(t)}{1 + b(H^{\text{col}}_j)}$$
   ここで $b(\cdot)$ は、エントロピーが閾値 $H_0$ を超えた場合にのみ作動する有界な単調関数である。最終的な要素ごとの場は平均値となる：$\beta_{ij} = \frac{1}{2}(\beta^{\text{row}}_i + \beta^{\text{col}}_j)$。
4. サンプリング: 最終的なソフト順列 $P$ は、この適応型場を用いてサンプリングされる：
   $$P = \text{Sinkhorn}(\beta \odot (S + g))$$
   ここで $g$ は Gumbel ノイズであり、$\odot$ は要素ごとの乗算を表す。

理論的解釈

本論文は、要素ごとの逆温度場を用いた Sinkhorn 正規化の適用が、局所的に再スケーリングされたコストを持つエントロピー正則化アサインメント問題の解決と等価であることを確立する。これは、適応型温度制御が曖昧な領域における対称性の破れを遅らせつつ、確信度の高い領域の集中を可能にし、かつグローバルな二重確率制約を維持するという、最適輸送の解釈を提供する。

主要な貢献

1. 統合フレームワーク: 再順序付けされたデータ上のタスク固有の構造的損失から直接潜在演算子としての順列を学習するためのフレームワーク。真の順列なしでの教師なし学習を可能にする。
2. エントロピー適応型 Gumbel–Sinkhorn: グローバル温度を、アサインメントエントロピーから導出される局所的に変化する場と置き換える新規バリアント。これにより、確信度の高いアサインメントは早期に離散化しつつ、曖昧な領域での探索を維持することが可能となる。
3. 最適輸送解釈: 適応型温度制御が Birkhoff 多面体上の局所コスト再スケーリングと等価であることを証明し、手法の挙動に対する理論的基盤を提供する。
4. 実証的検証: ソート、ジグソー再構築、教師なし TSP における実証により、エントロピー適応制御が、固定またはグローバルにアニーリングされたベースラインよりも、特に問題規模（$n$）とアサインメントの曖昧さが増大するにつれて、より信頼性の高い収束と高品質な順列をもたらすことが示された。

実験結果

本手法は 3 つの主要タスクで評価された：

• リストソート: 高い曖昧さを持つデータセット（値が $[10, 11]$ の範囲）において、エントロピー適応型温度は、グローバルアニーリングおよび NeuralSort を一貫して上回った。$n$ が 300 まで増加するにつれて性能差は広がり、適応型手法は著しく高い Kendall $\tau$ スコアを維持した。
• ジグソー再構築: CelebA-Test 画像をグリッド（最大 $7 \times 7$）に分割したタスクにおいて、適応型手法は、グローバルアニーリングと比較して、より高い Kendall $\tau$ と、ランダムシード全体にわたるより安定した収束を達成した。改善は、境界整合性の手がかりが曖昧になる大規模なパズルで最も顕著であった。
• 教師なし TSP: UTSP プロトコルに適用した際、本手法（次数違反に基づく適応バリアントを使用）は、標準的な Gumbel–Sinkhorn および UTSP ベースラインと比較して、特にノード数が多い場合（$n=500, 1000$）に、経路長と最適性ギャップを削減した。

すべてのケースにおいて、適応型手法はハイパーパラメータの選択（エントロピー閾値 $H_0$ および最大ブースト $b_{\text{max}}$）に対して頑健であり、高曖昧性領域におけるグローバル温度スケジュールに関連する不安定性を回避した。

意義と主張

本論文は、構造からの効果的な順列学習は、最適化中にどこで、いつエントロピーが崩壊するかを管理することに決定的に依存すると主張する。アサインメントの不確実性が不均質であることを認識することで、提案手法は、グローバル温度スケジュールに内在する安定性 - 離散化のトレードオフを解決する。

著者らは、この作業を、基礎となる緩和幾何学や収束特性を変更することなく、スケーラビリティと安定性を向上させる Gumbel–Sinkhorn ファミリーへの軽量な拡張として位置づけている。手法は最適化の安定性を向上させるが、高度に対称的または情報が弱い目的関数における根本的な曖昧さを解決するものではなく、何らかの対称性の破れ（例えば、ジグソーパズルにおけるアンカータイル）が依然として必要となる可能性があることに言及している。

将来の方向性としては、エントロピー適応制御をエンドツーエンドで学習すること、および不確実性認識型離散化をより複雑な組合せ構造やマルチモーダルマッチング問題へ拡張することが挙げられる。