Часть 8.

В нашем примере все пары связаны конъюнкцией, так что в качестве меры правила берется минимум их мер:

IFx, = Pand x2 = Z THEN u = P

min(0,5;0,2) = 0,2P

IF x, = P and x2 = N THEN u = Z

min(0,5; 0,8)=0,5Z

IF x, = Zand x2 = ZTHEN u = Z

min(0,5;0,2)=0,2Z

IF x, = Z and x2= N THEN u = N

min(0,5; 0,8)=0,5/V

Затем полученные результаты объединяются (выполняется дефаззификация). В нашем примере объединяются две области, показанные на рис. 8.10, полученные в результате активизации этого множества правил. Существует ряд методов дефаззификации [Ross, 1995]. Выберем один из наиболее известных - метод центра тяжести. При использовании этого метода окончательным выходным значением контроллера, применяемым к маятнику, является значение центра тяжести объединения областей выходных значений. На рис. 8.13 представлены и само объединение и центр тяжести объединения областей. Этот выход или результат применяется к системе, снова измеряются значения q и dq/dt, и цикл управления повторяется.

При описании систем нечетких рассуждений мы не рассматривали ряд вопросов, включая колебания в процессе сходимости и выбор оптимальных коэффициентов. Нечеткие системы предоставляют инженерам мощный инструментарий для борьбы с неточностью измерений, особенно в области управления.

Глава 8. Рассуждения в условиях неопределенности 349

8.2.3. Теория доказательства Демпстера-Шафера

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

Альтернативный подход, называемый теорией обоснования Демпстера-Шафера, рассматривает множества предположений и ставит в соответствие каждому из них вероятностный интервал доверия (правдоподобия), которому должна принадлежать степень уверенности в каждом предположении. Мера доверия обозначается toe/ и изменяется от нуля, что указывает на отсутствие свидетельств в пользу множества предположений, до единицы, означающей определенность. Мера правдоподобия предположения р - pl(p) определяется следующим образом:

pl(p) = 1 - bel(not(p)).

Таким образом, правдоподобие также изменяется от нуля до единицы и вычисляется на основе меры доверия предположению not(p). Если not(p) вполне обоснованно, то bel(not(p))= 1, a pl(p) равно 0. Единственно возможным значением для bel(p) также является нуль.

Предположим, что существуют две конкурирующие гипотезы и h2 При отсутствии информации, поддерживающей эти гипотезы, мера доверия и правдоподобия каждой из них принадлежат отрезку [ 0; 1 ]. По мере накопления информации эти интервалы будут уменьшаться, а доверие гипотезам - увеличиваться. Согласно байесовскому подходу (при отсутствии свидетельств) априорные вероятности распределяются поровну между двумя гипотезами: Р (hi)=0,5. Подход Демпстера-Шафера также подразумевает это. С другой стороны, байесовский подход может привести к такой же вероятностной мере независимо от количества имеющихся данных. Таким образом, подход Демпстера-Шафера может быть очень полезен, когда необходимо принимать решение на основе накопленных данных.

Итак, подход Демпстера-Шафера решает проблему измерения достоверности, делая коренное различие между отсутствием уверенности и незнанием. В теории вероятностей мы вынуждены выражать степень нашего знания о гипотезе h единственным числом P(h). Проблема такого подхода, по мнению Демпстера-Шафера, заключается в том, что мы просто не всегда можем знать значения вероятностей, и поэтому не любой выбор Р(h) может быть обоснован.

Функция доверия Демпстера-Шафера удовлетворяет аксиомам, которые слабее аксиом теории вероятности, и сводится к теории вероятности, если все вероятности известны. Функции доверия позволяют использовать имеющиеся знания для ограничения вероятностей событий при отсутствии точных значений вероятностей.

Теория Демпстера-Шафера основана на двух идеях. Первая- получение степени доверия для данной задачи из субъективных свидетельств о связанных с ней проблемах, и вторая - использование правила объединения свидетельств, если они основаны на независимых атомах. Это правило объединения первоначально было предложено Демпсте-ром [Dempster, 1968]. Далее представляется неформальный пример рассуждения Демпстера-Шафера, затем описывается правило Демпстера объединения свидетельств и, наконец, применение этого правила к более жизненной ситуации.

350 Часть ill. Представление и разум в ракурсе искусственного интеллекта

Рассмотрим субъективные вероятности правдивости свидетельств моей подруги Мелиссы. Вероятность того, что ей можно верить, составляет 0,9, а того, что верить нельзя, - 0,1. Предположим, Мелисса говорит, что мой компьютер сломался. Это утверждение истинно, если Мелиссе можно верить, но оно не обязательно ложно, если ей верить нельзя. Таким образом, утверждение Мелиссы, что мой компьютер сломался, обосновывается с достоверностью 0,9, а то, что он исправен - с достоверностью 0,0. Достоверность 0,0 не означает уверенности в том, что компьютер не сломался, как это означала бы вероятность 0,0. Это просто означает, что утверждение Мелиссы не дает причин верить, что мой компьютер не сломался. Мера правдоподобия pi в этой ситуации равна

р1{компьютер_сломался) =1 - Ье^поЦкомпьютер^ломался)^] -0,0,

или 1,0, и моя мера доверия Мелиссе есть [0,9; 1,0]. Заметим, что еще нет основания считать, что мой компьютер не сломался.

Далее рассмотрим правило Демпстера для объединения свидетельств. Допустим, мой друг Билл также говорит, что мой компьютер сломался. Предположим, вероятность того, что Биллу можно верить, составляет 0,8, а что верить нельзя - 0,2. Я также должен предположить, что утверждения Билла и Мелиссы о моем компьютере независимы друг от друга, т.е. они вызваны разными причинами. Событие "Билл заслуживает доверия" также должно быть независимо от события, определяющего степень доверия Мелиссе. Вероятность правдивости и Билла и Мелиссы равна произведению их вероятностей - 0,72; вероятность неправдивости обоих - 0,02. Вероятность того, что верить можно по крайней мере одному из них - 1-0,02 = 0,98. Поскольку оба они говорят, что мой компьютер сломался, и вероятность того, что по крайней мере один из них заслуживает доверия, равна 0,98, можно установить степень достоверности события поломки компьютера [0,98; 1,0].

