技術要約：混合集団における因果探索

問題設定

本論文は、広範な（グローバルな）潜在的交絡が存在する場合の**因果探索（Causal Discovery）**の課題に取り組んでいる。著者らは、観測変数 $V$ が有向非巡回グラフ（DAG） $G$ から生成されるが、データが $k$ 個の異なる集団（潜在クラス）の混合であり、それが未観測の離散変数 $U$ によって決定されている状況を想定している。拡張グラフ $G'$ において、$U$ はすべての観測変数 $V \in V$ を指し示す共通の原因として機能する。

この構造は「グローバルな交絡因子」を生み出し、すべての観測変数のペアをd-接続（d-connect）させ、標準的な条件付き独立性（CI）テストを無効にする。$U$ はすべての分離集合に含まれるため、周辺分布 $Pr(V)$において観測変数の間の条件付き独立性は成立しない。潜在変数を伴う既存の因果探索手法は、通常、パラメトリックな仮定（線形性やガウス型ノイズなど）に依存しているか、あるいは潜在変数が少数の観測変数にのみ影響を与える（低出次数）ことを前提としている。本論文は、潜在的な交絡因子$U$が離散的であり、そのクラス数$k$ が既知であると仮定した上で、非パラメトリックな設定（任意の構造方程式およびノイズ関数）を対象としている。

手法

提案手法は、標準的なCIテストを行列ランク・テストに置き換え、3段階のアルゴリズム・フレームワークを利用する。

1. CIの一般化としてのランク・テスト

核心となる理論的洞察は、グローバルな交絡の下ではCIが成立しない一方で、**非負ランク（non-negative rank）**が確率行列のグラフ構造を明らかにするということである。

• 確率行列: 変数 $X, Y$ および条件付け集合 $C$ に対して、行列 $M[X, Y | c]$ はエントリー $Pr(x, y | c)$ によって定義される。
• ランク・補題: もし $X$ と $Y$ が真のDAG $G'$ において $C$ によってd-分離されているならば、行列 $M[X, Y | C]$ の非負ランクは高々 $k$（潜在クラス数）である。逆に、もしそれらがd-接続されているならば、ランクは一般的に $k$ より大きくなる。
• 仮説検定: 著者らは、Ratsimalahelo [2001] に基づき、特異値閾値処理よりも優れた、行列ランクに基づく統計的仮説検定を開発した。

2. 小規模アルファベットのための集約（Agglomeration）

観測変数がバイナリ（ベルヌーイ分布）である場合、実用的な課題が生じる。単一のペアはランクが最大2となる $2 \times 2$ 行列を生成するため、$k \ge 2$ を区別できない。

• 解決策: アルゴリズムは、$\lceil \lg(k+1) \rceil$ 個のバイナリ変数を、より大きなカーディナリティ（$k+1$）を持つ「スーパー変数」へと**集約（agglomerate）**する。
• 独立性を保持する集約（IPA）: この手法は、条件付け集合によってd-分離可能な変数の集合を探索する。そのような集合が存在する場合、集約されたスーパー変数はその確率行列においてランク $\le k$ を示し、これによりアルゴリズムは非隣接性を検出できる。

3. アルゴリズムのフェーズ

アルゴリズムは以下の3つのフェーズで進行する。

• フェーズI（集約ランク・テスト）: 条件付け集合と集約されたスーパー変数を反復的に扱う修正版PCアルゴリズム。これは、ランク $\le k$ の条件を満たす変数間のエッジを除去する。このフェーズは「スケルトン（隣接関係）」を回収するが、集約が不可能な「初期頂点」（非子を持つノード）において**偽陽性（FP）**のエッジを残す可能性がある。
• フェーズII（k-MixProd補正）: FPエッジを解決するために、アルゴリズムは k-MixProd 問題（積分布の混合の特定）のインスタンスを構築する。変数集合 $T_{ij}$（候補となるエッジの端点とその隣接ノードを含む）と、他の2つの互いに素な集約集合 $X_1, X_2$ を選択する。特定の集合 $Z_{ij}$（$X_1, X_2$ の隣接ノード）で条件付けることにより、アルゴリズムは $T_{ij}, X_1, X_2$ が $U$ を与えられたときに互いに独立であることを保証する。オラクルが結合分布 $Pr(T_{ij} | u)$ を解くことで、各潜在クラス内での標準的なCIテストを実行し、エッジの検証または除去を行うことができる。
• フェーズIII（方向付け）: 回復されたスケルトンと分離集合を用いて、v-構造とMeek則によりエッジの向きを決定する、標準的なPCアルゴリズムと同様の手順である。これにより、マルコフ同値類（MEC）を表す完備部分DAG（CP-DAG）が得られる。

