01:541 Байесовские сети доверия Нечеткие знания 3

© Муромцев Д.И. Лекция 13 01:542 Вычислительная сложность вероятностных вычислений Преодолеть вычислительную сложность позволяет предположение о независимости или условной независимости переменных, что позволяет использовать в ходе рассуждений только вероятностные оценки множества наиболее адекватных событий и свидетельств. Вычислительная модель, учитывающая связи между переменными и тем самым позволяющая разделить вычисление их значений, получила название байесовская сеть доверия (Bayesian belief network) ]. Эта модель позволяет сфокусировать рассуждения на конкретном вопросе, предполагая остальные события условно независимыми. Благодаря такому подходу можно избежать построения огромных таблиц вероятностей и сократить объемы вычислений.

© Муромцев Д.И. Лекция 13 01:543 Определение байесовской сети Байесовская сеть это ориентированный граф, удовлетворяющий следующим условиям: 1. 1.Вершинами сети являются множество случайных переменных. Переменные могут быть дискретными или непрерывными Вершины попарно соединяются ориентированными рёбрами. Для двух вершин Х и Y, если ребро направлено от вершины Х к вершине Y, то вершина Х называется родительской по отношению к вершине Y Все связанные с родительскими вершины определяются таблицей условных вероятностей или функцией условных вероятностей Для вершин без родителей вероятности её состояний являются безусловными (маргинальными).

© Муромцев Д.И. Лекция 13 01:544 Определение байесовской сети (продолжение) 5. 5.Обозначим для вершины Хi множество ее родительских вершин как parents(Хi), тогда Хi характеризуется распределением условных вероятностей. P(Хi | parents(Хi)), которое количественно оценивает влияние родительских вершин на вершину Хi. Совместное распределение значений в вершинах можно оценить как результат произведения локальных распределений в каждом узле и его родителях: 5. 5.Если у вершины Xi нет родителей, то его локальное распределение вероятностей называют безусловным, иначе условным. Если значение в узле получено в результате опыта, то вершину называют свидетелем Граф не имеет циклов, состоящих из ориентированных рёбер, т.е. является ориентированным ациклическим графом (Directed Acyclic Graph DAG).

© Муромцев Д.И. Лекция 13 01:545 Семантика сети Топология сети (множество вершин и рёбер) показывает отношения, определяющие условную зависимость переменных, которые могут проявиться в данной предметной области. Можно сказать, что в корректно построенной байесовской сети смысл дуги состоит в том, что одна вершина оказывает непосредственное влияние на другую. По этой причине байесовские сети доверия иногда называют причинно- следственными сетями, в которых случайные события соединены причинно-следственными связями. Для эксперта определение того, какие именно могут быть влияния в данной предметной области, является достаточно лёгкой задачей по сравнению с фактическим определением самих вероятностей. После того как топология сети составлена, остаётся только указать распределение условных вероятностей для каждой переменной с учётом её родителей.

© Муромцев Д.И. Лекция 13 01:546 Свойство d-разделенности Вычисление условной независимости в байесовской сети основано на графическим свойством d-разделенности (d-separation). Две переменные x и y в байесовской сети являются d-разделенными, если на каждом пути, соединяющем эти две вершины на графе, найдется промежуточная переменная z (не совпадающая ни с x, ни с y), такая что: связь в пути в узле, соответствующем z, последовательная (рис. a) или расходящаяся (рис. b), и значение z известно, либо связь сходящаяся (рис. c), и нет свидетельств ни о значении z, ни о каждом из ее потомков. При этом свидетельства это утверждения вида «событие в узле x произошло», например: «Компьютер не загружается».

© Муромцев Д.И. Лекция 13 01:547 Пример Шерлок Холмс вышел из дому утром и заметил, что трава вокруг влажная. Он рассудил: «Я думаю, что ночью был дождь. Следовательно, трава возле дома моего соседа, доктора Ватсона, вероятно, также влажная». Таким образом, информация о состоянии травы у дома Холмса повлияла на его ожидания относительно влажности травы у дома Ватсона. Но предположим, что Холмс проверил состояние сборника дождевой воды и обнаружил, что тот сухой. В результате Холмс вынужден изменить ход своих рассуждений, и состояние травы возле его дома перестает влиять на ожидания по поводу травы у соседа. Рассмотрим две возможные причины, почему трава у дома Холмса оказалась влажной. Помимо дождя, Холмс мог просто забыть выключить поливальную установку накануне. Допустим, на следующее утро Холмс снова обнаруживает, что трава влажная. Это повышает его субъективные вероятности и для прошедшего дождя, и по поводу забытой дождевальной установки. Затем Холмс обнаруживает, что трава у дома Ватсона также влажная и заключает, что ночью был дождь.

