Байесовская сеть

Байесовская сеть (или байесова сеть, байесовская сеть доверия, англ. Bayesian network, belief network) — графовая вероятностная модель, представляющая собой множество переменных и их вероятностных зависимостей по Байесу. Например, байесовская сеть может быть использована для вычисления вероятности того, чем болен пациент, по наличию или отсутствию ряда симптомов, основываясь на данных о зависимости между симптомами и болезнями. Математический аппарат байесовых сетей создан американским учёным Джудой Перлом, лауреатом Премии Тьюринга (2011).

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

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

Если из вершины $A$ выходит дуга в вершину $B$, то $A$ называют родителем $B$, а $B$ называют потомком $A$. Если из вершины $A$ существует ориентированный путь в вершину $B$, то $A$ называется предком $B$, а $B$ называется потомком $A$.

Множество вершин-родителей вершины $V_{i}$ обозначим как $\mathrm {parents} (V_{i})=\mathbf {PA} _{i}$.

Направленный ациклический граф $G$ называется байесовской сетью для вероятностного распределения $P(\mathbf {v} )$, заданного над множеством случайных переменных $\mathbf {V}$, если каждой вершине графа поставлена в соответствие случайная переменная из $\mathbf {V}$, а дуги в графе удовлетворяют условию (марковское условие): любая переменная $V_{i}$ из $\mathbf {V}$ должна быть условно независима от всех вершин, не являющихся её потомками, если заданы (получили означивание, обусловлены) все её прямые родители $\mathbf {PA} _{i}$ в графе $G$, то есть

$\forall V_{i}\in \mathbf {V}$справедливо:$P(v_{i}\mid \mathbf {pa} _{i},\mathbf {s} )=P(v_{i}\mid \mathbf {pa} _{i}),$

где $v_{i}$ — значение $V_{i}$; $\mathbf {s}$ — конфигурация^{[уточнить]} $\mathbf {S}$; $\mathbf {S}$ — множество всех вершин, не являющихся потомками $V_{i}$; $\mathbf {pa} _{i}$ — конфигурация $\mathbf {PA} _{i}$.

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

$\mathrm {P} (V_{1},\ldots ,V_{n})=\prod _{i=1}^{n}\mathrm {P} (V_{i}\mid \operatorname {parents} (V_{i})).$

Если у вершины $V_{i}$ нет предков, то её локальное распределение вероятностей называют безусловным, иначе условным. Если вершина — случайная переменная получила означивание (например, в результате наблюдения), то такое означивание называют свидетельством (англ. evidence). Если значение переменной было установлено извне (а не наблюдалось), то такое означивание называется вмешательством (англ. action) или интервенцией (англ. intervention).

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

d-разделённость

Путь $p$ называют d-разделённым (англ. d-separated), или блокированным (англ. blocked) множеством вершин $Z$ тогда и только тогда, когда

1. $p$ содержит цепь $i\to m\to j$ или разветвление $i\gets m\to j$ такие, что $m$ принадлежит $Z$, или
2. $p$ содержит инвертированное разветвление (коллайдер) $i\to m\gets j$, такое, что $m$ не принадлежит $Z$ и у вершины $m$ нет потомков, которые принадлежат $Z$.