主な貢献

1. 初の非パラメトリック・アルゴリズム: 本論文は、観測変数に対するパラメトリックな仮定（線形性やガウス性など）を置かずに、グローバルな離散的交絡因子が存在する混合設定において因果構造を特定する、初のアルゴリズムを提示している。
2. ランクに基づくテスト: 行列ランクのテストが、広範な交絡を伴う設定におけるCIテストの一般化であることを確立し、行列ランクに対する厳密な統計的仮説検定を提供している。
3. 集約テクニック: 低カーディナリティの設定においてランク制約を適用することを可能にするため、バイナリ変数をより大きなスーパー変数へと集約する手法を導入した。
4. 識別可能性の境界: 以下の識別可能性の十分条件を導出した：
   $$|V| \ge (\Delta^3 + 2\Delta^2 + 4\Delta + 2)\lceil \lg(k+1) \rceil + 2\Delta^2 + 2\Delta^3$$
   ここで $\Delta$ はDAGの最大次数である。このとき、因果構造はMECまで識別可能である。
5. 計算量分析: アルゴリズムは、非負ランクとk-MixProdのオラクルに依存し、$|V|$ に対して多項式時間、$\Delta$ および $\log(k)$ に対して指数時間で動作する。

実験結果

著者らは、既知のグラウンドトゥルース（正解）を用いた合成データを用いてアプローチを検証した。

• ランク・テストの有効性: 提案された行列ランクの仮説検定は、特にサンプルサイズが2,000を超える場合、特異値閾値処理よりも、接続された構造と分割されたグラフ構造を区別する上で大幅に優れている。
• 密度への感度: アルゴリズムは疎なグラフ領域（理論的焦点）において堅牢に動作し、エッジを正しく回収し、非エッジを除去する。グラフの密度が高まると（集約に必要な疎性の仮定を満たすことが困難になるため）、性能は低下するが、これは予想通りの挙動である。
• 比較: PC法やFCI法は、グローバルな交絡をモデル化できず、真の疎性に関わらず密なグラフを返してしまうが、提案手法は疎な領域において交絡による依存関係を効果的に除去できる。
• パラメータへの感度: 実験により、本手法は $k$ の選択に敏感であることが示された。誤った $k$ は、過度に密または過度に疎なグラフを導く。これは、実用的なチューニング戦略が存在することを示唆している。

意義と主張

本論文は、離散的な潜在クラスがすべての観測を交絡する不均一な集団における因果探索の理論的基礎を提供すると主張している。

• 理論的新規性: グローバルな交絡が存在しても、システムのサイズと疎性に対して潜在クラスの数が十分に小さければ、パラメトリックな制限なしに識別可能であることを示している。
• 実用的有用性: 標準的な手法がグローバルな交絡のために失敗するような、混合データソース（例：異なるデモグラフィックや環境）から因果構造を学習するための経路を提供する。
• 謙虚な姿勢: 著者らは、識別可能性の境界が十分条件ではあるものの、必ずしもタイトではない（「緩い」ワーストケースの境界である）ことを認めている。また、$k$ が既知である必要があることは、混合モデルに共通する制限であることも述べている（ただし、$k$ は推定やチューニングが可能である）。本アプローチは現在、離散的な観測変数に焦点を当てているが、モーメント行列を介した連続変数への拡張を示唆している。

本研究は、因果探索、混合モデル、およびテンソル分解を橋渡しし、複雑で不均質なデータ環境における因果構造を学習するための新しいツールセットを提供している。