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

редактировать

Статистическая модель

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

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

Содержание

1 Графическая модель
2 Пример
3 Вывод и обучение
- 3.1 Вывод ненаблюдаемых объем
- 3.2 Обучение параметрам
- 3.3 Обучение структуре
4 Статистическое введение
- 4.1 Вводные примеры
- 4.2 Ограничения априорных значений
5 Определения и концепции
- 5.1 Определение факторизации
- 5.2 Локальное марковское свойство
- 5.3 Разработка байесовских сетей
- 5.4 Марковское одеяло
  - 5.4.1 d-разделение
- 5.5 Причинные сети
6 Сложность вывода и алгоритмы аппроксимации
7 Программное обеспечение
8 История
9 См. Также
10 Примечания
11 Ссылки
12 Дополнительная литература
13 Ссылки

Графическая модель

Формально байесовские сети - это ориентированные ациклические графы (DAG), узлы которые представляют переменные в байесовском смысле: они могут быть наблюдаемыми величинами, скрытыми переменными, неизвестные параметры или гипотезы. Ребра предоставьте собой условные зависимости; узлы, которые не связаны (никакой путь не соединяет один узел с другими), предоставьте переменные, которые условно независимы от друга. Каждый узел с функцией вероятности , которая принимает в качестве входных данных набор значений для родительских число узла и дает (в качестве выходных данных) вероятность (или распределение вероятностей, если применимо) перемен., представленной узлом. Например, если $m {\ displaystyle m}$ $m$ родительские узлы указывает $m {\ displaystyle m}$ $m$ логические переменные, тогда функция вероятности может быть представлена в виде таблицы из $2 м {\ displaystyle 2 ^ {m}}$ $2^{m}$ записей, по одной записи для каждой из $2 м {\ displaystyle 2 ^ {m}}$ $2^{m}$ в родительские комбинации. Подобные идеи могут быть применены к неориентированным и, возможно, циклическим графам, таким как сети Маркова.

Пример

Простая байесовская сеть с таблицами условной вероятности

Два события могут привести к намоканию трав: активная поливальная машина или дождь. Дождь имеет прямое влияние на использование дождевателя (а именно, когда идет дождь, дождеватель обычно не работает). Эту ситуацию можно смоделировать с помощью байесовской сети (показано справа). Каждая переменная имеет два значения: T (истина) и F (ложь).

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

Pr (G, S, R) = Pr (G ∣ S, R) Pr (S ∣ R) Pr (R) {\ displaystyle \ Pr (G, S, R) = \ Pr (G \ mid S, R) \ Pr (S \ mid R) \ Pr (R)}

\Pr(G,S,R)=\Pr(G\mid S,R)\Pr(S\mid R)\Pr(R)

где G = «Трава мокрая (истина / ложь)», S = «Спринклер включен (истина / ложь)» и R = «Дождь (истина / ложь)».

Модель может ответить на вопросы о наличии причины при наличии эффекта (так называемая обратная вероятность), например: «Какова вероятность того, что идет дождь, если трава мокрая?» с помощью формулы условной вероятности и суммирования по всем мешающим переменным :

Pr (R = T ∣ G = T) = Pr (G = T, R = T) Pr (G = T) Знак равно ∑ S ∈ {T, F} Pr (G = T, S, R = T) ∑ S, R ∈ {T, F} Pr (G = T, S, R) {\ Displaystyle \ Pr (R = T \ mid G = T) = {\ frac {\ Pr (G = T, R = T)} {\ Pr (G = T)}} = {\ frac {\ sum _ {S \ in \ {T, F \}} \ Pr (G = T, S, R = T)} {\ sum _ {S, R \ in \ {T, F \}} \ Pr (G = T, S, R)}}}

\Pr(R=T\mid G=T)={\frac {\Pr(G=T,R=T)}{\Pr(G=T)}}={\frac {\sum _{S\in \{T,F\}}\Pr(G=T,S,R=T)}{\sum _{S,R\in \{T,F\}}\Pr(G=T,S,R)}}

