論文の概要: Membership Testing in Markov Equivalence Classes via Independence Query Oracles

• arxiv url: http://arxiv.org/abs/2403.05759v1
• Date: Sat, 9 Mar 2024 02:10:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-13 12:30:54.974000
• Title: Membership Testing in Markov Equivalence Classes via Independence Query Oracles
• Title（参考訳）: 独立クエリオラクルによるマルコフ同値クラスのメンバシップテスト
• Authors: Jiaqi Zhang, Kirankumar Shiragur, Caroline Uhler
• Abstract要約: 因果関係を学習するよりも、因果関係をテストする方が比較的容易であることを示す。 特に、高いin-degreeと小さなcliqueサイズを特徴とするグラフにおいて、指数関数的に低い独立性テストが必要である。
• 参考スコア（独自算出の注目度）: 17.84347390320128
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding causal relationships between variables is a fundamental problem with broad impact in numerous scientific fields. While extensive research has been dedicated to learning causal graphs from data, its complementary concept of testing causal relationships has remained largely unexplored. While learning involves the task of recovering the Markov equivalence class (MEC) of the underlying causal graph from observational data, the testing counterpart addresses the following critical question: Given a specific MEC and observational data from some causal graph, can we determine if the data-generating causal graph belongs to the given MEC? We explore constraint-based testing methods by establishing bounds on the required number of conditional independence tests. Our bounds are in terms of the size of the maximum undirected clique ($s$) of the given MEC. In the worst case, we show a lower bound of $\exp(\Omega(s))$ independence tests. We then give an algorithm that resolves the task with $\exp(O(s))$ tests, matching our lower bound. Compared to the learning problem, where algorithms often use a number of independence tests that is exponential in the maximum in-degree, this shows that testing is relatively easier. In particular, it requires exponentially less independence tests in graphs featuring high in-degrees and small clique sizes. Additionally, using the DAG associahedron, we provide a geometric interpretation of testing versus learning and discuss how our testing result can aid learning.
• Abstract（参考訳）: 変数間の因果関係を理解することは、多くの科学分野で幅広い影響を持つ根本的な問題である。 データから因果グラフを学ぶために広範な研究が行われてきたが、因果関係をテストするという補完的な概念はほとんど未調査のままである。 学習は、基礎となる因果グラフのマルコフ同値クラス(MEC)を観測データから回収する作業を伴うが、テスト対象は以下の重要な問題に対処する: ある因果グラフから特定の MEC と観測データを与えられた場合、データ生成因果グラフが与えられた MEC に属するかどうかを判断できる。 条件付き独立テストの必要回数に制限を課すことにより,制約に基づくテスト手法を検討する。 私たちの境界は、与えられたMECの最大無向傾き($s$)の大きさである。 最悪の場合、$\exp(\Omega(s))$独立テストの低い境界を示す。 次に、そのタスクを$\exp(O(s))$テストで解決し、下位境界にマッチするアルゴリズムを与えます。 アルゴリズムが最大で指数関数的に多数の独立性テストを使用する場合の学習問題と比較すると、テストは比較的容易であることを示している。 特に、高いin-degreeと小さなcliqueサイズのグラフで指数関数的に低い独立性テストを必要とする。 さらに,dag associahedronを用いて,テストと学習の幾何学的解釈を行い,テスト結果が学習にどのように役立つかについて議論する。

関連論文リスト

• Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies [49.99600569996907]
  観測データに対して仮説化された因果モデルをテストすることは、多くの因果推論タスクにとって重要な前提条件である。 モデルは指数関数的に多くの条件付き独立関係(CI)を仮定できるが、これら全てをテストすることは実用的でなく不必要である。 隠れ変数を持つ因果グラフのc-LMPを導入し、これらのCIを多時間間隔でリストする遅延アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-09-22T21:05:56Z)