Пусть $X,Y,Z$ — непересекающиеся подмножества вершин в ацикличном ориентированном графе $G$. Говорят, что множество вершин $Z$ d-разделяет $X$ и $Y$ тогда и только тогда, когда $Z$ блокирует все пути из любой вершины, принадлежащей $X$ в любую вершину, принадлежащую $Y$, и обозначают $(\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{G}$. Под путём понимается последовательность следующих друг за другом рёбер (любого направления) в графе.

Теорема о d-разделённости

Для любых трёх непересекающихся подмножеств вершин $(X,Y,Z)$ в ацикличном ориентированном графе $G$ и для всех вероятностных распределений $P$ справедливо:

1. если $(\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{G}$, то $(\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{P}$, если $G$ и $P$ марковски совместимы, и
2. если отношение условной независимости $(\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{P}$ выполняется для всех вероятностных распределений, Марковски-совместимых с $G$, то из этого следует $(\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{G}$.

Другими словами, если вершины d-разделены, то они условно независимы; и если вершины условно-независимы во всех вероятностных распределениях, совместимых с графом $G$, то они d-разделены.

($(\langle X\perp \!\!\!\perp Y\mid Z\rangle )_{P}$ означает, что множества переменных $X$ и $Y$ условно-независимы при заданном множестве $Z$.)

Свидетельства

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

Вероятностные запросы

Байесовская сеть позволяет получить ответы на следующие типы вероятностных запросов:

• нахождение вероятности свидетельства,
• определение априорных маргинальных вероятностей,
• определение апостериорных маргинальных вероятностей, включая:

прогнозирование, или прямой вывод, — определение вероятности события при наблюдаемых причинах,

диагностирование, или обратный вывод (абдукция), — определение вероятности причины при наблюдаемых следствиях,

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

• вычисление наиболее вероятного объяснения наблюдаемого события (англ. most probable explanation, MPE),
• вычисление апостериорного максимума (англ. maximum a-posteriori, MAP).

Пример

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

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

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

$\mathrm {P} (G,S,R)=\mathrm {P} (G\mid S,R)\cdot \mathrm {P} (S\mid R)\cdot \mathrm {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\%.$

Вероятностный вывод

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

Для проведения вероятностного вывода в байесовских сетях используются следующие алгоритмы:

• Точные:
  • вывод методом грубой силы путём маргинализации полного совместного распределения;
  • алгоритмы устранения переменных и символьные вычисления,
  • кластеризация,
  • алгоритмы пропагации (передача) сообщений между узлами сети,
• Приближённые на основе метода Монте-Карло:
  • алгоритмы формирования выборок с исключением,
  • метод оценки выборок с учётом правдоподобия,
  • алгоритм МСМС (англ. Markov chain Monte Carlo) и др.

Приложения

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

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

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

Бесплатные и свободные программные продукты

• OpenBayes https://github.com/abyssknight/OpenBayes-Fork (contains a patched build of OpenBayes from openbayes.org)
• RISO: http://sourceforge.net/projects/riso/ Архивная копия от 4 марта 2007 на Wayback Machine (distributed belief networks)
• BANSY3 Архивная копия от 20 июля 2011 на Wayback Machine — Freeware. From the Non Linear Dynamics Laboratory. Mathematics Department, Science School, UNAM.
• SamIam: http://reasoning.cs.ucla.edu/samiam Архивная копия от 24 апреля 2007 на Wayback Machine

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

• AgenaRisk Bayesian network tool: http://www.agenarisk.com Архивная копия от 16 марта 2022 на Wayback Machine
• BayesFusion (GeNIe и SMILE): https://www.bayesfusion.com/ Архивная копия от 29 ноября 2018 на Wayback Machine
• Bayesian network application library: http://www.norsys.com/netlibrary/index.htm Архивная копия от 11 июня 2007 на Wayback Machine
• Bayesia: http://www.bayesia.com Архивная копия от 8 марта 2022 на Wayback Machine
• Hugin: http://www.hugin.com Архивная копия от 30 мая 2020 на Wayback Machine
• Netica: http://www.norsys.com Архивная копия от 20 мая 2007 на Wayback Machine
• BNet: http://www.cra.com/bnet Архивная копия от 5 июля 2008 на Wayback Machine
• Dezide: http://www.dezide.com Архивная копия от 8 марта 2022 на Wayback Machine
• MSBNx: a component-centric toolkit for modeling and inference with Bayesian Network (from Microsoft Research): https://www.microsoft.com/en-us/download/details.aspx?id=52299 Архивная копия от 29 ноября 2018 на Wayback Machine
• Bayes Net Toolbox for Matlab: http://bnt.sourceforge.net/ Архивная копия от 10 мая 2007 на Wayback Machine
• dVelox: http://www.apara.es/en/about-apara-predictive-analytics Архивная копия от 29 ноября 2018 на Wayback Machine
• SIAM & Causeway: https://web.archive.org/web/20070221060515/http://www.inet.saic.com/

См. также

• Теорема Байеса
• Байесовская вероятность
• Байесовское программирование

Ссылки

• Jensen, Finn V. 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 Архивная копия от 27 сентября 2007 на Wayback Machine
• 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://web.archive.org/web/20070927153751/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.
• Pearl, Judea. Probabilistic Reasoning in Intelligent Systems (англ.). — Morgan Kaufmann, 1988. — ISBN 0-934613-73-7.
• Judea Pearl. Causality. 2000.
• J.W. Comley and D.L. Dowe Архивная копия от 12 февраля 2006 на Wayback Machine, «Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages Архивная копия от 4 августа 2016 на Wayback Machine», chapter 11 (pp265 Архивная копия от 27 сентября 2016 на Wayback Machine—294 Архивная копия от 27 сентября 2016 на Wayback Machine) in P. Grunwald, M.A. Pitt and I.J. Myung (eds)., Advances in Minimum Description Length: Theory and Applications Архивная копия от 19 июня 2006 на Wayback Machine, 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 Архивная копия от 9 февраля 2006 на Wayback Machine (MML). An earlier version is Comley and Dowe (2003) Архивная копия от 4 августа 2016 на Wayback Machine, .pdf Архивная копия от 10 февраля 2006 на Wayback Machine.)
• Christian Borgelt and Rudolf Kruse. Graphical Models — Methods for Data Analysis and Mining Архивная копия от 10 июня 2007 на Wayback Machine, Chichester, UK: Wiley, 2002, ISBN 0-470-84337-3
• Korb, Kevin B.; Ann E Nicholson. Bayesian Artificial Intelligence (англ.). — CRC Press, 2004. — ISBN 1-58488-387-1. Архивная копия от 10 апреля 2007 на Wayback Machine
• Nevin Lianwen Zhang Архивная копия от 7 июня 2007 на Wayback Machine and David Poole Архивная копия от 10 июня 2007 на Wayback Machine, A simple approach to Bayesian network computations Архивная копия от 17 апреля 2007 на Wayback Machine, 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 Архивная копия от 30 мая 2007 на Wayback Machine, A Tutorial on Learning with Bayesian Networks Архивная копия от 19 июля 2006 на Wayback Machine. 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.