Предположим, Билл и Мелисса расходятся в том, что мой компьютер сломался: Мелисса утверждает, что он сломался, а Билл говорит, что нет. В этом случае они оба одновременно не могут говорить правду и не могут оба вызывать доверие. Либо обоим им нельзя верить, либо нельзя верить одному из них. Априорная вероятность того, что можно верить лишь Мелиссе, составляет 0,9*(1 - 0,8) = 0,18, а того, что верить можно только Биллу, - 0,8*(1 - 0,9) = 0,08, а того, что ни одному из них верить нельзя, - 0,2*0,1 = 0,02. Имея вероятность того, что по крайней мере одному из друзей верить нельзя, (0,18 + 0,08 + 0,02) = 0,28, можно вычислить апостериорную вероятность того, что верить можно лишь Мелиссе, и мой компьютер сломан - 0,18/0,28 = 0,643; или апостериорную вероятность того, что прав лишь Билл, и мой компьютер исправен - 0,08/0,28 = 0,286.

При этом было использовано правило Демпстера для объединения свидетельств. После заявления Мелиссы и Билла о том, что компьютер сломан, мы рассмотрели три гипотетические ситуации, связанные с поломкой: Биллу и Мелиссе можно верить; Биллу можно верить, а Мелиссе нет; Мелиссе можно верить, а Биллу нет. Доверие результату анализа возможных гипотетических сценариев составила 0,98. При втором использовании правила Демпстера свидетельства расходились. Снова были проанализированы все возможные сценарии. Исключалась единственная ситуация, связанная с тем, что верить можно обоим. Таким образом, либо Мелиссе можно верить, а Биллу нет; либо можно верить Биллу, а не Мелиссе; либо нельзя верить никому из них. Суммарная достоверность поломки составила 0,64. Достоверность того, что компьютер не сломан (согласно мнению Билла), - 0,286. Поскольку правдоподобие поломки составляет 1 -bel(not(поломка)) - 0,714, мера доверия принадлежит интервалу [0,28; 0,714].

Глава 8. Рассуждения в условиях неопределенности 351

Используя правило Демпстера, можно получить меру доверия для одной задачи (Был ли компьютер сломан?) из вероятности для другой (Является ли свидетельство надежным?). Для применения правила необходимо предположить, что задачи, для которых известны вероятности, независимы, но эта независимость лишь априорная. Она исчезает, когда возникает конфликт между различными атомами обоснования.

Использование подхода Демпстера-Шафера в каждой ситуации приводит к решению двух связанных проблем. Во-первых, мы разделяем неопределенность ситуации на априорно независимые части. Во-вторых, применяем правило Демпстера. Эти две задачи взаимосвязаны: предположим опять-таки, что Билл и Мелисса независимо друг от друга сказали, что они были уверены в том, что мой компьютер сломан. Предположим также, что я вызвал мастера для проверки компьютера, и что оба (и Билл, и Мелисса) были свидетелями этого. Из-за этого общего события мы не можем больше сравнивать степени доверия. Однако, явно учитывая возможность приглашения мастера, можно получить три независимых атомарных обоснования: правдивость Мелиссы, правдивость Билла и основание для присутствия мастера, которые можно затем объединить с помощью правила Демпстера.

Предположим, существует исчерпывающее множество взаимоисключающих гипотез. Обозначим его через О. Наша цель - приписать некоторую меру доверия т различным подмножествам Z множества О; т иногда называют вероятностной функцией чувствительности (probability density function) подмножества О. Реально свидетельства поддерживают не все элементы О. В основном поддерживаются различные подмножества Z множества О. Более того, поскольку элементы О предполагаются взаимоисключающими, доказательство в пользу одного из них может оказывать влияние на доверие другим элементам. В чисто байесовской системе (раздел 8.3) обе эти ситуации разрешаются за счет рассмотрения всех комбинаций условных вероятностей. В системе Демпстера-Шафера эти взаимодействия учитываются напрямую путем непосредственного манипулирования множествами гипотез. Величина mn(Z) означает степень доверия, связанную с подмножеством гипотез Z, а п представляет число источников свидетельств. Правило Демпстера имеет вид

Например, мерой доверия mn(Z) гипотезе Z для п=3 источников свидетельств считается сумма произведений гипотетических мер доверия гп\(Х) нт2(У), совместное вхождение которых поддерживаетZ, т.е. XnY=Z. Как видно из примера, знаменатель правила Демпстера допускает пустое пересечение X и У, а сумма мер доверия должна быть нормализована.

Применим правило Демпстера к задаче медицинской диагностики. Предположим, что рассматривается область О, содержащая четыре гипотезы: пациент был без сознания (С), у него был грипп (F), мигрень (Н) или менингит (М). Наша задача - связать меры доверия со множествами гипотез в рамках О. Как отмечалось выше, это именно множество гипотез, поскольку они ничем не обоснованы. Например, лихорадка свидетельствует в пользу {C,F,M}. Поскольку элементы О трактуются как взаимоисключающие гипотезы, подтверждение одной из них может влиять на достоверность других. Как уже говорилось, подход Демпстера-Шафера разрешает взаимодействие посредством прямой обработки множества гипотез.

352 Часть III. Представление и разум в ракурсе искусственного интеллекта

Для вероятностной функции чувствительности т и всех подмножеств Z множества Q значение m(gi) представляет меру доверия, которая назначается каждому q,- из О. Причем сумма всех m(gi) равна 1. Если Q содержит п элементов, то существует 2" подмножеств О - это очень много. Проблема упрощается за счет того, что многие из подмножеств недопустимы. Таким образом, существует некоторое упрощение, и невозможные значения могут быть проигнорированы. И, наконец, правдоподобие О есть р/(О)=1-Zm(qi), где q, - множество гипотез, имеющих некоторую вероятность поддержки. При отсутствии информации о некоторых гипотезах, что чаще всего бывает в начале процесса диагностики, р/(О)= 1,0.

Предположим, первая часть свидетельства - у пациента лихорадка. Она поддерживает {C,F,M} с вероятностью 0,6. Назовем это первой мерой доверия тi. Если это всего лишь гипотеза, то m1{C,F,M} = 0,6, где m1(Q) = 0,4 для оставшегося распределения мер доверия. Важно отметить, что m1(Q) = 0,4 представляет оставшуюся часть распределения достоверности, т.е. все другие возможные меры доверия Q, а не достоверность дополнения {С,F,M}.

Предположим теперь, что мы получили некоторые новые данные для постановки диагноза. К примеру, у пациента сильная рвота, которая свидетельствует о {C,F,H) со степенью доверия 0,7. Назовем меру доверия этому свидетельству т2 Для нее мы имеем m2{C,F,H} = 0,7 и m2{Q} = 0,3. Используем правило Демпстера для объединения этих двух свидетельств m1 и m2 Пусть X- набор подмножеств Q, на котором mi принимает ненулевые значения, и Y - набор подмножеств Q, на котором л?2 принимает ненулевые значения. Затем по правилу Демпстера определим объединенную меру доверия т3 на подмножествах Z множества Q.

