Введение

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

Байесовская сеть (также известная как сеть Байеса, Bayes net, сеть убеждений или сеть решений) – это вероятностная графическая модель, представляющая набор переменных и их условные зависимости с помощью направленного ациклического графа (DAG). Хотя это одна из нескольких форм причинно-следственного представления, причинно-следственные сети являются частными случаями байесовских сетей. Байесовские сети идеально подходят для анализа произошедшего события и прогнозирования вероятности того, что какая-либо из нескольких известных возможных причин была способствующим фактором. Например, байесовская сеть может представлять вероятностные взаимосвязи между заболеваниями и симптомами. При наличии симптомов сеть может быть использована для вычисления вероятностей наличия различных заболеваний. Эффективные алгоритмы позволяют выполнять логический вывод и обучение в байесовских сетях. Байесовские сети, моделирующие последовательности переменных (например, речевые сигналы или последовательности белков), называются динамическими байесовскими сетями. Обобщения байесовских сетей, способные представлять и решать задачи принятия решений в условиях неопределенности, называются диаграммами влияния.

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

Формально, байесовские сети являются направленными ациклическими графами (DAG), узлы которых представляют переменные в байесовском смысле: это могут быть наблюдаемые величины, латентные переменные, неизвестные параметры или гипотезы. Каждое ребро представляет прямую условную зависимость. Любая пара узлов, не связанных между собой (то есть не существует пути, соединяющего один узел с другим), представляет переменные, условно независимые друг от друга. С каждым узлом связана функция вероятности, которая на входе принимает определенный набор значений для родительских переменных этого узла и выдает (на выходе) вероятность (или распределение вероятностей, если это применимо) переменной, представленной узлом. Например, если родительские узлы представляют булевы переменные, то функция вероятности может быть представлена таблицей значений, по одному значению для каждой из возможных комбинаций родительских переменных. Аналогичные идеи могут быть применены к ненаправленным и, возможно, циклическим графам, таким как марковские сети.

Вывод неочевидных переменных

Поскольку байесовская сеть является полной моделью для своих переменных и их взаимосвязей, она может быть использована для ответа на вероятностные запросы относительно них. Например, сеть можно использовать для обновления информации о состоянии подмножества переменных при наблюдении других переменных (переменных-свидетельств). Этот процесс вычисления апостериорного распределения переменных при заданных свидетельствах называется вероятностным выводом. Апостериорное распределение предоставляет универсальную достаточную статистику для задач обнаружения, при выборе значений для подмножества переменных, минимизирующих некоторую ожидаемую функцию потерь, например, вероятность ошибки принятия решения. Таким образом, байесовскую сеть можно рассматривать как механизм автоматического применения теоремы Байеса к сложным задачам. Наиболее распространенными методами точного вывода являются: устранение переменных, которое последовательно исключает (путем интегрирования или суммирования) не наблюдаемые переменные, не входящие в запрос, распределяя сумму по произведению; распространение по деревьям клик, которое кэширует вычисления, позволяя одновременно выполнять запросы к множеству переменных и быстро распространять новые свидетельства; и рекурсивное обуславливание и поиск по схеме AND/OR, которые обеспечивают компромисс между использованием памяти и временем вычислений и соответствуют эффективности устранения переменных при достаточном объеме доступной памяти. Сложность всех этих методов экспоненциально зависит от ширины дерева сети. Наиболее распространенными алгоритмами приближенного вывода являются: важностная выборка, стохастическое моделирование методом Монте-Карло (MCMC), устранение с использованием мини-корзин, распространение сообщений в циклах (loopy belief propagation), обобщенное распространение сообщений и вариационные методы.

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

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

Введение в статистику

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

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

Ограничения приоров

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

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

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

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

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

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

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

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

Это определение можно обобщить, определив d-разделение двух узлов, где d означает «направленное». Этот результат стимулировал исследования алгоритмов аппроксимации с целью разработки вычислимого приближения к вероятностному выводу. В 1993 году Пол Дагум и Майкл Люби доказали два удивительных результата относительно сложности аппроксимации вероятностного вывода в байесовских сетях. Во-первых, они доказали, что не существует вычислимого детерминированного алгоритма, способного аппроксимировать вероятностный вывод с абсолютной погрешностью ɛ < 1/2. Во-вторых, они доказали, что не существует вычислимого рандомизированного алгоритма, способного аппроксимировать вероятностный вывод с абсолютной погрешностью ɛ < 1/2 с вероятностью достоверности, превышающей 1/2. Примерно в то же время Рот доказал, что точный вывод в байесовских сетях фактически является #P-полным (и, следовательно, столь же сложным, как подсчет количества удовлетворяющих назначений формулы конъюнктивной нормальной формы (CNF)), а аппроксимационный вывод с точностью до фактора 2n1−ɛ для любого ɛ > 0, даже для байесовских сетей с ограниченной архитектурой, является NP-трудным. С практической точки зрения, эти результаты о сложности показали, что, хотя байесовские сети являются богатым представлением для задач искусственного интеллекта и машинного обучения, их использование в крупных реальных приложениях должно быть ограничено либо топологическими структурными ограничениями, такими как наивные байесовские сети, либо ограничениями на условные вероятности. Алгоритм ограниченной дисперсии, разработанный Дагумом и Люби, был первым доказуемым быстрым алгоритмом аппроксимации, эффективно аппроксимирующим вероятностный вывод в байесовских сетях с гарантированной точностью аппроксимации. Этот мощный алгоритм требовал незначительного ограничения на условные вероятности байесовской сети, чтобы они были ограничены от нуля и единицы величиной, где был любым полиномом от числа узлов в сети, .