DOI: 10.17586/2226-1494-2015-15-1-78-85


MATRIX-VECTOR ALGORITHMS FOR NORMALIZING FACTORS IN ALGEBRAIC BAYESIAN NETWORKS LOCAL POSTERIORI INFERENCE

A. A. Zolotin, A. L. Tulupyev, A. V. Sirotkin


Read the full article 
Article in Russian

For citation: Zolotin A.A., Tulupyev A.L., Sirotkin A.V. Matrix-vector algorithms for normalizing factors in algebraic Bayesian networks local posteriori inference. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2015, vol. 15, no. 1, pp. 78–85 (in Russian)

Abstract

We consider a task of local posteriori inference description by means of matrix-vector equations in algebraical Bayesian networks that represent a class of probabilistic graphical models. Such equations were generally presented in previous publications, however containing normalizing factors that were provided with algorithmic descriptions of their calculations instead of the desired matrix-vector interpretation. To eliminate this gap, the normalized factors were firstly represented as scalar products. Then, it was successfully shown that one of the components in each scalar product can be expressed as a Kronecker degree of a constant two-dimensional vector. Later on, non-normalized posteriori inference matrixoperator transplantation and further transfer within each scalar product yielded a representation of one of the scalar product components as a sequence of tensor products of two-dimensional vectors. The latter vectors have only two possible values in one case and three values in the other. The choice among those values is determined by the structure of input evidence. The second component of each scalar products is the vector with original data. The calculations performed gave the possibility for constructing corresponding vectors; the paper contains a table with proper examples for some of them. Local posteriori inference representation for matrix-vector equations simplify the development of local posteriori inference algorithms, their verification and further implementation based on available libraries. These equations also give the possibility for application of classical mathematical techniques to the obtained results analysis. Finally, the results obtained make it possible to apply the method of postponed calculations. This method helps avoiding construction of big-size vectors; instead, the vectors components can be calculated just in time they are needed by means of bitwise operations. 


Keywords: Bayesian networks, posteriori inference, inference algorithms, postponed calculations, bitwise operations

Acknowledgements. Часть результатов, представленных в статье, была получена в рамках исследовательского проекта, поддержанного грантами РФФИ №№ 12-01-00945-а, 15-01-09001-а.

References

1. Gorodetskii V.I. Algebraicheskie baiesovskie seti – novaya paradigma ekspertnykh sistem [Algebraic Bayesian networks - a new paradigm of expert systems]. Yubileinyi sbornik trudov otdeleniya informatiki, vychislitel'noi tekhniki i avtomatizatsii RAN [Anniversary Collection Proceedings of the Department of Informatics, Computer Science and Automation RAS]. Moscow, RAS Publ., 1993, vol. 2, pp. 120–141.

2. Gorodetskii V.I., Tulup'ev A.L. Generating consistent knowledge bases with uncertainty. Journal of Computer and Systems Sciences International, 1997, vol. 36, no. 5, pp. 683–691.

3. 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.

4. 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.

5. Bobadilla J., Ortega F., Hernando A., Gutierrez A. Recommender systems survey. Knowledge-Based Systems, 2013, vol. 46, pp. 109–132. doi: 10.1016/j.knosys.2013.03.012

6. Borras J., Moreno A., Valls A. Intelligent tourism recommender systems: a survey. Expert Systems with Applications, 2014, vol. 41, no. 16, pp. 7370–7389. doi: 10.1016/j.eswa.2014.06.007

7. Constantinou A.C., Fenton N.E., Neil M. Pi-football: a Bayesian network model for forecasting Association Football match outcomes. Knowledge-Based Systems, 2012, vol. 36, pp. 322–339. doi: 10.1016/j.knosys.2012.07.008

8. Kim J.-S., Jun C.-H. Ranking evaluation of institutions based on a Bayesian network having a latent variable. Knowledge-Based Systems, 2013, vol. 50, pp. 87–99. doi: 10.1016/j.knosys.2013.05.010

9. Ngoduy D., Watling D., Timms P., Tight M. Dynamic Bayesian belief network to model the development of walking and cycling schemes. International Journal of Sustainable Transportation, 2013, vol. 7, no. 5, pp. 366–388. doi: 10.1080/15568318.2012.674627