При его применении к диагнозам прежде всего отметим, что не существует пустых множеств Хп Y, так что знаменатель равен 1. Распределение вероятностей mз приведено в табл. 8.1.

Четыре множества Z, представляющие все возможные способы пересечения X и У согласно правилу Демпстера, составляют крайний справа столбец табл. 8.1. Степень доверия вычисляется перемножением мер достоверности элементов X и У, для которых заданы т1 и m2 Отметим, что в этом примере каждое множество в Z уникально, что не является частым случаем.

Расширим пример, чтобы показать, как в процессе анализа факторизуются пустые множества достоверности. Предположим, получен новый факт, отражающий результаты лабораторного анализа, который связан с менингитом. Теперь т4{М}= 0,8 и m4{Q}= 0,2. Чтобы объединить результаты предыдущего анализа т3 с m4 для получения т5, можно использовать формулу Демпстера (табл. 8.2).

Глава 8. Рассуждения в условиях неопределенности 353

Сразу отметим, что т5{М} получается в результате пересечения двух различных пар множеств, поэтому общая вероятность т5{М}=0,240. Кроме того, в результате пересечения нескольких пар множеств получается пустое множество {}. Таким образом, знаменатель уравнения Демпстера равен 1 - (0,336 + 0,224) = 1 - 0,56 = 0,44. Окончательные значения функции доверия т5 будут иметь вид

т5{М} =0,545 m5{C,F} = 0,191 m5{}=0,56

m5{C,F,H} = 0,127 m5{C,F,M} = 0,082 m5{Q} = 0,055

Во-первых, высокая достоверность пустого множества m5 { } = 0,56 означает существование конфликта свидетельств на множестве мер доверия mj Данный пример позволяет показать несколько особенностей рассуждения Демпстера-Шафера, поэтому в нем автор пожертвовал медицинской согласованностью. Во-вторых, при существовании больших множеств гипотез, а также сложного множества свидетельств вычисление мер доверия может оказаться громоздким, хотя, как уже отмечалось, количество рассуждений все же значительно меньше, чем при использовании байесовского подхода. И последнее, подход Демпстера-Шафера является очень полезным инструментом, когда более строгие байесовские рассуждения себя не оправдывают.

Подход Демпстера-Шафера является примером алгебры, поддерживающей в рассуждении субъективные вероятности, в противоположность объективным вероятностям Байеса. В субъективной теории вероятностей мы строим алгебру рассуждений, часто ослабляя некоторые ограничения Байеса. Иногда субъективные вероятности лучше отражают рассуждения эксперта-человека. В последнем разделе главы 8 будут рассмотрены байесовские рассуждения, включая использование сетей доверия.

8.3. Стохастический подход к описанию неопределенности

В рамках теории вероятностей можно определить (зачастую априори) шансы наступления событий. Можно также описать, как комбинации событий влияют друг на друга. Хотя последние достижения в области теории вероятностей были получены математиками начала двадцатого столетия, включая Фишера, Неймана и Пирсона, попытка создать комбинаторную алгебру уходит корнями через средние века к грекам, включая Лулла, Порфирия и Платона [Glymour и др., 1995а]. Теория вероятностей строится на предпо-

354 Часть III. Представление и разум в ракурсе искусственного интеллекта

ложении о том, что, зная частоту наступления событий, можно рассуждать о частоте последующих комбинаций событий. Например, можно вычислить шансы на выигрыш в лотерее или в игре в покер.

Существует ряд ситуаций, при которых вероятностный анализ является подходящим средством. Во-первых, эта теория применима, если мир является действительно случайным, как при игре хорошо перетасованными картами или при беспристрастном поведении крупье. В картах, например, следующая карта является функцией от типа колоды и уже вытянутых карт. Во-вторых, этот подход применим при описании "нормального" мира. Хотя события в мире могут не быть совершенно случайными, для предсказания события часто неизвестны причины и их взаимосвязь. Статистические корреляции являются полезной заменой для причинно-следственного анализа, хотя в работах [Glymour и Cooper, 1999], [Pearl, 2000] делается попытка связать понятия вероятности и причинности. Дальнейшее использование вероятностей позволяет выявить возможные исключения в общих взаимосвязях. Статистический подход группирует все исключения, а затем использует эту меру для описания исключения общего вида. Другая важная роль статистики - это основа для индукции и обучения (например, алгоритм ID3 из раздела 9.3).

При решении задач, основанных на знаниях (глава 7), часто приходится проводить рассуждения с ограниченными знаниями и неполной информацией. Многие исследовательские группы направляли свои усилия на изучение различных форм вероятностных рассуждений. В этом разделе сначала описывается полный байесовский анализ, а затем ограниченная форма байесовского вывода, называемая сетями доверия.

8.3.1. Байесовские рассуждения

Байесовские рассуждения основаны на формальной теории вероятностей и интенсивно используются в некоторых современных областях исследований, включая распознавание образов и классификацию. Теория Байеса обеспечивает вычисление сложных вероятностей на основе случайной выборки событий. Например, в рамках простых вероятностных вычислений можно определить, как карты могут распределяться среди игроков. Предположим, я - один из четырех игроков в карточной игре, в которой все карты распределены равномерно. Если у меня нет пиковой дамы, я могу заключить, что вероятность ее нахождения у каждого из остальных игроков равна 1/3. Аналогично можно заключить, что вероятность нахождения у каждого из игроков червового туза также составляет 1/3, и что любой игрок имеет обе карты с вероятностью 1/3*1/3 или 1/9, предположив, что события получения двух карт являются независимыми.

В математической теории вероятностей отдельные вероятности вычисляются либо аналитически комбинаторными методами, либо эмпирически. Если известно, что А и В независимы, вероятность их комбинации вычисляется по следующему правилу:

вероятность(А&В) = вероятность(А) * вероятность(В)

ОПРЕДЕЛЕНИЕ

АПРИОРНАЯ ВЕРОЯТНОСТЬ

Априорная вероятность (prior probability), часто называемая безусловной вероятностью (unconditional probability) события, - это вероятность, присвоенная событию при отсутствии знания, поддерживающего его наступление. Следовательно, это вероятность события, предшествующего какой-либо основе. Априорная вероятность события обозначается Р(событие).

Глава 8. Рассуждения в условиях неопределенности 355

АПОСТЕРИОРНАЯ ВЕРОЯТНОСТЬ

Апостериорная вероятность (posterior probability), часто называемая условной вероятностью (conditional probability) события, - это вероятность события при некотором заданном основании. Апостериорная вероятность обозначается Р(событие| основание).

