技術要約：k次オーダーの忠実性仮定の緩和による高次マルコフ・ブランケットの発見

問題提起

マルコフ・ブランケット（MB）発見問題とは、ターゲット変数 $Y$ のグラフ上のMBを、結合分布 $P$ からサンプリングされたデータセットから推論することである。このタスクは、ベイジアンネットワーク（BN）やマルコヴ確率場（MRF）における構造学習、因果探索、および特徴量選択において基本的である。

既存のほとんどの制約ベースのMB発見手法は、**忠実性仮定（faithfulness assumption）**に依存している。これは、「分布 $P$ における任意の条件付き独立性は、グラフ構造 $G$ における対応する分離を意味する（かつその逆も然り）」という前提である。しかし、この仮定は以下の2つの方法で頻繁に破られる：

1. 真の違反（True Violations）: ノイジーなXORや高次のパリティ関数のような特定の関数的関係は、グラフ構造に対して「不忠実（unfaithful）」な依存関係を生み出す。例えば、$k+2$ 個の変数を含むノイジーなパリティ関数の場合、変数がグラフ内で接続されているにもかかわらず、ペアワイズ（2変数間）および低次の条件付き独立性が存在する可能性がある。
2. 経験的違反（Empirical Violations）: 真の分布が忠実であっても、有限のサンプルサイズによって統計的誤差が生じ、経験的な条件付き独立性が真の分布と一致しない場合がある。極端なケースでは、小規模なサンプルにおいて、アルゴリズムが真のMBを回収できなかったり、偽の依存関係を発見したりすることがある。

2-隣接忠実性（2-adjacency faithfulness）のような従来の緩和策は、3変数（XOR型）の関係は扱えるものの、より多くの変数に関わる高次のパリティ関係を捉えることはできない。

手法

$k$ 次オーダーの忠実性緩和

著者らは、忠実性の仮定を一般化した$k$ 次オーダーの忠実性を提案している。この緩和策は、$k+2$ 個の変数間のパリティ型の依存関係を捉えるように設計されている。

• $k$ 次オーダーの依存関係: 2つの変数 $Y$ と $X$ は、集合 $Z$（$|Z|=k$）を条件付けることで、分離集合 $S$ のいかなる部分集合を加えても条件付き依存性を維持する場合、$Z$ に対して $|Z|$ 次オーダーの依存関係にあると定義される。
• 仮定: グラフ $G$ が $P$ に対して $k$ 次オーダーの忠実性を持つとは、任意の変数 $Y, X$ および任意の集合 $S$ について、ある $Z$（サイズ $\le k$）と $S' \subseteq S$ を用いて $Y$ と $X$ が条件付き独立であるならば、$Y$ と $X$ は $S$ によってグラフ上で分離されていることを指す。
• 対偶: もしグラフにおいて $Y$ と $X$ が $S$ によって分離されていないならば、$Y$ と $X$ は $S$ に関して $Z$（サイズ $\le k$）を介して関連（依存）しているはずである。

計算の実現可能性を高めるため、著者らは**$l$ 有界セパレータ仮定（$l$-bounded separator assumption）**を導入している。これは、もし $Y$ と $X$ が大きな集合を条件付けることで条件付き独立になるならば、その集合の部分集合であり、サイズが $\le l$ である集合が存在して、それらも両者を独立にさせるという仮定である。これにより、CIテストにおける条件付け集合の探索空間が制限される。

kOMB アルゴリズム

論文では、これらの新しい仮定の下で動作するように Grow and Shrink (GS) アルゴリズムを修正した概念実証アルゴリズムである kOMB ($k$-order Markov blanket) を紹介している。

