Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 182
Текст из файла (страница 182)
Су~цествуют два способа, позволяющих понять семантику байесовских сетей. Первый из них состоит в том, что сеть следует считать одним из представлений совместного распределения вероятностей, а второй — в том, что она должна рассматриваться как описание совокупности утверждений об условной независимости. Эти две трактовки являются эквивалентными, но первая оказалась более полезной при определении способа составления сетей, а вторая — более применимой при проектировании процедур вероятностного вывода.
Представление полного совместного распределения Любая байесовская сеть представляет собой полное описание рассматриваемой проблемной области. Каждый элемент в полном совместном распределении вероятностей (которое ниже будет сокрагценно именоваться "совместным распределением") может быть рассчитан на основании информации, представленной в этой сети. Универсальным элементом в совместном распределении является вероятность конъюнкции конкретных присваиваний значений каждой переменной, такой как Р(Х;-х, л ...
о Х,=х„) . В качестве сокращенного обозначения для такой коньюнкции будет использоваться выражение Р (х„..., х„) . Значение этого элемента задается следующей формулой: Р(хь, ..., х„) = П Р(х,)рсгепга(Х,) ) к=1 где рагепсв(Х,) обозначает конкретные значения переменных в множестве вершинн Рагеп сэ ( х, ) . Поэтому каждый элемент в совместном распределении представлен в виде произведения соответствующих элементов в таблицах условных вероятностей (Сопгййопа! РгоЬаЬ!!Ыу ТаЫе — СРТ) байесовской сети. Таким образом, таблицы СРТ обеспечиваютдекомпонованное представление совместного распределения.
Для иллюстрации описанных выше понятий рассчитаем вероятность того, что прозвучал тревожный сигнал, но не произошли ни взлом, ни землетрясение, а позвонили и Мэри, и Джон. Мы будем использовать однобуквенные имена для этих переменных (см. рис. !4.2): 665 Глава 14. Вероятностные рассуждения Р(з л ги л а л -Ь л е) — Р(у(а) Р(т(а) Р(а(-~Ь л е) р( Ь) р( е) 0.90 х 0.70 х 0.001 х 0.999 х 0.998 = 0.00062 В разделе 13.4 было описано, как можно использовать полное совместное распределение для получения ответа на любой запрос о данной проблемной области. А если байесовская сеть служит представлением совместного распределения, то может также применяться для получения ответа на любой запрос путем суммирования соответствуюших элементов совместного распределения.
В разделе !4.4 показано, как найти ответ с помошью такого способа, а также описаны методы, которые являются гораздо более эффективными. Метод составления байесовских сетей В уравнении 14.1 показано, что означает данная конкретная байесовская сеть. Но это уравнение не позволяет определить, как следует составлять байесовскую сеть таким образом, чтобы результирую)цее совместное распределение служило адекватным представлением данной проблемной области.
Тем не менее в этом разделе будет показано, что из уравнения 14.1 следуют определенные отношения условной независимости, которые могут использоваться инженером по знаниям в качестве руководящих указаний при составлении топологии сети. Вначале перезапишем это совместное распределение в терминах условных вероятностей с использование правила произведения (см. главу 13): Р(хы, х„] = Р(х„(х„,, ..., х1) Р(х 1, ..., х1) Затем повторим этот процесс, приводя каждую конъюнктивную вероятность к условной вероятности и меныпей конъюнкции.
В конечном итоге будет получено одно большое произведение: Р(х1, ..., х„) = Р(х„(х„ы ..., Х1)Р(х 1)х г, ..., х1)... Р(х2(х1)Р(х1) п П Р( г ! х и, х1) 1=1 Это тождество справедливо для любого множества случайных переменных и называется 'ж цепным правилом (с))а)п гп1е). Сравнивая его с уравнением 14.1, можно обнаружить, что данная спецификация совместного распределения эквивалентна об)цему утверждению, что для каждой переменной хз В сЕти ВЕРНО СледуЮШЕе: Р(Х,(Х:-ы ..., Х1) = Р(Х,(рагеиее(Х,) ) (14.2) при условии, что Рагепев(хг) ~ ( х,,, ...,х, ). Это последнее условие можно выполнить, разметив вершины графа в любом порядке, совместимом с частичным упорядочением, неявно заданным в структуре графа. Фактически уравнение 14.2 свидетельствует о том, что байесовская сеть служит правильным представлением проблемной области, только если каждая вершина в ней условно независима от ее предшественников в конкретном упорядочении вершин, после того как заданы ее родительские вершины.
Поэтому, для того чтобы составить байесовскую сеть с правильной структурой для рассматриваемой проблемной области, необходимо выбрать для каждой вершины родительские вершины так, чтобы соблюдалось это свойство. Интуитивно ясно, что множество родительских 666 Часть Н. Неопределенные знания и рассуждения в условиях неопределенности вершин вершины Х, должно включать все такие вершины из множества Х„, ..., Х„,, которые пг- непосредственно влияют на х,.
Например, предположим, что мы полностью составили сеть, показанную на рис. (4.2, и осталось только выбрать родительские вершины для магуса11е. Безусловно, на вершину магуса11а оказывает влияние то, произошло ли событие виго1агу или Еагсйциа)се, но это — не непосредственное влияние. Очевидно, что наши знания в этой проблемной области говорят о том, что эти события влияют на поведение Мэри, касающееся звонков, только через свое воздействие на тревожный сигнал. Кроме того, если речь идет о наличии тревожного сигнала, то звонок Джона не влияет на звонок Мэри.
Формально говоря, составляя эту сеть, мы уверены в том, что справедливо следую(цее утверждение об условной независимости: Р(Магуса11а(Ооппеа11а, А1агга, Еагспдиане, Вигд1агу) В(Магуса11а(Л1агл) Компактность сети и упорядочение вершин Байесовская сеть не только является полным и неизбыточным представлением проблемной области, но часто оказывается намного более компактной по сравнению с полным совместным распределением.
Именно благодаря этому свойству байесовские сети становятся применимыми для представления проблемных областей со многими переменными. Компактность байесовских сетей является примером очень общего свойства Ъ. локально структурированных систем (называемых также ек разреженными системами). В локально структурированной системе каждый субкомпонент непосредственно взаимодействует только с ограниченным количеством других компонентов независимо от общего количества компонентов.
Локальная структура обычно ассоциируется с линейным, а не с экспоненциальным ростом сложности. В случае байесовских сетей резонно предположить, что в большинстве проблемных областей на каждую случайную переменную оказывают непосредственное влияние самое большее )г других переменных, где К вЂ” некоторая константа. Если для простоты предположить, что в сети представлено и булевых переменных, то количество информации, необходимое для задания каждой таблицы условных вероятностей, будет составлять не больше 2' чисел, а полная сеть может быть определена с помощью п2" чисел.
В отличие от этого, совместное распределение содержит 2а чисел. В качестве конкретного примера предположим, что имеется п=З 0 вершин, а каждая из них имеет пять родительских вершин ()с= 5). В таком случае для соответствующей байесовской сети потребуется 960 чисел, а для полного совместного распределения— больше миллиарда. Существуют и такие проблемные области, в которых на каждую переменную могут оказывать непосредственное влияние все другие переменные, поэтому соответствующая сеть является полносвязной.
В таком случае для задания таблиц условных вероятностей требуется такое же количество информации, как н для задания совместного распределения. Но есть н такие проблемные области, в которых существуют незначительные зависимости, тем не менее, обязательно требующие включения в сеть путем добавления нового ребра. Но если этн зависимости выражены очень слабо, то может не иметь смысла дополнительно повышать сложность сети ради небольшого выигрыша в точности. Например, можно было бы раскритиковать структуру нашей сети определения взлома на том основании, что если бы было землетря- 667 Глава 14.
Вероятностные рассуждения сение, то Джон и Мэри не позвонили бы, даже услышав тревожный сигнал, поскольку посчитали бы, что его причиной является землетрясение, Решение вопроса о том, слелует ли вводить связи от еахсЛстца)се к тойпса11а и иахуса11а (и таким образом увеличивать размеры таблиц), зависит от результатов сравнения важности получения более точных вероятностей с затратами на указание дополнительной информации. Составление локально структурированной байесовской сети даже в локально структурированной проблемной области представляет собой нетривиальную задачу.
Для этого требуется не только знать, что на каждую переменную непосредственно влияют лишь несколько других переменных, но и убелиться в том, что топология сети действительно отражает эти непосредственные влияния, представленные с помощью соответствуюшего множества родительских вершин. В связи с тем, как организована сама процедура составления сети, "непосредственно влияющие" вершины должны быть введены в сеть первыми, если они затем станут родительскими вершинами тех вершин, на которые влияют.
Поэтому лв- правильный порядок, в которолл следует вводить вершины, состоит в том, что вначале необходимо вводить вершины "коренных причин", затем вершины переменных, на которые они влияют, и т.д. до тех пор, пока не будут достигнуты "листовые вершины", которые не оказывают непосредственного причинного влияния на другие переменные. А что произойдет, если будет выбран порядок, который окажется неправильным? Еше раз рассмотрим пример со взломом. Предположим, что мы решили вводить вершины в порядке ееахуса11а, ыо?лпса11а, А1акт, Вцхр1аху, еахс)зс)паке. В таком случае будет получена немного более сложная сеть, показанная на рис. 14.3, а. При этом процесс введения вершин происходит, как описано ниже. а) б) Рис. !4.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