Априорная вероятность выпадения двойки или тройки при бросании игральной кости - это сумма двух возможностей, деленная на общее число возможных альтернатив, т.е. 2/6. Априорная вероятность болезни отдельного человека равна числу людей с этим заболеванием, деленному на число людей, находящихся под наблюдением.

Апостериорная вероятность заболевания d у человека с симптомом s равна:

P(d\s)= | dns| | s |,

где прямые скобки обозначают число элементов множества. В правой части этого уравнения указано число людей, имеющих как заболевание d, так и симптом s, деленное на количество людей с симптомом s. Расширим это уравнение

P(d\s) = P(dns)/ P(s) и получим эквивалентное соотношение для P(s\d) и P{d n s):

P(s\d) = P(dns)/ P(d), P(dns) = P(s\d) * P(d).

Подстановка этого результата в соотношение P(d| s) дает теорему Байеса (для одной болезни и одного симптома):

P(c/|s) = (P(s|d)*P(d))/P(s).

Важной особенностью теоремы Байеса является то, что числа в правой части уравнения получить легче, чем значение в его левой части. Например, вследствие меньшей популяции намного легче определить число больных менингитом, имеющих головные боли, чем процент больных менингитом из общего числа страдающих головной болью. Более важной особенностью теоремы Байеса является то, что для простого случая одной болезни и одного симптома в вычислениях участвует не очень много чисел. Трудности начинаются, когда мы рассматриваем комплексные заболевания dm из области заболеваний D и комплексные симптомы sn из множества возможных симптомов S. При рассмотрении каждой болезни из D и каждого симптома из S отдельно необходимо собрать и интегрировать тхп измерений. (В действительности тхп апостериорных вероятностей плюс (т+п) априорных вероятностей.)

К сожалению, анализ при этом становится намного сложнее. До сих пор мы рассматривали симптомы отдельно. В действительности отдельные симптомы встречаются редко. Например, когда врач осматривает пациента, он должен учитывать много различных комбинаций симптомов. Эту ситуацию описывает форма правила Байеса с комплексными симптомами.

