技術的概要：AVATAR – 能的最適輸送によるアライメント学習

1. 問題定義

アライメントは、マルチネットワーク分析、マルチモーダル学習、ポイントクラウド登録を含む機械学習における基本的なタスクである。その目的は、2 つのデータ点の集合間の意味のある対応関係を特定することである。最近、最適輸送（OT）は、コスト関数と周辺制約から導出される輸送計画に基づいてオブジェクトレベルのアライメントを推論することにより、これらの問題を解決するための堅牢な枠組みとして登場した。

しかし、OT ベースのアライメント手法は、監督の量と品質に対して極めて敏感である。実際には、高品質な監督（例えば、真の対応関係）を取得することが高コストであったり不可能であったりするため、疎な監督への依存を余儀なくされる。能動学習は、最も情報量の多いサンプルを選択して問い合わせることを目指すが、既存の能動アライメント手法は、OT に適用される際に以下の 3 つの主要な限界を有している：

1. OT 固有の最適化の欠如： 既存の手法は、コスト関数や周辺制約といった OT の主要コンポーネントを効果的に利用していない。
2. 原理的な影響定量化の欠如： 新しい監督信号が制約付き OT 定式化を介して伝播し、グローバルなアライメント結果にどのように影響するかを定量化する厳密な方法が存在しない。
3. 汎用性の低さ： 以前の能動アライメント戦略は、多くの場合タスク固有（例えば、ネットワーク整合性のみに設計されている）であり、他の OT ベースのタスクやドメインへの汎化が十分でない。

本論文は、能動的 OT ベースのアライメントの問題、すなわち、残りのラベルなしオブジェクトのアライメント性能の向上を最大化するために、オラクル（例えば、人間の注釈者）から問い合わせるソースオブジェクトの固定予算を選択する問題を扱う。

2. 手法：AVATAR

著者らは、OT ベースのアライメントに本質的に設計された原理的な枠組みであるAVATAR（Active Optimal Transport via Alignment via Active Optimal Transport）を提案する。核心的な革新は、勾配伝播を介してグローバルなアライメント結果に対する候補問い合わせの事後影響を測定することで、候補問い合わせの情報量を定量化することにある。

2.1. 勾配ベースの問い合わせ影響

AVATAR は、真のアライメントを問い合わせることが輸送計画 $T$ に対するグローバルなユーティリティ関数 $f(T)$ をどのように変化させるかを推定することにより、候補ソースオブジェクト $x_i$ を評価する。

• ペアごとの影響： 特定のペア $(x_i, y_j)$ を問い合わせる影響は、監督信号 $H_{i,j}$ に対するユーティリティ関数の勾配（すなわち、$\nabla_{H_{i,j}} f$）として定義される。
• 連鎖律分解： この勾配は、コスト行列に対する監督の影響 ($\nabla_{H_{i,j}} \tilde{C}$) と、ユーティリティ関数に対するコスト行列の影響 ($\nabla_{\tilde{C}} f$) に分解される。
• 課題： 輸送計画 $T$ は大規模な制約付き最適化問題によって定義されるコスト行列 $\tilde{C}$ の陰関数であるため、OT 定式化を通じた微分は困難である。ヤコビアン $\frac{dT}{d\tilde{C}}$ を明示的に計算することは計算量的に非現実的である（$O((nm)^2)$）。

2.2. 随伴状態法と線形システム

微分の課題を克服するために、AVATAR は勾配計算を再定式化するために随伴状態法を利用する。

• 線形システムの再定式化： 巨大なヤコビアンの逆行列を計算する代わりに、この手法は随伴ベクトル $y_\alpha$ と $y_\beta$ を含む $(n+m)$ サイズの線形システムを導出する。勾配 $\nabla_{\tilde{C}} f$ は以下のように計算される：
  $$\nabla_{\tilde{C}} f = \frac{1}{\epsilon} T \odot (y_\alpha \mathbf{1}_m^\top + \mathbf{1}_n y_\beta^\top - \nabla_T f)$$
  ここで、$\epsilon$ はエントロピー正則化重みである。
• システムの求解： この線形システムの係数行列は特異であるが半正定値である。著者らは、共役勾配（CG）法がこのシステムを解き、グローバル最適解への収束を保証することを証明している。
• 計算量： 輸送計画 $T$ の疎性（OT 応用では一般的に疎である）を利用することで、CG 法は問い合わせバッチあたり線形時間計算量 $O(K(n+m))$ を達成する。ここで $K$ は CG 反復回数である。

