Часть 7.

Алгоритм поиска с хронологическими возвратами должен пройти все шаги рассуждения в обратном порядке. Возврат с учетом зависимостей обеспечивает переход непосредственно к источнику противоречивой информации, а именно - к первому предположению об истинности q. Далее надо двигаться вперед, отменяя истинность р, г us. В это же время можно проверить, могут ли г и s быть выведены независимо от р и q. To, что они были выведены из неправильного предположения, не означает, что они не могут быть доказаны иным образом. И, наконец, так как f и и были выведены без р, г или s, пересматривать их не надо.

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

Связать с каждым выполняемым заключением его обоснование. Это обоснование

описывает процесс вывода данного заключения. Обоснование должно содержать

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

Обеспечить механизм нахождения множества ложных предположений в рамках

обоснования, которое привело к противоречию.

Отменить ложные предположения.

Создать механизм, отслеживающий отмененные предположения и отменяющий

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

предположения.

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

В [Doyle, 1979] описана одна из первых систем поддержки истинности, названная системой поддержки истинности с учетом обоснования (justification based truth maintenance system), или СПИО. Джон Дойл (Jon Doyle) был первым исследователем, который явно отделил систему поддержки истинности, сеть предположений и их обоснования от системы рассуждений, действующей в некоторой предметной области. Результатом этого разделения является то, что СПИО взаимодействует с решателем задач (возможно, системой автоматического доказательства теорем), получая информацию о новых предположениях и обоснованиях и, в свою очередь, поставляя решателю задач информацию о предположениях, которые должны быть достоверными с учетом существующих обоснований.

СПИО выполняет три основные операции. Первая - проверка сети обоснований. Эту проверку может инициировать решатель задач с помощью запросов вида: "Должен ли я доверять предположению р? Почему я должен доверять предположению р? Какие предположения лежат в основе р?".

Второй операцией СПИО является модификация сети зависимостей на основе информации, поставляемой решателем задач. Модификация подразумевает введение новых предположений, дополнение или устранение предпосылок, дополнение противоречий и обоснование предположений. Последней операцией СПИО является адаптация сети. Эта операция выполняется всякий раз, когда происходит изменение сети зависимостей. Операция адаптации пересматривает все предположения в соответствии с существующими обоснованиями.

Для демонстрации СПИО сконструируем простую сеть зависимостей. Рассмотрим модальный оператор М, представленный в подразделе 8.1.1, который помещается перед предикатом и читается как "не противоречит". Например,

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

"Xgooc/_sfudenf(X) ? M study_hard(X) ® studyJhard(X) "Yparty_person(Y) ® not( study_hard(Y)) good_student(david)

Поместим это множество предположений в сеть обоснований.

В СПИО каждый предикат, представляющий предположение, связывается с двумя другими множествами предположений. Первое множество, помеченное на рис. 8.1 меткой IN, является множеством предположений, которые должны быть достоверными для рассматриваемого предположения. Второе множество OUT является множеством предположений, которые не должны быть истинными для рассматриваемого предположения. На рис. 8.1 представлено обоснование предиката studyJhard(david), выведенного из предоставленных выше предикатов. Обозначения на рис. 8.1 адаптированы из работы [Goodwin, 1982] и объясняются на рис. 8.2. Предпосылки обоснований помечаются в соответствии с рис. 8.2, а, а комбинации предположений, приводящих к заключению, обозначаются в соответствии с рис. 8.2, б.

Из информации, приведенной на рис. 8.1, решатель задач может заключить, что study_hard(david) истинно, так как предпосылка good_student{david) считается истинной и совместимой с фактом, что хорошие студенты прилежно учатся. К тому же в этом примере нет информации о том, что Давид не учится прилежно.

Добавим предпосылку party_person(david). Это дополнение позволяет вывести not(study_hard(david)), и предпосылка study_hard(david) больше не поддерживается. Обоснования для этой новой ситуации отражены на рис. 8.3. Обратите внимание на метки IN и OUT.