10. Weber P., Medina-Oliva G., Simon C., Iung B. Overview on Bayesian networks applications for dependability, risk analysis and maintenance areas. Engineering Applications of Artificial Intelligence, 2012, vol. 25, no. 4, pp. 671–682. doi: 10.1016/j.engappai.2010.06.002

11. Chen T.-T., Leu S.-S. Fall risk assessment of cantilever bridge projects using Bayesian network. Safety Science, 2014, vol. 70, pp. 161–171. doi: 10.1016/j.ssci.2014.05.011

12. Hu Y., Zhang X., Ngai E.W.T., Cai R., Liu M. Software project risk analysis using Bayesian networks with causality constraints. Decision Support Systems, 2013, vol. 56, no. 1, pp. 439–449. doi: 10.1016/j.dss.2012.11.001

13. Khakzad N., Khan F., Amyotte P. Safety analysis in process facilities: comparison of fault tree and Bayesian network approaches. Reliability Engineering and System Safety, 2011, vol. 96, no. 8, pp. 925–932. doi: 10.1016/j.ress.2011.03.012

14. Khadjeh Nassirtoussi A., Aghabozorgi S., Ying Wah T., Ngo D.C.L. Text mining for market prediction: a systematic review. Expert Systems with Applications, 2014, vol. 41, no. 16, pp. 7653–7670. doi: 10.1016/j.eswa.2014.06.009

15. Landuyt D., Broekx S., D'hondt R., Engelen G., Aertsen J., Goethals P.L.M. A review of Bayesian belief networks in ecosystem service modeling. Environmental Modelling and Software, 2013, vol. 46, pp. 1–11. doi: 10.1016/j.envsoft.2013.03.011

16. Tulup'ev A.L., Sirotkin A.V. Algebraicheskie baiesovskie seti: printsip dekompozitsii i logiko-veroyatnostnyi vyvod v usloviyakh neopredelennosti [Algebraic Bayesian networks: decomposition principle and probabilistic-logic inference under uncertainty]. Information-Measuring and Control Systems, 2008, vol. 6, no. 10, pp. 85–87.

17. Nilsson N.J. Probabilistic logic. Artificial Intelligence, 1986, vol. 28, no. 1, pp. 71–87. doi: 10.1016/0004- 3702(86)90031-7

18. Schippers M. Probabilistic measures of coherence: from adequacy constraints towards pluralism. Synthese, 2014, vol. 191, no. 16, pp. 3821–3845. doi: 10.1007/s11229-014-0501-7 

19. Larrañaga P., Karshenas H., Bielza C., Santana R. A review on evolutionary algorithms in Bayesian network learning and inference tasks. Information Sciences, 2013, vol. 233, pp. 109–125. doi: 10.1016/j.ins.2012.12.051

20. de Campos L.M., Castellano J.G. Bayesian network learning algorithms using structural restrictions. International Journal of Approximate Reasoning, 2007, vol. 45, no. 2, pp. 233–254. doi: 10.1016/j.ijar.2006.06.009

21. Tulup'ev A.L. Aposteriornye otsenki veroyatnostei v algebraicheskikh baiesovskikh setyakh [A posteriori probabilistic estimates in algebraic Bayesian networks]. Vestnik of the St. Petersburg University: Seriya 10: Prikladnaya matematika. Informatika. Protsessy Upravleniya, 2012, no. 2, pp. 51–59.

22. Tulup'ev A.L., Sirotkin A.V. Matrichnye uravneniya lokal'nogo logiko-veroyatnostnogo vyvoda otsenok istinnosti elementov v algebraicheskikh baiesovskikh setyakh [Matrix-Vector Equations for Local Probabilistic-Logic In- ference in Algebraic Bayesian Networks]. Vestnik of the St. Petersburg University: Mathematics, 2012, no. 3, pp. 63–72.

23. Bellman R. Introduction to Matrix Analysis. NY, McGraw-Hill, 1970.

24. Sirotkin A.V. Algebraicheskie Baiesovskie Seti: Vychislitel'naya Slozhnost' Algoritmov LogikoVeroyatnostnogo Vyvoda v Usloviyakh Neopredelennosti. Diss. … kand. fiz.-mat. nauk [Algebraic Bayesian Networks: the Computational Complexity of Algorithms of Logical and Probabilistic Iinference Under Uncertainty. Phys.-math. sci. diss]. St. Petersburg, SPbSU, 2011, 218 p. 



Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2019 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.

Яндекс.Метрика