Использование разложения для совместной функции вероятности $Pr (G, S, R) {\ displaystyle \ Pr (G, S, R)}$ $\Pr(G,S,R)$ и условных вероятностей из В таблицах условной вероятности (CPT), указанный на диаграмме, можно оценить каждый член в суммах в числителе и знаменателе. Например,

Pr (G = T, S = T, R = T) = Pr (G = T ∣ S = T, R = T) Pr (S = T ∣ R = T) Pr (R = T) = 0,99 × 0,01 × 0,2 = 0,00198. {\ Displaystyle {\ begin {align} \ Pr (G = T, S = T, R = T) = \ Pr (G = T \ mid S = T, R = T) \ Pr (S = T \ mid R = T) \ Pr (R = T) \\ = 0,99 \ раз 0,01 \ раз 0,2 \\ = 0,00198. \ End {align}}}

{\begin{aligned}\Pr(G=T,S=T,R=T)=\Pr(G=T\mid S=T,R=T)\Pr(S=T\mid R=T)\Pr(R=T)\\=0.99\times 0.01\times 0.2\\=0.00198.\end{aligned}}

Числовые результаты (с индексами соответствующих чисел) равны

Pr (R = T ∣ G = T) = 0,00198 TTT + 0,1584 TFT 0,00198 TTT + 0,288 TTF + 0,1584 TFT + 0,0 TFF = 891 2491 ≈ 35,77%. {\ displaystyle \ Pr (R = T \ mid G = T) = {\ frac {0,00198_ {TTT} + 0,1584_ {TFT}} {0,00198_ {TTT} + 0,288_ {TTF} + 0, 1584_ {TFT} + 0,0_ {TFF}}} = {\ frac {891} {2491}} \ приблизительно 35,77 \%.}

\Pr(R=T\mid G=T)={\frac {0.00198_{TTT}+0.1584_{TFT}}{0.00198_{TTT}+0.288_{TTF}+0.1584_{TFT}+0.0_{TFF}}}={\frac {891}{2491}}\approx 35.77\%.

Чтобы ответить на интервенционный вопрос, например, "Какова вероятность того, что пойдет дождь, учитывая, что мы намочить траву? "ответ имеет функцию совместного распределения после вмешательства

Pr (S, R ∣ do (G = T)) = Pr (S ∣ R) Pr (R) {\ displaystyle \ Pr (S, R \ mid {\ text {do}} (G = T)) = \ Pr (S \ mid R) \ Pr (R)}

\Pr(S,R\mid {\text{do}}(G=T))=\Pr(S\mid R)\Pr(R)

, полученное путем удаления множителя $Pr (G ∣ S, R) {\ displaystyle \ Pr (G \ mid S, R)}$ $\Pr(G\mid S,R)$ из распределения до вмешательства. Оператор заставляет быть истинным. Действие не влияет на вероятность дождя:

Pr (R ∣ do (G = T)) = Pr (R). {\ displaystyle \ Pr (R \ mid {\ text {do}} (G = T)) = \ Pr (R).}

\Pr(R\mid {\text{do}}(G=T))=\Pr(R).

Чтобы предсказать влияние включения спринклера:

Pr (R, G ∣ сделать ( S = T)) знак равно Pr (R) Pr (G ∣ R, S = T) {\ displaystyle \ Pr (R, G \ mid {\ text {do}} (S = T)) = \ Pr (R) \ Pr (G \ mid R, S = T)}

\Pr(R,G\mid {\text{do}}(S=T))=\Pr(R)\Pr(G\mid R,S=T)

с членом $Pr (S = T ∣ R) {\ displaystyle \ Pr (S = T \ mid R)}$ $\Pr(S=T\mid R)$ удалено, действие, действие влияет на траву, но не на дождь.

Эти прогнозы могут оказаться невозможными с учетом ненаблюдаемых переменных, как в большинстве оценок политики. Эффект действия $do (x) {\ displaystyle {\ text {do}} (x)}$ ${\text{do}}(x)$ все еще может быть предсказан, однако всякий раз, когда удовлетворяется критерий задней двери. В нем говорится, что, если можно наблюдать набор Z узлов, что d-разделяет (или блокирует) все обходные пути от X до Y, тогда

