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

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

Байесовская сеть (также известная как сеть Байеса , сеть Байеса , сеть убеждений или сеть решений ) — это вероятностная графическая модель , которая представляет набор переменных и их условных зависимостей через направленный ациклический граф (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 _{x\in \{T,F\}}\Pr(G=T,S=x,R=T)}{\sum _{x,y\in \{T,F\}}\Pr(G=T,S=x,R=y)}}}$

Используя разложение совместной функции вероятности и условных вероятностей из таблиц условных вероятностей (КПТ), указанных на схеме, можно оценить каждое слагаемое в суммах в числителе и знаменателе. Например, ${\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 , потому что R d -разделяет (единственный) черный путь S  ←  R  →  G. Однако, если S не наблюдается, никакое другое множество d -не отделяет этот путь, и эффект включения разбрызгивателя ( S  =  T ) на траву ( G ) не может быть предсказан на основе пассивных наблюдений. В этом случае P ( G  | do( S  =  T )) не «идентифицирован». Это отражает тот факт, что при отсутствии интервенционных данных наблюдаемая зависимость между S и G обусловлена ​​причинной связью или является ложной (кажущаяся зависимость, возникающая по общей причине R ). (см. парадокс Симпсона )

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

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

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

Вывод и обучение

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

Вывод ненаблюдаемых переменных

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

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

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

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

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

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

Структурное обучение

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

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

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

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

Особенно быстрый метод точного обучения BN — представить задачу как задачу оптимизации и решить ее с помощью целочисленного программирования . В целочисленную программу (ИП) при решении добавляются ограничения ацикличности в виде секущих плоскостей . ^[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}$
• P содержит перевернутую вилку (или коллайдер) , такую, что средний узел m не находится в Z и ни один потомок m не находится в 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 . ( Марковское одеяло — это минимальный набор узлов, который d -отделяет узел 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-полный (и, следовательно, так же сложен, как подсчет количества удовлетворяющих присвоений формулы конъюнктивной нормальной формы (КНФ)) и что аппроксимационный вывод в пределах множителя 2 ^{n 1− ɛ} для каждого ɛ > 0, даже для байесовских сетей с ограниченной архитектурой, является NP-трудной. ^{[21] [22]}

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

Программное обеспечение

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

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

История

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

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

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

Смотрите также

• Математический портал

• Байесовская эпистемология
• Байесовское программирование
• Причинно-следственный вывод
• Диаграмма причинно-следственной петли
• Дерево Чоу-Лю
• Вычислительный интеллект
• Вычислительная филогенетика
• Сеть глубоких убеждений
• Теория Демпстера – Шафера - обобщение теоремы Байеса.
• Алгоритм ожидания-максимизации
• Факторный график
• Иерархическая временная память
• Фильтр Калмана
• Структура прогнозирования памяти
• Распределение смеси
• Модель смеси
• Наивный классификатор Байеса
• Обозначение таблички
• Политри
• Датчик слияния
• Выравнивание последовательности
• Структурное моделирование уравнение
• Субъективная логика
• Байесовская сеть переменного порядка

Примечания

1. Pearl, Иудея (2000). Причинность: модели, рассуждения и выводы. Издательство Кембриджского университета . ISBN 978-0-521-77362-1. ОСЛК  42291253.
2. «Критерий черного хода» (PDF) . Проверено 18 сентября 2014 г.
3. «D-Разлука без слез» (PDF) . Проверено 18 сентября 2014 г.
4. Перл Дж (1994). «Вероятностное исчисление действий». В Лопес де Мантарас Р., Пул Д. (ред.). UAI'94 Материалы Десятой международной конференции «Неопределенность в искусственном интеллекте» . Сан-Матео, Калифорния: Морган Кауфманн . стр. 454–462. arXiv : 1302.6835 . Бибкод : 2013arXiv1302.6835P. ISBN 1-55860-332-8.
5. Шпицер I, Перл Дж (2006). «Идентификация условных интервенционных распределений». В Дектер Р., Ричардсон Т.С. (ред.). Материалы двадцать второй конференции по неопределенности в искусственном интеллекте . Корваллис, Орегон: AUAI Press. стр. 437–444. arXiv : 1206.6876 .
6. Ребане Дж., Перл Дж. (1987). «Восстановление причинных полидеревьев по статистическим данным». Материалы 3-го семинара по неопределенности в ИИ . Сиэтл, Вашингтон. стр. 222–228. arXiv : 1304.2736 .{{cite book}}: CS1 maint: location missing publisher (link)
7. Спиртес П., Глимур С. (1991). «Алгоритм быстрого восстановления разреженных причинных графов» (PDF) . Компьютерный обзор социальных наук . 9 (1): 62–72. CiteSeerX 10.1.1.650.2922 . дои : 10.1177/089443939100900106. S2CID  38398322. 
8. Спиртес П., Глимур CN, Шайнс Р. (1993). Причинно-следственная связь, прогнозирование и поиск (1-е изд.). Спрингер-Верлаг. ISBN 978-0-387-97979-3.
9. Верма Т, Перл Дж (1991). «Эквивалентность и синтез причинных моделей». В Бониссоне П., Хенрионе М., Канале Л.Н., Леммере Дж.Ф. (ред.). UAI '90 Материалы шестой ежегодной конференции по неопределенности в искусственном интеллекте . Эльзевир. стр. 255–270. ISBN 0-444-89264-8.
10. Фридман Н., Гейгер Д., Гольдшмидт М. (ноябрь 1997 г.). «Байесовские сетевые классификаторы». Машинное обучение . 29 (2–3): 131–163. дои : 10.1023/А:1007465528199 .
11. Фридман Н., Линиал М., Нахман И., Пеер Д. (август 2000 г.). «Использование байесовских сетей для анализа данных о выражениях». Журнал вычислительной биологии . 7 (3–4): 601–20. CiteSeerX 10.1.1.191.139 . дои : 10.1089/106652700750050961. ПМИД  11108481. 
12. Кассенс Дж. (2011). «Обучение байесовской сети с помощью секущих плоскостей» (PDF) . Материалы 27-й ежегодной конференции по неопределенности в искусственном интеллекте : 153–160. arXiv : 1202.3713 . Бибкод : 2012arXiv1202.3713C.
13. Сканагатта М, де Кампос КП, Корани Г, Заффалон М (2015). «Изучение байесовских сетей с тысячами переменных». NIPS-15: Достижения в области нейронных систем обработки информации . Том. 28. Карран Ассошиэйтс. стр. 1855–1863.
14. Петижан Ф, Уэбб Дж.И., Николсон А.Е. (2013). Масштабирование лог-линейного анализа для многомерных данных (PDF) . Международная конференция по интеллектуальному анализу данных. Даллас, Техас, США: IEEE.
15. М. Сканагатта, Дж. Корани, К. П. де Кампос и М. Заффалон. Изучение байесовских сетей, ограниченных по ширине дерева, с тысячами переменных. В NIPS-16: Достижения в области нейронных систем обработки информации, 29, 2016 г.
16. Рассел и Норвиг 2003, стр. 496.
17. Рассел и Норвиг 2003, стр. 499.
18. Неаполитанский RE (2004). Изучение байесовских сетей. Прентис Холл. ISBN 978-0-13-012534-7.
19. Купер Г.Ф. (1990). «Вычислительная сложность вероятностного вывода с использованием байесовских сетей убеждений» (PDF) . Искусственный интеллект . 42 (2–3): 393–405. дои : 10.1016/0004-3702(90)90060-д. S2CID  43363498.
20. Дагум П., Луби М (1993). «Аппроксимация вероятностного вывода в байесовских сетях убеждений NP-трудна». Искусственный интеллект . 60 (1): 141–153. CiteSeerX 10.1.1.333.1586 . дои : 10.1016/0004-3702(93)90036-б. 
21. Д. Рот, О сложности приближенных рассуждений, IJCAI (1993).
22. Д. Рот, О сложности приближенных рассуждений, Искусственный интеллект (1996).
23. Дагум П., Луби М (1997). «Оптимальный алгоритм приближения для байесовского вывода». Искусственный интеллект . 93 (1–2): 1–27. CiteSeerX 10.1.1.36.7946 . дои : 10.1016/s0004-3702(97)00013-1. Архивировано из оригинала 6 июля 2017 г. Проверено 19 декабря 2015 г. 
24. Хоффман, Мэтью Д.; Гельман, Эндрю (2011). «Пробоотборник без разворота: адаптивная установка длины пути в гамильтоновом методе Монте-Карло». arXiv : 1111.4246 [stat.CO].
25. Перл Дж (1985). Байесовские сети: модель самоактивируемой памяти для доказательного рассуждения (Технический отчет Калифорнийского университета в Лос-Анджелесе CSD-850017) . Материалы 7-й конференции Общества когнитивных наук, Калифорнийский университет, Ирвин, Калифорния. стр. 329–334 . Проверено 1 мая 2009 г.
26. Байес Т. , Прайс (1763). «Очерк решения проблемы учения о шансах» . Философские труды Королевского общества . 53 : 370–418. дои : 10.1098/rstl.1763.0053 .
27. Перл Дж (15 сентября 1988). Вероятностные рассуждения в интеллектуальных системах. Сан-Франциско, Калифорния: Морган Кауфманн . п. 1988. ISBN 978-1-55860-479-7.
28. Неаполитанский RE (1989). Вероятностные рассуждения в экспертных системах: теория и алгоритмы. Уайли. ISBN 978-0-471-61840-9.

Рекомендации

• Бен Гал I (2007). «Байесовские сети» (PDF) . В Руджери Ф., Кеннетте Р.С., Фалтине Ф.В. (ред.). Страница поддержки . Энциклопедия статистики качества и надежности . Джон Уайли и сыновья . дои : 10.1002/9780470061572.eqr089 . ISBN 978-0-470-01861-3. Архивировано из оригинала (PDF) 23 ноября 2016 г. Проверено 27 августа 2007 г.
• Берч МакГрейн С. (2011). Теория, которая не умрет . Нью-Хейвен: Издательство Йельского университета .
• Боргельт С., Крузе Р. (март 2002 г.). Графические модели: методы анализа и анализа данных. Чичестер, Великобритания : Wiley . ISBN 978-0-470-84337-6.
• Борсук М.Е. (2008). «Экологическая информатика: байесовские сети». Йоргенсен , Свен Эрик , Фат, Брайан (ред.). Энциклопедия экологии . Эльзевир. ISBN 978-0-444-52033-3.
• Кастильо Э., Гутьеррес Х.М., Хади А.С. (1997). «Изучение байесовских сетей». Экспертные системы и вероятностные сетевые модели . Монографии по информатике. Нью-Йорк: Springer-Verlag . стр. 481–528. ISBN 978-0-387-94858-4.
• Комли Дж.В., Доу Д.Л. (июнь 2003 г.). «Общие байесовские сети и асимметричные языки». Материалы 2-й Гавайской международной конференции по статистике и смежным областям .
• Комли Дж.В., Доу Д.Л. (2005). «Минимальная длина сообщения и обобщенные байесовские сети с асимметричными языками». В полиции Грюнвальда, Мьюнг И.Дж., Питт М.А. (ред.). Достижения в минимальной длине описания: теория и приложения . Серия нейронной обработки информации. Кембридж, Массачусетс : Bradford Books ( MIT Press ) (опубликовано в апреле 2005 г.). стр. 265–294. ISBN 978-0-262-07262-5.(В этом документе деревья решений размещаются во внутренних узлах сетей Байеса с использованием минимальной длины сообщения ( MML ).
• Дарвич А. (2009). Моделирование и рассуждения с помощью байесовских сетей. Издательство Кембриджского университета . ISBN 978-0-521-88438-9.
• Доу, Дэвид Л. (31 мая 2011 г.). «Графические модели гибридных байесовских сетей, статистическая согласованность, инвариантность и уникальность» (PDF) . Философия статистики. Эльзевир. стр. 901–982. ISBN 978-0-08-093096-1.
• Фентон Н., Нил М.Э. (ноябрь 2007 г.). «Управление рисками в современном мире: применение байесовских сетей» (PDF) . Отчет о передаче знаний от Лондонского математического общества и Сети передачи знаний по промышленной математике . Лондон (Англия) : Лондонское математическое общество . Архивировано из оригинала (PDF) 14 мая 2008 г. Проверено 29 октября 2008 г.
• Фентон Н., Нил М.Э. (23 июля 2004 г.). «Объединение доказательств при анализе рисков с использованием байесовских сетей» (PDF) . Информационный бюллетень Клуба критических систем безопасности . Том. 13, нет. 4. Ньюкасл-апон-Тайн , Англия. стр. 8–13. Архивировано из оригинала (PDF) 27 сентября 2007 г.
• Гельман А., Карлин Дж.Б., Стерн Х.С., Рубин Д.Б. (2003). «Часть II: Основы байесовского анализа данных: глава 5, иерархические модели». Байесовский анализ данных. ЦРК Пресс . стр. 120–. ISBN 978-1-58488-388-3.
• Хеккерман, Дэвид (1 марта 1995 г.). «Учебное пособие по обучению с помощью байесовских сетей». В Иордании, Майкл Ирвин (ред.). Обучение графическим моделям . Адаптивные вычисления и машинное обучение. Кембридж, Массачусетс : MIT Press (опубликовано в 1998 г.). стр. 301–354. ISBN 978-0-262-60032-3. Архивировано из оригинала 19 июля 2006 года . Проверено 15 сентября 2006 г.{{cite book}}: CS1 maint: bot: original URL status unknown (link): Также появляется как Хеккерман, Дэвид (март 1997 г.). «Байесовские сети для интеллектуального анализа данных». Интеллектуальный анализ данных и обнаружение знаний . 1 (1): 79–119. дои : 10.1023/А: 1009730122752. S2CID  6294315.

Более ранняя версия опубликована под названием Microsoft Research , 1 марта 1995 г. Статья посвящена изучению как параметров, так и структур в байесовских сетях.

• Йенсен Ф.В., Нильсен Т.Д. (6 июня 2007 г.). Байесовские сети и графы решений. Серия «Информатика и статистика» (2-е изд.). Нью-Йорк : Springer-Verlag . ISBN 978-0-387-68281-5.
• Карими К., Гамильтон HJ (2000). «Нахождение временных отношений: причинно-следственные байесовские сети против C4.5» (PDF) . Двенадцатый международный симпозиум по методологиям интеллектуальных систем .
• Корб КБ, Николсон А.Е. (декабрь 2010 г.). Байесовский искусственный интеллект. CRC Информатика и анализ данных (2-е изд.). Чепмен и Холл ( CRC Press ). дои : 10.1007/s10044-004-0214-5. ISBN 978-1-58488-387-6. S2CID  22138783.
• Ланн Д., Шпигельхальтер Д., Томас А., Бест Н. (ноябрь 2009 г.). «Проект BUGS: эволюция, критика и будущие направления». Статистика в медицине . 28 (25): 3049–67. дои : 10.1002/сим.3680. PMID  19630097. S2CID  7717482.
• Нил М., Фентон Н., Тейлор М. (август 2005 г.). Гринберг, Майкл Р. (ред.). «Использование байесовских сетей для моделирования ожидаемых и неожиданных эксплуатационных потерь» (PDF) . Анализ риска . 25 (4): 963–72. дои : 10.1111/j.1539-6924.2005.00641.x. PMID  16268944. S2CID  3254505.
• Перл Дж (сентябрь 1986 г.). «Слияние, распространение и структурирование сетей убеждений». Искусственный интеллект . 29 (3): 241–288. дои : 10.1016/0004-3702(86)90072-X.
• Перл Дж (1988). Вероятностные рассуждения в интеллектуальных системах: сети правдоподобных выводов. Серия «Представление и рассуждение» (2-е печатное изд.). Сан-Франциско, Калифорния : Морган Кауфманн . ISBN 978-0-934613-73-6.
• Перл Дж ., Рассел С. (ноябрь 2002 г.). «Байесовские сети». В Арбиб М.А. (ред.). Справочник по теории мозга и нейронным сетям. Кембридж, Массачусетс : Bradford Books ( MIT Press ). стр. 157–160. ISBN 978-0-262-01197-6.
• Рассел, Стюарт Дж .; Норвиг, Питер (2003), Искусственный интеллект: современный подход (2-е изд.), Аппер-Сэддл-Ривер, Нью-Джерси: Прентис-Холл, ISBN 0-13-790395-2.
• Чжан Н.Л., Пул Д. (май 1994 г.). «Простой подход к вычислениям байесовской сети» (PDF) . Материалы десятой канадской конференции по искусственному интеллекту (AI-94), проводимой раз в два года. : 171–178.В этой статье представлено исключение переменных для сетей убеждений.

дальнейшее чтение

• Конради С., Жуфф Л. (01.07.2015). Байесовские сети и BayesiaLab – практическое введение для исследователей. Франклин, Теннесси: Байесианские США. ISBN 978-0-9965333-0-0.
• Чарняк Э. (зима 1991 г.). «Байесовские сети без разрывов» (PDF) . Журнал ИИ .
• Крузе Р., Боргельт С., Клавонн Ф., Мовес С., Штайнбрехер М., Хелд П. (2013). Вычислительный интеллект. Методологическое введение. Лондон: Springer-Verlag. ISBN 978-1-4471-5012-1.
• Боргельт С., Штайнбрехер М., Крузе Р. (2009). Графические модели – представления для обучения, рассуждения и интеллектуального анализа данных (второе изд.). Чичестер: Уайли. ISBN 978-0-470-74956-2.

Внешние ссылки

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