P(d|s,& s2 &...& sj = (P(d)*P(st& sz&...& sjd)) I P(s,& s2&...& sn).

Для обработки одного заболевания с одним симптомом необходимо лишь тхп измерений. Для каждой пары симптомов s,- и sy- и болезни d необходимо знать как P(Sj & Sj | d), так и P(Sj & Sj). Если S содержит л симптомов, число таких пар будет n*(n-1), или приблизительно n2. Если мы захотим воспользоваться правилом Байеса, то придется вычислить около (тхп2 условных вероятностей) + (n2 вероятностей симптомов) + (т вероятностей болезней) или собрать тхпг+п2+т единиц информации. В реальной медицинской системе с 200 заболеваниями и 2000 симптомами это значение превышает 800000000!

356 Часть III. Представление и разум в ракурсе искусственного интеллекта

Однако есть некоторая надежда, что многие из этих пар будут независимы, т.е. P(Sj | Sj)= P(Sj). Независимость означает, что вероятность s,- не зависит от Sj. В медицине большинство симптомов не связаны, например, облысение с кашлем. Но даже если десять процентов симптомов зависимы, необходимо рассматривать около 80000000 отношений.

Во многих задачах диагностики приходится иметь дело с отрицательной информацией, когда симптом у пациента отсутствует (например, низкое давление крови). В обоих случаях необходимо, чтобы

P(not s) = 1 - P(s) и P(not d | s)= 1 - P(d|s).

Наконец, следует отметить, что P(s|d) и P(d| s) - это не одно и то же, и в любой ситуации эти величины будут иметь различные значения. Эти отношения и попытка избежать циклических рассуждений являются важными при разработке байесовских сетей доверия (подраздел 8.3.2).

Далее будет представлен один из наиболее важных результатов теории вероятностей - теорема Байеса в общей форме. Она обеспечивает способ вычисления вероятности гипотезы Н„ следующей из отдельного основания, если даны лишь вероятности основания, следующего из реальных причин (гипотез).

где

Р(Н,|?) - вероятность истинности Н, при заданном основании Е; P(Hj) - вероятность истинности W, вообще;

Р(Е|Hj) - вероятность наблюдения основания, если истинно Н;

п - число возможных гипотез.

Предположим, необходимо определить вероятность обнаружения меди на основе пробы грунта. Для этого нужно знать наперед вероятность обнаружения каждого из множества минералов и вероятность определенного грунта при обнаружении каждого отдельного минерала. Тогда можно использовать теорему Байеса для определения вероятности присутствия меди на основе пробы грунта. Этот подход используется в системе PROSPECTOR, созданной в Стэндфордском университете и применяемой для геологоразведки (меди, молибдена и др.). Система PROSPECTOR позволила обнаружить коммерчески значимые залежи минералов в нескольких местах [Duda и др., 1979а].

Для использования теоремы Байеса существует два главных требования. Первое заключается в том, что должны быть известны вероятности взаимосвязи основания с различными гипотезами, а также вероятности взаимосвязи различных частей основания. Второе, и иногда более трудное в определении, требование заключается в том, что должны быть вычислены все взаимосвязи между основанием и гипотезами или Р(Е | Нк). Вообще и особенно в таких областях, как медицина, предположение независимости не может быть априори обоснованным.

Последняя проблема, затрудняющая использование сложных байесовских систем, заключается в переопределении таблицы вероятностей при выявлении новых взаимосвязей между гипотезами и обоснованиями. В таких активных исследовательских областях, как медицина, новые открытия осуществляются непрерывно. Для корректности заключений байесовских рассуждений требуется (постоянное) вычисление полных вероятностей, включая объединенные вероятности. Во многих областях такой обширный сбор данных и

Глава 8. Рассуждения в условиях неопределенности 357

верификация не возможны, а если и возможны, то стоят очень дорого. Там, где эти предположения выполняются, байесовский подход обеспечивает математически хорошо обоснованное управление неопределенностью. Большинство областей экспертных систем не удовлетворяют этим требованиям и должны опираться на эвристический подход. Более того, из-за сложности задач даже очень мощные компьютеры не могут использовать байесовские методы для успешного решения задач реального времени. В завершение этого раздела приведем небольшой пример, позволяющий показать, как полный байесовский подход можно использовать для организации взаимосвязей гипотеза-основание.

Предположим, вы ведете автомобиль по скоростной трассе и осознаете, что существенно снижаете скорость из-за большого скопления транспорта. Вы пытаетесь найти возможное объяснение снижения скорости. Может, это связано с ремонтом дороги? Была авария? Возможно, существуют и другие объяснения. Через несколько минут вы проезжаете мимо группы дорожных рабочих в оранжевых комбинезонах, расположившихся посреди дороги. В этот момент вы решаете, что наилучшим объяснением является ремонт дороги. И альтернативная гипотеза аварии отбрасывается. Аналогично, если бы вы увидели впереди "мигалку" автомобиля автоинспекции или скорой помощи, наилучшим объяснением этой ситуации стала бы транспортная авария, позволяющая отбросить версию о ремонте дороги. Отказ от гипотезы вовсе не означает, что она вообще невозможна. Скорее, в контексте нового основания она имеет намного меньшую вероятность.

На рис. 8.14 представлена байесовская интерпретация этой ситуации. Ремонт дороги связывается с оранжевыми комбинезонами и замедленным движением. Аналогично авария связывается с мигалкой и замедленным движением. Далее согласно рис. 8.14 строится объединенное вероятностное распределение для отношения ремонт дороги и замедленное движение. Упрощенно предположим, что эти переменные могут принимать значения true (?) или false (f). Вероятностные распределения для этого случая показаны на рис. 8.15. Отметим, что, если ремонт имеет значение f, замедленное движение невозможно, а при значении t - возможно. Отметим также, что вероятность того, что дорога сконструирована как скоростная С = true, равна 0,5, а вероятность замедленного передвижения Г = true равна 0,4 (это относится к штату Нью-Мексико).

358 Часть III. Представление и разум в ракурсе искусственного интеллекта

Далее рассматривается вероятность ремонта дороги при условии замедленного движения - Р(С | T or P(C=t | T=t). Используя упрощенное правило Байеса, получим

Р(С|Т) = P{C=t,T=t)/(P(C=t,T=t) + P(C=t,T=t)) =0,3/(0,3+0,1)=0,75.

Так что теперь вероятность ремонта дороги при замедленном движении возрастает с 0,5 до 0,75. Аналогично эта вероятность возрастет еще больше при наличии комбинезонов, позволяющих напрочь отбросить гипотезу аварии.

Кроме необходимости знать значение любого из параметров в каждом состоянии, следует учитывать вопросы сложности. Рассмотрим вычисление объединенной вероятности для всех параметров, показанных на рис. 8.14 (используя топологическую сортировку переменных).

P(C,A,B,T,L)=P(C)*P{A | С)*Р(В| С,А)*Р(Т| C,A,B)*P(L| С,А,В,Т).

Это, конечно, общая декомпозиция вероятностных мер, которая всегда истинна. Стоимость генерации таблицы объединенной вероятности экспоненциально возрастает с ростом числа параметров. В данном случае требуется таблица размером 25, или 32. Мы рассматриваем игрушечную проблему лишь с пятью параметрами. Для более интересной ситуации, скажем, с тридцатью или более параметрами потребуется таблица объединенной вероятности с биллионом элементов. Байесовские сети доверия позволяют решить вопросы представления и сложности вычислений.

8.3.2. Байесовские сети доверия

Несмотря на то, что байесовская теория вероятностей обеспечивает математическую основу для рассуждений в условиях неопределенности, сложность, возникающая при ее применении к реальным предметным областям, может оказаться недопустимой. К счастью, мы можем уменьшить эту сложность, сфокусировав поиск на меньшем множестве наиболее адекватных событий и свидетельств. Подход, называемый байесовскими сетями доверия (Bayesian belief network) [Pearl, 1988], предлагает вычислительную модель рассуждения с наилучшим объяснением множества данных в контексте ожидаемых причинных связей в предметной области.

Байесовские сети доверия ослабляют многие ограничения полной байесовской модели и показывают, как данные из предметной области (или даже отсутствующие данные!) позволяют разделять и фокусировать рассуждения. Наблюдения показывают, что модульность предметной области часто позволяет ослабить многие ограничения зависимости/независимости, требуемые для правила Байеса. В большинстве ситуаций не надо строить большую таблицу объединенной вероятности, содержащую вероятности всех возможных комбинаций событий и свидетельств. Человек-эксперт выбирает локальные явления, которые заведомо связаны друг с другом, и получает вероятности или меры влияния, которые отражают лишь эти кластеры событий. Эксперты предполагают, что остальные события или условно независимы, или их корреляции настолько малы, что ими можно пренебречь.

Рассмотрим снова пример транспортной задачи, показанный на рис. 8.14. Если предположить, что параметры зависят только от вероятностей их родителей, т.е. допустить, что при наличии знания о родителях узлы являются независимыми от других предшественников, то вычисление Р( C,A,B,T,L) выполняется следующим образом:

P(C,A,B,T,L) = P{C)*P(A)*P(B|C)*P{T|CA)*P(L|A).

Глава 8. Рассуждения в условиях неопределенности 359

Чтобы лучше проиллюстрировать сделанное нами упрощение, рассмотрим вероятность Р(В| С, А) из предыдущего уравнения. В последнем уравнении мы ослабили ее до Р( В | С). Это основывается на предположении, что авария не влияет на ремонт дороги. Аналогично на "оранжевые комбинезоны" не влияет замедленное движение, но ремонт и авария учитываются в Р(Т| С, А), а не в Р(Т| С, А,В). Наконец, P(L| C,A,B,T) ослабляется до P(L | А)! Вероятностное распределение для Р(С,А,В, T,L) теперь имеет всего 20 параметров (а не 32). При переходе к более жизненной проблеме, скажем, с 30 переменными, где каждое состояние имеет максимум двух родителей, в распределении будет не более 240 элементов. Если каждое состояние имеет трех родителей, в распределении будет максимум 480 элементов - значительно меньше, чем биллион, требуемый для полного байесовского подхода!

Необходимо обосновать зависимость узла сети доверия от родительских узлов. Связи между узлами сети доверия представляют условные вероятности причинного влияния. В рассуждении эксперта, использующего причинно-следственный вывод, неявно предполагается, что эти влияния являются направленными, т.е. реализация некоторого события вызывает другие события в сети. Кроме того, рассуждение причинного влияния не является цикличным, а раз так, воздействие не может вернуться назад, чтобы вызвать себя. По этим причинам байесовские, сети доверия могут быть естественным образом представлены в виде ациклического направленного графа (АНГ) (подраздел 3.1.1), где логически последовательные рассуждения отображаются как пути, проходящие через дуги причина-симптом.

В транспортном примере мы имеем даже более устойчивую ситуацию - здесь нет ненаправленных циклов. Это позволяет очень просто вычислять вероятностное распределение в каждом узле. Распределение узлов, не имеющих родителей, находится непосредственно. Значения узлов-наследников вычисляются на основе вероятностного распределения каждого из родителей путем соответствующих вычислений по таблицам условных вероятностей. Это возможно потому, что мы не заботимся о корреляциях между родителями любого узла (поскольку сеть задается как ациклический направленный граф). Это обеспечивает естественное абдуктивное отделение, при котором авария совсем не коррелирует с наличием "оранжевых комбинезонов" (см. рис. 8.14).

Далее рассмотрим предположение, неявно используемое в рассуждениях многих экспертов: присутствие или отсутствие данных об области может разделять и фокусировать поиск объяснений. Этот факт имеет важные комплексные последствия для пространства поиска. Приведем несколько примеров и концепцию d-отделения (d-separation), поддерживающую эти интуитивные рассуждения.

Сначала рассмотрим задачу диагностики наличия масла в автомобиле: предположим, старые поршневые кольца вызывают чрезмерное потребление масла, что, в свою очередь, приводит к низкому уровню масла. Эта ситуация отображается на рис. 8.16, а, где А - старые поршневые кольца, V - чрезмерное потребление масла и В - низкий уровень масла. Ничего не зная о чрезмерном потреблении масла, мы получаем причинное отношение между старыми поршневыми кольцами и низким уровнем масла. Однако, если проверка показывает, что переменная V, характеризующая чрезмерное потребление масла, имеет значение true или false, то переменные, описывающие старые поршневые кольца и низкий уровень масла, не зависят друг от друга.

Во втором примере старые поршневые кольца могут вызвать как синий выхлоп, так и низкий уровень масла. Эта ситуация показана на рис. 8.16, б, где V- старые поршневые кольца, А - синий выхлоп и В - низкий уровень масла. Не зная, какое значение имеет

360 Часть III. Представление и разум в ракурсе искусственного интеллекта

переменная В - true или false, - мы не знаем, являются ли переменные А (синий выхлоп) и В (низкий уровень масла) коррелированными; наличие информации о переменной V (старые поршневые кольца) означает, что эти переменные не коррелированы.

И, наконец, если низкий уровень масла вызван либо чрезмерным его потреблением, либо утечкой, то при наличии данных о низком уровне масла эти две возможные причины являются коррелированными. Более того, если переменная V (низкий уровень масла) истинна (рис. 8.16, в), то утечка масла объясняет его чрезмерное потребление. Если же состояние переменной V (низкий уровень масла) неизвестно, то эти две возможные причины являются независимыми. В любом случае информация о низком уровне масла является ключевым элементом в процессе рассуждения. Эта ситуация изображена на рис. 8.15, в, где переменная А означает чрезмерное потребление масла, В - утечку и V - низкий уровень масла.

Уточним эти интуитивные представления, определив d-отделение узлов в сети доверия [Perl, 1988].

ОПРЕДЕЛЕНИЕ d-ОТДЕЛЕНИЕ

Два узла А и В в ациклическом направленном графе являются d-отделенными, если все пути между ними блокированы. Путь - это любая непрерывная последовательность связей на графе (связывающая узлы в любом направлении, например, на рис. 8.17, б- путь от A к B). Путь является блокированным, если существует промежуточный узел V, обладающий одним из следующих свойств: связь является последовательной или расходящейся, и состояние V известно; связь является сходящейся, и ни V, ни любой из наследников V не имеют обоснования.

Глава 8. Рассуждения в условиях неопределенности 361

Дополнительные примеры последовательных, расходящихся и сходящихся отношений между узлами приводятся на рис. 8.17. Из этого рисунка видно, как d-отделение влияет на построение путей.

Перед тем как закончить рассмотрение графов на рис. 8.16, покажем, как предположения байесовской сети доверия упрощают вычисления условных вероятностей. По закону Байеса любое объединенное распределение вероятностей может рассматриваться как произведение условных вероятностей. На рис. 8.16, а условная вероятность для пути от А до V и от V до S вычисляется следующим образом

P(A,V,B) = Р(А) * P(V|A) * P(B|A,V).

Используем предположение байесовской сети доверия, что условная вероятность переменной при заданных значениях вероятностей всех ее предшественников равна условной вероятности при заданных значениях лишь для родителей. В результате в приведенном выше уравнении Р( В \ А, V) заменяется на Р( В \ V), поскольку V является прямым родителем В, a A - нет. Объединенные вероятностные распределения для трех сетей, показанных на рис. 8.16, вычисляются следующим образом.

a)P(A,V,B) = Р(А) * P(V|A) * P(B|V), 5)P(V,A,B) = P(V) * P(A|V) * P(B|V), b)P(A,B,V) = P(A) * P(B) * P(V|A,B).

