Байесовская сеть доверия

Байесовская сеть доверия

Байесовская сеть (или Байесовская сеть доверия) — это вероятностная модель, представляющая собой множество переменных и их вероятностных зависимостей. Например, байесовская сеть может быть использована для вычисления вероятности того, чем болен пациент по наличию или отсутствию ряда симптомов, основываясь на данных о зависимости между симптомами и болезнями.

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

Определения и принципы работы

Если ребро выходит из вершины A в вершину B, то A называют родителем B, а B называют потомком A. Множество вершин-предков вершины X_i обозначим как parents(X_i). Совместное распределение значений в вершинах можно удобно расписать как результат локальных распределений в каждом узле и его предках:

$\mathrm P(X_1, \ldots, X_n) = \prod_{i=1}^n \mathrm P(X_i \mid \operatorname{parents}(X_i)).\,$

Если у вершины X_i нет предков, то его локальное распределение вероятностей называют безусловным, иначе условным. Если значение в узле получено в результате опыта, то вершину называют свидетелем.

Семантика зависимостей

Граф кодирует зависимости между переменными. Условная независимость представлена графическим свойством d-разделенности.

Два узла направленного графа x и y называются d-разделенными, если для всякого пути из x в y (здесь не учитывается направление ребер) существует такой промежуточный узел z (не совпадающий ни с x, ни с y), что либо связь в пути в этом узле последовательная или расходящаяся, и узел z получил означивание, либо связь сходящаяся, и ни узел z, ни какой-либо из его потомков означивания не получил. В противном случае узлы называются d-связанными.

Свидетельства — утверждения вида «событие в узле x произошло». Например: «Компьютер не загружается».

Пример

Простая Байесовская сеть.

Предположим, что может быть две причины, по которым трава может стать мокрой (GRASS WET): сработала дождевальная установка, либо прошел дождь. Также предположим, что дождь влияет на работу дождевальной машины (во время дождя установка не включается). Тогда ситуация может быть смоделирована проиллюстрированной Байесовской сетью. Все три переменные могут принимать два возможных значения: T (правда — true) и F (ложь — false).

Совместная вероятность функции:

P(G,S,R) = P(G | S,R)P(S | R)P(R)

где имена трех переменных означают G = Трава мокрая (Grass wet), S = Дождевальная установка (Sprinkler), и R = Дождь (Rain).

Модель может ответить на такие вопросы как «Какова вероятность того, что прошел дождь, если трава мокрая?» используя формулу условной вероятности и суммируя переменные:

$\mathrm P(\mathit{R}=T \mid \mathit{G}=T) =\frac{\mathrm P(\mathit{G}=T,\mathit{R}=T)}{\mathrm P(\mathit{G}=T)} =\frac{\sum_{\mathit{S} \in \{T, F\}}\mathrm P(\mathit{G}=T,\mathit{S},\mathit{R}=T)}{\sum_{\mathit{S}, \mathit{R} \in \{T, F\}} \mathrm P(\mathit{G}=T,\mathit{S},\mathit{R})}$

$= \frac{(0.99 \times 0.01 \times 0.2 = 0.00198_{TTT}) + (0.8 \times 0.99 \times 0.2 = 0.1584_{TFT})}{0.00198_{TTT} + 0.288_{TTF} + 0.1584_{TFT} + 0_{TFF}} \approx 35.77 %.$

Вывод

В силу того, что Байесовская сеть — это полная модель для переменных и их отношений, она может быть использована для того, чтобы давать ответы на вероятностные вопросы. Например, сеть можно использовать чтобы получить новое знание о состоянии подмножества переменных наблюдая за другими переменными (переменные — свидетельства). Это процесс вычисления апостериорного распределения переменных по переменным-свидетельствам называют вероятностным выводом. Это следствие дает нам универсальную оценку для приложений, где нужно выбрать значения подмножества переменных, которое минимизирует функцию потерь, например вероятность ошибочного решения. Байесовская сеть может также считаться механизмом для автоматического построения расширения Теоремы Байеса для более сложных задач.

Приложения

Байесовские сети используются для моделирования в биоинформатике (генетические сети, структура белков), медицине, классификации документов, обработке изображений, обработке данных и системах принятия решений.

См. также

• Теорема Байеса
• Графическая модель
• Машинное обучение

Дополнительная информация

