×

The size distribution for Markov equivalence classes of acyclic digraph models. (English) Zbl 1043.68096

Bayesian networks, equivalently graphical Markov models determined by acyclic digraphs or ADGs (also called directed acyclic graphs or dags), have proved to be both effective and efficient for representing complex multivariate dependence structures in terms of local relations. However, model search and selection is potentially complicated by the many-to-one correspondence between ADGs and the statistical models that they represent. If the ADGs/models ratio is large, search procedures based on unique graphical representations of equivalence classes of ADGs could provide substantial computational efficiency. Hitherto, the value of the ADGs/models ratio has been calculated only for graphs with \(n=5\) or fewer vertices. In the present study, a computer program was written to enumerate the equivalence classes of ADG models and study the distributions of class sizes and number of edges for graphs up to \(n=10\) vertices. The ratio of ADGs to numbers of classes appears to approach an asymptote of about \(3.7.\) Distributions of the classes according to number of edges and class size were produced which also appear to be approaching asymptotic limits. Imposing a bound on the maximum number of parents to any vertex causes little change if the bound is sufficiently large, with four being a possible minimum. The program also includes a new variation of orderly algorithm for generating undirected graphs.

MSC:

68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence

Software:

MIM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersson, S. A.; Madigan, D.; Perlman, M. D., A characterization of Markov equivalence classes for acyclic digraphs, Ann. Statist., 25, 505-541 (1997) · Zbl 0876.60095
[2] Barbosa, V. C.; Szwarcfiter, J. L., Generating all the acyclic orientations of an undirected graph, Inform. Process. Lett., 72, 71-74 (1999) · Zbl 1339.05379
[3] Buntine, W. L., Operations for learning with graphical models, J. Artificial Intelligence Res., 2, 159-225 (1994)
[4] Chickering, D. M., A transformational characterization of equivalent Bayesian network structures, (Uncertainty in Artificial Intelligence: Proc. of the Eleventh Conference (1995), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 87-98
[5] Chickering, D. M., Learning equivalence classes of Bayesian network structures, (Uncertainty in Artificial Intelligence: Proc. of the Twelfth Conference (1996), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 150-157
[6] Colbourn, C. J.; Read, R. C., Orderly algorithms for graph generation, Intern. J. Comput. Math., 7, 167-172 (1979) · Zbl 0418.05046
[7] Cooper, G. F.; Herskovits, E., A Bayesian method for the induction of probabilistic networks from data, Machine Learning, 9, 309-347 (1992) · Zbl 0766.68109
[8] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press/McGraw-Hill: MIT Press/McGraw-Hill New York, pp. 263-280
[9] Edwards, D., Introduction to Graphical Modeling (1995), Springer: Springer New York
[10] Hall, M., The Theory of Groups (1976), Chelsea: Chelsea New York
[11] Heckerman, D.; Geiger, D.; Chickering, D. M., Learning Bayesian networks: The combination of knowledge and statistical data, (Uncertainty in Artificial Intelligence: Proc. of the Tenth Conference (1994), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 293-301
[12] Jensen, F. V., An Introduction to Bayesian Networks (1996), Univ. College London Press: Univ. College London Press London
[13] Lauritzen, S. L., Graphical Models (1996), Oxford Univ. Press: Oxford Univ. Press Oxford · Zbl 0907.62001
[14] Lauritzen, S. L.; Dawid, A. P.; Larsen, B. N.; Leimer, H. G., Independence properties of directed Markov fields, Networks, 20, 491-505 (1990) · Zbl 0743.05065
[15] Lauritzen, S. L.; Spiegelhalter, D. J., Local computations with probabilities on graphical structures and their application to expert systems (with discussion), J. Royal Statist. Soc. Ser. B, 50, 157-224 (1988) · Zbl 0684.68106
[16] Madigan, D.; Andersson, S. A.; Perlman, M. D.; Volinsky, C. M., Bayesian model averaging and model selection for Markov equivalence classes of acyclic digraphs, Comm. Statist. Theory Meth., 25, 2493-2519 (1996) · Zbl 0894.62032
[17] Madigan, D.; Raftery, D. A., Model selection and accounting for model uncertainty in graphical models using Occam’s window, J. Amer. Statist. Assoc., 89, 1535-1546 (1994) · Zbl 0814.62030
[18] Meek, C., Causal inference and causal explanation with background, (Uncertainty in Artificial Intelligence: Proc. of the Eleventh Conference (1995), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 403-410
[19] Neapolitan, R. E., Probabilistic Reasoning in Expert Systems (1990), Wiley: Wiley New York
[20] Oberschelp, W., Kombinatorische Anzahlbestimmungen in Relationen, Math. Annalen, 174, 53-78 (1967) · Zbl 0155.35002
[21] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[22] Pólya, G., Kombinatorische Anzahlbestimmungen für Gruppen, Graphen, und chemische Verbindungen, Acta Math., 68, 145-254 (1937) · JFM 63.0547.04
[23] Read, R. C., Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations, (Alspach, B.; Hell, P.; Miller, D. J., Ann. Discrete Math. 2: Algorithmic Aspects of Combinatorics (1978), North-Holland: North-Holland Amsterdam), 107-120 · Zbl 0392.05001
[24] Redfield, J. H., Enumeration of nonseparable graphs, Amer. J. Math., 49, 433-455 (1927) · JFM 53.0106.03
[25] Robinson, R. W., Counting labeled acyclic digraphs, (Harary, F., New Directions in the Theory of Graphs: Proc. of the Third Ann Arbor Conference on Graph Theory, 1971 (1973), Academic Press: Academic Press New York), 239-273 · Zbl 0259.05116
[26] Shachter, R. D.; Kenley, C. R., Gaussian influence diagrams, Management Sci., 35, 527-550 (1989)
[27] Spiegelhalter, D. J.; Dawid, A. P.; Lauritzen, S. L.; Cowell, R. G., Bayesian analysis in expert systems (with discussion), Statist. Sci., 8, 219-283 (1993) · Zbl 0955.62523
[28] Spiegelhalter, D. J.; Lauritzen, S. L., Sequential updating of conditional probabilities on directed graphical structures, Networks, 20, 579-605 (1990) · Zbl 0697.90045
[29] M.L. Stein, P.R. Stein, Enumeration of linear graphs and connected linear graphs up to \(p\); M.L. Stein, P.R. Stein, Enumeration of linear graphs and connected linear graphs up to \(p\)
[30] B. Steinsky, Enumeration of labeled chain graphs and labeled essential directed acyclic graphs, Discrete Math., Submitted; B. Steinsky, Enumeration of labeled chain graphs and labeled essential directed acyclic graphs, Discrete Math., Submitted · Zbl 1059.05099
[31] B. Steinsky, Efficient coding of labeled directed acyclic graphs, Soft Computing, Submitted; B. Steinsky, Efficient coding of labeled directed acyclic graphs, Soft Computing, Submitted · Zbl 1059.05099
[32] Verma, T.; Pearl, J., Equivalence and synthesis of causal models, (Uncertainty in Artificial Intelligence: Proc. Of the Sixth Conference (1990), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 220-227
[33] Verma, T.; Pearl, J., An algorithm for deciding if a set of observed independencies has a causal explanation, (Uncertainty in Artificial Intelligence: Proc. of the Eighth Conference (1992), Morgan Kaufmann: Morgan Kaufmann San Francisco, CA), 323-330
[34] Volf, M.; Studený, M., A graphical characterization of the largest chain graphs, Internat. J. Approx. Reason., 20, 209-236 (1999) · Zbl 0935.62063
[35] Whittaker, J. L., Graphical Models in Applied Multivariate Statistics (1990), Wiley: Wiley New York · Zbl 0732.62056
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.