Как свидетельствуют рис. 8.1 и 8.3, в СПИО предикатные отношения явно не выражаются через начальное множество предположений. СПИО - это просто сеть, позволяющая рассматривать лишь отношения между атомарными предположениями и их отрицаниями и использующая эти данные для подтверждения предположений. Полное множество предикатных связей и схем вывода ("X, ?, v, ® и т.д.) используется в самом решателе задач. В системах, описанных в [McAllester, 1978] и [Martins и Shapiro, 1988], СПИО и решатель задач объединены в рамках общего представления.

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

СПИО описывает лишь зависимости между предположениями, но не содержимое этих предположений. Поэтому предположения заменяются идентификаторами, часто имеющими вид ль л2, ..., которые ассоциируются с объектами (узлами) сети. Тогда алгебра множеств IN и OUT позволяет СПИО рассуждать о поддержке предположений.

Итак, СПИО работает со множествами узлов и обоснований. Узлы означают предположения, а обоснования поддерживают их. С узлами ассоциированы метки IN и OUT, указывающие статус предположения для данного узла. Мы можем рассуждать о поддержке любого узла посредством отнесения его ко множествам IN и OUT других узлов, составляющих их обоснования. Первичными операциями алгебры СПИО являются операторы проверки, модификации и адаптации, указанные выше. И, наконец, поскольку проверка обоснования производится путем обратного просмотра связей самой сети обоснований - это пример возврата с учетом зависимостей. Для получения более полной информации об этом подходе в СПИО читайте [Doyle, 1983] или [Reinfrank, 1989].

Другим типом системы поддержки истинности является система поддержки истинности на основе предположений (СПИП). Термин "на основе предположений" впервые был введен в работе [deKleer, 1984], хотя подобные идеи можно отыскать и в [Martins и Shapiro, 1983]. В этих системах для узлов сети не используются метки IN и OUT. Узлы скорее являются множествами предпосылок (предположений), лежащих в основе их вывода. В [deKleer, 1984] также учитывается различие между узлами-предпосылками, являющимися истинными везде, и узлами, которые могут описывать предположения решателя задач, которые позже могут быть отменены.

Преимущество СПИП по отношению к СПИО состоит в дополнительной гибкости, которую обеспечивает СПИП, работая со множеством возможных состояний предположений. Пометив предположения с помощью множеств предпосылок, при которых они истинны, получаем не единое состояние предположения (в СПИО все узлы IN), а скорее ряд возможных состояний- набор всех подмножеств, поддерживающих предпосылки. Создание различных множеств предположений или возможных миров позволяет сравнивать результаты, получаемые при выборе разных предпосылок, обнаруживать противоречия и избавляться от них, а также обеспечивает существование различных решений задачи. К недостаткам СПИП относятся невозможность представления множества предпосылок, которые сами являются немонотонными, и управления ими с помощью решателя задач.

Взаимодействие между СПИП и решателем задач реализовано аналогично системе СПИО. Оно основано на операторах проверки, модификации и адаптации. Единственное различие состоит в том, что в СПИП нет единого состояния предположения, а есть подмножества потенциальных предпосылок. Цель СПИП - найти минимальные множества предпосылок, достаточные для поддержки каждого узла. Эти

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

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

Ниже детально описывается пример из [Martins, 1992]. Предположим, что существует сеть ПСПИ, представленная на рис. 8.4. В этой сети nh пъ n4 и n5 являются предпосылками, которые по предположению являются истинными. Сеть зависимостей отражает то, ЧТО С ПОМОЩЬЮ ПОСЫЛОК Л] И Л2 ВЫВОДИТСЯ N3, С ПОМОЩЬЮ Nз И N4 ВЫВОДИТСЯ N7, С ПОМОЩЬЮ N4 И N5 ВЫВОДИТСЯ N6, И, Наконец, С ПОМОЩЬЮ N ВЫВОДИТСЯ N7-

На рис. 8.5 представлена решетка зависимостей предпосылок (подмножество/ супермножество), показанных на рис. 8.4. Эта решетка подмножеств обеспечивает хороший способ визуализации пространства комбинаций предпосылок. Если некоторые предпосылки вызывают подозрение, СПИП сможет определить, как они соотносятся с другими предпосылками подмножеств. Например, узел л3 на рис. 8.4 поддерживается всеми множествами предпосылок, которые находятся выше {n1 n2} в решетке на рис. 8.5.

Механизм рассуждения СПИП избавляется от противоречий путем удаления из узлов тех множеств предпосылок, которые являются несовместимыми. Предположим, например, что необходимо проверить рассуждения, представленные на рис. 8.4, в связи с противоречивостью узла Nз Поскольку меткой Nз является множество {n1,n2}, это множество предпосылок определяется как противоречивое. Когда эта противоречие обнаруживается, все множества предпосылок, относящиеся к супермножеству {пь n2}, помечаются как противоречивые и удаляются из сети зависимостей. В этой ситуации должна быть удалена одна из возможных меток, ведущих к п7. Полное описание алгоритма устранения противоречий можно найти в [deKleer, 1986].

