論文の概要: Active Structure Learning of Causal DAGs via Directed Clique Tree
- arxiv url: http://arxiv.org/abs/2011.00641v1
- Date: Sun, 1 Nov 2020 23:11:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-30 23:13:02.924285
- Title: Active Structure Learning of Causal DAGs via Directed Clique Tree
- Title（参考訳）: 直交斜め木を用いた因果DAGのアクティブ構造学習
- Authors: Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz,
Murat Kocaoglu, Karthikeyan Shanmugam
- Abstract要約: 我々は,最大傾きが構造学習の根本的障害であることを示す,単一ノード介入に対する普遍的下位境界を開発する。
具体的には,DAGを直交斜め木を通して独立に向き付け可能な成分に分解する。
また,最大傾き数における乗算対数係数までの最適介入数に一致する2相干渉設計アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 28.637447727749
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A growing body of work has begun to study intervention design for efficient
structure learning of causal directed acyclic graphs (DAGs). A typical setting
is a causally sufficient setting, i.e. a system with no latent confounders,
selection bias, or feedback, when the essential graph of the observational
equivalence class (EC) is given as an input and interventions are assumed to be
noiseless. Most existing works focus on worst-case or average-case lower bounds
for the number of interventions required to orient a DAG. These worst-case
lower bounds only establish that the largest clique in the essential graph
could make it difficult to learn the true DAG. In this work, we develop a
universal lower bound for single-node interventions that establishes that the
largest clique is always a fundamental impediment to structure learning.
Specifically, we present a decomposition of a DAG into independently orientable
components through directed clique trees and use it to prove that the number of
single-node interventions necessary to orient any DAG in an EC is at least the
sum of half the size of the largest cliques in each chain component of the
essential graph. Moreover, we present a two-phase intervention design algorithm
that, under certain conditions on the chordal skeleton, matches the optimal
number of interventions up to a multiplicative logarithmic factor in the number
of maximal cliques. We show via synthetic experiments that our algorithm can
scale to much larger graphs than most of the related work and achieves better
worst-case performance than other scalable approaches. A code base to recreate
these results can be found at https://github.com/csquires/dct-policy
- Abstract（参考訳）: 因果有向非巡回グラフ(DAG)の効率的な構造学習のための介入設計について研究が進められている。
典型的な設定は因果的に十分な設定であり、すなわち、観測同値クラス(ec)の本質グラフが入力として与えられ、介入が無ノイズであると仮定された場合、潜在共起者、選択バイアス、フィードバックのないシステムである。
既存の作業の多くは、DAGを指向するために必要な介入の数に対して、最悪のケースや平均ケースの低いバウンダリに重点を置いています。
これらの最悪の下界は、本質グラフの最大の傾きが真のDAGを学ぶのを困難にしていることを証明しているだけである。
本研究では,最大クランクが常に構造学習の基本的な障害であることを示す,単一ノード介入のための普遍的な下限を開発する。
具体的には、DAGを向き付けられた斜め木を通して独立に向き付け可能な成分に分解し、それを用いて、EC内の任意のDAGを向き付けるのに必要な単一ノード介入の数が、本命グラフの各チェーン成分の最大傾きの少なくとも半分であることを示す。
さらに, 弦骨格上の特定の条件下では, 最大クランク数における乗法対数係数まで, 最適な介入数に一致する二相干渉設計アルゴリズムを提案する。
合成実験により、我々のアルゴリズムは関連するほとんどの作業よりもはるかに大きなグラフにスケールでき、他の拡張性のあるアプローチよりも最悪のパフォーマンスが得られることを示す。
これらの結果を再現するコードベースはhttps://github.com/csquires/dct-policyにある。
関連論文リスト
- A Full DAG Score-Based Algorithm for Learning Causal Bayesian Networks with Latent Confounders [0.0]
因果ベイズネットワーク(Causal Bayesian Network, CBN)は、変数間の因果関係を符号化する一般的なグラフィカル確率モデルである。
本稿では,DAGの空間を探索し,潜在する共同設立者の存在を識別できる,初めての完全スコアに基づく構造学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-20T20:25:56Z) - Amplify Graph Learning for Recommendation via Sparsity Completion [16.32861024767423]
グラフ学習モデルは、協調フィルタリング(CF)ベースのレコメンデーションシステムに広くデプロイされている。
データ疎度の問題により、元の入力のグラフ構造は潜在的な肯定的な嗜好エッジを欠いている。
AGL-SC(Amplify Graph Learning framework)を提案する。
論文 参考訳（メタデータ） (2024-06-27T08:26:20Z) - Interventional Causal Discovery in a Mixture of DAGs [34.82590796630406]
本稿では,複数の因果系が支配する変数間の因果相互作用の学習における介入の役割について述べる。
これは、真のエッジと呼ばれる混合物の少なくとも1つの成分DAGに存在するエッジを特定することを目的としている。
論文 参考訳（メタデータ） (2024-06-12T22:12:03Z) - Causality is all you need [63.10680366545293]
因果グラフルーティング(Causal Graph Routing, CGR)は、データに隠された原因影響力を明らかにするための介入機構を完全に依存した統合因果スキームである。
CGRは、Visual Question AnswerとLong Document Classificationタスクの両方において、最先端のメソッドを超越することができる。
論文 参考訳（メタデータ） (2023-11-21T02:53:40Z) - Discovering Dynamic Causal Space for DAG Structure Learning [64.763763417533]
本稿では,DAG構造学習のための動的因果空間であるCASPERを提案する。
グラフ構造をスコア関数に統合し、因果空間における新しい尺度として、推定真理DAGと基底真理DAGの因果距離を忠実に反映する。
論文 参考訳（メタデータ） (2023-06-05T12:20:40Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - Localized Contrastive Learning on Graphs [110.54606263711385]
局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。
その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
論文 参考訳（メタデータ） (2022-12-08T23:36:00Z) - GFlowCausal: Generative Flow Networks for Causal Discovery [27.51595081346858]
本稿では,GFlowCausalと呼ばれる観測データからDAG(Directed Acyclic Graph)を学習するための新しい手法を提案する。
GFlowCausalは、事前定義された報酬に比例した確率を持つシーケンシャルアクションによって、ハイリワードDAGを生成するための最良のポリシーを学ぶことを目的としている。
合成データセットと実データセットの両方について広範な実験を行い、提案手法が優れていることを示すとともに、大規模環境での良好な性能を示す。
論文 参考訳（メタデータ） (2022-10-15T04:07:39Z) - Explainable Sparse Knowledge Graph Completion via High-order Graph
Reasoning Network [111.67744771462873]
本稿では,スパース知識グラフ(KG)のための新しい説明可能なモデルを提案する。
高次推論をグラフ畳み込みネットワーク、すなわちHoGRNに結合する。
情報不足を緩和する一般化能力を向上させるだけでなく、解釈可能性も向上する。
論文 参考訳（メタデータ） (2022-07-14T10:16:56Z) - Effect Identification in Cluster Causal Diagrams [51.42809552422494]
クラスタ因果図(略してC-DAG)と呼ばれる新しいタイプのグラフィカルモデルを導入する。
C-DAGは、限定された事前知識に基づいて変数間の関係を部分的に定義することができる。
我々はC-DAGに対する因果推論のための基礎と機械を開発する。
論文 参考訳（メタデータ） (2022-02-22T21:27:31Z) - Almost Optimal Universal Lower Bound for Learning Causal DAGs with
Atomic Interventions [2.750124853532831]
我々は、与えられたMECを指向するためにアルゴリズムが実行するべき原子介入の数に対して、新しい普遍的な下限を証明した。
我々の下限は、以前知られていた下限よりも確実に良い。
論文 参考訳（メタデータ） (2021-11-09T11:58:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。