Graph-based Complexity for Causal Effect by Empirical Plug-in

• URL: http://arxiv.org/abs/2411.10008v1
• Date: Fri, 15 Nov 2024 07:42:01 GMT
• Title: Graph-based Complexity for Causal Effect by Empirical Plug-in
• Authors: Rina Dechter, Annie Raichev, Alexander Ihler, Jin Tian,
• Abstract summary: This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. We show that computation can be done efficiently, potentially in time linear in the data size, depending on the estimand's hypergraph.
• Score: 56.14597641617531
• License:
• Abstract: This paper focuses on the computational complexity of computing empirical plug-in estimates for causal effect queries. Given a causal graph and observational data, any identifiable causal query can be estimated from an expression over the observed variables, called the estimand. The estimand can then be evaluated by plugging in probabilities computed empirically from data. In contrast to conventional wisdom, which assumes that high dimensional probabilistic functions will lead to exponential evaluation time of the estimand. We show that computation can be done efficiently, potentially in time linear in the data size, depending on the estimand's hypergraph. In particular, we show that both the treewidth and hypertree width of the estimand's structure bound the evaluation complexity of the plug-in estimands, analogous to their role in the complexity of probabilistic inference in graphical models. Often, the hypertree width provides a more effective bound, since the empirical distributions are sparse.

Related papers

• Estimating Causal Effects from Learned Causal Networks [56.14597641617531]
  We propose an alternative paradigm for answering causal-effect queries over discrete observable variables. We learn the causal Bayesian network and its confounding latent variables directly from the observational data. We show that this emphmodel completion learning approach can be more effective than estimand approaches.
  arXiv  Detail & Related papers  (2024-08-26T08:39:09Z)
• Learning Likelihood Ratios with Neural Network Classifiers [0.12277343096128711]
  approximations of the likelihood ratio may be computed using clever parametrizations of neural network-based classifiers. We present a series of empirical studies detailing the performance of several common loss functionals and parametrizations of the classifier output.
  arXiv  Detail & Related papers  (2023-05-17T18:11:38Z)
• Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels [3.59986669039879]
  Many real-world data sets can be presented in the form of a matrix whose entries correspond to the interaction between two entities of different natures. We assume in this paper that the mentioned interaction is determined by unobservable latent variables describing each entity. Our objective is to estimate the conditional expectation of the data matrix given the unobservable variables.
  arXiv  Detail & Related papers  (2023-04-07T11:21:52Z)
• Statistical Efficiency of Score Matching: The View from Isoperimetry [96.65637602827942]
  We show a tight connection between statistical efficiency of score matching and the isoperimetric properties of the distribution being estimated. We formalize these results both in the sample regime and in the finite regime.
  arXiv  Detail & Related papers  (2022-10-03T06:09:01Z)
• TACTiS: Transformer-Attentional Copulas for Time Series [76.71406465526454]
  estimation of time-varying quantities is a fundamental component of decision making in fields such as healthcare and finance. We propose a versatile method that estimates joint distributions using an attention-based decoder. We show that our model produces state-of-the-art predictions on several real-world datasets.
  arXiv  Detail & Related papers  (2022-02-07T21:37:29Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.