Байесовская сеть: различия между версиями

239 байт добавлено ,  1 год назад
стилевые правки
(стилевые правки)
 
== Определения и принципы работы ==
Если из вершины ''<math>A''</math> выходит дуга в вершину ''<math>B''</math>, то ''<math>A''</math> называют ''родителем'' ''<math>B''</math>, а ''<math>B''</math> называют ''потомком'' ''<math>A''</math>. Если из вершины ''<math>A''</math> существует ориентированный путь в вершину ''<math>B''</math>, то ''<math>A''</math> называется ''предком'' ''<math>B''</math>, а ''<math>B''</math> называется ''потомком'' ''<math>A''</math>.
Множество вершин-родителей вершины ''V''<sub>i</sub> обозначим как parents(''V''<sub>i</sub>) = '''PA'''<sub>''i''</sub>.
 
Множество вершин-родителей вершины ''V''<submath>iV_i</submath> обозначим как <math>\mathrm{parents}(''V''<sub>i</sub>V_i) = '''\mathbf{PA'''<sub>''i''}_i</submath>.
[[Направленный ациклический граф]] G называется ''байесовской сетью'' для вероятностного распределения P('''v'''), заданного над множеством случайных переменных '''V''', если каждой вершине графа поставлена в соответствие случайная переменная из '''V''', а дуги в графе удовлетворяют условию (марковское условие<ref name="Pearl2009" />): любая переменная ''V''<sub>''i''</sub> из '''V''' должна быть условно независима от всех вершин, не являющихся её потомками, если заданы (получили означивание, обусловлены) все её прямые родители '''PA'''<sub>''i''</sub> в графе G, то есть
 
[[Направленный ациклический граф]] <math>G</math> называется ''байесовской сетью'' для вероятностного распределения <math>P('''\mathbf{v'''})</math>, заданного над множеством случайных переменных '''<math>\mathbf{V'''}</math>, если каждой вершине графа поставлена в соответствие случайная переменная из '''<math>\mathbf{V'''}</math>, а дуги в графе удовлетворяют условию (марковское условие<ref name="Pearl2009" />): любая переменная ''V''<submath>''i''V_i</submath> из '''<math>\mathbf{V'''}</math> должна быть условно независима от всех вершин, не являющихся её потомками, если заданы (получили означивание, обусловлены) все её прямые родители '''PA'''<submath>''i''\mathbf{PA}_i</submath> в графе <math>G</math>, то есть
∀''V''<sub>''i''</sub> ∈ '''V''' справедливо: P(''v''<sub>''i''</sub>│'''pa'''<sub>''i''</sub>,'''s''') = P(''v''<sub>''i''</sub>│'''pa'''<sub>''i''</sub>),
 
<math>\forall V_i\in \mathbf{V}</math>справедливо:<math>P(v_i\mid \mathbf{pa}_i, \mathbf{s}) = P(v_i\mid \mathbf{pa}_i),</math>
где ''v''<sub>''i''</sub> — значение ''V''<sub>''i''</sub>; '''s''' — конфигурация{{уточнить}} '''S'''; '''S''' — множество всех вершин, не являющихся потомками ''V''<sub>''i''</sub>; '''pa'''<sub>''i''</sub> — конфигурация '''PA'''<sub>''i''</sub>.
 
где ''v''<submath>''i''v_i</submath> — значение ''V''<submath>''i''V_i</submath>; '''<math>\mathbf{s'''}</math> — конфигурация{{уточнить}} '''<math>\mathbf{S'''}</math>; '''<math>\mathbf{S'''}</math> — множество всех вершин, не являющихся потомками ''V''<submath>''i''V_i</submath>; '''pa'''<submath>''i''\mathbf{pa}_i</submath> — конфигурация '''PA'''<submath>''i''\mathbf{PA}_i</submath>.
 
Тогда полное совместное распределение значений в вершинах можно удобно записать в виде декомпозиции (произведения) локальных распределений:
: <math>\mathrm P(V_1, \ldots, V_n) = \prod_{i=1}^n \mathrm P(V_i \mid \operatorname{parents}(V_i)).</math>
 
