Моделирование деятельности образовательного учреждения в статике с использованием сетей Байеса, Основы Байесовского вывода - Моделирование сетей

Основы Байесовского вывода

Сети Байеса Jensen, Finn An introduction to Bayesian networks. -- Berlin: Springer, 1996. -- ISBN 0-387-91502-8 - наглядный инструмент моделирования сложных вероятностных процессов, включающих большое количество случайных переменных, связанных причинно-следственной связью. Сети Байеса - частный случай так называемых вероятностных графических моделей Koller, D.; Friedman, N. (2009). Probabilistic Graphical Models. Massachusetts: MIT Press. p. 1208. ISBN 0-262-01319-3..

Переменная в байесовском моделировании - некая сущность, обладающая именем и областью определения Comley J. W. and Dowe D. L., "Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages", chapter 11 (pp265--294) in P. Grunwald, M. A. Pitt and I. J. Myung (eds).,Advances in Minimum Description Length: Theory and Applications, Cambridge, MA: MIT Press, April 2005, ISBN 0-262-07262-9.. Обычно, рассматриваются переменные двух типов: дискретные и непрерывные. Дискретные переменные принимают значения из некоторого конечного множества X, а непрерывные - определены на некотором подмножестве множества действительных чисел. В общем случае, переменная определяется упорядоченной парой V=(N, X), где N - имя переменной, а X - множество возможных значений. В дальнейшем мы будем рассматривать только дискретные переменные.

Центральным понятием вероятностных графических моделей является понятие фактора Дьяконов А. П., Круглов В. В. MATLAB 6.5 SP1/7/7 SP1/7 SP2+Simulink 5/6. Инструменты искусственнго интеллекта и биоинформатики. М.: СОЛОН-Пресс, 2006. 456с.. Фактор это некая функция, которая ставит в соответствие каждому возможному набору значений некого множества переменных действительное число (значение фактора):

Фактор определен на некотором упорядоченном множестве переменных, называемом областью определения (scope) фактора. Область определения обозначается так: F(A, B, C) или так: scope(F)={A, B, C}, где F - фактор, A, B и C - переменные, входящие в фактор. Заметим, что определение фактора не накладывает никаких ограничений ни на отдельные значения, ни на сумму этих значений, несмотря на то, что теория вероятности предусматривает такие ограничения. Фактор - это базовый строительный блок в вероятностных графических моделях. и представление вероятностей - всего лишь одно из возможных применений факторов. Например, определим фактор на одной переменной M, следующим образом:

Фактор, представляющий безусловную вероятность

M

F

"орел"

0.5

"решка"

0.5

Этот фактор может быть интерпретирован как безусловная вероятность того, что данная переменная примет соответствующее значение. Это возможно потому, что сумма всех значений данного фактора равна 1. В математических обозначениях данный фактор определяется следующим образом: f=("P(M)", {M}, {0.5, 0.5}). можно определить другой фактор на той же области определения:

Фактор, представляющий ненормализованную меру

M

G

"орел"

20

"решка"

21

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

Факторы удобны для использования в вероятностных графических моделях тем, что на них определены некоторые операции, часто выполняемые в процессе логического вывода, в довольно общей форме, что позволяет использовать их как элементарные объекты для построения логических сетей. Определим три переменные A, B, C. A=("A", {1, 2, 3}), B=("B", {1, 2}), C=("C", {1, 2}). Одной из наиболее часто используемых операций над факторами является факторное произведение. F(A, B)*G(B, C)=H(A, B, C). Произведение факторов объединяет области определения двух факторов. Значением для каждого назначения является произведение соответствующих назначений множителей.

Еще одной операцией является маргинализация: H(A, B, C) - B = J(A, C). Маргинализация позволяет исключить переменную из области определения фактора, просуммировав соответствующие значения назначений маргинализируемого фактора. Маргинализация является основой алгоритма variable elimination.

Последней элементарной факторной операцией является сокращение (reduction). H(A, B, C) / B = K(A, C).

Существенно, что, несмотря на то, что в таблице для фактора K указаны значения переменной B, значения фактора не зависят от нее, то есть областью определения является набор {A, C}. Сокращение фактора позволяет выбрать те значения фактора, которые согласуются с определенным значением одной из переменных области определения этого фактора.

Также, факторы могут представлять условные вероятности. Рассмотрим пример из медицинской диагностики. Определим бинарную переменную с=("болезнь", {"нет", "есть"}) и бинарную переменную t=("тест", {"положительный", "отрицательный"}). Переменная с показывает, есть ли у пациента определенное заболевание. а переменная t - результат диагностического теста. Допустим, что априорная вероятность данного заболевания равна 1%. Сконструируем фактор С=("P(c)", {c}, {0.99, 0.01}). Очевидно, что вероятность получения определенного результата теста зависит от того, есть ли данное заболевание у пациента, или нет, то есть мы предполагаем известной вероятность P(t|c). Допустим, что вероятность получения положительного результата теста равна 90%. Соответственно, вероятность ложноотрицательного результата равна 0,1. Вероятность получить отрицательный результат при отсутствии заболевания равна 0,8, а вероятность ложноположительного результата - 0,2. Создадим фактор, представляющий данную условную вероятность: Т=("P(t|c)", {c, t}, {0.2, 0.8, 0.9, 0.1}).

Условная вероятность

C

T

P(c|t)

Нет

Положительный

0,2

Нет

Отрицательный

0,8

Есть

Положительный

0,9

