Байесовские сети

Определение:

Байесовская сеть (англ. Bayesian network) — это направленный ациклический граф [math]G\ = \lt V, E\gt [/math], в котором каждой вершине [math]v \in V[/math] поставлена в соответствие случайная переменная [math]X_v[/math] и каждое ребро [math](u, v) \in E[/math] представляет прямую зависимость [math]X_v[/math] от [math]X_u[/math]. Пусть [math]parents(v) = {u\ |\ (u,\ v)\ \in\ E}[/math], тогда в Байесовской сети каждой вершине [math]v\ \in\ V[/math] графа должно быть сопоставлено распределение условных вероятностей от вершин из [math]parents(v)[/math].

Цепное правило для Байесовских сетей: [math]\mathrm P(X_1, \ldots, X_n) = \prod_{i=1}^n \mathrm P(X_i \mid \operatorname{parents}(X_i)).[/math] Цепное правило позволяет разложить (факторизовать) совместное распределение в произведение условных распределений.

Пример

Рис. 1: Байесовская сеть "Студент"

Байесовская сеть, представленная на рисунке 1, отображает следующие зависимости. Оценка студента (Grade) зависит от его интеллекта (Intelligence) и сложности курса (Difficulty). Студент просит у преподавателя рекомендательное письмо (Letter), предположим, что преподаватель может написать плохое или хорошее письмо в зависимости от оценки студента. Также студент сдаёт экзамен для поступления в колледж (SAT), результаты экзамена не зависят от письма преподавателя, оценки за его курс и сложности курса. Представление этой модели в Байесовской сети представлено на рисунке ниже.

С помощью цепного правила рассчитаем вероятность того, что умный студент получает B по лёгкому курсу, высокий балл по SAT и плохое рекомендательное письмо: [math] P(i1, d0, g2, s1, l0) = P(i1)P(d0)P(g2 | i1, d0)P(s1 | i1)P(l0 | g2) = 0.3*0.6*0.08*0.8*0.4 = 0.004608. [/math]

Байесовская сеть представляет допустимое вероятностное распределение:

• Вероятность исхода в Байесовской сети неотрицательна, так как вычисляется как произведение условных вероятностей событий, которые неотрицательны.
• Сумма вероятностей исходов в Байесовской сети равна единице:

[math] \sum\limits_{D,I,G,S,L} P(D,I,G,S,L) = \sum\limits_{D,I,G,S,L} P(D)P(I)P(G|I,D)P(S|I)P(L|G) = [/math] [math] \sum\limits_{D,I,G,S} P(D)P(I)P(G|I,D)P(S|I) \sum\limits_{L} P(L|G) = \sum\limits_{D,I,G,S} P(D)P(I)P(G|I,D)P(S|I) = [/math] [math] \sum\limits_{D,I,G} P(D)P(I)P(G|I,D) \sum\limits_{S} P(S|I) = \sum\limits_{D,I,G} P(D)P(I)P(G|I,D) = \ldots [/math]

Виды вероятностного вывода (англ. Reasoning Patterns)

Прямой вывод, или прогнозирование (англ. Causal Reasoning)

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

Пример к рисунку 1: вероятность получения хорошего рекомендательного письма, если известно, что студент обладает низким интеллектом, [math]P(l1 | i0) \approx 0.39[/math], если известно, что курс был лёгким, вероятность повысится, [math]P(l1 | i0, d0) \approx 0.51 [/math].

Обратный вывод, или диагностирование (англ. Evidential Reasoning)

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

Пример к рисунку 1: вероятность того, что курс сложный, если студент получил оценку С, [math]P(d1 | g3) \approx 0.63[/math], вероятность того, что студент умный, если он получил оценку С, [math] P(i1 | g3) \approx 0.08 [/math].

Межпричинный (смешанный) вывод (англ. Intercausal Reasoning)

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

Рассмотрим вероятность из прошлого примера, [math] P(i1 | g3) \approx 0.08 [/math], вероятность того, что студент умный, слегка увеличивается, если также известно, что курс сложный, [math] P(i1 | g3, d1) \approx 0.11 [/math], сложность курса (D) и интеллект студента (I) не связаны ребром, рассмотрим, как получается, что они влияют друг на друга, на более простом примере.

