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

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

Часть серии по
Байесовская статистика
Теория
Допустимое правило принятия решения Байесовская эффективность Байесовская вероятность Вероятностные интерпретации Теорема Байеса Фактор Байеса Байесовский вывод Байесовская сеть Прежний Задний Вероятность Конъюгировать приор Задний прогностический Гиперпараметр Hyperprior Принцип безразличия Принцип максимальной энтропии Эмпирический метод Байеса Правило Кромвеля Теорема Бернштейна – фон Мизеса Критерий Шварца Достоверный интервал Максимальная апостериорная оценка Радикальный вероятности
Методы
Байесовская линейная регрессия Байесовская оценка Приближенное байесовское вычисление Цепь Маркова Монте-Карло
Математический портал
v т е

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

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

Графическая модель [ править ]

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

Пример [ править ]

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

Функция совместной вероятности является:

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

где G = «Трава мокрая (истина / ложь)», 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)}}}$

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

${\displaystyle {\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}}}$

Тогда численные результаты (с индексами соответствующих значений переменных) будут

${\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}}\approx 35.77\%.}$

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

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

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

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

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

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

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

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

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

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

Чтобы определить, идентифицируется ли причинная связь из произвольной байесовской сети с ненаблюдаемыми переменными, можно использовать три правила « do -calculus» ^{[1] [4]} и проверить, можно ли удалить все do- члены из выражения этого отношения. , тем самым подтверждая, что желаемое количество можно оценить по частотным данным. ^[5]

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

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

Вывод и обучение [ править ]

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

Вывод ненаблюдаемых переменных [ править ]

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

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

Обучение параметрам [ править ]

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

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

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

Структурное обучение [ править ]

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

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

Узоры соединений

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

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

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

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

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

Другой метод состоит в сосредоточении внимания на подклассе разложимых моделей, для которых MLE имеют замкнутую форму. Тогда можно обнаружить непротиворечивую структуру для сотен переменных. ^[14]

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

Статистическое введение [ править ]

При заданных данных и параметре простой байесовский анализ начинается с априорной вероятности ( априорной ) и правдоподобия для вычисления апостериорной вероятности .${\displaystyle x\,\!}$${\displaystyle \theta }$${\displaystyle p(\theta )}$ ${\displaystyle p(x\mid \theta )}$ ${\displaystyle p(\theta \mid x)\propto p(x\mid \theta )p(\theta )}$

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

${\displaystyle p(\theta ,\varphi \mid x)\propto p(x\mid \theta )p(\theta \mid \varphi )p(\varphi ).}$

Это простейший пример иерархической байесовской модели . ^{[ требуется разъяснение ]}

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

Вводные примеры [ править ]

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

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

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

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

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

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

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

с ненадлежащими настоятелями , . Когда это идентифицированная модель (т. Е. Существует уникальное решение для параметров модели), и апостериорные распределения индивидуума будут иметь тенденцию перемещаться или сокращаться от оценок максимального правдоподобия к их общему среднему значению. Это сжатие - типичное поведение в иерархических байесовских моделях.${\displaystyle \varphi \sim {\text{flat}}}$${\displaystyle \tau \sim {\text{flat}}\in (0,\infty )}$${\displaystyle n\geq 3}$${\displaystyle \theta _{i}}$

Ограничения по приору [ править ]

При выборе априорных значений в иерархической модели требуется некоторая осторожность, особенно в отношении масштабных переменных на более высоких уровнях иерархии, таких как переменная в примере. Обычные априорные значения, такие как априор Джеффри, часто не работают, потому что апостериорное распределение не поддается нормализации и оценки, сделанные путем минимизации ожидаемых потерь, будут недопустимыми .${\displaystyle \tau \,\!}$

Определения и понятия [ править ]

Было предложено несколько эквивалентных определений байесовской сети. Для следующего, пусть G = ( V , E ) быть ориентированный ациклический граф (DAG) , и пусть X = ( X _v ), v ∈ V некоторое множество случайных величин , индексированных V .

Определение факторизации [ править ]

X является байесовской сетью по отношению к G, если ее совместная функция плотности вероятности (относительно меры произведения ) может быть записана как произведение отдельных функций плотности, обусловленных их родительскими переменными: ^[16]

${\displaystyle p(x)=\prod _{v\in V}p\left(x_{v}\,{\big |}\,x_{\operatorname {pa} (v)}\right)}$

где pa ( v ) - это множество родителей v (т.е. те вершины, которые указывают прямо на v через одно ребро).

Для любого множества случайных величин, вероятность любого члена совместного распределения может быть вычислена из условных вероятностей , используя правило цепи ( по заданной топологическое упорядочению из X ) следующим образом : ^[16]