Существует несколько других важных подходов к рассуждениям с помощью СПИ. Логические системы поддержки истинности (ЛСПИ) строятся на результатах работы [McAllester, 1978]. В ЛСПИ отношения между предположениями представляются с помощью выражений (дизъюнктов), которые можно использовать для вывода значений истинности соответствующих предложений. Другой подход - механизм рассуждений на основе множественной достоверности (МДР) - подобен механизму рассуждений СПИП за исключением того, что решатель задач и система поддержки истинности объединены в одну систему. МДР основывается на логическом языке SWM*, описывающем состояния знаний. Каждое состояние знаний описывается парой дескрипторов: первый отражает базу знаний, а второй - набор множеств в этой базе знаний, предпосылки которых являются несовместимыми. Алгоритмы проверки на несовместимость в процессе рассуждений можно найти в [Martins, 1992].

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

8.1.3. Логики, основанные на минимальных моделях

В предыдущих разделах мы расширили логику с помощью нескольких модальных операторов, которые были специально разработаны для рассуждений об обычных состояниях мира. Это позволяет ослабить требования к полноте наших знаний о мире. Модальные операторы появились вследствие необходимости создания более гибкого и изменчивого описания мира. В этом разделе представляются логики, специально разработанные для рассуждения в двух ситуациях: когда множество утверждений описывает лишь истинные положения, и когда из-за природы решаемой задачи множества предположений являются истинными в большинстве случаев. В первой ситуации используется предположение о замкнутости мира, во второй - ограничения. Эти подходы часто называют рассуждениями на минимальных моделях (reasoning over minimum models).

Как указывалось в разделе 2.3, моделью называется интерпретация, которая удовлетворяет множеству предикатных выражений S для всех значений переменных. Существует несколько определений минимальной модели. Автор определяет минимальную модель как модель, для которой не существует подмоделей, удовлетворяющих множеству выражений S при всех значениях переменных.

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

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

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

Предположение о замкнутости мира основывается на минимальной модели мира. Используются только предикаты, необходимые для решения. Предположение замкнутости влияет на семантику отрицания в рассуждении. Например, если мы хотим опреде­лить, является ли студент членом группы, то можем просмотреть список (базу данных) этой группы. Коль скоро студент явно не помещен в эту базу данных (минимальная мо­дель), он не является членом класса. Аналогично, если необходимо узнать, существует ли авиасообщение между двумя городами, необходимо просмотреть список всех рейсов. Если прямой рейс туда не помещен, то он не существует.

Предположение о замкнутости мира сводится к следующему. Если вычислительная система не может сделать заключения об истинности р(Х), то истинно not(p(X)). Как будет показано в разделе 12.4, на предположении о замкнутости мира строится вывод в системе PROLOG. В разделе 12.4 при использовании минимальных моделей неявно учитывают­ся три предположения (аксиомы). Этими аксиомами являются уникальность имен, замкну­тость мира и замкнутость предметной области. Уникальность имен означает, что все ато­мы с различными именами являются различными. Замкнутость мира приводит к тому, что экземплярами отношений являются лишь те, которые выведены из имеющихся выражений (дизъюнктов). Замкнутость предметной области означает, что атомарными предложениями в предметной области являются только те, которые принадлежат модели. Если эти три пред­положения подтверждаются, минимальная модель является полной логической спецификаци­ей. В противном случае требуется алгоритм поддержки истинности.

Если для использования предположения о замкнутости мира требуется, чтобы были определены все предикаты, составляющие модель, то для алгебры ограничений [McCarthy, 1980], [Lifschitz, 1984], [McCarthy, 1986] необходимо, чтобы были определе­ны только предикаты, существенные для решения задачи. В алгебре ограничений в сис­тему добавляются аксиомы, определяющие минимальную интерпретацию на предикатах из базы знаний. Эти "метапредикаты" (предикаты над предикатами утверждений задачи) описывают способ интерпретации конкретных предикатов. Таким образом, они опреде­ляют границы (или ограничивают) возможные интерпретации предикатов.

В работе [McCarthy, 1980] идея ограничения используется в задаче о миссионерах и каннибалах. Для решения этой задачи необходимо разработать последовательность ходов (по переправе лодки через реку) для шести символов при множестве ограничений. В [McCarthy, 1980] приводится большое число абсурдных ситуаций, которые вполне могли быть использованы при формулировке задачи. Некоторые из них, такие как фактор вет­ра, уже были упомянуты в этом разделе. Несмотря на то что человек рассматривает эти ситуации как абсурдные, соответствующие рассуждения не столь очевидны. Аксиомы ограничений, которые Мак-Карти (McCarthy) предлагает добавить в описание задачи, позволяют точно ограничить множество предикатов.

В качестве другого примера ограничений рассмотрим предикатное выражение из объектно-ориентированной спецификации рассуждений на основе здравого смысла (раздел 8.5).

"Xbird(X) ? not (abnormal(X)) ® flies(X), где bird - птица.

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

Это выражение может встретиться в рассуждениях, в которых одним из свойств птицы является flies (летает). Но что означает предикат abnormal (аномальный)? То, что птица- пингвин, у нее перебито крыло или она мертва? Спецификация предиката abnormal принципиально невозможна.