Есть

Отрицательный

0,1

Графическая модель такой системы факторов в виде направленного ациклического графа G представлена на рисунке 16. Это простейшая Байесовская сеть, состоящая из двух переменных, связанных причинно-следственной связью.

Простейшая байесовская сеть

Сети Байса традиционно представляются в виде графа, в котором вершины представляют переменные, входящие в сеть, а ребра - причинно следственные связи, причем ребро направлено от причины к следствию. Это очень наглядное представление является одним из главных достоинств вероятностных графических моделей и позволяет отобразить условную вероятность в виде взаимосвязей переменных и факторов, а также зачастую построить граф по экспертным или эмпирическим данным для моделирования распределения вероятностей Korb Kevin B. Bayesian Artificial Intelligence. -- CRC Press, 2004. --ISBN 1-58488-387-1. В графе наглядно видна иерархичность условной вероятности. Если некая переменная X зависит от переменной Y, то переменная Y будет среди родителей переменной X на графе. Заметим, что причинно-следственная связь не эквивалентна зависимости переменных, которая в свою очередь, может быть прослежена на графе, используя механизм G-разделяемости (G-separation).

Рассмотрим подробнее процесс Байсовского вывода. Определим системы из трех бинарных переменных a, b, c и трех факторов: A=("P(a)", {a}, {0.6, 0.4}), B=("P(b)", {b}, {0.7, 0.3}), C=("P(c|a, b)", {a, b, c}, {0.7, 0.3, 0.9, 0.1, 0.8, 0.2, 0.6, 0.4}). Вычислим распределение полной вероятности P(a, b, c) = P(c|a, b)*P(a)*P(b): J=A*B*C.

Сеть Байеса

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

Какова вероятность того, что переменная X примет значение x0?

Какова вероятность того, что переменная X примет значение x0, если известно, что переменная Y принимает значение y0?

Каково распределение вероятности для переменной Х?

Каково распределение вероятности для переменной X, если известно, что переменная Y принимает значение y0? [8,15,19,20]

Заметим, что в общей форме вопрос к байесовской сети выглядит следующим образом: каково распределение полной вероятности набора переменных Q, при условии, что набор переменных E принимает назначение q? Множество переменных Q называется запросом (query) или целевыми переменными и может состоять из одной и более переменных. Множество условий E называется наблюдения (evidence) или наблюдаемыми переменными и, в общем случае, может быть пустым. Множества Q и E не должны пересекаться. Множество переменных, входящих в байесовскую сеть, но не входящих во множества Q и E называется скрытые (hidden) переменные. Семантика этих множеств довольно очевидна. Запрос - это целевые переменные, которые нас интересуют, исходя из контекста конкретной задачи. Наблюдение - это те переменные, значения которых мы можем измерить или предсказать. Скрытые переменные не являются ни тем, ни другим, но могут оказывать неявное влияние на запрос и/или на наблюдения. В таких обозначениях использование сети Байеса для логического вывода сводится к вычислению вероятности P(Q|E).

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

    - все переменные входящие в множества наблюдений и запросов входят в область определения сети: - множества Q и E не пересекаются: Ш;

Итак, каждый запрос разбивает множество переменных области определения сети на три непересекающихся множества: Q, E и H. Значение любого запроса к Байсовской сети на этих множествах может быть вычислен только из фактора, представляющего распределение полной вероятности P().

Рассмотрим несколько запросов к сети G:

P(C|A, B) - P(C|A=0, B=1). В данном случае скрытых переменных нет (пустое множество), С - целевая переменная, А и В - наблюдения. Требуется найти распределение вероятности переменной С при условии, что А=0. а В=1. Для вычисления необходимо выполнить последовательно четыре действия:

Из распределения полной вероятности J сократим переменную А со значением 0:

Сокращенный фактор

В

С

P'(B, C|A=0)

0

0

0.294

0

1

0.126

1

0

0.162

1

1

0.018

Важно, что данный фактор представляет так называемую ненормализованную меру вероятности: его значения не суммируются к единице. Сумма значений данного фактора равна 0,6, что в точности соответствует вероятности P(A=0).

Нормализуем все вероятности так, чтобы в сумме они давали единицу:

Нормализованный фактор

В

С

P(B, C|A=0)

0

0

0,49

0

1

0,21

1

0

0,27

1

1

0,03

Из получившегося распределения сократим переменную В со значением 1

Сокращенный фактор

С

P'(C|A=0,B=1)

0

0,27

1

0,21

Нормализуем вероятности:

Нормализованный фактор

С

P(C|A=0,B=1)

0

0,9

1

0,1

Получившееся распределение и является ответом на запрос P(C|A=0, B=1). Заметим, что данное распределение явно присутствует в таблице (3-я и 4-я строки), что очевидно. Данный конкретный запрос является тривиальным, так как распределение P(C|A, B) в явном виде использовалось нами для задания сети.

Таким образом, общий алгоритм байесовского вывода не зависит от направления причинно-следственных связей в модели и может применяться независимо от направлений ребер в графе G. Все вышесказанное верно и в общем случае. Определим общий алгоритм байсовского вывода для произвольного корректного запроса:

Построить распределение полной вероятности на множестве по формуле (1).

Для каждой скрытой переменной маргинализовать ее из этого распределения

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

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

Похожие статьи




Моделирование деятельности образовательного учреждения в статике с использованием сетей Байеса, Основы Байесовского вывода - Моделирование сетей

Предыдущая | Следующая