Компактность сети и упорядочение вершин

Байесовская сеть не только является полным и неизбыточным представлением проблемной области, но часто оказывается намного более компактной по сравнению с полным совместным распределением. Именно благодаря этому свойству байесовские сети становятся применимыми для представления проблемных областей со многими переменными. Компактность байесовских сетей является примером очень общего свойства локально структурированных систем (называемых также разреженными системами). В локально структурированной системе каждый субкомпонент непосредственно взаимодействует только с ограниченным количеством других компонентов независимо от общего количества компонентов. Локальная структура обычно ассоциируется с линейным, а не с экспоненциальным ростом сложности. В случае байесовских сетей резонно предположить, что в большинстве проблемных областей на каждую случайную переменную оказывают непосредственное влияние самое большее к других переменных, где к — некоторая константа. Если для простоты предположить, что в сети представлено п булевых переменных, то количество информации, необходимое для задания каждой таблицы условных вероятностей, будет составлять не больше 2к чисел, а полная сеть может быть определена с помощью л2к чисел. В отличие от этого, совместное распределение содержит 2П чисел. В качестве конкретного примера предположим, что имеется л=3 0 вершин, а каждая из них имеет пять родительских вершин (к=5). В таком случае для соответствующей байесовской сети потребуется 960 чисел, а для полного совместного распределения — больше миллиарда.
Существуют и такие проблемные области, в которых на каждую переменную могут оказывать непосредственное влияние все другие переменные, поэтому соответствующая сеть является полносвязной. В таком случае для задания таблиц условных вероятностей требуется такое же количество информации, как и для задания совместного распределения. Но есть и такие проблемные области, в которых существуют незначительные зависимости, тем не менее, обязательно требующие включения в сеть путем добавления нового ребра. Но если эти зависимости выражены очень слабо, то может не иметь смысла дополнительно повышать сложность сети ради небольшого выигрыша в точности. Например, можно было бы раскритиковать структуру нашей сети определения взлома на том основании, что если бы было землетрясение, то Джон и Мэри не позвонили бы, даже услышав тревожный сигнал, поскольку посчитали бы, что его причиной является землетрясение. Решение вопроса о том, следует ли вводить связи от Earthquake к JohnCalls и MaryCalls (и таким образом увеличивать размеры таблиц), зависит от результатов сравнения важности получения более точных вероятностей с затратами на указание дополнительной информации.
Составление локально структурированной байесовской сети даже в локально структурированной проблемной области представляет собой нетривиальную задачу. Для этого требуется не только знать, что на каждую переменную непосредственно влияют лишь несколько других переменных, но и убедиться в том, что топология сети действительно отражает эти непосредственные влияния, представленные с помощью соответствующего множества родительских вершин. В связи с тем, как организована сама процедура составления сети, "непосредственно влияющие" вершины должны быть введены в сеть первыми, если они затем станут родительскими вершинами тех вершин, на которые влияют. Поэтому Ж3 правильный порядок, в котором следует вводить вершины, состоит в том, что вначале необходимо вводить вершины "коренных причин", затем вершины переменных, на которые они влияют, и т.д. до тех пор, пока не будут достигнуты "листовые вершины", которые не оказывают непосредственного причинного влияния на другие переменные.
А что произойдет, если будет выбран порядок, который окажется неправильным? Еще раз рассмотрим пример со взломом. Предположим, что мы решили вводить вершины в порядке MaryCalls, JohnCalls, Alarm, Burglary, Earthquake. В таком случае будет получена немного более сложная сеть, показанная на рис. 14.3, а. При этом процесс введения вершин происходит, как описано ниже.
• Введение вершины MaryCalls — родительские вершины отсутствуют.
• Введение вершины JohnCalls — если звонит Мэри, это, по-видимому, означает, что раздался тревожный сигнал, а вероятность такого события, очевидно, будет выше, если позвонит также и Джон. Поэтому для вершины JohnCalls необходимо использовать в качестве родительской вершину MaryCalls.
• Введение вершины Alarm — безусловно, если позвонили оба соседа, вероятность того, что раздался тревожный сигнал, больше, чем лишь при одном звонке или вообще без звонков, поэтому в качестве родительских необходимо включить обе вершины, и MaryCalls, и JohnCalls.
• Введение вершины Burglary — если известно состояние тревожного сигнала, то звонок от Джона или Мэри может дать жильцу охраняемого дома информацию о том, что звонил его телефон или Мэри слушала музыку, но не о взломе:
Р[Burglary]Alarm,JohnCalls,MaryCalls) - P[Burglary]Alarm)
Поэтому для использования в качестве родительской вершины требуется только Alarm.
• Введение вершины Earthquake — если раздался тревожный сигнал, то возможно также, что было землетрясение (эта тревожная сигнализация является к тому же своего рода детектором землетрясения). Но известно, что если был взлом, то тревожный сигнал объясняется именно этим, а вероятность землетрясения должна быть лишь ненамного выше нормальной. Поэтому в качестве родительских вершин для этой вершины необходимо иметь и Alarm, и Burglary.
Результирующая сеть имеет на два ребра больше по сравнению с первоначальной сетью, показанной на рис. 14.2, а также требует указания трех дополнительных вероятностей. Но что еще хуже, некоторые из ее связей представляют надуманные отношения, которые требуют формирования сложных и неестественных суждений о вероятностях, таких как оценки вероятности Earthquake, если даны Burglary и Alarm. Такой феномен является весьма распространенным и связан с различием между причинными и диагностическими моделями, которые были представлены в главе 8. Если мы попытаемся построить диагностическую модель со связями от симптомов к причинам (как, например, от MaryCalls к Alarm или от Alarm к Burglary), то в конечном итоге будем вынуждены задавать дополнительные зависимости между причинами, которые во всем остальном являются независимыми (а часто даже между отдельно возникающими симптомами). Ж3 Если же мы будем придерживаться причинной модели, то в конечном итоге нам придется задавать меньше чисел и сами эти числа, скорее всего, можно будет легче определить. Например, Тверский и Канеман [1523] для проблемной области медицинской диагностики показали, что опытные врачи предпочитают составлять вероятностные суждения для причинных, а не диагностических правил.
На рис. 14.3, б показано еще худшее упорядочение вершин: MaryCalls, JohnCalls, Earthquake, Burglary, Alarm. Для этой сети требуется задать 31 отдельную вероятность — точно такое же количество, как и при использовании полного совместного распределения. Однако важно понять, что любая из этих трех сетей может представлять точно такое же совместное распределение, как и другие. Просто в последних двух версиях не удалось успешно выявить все отношения условной независимости и поэтому вместо них пришлось ввести много ненужных чисел.







Материалы

Яндекс.Метрика