Reinforcement Causal Structure Learning on Order Graph
원문 초록
Learning directed acyclic graph (DAG) that describes the causality of observed data is a very challenging but important task. Due to the limited quantity and quality of observed data, and non-identifiability of causal graph, it is almost impossible to infer a single precise DAG. Some methods approximate the posterior distribution of DAGs to explore the DAG space via Markov chain Monte Carlo (MCMC), but the DAG space is over the nature of super-exponential growth, accurately characterizing the whole distribution over DAGs is very intractable. In this paper, we propose {Reinforcement Causal Structure Learning on Order Graph} (RCL-OG) that uses order graph instead of MCMC to model different DAG topological orderings and to reduce the problem size. RCL-OG first defines reinforcement learning with a new reward mechanism to approximate the posterior distribution of orderings in an efficacy way, and uses deep Q-learning to update and transfer rewards between nodes. Next, it obtains the probability transition model of nodes on order graph, and computes the posterior probability of different orderings. In this way, we can sample on this model to obtain the ordering with high probability. Experiments on synthetic and benchmark datasets show that RCL-OG provides accurate posterior probability approximation and achieves better results than competitive causal discovery algorithms.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
잠재 변수를 가진 인과 구조의 관측적 부분 순서
The observational partial order of causal structures with latent variables
동일한 가시 변수(visible variable) 집합을 갖는 두 인과 구조에 대해, 첫 번째 구조로 실현 가능한 가시 변수 상의 분포 집합이 두 번째 구조로 실현 가능한 가시 변수 상의 분포 집합을 포함하면, 첫 번째 구조가 두 번째 구조를 관측적으로 지배(observationally dominate)한다고 한다. 이러한 지배 관계를 알면 관측 데이터가 주어졌을 때 이들 구조 중 어느 것이 적합한지 판별하는 데 유용하다. 본 연구에서는 잠재 변수(latent variable)를 가진 인과 구조의 동치류(equivalence class)들이 관측적 지배 관계에 대해 이루는 부분 순서를 결정하는 문제를 다룬다. 가시 변수가 세 개인 경우에는 지배 순서를 완전하게 규명하였고, 가시 변수가 네 개인 경우에는 부분적으로 규명하였다. 또한 우리의 기법은 어떤 관측적 동치류가 벨 부등식(Bell inequalities) 및 도구 부등식(instrumental inequalities)과 유사한 비자명한(nontrivial) 부등식 제약으로 실현 가능한 분포 집합이 특징지어지는지를 식별하는 데에도 도움이 된다. 가시 변수의 수가 늘어날수록 비자명한 부등식 제약을 만족하는 동치류가 어디에나 존재하게 된다는 증거를 발견하였다. (이러한 동치류는 양자적으로 실현 가능한 분포와 고전적으로 실현 가능한 분포 사이에 차이가 있을 수 있는 경우이므로, 이는 양자-고전 간극(quantum-classical gap)이 존재할 가능성 또한 어디에나 있음을 시사한다.) 나아가, 조건부 독립 제약에만 의존하는 제약 기반 인과 발견(causal discovery) 알고리즘은, 이를 넘어서는 알고리즘(즉, 중첩 마르코프(nested Markov) 제약과 부등식 제약도 함께 활용하는 알고리즘)에 비해 관측적 동치류를 구별하는 능력이 상당히 약하다는 증거도 발견하였다.
Personalized Exercise Recommendation with Semantically-Grounded Knowledge Tracing
ADDQ: Adaptive Distributional Double Q-Learning
Paths to Causality: Finding Informative Subgraphs Within Knowledge Graphs for Knowledge-Based Causal Discovery
Permutation-Free High-Order Interaction Tests
TimeGraph: Synthetic Benchmark Datasets for Robust Time-Series Causal Discovery
토론
이 논문과 연결된 포럼 글이 아직 없습니다.