Применение третичной структуры алгебраической байесовской сети в задаче апостериорного вывода

Артем Андреевич Вяткин, Максим Викторович Абрамов, Никита Алексеевич Харитонов, Александр Львович Тулупьев

Аннотация


В теории алгебраических байесовских сетей существуют алгоритмы, позволяющие проводить глобальный апостериорный вывод с использованием вторичных структур. При этом построение вторичных структур предполагает использование третичной структуры. Следовательно, возникает вопрос об обособленном применении третичной структуры в задаче апостериорного вывода. Этот вопрос рассматривался ранее, но было приведено только общее описание алгоритма, при этом учитывались лишь модели со скалярными оценками вероятности истинности. В данной работе приведен алгоритм, расширяющий вышеупомянутый до возможности его использования в случае интервальных оценок. Помимо этого, важным свойством алгебраической байесовской сети является ацикличность, и корректность работы перечисленных алгоритмов обеспечивается только для ацикличных сетей. Поэтому необходимо также уметь проверять ацикличность алгебраической байесовской сети с применением третичной структуры. Описание этого алгоритма также представлено в работе, в его основе лежит ранее доказанная теорема, которая связывает количество моделей фрагментов знаний в сети с количеством непустых сепараторов и количеством компонент связности сильных сужений в цикличной АБС, а также доказанная в данной статье теорема о принадлежности двух моделей фрагментов знаний к одной компоненте связности сильного сужения. Для всех разработанных алгоритмов доказана корректность работы, а также вычислена их оценка временной сложности.

Ключевые слова


алгебраические байесовские сети; фрагмент знаний; логико-вероятностный вывод; третичная структура; вероятностные графические модели; машинное обучение

Полный текст:

PDF

Литература


Larrañaga P., Moral S. Probabilistic graphical models in artificial intelligence. Applied Soft Computing. 2011. Vol. 11, no. 2. P. 1511–1528. DOI: 10.1016/j.asoc.2008.01.003.

Yang Y., Xu M., Wu W., et al. 3D Multiview Basketball Players Detection and Localization Based on Probabilistic Occupancy. 2018 Digital Image Computing: Techniques and Applications (DICTA). IEEE. 2018. P. 1–8. DOI: 10.1109/DICTA.2018.8615798.

Masmoudi K., Abid L., Masmoudi A. Credit risk modeling using Bayesian network with a latent variable. Expert Systems with Applications. 2019. Vol. 127. P. 157–166. DOI: 10.1016/j.eswa.2019.03.014.

Qiao W., Liu Y., Ma X., Liu Y. Human Factors Analysis for Maritime Accidents Based on a Dynamic Fuzzy Bayesian Network. Risk analysis. 2020. Vol. 40, no. 5. P. 957–980. DOI: 10.1111/risa.13444.

Khlobystova A.O., Abramov M.V., Tulupyev A.L. An Approach to Estimating of Criticality of Social Engineering Attacks Traces. International Conference on Information Technologies, Saratov, February 7–8, 2019. Vol. 199. Springer. 2019. P. 446–456. DOI: 10.1007/978-3-030-12072-6_36.

Korepanova A.A., Abramov M.V., Tulupyeva T.V. Identification of User Accounts in the Social Networks “VKontakte” and “Odnoklassniki”. Seventeenth Russian Conference on Artificial Intelligence RCAI-2019: collection of scientific papers, Ulyanovsk, October 21–25, 2019. Vol. 2. 2019. P. 153–163. (in Russian).

Tulupyev A.L., Nikolenko S.I., Sirotkin A.V. Bayesian Networks: a Logical and Probabilistic Approach. SPb.: Nauka, 2006. 607 p. (in Russian).

Tulupyev A.L. Algebraic Bayesian Networks: Global Logical and Probabilistic Inference in Joint Trees. SPb.: Anatolia Publishing House LLC, 2007. 40 p. Elements of Soft Computing. (in Russian).

