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

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

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

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

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

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

Пример

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

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

Совместная функция вероятности , согласно цепному правилу вероятности ,

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

Используя расширение для функции совместной вероятности и условные вероятности из таблиц условных вероятностей (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)}$

Эти прогнозы могут быть невозможны при наличии ненаблюдаемых переменных, как в большинстве проблем оценки политики. Однако эффект действия все еще может быть предсказан, когда критерий бэкдора выполняется. ^{[2] [3]} Он утверждает, что если можно наблюдать набор Z узлов, который d-разделяет ^[4] (или блокирует) все бэкдор-пути от 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 » ^{[2] [5]} и проверить, можно ли удалить все члены do из выражения этой связи, тем самым подтвердив, что желаемая величина может быть оценена на основе данных о частоте. ^[6]

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

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

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

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

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

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

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

Параметр обучения

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

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

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

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

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

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

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

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

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

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

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

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

Статистическое введение

При наличии данных и параметров простой байесовский анализ начинается с априорной вероятности ( приорного значения ) и правдоподобия для вычисления апостериорной вероятности . ${\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, если ее совместная функция плотности вероятности (относительно меры произведения ) может быть записана как произведение отдельных функций плотности, обусловленных их родительскими переменными: ^[17]

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

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

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

${\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, если она удовлетворяет локальному марковскому свойству : каждая переменная условно независима от своих непотомков, учитывая ее родительские переменные: ^[18]

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

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

Структура предельной независимости

В целом, обучение байесовской сети по данным известно как NP-трудная задача . ^[19] Это отчасти связано с комбинаторным взрывом перечисления DAG по мере увеличения числа переменных. Тем не менее, понимание базовой байесовской сети может быть получено из данных за полиномиальное время, если сосредоточиться на ее структуре маргинальной независимости: ^[20] в то время как условные утверждения независимости распределения, смоделированного байесовской сетью, кодируются DAG (согласно факторизации и свойствам Маркова выше), ее маргинальные утверждения независимости — условные утверждения независимости, в которых множество обусловливания пусто — кодируются простым неориентированным графом со специальными свойствами, такими как равные числа пересечений и независимости .

Разработка байесовских сетей

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

марковское одеяло

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

г-разделение

Это определение можно сделать более общим, определив «d»-разделение двух узлов, где d означает направленный. ^[2] Сначала мы определим «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 . ^[2] Используя эту семантику, можно предсказать влияние внешних вмешательств на основе данных, полученных до вмешательства.

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

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

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

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

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

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

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

История

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

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

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

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

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

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

Примечания

1. Руджери, Фабрицио; Кенетт, Рон С.; Фалтин, Фредерик В., ред. (14 декабря 2007 г.). Энциклопедия статистики по качеству и надежности (1-е изд.). Wiley. стр. 1. doi :10.1002/9780470061572.eqr089. ISBN 978-0-470-01861-3.
2. Pearl, Judea (2000). Причинность: модели, рассуждения и выводы. Cambridge University Press . ISBN 978-0-521-77362-1. OCLC  42291253.
3. "Критерий Back-Door" (PDF) . Получено 2014-09-18 .
4. "d-Разлука без слез" (PDF) . Получено 2014-09-18 .
5. Pearl J (1994). "Вероятностное исчисление действий". В Lopez de Mantaras R, Poole D (ред.). UAI'94 Труды Десятой международной конференции по неопределенности в искусственном интеллекте . Сан-Матео, Калифорния: Morgan Kaufmann . С. 454–462. arXiv : 1302.6835 . Bibcode : 2013arXiv1302.6835P. ISBN 1-55860-332-8.
6. Шпицер И, Перл Дж (2006). «Идентификация условных интервенционных распределений». В Dechter R, Richardson TS (ред.). Труды Двадцать второй конференции по неопределенности в искусственном интеллекте . Корваллис, Орегон: AUAI Press. стр. 437–444. arXiv : 1206.6876 .
7. Rebane G, Pearl J (1987). «Восстановление каузальных поли-деревьев из статистических данных». Труды 3-го семинара по неопределенности в ИИ . Сиэтл, Вашингтон. С. 222–228. arXiv : 1304.2736 .{{cite book}}: CS1 maint: location missing publisher (link)
8. Spirtes P, Glymour C (1991). "Алгоритм быстрого восстановления разреженных причинных графов" (PDF) . Social Science Computer Review . 9 (1): 62–72. CiteSeerX 10.1.1.650.2922 . doi :10.1177/089443939100900106. S2CID  38398322. 
9. Спиртес П., Глимур CN, Шайнс Р. (1993). Причинно-следственная связь, прогнозирование и поиск (1-е изд.). Спрингер-Верлаг. ISBN 978-0-387-97979-3.
10. Verma T, Pearl J (1991). «Эквивалентность и синтез причинных моделей». В Bonissone P, Henrion M, Kanal LN, Lemmer JF (ред.). Труды Шестой ежегодной конференции UAI '90 по неопределенности в искусственном интеллекте . Elsevier. стр. 255–270. ISBN 0-444-89264-8.
11. Фридман Н., Гейгер Д., Голдшмидт М. (ноябрь 1997 г.). «Байесовские сетевые классификаторы». Машинное обучение . 29 (2–3): 131–163. doi : 10.1023/A:1007465528199 .
12. Фридман Н., Линиал М., Нахман И., Пеер Д. (август 2000 г.). «Использование байесовских сетей для анализа данных экспрессии». Журнал вычислительной биологии . 7 (3–4): 601–20. CiteSeerX 10.1.1.191.139 . doi :10.1089/106652700750050961. PMID  11108481. 
13. Cussens J (2011). «Обучение байесовских сетей с помощью секущих плоскостей» (PDF) . Труды 27-й конференции Ежегодная конференция по неопределенности в искусственном интеллекте : 153–160. arXiv : 1202.3713 . Bibcode : 2012arXiv1202.3713C.
14. Scanagatta M, de Campos CP, Corani G, Zaffalon M (2015). «Изучение байесовских сетей с тысячами переменных». NIPS-15: Достижения в области нейронных систем обработки информации . Том 28. Curran Associates. С. 1855–1863.
15. Petitjean F, Webb GI, Nicholson AE (2013). Масштабирование логлинейного анализа для многомерных данных (PDF) . Международная конференция по интеллектуальному анализу данных. Даллас, Техас, США: IEEE.
16. M. Scanagatta, G. Corani, CP de Campos и M. Zaffalon. Обучение байесовских сетей с ограниченной шириной дерева и тысячами переменных. В NIPS-16: Достижения в области нейронных систем обработки информации 29, 2016.
17. Russell & Norvig 2003, стр. 496.
18. Russell & Norvig 2003, стр. 499.
19. Чикеринг, Дэвид М.; Хекерман, Дэвид; Мик, Кристофер (2004). «Обучение байесовских сетей на больших выборках является NP-трудным» (PDF) . Журнал исследований машинного обучения . 5 : 1287–1330.
20. Deligeorgaki, Danai; Markham, Alex; Misra, Pratik; Solus, Liam (2023). «Комбинаторные и алгебраические перспективы структуры маргинальной независимости байесовских сетей». Алгебраическая статистика . 14 (2): 233–286. arXiv : 2210.00822 . doi : 10.2140/astat.2023.14.233.
21. Neapolitan RE (2004). Изучение байесовских сетей. Prentice Hall. ISBN 978-0-13-012534-7.
22. Купер ГФ (1990). «Вычислительная сложность вероятностного вывода с использованием байесовских сетей доверия» (PDF) . Искусственный интеллект . 42 (2–3): 393–405. doi :10.1016/0004-3702(90)90060-d. S2CID  43363498.
23. Дагум П., Луби М. (1993). «Аппроксимационный вероятностный вывод в байесовских сетях убеждений — NP-трудный». Искусственный интеллект . 60 (1): 141–153. CiteSeerX 10.1.1.333.1586 . doi :10.1016/0004-3702(93)90036-b. 
24. Д. Рот, О трудности приближенных рассуждений, IJCAI (1993)
25. Д. Рот, О трудности приблизительных рассуждений, Искусственный интеллект (1996)
26. Дагум П., Луби М. (1997). «Оптимальный алгоритм аппроксимации для байесовского вывода». Искусственный интеллект . 93 (1–2): 1–27. CiteSeerX 10.1.1.36.7946 . doi :10.1016/s0004-3702(97)00013-1. Архивировано из оригинала 2017-07-06 . Получено 2015-12-19 . 
27. Хоффман, Мэтью Д.; Гельман, Эндрю (2011). «Сэмплер без разворота: адаптивная установка длин путей в гамильтоновом Монте-Карло». arXiv : 1111.4246 [stat.CO].
28. Pearl J (1985). Байесовские сети: модель самоактивируемой памяти для доказательного рассуждения (Технический отчет UCLA CSD-850017) . Труды 7-й конференции Общества когнитивной науки, Калифорнийский университет, Ирвайн, Калифорния. С. 329–334 . Получено 01.05.2009 .
29. Байес Т. , Прайс (1763). "Опыт решения проблемы в учении о случайностях" . Философские труды Королевского общества . 53 : 370–418. doi : 10.1098/rstl.1763.0053 .
30. Pearl J (1988-09-15). Вероятностное рассуждение в интеллектуальных системах. Сан-Франциско, Калифорния: Morgan Kaufmann . стр. 1988. ISBN 978-1-55860-479-7.
31. Неаполитан RE (1989). Вероятностные рассуждения в экспертных системах: теория и алгоритмы. Wiley. ISBN 978-0-471-61840-9.

Ссылки

• Ben Gal I (2007). "Bayesian Networks" (PDF) . В Ruggeri F, Kennett RS, Faltin FW (ред.). Support-Page . Encyclopedia of Statistics in Quality and Reliability . John Wiley & Sons . doi : 10.1002/9780470061572.eqr089 . ISBN 978-0-470-01861-3. Архивировано из оригинала (PDF) 2016-11-23 . Получено 2007-08-27 .
• Берч Макгрейн С. (2011). Теория, которая не умрет . Нью-Хейвен: Издательство Йельского университета .
• Borgelt C, Kruse R (март 2002 г.). Графические модели: методы анализа и добычи данных. Чичестер, Великобритания : Wiley . ISBN 978-0-470-84337-6.
• Борсук М.Е. (2008). "Экологическая информатика: байесовские сети". В Йоргенсен, Свен Эрик , Фат, Брайан (ред.). Энциклопедия экологии . Elsevier. ISBN 978-0-444-52033-3.
• Castillo E, Gutiérrez JM, Hadi AS (1997). "Изучение байесовских сетей". Экспертные системы и вероятностные сетевые модели . Монографии по информатике. Нью-Йорк: Springer-Verlag . С. 481–528. ISBN 978-0-387-94858-4.
• Comley JW, Dowe DL (июнь 2003 г.). «Общие байесовские сети и асимметричные языки». Труды 2-й Гавайской международной конференции по статистике и смежным областям .
• Comley JW, Dowe DL (2005). "Минимальная длина сообщения и обобщенные байесовские сети с асимметричными языками". В Grünwald PD, Myung IJ, Pitt MA (ред.). Достижения в области минимальной длины описания: теория и приложения . Серия по нейронной обработке информации. Кембридж, Массачусетс : Bradford Books ( MIT Press ) (опубликовано в апреле 2005 г.). стр. 265–294. ISBN 978-0-262-07262-5.(В этой статье деревья решений помещаются во внутренние узлы сетей Байеса с использованием минимальной длины сообщения ( MML ).
• Darwiche A (2009). Моделирование и рассуждения с использованием байесовских сетей. Cambridge University Press . ISBN 978-0-521-88438-9.
• Доу, Дэвид Л. (2011-05-31). "Графические модели гибридной байесовской сети, статистическая согласованность, инвариантность и уникальность" (PDF) . Философия статистики. Elsevier. С. 901–982. ISBN 978-0-08-093096-1.
• Fenton N, Neil ME (ноябрь 2007 г.). "Управление рисками в современном мире: применение байесовских сетей" (PDF) . Отчет о передаче знаний Лондонского математического общества и Сети передачи знаний по промышленной математике . Лондон (Англия) : Лондонское математическое общество . Архивировано из оригинала (PDF) 2008-05-14 . Получено 2008-10-29 .
• Fenton N, Neil ME (23 июля 2004 г.). «Объединение доказательств в анализе риска с использованием байесовских сетей» (PDF) . Информационный бюллетень клуба критических систем безопасности . Том 13, № 4. Ньюкасл-апон-Тайн , Англия. стр. 8–13. Архивировано из оригинала (PDF) 27.09.2007.
• Gelman A, Carlin JB, Stern HS, Rubin DB (2003). "Часть II: Основы байесовского анализа данных: Гл. 5 Иерархические модели". Байесовский анализ данных. CRC Press . стр. 120–. ISBN 978-1-58488-388-3.
• Хекерман, Дэвид (1 марта 1995 г.). «Учебник по обучению с помощью байесовских сетей». В Jordan, Майкл Ирвин (ред.). Обучение на графических моделях . Адаптивные вычисления и машинное обучение. Кембридж, Массачусетс : 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. doi :10.1023/A:1009730122752. S2CID  6294315.

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

• Jensen FV, Nielsen TD (6 июня 2007 г.). Байесовские сети и графы решений. Серия «Информационная наука и статистика» (2-е изд.). Нью-Йорк : Springer-Verlag . ISBN 978-0-387-68281-5.
• Карими К, Гамильтон Х.Дж. (2000). "Поиск временных связей: каузальные байесовские сети против C4. 5" (PDF) . Двенадцатый международный симпозиум по методологиям для интеллектуальных систем .
• Korb KB, Nicholson AE (декабрь 2010 г.). Байесовский искусственный интеллект. CRC Computer Science & Data Analysis (2-е изд.). Chapman & Hall ( CRC Press ). doi :10.1007/s10044-004-0214-5. ISBN 978-1-58488-387-6. S2CID  22138783.
• Lunn D, Spiegelhalter D, Thomas A, Best N (ноябрь 2009 г.). «Проект BUGS: эволюция, критика и будущие направления». Статистика в медицине . 28 (25): 3049–67. doi :10.1002/sim.3680. PMID  19630097. S2CID  7717482.
• Neil M, Fenton N, Tailor M (август 2005 г.). Greenberg, Michael R. (ред.). «Использование байесовских сетей для моделирования ожидаемых и непредвиденных операционных потерь» (PDF) . Risk Analysis . 25 (4): 963–72. doi :10.1111/j.1539-6924.2005.00641.x. PMID  16268944. S2CID  3254505.
• Pearl J (сентябрь 1986 г.). «Слияние, распространение и структурирование в сетях убеждений». Искусственный интеллект . 29 (3): 241–288. doi :10.1016/0004-3702(86)90072-X.
• Pearl J (1988). Вероятностное рассуждение в интеллектуальных системах: сети правдоподобного вывода. Серия «Представление и рассуждение» (2-е издание). Сан-Франциско, Калифорния : Morgan Kaufmann . ISBN 978-0-934613-73-6.
• Pearl J , Russell S (ноябрь 2002 г.). «Байесовские сети». В Arbib MA (ред.). Справочник по теории мозга и нейронным сетям. Кембридж, Массачусетс : Bradford Books ( MIT Press ). стр. 157–160. ISBN 978-0-262-01197-6.
• Рассел, Стюарт Дж.; Норвиг , Питер (2003), Искусственный интеллект: Современный подход (2-е изд.), Аппер Сэдл Ривер, Нью-Джерси: Prentice Hall, ISBN 0-13-790395-2.
• Чжан Н. Л., Пул Д. (май 1994 г.). «Простой подход к вычислениям байесовских сетей» (PDF) . Труды Десятой двухгодичной канадской конференции по искусственному интеллекту (AI-94). : 171–178.В данной статье представлено исключение переменных для сетей убеждений.

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

• Conrady S, Jouffe L (2015-07-01). Bayesian Networks and BayesiaLab – Практическое введение для исследователей. Франклин, Теннесси: Bayesian USA. ISBN 978-0-9965333-0-0.
• Charniak E (Зима 1991). "Байесовские сети без слез" (PDF) . Журнал AI .
• Крузе Р., Боргельт С., Клавонн Ф., Мовес С., Штайнбрехер М., Хелд П. (2013). Вычислительный интеллект. Методологическое введение. Лондон: Springer-Verlag. ISBN 978-1-4471-5012-1.
• Borgelt C, Steinbrecher M, Kruse R (2009). Графические модели – представления для обучения, рассуждения и добычи данных (второе изд.). Чичестер: Wiley. ISBN 978-0-470-74956-2.

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

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