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

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

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

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

Определения

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

Направленный ациклический граф G называется байесовской сетью для вероятностного распределения P(v), заданного над множеством случайных переменных V, если каждой вершине графа поставлена в соответствие случайная переменная из V, а дуги в графе удовлетворяют условию (марковское условие): любая переменная V_i из V должна быть условно независима от всех вершин, не являющихся её потомками, если заданы (получили означивание, обусловлены) все её прямые родители PA_i в графе G, то есть

∀V_i ∈ V справедливо: P(v_i│pa_i,s) = P(v_i│pa_i),

где v_i — значение V_i; s — конфигурация S; S — множество всех вершин, не являющихся потомками V_i; pa_i — конфигурация PA_i.

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

[math]\displaystyle{ \mathrm P(V_1, \ldots, V_n) = \prod_{i=1}^n \mathrm P(V_i \mid \operatorname{parents}(V_i)). }[/math]

Если у вершины V_i нет предков, то её локальное распределение вероятностей называют безусловным, иначе условным. Если вершина — случайная переменная получила означивание (например, в результате наблюдения), то такое означивание называют свидетельством. Если значение переменной было установлено извне (а не наблюдалось), то такое означивание называется вмешательством или интервенцией.

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

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

Путь [math]\displaystyle{ p }[/math] называют d-разделённым, или блокированным множеством вершин [math]\displaystyle{ Z }[/math] тогда и только тогда, когда

1. [math]\displaystyle{ p }[/math] содержит цепь [math]\displaystyle{ i }[/math] → [math]\displaystyle{ m }[/math] → [math]\displaystyle{ j }[/math] или разветвление [math]\displaystyle{ i }[/math] ← [math]\displaystyle{ m }[/math] → [math]\displaystyle{ j }[/math] такие, что [math]\displaystyle{ m }[/math] принадлежит [math]\displaystyle{ Z }[/math], или
2. [math]\displaystyle{ p }[/math] содержит инвертированное разветвление (коллайдер) [math]\displaystyle{ i }[/math] → [math]\displaystyle{ m }[/math] ← [math]\displaystyle{ j }[/math], такое, что [math]\displaystyle{ m }[/math] не принадлежит [math]\displaystyle{ Z }[/math] и у вершины [math]\displaystyle{ m }[/math] нет потомков, которые принадлежат [math]\displaystyle{ Z }[/math].

Пусть [math]\displaystyle{ X, Y, Z }[/math] — не пересекающиеся подмножества вершин в ацикличном ориентированном графе [math]\displaystyle{ G }[/math]. Говорят, что множество вершин [math]\displaystyle{ Z }[/math] d-разделяет [math]\displaystyle{ X }[/math] и [math]\displaystyle{ Y }[/math] тогда и только тогда, когда [math]\displaystyle{ Z }[/math] блокирует все пути из любой вершины, принадлежащей [math]\displaystyle{ X }[/math] в любую вершину, принадлежащую [math]\displaystyle{ Y }[/math], и обозначают [math]\displaystyle{ (\lt X \perp\!\!\!\perp Y|Z\gt )_G }[/math]. Под путём понимается последовательность следующих друг за другом рёбер (любого направления) в графе.

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

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

1. если [math]\displaystyle{ (\lt X \perp\!\!\!\perp Y|Z\gt )_G }[/math], то [math]\displaystyle{ (\lt X \perp\!\!\!\perp Y|Z\gt )_P }[/math], если [math]\displaystyle{ G }[/math] и [math]\displaystyle{ P }[/math] марковски совместимы, и
2. если отношение условной независимости [math]\displaystyle{ (\lt X \perp\!\!\!\perp Y|Z\gt )_P }[/math] выполняется для всех вероятностных распределений, Марковски-совместимых с [math]\displaystyle{ G }[/math], то из этого следует [math]\displaystyle{ (\lt X \perp\!\!\!\perp Y|Z\gt )_G }[/math].

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

([math]\displaystyle{ (\lt X \perp\!\!\!\perp Y|Z\gt )_P }[/math] означает, что множества переменных [math]\displaystyle{ X }[/math] и [math]\displaystyle{ Y }[/math] условно-независимы при заданном множестве [math]\displaystyle{ Z }[/math].)

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

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

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

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

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

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

• вычисление наиболее вероятного объяснения наблюдаемого события,
• вычисление апостериорного максимума.