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

Материал из wikixw
Перейти к навигации Перейти к поиску

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

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

Простая байесовская сеть. Дождь влияет на активацию разбрызгивателя, а дождь и разбрызгиватель влияют на влажность травы.

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

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

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

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

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

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

где G = трава влажная (true/false) , S = разбрызгиватель включен (true/false) и R = дождь (true/false) .

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

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

Затем числовые результаты (подписанные соответствующими значениями переменных):

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

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

Прогнозировать удар поворачивать спринклер дальше:

с термином Pr ( S = T | R ) удалены, показывая, что действие влияет на траву, но не дождь. Эти предсказания могут оказаться невыполнимыми, учитывая ненаблюдаемые переменные, как и в большинстве проблем оценки политики. Тем не менее, эффект действия do ( x ) (x)все еще может быть предсказан, когда выполняется критерий задней двери.[1] [2] в нем говорится, что если множество Z узлов можно наблюдать, что d-отделяет [3] (или блокирует) все задние пути от X до Y, то

Путь задней двери-это путь, который заканчивается стрелкой в 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-calculus" [1] [4] и проверить, могут ли все члены do быть удалены из выражения этого отношения, тем самым подтверждая, что требуемая величина оценивается по частотным данным.[5]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Узор Модель
Цепь Х ->Y ->Z
Вилка Х <-Y-> Z
Коллайдер Х ->Y<- Z


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

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

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

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

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

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

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

Главная статья: байесовская статистика

Учитывая данные x !и параметр θ тета , простой байесовский анализ начинается с предшествующей вероятности ) p ( θ ) p ()и вероятности p ( x ∣ θ ) для вычисления задней вероятности p ( θ ∣ x ) ∝ p ( x ∣ θ ) p ( θ ) propto p(x\mid

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

   p ( θ , φ | x ) ∝ p ( x | θ ) p ( θ | φ ) p ( φ ) .

Это самый простой пример иерархической модели Байеса .[ требуется разъяснение]

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

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

Учитывая измеренные величины x 1 , … , x n \!, каждая с нормально распределенными ошибками известного стандартного отклонения σ {\displaystyle \sigma \,\!} "Сигма",!,
  • x i ∼ N ( θ i , σ 2 )

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

  • θ i = x i

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

  • x i ∼ N ( θ i , σ 2 ) ,
  • θ i ∼ N ( φ , τ 2 )

с неправильными Приорами φ ∼ \sim плоскими, τ ∼ плоскими ∈ ( 0 , ∞ ). Когда n ≥ 3 3это-идентифицированная модель (т. е. существует уникальное решение для параметров модели), и задние распределения человека θ i a _{i}будут иметь тенденцию двигаться или уменьшаться от оценок максимального правдоподобия к их общему среднему значению. Это сжатие является типичным поведением в иерархических моделях Байеса.

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

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

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

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

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

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

X-байесовская сеть относительно G, если ее совместная функция плотности вероятности (относительно меры продукта ) может быть записана как произведение отдельных функций плотности, обусловленных их родительскими переменными

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

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

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

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

Локальное Марковское свойство[править]

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

  • X v ⊥ ⊥ X V ∖ de ⁡ ( v ) ∣ X pa ⁡ ( v ) for all v ∈ V

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

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

  • P ( X v = x v ∣ X i = x i для каждого X i , который не является потомком X v ) = P ( X v = x v ∣ X j = x j }для каждого X j который является родителем X v )

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

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

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

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

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

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

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

  • P содержит (но не должен быть полностью) направленную цепочку, u … ← m ← … v }или u … → m → … v , такой, что средний узел m находится в Z,
  • P содержит вилку, u … ← m → … v , такую, что средний узел m находится в Z, или
  • P содержит перевернутую вилку (или коллайдер) u … → m ← … v , так что средний узел m не находится в Z , а потомок m не находится в Z .

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

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

  • X u ⊥ ⊥ X v ∣ X Z

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

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

  • a → b → c and a ← b ← c

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

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

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

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

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

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

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

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

  • Просто еще один Gibbs sampler (JAGS) - Open-Source альтернатива WinBUGS. Использует выборку Гиббса.
  • OpenBUGS-разработка WinBUGS с открытым исходным кодом.
  • SPSS Modeler-коммерческое программное обеспечение, включающее в себя реализацию для байесовских сетей.
  • Stan (программное обеспечение)-Stan представляет собой пакет с открытым исходным кодом для получения байесовского вывода с использованием no-U-Turn sampler, варианта Гамильтонова Монте-Карло.
  • WinBUGS-одна из первых вычислительных реализаций пробоотборников MCMC. Больше не поддерживается.

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

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

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

В конце 1980-х вероятностные рассуждения Перла в интеллектуальных системах и неаполитанские вероятностные рассуждения в экспертных системах суммировали их свойства и установили их как область исследования.

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

Читать[править]

/books.google.kz/books?id=I8Fa-LKDpF0C&redir_esc=y

Пруф[править]

/bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-7-514

Источник — https://wikixw.ru/index.php?title=Байесовская_сеть&oldid=5261