Предположим, у пациента температура, это сильно повышает вероятность как простуды, так и отравления, хотя они не влияют друг на друга, но если станет известно, что пациент отравился, вероятность простуды сильно уменьшится, симптом уже объяснён одной из возможных причин, и вторая становится менее вероятной. Таким образом, если общее следствие получает означивание, причины становятся зависимыми. По-английски этот феномен называется «explaining away».

Пропагация вывода (англ. Flow of Probabilistic Influence)

Обобщим наблюдения из прошлой секции.

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

[math]X[/math] влияет на [math]У[/math], когда свидетельство [math]X[/math] может изменить распределение вероятностей Y.

Рассмотрим случаи, когда [math]X[/math] влияет на [math]У[/math] при имеющихся свидетельствах [math]Z[/math]:

• Если вершины связаны непосредственно ([math]X \rightarrow Y[/math] или [math]X \leftarrow Y[/math]), [math]X[/math] всегда влияет на [math]Y[/math].
• [math]X \rightarrow W \rightarrow Y, X \leftarrow W \leftarrow Y, X \leftarrow W \rightarrow Y[/math] — [math]X[/math] влияет на [math]Y[/math], если [math]W[/math] не принадлежит [math]Z[/math].
• [math]X \rightarrow W \leftarrow Y[/math] ([math]V[/math]-образная структура) — [math]X[/math] влияет на [math]Y[/math], если [math]W[/math] или кто-либо из потомков [math]W[/math] принадлежит [math]Z[/math], и, соответственно, [math]X[/math] не влияет на [math]Y[/math], если [math]W[/math] или хотя бы кто-либо из потомков [math]W[/math] не принадлежит [math]Z[/math].

Определение:

Активные пути (англ. Active Trails) — путь [math] X_1 — \ldots — X_k [/math] активен при свидетельствах [math]Z[/math], если: для каждой [math]V[/math]-образной структуры [math]X_i-1 \rightarrow X_i \leftarrow X_i+1[/math] [math]X_i[/math] или один из его потомков принадлежит [math]Z[/math]; все остальные [math]X_i[/math] (которые не образуют [math]V[/math]-образную структуру) не принадлежат [math]Z[/math].

Условная независимость

Определение:

Маргинальная вероятность — это безусловная вероятность [math]P(A)[/math] события [math]A[/math]; то есть, вероятность события [math]A[/math], независимо от того, наступает ли какое-то другое событие [math]B[/math] или нет. Если о [math]B[/math] можно думать как о некоторой случайной величине, принявшей данной значение, маргинальная вероятность [math]A[/math] может быть получена суммированием (или более широко интегрированием) совместных вероятностей по всем значениям этой случайной величины. Эту процедуру иногда называют маргинализацией вероятности. На рисунке 1 вероятность того, что студент умный ([math]i=1[/math]) является маргинальной, так как у вершины i нет родителей, с помощью маргинализации эту же вероятность можно получить сложив вероятности того, что студент умный, и он получит высокий балл по SAT, и того что, студент умный и получит низкий балл по SAT.

Определение:

[math]X[/math] и [math]Y[/math] являются [math]d[/math]-разделёнными (англ. [math]d[/math]-separated), если в графе [math]G[/math] при означивании [math]Z[/math] не существует активного пути между [math]X[/math] и [math]Y[/math]. Обозначение: [math]dsep_G(X, Y|Z)[/math].

Определение:

[math]P[/math] факторизуется над [math]G[/math], если [math]\mathrm P(X_1, \ldots, X_n) = \prod_{i=1}^n \mathrm P(X_i \mid \operatorname{parents}(X_i)).[/math]

Определение:

[math]P \models (X \bot Y|Z)[/math] — в вероятностном пространстве [math]P[/math] переменная [math]X[/math] не зависима от переменной [math]Y[/math] при условии означивания переменной [math]Z[/math]. Знак [math]\models[/math] следует читать как "удовлетворяет".

Утверждение:

[math]P \models (X \bot Y | Z)[/math], если [math]P(X,Y,Z) \propto \phi_1(X,Z) \phi_2(Y,Z)[/math], где [math]\phi_i[/math] — факторы, [math]\propto[/math] следует читать как "пропорционально".