1. Growフェーズ: 個々の変数をテストする代わりに、kOMBは現在の候補MBに現在の候補MBを条件付けることで、$Y$ と他の変数の間の依存関係を明らかにするような、最大サイズ $k$ の変数の部分集合を反復的に探索する。これは「相互関連（inter-associated）」する集合を特定するために再帰的探索（find_inter_dep）を利用する。
2. Shrinkフェーズ: 残りのMB変数の部分集合（$l$ で制限）によって $Y$ から分離できる場合、アルゴリズムはその変数を候補MBから削除する。
3. 理論的保証: グローバル・マルコフ特性、$k$ 次オーダーの忠実性、および $l$ 有界セパレータ仮定の下で、kOMBが変数のグラフ上のMBを正しく回収することを著者らは証明している。

主な貢献

1. 理論的枠組み: $k+2$ 個の変数に関わる高次のパリティ関係を扱うために、従来の緩和策（2-隣接忠実性など）を一般化した$k$ 次オーダーの忠実性の定義。
2. アルゴリズムの実装: 高次の依存関係が存在する状況下でMBの発見を可能にする、制約ベースのアルゴリズムである kOMB の開発。
3. 実証的検証: 従来のメソッドが真の不忠実性（例：パリティ関数）や経験的不忠実性（有限サンプル効果）によって失敗するシナリオにおいて、kOMBがMBを回収できることを実証。

実験結果

合成データ

著者らは、ターゲット $Y$ が5種類の異なるブール関数（XOR、パリティ、"exactly-1"を含む）によって生成された4変数の合成ベイジアンネットワークを用いてkOMBをテストした。

• 性能: kOMBは、Grow and Shrink (GS) アルゴリズムおよび他の既存手法（IAMB, HITON等）を一貫して上回った。
• 高次回復: 3変数XORの拡張であるパリティ関数の場合、標準的な手法はMBを回収できなかった。しかし、$k=2$ を用いたkOMBは完全な回復（F1スコア 1.0）を達成し、3つの条件付け変数が必要な依存関係を検出できる能力を確認した。
• サンプルサイズへの感度: 低サンプル領域において、より高い $k$ 値を持つkOMBは、より低い次数の手法と比較して、経験的忠実性の違反に対して優れた堅牢性を示した。

ベンチマークデータセット

4つの標準的なデータセット（Alarm1, Barley, Insurance, Mildew）で実験を行った。

• 性能: kOMBは、BAMB, HITON, MMMBといった最先端の手法と比較して、概して競争力のある、あるいは優れたF1スコアを達成した。
• 次数の感度: $k$ 値による恩恵はデータセットに依存していた。低カーディナリティのネットワーク（Alarm1, Insurance）では、$k=2$ が性能を向上させた。高カーディナリティのネットワーク（Barley, Mildew）では、与えられたサンプル数（5000サンプル）において、大きな条件付け集合がCIテストの検出力を低下させるため、$k=1$ の方が良好な結果を示すことが多かった。
• 実行時間: 予想通り、実行時間は $k$ およびネットワークのカーディナリティとともに大幅に増加した。高カーディナリティのネットワークでは、$k=2$ の構成は $k=1$ やベースラインの手法よりも大幅に遅くなった。

意義と主張

本論文は、高次の依存関係を利用することが、忠実性の違反が存在する状況でのMB発見を改善できることを示す**概念実証（proof-of-concept）**としてkOMBを位置づけている。

• 控えめな主張: 著者らは、kOMBが効率化のために最適化されているのではなく、その主な目的は $k$ 次オーダーの忠実性の理論的有用性を検証することであると明記している。
• 実用的な示唆: パリティのような関係が含まれる問題や、サンプルサイズが限られている問題において、忠実性の仮定をより高い次数へと緩和することが有益であることを結果は示唆している。
• 今後の方向性: 最悪ケースの計算コストを削減するための近似アルゴリズム、専門知識なしに $k$ と $l$ を選択するための原理的な手法、および実験で使用されたGテストやSCIテストを超えた、より新しい条件付き独立性テストの統合の必要性を指摘している。

本研究は、伝統的な忠実性仮定は多くの場合十分であるが、特定の構造的関係（パリティなど）や有限サンプルの現実には、より柔軟で高次のアプローチが必要であることを確立している。