Если у вершины ''V''<submath>''i''V_i</submath> нет предков, то её локальное распределение вероятностей называют ''безусловным'', иначе ''условным''. Если вершина — случайная переменная получила означивание (например, в результате наблюдения), то такое означивание называют ''свидетельством'' ({{lang-en|evidence}}). Если значение переменной было установлено извне (а не наблюдалось), то такое означивание называется ''вмешательством'' ({{lang-en|action}}) или ''интервенцией'' ({{lang-en|intervention}})<ref name="Pearl2009" />.
 
''[[Условная независимость]]'' в байесовской сети представлена графическим свойством ''d-разделённости''.
=== d-разделённость ===
Путь <math>p</math> называют ''d-разделённым'' ({{lang-en|d-separated}}), или ''блокированным'' ({{lang-en|blocked}}) множеством вершин <math>Z</math> тогда и только тогда, когда
# <math>p</math> содержит ''цепь'' <math>i</math>\to → <math>m</math>\to → <math>j</math> или ''разветвление'' <math>i</math>\gets ← <math>m</math> \to <math>j</math> такие, что <math>m</math> принадлежит <math>Z</math>, или
# <math>p</math> содержит ''инвертированное разветвление (коллайдер)'' <math>i</math>\to → <math>m</math> ←\gets <math>j</math>, такое, что <math>m</math> не принадлежит <math>Z</math> и у вершины <math>m</math> нет потомков, которые принадлежат <math>Z</math>.
Пусть <math>X, Y, Z</math> — непересекающиеся подмножества вершин в ацикличном ориентированном графе <math>G</math>. Говорят, что множество вершин <math>Z</math> d-разделяет <math>X</math> и <math>Y</math> тогда и только тогда, когда <math>Z</math> блокирует все пути из любой вершины, принадлежащей <math>X</math> в любую вершину, принадлежащую <math>Y</math>, и обозначают <math>(<\langle X \perp\!\!\!\perp Y|\mid Z>\rangle)_G</math>. Под путём понимается последовательность следующих друг за другом рёбер (любого направления) в графе<ref name="Pearl2009">{{книга
|автор = Judea Pearl.
|заглавие = Causality: Models, Reasoning, and Inference. — 2-nd Edition
=== Теорема о d-разделённости ===
Для любых трёх непересекающихся подмножеств вершин <math>(X, Y, Z)</math> в ацикличном ориентированном графе <math>G</math> и для всех вероятностных распределений <math>P</math> справедливо:
# если <math>(<\langle X \perp\!\!\!\perp Y|\mid Z>\rangle)_G</math>, то <math>(<\langle X \perp\!\!\!\perp Y|\mid Z>\rangle)_P</math>, если <math>G</math> и <math>P</math> марковски совместимы, и
# если отношение условной независимости <math>(<\langle X \perp\!\!\!\perp Y|\mid Z>\rangle)_P</math> выполняется для всех вероятностных распределений, Марковски-совместимых с <math>G</math>, то из этого следует <math>(<\langle X \perp\!\!\!\perp Y|\mid Z>\rangle)_G</math>.
Другими словами, если вершины d-разделены, то они условно независимы; и если вершины условно-независимы во всех вероятностных распределениях, совместимых с графом ''<math>G''</math>, то они d-разделены<ref name="Pearl2009" />.
 
(<math>(<\langle X \perp\!\!\!\perp Y|\mid Z>\rangle)_P</math> означает, что множества переменных <math>X</math> и <math>Y</math> условно-независимы при заданном множестве <math>Z</math>.)
 
=== Свидетельства ===
Совместная вероятность функции:
 
<math>\mathrm P(G,S,R)=\mathrm P(G|\mid S,R)\cdot \mathrm P(S|\mid R)\cdot \mathrm P(R)</math>
 
где имена трёх переменных означают ''G = Трава мокрая (Grass wet)'', ''S = Дождевальная установка (Sprinkler)'', и ''R = Дождь (Rain)''.