Filchenkov A.A. Minimal join graph set synthesis self-managed possession cliques algorithm. Informatics and Automation. 2010. No. 14. P. 150–169. (in Russian) DOI: 10.15622/sp.14.9.

Filchenkov A.A. Minimal join graph set synthesis proprietor possession cliques algorithm. Informatics and Automation. 2010. No. 15. P. 193–212. (in Russian) DOI: 10.15622/sp.15.10.

Filchenkov A.A., Tulupyev A.L. The Algebraic Bayesian Network Tertiary Structure. Informatics and Automation. 2011. No. 18. P. 164–187. (in Russian) DOI: 10.15622/sp.18.7.

Frolenkov K.V., Filchenkov A.A., Tulupyev A.L. Posteriori inference in tertiary polystructure of an algebraic Bayesian network. Informatics and Automation. 2012. No. 23. P. 343–356. (in Russian) DOI: 10.15622/sp.23.17.

Kabir S., Papadopoulos Y. Applications of Bayesian networks and Petri nets in safety, reliability, and risk assessments: A review. Safety Science. 2019. Vol. 115. P. 154–175. DOI: 10.1016/j.ssci.2019.02.009.

Amin M.T., Khan F., Ahmed S., Imtiaz S. A data-driven Bayesian network learning method for process fault diagnosis. Process Safety and Environmental Protection. 2021. Vol. 150. P. 110–122. DOI: 10.1016/j.psep.2021.04.004.

Baksh A.-A., Abbassi R., Garaniya V., Khan F. Marine transportation risk assessment using Bayesian Network: Application to Arctic waters. Ocean Engineering. 2018. Vol. 159. P. 422–436. DOI: 10.1016/j.oceaneng.2018.04.024.

Cai B., Kong X., Liu Y., et al. Application of Bayesian Networks in Reliability Evaluation. IEEE Transactions on Industrial Informatics. 2019. Vol. 15, no. 4. P. 2146–2157. DOI: 10.1109/TII.2018.2858281.

Wang Z., Chen C. Fuzzy comprehensive Bayesian network-based safety risk assessment for metro construction projects. Tunnelling and Underground Space Technology. 2017. Vol. 70. P. 330–342. DOI: 10.1016/j.tust.2017.09.012.

Tavana M., Abtahi A.-R., Caprio D.D., Poortarigh M. An Artificial Neural Network and Bayesian Network model for liquidity risk assessment in banking. Neurocomputing. 2018. Vol. 275. P. 2525–2554. DOI: 10.1016/j.neucom.2017.11.034.

Chaturvedi I., Ragusa E., Gastaldo P., et al. Bayesian network based extreme learning machine for subjectivity detection. Journal of the Franklin Institute. 2018. Vol. 355, no. 4. P. 1780–1797. DOI: 10.1016/j.jfranklin.2017.06.007.

Ruz G.A., Henríquez P.A., Mascareño A. Sentiment analysis of Twitter data during critical events through Bayesian networks classifiers. Future Generation Computer Systems. 2020. Vol. 106. P. 92–104. DOI: 10.1016/j.future.2020.01.005.

Mohammadfam I., Ghasemi F., Kalatpour O., Moghimbeigi A. Constructing a Bayesian network model for improving safety behavior of employees at workplaces. Applied Ergonomics. 2017. Vol. 58. P. 35–47. DOI: 10.1016/j.apergo.2016.05.006.

Sierra L.A., Yepes V., García-Segura T., Pellicer E. Bayesian network method for decisionmaking about the social sustainability of infrastructure projects. Journal of Cleaner Production. 2018. Vol. 176. P. 521–534. DOI: 10.1016/j.jclepro.2017.12.140.

McLachlan S., Dube K., Hitman G.A., et al. Bayesian networks in healthcare: Distribution by medical condition. Artificial Intelligence in Medicine. 2020. Vol. 107. P. 101912. DOI: 10.1016/j.artmed.2020.101912.

Sperotto A., Molina J.-L., Torresan S., et al. Reviewing Bayesian Networks potentials for climate change impacts assessment and management: A multi-risk perspective. Journal of Environmental Management. 2017. Vol. 202. P. 320–331. DOI: 10.1016/j.jenvman.2017.07.044.

