Principles and analytical tools for reconstruction of probabilistic dependency structures in special class

O.S. Balabanov


We examine a problem of reconstruction of dependency structure from data. It is assumed that model structure belongs to class of "mono-flow" graphs, which is a subclass of acyclonic digraph (known as DAGs) and is super-class relatively to the poly-trees. Properties of the mono-flow dependency models are examined, especially in terms of patterns of unconditional dependencies and mutual information. We characterize the twin-association evolving among two variables. Specialized methods of inference of mono-flow dependency model are briefly reviewed. To justify correctness of model recovery from data we formulate an assumption of unconditional (marginal) edge-wise faithfulness, perhaps the most reliable one among all simple versions of Causal faithfulness assumption. On the basis of the assumption and the properties of mono-flow dependency models we derive several empirical resolutions for edge identification, which make use 2-placed statistics only. A lot of experiments with artificial data have demonstrated efficiency of the resolutions in that they correctly recover many edges and commit low error rate.

Problems in programming 2017; 1: 97-110


dependence structure recovery; mono-flow graph; unconditional dependence; empirical manifestation of dependence; empirical resolutions of edge identification


Spirtes P. (2010). Introduction to causal inference. Journal of Machine Learning Research. 11, 1643−1662.

Kalisch M., Bühlmann P. (2014). Causal structure learning and inference: a selective review. Quality Technology & Quantitative Management. 11 (1), 3-21.

Scheines R., Spirtes P., Glymour C. et al. (1998). The TETRAD Project: Constraint based aids to causal model specification. Multivariate Behavioral Research. 33 (1), 65-118.

Chickering D., Heckerman D., Meek C. (2004). Large-sample learning of Bayesian networks is NP-hard. Journal of Machine Learning Research. 5, 1287-1330.

Balabanov O.S. (2016). Vidtvorennya kauzalnych merezh na osnovi analizu markovskich vlastyvostej [Reconstruction of causal networks via analysis of Markov properties]. Mathematical Machines and Systems. (1), 16-26. [In Ukrainian].

Balabanov O.S. (2014). Causal nets: analysis, synthesis and inference from statistical data, Doctor of math. sciences thesis, V.M. Glushkov Institute of Cybernetics, Kyiv, Ukraine. [In Ukrainian].

Balabanov O.S. (2009) Probabilistic dependency models: graphical and statistical properties. Mathematical Machines and Systems. (3), 80-97. [In Ukrainian].

Balabanov O.S. (2007). Rules for picking up separators in Bayesian networks. Problems in programming. (4), 33-43. [In Ukrainian].

Chow C.K., Liu C.N. (1968). Approximating discrete probability distributions with dependence trees. IEEE trans. on Information Theory. 14 (3), 462-467.

Balabanov O.S. (2001). Inductive recovery of structures of dependency trees. Problems in programming. (1-2), 95-108. [In Ukrainian].

Balabanov O.S. (2011). Accelerating algorithms for Bayesian networks recovery. Adaptation to structures without cycles. Problems in programming. (1), 63-69. [In Ukrainian].

Geiger D., Paz A., Pearl J. (1993). Learning simple causal structures. Internat. Journal of Intelligent Systems. 8 (2), 231-247.

de Campos L.M., Huete J.F. (1997). On the use of independence relationships for learning simplified belief networks. Intern. Journal of Intelligent Systems. 12 (7), 495-522.<495::AID-INT2>3.0.CO;2-G

Balabanov O.S. (2004). Efficient method for discovery of dependency structures in statistical data. Problems in programming. (2 -3), 312-319. [In Russian].

Balabanov A.S. (2005). Inference of structures of models of probabilistic dependences from statistical data. Cybernetics and Systems Analysis. 41 (6), 808-817. -Springer, New York.

Balabanov A.S. (2003). Inductive reconstruction method for "mono-flow" probabilistic graphical models of Dependencies. Journal of Automation and Information Sciences. 35 (10), 1-8. - Begell House Publishers, Danbury.

Balabanov A.S. (2009). Reconstruction of the model of probabilistic dependences by statistical data. Tools and algorithm. J. of Automation and Information Sciences. 41 (12), 32-46.

Balabanov O.S. (2016). Induced dependence, factor interaction, and discriminating between causal structures. Cybernetics and Systems Analysis. 52 (1), 8-19.



  • There are currently no refbacks.