• Scalable and Flexible Causal Discovery with an Efficient Test for Adjacency [48.769884734826974]
  因果グラフに2つの変数が隣接しているかどうかを評価するために,スケーラブルで柔軟な手法を構築した。 微分可能隣接テストは指数関数的な数のテストを、証明可能な等価な緩和問題に置き換える。 DAT, DAT-Graphに基づくグラフ学習手法も構築し, 介入したデータから学習する。
  論文  参考訳（メタデータ） (2024-06-13T14:39:40Z)
• Causal Discovery with Fewer Conditional Independence Tests [15.876392307650248]
  我々の研究は、条件付き独立テストの数を減らすことで、基礎となる因果グラフについて何が学べるかを特徴づけることに重点を置いている。 隠れ因果グラフの粗い表現を多数のテストで学習できることを示す。 その結果,本研究では,多数のテストで真の因果グラフを復元するアルゴリズムを初めて提案した。
  論文  参考訳（メタデータ） (2024-06-03T22:27:09Z)
• Collaborative non-parametric two-sample testing [55.98760097296213]
  目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。 グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。 提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
  論文  参考訳（メタデータ） (2024-02-08T14:43:56Z)
• Characterization and Learning of Causal Graphs with Small Conditioning Sets [6.52423450125622]
  制約に基づく因果探索アルゴリズムは、条件付き独立性を体系的にテストすることで因果グラフ構造の一部を学習する。 2つの因果グラフ間の$k$-Markov同値をグラフィカルに特徴付ける新しい表現を提案する。 合成および半合成実験を行い、$k$-PCアルゴリズムがより堅牢な因果発見を可能にすることを示す。
  論文  参考訳（メタデータ） (2023-01-22T00:24:22Z)
• Sequential Kernelized Independence Testing [101.22966794822084]
  我々は、カーネル化依存度にインスパイアされたシーケンシャルなカーネル化独立試験を設計する。 シミュレーションデータと実データの両方にアプローチのパワーを実証する。
  論文  参考訳（メタデータ） (2022-12-14T18:08:42Z)
• Multiple imputation and test-wise deletion for causal discovery with incomplete cohort data [0.0]
  因果探索アルゴリズムは観測データから因果グラフを推定する。 最近まで、これらのアルゴリズムは欠落した値を扱うことができなかった。 テストワイド削除と多重計算の2つの方法について検討する。
  論文  参考訳（メタデータ） (2021-08-30T15:51:30Z)
• Improving Efficiency and Accuracy of Causal Discovery Using a Hierarchical Wrapper [7.570246812206772]
  観測データからの因果発見は、科学の多くの分野において重要なツールである。 大規模なサンプルリミットでは、音と完全な因果探索アルゴリズムが導入されている。 しかし、これらのアルゴリズムが使用する統計的テストのパワーを制限するのは、有限のトレーニングデータのみである。
  論文  参考訳（メタデータ） (2021-07-11T09:24:49Z)
• Testing Directed Acyclic Graph via Structural, Supervised and Generative Adversarial Learning [7.623002328386318]
  有向非巡回グラフ(DAG)の新しい仮説テスト法を提案する。 非常に柔軟なニューラルネットワーク学習者に基づいてテストを構築します。 シミュレーションと脳接続ネットワーク解析による実験の有効性を実証する。
  論文  参考訳（メタデータ） (2021-06-02T21:18:59Z)
• Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
  我々は、軽度の仮定の下で、識別性と学習可能性に関する保証を提供する。 我々は,線形制約付き結合テンソル分解に基づく効率的なアルゴリズムを開発し,スケーラブルで保証可能な解を得る。
  論文  参考訳（メタデータ） (2021-01-17T07:48:45Z)
• Comprehensible Counterfactual Explanation on Kolmogorov-Smirnov Test [56.5373227424117]
  我々は,KSテストに失敗するテストデータに対して,反実的説明を生成する問題に対処する。 我々は、KSテストに失敗したテストセットの指数的なサブセット数を列挙し、チェックするのを避ける効率的なアルゴリズムMOCHEを開発した。
  論文  参考訳（メタデータ） (2020-11-01T06:46:01Z)

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

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