Формирование рассуждений в байесовских сетях

В данном разделе приведена реализация программы, применяемой для интерпре­тации байесовских сетей. Задача состоит в том, чтобы этот интерпретатор при нали­чии некоторой байесовской сети отвечал на вопросы в следующей форме: "Какова ве­роятность определенных высказываний, если дана вероятность некоторых других высказываний?" Примеры таких запросов приведены ниже. р( burglary S alarm) = ? pf burglary л lightning) = ? p{ burglary | alarm л -lightning) = ? p{ alarm л -call I burglary) = ?

Интерпретатор формирует ответ на любой из этих вопросов, рекурсивно применяя правила, описанные ниже.

1. Вероятность конъюнкции:

р( XiAX₂ | Cond) = р[ Xi I Cond} * р{ X, I Xi л Cond)

2. Вероятность возможного события: pWTfi л ,,. Л X л ...) =1

3. Вероятность невозможного события:

р{X | Yiл ... л -X л . . .) = О

4. Вероятность отрицания:

р( ~Х | Cond) = 1 - р{Х| Cond)

5. Если от некоторого условия Cond зависит вероятность события, дочернего по
отношению к событию X, то для определения вероятности события X необхо­
димо использовать теорему Вайеса следующим образом:

Если ccnd_c - У л Cond, где У - событие в байесовской сети,

дочернее по отношению к событию X то pfXiCoado) = p(XICond) * _P(Y|X л cond) / p{Y|Cond)

6. Если от некоторого условия Cond не зависит вероятность события, дочернего
по отношению к событию X, то могут иметь место следующие случаи:

а) если событие X не имеет родительских событий, то р (X | Cond) = (X), при
условии, что известна вероятность р (X);

б) если событие X имеет родительские события Parents, состояния которых
определяются отношением pcssible_states, то

piX!Cond) = £ р[Х|Ё} p(S|Cond}

В качестве примера рассмотрим следующий вопрос: "Какова вероятность взлома, если известно, что прозвучал тревожный сигнал?" plburgiaryi alarm) = ?

В соответствии с приведенным выше правилом 5:

р(burglary|alarm) = р(burglary) * р!alarm|burglary) / р(alarm)

В соответствии с правилом 6: р[ alarm I burglary) = p(alarir,| sensor) p (sensor ! burglary)

+ p(alarm|-sensor) p(-sensor|burglary)

В соответствии с правилом 6:

р (sensor | burglary) = p (sensor i burglary л lightning) plburolary

л Irghtmng Iburglary) + p (sensor |-burglary л lightning)

Глава 15. Представление знаний и экспертные системы

p(-burglary л lightning|burglary) + р(sensor|burglary л -lightning) pfburglaiyл -lightningIburglary) + p(sensor I -burglary л -lightning) p(-burglary л -lightning burglary)

Применив несколько раз правила 1-4 и используя условные вероятности, задан­ные в сети, получим следующее:

р (sensor | burglary) - 0.9 * 0.0 2 + 0 + 0.9 * 0.98 + 0 = 0,Э pfalarml burglary! = 0.95 * 0.Э + 0.001 * (1 - 0.Э) - 0.8551

Применив несколько раз правила 1, 4, 6, получим: p(alarm) - 0.00467929

Наконец, будет получен следующий результат: р(burglary|alarm) - 0.001 ⁺ 0.B551 / 0.00467929 - 0.182741

Программа, проводящая рассуждения в соответствии с описанными выше прин­ципами, приведена в листинге 15.8. Конъюнкция высказываний X: л Х₂ л ... представлена в виде списка высказываний [XI, Х2, . . . ]. Отрицание -X выражается с помощью терма not X языка Prolog. Основным предикатом этой программы явля­ется следующий: prob( Proposition, Cond, P)

где Р — условная вероятность высказывания Proposition при условии Cond. В про­грамме предполагается, что байесовская сеть представлена с помощью описанных ниже отношений.

• parent ( ParentNode, Node). Определяет структуру сети.

• р ( X, ParentsState, P}. Представляет вероятность события, имеющего ро­дительские события; Р — условная вероятность некорневого узла X в зависи­мости от заданного состояния родительских событий, ParentsState.

• р! X, ?!. Представляет вероятность события, не имеющего родительских со­бытий; X - корневой узел, Р — его вероятность.

В листинге 15.9 приведен пример определения с помощью этих предикатов байе­совской сети, показанной на рис. 15.4. С программой обработки байесовской сети, показанной в листинге 15.8, в которую введено определение сети из листинга 15.9, возможен приведенный ниже диалог. Предположим, что получен предупреждающий телефонный звонок, поэтому требуется узнать вероятность взлома:

?- prob( burglary, [call], P). F = 0.232137

Затем стало известно, что в это время была сильная гроза, поэтому запрос принял следующий вид:

?- о: burglary, [call, lightning], P).

