Learning Sparse Fixed-Structure Gaussian Bayesian Networks
Preprint
Abstract
Gaussian Bayesian networks (a.k.a. linear Gaussian structural equation models) are widely used to model causal interactions among continuous variables. In this work, we study the problem of learning a fixed-structure Gaussian Bayesian network up to a bounded error in total variation distance. We analyze the commonly used node-wise least squares regression (LeastSquares) and prove that it has a near-optimal sample complexity. We also study a couple of new algorithms for the problem: - BatchAvgLeastSquares takes the average of several batches of least squares solutions at each node, so that one can interpolate between the batch size and the number of batches. We show that BatchAvgLeastSquares also has near-optimal sample complexity. - CauchyEst takes the median of solutions to several batches of linear systems at each node. We show that the algorithm specialized to polytrees, CauchyEstTree, has near-optimal sample complexity. Experimentally, we show that for uncontaminated, realizable data, the LeastSquares algorithm performs best, but in the presence of contamination or DAG misspecification, CauchyEst/CauchyEstTree and BatchAvgLeastSquares respectively perform better.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Testing Bayesian NetworksIEEE Transactions on Information Theory, 2020
- Identifiability of Gaussian linear structural equation models with homogeneous and heterogeneous error variancesJournal of the Korean Statistical Society, 2020
- On causal discovery with an equal-variance assumptionBiometrika, 2019
- Identifiability of Gaussian structural equation models with equal error variancesBiometrika, 2013
- Smallest singular value of a random rectangular matrixCommunications on Pure and Applied Mathematics, 2009
- Sparse inverse covariance estimation with the graphical lassoBiostatistics, 2007
- From correlation to causation networks: a simple approximate learning algorithm and its application to high-dimensional plant gene expression dataBMC Systems Biology, 2007
- The Sample Complexity of Learning Fixed-Structure Bayesian NetworksMachine Learning, 1997
- Decision theoretic generalizations of the PAC model for neural net and other learning applicationsInformation and Computation, 1992
- Fusion, propagation, and structuring in belief networksArtificial Intelligence, 1986