Causal Layering via Conditional Entropy

• URL: http://arxiv.org/abs/2401.10495v1
• Date: Fri, 19 Jan 2024 05:18:28 GMT
• Title: Causal Layering via Conditional Entropy
• Authors: Itai Feigenbaum, Devansh Arpit, Huan Wang, Shelby Heinecke, Juan Carlos Niebles, Weiran Yao, Caiming Xiong, and Silvio Savarese
• Abstract summary: Causal discovery aims to recover information about an unobserved causal graph from the observable data it generates. We provide ways to recover layerings of a graph by accessing the data via a conditional entropy oracle.
• Score: 85.01590667411956
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Causal discovery aims to recover information about an unobserved causal graph from the observable data it generates. Layerings are orderings of the variables which place causes before effects. In this paper, we provide ways to recover layerings of a graph by accessing the data via a conditional entropy oracle, when distributions are discrete. Our algorithms work by repeatedly removing sources or sinks from the graph. Under appropriate assumptions and conditioning, we can separate the sources or sinks from the remainder of the nodes by comparing their conditional entropy to the unconditional entropy of their noise. Our algorithms are provably correct and run in worst-case quadratic time. The main assumptions are faithfulness and injective noise, and either known noise entropies or weakly monotonically increasing noise entropies along directed paths. In addition, we require one of either a very mild extension of faithfulness, or strictly monotonically increasing noise entropies, or expanding noise injectivity to include an additional single argument in the structural functions.

Related papers

• Lower bounds on bipartite entanglement in noisy graph states [8.59730790789283]
  We consider a noise model where the initial qubits undergo depolarizing noise before the application of the CZ operations. We find a family of graph states that maintain a strictly positive coherent information for any amount of (non-maximal) depolarizing noise.
  arXiv  Detail & Related papers  (2024-04-13T14:01:45Z)
• Root Cause Explanation of Outliers under Noisy Mechanisms [50.59446568076628]
  Causal processes are often modelled as graphs with entities being nodes and their paths/interconnections as edge. Existing work only consider the contribution of nodes in the generative process. We consider both individual edge and node of each mechanism when identifying the root causes.
  arXiv  Detail & Related papers  (2023-12-19T03:24:26Z)
• Local Graph-homomorphic Processing for Privatized Distributed Systems [57.14673504239551]
  We show that the added noise does not affect the performance of the learned model. This is a significant improvement to previous works on differential privacy for distributed algorithms.
  arXiv  Detail & Related papers  (2022-10-26T10:00:14Z)
• Diffusion Models for Causal Discovery via Topological Ordering [20.875222263955045]
  emphTopological ordering approaches reduce the optimisation space of causal discovery by searching over a permutation rather than graph space. For ANMs, the emphHessian of the data log-likelihood can be used for finding leaf nodes in a causal graph, allowing its topological ordering. We introduce theory for updating the learned Hessian without re-training the neural network, and we show that computing with a subset of samples gives an accurate approximation of the ordering.
  arXiv  Detail & Related papers  (2022-10-12T13:36:29Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  We show that deviating from this assumption can actually lead to better statistical estimators. In particular, the optimal noise distribution is different from the data's and even from a different family.
  arXiv  Detail & Related papers  (2022-03-02T13:59:20Z)
• Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation [50.85788484752612]
  Noise-contrastive estimation (NCE) is a statistically consistent method for learning unnormalized probabilistic models. It has been empirically observed that the choice of the noise distribution is crucial for NCE's performance. In this work, we formally pinpoint reasons for NCE's poor performance when an inappropriate noise distribution is used.
  arXiv  Detail & Related papers  (2021-10-21T16:57:45Z)
• On the Role of Entropy-based Loss for Learning Causal Structures with Continuous Optimization [27.613220411996025]
  A method with non-combinatorial directed acyclic constraint, called NOTEARS, formulates the causal structure learning problem as a continuous optimization problem using least-square loss. We show that the violation of the Gaussian noise assumption will hinder the causal direction identification. We propose a more general entropy-based loss that is theoretically consistent with the likelihood score under any noise distribution.
  arXiv  Detail & Related papers  (2021-06-05T08:29:51Z)
• Learning Node Representations from Noisy Graph Structures [38.32421350245066]
  Noises prevail in real-world networks, which compromise networks to a large extent. We propose a novel framework to learn noise-free node representations and eliminate noises simultaneously.
  arXiv  Detail & Related papers  (2020-12-04T07:18:39Z)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)

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.