В алгебре ограничений система аксиом, или множество метаправил, в рамках исчисления предикатов первого порядка используется для генерации предикатов для некото­рой предметной области. Система правил обеспечивает наименьшее расширение для оп­ределенной формулы. Например, если В является системой предположений, включаю­щей знание о мире К и знание из предметной области А(р) о предикате р, то р можно считать минимизированным в том смысле, что минимально возможное количество ато­мов aj, удовлетворяющее p(aj), является также совместимым с А(р) и К. Знание мира К вместе с А(р) и схемой ограничения используются для вывода заключений в стандарт­ном исчислении предикатов первого порядка. Эти заключения затем добавляются в сис­тему предположений В.

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

isblock(A) ? isblock(B) ? isblock(C),

утверждающее, что А, В и С являются блоками. Ограничение предиката isblock приводит к утверждению

"X(isblock(X) ? ((Х=А) v (X=B)v (X=C))).

Это выражение означает, что блоками являются только А, В и С, т.е. только те объекты, которые считаются блоками согласно предикату isblock. Подобным образом предикат

isblock(A) v isblock(B) может быть ограничен утверждением

"X(isblock(X) ? ((X=A)v (Х=В))).

Более подробная информация об использовании схемы аксиом для вывода результатов содержится в [McCarthy, 1980] (раздел 4).

Использование ограничений для таких операторов, как abnormal, аналогично предположению о замкнутости мира, так как допустимы только те связывания переменных, которые может поддерживать abnormal. Алгебра ограничений, однако, позволяет рас­ширить процесс рассуждений посредством предикатного представления. Если имеется предикат p(X) v q(X), то можно ограничить либо предикат р, либо q, либо оба сразу. Та­ким образом, в отличие от предположения замкнутости мира, алгебра ограничений по­зволяет описать возможные связывания переменных через набор предикатов.

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

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

Как отмечалось во введении к этой главе, при абдуктивных рассуждениях рассматриваются правила типа р ?д, в которых q является обоснованным предположением. Тре

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

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

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

В рамках множественного покрытия абдуктивное объяснение определяется как покрытие предикатов, описывающих наблюдения, с помощью предикатов, описывающих гипотезы. В работе [Reggia и др., 1983] описывается покрытие, основанное на бинарном причинном отношении Я, где Я является подмножеством множества {ГипотезыхНаблюдения). Таким образом, абдуктивным объяснением множества наблюдений S2 является множество гипотез S1, достаточное для объяснения S2. Оптимальным является минимальное по­крытие множества S2. Слабость этого подхода заключается в том, что он сводит объяс­нение к простому списку гипотез S1. В ситуациях, где существуют взаимосвязанные или взаимодействующие причины, или где требуется понимание структуры или последовательно­сти причинных взаимодействий, модель множественного покрытая является неадекватной.

Логические подходы к абдукции основаны на более сложной модели объяснения. В работе [Levesque, 1989] абдуктивным объяснением некоторого ранее необъясненного множества наблюдений О считается минимальное множество гипотез Н, совместимых с исходными знаниями агента К. Из гипотез Н и исходных знаний К должны следовать наблюдения О. Более формально

abduce(K.O) = H тогда и только тогда, когда

а) из К не следует О,

б) из H ? K следует О,

в) Н ? К не противоречиво,

г) не существует подмножества Н, обладающего свойствами 1, 2 и 3.

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

Логическое определение абдуктивного объяснения обеспечивает соответствующий ме­ханизм получения объяснения в контексте системы баз знаний. Если из поясняющих гипо­тез должны следовать наблюдения О, то для построения полного объяснения нужно рассу­ждать в обратном направлении от О. Как было показано в разделах 3.3 и 6.2, можно начать с конъюнктивных компонентов О и проводить рассуждения от заключений к антецедентам.

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

Существуют также интеллектуальные способы нахождения полного множества абдуктивных объяснений. Системы поддержки истинности, основанные на предположени­ях (СПИП) ([deKleer, 1986], подраздел 7.2.3), реализуют алгоритм вычисления мини-

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

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

Несмотря на простоту, точность и удобство логической абдукции, ей присущи два взаимосвязанных недостатка: высокая вычислительная сложность и семантическая слабость. В работе [Selman и Levesque, 1990] установлено, что сложность задач абдукции аналогична сложности вычисления множеств поддержки СПИП. Стандартное доказательство того факта, что задача СПИП является NP-сложной, основывается на существовании примеров задач с экспоненциальным числом решений. Авторы не рассматривают вопрос о потенциальной сложности ряда задач, сводя эту проблему к нахождению меньшего множества NP-сложных решений. Для заданной базы знаний хорновских выражений (см. раздел 12.2) авторы приводят алгоритм нахождения единственного объяснения порядка О (к*n), где к - число пропозициональных переменных, an- число вхождений литералов. Однако, если ввести ограничение на типы искомых объяснений, задача снова становится NP-сложной даже для хорновских дизъюнктов.

