Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound

技術的概要：エッジごとの不可能性証明書を用いた反復的因果発見

問題定義
現在の因果発見アルゴリズムは、通常、完全に方向付けられた有向非巡回グラフ（DAG）を返すが、データによって特定されたエッジの方向と、出力制約を満たすためにアルゴリズムによって課されたエッジの方向を区別することに失敗している。標準的なマルコフ条件と忠実性の条件下では、観測データはマルコフ同値クラスのみを特定する；v-構造上にないエッジの方向付けは、結合分布によって決定されない。既存の手法は、診断的な正当性なしに識別不可能なエッジに方向付けを強制する（例：NOTEARS、DAGMA）か、それらを方向付けずに残す（例：FCI）が、それらを解決するために必要な具体的な事前情報を指定しない。さらに、連続最適化手法は、真の識別を模倣するデータアーティファクト（例：varsortability）を悪用することが示されている。データ駆動型の識別可能性とアルゴリズムによる課与を明確に分離し、識別不可能なエッジを解決するために必要な具体的な専門家への質問を特定する、原理的なプロトコルが存在しない。

手法
本論文は、連続データに対する観測的因果発見のための決定論的、3段階プロトコルを提案する。このプロトコルは、データのみから構築されたスケルトン内のすべての候補エッジに対して離散的な「不可能性証明書」を出力し、エッジを解決済み（データによって特定または媒介された）または不可能（データ不十分であり、専門家の入力が必要）のいずれかに分類する。

1. ステージ1：スケルトンと媒介変数探索

   • FDR制御された HSIC 検定を用いて、辺縁的に独立なペアを破棄し、スケルトンを構築する。
   • 多段の媒介変数探索を行い、観測変数によって媒介されるエッジを特定し、削除する。

2. ステージ2：ゲート付き識別可能性カスケード

   • 8段階のカスケードが、残りのエッジを評価する。段階には、古典的手法（線形 ANM $L_0$、非線形 ANM $L_1$、HOC LiNGAM $L_2$）と、本論文で導入された 5 つの新しい段階が含まれる：LSNM（位置・スケーリングノイズ）、IGCI（情報幾何学）、Stein（スコアマッチング）、MDL（アルゴリズム的マルコフ条件）、およびPEIT（エントロピー逆転テスト）。
   • ゲート機構：各段階は、統計的検定（非ガウス性のためのシャピロ・ウィルク検定、異分散性検定など）によって事前条件付けされる。ある段階の事前条件が満たされない場合、その段階は方向付けを強制するのではなく、棄権する。
   • 段階間コンセンサス：「不一致ガード」は、より高精度の段階（IGCI、Stein、MDL）が方向に矛盾する場合、$L_0$ のコミットを降格させ、エッジを impossible_l0_disagrees_with_high_tier として再ラベルする。
   • どの段階によっても解決されなかったエッジは、失敗モード（例：潜在交絡、弱い非線形性）と、それに対応するドメイン専門家への質問を符号化した impossible_* ラベルを受け取る。

3. ステージ3：ターゲット型オラクルクエリ

   • プロトコルは、impossible_* とラベル付けされたエッジに対してのみ、ドメイン専門家と対話する。
   • クエリプリミティブ：
     • エッジごとのクエリ：方向（FWD/BWD）または不在を問う。
     • メタハブクエリ：出力次数による上位 $K$ 個のノードを問う。
     • ノード・子クエリ：特定のノードの直接の子を問うことで、すべての外向きエッジを同時にコミットする。
   • 自動伝播：各オラクルのコミット後、システムはゼロコストの自動解決パス（非巡回性チェック、ミークルール、推移的 d-分離）を実行し、追加のクエリなしに追加のエッジを解決する。

主要な貢献

