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


УДК004.8

МАТРИЧНО-ВЕКТОРНЫЕ АЛГОРИТМЫ НОРМИРОВКИ ДЛЯ ЛОКАЛЬНОГО АПОСТЕРИОРНОГО ВЫВОДА В АЛГЕБРАИЧЕСКИХ БАЙЕСОВСКИХ СЕТЯХ

Золотин А.А., Тулупьев А.Л., Сироткин А.В.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования: Золотин А.А., Тулупьев А.Л., Сироткин А.В. Матрично-векторные алгоритмы нормировки для локального апостериорного вывода в алгебраических байесовских сетях // Научно-технический вестник информационных технологий, механики и оптики. 2015. Том 15. № 1. С. 78–85

Аннотация

Рассматривается задача описания локального апостериорного вывода в алгебраических байесовских сетях, являющихся одним из классов вероятностных графических моделей, с помощью матрично-векторных уравнений. Такие уравнения, в основном, были описаны в предыдущих работах, однако содержали нормирующие множители, вычисления которых использовали алгоритмическую компоненту, не получившую искомой интерпретации на матрично-векторном языке. Для устранения указанного недостатка нормирующие множители сначала были представлены в форме скалярного произведения. Удалось показать, что одна из компонент в каждом скалярном произведении выражается как степень Кронекера фиксированного вектора размерности два. За счет переноса транспонированной матрицы-оператора ненормированного апостериорного вывода внутри скалярного произведения было получено разложение одного из множителей в виде последовательности тензорных произведений векторов размерности два, причем такие векторы могут принимать лишь два значения в одном случае и три – в другом. Выбор указанных значений определяется структурой поступившего свидетельства. Второй компонентой скалярного произведения становятся векторы с исходными данными. Вычислительные эксперименты позволили построить соответствующие векторы, примеры некоторых из них приведены в работе. Описание в виде матрично-векторных уравнений локального апостериорного вывода упрощает разработку спецификации алгоритмов локального апостериорного вывода, обоснование их корректности и последующую реализацию с применением уже существующих библиотек. Также такие уравнения позволяют применить классические математические техники для анализа полученных результатов. Полученные результаты делают возможным использование метода отложенных вычислений: не формировать для проведения вычислений векторы большой размерности, а вычислять их компоненты за счет применения побитовых операций по мере надобности. 


Ключевые слова: байесовские сети, апостериорный вывод, алгоритмы вывода, отложенные вычисления, побитовые операции

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

Список литературы

1. Городецкий В.И. Алгебраические байесовские сети – новая парадигма экспертных систем // Юбилей- ный сборник трудов отделения информатики, вычислительной техники и автоматизации РАН. Т. 2. М.: РАН, 1993. С. 120–141.

2. Городецкий В.И., Тулупьев А.Л. Формирование непротиворечивых баз знаний с неопределенностью // Изв. РАН. Сер. Теория и системы управления. 1997. Т. 36. № 5. C. 33–42.

3. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.

4. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: СПбГУ, 2009. 400 c.

5. Bobadilla J., Ortega F., Hernando A., Gutierrez A. Recommender systems survey // Knowledge-Based Systems. 2013. V. 46. P. 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. V. 41. N 16. P. 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. V. 36. P. 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. V. 50. P. 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. V. 7. N 5. P. 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. V. 25. N 4. P. 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. V. 70. P. 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. V. 56. N 1. P. 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. V. 96. N 8. P. 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. V. 41. N 16. P. 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 modelling // Environmental Modelling and Software. 2013. V. 46. P. 1–11. doi: 10.1016/j.envsoft.2013.03.011

16. Тулупьев А.Л., Сироткин А.В. Алгебраические байесовские сети: принцип декомпозиции и логико- вероятностный вывод в условиях неопределенности // Информационно-измерительные и управляю- щие системы. 2008. Т. 6. № 10. С. 85–87.

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

18. Schippers M. Probabilistic measures of coherence: from adequacy constraints towards pluralism // Synthese. 2014. V. 191. N 16. P. 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. V. 233. P. 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. V. 45. N 2. P. 233–254. doi: 10.1016/j.ijar.2006.06.009 .А. Золотин, А.Л. Тулупьев, А.В. Сироткин  85

21. Тулупьев А.Л. Апостериорные оценки вероятностей в алгебраических байесовских сетях // Вестник Санкт-Петербургского университета. Серия 10: Прикладная математика. Информатика. Процессы управления. 2012. № 2. С. 51–59.

22. Тулупьев А.Л., Сироткин А.В. Матричные уравнения локального логико-вероятностного вывода оце- нок истинности элементов в алгебраических байесовских сетях // Вестник Санкт-Петербургского университета. Серия 1: Математика. Механика. Астрономия. 2012. № 3. С. 63–72.

23. Беллман Р. Введение в теорию матриц. М.: Наука, 1969. 375 с

. 24. Сироткин А.В. Алгебраические байесовские сети: вычислительная сложность алгоритмов логико- вероятностного вывода в условиях неопределенности. Дисс. … канд. физ.-мат. наук. СПб.: СПбГУ, 2011. 218 с. 



Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2019 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

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