Optimal Experiment Design for Causal Discovery from Fixed Number of Experiments
We study the problem of causal structure learning over a set of random variables when the experimenter is allowed to perform at most $M$ experiments in a non-adaptive manner. We consider the optimal learning strategy in terms of minimizing the portions of the structure that remains unknown given the limited number of experiments in both Bayesian and minimax setting. We characterize the theoretical optimal solution and propose an algorithm, which designs the experiments efficiently in terms of time complexity. We show that for bounded degree graphs, in the minimax case and in the Bayesian case with uniform priors, our proposed algorithm is a $\rho$-approximation algorithm, where $\rho$ is independent of the order of the underlying graph. Simulations on both synthetic and real data show that the performance of our algorithm is very close to the optimal solution.
Code (0)
등록된 구현이 없습니다.
Tasks
Causal DiscoverySimilar Papers 제목 키워드 기반
Can Large Language Models Help Experimental Design for Causal Discovery?
Designing proper experiments and selecting optimal intervention targets is a longstanding problem in scientific or causal discovery. Identifying the underlying causal structure from observational data alone is inherently…
Causal DiscoveryExperimental DesignLarge Language Modelscientific discovery+1Bivariate Causal Discovery for Categorical Data via Classification with Optimal Label Permutation
Causal discovery for quantitative data has been extensively studied but less is known for categorical data. We propose a novel causal model for categorical data based on a new classification model, termed classification …
Causal DiscoveryInterventions, Where and How? Experimental Design for Causal Models at Scale
Causal discovery from observational and interventional data is challenging due to limited data and non-identifiability: factors that introduce uncertainty in estimating the underlying structural causal model (SCM). Selec…
Causal DiscoveryExperimental DesignCausal Discovery and Optimal Experimental Design for Genome-Scale Biological Network Recovery
Causal discovery of genome-scale networks is important for identifying pathways from genes to observable traits - e.g. differences in cell function, disease, drug resistance and others. Causal learners based on graphical…
Causal DiscoveryExperimental DesignScore-based Causal Discovery from Heterogeneous Data
Causal discovery has witnessed significant progress over the past decades. Most algorithms in causal discovery consider a single domain with a fixed distribution. However, it is commonplace to encounter heterogeneous dat…
Causal Discovery