Complexity statistical estimates of straightforward and greedy algorithms for algebraic Baesian networks syntesis

M. A. Zotov ; A. L. Tulupyev ; A. V. Sirotkin

Nečetkie sistemy i mâgkie vyčisleniâ, Tome 10 (2015) no. 1, pp. 75-91.

Résumé

The paper considers straightforward and greedy minimal joint graph synthesis algorithms. Comparative statistical analysis of runtime was done based on experiments run on specially generated datasets. A new algorithm for generating the loads with certain characteristics was developed. Statistical analysis pointed out three subintervals of joint graph vertex set cardinality (number of elements): that of 5–35 where the greedy algorithm had sufficiently higher speed than the straightforward algorithm did, that of 60–105 the straightforward algorithm had sufficiently higher speed than the greedy algorithm did, and that of 35–60 where the algorithms advantage in their speed depended on each specific initial dataset. According to rank statistics, there may be detected a few outbursts in the subinterval of 5–60.

Détail

Keywords: uncertainty representation, algebraic Bayesian networks, probabilistic graphical models, knowledge pattern, knowledge with uncertainty, probabilistic-logic inference, statistical indicators for algorithm's complexity.

Bibliographie

[1] Tulupyev A. L., “Automatic learning of fragments of knowledge in algebraic Bayesian networks”, Proceedings of V-th International scientific-practical conference «Integrated Models and Soft Computing in Artificial Intelligence», v. 1, Fizmatlit Publ., Moscow, 2009, 163–176 (in Russian)

[2] Tulupyev A. L., “Algebraic Bayesian networks: open problems of the local machine learning”, Proceedings of the All-Russian Scientific Conference for Computer Science «Spisok-2014», VVM Publ., SPb., 2014, 569–577 (in Russian)

[3] Tulupyev A. L., Sirotkin A. V., Nikolenko S. I., Bayesian belief networks: logic-probabilistic inference in the acyclic directed graphs, Saint-Petersburg State University Publ., SPb, 2009, 400 pp. (in Russian)

[4] Jaynes E. T., “Bayesian methods: general background”, Maximum-Entropy and Bayesian Methods in Applied Statistics, ed. J. H. Justice, Cambridge Univ. Press, Cambridge, 1986 | MR

[5] Pearl J., Causality: Models, Reasoning, and Inference, Cambridge University Press, Cambridge, 2000, 400 pp. | MR | Zbl

[6] Tulupyev A. L., “Probabilistic logic and probabilistic graphical models in the databases of fragments of knowledge with uncertainty”, Scientific reports of scientific-practical conference of students, graduate students, young scientists and specialists “Integrated models and soft computing, probabilistic systems and program systems in artificial intelligence”, v. 1, Fizmatlit Publ., Moscow, 2009, 26–46 (in Russian)

[7] Tulupyev A. L., “Adjacency tree with ideals of conjuncts as an acyclic algebraic Bayesian network”, SPIIRAS Proceedings, 1:3 (2006), 198–227 (in Russian) | DOI

[8] Tulupyev A. L., Algebraic Bayesian networks: global logic-probabilistic inference in the adjacent trees, Tutorial, Elements of soft computing, Saint-Petersburg State University Publ., SPb, 2007, 40 pp. (in Russian)

[9] Tulupyev A. L., Nikolenko S. I., Sirotkin A. V., Bayesian network: the logical-probabilistic approach., Nauka Publ., SPb, 2006, 607 pp. (in Russian)

[10] Oparin V. V., Tulupyev A. L., “Synthesis of the adjacency graph with the minimum number of edges: an algorithm formalization and analysis of its correctness”, SPIIRAS Proceedings, 2009, no. 11, 142-157 (in Russian)

[11] Filchenkov A. A., Tulupyev A. L., “The structural analysis of systems of minimal adjacency graphs”, SPIIRAS Proceedings, 2009, no. 11, 104–129 (in Russian)

[12] Filchenkov A. A., Tulupyev A. L., “Analysis of cycles in the minimum adjacency graphs of algebraic Bayesian networks”, SPIIRAS Proceedings, 2011, no. 2(17), 151–173 (in Russian)

[13] Tulupyev A. L., “Automatic learning of fragments of knowledge in algebraic Bayesian networks”, Proceedings of V-th International scientific-practical conference “Integrated Models and Soft Computing in Artificial Intelligence”, v. 1, Fizmatlit Publ., Moscow, 2009, 163–176 (in Russian)

[14] Oparin V. V., Filchenkov A. A., Sirotkin A. V., Tulupyev A. L., “Matroid representation of adjacency graphs family over a set of fragments of knowledge”, Scientific and Technical Bulletin of Saint Petersburg State University of Information Technologies, Mechanics and Optics, 2010, no. 4(68), 73–76 (in Russian)

[15] Class LinkedList$$E$>$, Java 2 Platform Standard Edition 5.0 API Specification. https://docs.oracle.com/javase/1.5.0/docs/api/java/util/LinkedList.html

[16] class template std::queue, CPlusPlus.com. http://www.cplusplus.com/reference/queue/queue/

[17] Interface Queue$$E$>$, Java 2 Platform Standard Edition 5.0 API Specification. https://docs.oracle.com/javase/1.5.0/docs/api/java/util/Queue.html

[18] Queue$$T$>$ Class, Microsoft Developer Network. http://msdn.microsoft.com/ru-ru/library/7977ey2c(v=vs.110).aspx

[19] Class ArrayList$$E$>$, Java 2 Platform Standard Edition 5.0 API Specification. https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html

[20] Interface List$$E$>$, Java 2 Platform Standard Edition 5.0 API Specification https://docs.oracle.com/javase/7/docs/api/java/util/List.html

[21] List$$T$>$ Class, Microsoft Developer Network. http://msdn.microsoft.com/ru-ru/library/6sh2ey19(v=vs.110).aspx

[22] class template std::vector, CPlusPlus.com. http://www.cplusplus.com/reference/vector/vector