QUATERNARY STRUCTURE SYNTHESIS IN ALGEBRAIC BAYESIAN NETWORKS: INCREMENTAL AND DECREMENTAL ALGORITHMS

Subject of Research. Algebraic Bayesian networks are referred to a class of probabilistic graphical models that are a representation of knowledge bases with uncertainty. The distinguishing feature of ABN is the availability of global structures. Among them there are primary and secondary structures that are directly used in various kinds of probabilistic logical inference as well as tertiary and quaternary involved in the problems of automatic synthesis and identification of the properties of the secondary structure and partially in the machine learning tasks within specified networks. Existing algorithms for quaternary structure changing require its complete rebuild when changing the primary structure. That feature slows down the whole global structures synthesis, dispels user’s attention who is forced to re-analyze the whole rebuilt structure instead of focusing on the changes that were directly caused by the limited modification of the original data. This fact reduces ABN attractiveness as a model for data processing in general. Scope of Research. This paper is aimed at speeding up the rebuild process and eliminating the shortage of the quaternary structure rebuild algorithms when adding and deleting vertices of primary structure expressed in excess rebuild of the entire structure. The task of algorithm incrementalization for quaternary structure rebuild is solved to achieve the goal. Method. The proposed approach is based on the properties of incremental algorithms that reduce the amount of computations due to the result obtained at the previous step of the algorithm. All the arguments used in the paper are expressed in a graph theory language to apply the established system of terms and classical results. Main Results. The paper presents incremental and decremental algorithms, complemented by a proof of correctness and listing. Given algorithms are based on the previously obtained incremental algorithms for tertiary structure. Moreover, a detailed analysis of the plurality of separators is carried out on each stage of the algorithms. Theoretical and Practical Relevance. These algorithms develop a global structure of algebraic Bayesian networks as well as the theory of probabilistic graphical models in general. Furthermore, they create the groundwork for creation of the secondary structure invariants that may be non-unique even if the primary structure is fixed unlike the current approach where connections are included in the secondary structure. The deletion of manipulation with a set of secondary structures considerably simplifies and makes foreseeable visualization of such complex object as ABN and may improve the computational characteristics of probabilistic logical inference algorithms. It also enables to reformulate the problem of ABN machine learning excluding any need for synthesis of many different objects with complex structure and virtually the same semantics. It also can be expected that the obtained incremental algorithms will accelerate computational processes of rebuilding and properties analysis for all four global ABN structures.