Одним из интересных результатов работы [Selman и Levesque, 1990] является тот факт, что добавление определенных типов целей или ограничений в задачу абдукции действительно значительно усложняет вычисление. С точки зрения решения задач человеком эта дополнительная сложность удивляет - для человека добавление дополнительных ограничений на поиск объяснений упрощает задачу. Причина усложнения задачи в логической модели абдукции заключается в том, что добавление ограничений приводит к появлению дополнительных дизъюнктов задачи, а не к модификации структуры задачи, упрощающей вывод решения.

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

Одной из простых стратегий получения качественных объяснений является определение абдуктивного множества фактов, т.е. множества дизъюнктов, из которого должны выбираться гипотезы-кандидаты. Это множество дизъюнктов позволяет заранее ограничить поиск теми факторами, которые потенциально могут играть существенную роль в выбранной области. Другой стратегией является добавление критерия отбора для оценки и выбора объяснений. Были предложены различные стратегии отбора, включая минимальность множества. Согласно этой стратегии из двух согласованных множеств предпочтение отдается минимальному, т.е. тому, которое содержится в другом. Критерий простоты приводит к выбору экономных множеств гипотез, т.е. таких, которые содержат меньше непроверенных предположений [Levesque, 1989].

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

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

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

Интересными являются и два следующих механизма выбора объяснения, принимающие во внимание как свойства множества гипотез, так и свойства процедуры доказательства. Первый - абдукция на основе стоимости - сводится к оценке стоимости потенциальных гипотез и правил. Общая стоимость объяснения вычисляется как сумма общей стоимости и правил, используемых для абдукции. Затем конкурирующие множества гипотез сравниваются по стоимости. Одной из естественных семантик, которые могут быть добавлены к этой схеме, является вероятностная семантика [Charniak и Shimony, 1990] (раздел 13.4). Чем выше стоимость гипотезы, тем ниже вероятность событий; чем выше стоимость правил, тем менее вероятны причинные механизмы. Метрики, основанные на стоимости, можно использовать в сочетании с алгоритмами поиска наименьшей стоимости, такими как поиск до первого наилучшего совпадения (см. главу 4), значительно уменьшающими вычислительную сложность задачи.

Второй механизм - выбор на основе когерентности - применяют в том случае, когда необходимо объяснить не простое высказывание, а множество высказываний. В работе [Ng и Моопеу, 1990] доказано, что метрика когерентности лучше метрики простоты для выбора объяснений при анализе естественно-языковых текстов. Авторы определяют когерентность как свойство графа доказательства. Более когерентными считаются объяснения с большим количеством связей между парами наблюдений и меньшим числом непересекающихся разбиений. Критерий когерентности основан на эвристическом предположении о том, является ли предмет объяснения единственным событием или действием с различными аспектами. Обоснование метрики когерентности в задачах понимания естественного языка строится на "принципе красноречия", который говорит о том, что речь оратора должна быть связной и предметной [Grice, 1975]. Не трудно распространить этот подход на другие ситуации. Например, в задаче диагностики все наблюдения рассматриваются в комплексе, поскольку предполагается, что они являются проявлениями одной и той же неисправности.

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

8.2. Абдукция: альтернативы логическому подходу

Логические подходы, описанные в разделе 8.1, являются громоздкими и вычислительно сложными, особенно при их использовании в экспертных системах. В качестве альтернативы в некоторых ранних экспертных системах (например PROSPECTOR) была сделана попытка применить для абдуктивного вывода байесовские методы (раздел 8.3). Однако применимость этого подхода ограничивается предположениями о независимости, непрерывности обновления статистических данных и сложностью вычислений для поддержки стохастического вывода. Альтернативное решение было использовано в Стэндфорде для разработки ранних экспертных систем, в том числе MYCIN [Buchanan и Shortliffe, 1984].

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

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

помощью таких терминов, как "весьма вероятно", "маловероятно", "почти наверняка" или "возможно". Эти "весовые коэффициенты" не основаны на тщательном вероятностном анализе. Они сами являются эвристиками, выведенными из опыта рассуждений о предметной области. В разделе 8.2 вводятся три методологии абдуктивного вывода: Стэндфордский метод неточного вывода на основе фактора уверенности, нечеткие рассуждения и теория Демпстера-Шафера. В разделе 8.3 представлены стохастические подходы к описанию неопределенностей.

8.2.1. Неточный вывод на основе фактора уверенности