1. エッジごとの証明書：プロトコルは、すべてのエッジに離散コードを割り当てる。resolved_* コードは方向を正当化する特定の定理（例：$L_{Stein}$）を引用し、impossible_* コードは失敗モードとそれを解決するために必要な具体的な質問を記録する。
2. 段階を認識した棄権：5 つの新しいゲート付き段階（LSNM、IGCI、Stein、MDL、PEIT）の導入により、特定の識別可能性定理が満たされた場合のみ方向付けがコミットされることを保証する。事前条件が満たされない場合、システムは潜在的に偽の方向付けを強制するのではなく棄権する。
3. $1+K$ 相互作用境界：本論文は、真の DAG を回復するための情報理論的上限を $1+K$ 回の専門家相互作用として確立する。ここで $K$ は非葉ノードの数である。これは、ターゲットを特定するための単一のメタハブクエリと、$K$ 回のノード・子クエリを組み合わせることで達成される。
4. ターゲット型引き出し：完全なトポロジカル順序や広範な介入を要求する可能性のある能動学習手法とは異なり、本プロトコルは識別不可能なエッジのみを分離し、それらを解決するために必要な具体的な情報を要求する。

実験結果
本プロトコルは、4 つの標準ベンチマーク（Asia、Sachs、Child、Alarm）と、特定の段階をストレステストするように設計された合成データで評価された。

• 理想的オラクル性能：完全なオラクルを仮定すると、プロトコルはすべての 4 つのベンチマークで、正確に $1+K$ 回の相互作用を用いて、真の DAG を Precision = Recall = F1 = 1.000 で回復した。
  • Alarm (V=37): 27 回の相互作用で 46 本のエッジを回復。
  • Sachs (V=11): 8 回の相互作用で 17 本のエッジを回復。
• カスケードの有効性：Sachs データセットにおいて、カスケード単独で、データのみから 19 本の真のエッジのうち 5 本を解決した。新しい安全な段階の追加により、不一致ガードがアクティブな場合、方向の精度はベースの L0-L2 の 61.5% から 66.7% に向上した。
• 段階の特異性：合成ストレステストは、各新しい段階がそのネイティブ領域（例：位置・スケーリングノイズにおける LLSNM、ほぼ決定論的データにおける LIGCI）において精度が正であることを確認し、オフ領域のデータでは棄権（40 件中 0 件発火）し、偽陽性を防止することを示した。
• パレートフロンティア：Sachs において、プロトコルはクエリ数と F1 スコアの間のトレードオフを示した。「SAFE のみ」のアプローチ（オラクルなしのカスケード）は、5 回のクエリで F1=0.571 を達成したが、完全なプロトコルは、オラクルの負担を軽減するためにカスケードを使用することで、13 回のクエリで F1=1.000 を達成した。

意義と主張
本論文は、因果発見における根本的なギャップ、すなわち、現在の手法がデータによって特定された方向とアルゴリズムによって課された方向を区別できないという課題に対処すると主張する。すべてのエッジに「証明書」を添付することで、プロトコルは透明な監査証跡を提供する。

• 理論的貢献：$1+K$ 境界は、専門家の知識が利用可能な場合の DAG の解決に必要な最小情報を定量化するものであり、能動的因果発見における介入予算境界に対する引き出し側の対応物である。
• 実用的有用性：本プロトコルにより、実践者は専門家の労力を識別不可能なエッジに専ら集中させることができ、生のエッジ方向ではなく、領域認識型の具体的な質問を提示することで認知的負荷を軽減する。
• 限界：著者は明示的に、現在の範囲は連続変数に制限されており、離散ベイズネットワークはオラクル層の堅牢性チェックとしてのみ扱われることを指摘している。プロトコルは完全なオラクルを仮定しており、ノイズのある確率的な専門家応答の処理は将来の課題として特定されている。さらに、スケルトン構築段階はリコール制限を課す。初期の HSIC 検定によって剪定されたエッジは回復できないためである。

この研究は、スケーラブルな連続最適化や制約ベースの手法の代替としてではなく、エッジごとの監査可能性を優先し、ターゲット型で証明書駆動のクエリを通じて専門家の引き出しコストを最小化する、直交するアプローチとして位置付けられている。