ЭФФЕКТИВНОЕ ПРЕДСТАВЛЕНИЕ РАСПРЕДЕЛЕНИЙ УСЛОВНЫХ ВЕРОЯТНОСТЕЙ
2 Существует также общий топологический критерий, называемый d-отделением, для принятия решения о том, является ли множество вершин X независимым от другого множества У, если задано третье множество Z. Этот критерий является довольно сложным и не требуется для разработки алгоритмов, приведенных в данной главе, поэтому мы его не описываем. Подробные сведения об этом критерии можно найти в [1191] или [1328], а в [1384] описан более интуитивно понятный метод проверки выполнения условий d-отделения.
Даже если максимальное количество родительских вершин к невелико, для заполнения таблицы СРТ, относящейся к некоторой вершине, необходимо будет задать вплоть до 0(2к) чисел, а также, возможно, потребуется значительный опыт оценки всех возможных обусловливающих случаев. К тому же на практике иногда встречается наихудшая ситуация, в которой связь между родительскими вершинами и дочерней вершиной является полностью произвольной. Обычно такие отношения можно описать с помощью канонического распределения, которое соответствует некоторому стандартному образцу. В таких случаях всю таблицу можно задать, указав тип распределения и, возможно, введя несколько параметров, что намного проще по сравнению с определением экспоненциального количества параметров.
С другой стороны, примером простейшей ситуации является наличие детерминированных вершин. Детерминированная вершина характеризуется тем, что ее значение точно определяется значениями ее родительских вершин, без какой-либо неопределенности. Отношение между вершинами может быть логическим, например, отношение между родительскими вершинами Canadian, US, Mexican и дочерней вершиной NorthAmerican состоит в том, что значение дочерней вершины представляет собой дизъюнкцию значений родительских вершин. Такое отношение может также быть числовым, например, если значениями родительских вершин являются цены на конкретную модель автомобиля у нескольких дилеров, а значением дочерней вершины является цена, которую в конечном итоге заплатит охотник за низкими ценами, то значением дочерней вершины является минимальное из значений родительских вершин. Если же значениями родительских вершин являются притоки воды (через реки, ключи, росу) в озеро и оттоки воды (через реки, испарения, дренаж) из озера, а значением дочерней вершины является изменение уровня воды в озере, то значение дочерней вершины представляет собой общую разницу между родительскими вершинами с притоком и родительскими вершинами с оттоком.
Неопределенные отношения можно также часто охарактеризовать с использованием так называемых "зашумленных" логических отношений. Стандартным примером является отношение зашумленного OR, которое представляет собой обобщение логического отношения OR. В пропозициональной логике можно составить утверждение, что высказывание Fever (Жар) является истинным тогда и только тогда, когда истинны высказывания Cold (Простуда), Flu (Грипп) или Malaria (Малярия). Модель зашумленного OR позволяет учитывать неопределенность знаний в отношении способности каждой из родительских вершин вызывать присваивание истинного значения дочерней вершине, поскольку причинная связь между родительской и дочерней вершинами может быть заблокирована и поэтому иногда пациент бывает простужен, но у него не обнаруживается жар. В этой модели приняты два предположения. Во-первых, в ней предполагается, что учтены все возможные причины. (Это — не такое строгое требование, как кажется на первый взгляд, поскольку всегда есть возможность ввести так называемую вершину утечки (leak node), которая покрывает "прочие причины".) Во-вторых, предполагается, что блокирование каждой родительской вершины не зависит от блокирования любых других родительских вершин, например, та причина, которая блокирует возникновение жара под влиянием действия вершины Malaria, не зависит от тех причин, которые блокируют возникновение жара под действием вершины Flu. С учетом этих предположений значение вершины Fever является ложным тогда и только тогда, когда заблокированы все ее родительские вершины, имеющие истинное значение, а вероятность такой ситуации представляет собой произведение вероятностей блокировки каждой родительской вершины. Предположим, что такие отдельные вероятности блокировки выражаются следующим образом:
Р( —\f ever I cold, —\flu, —\malaria) = 0.6 P(—\f ever I —\Cold, flu, —imalaria) = 0.2 P(—\f ever I —\cold, —\flu, malaria) = 0.1
В таком случае появляется возможность составить всю таблицу СРТ на основании этой информации и предположений модели зашумленного OR. Пример вычисления значений соответствующих элементов показан в табл. 14.1.
Вообще говоря, зашумленные логические отношения, в которых некоторая переменная зависит от к родительских переменных, могут быть описаны с использованием О {к) параметров вместо 0(2к) параметров, которые требуются для полной таблицы условных вероятностей. Благодаря этому задачи присваивания значений и обучения намного упрощаются. Например, распределения зашумленного OR и зашумленного МАХ успешно использовались в сети CPCS [1232] для моделирования отношений между заболеваниями и симптомами в диагностике внутренних органов. При наличии 448 вершин и 906 связей в этой сети потребовалось только 8254 значения вместо 133 931 430 значений для сети с полными таблицами СРТ.
Байесовские сети с непрерывными переменными
Для решения многих реальных задач требуется учитывать непрерывные количества, такие как уровень, масса, температура и сумма денежных средств; в действительности большая часть такого научного направления, как статистика, посвящена исследованию случайных переменных, области определения которых являются непрерывными. По определению непрерывные переменные имеют бесконечное количество возможных значений, поэтому невозможно явно задать условные вероятности для каждого значения. Один из возможных способов обработки непрерывных переменных состоит в избавлении от них с помощью дискретизации, т.е. разделения всех возможных значений на постоянное множество интервалов. Например, температуры могут быть разделены на интервалы (<0°С), (0°С-100°С) и (>100°С). Иногда дискретизация становится вполне адекватным решением, но часто приводит к значительной потере точности и появлению очень больших таблиц СРТ. Еще одно решение состоит в определении стандартных семейств функций плотности вероятностей (см. приложение А), которые задаются с помощью конечного количества параметров. Например, гауссово (или нормальное) распределение N(\x,a2) (х) имеет в качестве параметров среднее JI и дисперсию а2.
Сеть, в которой имеются и дискретные, и непрерывные переменные, называется гибридной байесовской сетью. Для составления гибридной сети необходимо определить два новых типа распределений: условное распределение для непрерывной переменной, если даны дискретные или непрерывные родительские переменные, и условное распределение для дискретной переменной, если даны непрерывные родительские переменные. Рассмотрим простой пример, приведенный на рис. 14.5, в котором клиент покупает какие-то фрукты в зависимости от их стоимости, которая, в свою очередь, зависит от размера урожая и от того, применяется ли правительственная программа субсидий. Переменная Cost (Стоимость) является непрерывной и имеет непрерывные и дискретные родительские переменные; переменная Buys (Покупает) является дискретной и имеет непрерывную родительскую переменную.
Для переменной Cost необходимо задать распределение Р (Cost | Harvest, Subsidy). Это дискретное родительское значение учитывается с помощью явного перечисления, т.е. определения и значения P(Cost \ Harvest, subsidy), и значения P{Cost | Harvest,subsidy). Чтобы учесть переменную Harvest, требуется определить, как распределение по стоимости зависит от непрерывного значения л переменной Harvest. Иными словами, необходимо определить параметры распределения стоимости как функции от л. Наиболее часто применяемым вариантом является линейное гауссово распределение, в котором дочерняя переменная имеет
гауссового распределение со средним JLI, изменяющимся линейно в зависимости от значения родительской переменной, и с постоянным среднеквадратичным отклонением о. Необходимо иметь два распределения, одно для subsidy, а другое для -subsidy, с разными параметрами:
lfc-(ath+bt)f
P(c\h, subsidy) = N(ath + btl ot2)(c) = —%= e 2 St '
at"v271
lfc-(afh+bf)V
P{c\h,-nsubsidy) = N{ath + bt, Of2) (c) = —h= e 2 Sf '
Gt\J2ll
Итак, в данном примере условное распределение для переменной Cost было задано путем обозначения его как линейного гауссового распределения и предоставления параметров
нескольких измерениях, которая имеет пик в районе среднего значения, в п измерениях, и уменьшается по всем направлениям.) Если в сеть введены дискретные переменные (при условии, что ни одна дискретная переменная не является дочерней применительно к непрерывной переменной), то сеть определяет условное гауссово распределение, или распределение CG (conditional Gaussian): если дано любое присваивание дискретным переменным, то распределение по непрерывным переменным становится многомерным гауссовым распределением.
Теперь обратимся к распределениям для дискретных переменных с непрерывными родительскими переменными. Например, рассмотрим вершину Buys на рис. 14.5. Представляется обоснованным предположение, что клиент сделает покупку, если стоимость является низкой, и не сделает покупку, если она высока, а также, что вероятность покупки изменяется плавно в некотором промежуточном регионе. Другими словами, условное распределение напоминает "мягкую" пороговую функцию. Один из способов определения мягких пороговых функций состоит в использовании интеграла стандартного нормального распределения:
Ф(х) = N(0,1) (х) dx
В таком случае вероятность события Buys, если дано значение Cost, может выражаться следующей формулой:
P(buys\Cost=c) = Ф((-с+ц)/а)
которая означает, что пороговое значение стоимости обнаруживается в районе п., ширина порогового региона пропорциональна а, а вероятность покупки уменьшается по мере возрастания стоимости.
Такое распределение вероятностей называется пробит-распределением (probit distribution) и показано на рис. 14.7, а. Возможность применения распределения с такой формой может быть обосновано тем, что соответствующий процесс принятия решения имеет твердый порог, но точное расположение этого порогового значения подвержено воздействию случайного гауссового шума. Альтернативным по отношению к пробит-распределению является логит-распределение (logit distribution), в котором для формирования мягкого порога используется сигмоидальная функция (sigmoid function):
l
P(buys\Cost=c) =
l+exp(-2 )
о
Это распределение показано на рис. 14.7, б. Два распределения внешне выглядят одинаковыми, но фактически логит-распределения имеют более длинные "хвосты". Пробит-распределения часто лучше подходят в реальных ситуациях, а логит-распределения иногда проще поддаются математической обработке. Последние широко используются в нейронных сетях (глава 20). И пробит- и логит-распределения могут быть обобщены для учета многочисленных непрерывных родительских значений путем применения линейной комбинации родительских значений. Расширения для случая многомерных дискретных дочерних значений рассматриваются в упр. 14.6.
Основной задачей для любой системы вероятностного вывода является вычисление распределения апостериорных вероятностей для множества переменных запроса, если дано некоторое наблюдаемое событие, т.е. если выполнено некоторое присваивание значений множеству переменных свидетельства. Мы будем использовать систему обозначений, введенную в главе 13: X обозначает переменную запроса; Е — множество переменных свидетельства, Ег,..., JE; е — конкретное наблюдаемое событие; Y обозначает переменные, отличные от переменных свидетельства, Ylt..., YY (иногда называемые скрытыми переменными). Таким образом, полное множество переменных определяется выражением X={X}UEUY. В типичном запросе4 содержится просьба определить распределение апостериорных вероятностей Р {Х \ е).
В сети с описанием взлома может наблюдаться событие, в котором JohnCalls=true и MaryCalls-true. В таком случае можно ввести следующий запрос, скажем, для определения вероятности того, что произошел взлом:
Р{Burglary\JohnCalls=true,MaryCalls=true) = <0 . 284, 0.716>
В этом разделе рассматриваются точные алгоритмы вычисления апостериорных вероятностей и приводятся сведения о сложности такой задачи. Как оказалось, в общем случае эта задача неразрешима, поэтому в разделе 14.5 рассматриваются методы приближенного вероятностного вывода.