p = 0.00892857

Листинг15.8. Интерпретатор байесовских сетей доверия

% Формирование рассуждений в байесовских сетях доверия

% Байесовская сеть доверия представлена приведенными ниже Отношениями.

parent I ParentNode, Node) % р( Node, ParentStates, Prob)

Prob - условная вероятность узла Node при заданных значениях
% родительских переменных ParentStates, например:

р( alarm, [ burglary, not earthquake], 0.99) % p( Mode, Prob)

вероятность узла, не имеющего родительских узлов

% prob( Event, Condition, P):
______________________

346 Часть II. Применение языка Prolog в области искусственного интеллекта

I

* вероятность события Event при условии Condition равна Р;

% Event - переменная, ее отрицание или список простых событий, представленный в виде ик конъюнкции

prob! [X | Xsj , Cond, Р) :- !, % Вероятность конъюнкции ргоЬС X, Cond, Px) , prob[ Xs, [X I Cond], PRest], Р is Px * PRest.

prob! [], _, 1) :- !. % Пустая КОНЪЮНКЦИЯ

рГОЬ( X, Cond, 1) :-

memberf X, Cond), ». % Из условия Cond следует Х

prob( X, Cond, 0) :-

member! notX, Cond)_r !. % Из условия Cond следует, что X - ЛОЖНО

prob! not X, Cond, P) :- !, % Вероятность отрицания prob( X, Cond, P0>, P is 1 - PO.

% Применить закон Байеса, если условие распространяется на дочерние уэлы узла X

probt х, CoadO, Р) :-

delete ( Y, CondO, Cond) ,

predecessor! X, Y), !, $ Y - дочерний узел узла X

probt X, Cond, Px) ,

probt Y, [X I Cond], PyGivenX) ,

prob( Y, Cond, Py> ,

P is Px * PyGivenX / Py. % Предполагается, что Ру > 0

Случаи, в которых условие не распространяется на дочерние узлы

ргоЬ( X, Cond, P) :-

р| X, Р] , !. % X - корневой узел,- его вероятность задана

ргоЫ X, Cond, Р) :- ! ,

findallt [COBDi,Pi), p(X,COHDi,Pi), CPlist) , % Условия, которые

% распространяются на родительские уэлы sum_probs( CPlist, Cond, P) .

* sum_probs ( CondsProbs, Cond, WeiothedSum) :

% CondsProbs - список условий и соответствующих вероятностей,
% WeightedSum - взвешенная сумма вероятностей условий Conds
% при заданном условии Cond

sum_probs( [] , _, 0) .

sum_probs( [ (CONDI,PI) | CondsProbs], COND, P) :-prob( CONDI, COND, PCI),

sum_probs( CondsProbs, COND, PRest), P is PI * PCI + PRest.

predecessor( X, not Y) :- I, l Переменная Y, к которой применена

% операция отрицания predecessor I X* y) .

predecessor! x, Y) :-

parent { X, Y) .

predecessor! X, Z) :-parent! X, Y) , predecessor! y, z) .

membei X, [X [ )) .

Глава 15.Представление знаний и экспертные системы

member [X, [_ I L] } :-member! X, L) .

delete! x, [x | L] , L) .

delete ! X, [Y I L] , (Y I L2] )

delete ( JC, l , L2) .

Листинг 15.9. Спецификация байесовской сети, показанной на рис. 15.4, которая соответствует требованиям программы в листинге 15.8

% Байесовская сеть доверия "sensor"

parent! burglary, sensor). % Обычно при взломе срабатывает датчик

parent( lightning, sensor). 3 Датчик может сработать при силвной грозе

parent( sensor, alarm).

parent! sensor, call) .

p ( burglary, 0,001.

p( lightning, 0.02} .

p( sensor, [ burglary, lightning), 0.9).

p{ sensor, [ burglary, not lightning], 0.9).

p( sensor, [ not burglary, lightning], 0.1).

p( sensor, E not burglary, not lightning] , С .001) .

p( alarm, [ sensor], 0.95) .

p[ alarm, [ not sensor], 0.001).

p ( call, [ sensor], 0.9).

p( call, [ not sensor], 0.0).

Поскольку предупреждающий звонок можно объяснить сильной грозой, взлом становится гораздо менее вероятным. Но если погода была прекрасной, взлом стано­вится вполне вероятным, как показано ниже. ?- prob( burglary, [call, not lightning), P).

P = 0.473934

Следует отметить, что при разработке показанной здесь реализации интерпретато­ра байесовских сетей была поставлена задача создать короткую и понятную про­грамму. Поэтому полученная программа отличается довольно низкими эксплуатаци­онными характеристиками. При ее использовании для обработки небольших байе­совских сетей, подобных той, которая определена в листинге 15.9, проблемы не возникают, но становятся заметными при обработке более крупных сетей. Однако более эффективная реализация была бы гораздо сложнее,