В данном разделе приведена реализация программы, применяемой для интерпретации байесовских сетей. Задача состоит в том, чтобы этот интерпретатор при наличии некоторой байесовской сети отвечал на вопросы в следующей форме: "Какова вероятность определенных высказываний, если дана вероятность некоторых других высказываний?" Примеры таких запросов приведены ниже. р(burglary S alarm) =? pf burglary л lightning) =? p{ burglary | alarm л -lightning) =? p{ alarm л -call I burglary) =?
Интерпретатор формирует ответ на любой из этих вопросов, рекурсивно применяя правила, описанные ниже.
1. Вероятность конъюнкции:
р(XiAX2 | Cond) = р[ Xi I Cond} * р{ X, I Xi л Cond)
2. Вероятность возможного события: pWTfi л,,. Л X л...) =1
3. Вероятность невозможного события:
р{ X | Yi л... л -X л...) = О
4. Вероятность отрицания:
р(~Х | Cond) = 1 - р{Х| Cond)
5. Если от некоторого условия Cond зависит вероятность события, дочернего по
отношению к событию X, то для определения вероятности события X необхо
димо использовать теорему Вайеса следующим образом:
Если ccndc - У л 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: л Х2 л... представлена в виде списка высказываний [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! not X, 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, проблемы не возникают, но становятся заметными при обработке более крупных сетей. Однако более эффективная реализация была бы гораздо сложнее,