Стэндфордская теория фактора уверенности основывается на ряде наблюдений. Во-первых, в традиционной теории вероятностей сумма вероятностей отношения и его отрицания должна равняться единице. Однако нередки ситуации, при которых человек-эксперт, оценив вероятность (достоверность) некоторого отношения значением 0.7, полагает, что отношение истинно, и вовсе не учитывает, что оно может быть ложным. Еще одно предположение, подкрепляющее теорию фактора уверенности, состоит в том, что знание самих правил намного важнее, чем знание алгебры для вычисления их достоверности. Мера уверенности (или доверия) - это неформальная оценка, которую человек-эксперт добавляет к заключению, например: "вероятно, это так", "почти наверняка, это так" или "это совершенно невероятно".

Стэндфордская теория фактора уверенности вводит некоторые простые предположения о мере доверия и предлагает правила для объединения свидетельств при выводе заключений. Первым допущением является разделение меры доверия и недоверия ("за" и "против") для каждого отношения.

Пусть МВ(Н\ Е) - мера уверенности в гипотезе Н при заданном свидетельстве Е.

Обозначим через MD( Н | Е) меру недостоверности гипотезы Н при заданном свидетельстве Е.

Тогда:

1 > МВ(Н|Е) > 0, если MD{H|E)=0, или

1 > MD(H|E) >0, если МВ(Н|Е)=0.

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

CF(H|Е) = МВ(Н|Е) - MD(H|E).

С приближением фактора уверенности CF (certainty factor) к 1 усиливается доверие к гипотезе, а с приближением CF к -1 - ее отрицание. Близость значения CF к 0 означает, что доказательств в пользу гипотезы и против нее слишком мало, либо эти свидетельства сбалансированы.

Когда эксперты формируют базу правил, они сопоставляют с каждым правилом определенное значение CF. Фактор CF отражает их уверенность в надежности правила. Меры уверенности позволяют регулировать производительность системы, хотя слабые вариации меры доверия обычно мало влияют на общую результативность. Эта вторая роль меры доверия подтверждает тезис о том, что "знание - сила". Другими словами, наилучшей гарантией корректности диагностики является целостность самих знаний.

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

Предпосылка каждого правила состоит из ряда фактов, связанных операциями конъюнкции и дизъюнкции. При использовании продукционного правила учитываются факторы доверия, связанные с каждым условием предпосылки. Их сочетание определяет меру доверия всей предпосылке следующим образом. Для предпосылок Р1 и Р2

CF(P1 andP2) = MIN(CF(P1), CF(P2)) и

CF(P1 orP2) = MAX(CF(P1), CF(P2)).

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

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

(Р1 andP2) or РЗ ® Я1(0,7) and R2 (0,3),

где PI, P2 и РЪ - предпосылки, а Я1 и R2 - заключения правила с фактором доверия CF, равным 0,7 и 0,3 соответственно. Эти числа добавляются к правилу при его разработке и представляют уверенность эксперта в выводе, если все предпосылки известны с полной определенностью. Если в процессе выполнения программы для PI, P2 и РЗ получены значения CF, равные 0,6, 0,4 и 0,2 соответственно, то в данном случае RI и R2 следует учитывать с факторами доверия CF, равными 0,28 и 0,12 соответственно. Ниже приводятся вычисления для этого примера.

CF(P1(0,6) and P2(0,4)) = MIN(0,6; 0,4) = 0,4 CF((0,4) or P3(0,2)) = МАX(0,4; 0,2) =0,4

Значение CF для R1 в описании правила равно 0,7, так что Я1 добавляется ко множеству конкретных знаний о данной ситуации со значением CF= (0,7)* (0,4) = 0,28.

Значение CF для R2 в общем правиле равно 0,3, так что R2 добавляется ко множеству знаний о данной ситуации со значением CF (0,3) * (0,4) =0,12.

Требуется определить еще одну метрику. Как объединить несколько значений CF, если два или более правил приводят к одному и тому же результату R? Правило для этого случая отражает аналогию алгебры достоверности с теорией вероятности. Меры доверия при объединении независимых свидетельств перемножаются. Многократно используя это правило, можно объединять результаты любого количества правил, используемых для определения результата R. Если CF(R1) представляет фактор доверия результату Я, а ранее не использованное правило приводит к результату R (снова) со значением CF( R2), то новое значение CF результата Я вычисляется следующим образом:

CF(R1) + CF(R2) - (CF(fl1)*CF(R2)), если CF(R1) и CF( Я2) положительны,

CF(R1) + CF(R2) + (CF(R1) * CF(R2)), если CF(R1) и CF(R2) отрицательны и

во всех остальных случаях, где |Х| - абсолютное значение X.

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

