Редактирование: Байесовские сети

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Байесовская сеть''' (англ. ''Bayesian network'') — это направленный ациклический граф <tex>G\ = <V, E></tex>, в котором каждой вершине <tex>v \in V</tex> поставлена в соответствие случайная величина <tex>X_v</tex> и каждое ребро <tex>(u, v) \in E</tex> представляет прямую зависимость <tex>X_v</tex> от <tex>X_u</tex>. Пусть <tex>parents(v) = {u\ |\ (u,\ v)\ \in\ E}</tex>, тогда в Байесовской сети каждой вершине <tex>v\ \in\ V</tex> графа должно быть сопоставлено распределение условных вероятностей от вершин из <tex>parents(v)</tex>.
+
'''Байесовская сеть''' (англ. ''Bayesian network'') — это направленный ациклический граф <tex>G\ = <V, E></tex>, в котором каждой вершине <tex>v \in V</tex> поставлена в соответствие случайная переменная <tex>X_v</tex> и каждое ребро <tex>(u, v) \in E</tex> представляет прямую зависимость <tex>X_v</tex> от <tex>X_u</tex>. Пусть <tex>parents(v) = {u\ |\ (u,\ v)\ \in\ E}</tex>, тогда в Байесовской сети каждой вершине <tex>v\ \in\ V</tex> графа должно быть сопоставлено распределение условных вероятностей от вершин из <tex>parents(v)</tex>.
 
}}
 
}}
  
Строка 8: Строка 8:
 
== Пример ==
 
== Пример ==
  
[[Файл:Модель студента.png|мини|center|600px|Рис. 1: Байесовская сеть "Студент".]]
+
[[Файл:Bayesian Student Network.png]]
  
Байесовская сеть, представленная на рисунке 1, отображает следующие зависимости. Оценка студента зависит от его интеллекта и сложности курса. Студент просит у преподавателя рекомендацию, предположим, что преподаватель может написать плохую или хорошую рекомендацию в зависимости от оценки студента. Также студент сдаёт госэкзамен, результаты экзамена не зависят от рекомендации преподавателя, оценки за его курс и сложности курса. Представление этой модели в Байесовской сети представлено на рисунке ниже.  
+
Оценка студента (Grade) зависит от его интеллекта (Intelligence) и сложности курса (Difficulty). Студент просит у преподавателя рекомендательное письмо (Letter), предположим, что преподаватель может написать плохое или хорошее письмо в зависимости от оценки студента. Также студент сдаёт экзамен для поступления в колледж (SAT), результаты экзамена не зависят от письма преподавателя, оценки за его курс и сложности курса. Представление этой модели в Байесовской сети представлено на рисунке ниже.  
  
С помощью цепного правила рассчитаем вероятность того, что умный студент получает B по лёгкому курсу, высокий балл за госэкзамен и плохую рекомендацию: <math> P(i_1, d_0, g_2, s_1, l_0) = P(i_1)P(d_0)P(g_2 | i_1, d_0)P(s_1 | i_1)P(l_0 | g_2) = 0.3*0.6*0.08*0.8*0.4 = 0.004608. </math>
+
С помощью цепного правила рассчитаем вероятность того, что умный студент получает 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,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) = \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,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) = \sum\limits_{D,I} P(D)P(I)\sum\limits_{G}P(G|I,D) = \sum\limits_{D,I} P(D)P(I) = 1. </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) ==
 
== Виды вероятностного вывода (англ. Reasoning Patterns) ==
Строка 28: Строка 28:
 
Прямой вывод — определение вероятности события при наблюдаемых причинах.
 
Прямой вывод — определение вероятности события при наблюдаемых причинах.
  
Пример к рисунку 1: вероятность получения хорошей рекомендации, если известно, что студент обладает низким интеллектом, <math>P(l_1 | i_0) \approx 0.39</math>, если известно, что курс был лёгким, вероятность повысится, <math>P(l_1 | i_0, d_0) \approx 0.51 </math>.  
+
Пример: вероятность получения хорошего рекомендательного письма, если известно, что студент обладает низким интеллектом, <math>P(l1 | i0) \approx 0.39</math>, если известно, что курс был лёгким, вероятность повысится, <math>P(l1 | i0, d0) \approx 0.51 </math>.  
  
 
'''Обратный вывод, или диагностирование (англ. Evidential Reasoning)'''
 
'''Обратный вывод, или диагностирование (англ. Evidential Reasoning)'''
Строка 34: Строка 34:
 
Обратный вывод — определение вероятности причины при наблюдаемых следствиях.
 
Обратный вывод — определение вероятности причины при наблюдаемых следствиях.
  
Пример к рисунку 1: вероятность того, что курс сложный, если студент получил оценку С, <math>P(d_1 | g_3) \approx 0.63</math>, вероятность того, что студент умный, если он получил оценку С, <math> P(i_1 | g_3) \approx 0.08 </math>.
+
Пример: вероятность того, что курс сложный, если студент получил оценку С, <math>P(d1 | g3) \approx 0.63</math>, вероятность того, что студент умный, если он получил оценку С, <math> P(i1 | g3) \approx 0.08 </math>.
  
 
'''Межпричинный (смешанный) вывод (англ. Intercausal Reasoning)'''
 
'''Межпричинный (смешанный) вывод (англ. Intercausal Reasoning)'''
Строка 40: Строка 40:
 
Межпричинный вывод — определение вероятности одной из причин наступившего события при условии наступления одной или нескольких других причин этого события.
 
Межпричинный вывод — определение вероятности одной из причин наступившего события при условии наступления одной или нескольких других причин этого события.
  
Рассмотрим вероятность из прошлого примера, <math> P(i_1 | g_3) \approx 0.08 </math>, вероятность того, что студент умный, слегка увеличивается, если также известно, что курс сложный,  <math> P(i_1 | g_3, d_1) \approx 0.11 </math>, сложность курса (D) и интеллект студента (I) не связаны ребром, рассмотрим, как получается, что они влияют друг на друга, на более простом примере.
+
Рассмотрим вероятность из прошлого примера, <math> P(i1 | g3) \approx 0.08 </math>, вероятность того, что студент умный, слегка увеличивается, если также известно, что курс сложный,  <math> P(i1 | g3, d1) \approx 0.11 </math>, сложность курса (D) и интеллект студента (I) не связаны ребром, рассмотрим, как получается, что они влияют друг на друга, на более простом примере.
  
 
Предположим, у пациента температура, это сильно повышает вероятность как простуды, так и отравления, хотя они не влияют друг на друга, но если станет известно, что пациент отравился, вероятность простуды сильно уменьшится, симптом уже объяснён одной из возможных причин, и вторая становится менее вероятной. Таким образом, если общее следствие получает '''означивание''', причины становятся зависимыми. По-английски этот феномен называется '''«explaining away»'''.
 
Предположим, у пациента температура, это сильно повышает вероятность как простуды, так и отравления, хотя они не влияют друг на друга, но если станет известно, что пациент отравился, вероятность простуды сильно уменьшится, симптом уже объяснён одной из возможных причин, и вторая становится менее вероятной. Таким образом, если общее следствие получает '''означивание''', причины становятся зависимыми. По-английски этот феномен называется '''«explaining away»'''.
Строка 50: Строка 50:
 
''' Свидетельства ''' — утверждения вида «событие в узле x произошло».
 
''' Свидетельства ''' — утверждения вида «событие в узле x произошло».
  
<math>X</math> '''влияет''' на <math>Y</math>, когда свидетельство <math>X</math> может изменить распределение вероятностей <math>Y</math>.
+
<math>X</math> '''влияет''' на <math>У</math>, когда свидетельство <math>X</math> может изменить распределение вероятностей Y.
  
Рассмотрим случаи, когда <math>X</math> влияет на <math>Y</math> при имеющихся свидетельствах <math>Z</math>:
+
Рассмотрим случаи, когда <math>X</math> влияет на <math>У</math> при имеющихся свидетельствах <math>Z</math>:
  
* <math>X \rightarrow Y</math>: <math>X</math> всегда влияет на <math>Y</math>.
+
* Если вершины связаны непосредственно (<math>X \rightarrow Y</math> или <math>X \leftarrow Y</math>), <math>X</math> всегда влияет на <math>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 \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>.
* <math>X \leftarrow W \leftarrow Y</math>: <math>X</math> влияет на <math>Y</math>, если <math>W</math> не принадлежит <math>Z</math>.
 
* <math>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>.
 
  
 
{{Определение
 
{{Определение
Строка 72: Строка 69:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
'''Маргинальная вероятность''' — это безусловная вероятность <math>P(A)</math> события <math>A</math>; то есть, вероятность события <math>A</math>, независимо от того, наступает ли какое-то другое событие <math>B</math> или нет.
+
<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>B</math> можно думать как о некоторой случайной величине, принявшей данное значение, маргинальная вероятность <math>A</math> может быть получена суммированием (или более широко интегрированием) совместных вероятностей по всем значениям этой случайной величины. Эту процедуру иногда называют '''маргинализацией''' вероятности. На рисунке 1 вероятность того, что студент умный (<math>i=1</math>), является маргинальной, так как у вершины <math>i</math> нет родителей, с помощью маргинализации эту же вероятность можно получить, сложив вероятности того, что студент умный и он получит высокий балл за госэкзамен, и того, что студент умный и получит низкий балл за госэкзамен.
 
 
 
{{Определение
 
|definition =
 
<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>.
 
 
}}
 
}}
  
Строка 86: Строка 76:
 
<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</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>\models</math> следует читать как "удовлетворяет", <math>\propto</math> — "пропорционально".
 
 
{{Определение
 
|definition =
 
<math>P \models (X \bot Y|Z)</math> — в вероятностном пространстве <math>P</math> переменная <math>X</math> не зависима от переменной <math>Y</math> при условии означивания переменной <math>Z</math>.
 
}}
 
 
{{Утверждение
 
|statement=<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> — факторы.
 
}}
 
 
  
 
{{Теорема
 
{{Теорема
 
|id = factorization independence
 
|id = factorization independence
 
|author=
 
|author=
|statement=Если <math>P</math> факторизуется над <math>G</math> и <math>dsep_G(X, Y|Z)</math>, то <math>P \models (X \bot Y|Z)</math>.
+
|statement=Если <math>P</math> факторизуется над <math>G</math> и <math>dsep_G(X, Y|Z)</math>, то P удовлетворяет <math>(X \bot Y|Z)</math>.
}}
+
|proof= <math>P(D,I,G,S,L) = P(D)P(I)P(G|I,D)P(S|I)P(L|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>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)=\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>.
 
  
 
{{Утверждение
 
{{Утверждение
|statement=Если <math>P</math> факторизуется над <math>G</math>, то в <math>P</math> каждая переменная <math>d</math>-отделена (независима) от вершин, не являющихся её потомками, при означивании родителей.
+
|statement=Если <math>P</math> факторизуется над <math>G</math>, то в <math>P</math> каждая переменная независима от вершин, не являющихся её потомками, при условии родителей.
 
}}
 
}}
 
[[Файл:Flow_of_influence_and_d-separation.PNG|мини|600px|Рис. 2: Иллюстрация к утверждению про независимость переменной от вершин, не являющихся её потомками. Красным цветом обозначена проверочная вершина, жёлтым — её родители, синим — потомки, зелёным — вершины, не являющиеся её потомками.]]
 
 
Рассмотрим пример на рисунке 2: вершина <math>L</math> <math>d</math>-отделена от всех вершин, не являющихся её потомками: в вершину <math>L</math> можно попасть из вершин <math>G</math> или <math>J</math>, все пути к ней от вершин, не являющихся её потомками, проходящие через <math>G</math>, неактивны, так как <math>G</math> получила означивание, а пути, проходящие через <math>J</math>, также не являются активными, так как <math>J</math> не получила означивания и образует <math>v</math>-образную структуру с <math>L</math> и <math>S</math> и <math>L</math> и <math>H</math>.
 
  
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<math>I(G)={(X \bot Y | Z):dsep_G(X, Y|Z)}</math>, если <math>P \models I(G)</math>, <math>G</math> является '''картой независимостей''' (англ. ''Independency map (I-map)'') для <math>P</math>. <math>I(G)</math> — множество независимостей.
+
<math>I(G)={(X \bot Y | Z):dsep_G(X, Y|Z)}</math>, если <math>P</math> удовлетворяет <math>I(G)</math>, <math>G</math> является <math>I-map</math> (independency map) для <math>P</math>.
 
}}
 
}}
  
Строка 131: Строка 99:
 
|id = factorization independence 2
 
|id = factorization independence 2
 
|author=
 
|author=
|statement=Если <math>P</math> факторизуется над <math>G</math>, то <math>G</math> является картой независимостей для <math>P</math>.
+
|statement=Если <math>P</math> факторизуется над <math>G</math>, то <math>G</math> является <math>I-map</math> для <math>P</math>.
 
}}
 
}}
  
Строка 137: Строка 105:
 
|id = factorization independence 2
 
|id = factorization independence 2
 
|author=
 
|author=
|statement=Если <math>G</math> является картой независимостей для <math>P</math>, то <math>P</math> факторизуется над <math>G</math>.
+
|statement=Если <math>G</math> является <math>I-map</math> для <math>P</math>, то <math>P</math> факторизуется над <math>G</math>.
|proof= <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> — цепное правило для вероятностей,
+
|proof= <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(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(D)P(G|D,I)P(S|I)P(L|D,I,G,S)=</math>
Значит <math>P</math> факторизуется над <math>G</math>.
+
<math>P(D)P(G|D,I)P(S|I)P(L|G)</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
 
* 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

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)