2.3. 事後オブジェクト問い合わせ影響

ソースオブジェクト $x_i$ に対する総影響は、潜在的なターゲット上の事後分布として機能する現在の輸送計画確率 $T_{i,j}$ によって重み付けされたペアごとの影響の集約である：
$$I(p_i) = \sum_{j=1}^m T_{i,j} I(p_{ij})$$
これにより、AVATAR はグローバルなアライメント品質に対する期待影響が最も高いソースオブジェクトを選択できる。

2.4. ユーティリティ関数

AVATAR はタスク非依存であり、アライメント品質を符号化する効果的なユーティリティ関数 $f(T)$ を利用する：

• $f_{L2}$： 確定的なアライメント（置換行列の近似）を促進する。
• $f_{entropy}$： エントロピー正則化 OT 目的関数と整合するアライメントを促進する。
• $f_{consist}$： ネットワークアライメントに特化して設計され、アライメントされたノードの近傍は類似したアライメント結果を共有すべきであるという整合性の原則を強制する。

3. 主要な貢献

1. 問題の定式化： 本論文は、OT ベースのアライメントに特化した能動学習の問題を初めて定式化したものである。
2. 新規手法（AVATAR）： エントロピー正則化 OT 定式化を通じた勾配伝播を介して候補の情報量を定量化し、陰的な制約を処理するために随伴状態法を利用する手法を提案する。
3. 理論的解析： 勾配計算の正確性、解の線形時間計算量、および使用される共役勾配法の線形収束率を確立する証明を提供する。
4. 実証的検証： ネットワークアライメント（NA）、画像 - テキスト検索、画像 - テキストグラウンディングという 3 つの多様なアライメントタスクにおける有効性を実証する。

4. 実験結果

8 つのデータセットを用い、4 つの OT ベースのアライメントアルゴリズムと 9 つのベースライン能動学習手法で実験が行われた。

• 有効性： AVATAR は、同じ問い合わせ予算の下で、既存の能動学習アプローチ（ランダム、エントロピー、マージン、および GibbsMatchings のようなタスク固有の手法を含む）を一貫して上回った。
  • ネットワークアライメントにおいて、AVATAR はベースラインに対して最大 2.8% の平均逆数ランク（MRR）の向上を達成した。
  • 画像 - テキストタスクにおいて、AVATAR は最良の Recall@1 を達成し、ベースラインを最大 2.6% 上回ることが多かった。
• 効率性とスケーラビリティ： AVATAR は、性能と効率の間の強力なバランスを示した。一部のベースライン（例えば TopMatchings）と比較して、問い合わせ時間において最大25 倍の高速化を達成しながら、MRR を最大 8.1% 向上させた。合成グラフ上のスケーラビリティテストは、ノード数に対して線形にスケーリングすることを確認した。
• 収束性： 事後システムを解くために使用される共役勾配法の経験的解析は、急速に収束し、OT ソルバー自体に使用される Sinkhorn アルゴリズムよりもエントロピー正則化重み $\epsilon$ に対して敏感でないことを示した。
• アブレーション研究：
  • 疎行列 vs 密行列： 疎行列演算を使用することは、精度を損なうことなく効率を大幅に向上させた（最大 8.6 倍の高速化）。
  • 事後集約： 集約のための事後重みとして輸送計画 $T$ を使用することは、均一な集約よりも優れていることが証明された。

5. 意義と主張

本論文は、AVATAR が最適輸送の文脈における能動学習のための原理的かつタスク非依存の枠組みを提供すると主張している。その意義は以下の点にある：

• ギャップの埋め合わせ： 監督の OT 定式化を通じた伝播を明示的にモデル化することで、既存の能動アライメント手法の重要な限界に対処する。
• スケーラビリティ： 勾配計算を線形計算量を持つ解決可能な線形システムに再定式化することで、以前は計算的に不可能であった大規模なアライメント問題に対して能動学習を実行可能にする。
• 汎用性： この枠組みは、タスク固有の問い合わせヒューリスティックを必要とするのではなく、単にユーティリティ関数を変更するだけで、ネットワークやマルチモーダルデータなど多様なアライメントタスクに適用可能である。

著者らは、AVATAR が最小限の監督でアライメント性能を効果的に向上させ、高品質なラベルが不足しているか取得に高コストなシナリオに対する堅牢な解決策を提供することを結論付けている。