© Муромцев Д.И. Лекция 13 01:548 Попутное (контекстное) объяснение Следующие рассуждения практически невозможно воспроизвести в системах, основанных на правилах, однако он абсолютно естественен для человека: влажность травы у дома Ватсона объясняется дождем, и, следовательно, нет более оснований ожидать, что была оставлена включенной поливальная машина. Следовательно, возросшая субъективная вероятность относительно забытой поливальной машины уменьшается до исходного значения, имевшего место до выхода Холмса из дому. Такой способ рассуждения можно назвать попутное (контекстное) объяснение, или редукция причины (explaining away). Важная особенность «попутного объяснения» состоит в изменении отношений зависимости между событиями по мере поступления информации. До выхода из дому Холмса факты дождя и работы поливальной установки были независимы. После получения информации о траве у дома они стали зависимыми. Далее, когда появилась информации о влажности травы у дома Ватсона, состояние зависимости вновь изменилось

© Муромцев Д.И. Лекция 13 01:549 Продолжение примера Описанная ситуация может быть смоделирована с помощью сети, содержащей четыре вершины: «Дождь», «Поливальная машина», «Ватсон» и «Холмс». Переменные, соответствующие этим вершинам, могут принимать только булевы значения Истина (И) или Ложь (Л). Вершина «Дождь» говорит о том, что если аналогичная переменная получит истинное значение, то тогда определенно прошел дождь, и по этой причине трава будет мокрой и у дома Ватсона, и во дворе Холмса. Напротив, вершина «Поливальная машина» в случае истинности соответствующей ей переменной свидетельствует только в пользу влажности травы во дворе Холмса. Описанные зависимости отображены стрелками на байесовской сети доверия.

© Муромцев Д.И. Лекция 13 01:5410 Продолжение примера Для вычислений в байесовской сети потребуются следующие переменные: R «был дождь» (Rain), S «работала поливальная машина» (Sprinkler), H «влажная трава у дома Холмса» и W «влажная трава у дома Ватсона». Также требуются распределения интересующих нас переменных, взятые по отдельности. Следует отметить, что вероятность пребывания вершины «Ватсон» (переменная W) в определённом состоянии обусловлено состоянием её родительских вершин. Вершины «Дождь» и «Поливальная машина» не имеют родительских вершин, поэтому, соответствующие им вероятности являются маргинальными, т.е. ни от чего не зависят. Они также могут быть получены из соотношения для полной вероятности при помощи маргинализации суммирования по реализациям всех переменных, кроме выбранных.

© Муромцев Д.И. Лекция 13 01:5411 Продолжение примера Совместная вероятность P(R, S, H, W) может быть задана таблицей из 16 чисел, нормируемой следующим образом: Из теоремы умножения вероятностей полная вероятность представляется произведением условных вероятностей: В описанной выше байесовской сети ориентированные ребра графа отражают только те зависимости, которые реально имеют место в задаче. Поэтому формула для полной вероятности существенно упрощается: Построенная модель позволяет осуществлять вычисления для ответа на вопросы типа «Какова вероятность того, что был дождь, если трава у дома мокрая»

© Муромцев Д.И. Лекция 13 01:5412 Продолжение примера Найдем сначала полные вероятности двух событий: трава у дома Холмса оказалась влажной, и трава у дома Ватсона оказалась влажной: Аналогично: Теперь, если найдутся свидетельства в пользу того, что ночью был дождь, то эта информация изменит (увеличит) вероятности наблюдения мокрой травы:

© Муромцев Д.И. Лекция 13 01:5413 Продолжение примера С другой стороны, пусть Холмсу известно, что трава у его дома влажная. Каковы вероятности того, что был дождь, и что дело в поливальной установке? Следующие вычисления позволяют оценить вероятность этой причины: Числитель этой формулы получен путем маргинализации суммирования по значениям переменных S и W. Полученные значения апостериорных вероятностей и для дождя, и для поливальной машины, как и следовало ожидать, выше соответствующих величин 0,3 и 0,2 для априорных вероятностей. Наконец, если Холмс обнаружит, что трава у дома Ватсона влажная, то вероятности снова изменятся:

© Муромцев Д.И. Лекция 13 01:5414 Выводы Вероятность дождя возросла вследствие дополнительной информации о влаге на траве у дома Ватсона. Так как высокая вероятность дождя объясняет влажность травы у дома самого Холмса, то объяснений при помощи другой причины (т. е. включенной поливальной установки) больше не требуется и ее вероятность понижается почти до исходного значения 0,2. Этот пример иллюстрирует «попутное объяснение» (редукцию причины), о котором говорилось выше. В общем случае при росте числа переменных в сети задача точного нахождения вероятностей в сети является крайне вычислительно сложной вследствие комбинаторного сочетания значений переменных в суммах при вычислении маргиналов от совместного распределения вероятностей, а также потенциальным наличием нескольких путей, связывающих пару переменных на графе. На практике часто используются приближенные методы для оценок комбинаторных сумм, например вариационные методы и многочисленные вариации методов Монте-Карло. В силу того, что байесовская сеть это полная модель для переменных и их отношений, она может быть использована для ответов на вероятностные вопросы. Например, сеть можно использовать, чтобы получить новое знание о состоянии подмножества переменных, наблюдая за другими переменными (переменные свидетельства). Это процесс вычисления апостериорного распределения переменных по переменным- свидетельствам называют вероятностным выводом.