Как показывает транспортный пример (см. рис. 8.14), в более масштабных байесовских сетях доверия многие переменные условных вероятностей могут быть исключены. Это делает сети доверия значительно более простыми в реализации, чем полный байесовский анализ.

В следующем примере [Pearl, 1988] рассматривается более сложная байесовская сеть. Как показано на рис. 8.17, переменная season (сезон) определяет вероятность rain (идет дождь), а также вероятность water (вода поступает из поливной системы). Переменная Wet sidewalk (мокрый тротуар) будет коррелировать с дождем или водой из поливной системы. Наконец, тротуар будет slick (блестящим) в зависимости от того, мокрый он или нет. На рисунке показаны вероятностные отношения для этой ситуации. Отметим также, что в отличие от транспортного примера в данном графе имеется ненаправленный цикл.

Теперь зададим вопрос, как может быть описана вероятность мокрого тротуара Р( WS). Это не может быть сделано так, как было описано выше, т.е. Р( IV) = Р( W| S) * P(S) или P(R) = P(R|S) * P(S). Обе причины WS являются взаимно независимыми, например: если время года - это лето, то можно использовать как Р( W), так и Р( R). Таким образом, должны быть вычислены полные корреляции двух переменных, а также их корреляция с S. В данной ситуации это возможно, но сложность таких вычислений экспоненциально зависит от числа возможных причин WS. Результаты вычислений представлены на рис. 8.18. Здесь вычисляется один элемент x при истинных значениях Я и W; для простоты предполагается, что переменная S (время года) может принимать значения либо hot (теплое), либо cold (холодное).

х = Р(Я = Г, W = t) для всех условий S, season

= P(S = hot) * P(R=t\ S = hot) * P(tV= t\ S = hot) +

P(S = cold) * P(R = t | S = clod) * P(W= t\S = cold)

Аналогичным образом можно вычислить остальные значения таблицы, показанной на рис. 8.18. При этом получим объединенную вероятность дождя и воды из поливной системы. Такой "макроэлемент" представляет Р( WS) = P(WS| R,W) * Р(R, W). Эта задача