Кроме легкости вычислений эти комбинационные уравнения имеют другие полезные свойства. Во-первых, значение фактора CF, вычисленное согласно этому правилу, всегда будет лежать между 1 и -1. Во-вторых, в результате объединения противоположные значения CF сокращаются, что тоже является положительным моментом. И, наконец, комбинированная мера CF является монотонно возрастающей (убывающей) функцией, что в какой-то мере и следовало ожидать для обобщенного свидетельства.

Итак, мера уверенности стэндфордской алгебры описывает человеческую (субъективную) оценку причинной вероятностной меры. Как указывалось в подразделе 7.1.2, в традиционном байесовском подходе, если А, В и С влияют на D, то при рассуждении о D необходимо выделить и скомбинировать все априорные и апостериорные вероятности, включая P(D), P(D|A), P(D|B), P(D|C), P(A|D). Подход, основанный на стэндфордском факторе уверенности, позволяет специалисту по знаниям описать все эти взаимосвязи одним фактором CF доверия правилу, т.е. if A and В and С then D(CF). Эта простая алгебра лучше отражает способ мышления человека-эксперта.

Теория фактора уверенности может быть подвергнута критике как необоснованная. Несмотря на то что она определяется в рамках формальной алгебры, значение меры доверия не так строго обосновано, как в теории вероятностей. Однако теория фактора уверенности не пытается строить алгебру для "корректного" рассуждения. Она обеспечивает компромисс, позволяющий экспертной системе объединять свидетельства по мере решения задачи. Эти меры являются эвристическими в том смысле, что уверенность эксперта в результатах является неполной, эвристической и неформальной. В системе MYCIN факторы CF используются при эвристическом поиске для установки приоритетов целей и определения точки отсечения, после которой цель не должна более рассматриваться. Но, несмотря на использование факторов CF для поддержки выполнения программы и сбора информации, производительность программы определяется качеством правил.

8.2.2. Рассуждения с нечеткими множествами

Традиционная формальная логика основывается на двух предположениях. Первое связано с установлением принадлежности - для любого элемента и множества, принадлежащего некоторому универсуму, элемент является либо членом множества, либо членом дополнения множества. Второе предположение основано на законе исключения третьего (the law of excluded middle), утверждающем, что элемент не может одновременно принадлежать множеству и его дополнению. Оба этих предположения нарушаются в теории нечетких множеств (fuzzy set theory) Лофти Заде. С точки зрения нечетких множеств множества и законы рассуждений в рамках традиционной логики называют четкими.

Главное утверждение Заде [Zadeh, 1983] заключается в том, что теория вероятностей является хорошим инструментом для измерения случайности информации, но не подходит для измерения смысла информации. В самом деле, путаница, возникающая при использования слов и фраз естественного языка, связана скорее с отсутствием ясности (неопределенность), чем со случайностью. Это является критической точкой для анализа языковых структур и играет важную роль для определения меры достоверности продукционных правил. Для измерения неопределенности Заде пред-

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

лагает теорию возможностей, в то время как теория вероятностей позволяет определить меру случайности.

Теория Заде дает количественное выражение неточности. Для этого вводится функция принадлежности множеству, которая может принимать реальные значения в интервале между 0 и 1. Понятие нечеткого множества (fuzzy set) может быть описано следующим образом: пусть S - множество, as - элемент этого множества. Нечеткое подмножество F множества S определяется функцией принадлежности mF(s), задающей "степень" принадлежности s к F.

На рис. 8.6 представлен стандартный пример нечеткого множества, где S - множество положительных чисел, a F- нечеткое подмножество S, называемое множеством малых чисел. Приведенные ниже различные числовые значения могут иметь распределение "возможности", определяющее их "нечеткую принадлежность" множеству малых

чисел: mF(l) = 1,0, mF(2) = 1,0, mF(3) = 0,9, mF(4) = 0,8 mF(50) = 0,001 и т.д.

Для описания принадлежности положительного числа X множеству малых чисел создается распределение mF возможности для всего множества положительных чисел S.

Теория нечетких множеств связана не с созданием этих распределений, а скорее с правилами вычисления комбинированных возможностей на выражениях, содержащих нечеткие переменные. Таким образом, она включает правила сочетания мер возможности для выражений, содержащих нечеткие переменные. Законы изменения меры возможности для операций or, and и not над этими выражениями напоминают соответствующие соотношения из стэндфордской алгебры фактора уверенности (см. подраздел 8.2.1).

Для нечеткого множества, представленного множеством малых чисел на рис. 8.6, каждое число принадлежит этому множеству с соответствующей мерой достоверности. В традиционной логике "четких" множеств достоверность того, что элемент принадлежит множеству, равна либо 1, либо 0. На рис. 8.7 представлена функция принадлежности множествам понятий "низкие, средние и высокие мужчины". Отметим, что любой элемент может принадлежать более чем одному множеству. Например, мужчина ростом 5'10" принадлежит как множеству средних, так и множеству высоких мужчин.

