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

Байесовская сеть не только является полным и неизбыточным представлением проблемной области, но часто оказывается намного более компактной по сравнению с полным совместным распределением. Именно благодаря этому свойству байесовские сети становятся применимыми для представления проблемных областей со многими переменными. Компактность байесовских сетей является примером очень общего свойства локально структурированных систем (называемых также разреженными системами). В локально структурированной системе каждый субкомпонент непосредственно взаимодействует только с ограниченным количеством других компонентов независимо от общего количества компонентов. Локальная структура обычно ассоциируется с линейным, а не с экспоненциальным ростом сложности. В случае байесовских сетей резонно предположить, что в большинстве проблемных областей на каждую случайную переменную оказывают непосредственное влияние самое большее к других переменных, где к— некоторая константа. Если для простоты предположить, что в сети представлено η булевых переменных, то количество информации, необходимое для задания каждой таблицы условных вероятностей, будет составлять не большечисел, а полная сеть может быть определена с помощью чисел. В отличие от этого, совместное распределение содержитчисел. В качестве конкретного примера предположим, что имеется n=3 0 вершин, а каждая из них имеет пять родительских вершин (k=5). В таком случае для соответствующей байесовской сети потребуется 960 чисел, а для полного совместного распределения — больше миллиарда.

Существуют и такие проблемные области, в которых на каждую переменную могут оказывать непосредственное влияние все другие переменные, поэтому соответствующая сеть является полносвязной. В таком случае для задания таблиц условных вероятностей требуется такое же количество информации, как и для задания совместного распределения. Но есть и такие проблемные области, в которых существуют незначительные зависимости, тем не менее, обязательно требующие включения в сеть путем добавления нового ребра. Но если эти зависимости выражены очень слабо, то может не иметь смысла дополнительно повышать сложность сети ради небольшого выигрыша в точности. Например, можно было бы раскритиковать структуру нашей сети определения взлома на том основании, что если бы было землетрясение, то Джон и Мэри не позвонили бы, даже услышав тревожный сигнал, поскольку посчитали бы, что его причиной является землетрясение. Решение вопроса о том, следует ли вводить связи от Earthquake к JohnCalls и MaryCalls (и таким образом увеличивать размеры таблиц), зависит от результатов сравнения важности получения более точных вероятностей с затратами на указание дополнительной информации.