Теорема:

Если [math]P[/math] факторизуется над [math]G[/math] и [math]dsep_G(X, Y|Z)[/math], то [math]P \models (X \bot Y|Z)[/math].

Доказательство:

[math]\triangleright[/math]

Покажем на примере из рисунка 1: [math]dsep_G(D, S|G)[/math], [math]P(D,I,G,S,L) = P(D)P(I)P(G|I,D)P(S|I)P(L|G)[/math] — цепное правило, [math]P[/math] факторизуется над [math]G[/math], [math]P(D,S) = \sum\limits_{G, L, I} P(D)P(I)P(G|D,I)P(S|I)P(L|G)=[/math] [math]\sum\limits_{I}P(D)P(I)P(S|I)\sum\limits_{G}(P(C|D,I)\sum\limits_{L}P(L|G))=P(D)(\sum\limits_{I}P(I)P(S|I))=\phi_1(D)\phi_2(S)[/math]. Значит, [math]P\models (X\bot Y | Z)[/math].

[math]\triangleleft[/math]

Утверждение:

Если [math]P[/math] факторизуется над [math]G[/math], то в [math]P[/math] каждая переменная [math]d[/math]-разделена (независима) от вершин, не являющихся её потомками, при означивании родителей.

Рис. 2: Иллюстрация к утверждению про независимость переменной от вершин, не являющихся её потомками

Рассмотрим пример на рисунке 2: Вершина [math]L[/math] [math]d-разделена[/math] от всех вершин, не являющихся её потомками, так как все пути от вершин, не являющихся потомками, проходят через [math]G[/math], которая получила означивание, следовательно, такие пути неактивны, а пути, проходящие через [math]J[/math] или [math]L[/math] не являются активными, так как данные вершины не получили означивание и образуют [math]v[/math]-образную структуру.

Определение:

[math]I(G)={(X \bot Y | Z):dsep_G(X, Y|Z)}[/math], если [math]P \models I(G)[/math], [math]G[/math] является картой независимостей для [math]P[/math]. [math]I(G)[/math] — множество независимостей.

Теорема:

Если [math]P[/math] факторизуется над [math]G[/math], то [math]G[/math] является картой независимостей для [math]P[/math].

Доказательство:

[math]\triangleright[/math]

Теорема является более формальной записью утверждения про [math]d[/math]-разделимость выше, доказательство на примере из рисунка 2 приведено выше.

[math]\triangleleft[/math]

Теорема:

Если [math]G[/math] является картой независимостей для [math]P[/math], то [math]P[/math] факторизуется над [math]G[/math].

Доказательство:

[math]\triangleright[/math]

[math]P(D,I,G,S,L) = P(D)P(I|D)P(G|D,I)P(S|D,I,G)P(L|D,I,G,S)[/math] — цепное правило для вероятностей, воспользуемся тем, что переменные независимы от вершин, не являющихся их потомками, при означивании родителей, получим: [math]P(D)P(I|D)P(G|D,I)P(S|D,I,G)P(L|D,I,G,S)=P(D)P(I)P(G|D,I)P(S|I)P(L|G)[/math] — цепное правило для байесовской сети. Значит [math]P[/math] факторизуется над [math]G[/math].

[math]\triangleleft[/math]

Применение

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

Примечания

• https://www.coursera.org/lecture/probabilistic-graphical-models/semantics-factorization-trtai
• https://www.coursera.org/lecture/probabilistic-graphical-models/reasoning-patterns-KMjHs
• https://www.coursera.org/lecture/probabilistic-graphical-models/flow-of-probabilistic-influence-1eCp1
• https://www.coursera.org/lecture/probabilistic-graphical-models/conditional-independence-PTXfn
• https://www.coursera.org/lecture/probabilistic-graphical-models/independencies-in-bayesian-networks-JRkCU

См. также

• Условная вероятность

Источники информации

• Andrew D. Gordon, Thomas A. Henzinger, Aditya V. Nori, and Sriram K. Rajamani. 2014. Probabilistic programming. In Proceedings of the on Future of Software Engineering (FOSE 2014). ACM, New York, NY, USA, 167-181. DOI=10.1145/2593882.2593900 doi.acm.org/10.1145/2593882.2593900