362 Часть III. Представление и разум в ракурсе искусственного интеллекта

решена в рамках приемлемых объемов вычислений, но проблема состоит в том, что объем вычислений экспоненциально увеличивается с ростом числа родителей состояния.

Назовем этот макроэлемент объединенной переменной для вычисления P(WS). Теперь введем понятие клики, чтобы заменить ограничения АНГ из рис. 8.17 ациклическим деревом клик, которое показано на рис. 8.19. Прямоугольники означают переменные, выше и ниже которых находятся клики. Размер таблицы, описывающей передачу параметров через следующую клику, экспоненциально зависит от числа этих параметров. Необходимо отметить, что в клике должна быть представлена связанная переменная вместе с ее родителями. Таким образом, при построении сети доверия (процесс инженерии знаний) необходимо задумываться о количестве родителей каждого состояния. Как показано на рис. 8.19, б, клики могут пересекаться и передавать информацию через полное дерево клик, называемое объединенным деревом. Представим алгоритм создания объединенного дерева на основе сети доверия. Этот алгоритм разработан в [Lauritzen и Spiegelhalter, 1988].

Для всех узлов сети доверия сделать все направленные связи ненаправленными.

Для каждого узла начертить связи между всеми его родителями (штриховая линия

между узлами R и W на рис. 8.19, б).

Просмотреть каждый цикл в результирующем графе длины >3 и добавить дополнительные связи, ослабляющие этот цикл до дерева. Этот процесс называется триангуляцией и не является необходимым для примера, показанного на рис. 8.19, б.

Сформировать объединенное дерево из результирующих триангулярных структур.

Это делается с помощью выявления максимальных клик (клик, являющихся пол

ными подграфами, а не подграфами больших клик). Переменные в этих кликах

объединяются, и создается результирующее объединенное дерево. В нем соединяются любые два объединения, содержащих по крайней мере одну общую переменную, как показано на рис. 8.19, а.

Процесс триангуляции, описанный в п. 3, является критическим, так как при распространении информации результирующее объединенное дерево должно иметь минимальную вычислительную стоимость. К сожалению, это решение является NP-сложным. Но, к счастью, для получения результата часто достаточно применить несложный ограни-

Глава 8. Рассуждения в условиях неопределенности 363

ченный алгоритм. Отметим, что размеры таблиц, необходимых для обработки объединенного дерева, показанного на рис. 8.19, составляют 2*2*2, 2*2*2 и 2*2 соответственно.

И, наконец, рассмотрим пример сети на рис. 8.17 и вернемся к вопросу d-отделения. Напомним, что при наличии некоторой информации d-отделение позволяет проигнорировать при вычислении вероятностных распределений часть сети доверия.

SL d-отделимо от R, S, W, если известно WS.

d-отделение является симметричным, т.е. S также d-отделимо (и не является объяснением SL) при знании WS.

R и W являются зависимыми вследствие S, но значения S, R и W являются d-

отделенными.

Если известно значение WS, то R и W не являются d-отделимыми, если же значение WS не известно - являются.

При заданной цепочке R®WS®SL, если известно WS, то R и SL являются d-

отделимыми.

Мы должны быть осторожны, если известна информация о наследниках некоторого состояния. Например, если известно SL, то R и W не являются d-отделимыми, поскольку SL коррелирует с WS, a WS, R и W не являются d-отделимыми.

Заключительный комментарий: байесовские сети доверия отражают рассуждения человека о сложных областях, где некоторые факторы известны и априори связаны с другими. Поскольку рассуждение реализуется при постепенной конкретизации информации, последующий поиск ограничивается, и в результате оказывается более эффективным. Эта эффективность поиска сильно контрастирует с представлением (поддерживаемым применением точного закона Байеса) о том, что добавление информации вызывает экспоненциальный рост статистических отношений и расширение результирующей области поиска.

Существует ряд алгоритмов для построения сетей доверия и распространения информации при получении нового основания. Автор особенно рекомендует подход, основанный на передаче сообщений, изложенный в [Pearl, 1988], а также метод триангуляции дерева клик, предложенный в работе [Laurintzen и Spiegelhalter, 1988]. В работе [Druzdel

364 Часть III. Представление и разум в ракурсе искусственного интеллекта

и Henrion, 1993] также представлены алгоритмы, позволяющие вычислить распространение влияния в сети. В работе [Dechter, 1996] в основу унифицированной системы вероятностного вывода положен алгоритм сегментного исключения.

Однако при использовании сетей доверия остается много ограничений как с точки зрения инженерии знаний, так и с точки зрения вычислительной сложности [Xiang и др., 1993], [Laskey и Mahoney, 1997]. Эти ограничения мотивированы разнообразием исследований в иерархических и компонуемых байесовских моделях [Koller и Pfeffer, 1997,1998], [Pfeffer и др., 1999], [Xiang и др., 2000]. Эти новые формализмы моделирования поддерживают декомпозицию модели подобно объектно-ориентированному проектированию программного обеспечения. Дальнейшие расширения до полных стохастических моделей Тьюринга можно найти в [Koller и Pfeffer, 1997], [Pless и др., 2000]. В работе [Pearl, 2000] используются стохастические методы поддержания философской идеи причинности.

Стохастические методы играют важную роль в области искусственного интеллекта, например, в решении задач с вероятностными агентами [Kosoresow, 1993]. Со стохастическими методами мы снова встретимся при рассмотрении проблем обучения (раздел 9.7) и задач понимания естественного языка (глава 13).

8.4. Резюме и дополнительная литература

С самого начала исследований в области искусственного интеллекта существовал круг ученых, хорошо чувствовавших логику и предлагавших ее расширения, достаточные для представления интеллекта. Для описания рассуждений в условиях неопределенности были предложены важные альтернативы исчислению предикатов первого порядка.

Многозначные логики расширили логику путем добавления к стандартным значениям true и false таких новых значений истинности, как unknown. Это может обеспечить механизм для отделения ложных утверждений от утверждений, истинность которых просто неизвестна.

Модальные логики добавляют операторы, которые позволяют решать проблемы,

связанные со знаниями, их достоверностью, необходимостью и возможностью.

В данной главе обсуждались модальные операторы unless и consistent with.

Временные логики дают возможность квантифицировать выражения относительно логики, указывая, например, что выражение всегда истинно или будет истиннов определенное время в будущем.

Логики более высокого порядка. Многие категории знаний включают понятия

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

только переменные, но и предикаты. Действительно для работы с этими знаниями