• Association for Uncertainty in Artificial Intelligence: http://www.auai.org/
• Intro to Bayesian networks: http://www.niedermayer.ca/papers/bayesian/bayes.html
• On-line Tutorial on Bayesian nets and probability: http://www.dcs.qmw.ac.uk/%7Enorman/BBNs/BBNs.htm
• Сергей Николенко. Лекции № 8, № 9 и № 10, посвященные байесовским сетям доверия. Курс «Самообучающиеся системы»

Бесплатные и Open-Source продукты

• GeNIe & SMILE: http://genie.sis.pitt.edu
• OpenBayes: http://www.openbayes.org
• RISO: http://sourceforge.net/projects/riso/ (distributed belief networks)
• BANSY3 — Freeware. From the Non Linear Dynamics Laboratory. Mathematics Department, Science School, UNAM.
• SamIam: http://reasoning.cs.ucla.edu/samiam

Коммерческие продукты

• AgenaRisk Bayesian network tool: http://www.agenarisk.com
• Bayesian network application library: http://www.norsys.com/netlibrary/index.htm
• Bayesia: http://www.bayesia.com
• Hugin: http://www.hugin.com
• Netica: http://www.norsys.com
• BNet: http://www.cra.com/bnet
• Dezide: http://www.dezide.com
• MSBNx: a component-centric toolkit for modeling and inference with Bayesian Network (from Microsoft Research): http://research.microsoft.com/adapt/MSBNx/
• Bayes Net Toolbox for Matlab: http://bnt.sourceforge.net/
• dVelox: http://www.aparasw.com/index.php?option=com_content&task=view&id=65&Itemid=102
• SIAM & Causeway: http://www.inet.saic.com/

Ссылки

• Finn V. Jensen Bayesian Networks and Decision Graphs. — Springer, 2001.
• Judea Pearl, Stuart Russell. Bayesian Networks. UCLA Cognitive Systems Laboratory, Technical Report (R-277), November 2000.
• Judea Pearl, Stuart Russell. Bayesian Networks, in M. A. Arbib (Ed.), Handbook of Brain Theory and Neural Networks, pp. 157—160, Cambridge, MA: MIT Press, 2003, ISBN 0-262-01197-2.
• Neil M, Fenton N, Tailor M, «Using Bayesian Networks to model Expected and Unexpected Operational Losses», Risk Analysis: An International Journal, Vol 25(4), 963—972, 2005. http://www.dcs.qmul.ac.uk/~norman/papers/oprisk.pdf
• Enrique Castillo, José Manuel Gutiérrez, and Ali S. Hadi. Expert Systems and Probabilistic Network Models. New York: Springer-Verlag, 1997. ISBN 0-387-94858-9
• Fenton NE and Neil M, «Combining evidence in risk analysis using Bayesian Networks». https://www.dcs.qmul.ac.uk/~norman/papers/Combining%20evidence%20in%20risk%20analysis%20using%20BNs.pdf
• Judea Pearl. Fusion, propagation, and structuring in belief networks. Artificial Intelligence 29(3):241—288, 1986.
• Judea Pearl Probabilistic Reasoning in Intelligent Systems. — Morgan Kaufmann, 1988. — ISBN 0-934613-73-7
• Judea Pearl. Causality. 2000.
• J.W. Comley and D.L. Dowe, «Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages», chapter 11 (pp265—294) in P. Grunwald, M.A. Pitt and I.J. Myung (eds)., Advances in Minimum Description Length: Theory and Applications, Cambridge, MA: MIT Press, April 2005, ISBN 0-262-07262-9. (This paper puts decision trees in internal nodes of Bayes networks using Minimum Message Length (MML). An earlier version is Comley and Dowe (2003), .pdf.)
• Christian Borgelt and Rudolf Kruse. Graphical Models — Methods for Data Analysis and Mining, Chichester, UK: Wiley, 2002, ISBN 0-470-84337-3
• Kevin B. Korb Bayesian Artificial Intelligence. — CRC Press, 2004. — ISBN 1-58488-387-1
• Nevin Lianwen Zhang and David Poole, A simple approach to Bayesian network computations, Proceedings of the Tenth Biennial Canadian Artificial Intelligence Conference (AI-94), Banff, May 1994, 171—178. This paper presents variable elimination for belief networks.
• David Heckerman, A Tutorial on Learning with Bayesian Networks. In Learning in Graphical Models, M. Jordan, ed.. MIT Press, Cambridge, MA, 1999. Also appears as Technical Report MSR-TR-95-06, Microsoft Research, March, 1995. An earlier version appears as Bayesian Networks for Data Mining, Data Mining and Knowledge Discovery, 1:79-119, 1997. The paper is about both parameter and structure learning in Bayesian networks.