論文の概要: A Single Iterative Step for Anytime Causal Discovery
- arxiv url: http://arxiv.org/abs/2012.07513v2
- Date: Thu, 24 Dec 2020 11:29:06 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-08 14:45:04.364741
- Title: A Single Iterative Step for Anytime Causal Discovery
- Title（参考訳）: あらゆる因果発見のための反復的なステップ
- Authors: Raanan Y. Rohekar, Yaniv Gurwicz, Shami Nisimov, Gal Novik
- Abstract要約: 観測された非介入データから因果グラフを回復するための健全で完全なアルゴリズムを提示する。
我々は因果マルコフと忠実性仮定に依存し、基礎となる因果グラフの同値クラスを回復する。
提案アルゴリズムでは,FCIアルゴリズムと比較して,CIテストと条件セットの大幅な削減が要求される。
- 参考スコア（独自算出の注目度）: 7.570246812206772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a sound and complete algorithm for recovering causal graphs from
observed, non-interventional data, in the possible presence of latent
confounders and selection bias. We rely on the causal Markov and faithfulness
assumptions and recover the equivalence class of the underlying causal graph by
performing a series of conditional independence (CI) tests between observed
variables. We propose a single step that is applied iteratively, such that the
independence and causal relations entailed from the resulting graph, after any
iteration, is correct and becomes more informative with successive iteration.
Essentially, we tie the size of the CI condition set to its distance from the
tested nodes on the resulting graph. Each iteration refines the skeleton and
orientation by performing CI tests having condition sets that are larger than
in the preceding iteration. In an iteration, condition sets of CI tests are
constructed from nodes that are within a specified search distance, and the
sizes of these condition sets is equal to this search distance. The algorithm
then iteratively increases the search distance along with the condition set
sizes. Thus, each iteration refines a graph, that was recovered by previous
iterations having smaller condition sets -- having a higher statistical power.
We demonstrate that our algorithm requires significantly fewer CI tests and
smaller condition sets compared to the FCI algorithm. This is evident for both
recovering the true underlying graph using a perfect CI oracle, and accurately
estimating the graph using limited observed data.
- Abstract（参考訳）: そこで本研究では,非干渉データからの因果グラフを潜在共同設立者と選択バイアスが存在する可能性から回収する,健全かつ完全なアルゴリズムを提案する。
我々は因果マルコフと忠実性の仮定に頼り、観測変数間の一連の条件独立(CI)テストを実行することにより、基礎となる因果グラフの同値クラスを復元する。
結果グラフに含まれる独立性と因果関係は,任意の反復の後に正し,反復によってより有益になるように,反復的に適用される1つのステップを提案する。
本質的には、ci条件セットのサイズを、結果グラフ上のテストされたノードからの距離に結びつける。
各イテレーションは、前回のイテレーションよりも大きい条件セットを持つCIテストを実行することで、スケルトンと向きを洗練します。
繰り返し、CIテストの条件セットは特定の探索距離内にあるノードから構築され、これらの条件セットのサイズはこの探索距離と等しい。
このアルゴリズムは、条件セットのサイズとともに探索距離を反復的に増加させる。
したがって、各イテレーションは、より小さな条件セットを持つ以前のイテレーションによって復元されたグラフを洗練します。
提案アルゴリズムでは,FCIアルゴリズムと比較して,CIテストと条件セットの大幅な削減が要求される。
これは、完全なCIオラクルを使用して真の基盤グラフを復元し、限られた観測データを用いてグラフを正確に推定することの両方で明らかである。
関連論文リスト
- Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies [49.99600569996907]
観測データに対して仮説化された因果モデルをテストすることは、多くの因果推論タスクにとって重要な前提条件である。
モデルは指数関数的に多くの条件付き独立関係(CI)を仮定できるが、これら全てをテストすることは実用的でなく不必要である。
隠れ変数を持つ因果グラフのc-LMPを導入し、これらのCIを多時間間隔でリストする遅延アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-09-22T21:05:56Z) - New metrics and search algorithms for weighted causal DAGs [7.424262881242935]
ノード依存コストの適応的介入による因果グラフ発見について検討する。
検索アルゴリズムの最悪の介入コストをキャプチャする新しいベンチマークを定義する。
本研究では,様々な条件下で対数近似を実現する適応探索アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-05-08T03:48:37Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Characterization and Learning of Causal Graphs with Small Conditioning
Sets [6.52423450125622]
制約に基づく因果探索アルゴリズムは、条件付き独立性を体系的にテストすることで因果グラフ構造の一部を学習する。
2つの因果グラフ間の$k$-Markov同値をグラフィカルに特徴付ける新しい表現を提案する。
合成および半合成実験を行い、$k$-PCアルゴリズムがより堅牢な因果発見を可能にすることを示す。
論文 参考訳（メタデータ） (2023-01-22T00:24:22Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳（メタデータ） (2022-01-25T00:10:03Z) - Iterative Causal Discovery in the Possible Presence of Latent
Confounders and Selection Bias [7.570246812206772]
本稿では,潜在的共同設立者と選択バイアスの存在下で因果グラフを復元するための,健全で完全なアルゴリズムを提案する。
ICDは因果マルコフと忠実性の仮定に依存し、基礎となる因果グラフの同値類を復元する。
ICDはCIテストが著しく少なく、FCI、FCI+、RFCIアルゴリズムよりも正確な因果グラフを学習できることを実証的に実証した。
論文 参考訳（メタデータ） (2021-11-07T14:04:46Z) - Information-Theoretic Generalization Bounds for Iterative
Semi-Supervised Learning [81.1071978288003]
特に,情報理論の原理を用いて,反復型SSLアルゴリズムのエミュレータ一般化誤差の振る舞いを理解することを目的とする。
我々の理論的結果は、クラス条件分散があまり大きくない場合、一般化誤差の上限は反復数とともに単調に減少するが、すぐに飽和することを示している。
論文 参考訳（メタデータ） (2021-10-03T05:38:49Z) - Efficient Neural Causal Discovery without Acyclicity Constraints [30.08586535981525]
本研究では,有向非巡回因果グラフの効率的な構造学習法であるENCOを提案する。
実験の結果,ENCOは数百ノードのグラフを効率よく回収できることがわかった。
論文 参考訳（メタデータ） (2021-07-22T07:01:41Z) - Improving Efficiency and Accuracy of Causal Discovery Using a
Hierarchical Wrapper [7.570246812206772]
観測データからの因果発見は、科学の多くの分野において重要なツールである。
大規模なサンプルリミットでは、音と完全な因果探索アルゴリズムが導入されている。
しかし、これらのアルゴリズムが使用する統計的テストのパワーを制限するのは、有限のトレーニングデータのみである。
論文 参考訳（メタデータ） (2021-07-11T09:24:49Z) - Consistency of a Recurrent Language Model With Respect to Incomplete
Decoding [67.54760086239514]
逐次言語モデルから無限長のシーケンスを受信する問題について検討する。
不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
論文 参考訳（メタデータ） (2020-02-06T19:56:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。