нужны логики более высокого порядка или достаточно логики первого порядка?

Если они нужны, как их описать наилучшим образом?

Логические формулировки определений, прототипов и исключений. Исключения часто рассматриваются как необходимая особенность системы определений. Однако неосторожное использование исключений подрывает семантику представления. Другим вопросом является различие между определением и прототипом или описанием типичных представителей. Какова разница между свойствами класса и типичного представителя? Как должны быть представлены прототипы? Когда прототип является более адекватным представлением, чем определение?

Глава 8. Рассуждения в условиях неопределенности 365

Представления, основанные на логике, продолжают оставаться важной областью исследований [McCarthy, 1968], [Hayes, 1979], [Weyhrauch, 1980], [Moore, 1982], [Turner, 1984].

Существуют и другие важные достижения в области систем рассуждений с поддержкой истинности (СПИ). Основанные на логике СПИ (ЛСПИ) изложены в работе [McAllester, 1978]. В ЛСПИ отношения между предположениями представляются дизъюнктами, которые могут быть использованы для вывода значений истинности любых предположений. Другим подходом является механизм рассуждений на основе множественной достоверности (МДР), подобный механизму рассуждений СПИП [deKleer, 1984]. Аналогичные идеи могут быть найдены в [Martins и Shapiro, 1983]. МДР основывается на логическом языке SWM*, описывающем состояния знаний. Алгоритмы для проверки непротиворечивости базы знаний в процессе рассуждения приводятся в [Martins, 1991]. Более полная информация по алгебре узлов содержится в [Doyle, 1983] или [Reinfrank, 1989]. Логика умолчания позволяет рассматривать любую теорему, выведенную в расширении системы, в качестве аксиомы для дальнейших рассуждений. Эти вопросы рассматриваются в [Reiter и Criscuolo, 1981] и [Touretzky, 1986].

В области немонотонных рассуждений, логики достоверности и поддержки истинности, кроме оригинальных статей, существует обширная литература [Doyle, 1979], [Reiter, 1985], [deKleer, 1986], [McCarthy, 1980]. Стохастические модели описаны в [Pearl, 1988], [Shafer и Pearl 1990], [Davis, 1990] и многочисленных докладах последних конференций AAAI и IJCAI. Автор рекомендует также энциклопедию искусственного интеллекта [Shapiro, 1992]. Обширный материал собран в книгах [Josephson и Josephson, 1994] и [Hobbs и Moore, 1985]. Работа [Pearl 2000] вносит свой вклад в понимание причинно-следственных отношений в мире.

Дальнейшие исследования по ограничениям и минимизации логической модели можно найти в [Genesereth и Nilsson, 1987], [Lifschitz, 1986] и [McCarthy, 1986]. Важный вклад в развитие ограниченного вывода вносит работа [Perlis, 1988], учитывающая отсутствие знаний у отдельного агента. Важная коллекция статей по немонотонным системам собрана в книге [Ginsburg, 1987].

В качестве литературы по нечетким системам мы бы рекомендовали оригинальную статью [Zadeh, 1983]. Более современные реализации этого подхода можно найти в работах [Yager и Zadeh, 1994] и [Ross, 1995]. Задача перевернутого маятника, представленная в подразделе 8.2.2, взята из [Ross, 1995].

Алгоритмы реализации байесовских сетей доверия на основе передачи сообщений изложены в [Pearl, 1988], а метод триангуляции клик (раздел 8.3) изложен в [Lauritzen и Spiegelhalter, 1988]. Этот алгоритм обсуждается в [Shapiro, 1992]. Введение в байесовские сети доверия содержится в [van der Gaag, 1996], а обсуждение качественных вероятностных сетей приводится в [Druzdel, 1996].

Стохастические представления и алгоритмы продолжают оставаться очень актуальной областью исследований [Xiang и др., 1993], [Laskey и Mahoney, 1997]. Ограничения байесовского представления обусловили исследования по иерархическим и компонуемым байесовским моделям [Koller и Pfeffer, 1997, 1998], [Pfeffer и др.,1999], [Xiang и др., 2000]. Дальнейшее расширение этих результатов до полных моделей Тьюринга можно найти в [Pless и др., 2000].

366 Часть III. Представление и разум в ракурсе искусственного интеллекта

8.5. Упражнения

Укажите три прикладные области, в которых необходимы рассуждения в условиях

неопределенности. Выберите одну из этих областей и разработайте шесть правил

вывода, отражающих рассуждения в ней.

Даны следующие правила, применяемые в экспертной системе, работающей на основе "обратной цепочки".

А ? not(B) ? C(0,9) C v D =>E(0,75)

F? А(0,6)

G ?D(0,8)

Система может вывести следующие факты (с заданной достоверностью).

F(0,9)

В(-0,8)

G(0,7)

Используйте стэндфордскую алгебру фактора уверенности для определения Е и его достоверности.

Рассмотрите простое MYCIN-подобное правило: if А ? (6 v С) ?D(0,9) ? Е(0,75).

Обсудите вопросы, возникающие при работе с такими неопределенностями в кон

тексте байесовского подхода. Как это правило можно использовать в рассуждениях

Демпстера-Шафера?

Приведите новый пример диагностических рассуждений и используйте уравнение

Демпстера-Шафера из подраздела 8.2.3 для объединения свидетельств, аналогичного

приведенному в табл. 8.1 и 8.2.

Используйте схему аксиом, представленную в работе [McCarthy, 1980, раздел 4], для

воссоздания результатов, приведенных в разделе 8.1.3.

Создайте сеть рассуждений, подобную представленной на рис. 8.4, и постройте решетку зависимостей для ее посылок, как это сделано на рис. 8.5.

Рассуждения на минимальных моделях являются важными в повседневной жизни

человека. Приведите не менее двух примеров, предполагающих использование минимальных моделей.

Вернитесь к примеру перевернутого маятника из пода 8.2.2. Воспроизведите не менее двух итераций работы нечеткого контроллера.

Напишите программу, реализующую нечеткий контроллер из подраздела 8.2.2.

С использованием литературных источников (например [Ross, 1995]) опишите две

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

Добавьте некоторую новую связь на рис. 8.26, скажем, соединяющую сезон с тротуаром, и создайте дерево клик для представления этой ситуации. Сопоставьте сложность этой задачи с той, которая представлена деревом клик на рис. 8.17.

Добавьте оценки, необходимые для завершения табл. 8.4.

Создайте алгоритм реализации байесовских сетей доверия и примените его к задаче

скользкого тротуара из подраздела 8.3.2. Можно использовать подход передачи со-

Глава 8. Рассуждения в условиях неопределенности 367