${\displaystyle \operatorname {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\operatorname {P} \left(X_{v}=x_{v}\mid X_{v+1}=x_{v+1},\ldots ,X_{n}=x_{n}\right)}$

Используя приведенное выше определение, это можно записать как:

${\displaystyle \operatorname {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\operatorname {P} (X_{v}=x_{v}\mid X_{j}=x_{j}{\text{ for each }}X_{j}\,{\text{ that is a parent of }}X_{v}\,)}$

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

Местная марковская собственность [ править ]

X является байесовской сетью по отношению к G, если она удовлетворяет локальному марковскому свойству : каждая переменная условно не зависит от своих не-потомков, учитывая ее родительские переменные: ^[17]

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\,\smallsetminus \,\operatorname {de} (v)}\mid X_{\operatorname {pa} (v)}\quad {\text{for all }}v\in V}$

где de ( v ) - множество потомков, а V  \ de ( v ) - множество не потомков v .

Это можно выразить в терминах, аналогичных первому определению, как

${\displaystyle {\begin{aligned}&\operatorname {P} (X_{v}=x_{v}\mid X_{i}=x_{i}{\text{ for each }}X_{i}{\text{ that is not a descendant of }}X_{v}\,)\\[6pt]={}&P(X_{v}=x_{v}\mid X_{j}=x_{j}{\text{ for each }}X_{j}{\text{ that is a parent of }}X_{v}\,)\end{aligned}}}$

Набор родителей является подмножеством множества не-потомков, потому что граф является ациклическим .

Разработка байесовских сетей [ править ]

Развитие байесовской сети часто начинается с создания DAG G такое , что X удовлетворяет местный марковским свойством по отношению к G . Иногда это причинный DAG. Условные распределения вероятностей каждой переменной с учетом его родители в G оцениваются. Во многих случаях, в частности , в том случае , когда переменные являются дискретными, если совместное распределение X является произведением этих условных распределений, то X является байесовской сети по отношению к G . ^[18]

Марковское одеяло [ править ]

Марковское узла является множеством узлов , состоящих из своих родителей, своих детей, а также любых других родителей своих детей. Одеяло Маркова делает узел независимым от остальной сети; совместное распределение переменных в марковском бланкете узла является достаточным знанием для вычисления распределения узла. X является байесовской сетью относительно G, если каждый узел условно независим от всех других узлов в сети, учитывая его марковское одеяло . ^[17]

г- разделение [ править ]

Это определение можно сделать более общим, определив «d» -разделение двух узлов, где d означает направленность. ^[1] Сначала мы определяем «d» -разделение трассы, а затем мы определяем «d» -разделение двух узлов в терминах этого.

Пусть P - тропа от узла u до v . Трасса - это свободный от петель, неориентированный (т. Е. Все направления краев игнорируются) путь между двумя узлами. Тогда P называется d- разделенным набором узлов Z, если выполняется одно из следующих условий:

• P содержит (но не обязательно полностью) направленную цепочку, или , если средний узел m находится в Z ,${\displaystyle u\cdots \leftarrow m\leftarrow \cdots v}$${\displaystyle u\cdots \rightarrow m\rightarrow \cdots v}$
• P содержит вилку,, такую, что средний узел m находится в Z , или${\displaystyle u\cdots \leftarrow m\rightarrow \cdots v}$
• Р содержит перевернутую вилку (или коллайдер), таким образом, что средний узел м не находится в Z и ни один потомок м не находится в Z .${\displaystyle u\cdots \rightarrow m\leftarrow \cdots v}$

Узлы U и V являются d -разделенного от Z , если все маршруты между ними d -разделенными. Если u и v не разделены d, они d-связаны.

X - байесовская сеть относительно G, если для любых двух узлов u , v :

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{Z}}$

где Z - множество, которое d- разделяет u и v . (The одеяло Маркова является минимальным набором узлов , которые д разъединителей узла V от всех других узлов.)

Причинные сети [ править ]

Хотя байесовские сети часто используются для представления причинно-следственных связей, это не обязательно: направленное ребро от u до v не требует, чтобы X _v причинно зависел от X _u . Об этом свидетельствует тот факт, что байесовские сети на графах:

${\displaystyle a\rightarrow b\rightarrow c\qquad {\text{and}}\qquad a\leftarrow b\leftarrow c}$

эквивалентны: то есть они предъявляют точно такие же требования условной независимости.

Причинная сеть - это байесовская сеть с требованием, чтобы отношения были причинными. Дополнительная семантика причинных сетей указывает, что если узел X активно находится в заданном состоянии x (действие, записанное как do ( X  =  x )), то функция плотности вероятности изменяется на функцию плотности вероятности, полученную путем разрезания ссылки от родителей X на X и установка X на вызванное значение x . ^[1] Используя эту семантику, можно предсказать влияние внешнего вмешательства на основании данных, полученных до вмешательства.

Сложность вывода и алгоритмы аппроксимации [ править ]