Afenyo M., Khan F., Veitch B., Yang M. Arctic shipping accident scenario analysis using Bayesian Network approach. Ocean Engineering. 2017. Vol. 133. P. 224–230. DOI: 10.1016/j.oceaneng.2017.02.002.

Wu J., Zhou R., Xu S.,Wu Z. Probabilistic analysis of natural gas pipeline network accident based on Bayesian network. Journal of Loss Prevention in the Process Industries. 2017. Vol. 46. P. 126–136. DOI: 10.1016/j.jlp.2017.01.025.

Tulupyev A.L. Algebraic Bayesian Networks: Local Logical and Probabilistic Inference. SPb.: Anatolia Publishing House LLC, 2007. 80 p. (in Russian).

Tulupyev A.L. Bayesian Networks: Logic-probabilistic Inference in Cycles. SPb.: St. Petersburg University Press, 2008. 140 p. Elements of Soft Computing. (in Russian).

Filchenkov A.A., Frolenkov K.V., Sirotkin A.V., Tulupyev A.L. Minimal join graph subsets synthesis system. Informatics and Automation. 2013. No. 27. P. 200–244. (in Russian) DOI: 10.15622/sp.27.17.

Filchenkov A.A., Tulupyev A.L. Algorithm for detection of algebraic Bayesian network primary structure acyclicity based on its quaternary structure. Informatics and Automation. 2011. No. 19. P. 128–145. (in Russian) DOI: 10.15622/sp.19.7.

Filchenkov A.A., Tulupyev A.L. Connectivity and Acyclicity of the Primary Structure of an Algebraic Bayesian Network. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy. 2013. No. 1. P. 110–119. (in Russian).

Filchenkov A.A., Tulupyev A.L. Minimal joint graph structure synthesis. Informatics and Automation. 2009. No. 11. P. 104–129. (in Russian) DOI: 10.15622/sp.11.6.

Sirotkin A.V., Tulupyev A.L. Knowledge and reasoning with uncertainty modeling: matrix-and-vector calculus for local reconciliation of truth estimates. Informatics and Automation. 2011. No. 18. P. 108–135. (in Russian) DOI: 10.15622/sp.18.5.

Filchenkov A.A., Tulupyev A.L. Algorithm for Detection Algebraic Bayesian Network Primary Structure Acyclicity Based on Number of Minimal Join Graph Edges Estimating. Informatics and Automation. 2012. No. 22. P. 205–223. (in Russian) DOI: 10.15622/sp.22.11.

Tulupyev A.L., Sirotkin A.V. Local Posterior Inference in Algebraic Bayesian Networks as a System of Matrix-and-vector Operations. Integrated Models and Soft Computing in Artificial Intelligence. V-th International Scientific and Practical Conference, September 9–12, 2009. Collection of scientific works. In 2 vols. Vol. 1. SPb.: Nauka, 2012. P. 425–434. (in Russian).

Aho A., Garey M., Ullman J. The Transitive Reduction of a Directed Graph. SIAM Journal on Computing. 1972. Vol. 1, no. 2. P. 131–137. DOI: 10.1137/0201008.

Tulupyev A.L., Sirotkin A.V., Nikolenko S.I. Bayesian Belief Networks: Logical and Probabilistic Inference in Acyclic Directed Graphs. SPb.: St. Petersburg University Press, 2009. 400 p. (in Russian).

Web application for algebraic Bayesian networks. URL: https://abn.dscs.pro/ (accessed: 09.03.2023).

Automated ABN algorithms using tertiary structure, in particular – global a posterior inference. URL: https://abn.dscs.pro/parent_separators_graph (accessed: 09.03.2023).

Automated ABN algorithms working with the primary structure, in particular – check acyclicity. URL: https://abn.dscs.pro/primary_structure (accessed: 09.03.2023).




DOI: http://dx.doi.org/10.14529/cmse230104