論文の概要: On the Number of Conditional Independence Tests in Constraint-based Causal Discovery

• arxiv url: http://arxiv.org/abs/2603.21844v1
• Date: Mon, 23 Mar 2026 11:33:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-24 19:11:39.635922
• Title: On the Number of Conditional Independence Tests in Constraint-based Causal Discovery
• Title（参考訳）: 制約に基づく因果発見における条件付き独立試験の回数について
• Authors: Marc Franquesa Monés, Jiaqi Zhang, Caroline Uhler,
• Abstract要約: より複雑な$pmathcalO(s)$テストを実現するアルゴリズムを提案する。 制約に基づくアルゴリズムは、少なくとも2(s)$条件付き独立性テストを実行しなければならない。
• 参考スコア（独自算出の注目度）: 20.562877135664852
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning causal relations from observational data is a fundamental problem with wide-ranging applications across many fields. Constraint-based methods infer the underlying causal structure by performing conditional independence tests. However, existing algorithms such as the prominent PC algorithm need to perform a large number of independence tests, which in the worst case is exponential in the maximum degree of the causal graph. Despite extensive research, it remains unclear if there exist algorithms with better complexity without additional assumptions. Here, we establish an algorithm that achieves a better complexity of $p^{\mathcal{O}(s)}$ tests, where $p$ is the number of nodes in the graph and $s$ denotes the maximum undirected clique size of the underlying essential graph. Complementing this result, we prove that any constraint-based algorithm must perform at least $2^{Ω(s)}$ conditional independence tests, establishing that our proposed algorithm achieves exponent-optimality up to a logarithmic factor in terms of the number of conditional independence tests needed. Finally, we validate our theoretical findings through simulations, on semi-synthetic gene-expression data, and real-world data, demonstrating the efficiency of our algorithm compared to existing methods in terms of number of conditional independence tests needed.
• Abstract（参考訳）: 観測データから因果関係を学習することは、多くの分野にわたる幅広い応用において根本的な問題である。 制約に基づく手法は条件付き独立試験によって根底にある因果構造を推定する。 しかし、PCアルゴリズムのような既存のアルゴリズムは、多くの独立性テストを実行する必要があり、最悪の場合、因果グラフの最大度で指数関数的である。 広範な研究にもかかわらず、さらなる仮定なしでより複雑なアルゴリズムが存在するかどうかは不明だ。 ここでは、より複雑な$p^{\mathcal{O}(s)}$テストを実現するアルゴリズムを確立し、$p$はグラフ内のノードの数であり、$s$は基礎となる本質グラフの最大無向クリリーサイズを表す。 この結果の補足として,任意の制約ベースのアルゴリズムが条件付き独立テストに対して少なくとも2^{Ω(s)}$条件付き独立テストを行う必要があることを証明し,提案アルゴリズムが条件付き独立テストに必要な条件付き独立テストの数で対数係数まで指数最適性を達成することを証明した。 最後に, シミュレーション, 半合成遺伝子発現データ, 実世界のデータを用いて, 条件付き独立性テストの数の観点から, 既存の手法と比較して, アルゴリズムの効率性を実証した。

関連論文リスト

• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Membership Testing in Markov Equivalence Classes via Independence Query Oracles [17.84347390320128]
  因果関係を学習するよりも、因果関係をテストする方が比較的容易であることを示す。 特に、高いin-degreeと小さなcliqueサイズを特徴とするグラフにおいて、指数関数的に低い独立性テストが必要である。
  論文  参考訳（メタデータ） (2024-03-09T02:10:08Z)
• Precise Error Rates for Computationally Efficient Testing [67.30044609837749]
  本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。 線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
  論文  参考訳（メタデータ） (2023-11-01T04:41:16Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Characterization and Learning of Causal Graphs with Small Conditioning Sets [6.52423450125622]
  制約に基づく因果探索アルゴリズムは、条件付き独立性を体系的にテストすることで因果グラフ構造の一部を学習する。 2つの因果グラフ間の$k$-Markov同値をグラフィカルに特徴付ける新しい表現を提案する。 合成および半合成実験を行い、$k$-PCアルゴリズムがより堅牢な因果発見を可能にすることを示す。
  論文  参考訳（メタデータ） (2023-01-22T00:24:22Z)
• Recursive Causal Structure Learning in the Presence of Latent Variables and Selection Bias [27.06618125828978]
  本稿では,潜伏変数と選択バイアスの存在下での観測データからシステムの因果MAGを学習する問題を考察する。 本稿では,音と完全性を備えた計算効率のよい制約ベースの新しい手法を提案する。 提案手法と人工と実世界の両方の構造に関する技術の現状を比較した実験結果を提供する。
  論文  参考訳（メタデータ） (2021-10-22T19:49:59Z)
• Multiple imputation and test-wise deletion for causal discovery with incomplete cohort data [0.0]
  因果探索アルゴリズムは観測データから因果グラフを推定する。 最近まで、これらのアルゴリズムは欠落した値を扱うことができなかった。 テストワイド削除と多重計算の2つの方法について検討する。
  論文  参考訳（メタデータ） (2021-08-30T15:51:30Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。