Pr (Y, Z ∣ do (x)) = Pr (Y, Z, X = x) Pr (X = x ∣ Z). {\ Displaystyle \ Pr (Y, Z \ mid {\ text {do}} (x)) = {\ frac {\ Pr (Y, Z, X = x)} {\ Pr (X = x \ mid Z) }}.}

\Pr(Y,Z\mid {\text{do}}(x))={\frac {\Pr(Y,Z,X=x)}{\Pr(X=x\mid Z)}}.

Черный ход - это путь, который заканчивается стрелкой в X. Наборы, удовлетворяющие критерию черного хода, называются «достаточными» или «допустимыми». Например, множество Z = R допустимо для предсказания влияния S = T на G, потому что R d-разделяет (единственный) черный ход S ← R → G. Однако, если S не соблюдается, никакие другие набор d отделяет этот путь, и эффект включения разбрызгивателя (S = T) на траве (G) не может быть предсказан на пассивных наблюдений. В этом случае P (G | do (S = T)) не идентифицирован ». Это отражает тот факт, что при отсутствии предполагаемой зависимости S и G обусловлена причинной связью или ложной (очевидная зависимость, вызывающая из общей причины, R). (см. парадокс Симпсона )

Чтобы определить идентифицирует ли причинную связь из произвольной байесовской сети с ненаблюдаемыми переменными, можно использовать три правила «выполнить-исчисления» и проверить, проверить, удалить ли можно удалить все члены из выражения этих отношений,

Использование байесовской сети может сэкономить значительный объем памяти по сравнению с исчерпывающими таблицами вероятностей, если зависимости в совместном распределении вероятностей являются разреженными. 10 двузначных чисел в виде таблицы требует места для хранения $2 10 = 1024 {\ displaystyle 2 ^ {10} = 1024}$ $2^{10}=1024$ значений. байесовской сети хранит не более $10 ⋅ 2 3 = 80 {\ displaystyle 10 \ cdot 2 ^ {3} = 80}$ $10\cdot 2^{3}=80$ значений.

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

Логический вывод и обучение

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

Выведение ненаблюдаемых чисел

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

Наиболее распространенными методами эффективного вывода являются: исключение чисел, ненаблюдаемые переменные, не относящиеся к запросу, одно за другим путем распределения суммы по произведению; распространение кликов, которое кэширует вычисления, чтобы можно было запрашивать сразу несколько чисел и быстро распространять новые свидетельства; и рекурсивное кондиционирование и поиск И / ИЛИ, которые допускают компромисс между пространством и временем и соответствуют эффективности исключения, когда используется достаточно места. Все эти методы имеют сложность, которая экспоненциально зависит от ширины дерева сети. Наиболее распространенными алгоритмами приближенного вывода являются выбор по важности, стохастическое моделирование MCMC, устранение мини-ведра, распространение веры с петлей, распространение обобщенных системений и вариационные методы.

изучение параметров

Чтобы полностью определить байесовскую сеть и таким образом, полностью представить совместное распределение вероятностей, необходимо указать для каждого Распределение X узла вероятностей для X в зависимости от родителей X. Распределение X в зависимости от его родителей может иметь любую форму. Обычно работают с дискретными или гауссовыми распределениями, это упрощает вычисления. Иногда известны только ограничения на распределение; затем можно использовать максимальной энтропии для определения единственного распределения, то есть с наибольшей энтропией с учетом ограничений. (Аналогично, в конкретном контексте динамической байесовской сети, условное распределение для временной эволюции скрытого состояния обычно для максимизации скорости энтропии подразумеваемого стохастического процесса.)

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

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

Изучение структуры

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

Автоматическое изучение структуры графа байесовской сети (BN) - задача, решаемая в рамках машинного обучения. Основная идея восходит к алгоритму восстановления, разработанному Ребэйном и Перлом, и основывается на различии между тремя возможными шаблонами, разрешенными в 3-узловом DAG:

Шаблоны соединений
Шаблон	Модель
Цепочка	$X → Y → Z {\ displaystyle X \ rightarrow Y \ rightarrow Z}$ $X\rightarrow Y\rightarrow Z$
Вилка	$X ← Y → Z {\ displaystyle X \ leftarrow Y \ rightarrow Z}$ $X\leftarrow Y\rightarrow Z$
Коллайдер	$X → Y ← Z {\ displaystyle X \ rightarrow Y \ leftarrow Z}$ $X\rightarrow Y\leftarrow Z$

Первые 2 значения одинаковые зависимости ( $X {\ displaystyle X}$ $X$ и $Z {\ displaystyle Z}$ $Z$ не зависит от $Y {\ displaystyle Y}$ $Y$ ) и поэтому неотличимы. Однако коллайдер можно однозначно идентифицировать, поскольку $X {\ displaystyle X}$ $X$ и $Z {\ displaystyle Z}$ $Z$ незначительно независимы, а все остальные пары зависимый. Таким образом, хотя скелеты (графики, лишенные стрелок) трех этих троек идентичны, направление стрелок частично идентифицируется. Такое же различие используется, когда $X {\ displaystyle X}$ $X$ и $Z {\ displaystyle Z}$ $Z$ имеют общих родителей, за исключением того, что сначала нужно указать этих родителей. Были разработаны алгоритмы для систематического определения скелета и последующего ориентирования всех стрелок.

Альтернативный метод структурного обучения использует поиск на основе оптимизации. Для этого требуется функция оценки и стратегия поиска. Обычная функция оценки является апостериорная вероятность структуры с учетом обучающих данных, например BIC или BDeu. Требование времени для исчерпывающего поиска, возвращающего структуру, которая максимизирует оценку, составляет суперэкспоненциальный по количеству числа. Стратегия локального поиска внеситенные изменения, улучшение структуры. Алгоритм глобального поиска, такой как цепь Маркова Монте-Карло, может избежатьпопадания в локальных минимумов. Friedman et al. использовать использование взаимной информации между переменными и поисковыми структурами, которая максимизирует это. Они делают это, ограничивая набор родительских кандидатов k узлами и просматривая их.

Особенно быстрый метод точного обучения BN - это преобразовать проблему в задачу оптимизации и решить ее с помощью целочисленного программирования. Ограничения ацикличности добавляются к целочисленной программе (IP) во время решения в виде плоскостей резки. Такой метод может обрабатывать задачи с числом до 100.

справиться с проблемами с числом чисел, необходимым подход. Один из них в том, чтобы сначала выбрать один порядок, а найти оптимальную структуру BN по отношению к этому порядку. Это подразумевает работу над пространством поиска порядков. Затем выберитека и оценка нескольких заказов. Этот метод зарекомендовал себя как лучший из доступных в литературе при огромном количестве чисел.

Другой метод состоит в сосредоточении внимания на подклассе разложимых моделей, для которого MLE имеет закрытую форму. Затем можно непротиворечивую структуру для сотен число.

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

Введение в статистику

Данные данные $x {\ displaystyle x \, \!}$ $x\,\!$ и параметр $θ {\ displaystyle \ theta}$ $\theta$ , простой байесовский анализ начинается с априорной вероятностью (априорной) $п (θ) {\ displaystyle p (\ theta)}$ $p(\theta)$ и правдоподобие $p (x ∣ θ) {\ displaystyle p (x \ mid \ theta)}$ $p(x\mid \theta)$ для вычислений апостериорной вероятности $p (θ ∣ Икс) ∝ п (Икс ∣ θ) п (θ) {\ Displaystyle p (\ theta \ mid x) \ propto p (x \ mid \ theta) p (\ theta)}$ $p(\theta \mid x)\propto p(x\mid \theta)p(\theta)$ .