1. Tulup'ev A.L., Nikolenko S.I., Sirotkin A.V. Baiesovskie Seti: Logiko-Veroyatnostnyi Podkhod [Bayesian Networks: Logical-Probabilistic Approach]. St. Petersburg, Nauka Publ., 2006, 607 p.
2. Tulup'ev A.L., Sirotkin A.V., Nikolenko S.I. Baiesovskie Seti Doveriya: Logiko-Veroyatnostnyi Vyvod v Atsiklicheskikh Napravlennykh Grafakh [Bayesian Belief Networks: Logical-Probabilistic Inference in the Acyclic Directed Graph]. St. Petersburg, SPbSU Publ., 2009, 400 p.
3. Tulup'ev A.L. Algebraicheskie Baiesovskie Seti: Lokal'nyi Logiko-Veroyatnostnyi Vyvod [Algebraic Bayesian Networks: a Local Logic-Probabilistic Inference]. St. Petersburg, SPbGU Publ., Anatoliya, 2007, 80 p.
4. Kabir G., Sadiq R., Tesfamariam S. A fuzzy Bayesian belief network for safety assessment of oil and gas pipelines. Structure and Infrastructure Engineering, 2016, vol. 12, no. 8, pp. 874–889. doi: 10.1080/15732479.2015.1053093
5. John A., Yang Z., Riahi R., Wang J. A risk assessment approach to improve the resilience of a seaport system using Bayesian networks. Ocean Engineering, 2016, vol. 111, pp. 136–147. doi: 10.1016/j.oceaneng.2015.10.048
6. Zarikas V., Papageorgiou E., Regner P. Bayesian network construction using a fuzzy rule based approach for medical decision support. Expert Systems, vol. 32, no. 3, pp. 344–369. doi: 10.1111/exsy.12089
7. Zhang Q. Dynamic uncertain causality graph for knowledge representation and reasoning: continuous variable, uncertain evidence, and failure forecast. IEEE Transactions on Systems Man, and Cybernetics: Systems, 2015, vol. 45, no. 7, pp. 990–1003. doi: 10.1109/TSMC.2015.2392711
8. Zotov M.A., Levenets D.G., Tulupyev A.L., Zolotin A.A. Synthesis of the secondary structure of algebraic Bayesian networks: an incremental algorithm and statistical estimation of its complexity. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2016, vol. 16, no. 1, pp. 122–132. doi: 10.17586/2226-1494-2016-16-1-122-132
9. Banerjee S., Ghosal S. Bayesian structure learning in graphical models. Journal of Multivariate Analysis, 2015, vol. 136, pp. 147–162. doi: 10.1016/j.jmva.2015.01.015
10. Filchenkov A.A., Tulupyev A.L. The algebraic Bayesian network minimal join graphs cycles analysis. SPIIRAS Proceedings, 2011, no. 2, pp. 151–173.
11. Filchenkov A.A., Tulupyev A.L. Algorithm for detection of algebraic Bayesian network primary structure acyclicity based on its quaternary structure. SPIIRAS Proceedings, 2011, no. 4, pp. 128–145.
12. Filchenkov A.A. Sintez Grafov Smezhnosti v Mashinnom Obuchenii Global'nykh Struktur Algebraicheskikh Baiesovskikh Setei. Dis. ... kand. fiz.-mat. nauk [Synthesis Join Graph in Machine Learning of Global Structures of Algebraic Bayesian Networks. Dis. Phys.-Math. Sci.]. Samara, 2013, 339 p.
13. Filchenkov A.A., Tulupyev A.L. The Algebraic Bayesian Network Tertiary Structure. SPIIRAS Proceedings, 2011, no. 3, pp. 164–187.
14. Bernstein A. Maintaining shortest paths under deletions in weighted directed graphs. SIAM Journal on Computing, 2016, vol. 45, no. 2, pp. 548–574. doi: 10.1137/130938670
15. Soulignac F. J. Fully dynamic recognition of proper circular-arc graphs. Algorithmica, 2015, vol. 71, no. 4, pp. 904–968. doi: 10.1007/s00453-013-9835-7
16. Lu G.-F., Zou J., Wang Y. A new and fast implementation of orthogonal LDA algorithm and its incremental extension. Neural Processing Letters, 2016, vol. 43, no. 3, pp. 687–707. doi: 10.1007/s11063-015-9441-6
17. Feng L., Wang Y., Zuo W. Quick online spam classification method based on active and incremental learning. Journal of Intelligent and Fuzzy Systems, 2016, vol. 30, no. 1, pp. 17–27. doi: 10.3233/IFS-151707
18. Chen M.-H., Chang P.-C., Wu J.-L. A population-based incremental learning approach with artificial immune system for network intrusion detection. Engineering Applications of Artificial Intelligence, 2016, vol. 51, pp. 171–181. doi: 10.1016/j.engappai.2016.01.020
19. Levenets D.G., Zotov M.A., Romanov A.V., Tulupyev A.L., Zolotin A.A., Filchenkov A.A. Decremental and incremental reshaping of algebraic Bayesian networks global structures. Proc. 1st Int. Scientific Conference on Intelligent Information Technologies for Industry, IITI’16. Sochi, Russia, 2016, pp. 57–67. doi: 10.1007/978-3-319-33816-3_6
20. Romanov A.V., Levenets D.G., Zolotin A.A., Tulup'ev A.L. Incremental synthesis of tertiary structure of algebraic Bayesian networks. Proc. Int. Conf. on Soft Computing and Measurements. St. Petersburg, 2016, vol. 1, pp. 27–29. (In Russian)
21. Zotov M.A., Tulupyev A.L Secondary structure synthesis in algebraic Bayesian networks: a statistical technique for complexity estimates and comparative analysis of greedy and straightforward algorithms. Computer Tools in Education, 2015, no. 1, pp. 3–18.
22. Zotov M.A., Tulupyev A.L., Sirotkin A.V. Complexity statistical estimates of straightforward and greedy algorithms for algebraic Bayesian networks syntesis. Fuzzy Systems and Soft Computing, 2015, vol. 10, no. 1, pp. 75–91.
 

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License