Байесовская сеть - Bayesian network

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

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

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

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

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

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

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

${\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)}$ удалено, показывая, что действие влияет на траву, но не на дождь.

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

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

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

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

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

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

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

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

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

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

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

Обучение параметрам

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

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

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

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

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

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

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

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

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

Определения и понятия

Смотрите также: Глоссарий теории графов § Направленные ациклические графы

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

Определение факторизации

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

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

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

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

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

Местная марковская собственность

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

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

где де (v) - множество потомков и V де (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. грамм такой, что Икс удовлетворяет локальному марковскому свойству относительно грамм. Иногда это причинный DAG. Условные распределения вероятностей каждой переменной с учетом ее родителей в грамм оцениваются. Во многих случаях, в частности, в случае дискретных переменных, если совместное распределение Икс является продуктом этих условных распределений, то Икс является байесовской сетью относительно грамм.^[18]

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

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

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

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

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

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

Узлы ты и v находятся d-разделены по Z если все тропы между ними d-разделено. Если ты и v не d-разделены, они d-связаны.

Икс является байесовской сетью относительно грамм если для любых двух узлов ты, v:

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

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

Причинные сети

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

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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

Примечания

1. Жемчужина, Иудея (2000). Причинная связь: модели, рассуждения и выводы. Издательство Кембриджского университета. ISBN  978-0-521-77362-1. OCLC  42291253.
2. "Критерий задней двери" (PDF). Получено 2014-09-18.
3. «г-разлука без слез» (PDF). Получено 2014-09-18.
4. Перл Дж (1994). «Вероятностное исчисление действий». В Лопес де Мантарас Р., Пул Д. (ред.). UAI'94 Труды Десятой международной конференции по неопределенности в искусственном интеллекте. Сан-Матео, Калифорния: Морган Кауфманн. С. 454–462. arXiv:1302.6835. Bibcode:2013arXiv1302.6835P. ISBN  1-55860-332-8.
5. Шпицер I, Перл Дж (2006). «Идентификация условных интервенционных распределений». В Dechter R, Richardson TS (ред.). Материалы двадцать второй конференции по неопределенности в искусственном интеллекте. Корваллис, Орегон: AUAI Press. С. 437–444. arXiv:1206.6876.
6. Ребане Дж., Перл Дж. (1987). «Восстановление причинных полидеревьев из статистических данных». Труды, 3-й семинар по неопределенности в ИИ. Сиэтл, Вашингтон. С. 222–228. arXiv:1304.2736.
7. Спиртес П., Глимур С. (1991). «Алгоритм быстрого восстановления разреженных причинных графов» (PDF). Компьютерный обзор социальных наук. 9 (1): 62–72. Дои:10.1177/089443939100900106. S2CID  38398322.
8. Спиртес П., Глимур С. Н., Шайнс Р. (1993). Причинно-следственная связь, прогнозирование и поиск (1-е изд.). Springer-Verlag. ISBN  978-0-387-97979-3.
9. Верма Т., Перл Дж. (1991). «Эквивалентность и синтез причинных моделей». В Bonissone P, Henrion M, Kanal LN, Lemmer JF (ред.). 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. PMID  11108481.
12. Куссенс Дж (2011). «Байесовское сетевое обучение с режущими плоскостями» (PDF). Материалы 27-й ежегодной конференции по неопределенности в искусственном интеллекте: 153–160. arXiv:1202.3713. Bibcode:2012arXiv1202.3713C.
13. Scanagatta M, de Campos CP, Corani G, Zaffalon M (2015). «Изучение байесовских сетей с тысячами переменных». NIPS-15: Достижения в системах обработки нейронной информации. 28. Curran Associates. С. 1855–1863.
14. Петижан Ф., Уэбб Г.И., Николсон А.Е. (2013). Масштабирование лог-линейного анализа до многомерных данных (PDF). Международная конференция по интеллектуальному анализу данных. Даллас, Техас, США: IEEE.
15. М. Сканагатта, Г. Корани, К. П. де Кампос и М. Заффалон. Изучение байесовских сетей с ограничением по ширине дерева с тысячами переменных. В NIPS-16: Достижения в системах обработки нейронной информации 29, 2016.
16. Рассел и Норвиг, 2003 г., п. 496. Ошибка sfn: цель отсутствует: CITEREFRussellNorvig2003 (помощь)
17. Рассел и Норвиг, 2003 г., п. 499. Ошибка sfn: цель отсутствует: CITEREFRussellNorvig2003 (помощь)
18. Неаполитанский RE (2004). Изучение байесовских сетей. Прентис Холл. ISBN  978-0-13-012534-7.
19. Купер Г.Ф. (1990). «Вычислительная сложность вероятностного вывода с использованием байесовских сетей доверия» (PDF). Искусственный интеллект. 42 (2–3): 393–405. Дои:10.1016 / 0004-3702 (90) 90060-д.
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 / с0004-3702 (97) 00013-1. Архивировано из оригинал на 2017-07-06. Получено 2015-12-19.
24. Хоффман, Мэтью Д.; Гельман, Андрей (2011). «Пробоотборник без разворота: адаптивная установка длины пути в гамильтониане Монте-Карло». arXiv:1111.4246. Bibcode:2011arXiv1111.4246H.
25. Жемчуг J (1985). Байесовские сети: модель самоактивирующейся памяти для доказательных рассуждений (Технический отчет UCLA CSD-850017). Материалы 7-й конференции Общества когнитивных наук, Калифорнийский университет, Ирвин, Калифорния. стр. 329–334. Получено 2009-05-01.
26. Байес Т, Прайс (1763 г.). «Очерк решения проблемы в доктрине шансов». Философские труды Королевского общества. 53: 370–418. Дои:10.1098 / рстл.1763.0053.
27. Перл Дж (1988-09-15). Вероятностные рассуждения в интеллектуальных системах. Сан-Франциско, Калифорния: Морган Кауфманн. п. 1988 г. ISBN  978-1558604797.
28. Неаполитанский RE (1989). Вероятностные рассуждения в экспертных системах: теория и алгоритмы. Вайли. ISBN  978-0-471-61840-9.

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

• Бен Гал I (2007). «Байесовские сети» (PDF). В Ruggeri F, Kennett RS, Faltin FW (ред.). Страница поддержки. Энциклопедия статистики качества и надежности. Джон Уайли и сыновья. Дои:10.1002 / 9780470061572.eqr089. ISBN  978-0-470-01861-3.
• Бертч МакГрейн С (2011). Теория, которая не умрет. Новый рай: Издательство Йельского университета.
• Боргельт C, Kruse R (Март 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). «Минимальная длина сообщения и обобщенные байесовские сети с асимметричными языками». В Grünwald PD, Myung IJ, Pitt MA (ред.). Достижения в области минимальной длины описания: теория и приложения. Серия обработки нейронной информации. Кембридж, Массачусетс: Bradford Books (MIT Press ) (опубликовано в апреле 2005 г.). С. 265–294. ISBN  978-0-262-07262-5. (В этой статье деревья решений во внутренних узлах байесовских сетей с использованием Минимальная длина сообщения (MML ).
• Дарвиче А (2009). Моделирование и рассуждение с помощью байесовских сетей. Издательство Кембриджского университета. ISBN  978-0521884389.
• Доу, Дэвид Л. (31 мая 2011 г.). «Гибридные байесовские сетевые графические модели, статистическая согласованность, инвариантность и уникальность» (PDF). Философия статистики. Эльзевир. стр.901–982. ISBN  9780080930961.
• Фентон Н., Нил М.Э. (ноябрь 2007 г.). «Управление рисками в современном мире: приложения байесовских сетей» (PDF). Отчет о передаче знаний Лондонского математического общества и Сети передачи знаний по промышленной математике. Лондон, Англия): Лондонское математическое общество.
• Фентон Н., Нил М.Э. (23 июля 2004 г.). «Объединение доказательств в анализе риска с использованием байесовских сетей» (PDF). Информационный бюллетень Клуба по критическим системам безопасности. 13 (4). Ньюкасл-апон-Тайн, Англия. С. 8–13. Архивировано из оригинал (PDF) на 2007-09-27.
• Гельман А, Карлин Дж.Б., Стерн Х.С., Рубин Д.Б. (2003). «Часть II: Основы байесовского анализа данных: Глава 5 Иерархические модели». Байесовский анализ данных. CRC Press. С. 120–. ISBN  978-1-58488-388-3.
• Хекерман, Дэвид (1 марта 1995 г.). «Учебное пособие по обучению с использованием байесовских сетей». В Иордании, Майкл Ирвин (ред.). Обучение в графических моделях. Адаптивные вычисления и машинное обучение. Кембридж, Массачусетс: MIT Press (опубликовано в 1998 г.). С. 301–354. ISBN  978-0-262-60032-3.

Также отображается как Хекерман, Дэвид (март 1997 г.). «Байесовские сети для интеллектуального анализа данных». Интеллектуальный анализ данных и обнаружение знаний. 1 (1): 79–119. Дои:10.1023 / А: 1009730122752. S2CID  6294315.

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

• Дженсен Ф.В., Нильсен ТД (6 июня 2007 г.). Байесовские сети и графы решений. Серия "Информатика и статистика" (2-е изд.). Нью-Йорк: Springer-Verlag. ISBN  978-0-387-68281-5.
• Карими К., Гамильтон HJ (2000). «Нахождение временных отношений: причинно-следственные байесовские сети против C4. 5» (PDF). Двенадцатый международный симпозиум по методологиям интеллектуальных систем.
• Корб КБ, Николсон А.Е. (декабрь 2010 г.). Байесовский искусственный интеллект. CRC Computer Science & Data Analysis (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 / sim.3680. PMID  19630097.
• Нил М., Фентон Н., Портной М. (август 2005 г.). Гринберг, Майкл Р. (ред.). «Использование байесовских сетей для моделирования ожидаемых и непредвиденных операционных потерь» (PDF). Анализ риска. 25 (4): 963–72. Дои:10.1111 / j.1539-6924.2005.00641.x. PMID  16268944. S2CID  3254505.
• Жемчуг J (Сентябрь 1986 г.). «Слияние, распространение и структурирование в сетях убеждений». Искусственный интеллект. 29 (3): 241–288. Дои:10.1016 / 0004-3702 (86) 90072-Х.
• Жемчуг J (1988). Вероятностное мышление в интеллектуальных системах: сети правдоподобных выводов. Серия представлений и рассуждений (2-е изд.). Сан - Франциско, Калифорния: Морган Кауфманн. ISBN  978-0-934613-73-6.
• Жемчуг J, Рассел С. (Ноябрь 2002 г.). «Байесовские сети». В Арбиб М.А. (ред.). Справочник по теории мозга и нейронным сетям. Кембридж, Массачусетс: 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. В этой статье представлено исключение переменных для сетей убеждений.

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

• Конради С., Джофф Л. (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.

внешняя ссылка

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