Далее приводятся правила для сочетания и передачи нечетких мер для задачи, ставшей уже классической в литературе по нечетким множествам, - задачи управления перевернутым маятником. На рис. 8.8 представлен перевернутый маятник, который необходимо удерживать в вертикальном положении. Положение маятника регулируется посредством перемещения основания системы в направлении отклонения маятника и действием силы тяжести. Детерминированный способ решения задачи стабилизации маятника в состоянии равновесия может быть описан с помощью набора дифференциальных уравнений [Ross, 1995]. Преимущество нечеткого подхода к управлению маятниковой системой состоит в том, что можно описать алгоритм эффективного управления системой в реальном времени. Этот алгоритм управления приводится ниже.

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

Упростим задачу стабилизации маятника, рассматривая ее в двухмерном пространстве. Как показано на рис. 8.8, в качестве входных значений контроллера используются две измеряемые величины: первая - угол отклонения маятника от вертикали 0, а вторая - скорость d?/dt, с которой движется маятник. Обе эти величины положительны в правом квадранте и отрицательны в левом. Оба эти значения подаются на вход нечеткого контроллера на каждой итерации работы системы. Выходом котроллера являются величина и направление перемещения основания системы. Команды по перемещению с указанием его направления обеспечивают сохранение равновесия маятника.

Для объяснения работы нечеткого контроллера опишем процесс решения задачи на основе нечетких множеств. Данные, описывающие состояние маятника (? и d?/dt), интерпретируются как нечеткие меры (рис. 8.9), которые используются во множестве нечетких правил. Этот шаг может быть очень эффективно реализован за счет использования нечеткой ассоциативной матрицы (НАМ) (fuzzy associative matrix), показанной на рис. 8.12. В НАМ отношения вход-выход кодируются напрямую. Правила не объединяются, как при традиционном решении задач на основе правил. Все применимые правила активизируются, а затем их результаты объединяются. Общий результат обычно задается областью пространства нечетких выходных параметров (рис. 8.10), который затем подвергается дефаззификации для получения "четкого" управляющего воздействия. Заметим, что и входные, и выходные значения контроллера являются "четкими" значениями. Они представляют точные показания некоторого монитора на входах и точные команды управления на выходе.

Опишем нечеткие области входных значений, ? и d?/dt. В этом примере для ряда нечетких областей входных значений ситуация упрощена, но показан полный цикл применения правил и получения результата контроллера. Диапазон входных значений ? (от -2 до +2 радиан) разделяется на три области: область отрицательных чисел N (Negative), окрестность нуля Z (Zero) и область положительных чисел Р (Positive) (рис. 8.9, а). На рис. 8.9, б представлены три области, на которые разбивается диапазон изменения (от -5 до +5 градусов в секунду) второго входного значения d ? /dt: N, Р и Z.

На рис. 8.10 представлены подмножества выходных значений: большое отрицательное NB (Negative Big), отрицательное N (Negative), нулевое Z (Zero), положительное Р (Positive) и большое положительное РВ (Positive Big). Величина и направление перемещения изменяются в диапазоне от -24 до +24.

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

Предположим, сначала контроллеру передаются значения ? =1 и d ? /dt=-4. На рис. 8.11 иллюстрируется процесс фаззификации этих входных значений. Каждое входное значение можно отнести к двум нечетким множествам. Для 6 мера принадлежности области нуля и области положительных чисел составляет 0,5. Значение d ? /dt принадлежит области N с мерой 0,8 и Z с мерой 0,2. На рис. 8.12 представлена упрощенная форма нечеткой ассоциативной матрицы для этой задачи. Входные значения для 9 или Xi заданы в первом столбце, а для d ? /dt или х2 - в верхней строке матрицы. Выходные значения представлены в правом нижнем квадранте матрицы НАМ размером 3x3. Например,

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

если значение ? равно Р, a d ? /dt - N, НАМ возвращает значение Z. После этого необходимо выполнить дефаззификацию выхода.

В данном случае, поскольку входные значения относятся к двум нечетким областям входного пространства, необходимо применять четыре правила. Как отмечалось выше, объединение правил для нечетких систем выполняется аналогично стэндфордской алгебре фактора уверенности. Фактически Заде [Buchanan и Shortliffe,' 1984] впервые (исторически) предложил эти комбинации правил для алгебры нечетких рассуждений. Если меры принадлежности двух предпосылок связаны конъюнкцией, в качестве меры правила берется минимум этих мер. Если меры двух предпосылок связаны дизъюнкцией, в качестве меры правила берется максимум из этих мер.

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