Researchers study learning polytree graphs from linear SEMs with exact recovery conditions.
problem Learning polytree graphs from linear SEMs with exact recovery conditions.
method Study Gaussian polytree models, derive sufficient and necessary conditions for sample sizes, and establish estimation error bounds.
result Sharp characterization of difficulty with matching sufficient and necessary conditions.
Local approach learns causal structure of linear Gaussian polytree models from interventional data.
problem Learning causal structure of linear Gaussian polytree models from interventional data.
method First learns the skeleton and then orients edges of the polytree using second order statistics and low-dimensional marginal distributions.
result Consistent and scalable approach that handles problems with thousands of nodes.
Efficiently learns polytrees with known skeleton in polynomial time and sample complexity.
problem Learning polytrees with known skeleton structure.
method Proposes an efficient algorithm for learning d-polytrees in polynomial time and sample complexity when the skeleton is known. result Establishes finite-sample guarantees for efficient learning of d-polytrees. New algorithms learn polytree structures from data.
problem Learning causal graphs from non-Gaussian data.
method Combines Chow-Liu algorithm with edge orientation schemes.
result Established high-dimensional consistency results.
Optimal algorithms learn Gaussian trees and polytrees from data.
problem Learning undirected Gaussian trees and polytrees from data.
method Two approaches: Chow-Liu algorithm for tree structure and modified PC algorithm for polytree structure.
result Explicit finite-sample guarantees and matching lower bounds for both approaches.
Algorithm recovers large causal tree from small samples.
problem Determining causal structure in large gene networks.
method Algorithm that recovers tree with high accuracy under mild conditions.
result High accuracy in recovering causal tree from small samples.
We present a graphical criterion for reading dependencies from the minimal directed independence map G of a graphoid p when G is a polytree and p satisfies composition and weak transitivity. We prove that the criterion is sound and complete. We argue that assuming composition and weak transitivity is not too restrictiv…
Paper tackles anomaly detection with missing causal knowledge.
problem Detect anomalies with missing structural knowledge.
method Simple, efficient methods for polytree causal graphs.
result Heuristic identifies root causes based on anomaly scores.
Study on learning sparse fixed-structure Gaussian Bayesian networks with near-optimal sample complexity.
problem Learning a fixed-structure Gaussian Bayesian network up to a bounded error in total variation distance.
method Analysis of node-wise least squares regression and introduction of BatchAvgLeastSquares and CauchyEst algorithms.
result BatchAvgLeastSquares and CauchyEstTree have near-optimal sample complexity.
Algorithm learns Bayesian network structure efficiently from data.
problem Learning directed acyclic graphical models from observational data.
method Local Markov boundary search procedure to recursively construct ancestral sets.
result Simple greedy search algorithm learns Markov boundary of each node efficiently.
We describe various sets of conditional independence relationships, sufficient for qualitatively comparing non-vanishing squared partial correlations of a Gaussian random vector. These sufficient conditions are satisfied by several graphical Markov models. Rules for comparing degree of association among the vertices of…
SOLBP extends efficient inference to uncertain Bayesian networks.
problem Inference in uncertain Bayesian networks with second-order probabilities.
method Extends Loopy Belief Propagation to second-order Bayesian networks.
result Generates inferences consistent with sum-product networks, more efficient and scalable.
This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. First, it is demonstrated that the problem remains hard even in networks with very simple top…