論文の概要: Subset verification and search algorithms for causal DAGs
- arxiv url: http://arxiv.org/abs/2301.03180v3
- Date: Tue, 13 Feb 2024 05:11:17 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 20:19:38.087543
- Title: Subset verification and search algorithms for causal DAGs
- Title（参考訳）: 因果DAGのサブセット検証と探索アルゴリズム
- Authors: Davin Choo, Kirankumar Shiragur
- Abstract要約: エッジのサブセット(ターゲットエッジ)間の因果関係を学習するために必要な最小の介入セットを特定する問題について検討する。
介入因果グラフのいくつかの興味深い構造的特性を証明し、ここで研究されるサブセット検証・探索問題以外の応用があると信じている。
- 参考スコア（独自算出の注目度）: 13.108039226223793
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning causal relationships between variables is a fundamental task in
causal inference and directed acyclic graphs (DAGs) are a popular choice to
represent the causal relationships. As one can recover a causal graph only up
to its Markov equivalence class from observations, interventions are often used
for the recovery task. Interventions are costly in general and it is important
to design algorithms that minimize the number of interventions performed. In
this work, we study the problem of identifying the smallest set of
interventions required to learn the causal relationships between a subset of
edges (target edges). Under the assumptions of faithfulness, causal
sufficiency, and ideal interventions, we study this problem in two settings:
when the underlying ground truth causal graph is known (subset verification)
and when it is unknown (subset search). For the subset verification problem, we
provide an efficient algorithm to compute a minimum sized interventional set;
we further extend these results to bounded size non-atomic interventions and
node-dependent interventional costs. For the subset search problem, in the
worst case, we show that no algorithm (even with adaptivity or randomization)
can achieve an approximation ratio that is asymptotically better than the
vertex cover of the target edges when compared with the subset verification
number. This result is surprising as there exists a logarithmic approximation
algorithm for the search problem when we wish to recover the whole causal
graph. To obtain our results, we prove several interesting structural
properties of interventional causal graphs that we believe have applications
beyond the subset verification/search problems studied here.
- Abstract（参考訳）: 変数間の因果関係の学習は因果関係の基本的な課題であり、有向非巡回グラフ(DAG)は因果関係を表現するための一般的な選択である。
因果グラフを観測結果からマルコフ同値クラスまでしか回収できないため、リカバリ作業にしばしば介入が用いられる。
介入は一般的にコストがかかり、実行される介入の数を最小化するアルゴリズムを設計することが重要である。
本研究では,エッジのサブセット(ターゲットエッジ)間の因果関係を学ぶのに必要な介入の最小セットを特定する問題について検討する。
忠実性,因果便益性,理想的な介入という仮定の下で,基礎となる真理因果グラフが既知の場合(サブセット検証)と未知の場合(サブセット探索)という2つの設定でこの問題を研究する。
サブセット検証問題に対して、最小サイズの介入集合を計算するための効率的なアルゴリズムを提供し、これらの結果をさらに、境界サイズの非原子的介入とノード依存の介入コストに拡張する。
部分集合探索問題の場合、最悪の場合、(適応性やランダム化を伴う)アルゴリズムが、部分集合検証数と比較して対象辺の頂点被覆よりも漸近的に良い近似比を達成することができないことを示す。
因果グラフ全体を復元したい場合には,探索問題に対する対数近似アルゴリズムが存在するので,この結果は意外である。
以上の結果を得るため,本研究で研究されている部分的検証・探索問題以上の応用が期待できる介入因果グラフの興味深い構造的性質を示す。
関連論文リスト
- Sample Efficient Bayesian Learning of Causal Graphs from Interventions [6.823521786512908]
本研究では,限られた介入サンプルを用いた因果グラフ学習におけるベイズ的アプローチについて考察する。
我々は,提案アルゴリズムが真の因果グラフを高い確率で返すことを理論的に示す。
本稿では,このアルゴリズムを,グラフ全体を学習することなく,より一般的な因果問題にどう対応できるかを示すケーススタディを提案する。
論文 参考訳（メタデータ） (2024-10-26T05:47:56Z) - Adaptive Online Experimental Design for Causal Discovery [9.447864414136905]
因果発見は因果グラフに符号化された因果関係を明らかにすることを目的としている。
オンライン学習の観点から,データの介入効率に着目し,因果発見を形式化する。
グラフ分離システムから介入を適応的に選択するトラック・アンド・ストップ因果探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-19T13:26:33Z) - Causal Discovery under Off-Target Interventions [18.92683981229985]
因果グラフ発見は様々な分野の応用において重要な問題である。
本研究は,介入数の最小化を目標とした介入設定の下での因果発見問題に対処する。
論文 参考訳（メタデータ） (2024-02-13T05:43:49Z) - Meek Separators and Their Applications in Targeted Causal Discovery [17.84347390320128]
我々は、サブセット検索と因果マッチングの2つの問題に焦点をあてる。
小型のMeekセパレータを効率よく見つけるアルゴリズムを提案する。
以上の結果から,両問題に対する既知の平均ケース保証が得られた。
論文 参考訳（メタデータ） (2023-10-30T23:15:27Z) - Predictive Coding beyond Correlations [59.47245250412873]
このようなアルゴリズムのうちの1つは、予測符号化と呼ばれ、因果推論タスクを実行することができるかを示す。
まず、予測符号化の推論過程における簡単な変化が、因果グラフを再利用したり再定義したりすることなく、介入を計算できることを示す。
論文 参考訳（メタデータ） (2023-06-27T13:57:16Z) - Nonparametric Identifiability of Causal Representations from Unknown
Interventions [63.1354734978244]
本研究では, 因果表現学習, 潜伏因果変数を推定するタスク, およびそれらの変数の混合から因果関係を考察する。
我々のゴールは、根底にある真理潜入者とその因果グラフの両方を、介入データから解決不可能なあいまいさの集合まで識別することである。
論文 参考訳（メタデータ） (2023-06-01T10:51:58Z) - New metrics and search algorithms for weighted causal DAGs [7.424262881242935]
ノード依存コストの適応的介入による因果グラフ発見について検討する。
検索アルゴリズムの最悪の介入コストをキャプチャする新しいベンチマークを定義する。
本研究では,様々な条件下で対数近似を実現する適応探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-05-08T03:48:37Z) - Learning to Bound Counterfactual Inference in Structural Causal Models
from Observational and Randomised Data [64.96984404868411]
我々は、従来のEMベースのアルゴリズムを拡張するための全体的なデータの特徴付けを導出する。
新しいアルゴリズムは、そのような混合データソースからモデルパラメータの(不特定性)領域を近似することを学ぶ。
反実的な結果に間隔近似を与え、それが特定可能な場合の点に崩壊する。
論文 参考訳（メタデータ） (2022-12-06T12:42:11Z) - Active Bayesian Causal Inference [72.70593653185078]
因果発見と推論を統合するための完全ベイズ能動学習フレームワークであるアクティブベイズ因果推論(ABCI)を提案する。
ABCIは因果関係のモデルと関心のクエリを共同で推論する。
我々のアプローチは、完全な因果グラフの学習のみに焦点を当てた、いくつかのベースラインよりも、よりデータ効率が高いことを示す。
論文 参考訳（メタデータ） (2022-06-04T22:38:57Z) - Scalable Intervention Target Estimation in Linear Models [52.60799340056917]
因果構造学習への現在のアプローチは、既知の介入目標を扱うか、仮説テストを使用して未知の介入目標を発見する。
本稿では、全ての介入対象を一貫して識別するスケーラブルで効率的なアルゴリズムを提案する。
提案アルゴリズムは、与えられた観測マルコフ同値クラスを介入マルコフ同値クラスに更新することも可能である。
論文 参考訳（メタデータ） (2021-11-15T03:16:56Z) - Learning Neural Causal Models with Active Interventions [83.44636110899742]
本稿では,データ生成プロセスの根底にある因果構造を素早く識別する能動的介入ターゲット機構を提案する。
本手法は,ランダムな介入ターゲティングと比較して,要求される対話回数を大幅に削減する。
シミュレーションデータから実世界のデータまで,複数のベンチマークにおいて優れた性能を示す。
論文 参考訳（メタデータ） (2021-09-06T13:10:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。