В 1990 году, работая в Стэнфордском университете над большими биоинформатическими приложениями, Купер доказал, что точный вывод в байесовских сетях NP-труден . ^[19] Этот результат побудил исследовать алгоритмы приближения с целью разработки удобного приближения к вероятностному выводу. В 1993 году Дагум и Луби доказали два удивительных результата о сложности аппроксимации вероятностного вывода в байесовских сетях. ^[20] Во- первых, они доказали , что не послушной детерминированный алгоритм не может аппроксимировать вероятностный вывод в пределах абсолютной погрешности ɛ  <1/2. Во-вторых, они доказали, что ни один поддающийся обработке рандомизированный алгоритмможно аппроксимировать вероятностный вывод в пределах абсолютной погрешности ɛ  <1/2 с доверительной вероятностью больше 1/2.

Примерно в то же время Рот доказал, что точный вывод в байесовских сетях на самом деле является # P-полным (и, таким образом, столь же сложен, как подсчет числа удовлетворяющих присваиваний формулы конъюнктивной нормальной формы (CNF) и этот приблизительный вывод в пределах коэффициента 2 ^{n 1− ɛ} для любого ɛ > 0, даже для байесовских сетей с ограниченной архитектурой, является NP-трудным. ^{[21] [22]}

С практической точки зрения, эти результаты сложности предполагают, что, хотя байесовские сети были богатым представлением для приложений ИИ и машинного обучения, их использование в больших реальных приложениях должно было сдерживаться либо топологическими структурными ограничениями, такими как наивные байесовские сети, либо ограничениями. от условных вероятностей. Алгоритм ограниченной дисперсии ^[23] был первым доказуемым алгоритмом быстрой аппроксимации для эффективной аппроксимации вероятностного вывода в байесовских сетях с гарантиями приближения ошибки. Этот мощный алгоритм требовал, чтобы небольшое ограничение на условные вероятности байесовской сети было отделено от нуля и единицы величиной 1 / p ( n ), где p ( n) был любым полиномом от числа узлов в сети  n .

Программное обеспечение [ править ]

Известное программное обеспечение для байесовских сетей включает:

• Еще один семплер Гиббса (JAGS) - альтернатива WinBUGS с открытым исходным кодом. Использует выборку Гиббса.
• OpenBUGS - разработка WinBUGS с открытым исходным кодом.
• SPSS Modeler - коммерческое программное обеспечение, которое включает реализацию для байесовских сетей.
• Stan (программное обеспечение) - Stan - это пакет с открытым исходным кодом для получения байесовского вывода с использованием семплера без разворота (NUTS), ^[24] вариант гамильтониана Монте-Карло.
• PyMC3 - библиотека Python, реализующая встроенный предметно-ориентированный язык для представления байесовских сетей и различные семплеры (включая NUTS)
• WinBUGS - одна из первых вычислительных реализаций семплеров MCMC. Больше не поддерживается.

История [ править ]

Термин байесовская сеть был введен Джудеей Перл в 1985 году, чтобы подчеркнуть: ^[25]

• часто субъективный характер вводимой информации
• использование условий Байеса как основы для обновления информации
• различие между причинным и доказательным способами рассуждения ^[26]

В конце 1980 - х годов Перл Вероятностный Рассуждая в интеллектуальных системах ^[27] и неаполитанский «s Вероятностный Рассуждая экспертных систем ^[28] суммированы их свойства и установили их в качестве области исследования.

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Конради С., Джофф Л. (01.07.2015). Байесовские сети и BayesiaLab - практическое введение для исследователей . Франклин, Теннесси: Байесовские США. ISBN 978-0-9965333-0-0.
• Чарняк Э. (Зима 1991). «Байесовские сети без слез» (PDF) . Журнал AI .
• Kruse R, Borgelt C, Klawonn F, Moewes C, Steinbrecher M, Held P (2013). Вычислительный интеллект - методологическое введение . Лондон: Springer-Verlag. ISBN 978-1-4471-5012-1.
• Боргельт C, Steinbrecher M, Kruse R (2009). Графические модели - представления для обучения, рассуждений и интеллектуального анализа данных (второе изд.). Чичестер: Вайли. ISBN 978-0-470-74956-2.

Внешние ссылки [ править ]

• Введение в байесовские сети и их современные приложения
• Он-лайн учебник по байесовским сетям и вероятностям
• Веб-приложение для создания байесовских сетей и запуска его методом Монте-Карло
• Байесовские сети с непрерывным временем
• Байесовские сети: объяснение и аналогия
• Живое руководство по изучению байесовских сетей
• Иерархическая модель Байеса для обработки неоднородности образцов в задачах классификации предоставляет модель классификации, учитывающую неопределенность, связанную с измерением повторяющихся образцов.
• Иерархическая наивная байесовская модель для обработки неопределенности выборки показывает, как выполнять классификацию и обучение с непрерывными и дискретными переменными с реплицированными измерениями.