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.