Часто предшествующее значение $θ {\ displaystyle \ theta}$ $\theta$ , в свою очередь, зависит от других параметров $φ {\ displaystyle \ varphi}$ $\varphi$ , которые не появляются по вероятности. Таким образом, предыдущий $p (θ) {\ displaystyle p (\ theta)}$ $p(\theta)$ должен быть заменен с вероятностью $p (θ ∣ φ) {\ displaystyle p (\ theta \ mid \ varphi)}$ $p(\theta \mid \varphi)$ , и предыдущий $p (φ) {\ displaystyle p (\ varphi)}$ $p(\varphi)$ на вновь введенных параметрах $φ {\ displaystyle \ varphi }$ $\varphi$ требуется, что дает апостериорную вероятность

p (θ, φ ∣ x) ∝ p (x ∣ θ) p (θ ∣ φ) p (φ). {\ displaystyle p (\ theta, \ varphi \ mid x) \ propto p (x \ mid \ theta) p (\ theta \ mid \ varphi) p (\ varphi).}

p(\theta,\varphi \mid x)\propto p(x\mid \theta)p(\theta \mid \varphi)p(\varphi).

Это простейший пример иерархическая байесовская модель.

Процесс может повторяться; например, параметры $φ {\ displaystyle \ varphi}$ $\varphi$ могут, в свою очередь, зависеть от дополнительных параметров $ψ {\ displaystyle \ psi \, \!}$ $\psi \,\!$ , которые требуют свои приора. В конце концов процесс должен завершиться с приоритетами, не зависящими от не упомянутых параметров.

Вводные примеры

Учитывая измеренные величины $x 1,…, xn {\ displaystyle x_ {1}, \ dots, x_ {n} \, \!}$ $x_{1},\dots,x_{n}\,\!$ каждая с нормально распределенными ошибками известного стандартного отклонения $σ {\ displaystyle \ sigma \, \!}$ $\sigma \,\!$ ,

xi ∼ N (θ i, σ 2) {\ displaystyle x_ {i} \ sim N (\ theta _ {i}, \ sigma ^ {2})}

x_{i}\sim N(\theta _{i},\sigma ^{2})

Предположим, нас интересует оценка $θ i {\ displaystyle \ theta _ {i }}$ $\theta _{i}$ . Подход может заключаться в оценке $θ i {\ displaystyle \ theta _ {i}}$ $\theta _{i}$ с использованием подхода максимального правдоподобия ; поскольку наблюдения независимы, вероятность факторизуется, и оценка максимального правдоподобия просто равна

θ i = x i. {\ displaystyle \ theta _ {i} = x_ {i}.}

\theta _{i}=x_{i}.

Однако, если количества связаны, например, индивидуальный $θ i {\ displaystyle \ theta _ {i}}$ $\theta _{i}$ сами были взяты из базового распределения, то это отношение разрушает независимость и предлагает более сложную модель, например,

xi ∼ N (θ i, σ 2), {\ displaystyle x_ {i} \ сим N (\ theta _ {i}, \ sigma ^ {2}),}

x_{i}\sim N(\theta _{i},\sigma ^{2}),

θ я ∼ N (φ, τ 2), {\ displaystyle \ theta _ {i} \ sim N (\ varphi, \ tau ^ {2}),}

\theta _{i}\sim N(\varphi,\tau ^{2}),

с неправильными априорными значениями $φ ∼ flat {\ displaystyle \ varphi \ sim {\ text {flat}}}$ $\varphi \sim {\text{flat}}$ , $τ ∼ flat ∈ (0, ∞) {\ Displaystyle \ тау \ sim {\ text {flat}} \ in (0, \ infty)}$ $\tau \sim {\text{flat}}\in (0,\infty)$ . Когда $n ≥ 3 {\ displaystyle n \ geq 3}$ $n\geq 3$ , это идентифицированная модель (т.е. существует уникальное решение для параметров модели), и апостериорные распределения индивидуума $θ i {\ displaystyle \ theta _ {i}}$ $\theta _{i}$ будет иметь тенденцию перемещаться или сокращаться от оценок максимального