Часть 6.

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

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

Повторное использование макрооператоров помогает также решить проблему противоречивости подцелей. Если планировщик разработал план достижения целей вида stack(X,Y)^Stack(Y,Z), то этот план можно запомнить и использовать повторно. Это исключает необходимость разбивать цель на подцели и позволяет избежать возможных усложнений.

На рис. 7.21 представлена треугольная таблица для макрооператора stack(X, Y)^Stack(Y, Z). Этот макрооператор можно применять в состояниях, для которых истинно выражение оп(Х, Y)^clear(X)^clear(Z). Эта треугольная таблица соответствует начальному состоянию 1 при X=d, Y=а и Z=c.

Атомарные действия плана записываются вдоль диагонали. Эти четыре действия (pickup, putdown, stack и unstack) рассмотрены ранее в данном разделе. Множество предусловий каждого из этих действий описывается в строке, соответствующей этому действию, а постусловия - в соответствующем столбце. Например, в строке 5 содержатся предусловия, а в столбце 6 - постусловия (списки добавления и вычеркивания) для оператора pickup(X). Постусловия одних действий являются предусловиями других (дальнейших). Цель треугольной таблицы - соответствующим образом упорядочить предусловия и постусловия каждого действия при достижении более крупной цели. Таким образом треугольные таблицы решают вопросы нелинейности планирования на уровне макрооператора. Эти же вопросы можно решить и на основе других подходов, в том числе при использовании частично упорядоченных планировщиков [Russell и Norvig, 1995].

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

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

Ядро п-го порядка, или п-е ядро, - это пересечение всех строк, начиная с n-й, с п столбцами, начиная с крайнего слева. На рис. 7.21 мы очертили третье ядро жирной линией. При выполнении плана, представленного треугольной таблицей, i-я операция (т.е. операция в i-Й строке) может быть выполнена, если все предикаты, содержащиеся в i-м ядре, истинны. Это позволяет проверить, какой шаг может быть выполнен, и восстановить выполнение плана при его нарушении. Для этого в треугольной таблице нужно найти и выполнить действие, соответствующее ядру максимального порядка. Это дает возможность не только возвратиться к предыдущим шагам плана, но и скачкообразно перейти вперед после неожиданного события.

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

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

Глава 7. Сильные методы решения задач 315

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

7.4.3. Адаптивное планирование

С момента появления ранних работ по планированию, описанных в предыдущем разделе [Fikes и Nilsson, 1971], в этой области был получен ряд значительных результатов. Многие из них не связаны с конкретной предметной областью. Но в последнее время особое значение приобретает планирование в специфических областях, где используется распределенный механизм "восприятие-реакция". В следующих разделах будет описана не зависящая от предметной области система адаптивного планирования, а также более специфический планировщик Бартона (Burton) из NASA. В качестве дополнительной литературы по исследованиям в области планирования рекомендуем книгу [Allen и др., 1990].

Адаптивное, или телео-реактивное, планирование (АП) впервые было предложено в [Nilsson, 1994] и [Benson, 1995]. Принцип АП может применяться во многих областях, требующих скоординированного управления сложными подсистемами для достижения целей более высокого уровня. Здесь иерархическая архитектура управления (сверху вниз) соединяется с агентным подходом (раздел 6.4) или управлением снизу вверх. Результатом является система, которая может решать сложные проблемы посредством координации простых проблемно-ориентированных агентов. Такой подход можно обосновать следующим образом. Простые агенты хорошо работают в ограниченных пространствах. С другой стороны, контроллер более высокого уровня может делать более общие заключения, относящиеся ко всей системе. Например, он позволяет оценить, как текущее локальное решение воздействует на процесс решения общей задачи.

Адаптивное управление объединяет аспекты управления по обратной связи и планирование конкретных действий. Адаптивная программа - это последовательность действий, обеспечивающих выполнение целенаправленного плана. В отличие от более традиционных сред интеллектуального планирования [Weld, 1994] здесь не делается предположений о дискретности и непрерывности действий, а также о полной предсказуемости их результатов. Наоборот, целенаправленные действия могут поддерживаться в течение длительного периода времени, т.е. действие выполняется до тех пор, пока удовлетворяются предусловия и не достигнута соответствующая цель. В [Nilsson, 1994] такие действия называются продолжительными (durative). Они могут быть прерваны при активизации некоторого другого действия, более близкого к цели верхнего уровня. При изменении среды управляющие действия быстро изменяются, отражая новое состояние решения проблемы.

Последовательности продолжительных действий представляются специальными структурами данных- TR-деревьями (рис. 7.22). TR-дерево описывается множеством пар условие?действие или продукционными правилами (раздел 5.3). Например,

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

где Сi - условия, а Ai - соответствующие им действия. С0 - это ссылка на цель верхнего уровня дерева, а Ао - нулевое действие, показывающее, что при достижении цели верхнего уровня никаких действий не требуется. На каждом цикле работы такой системы условия Сi оцениваются сверху вниз (С0, С1, ..., Сn) до тех пор, пока не находится первое истинное условие, и действие, связанное с этим условием, выполняется. Затем цикл повторяется. Частота повторения определяется скоростью реакции контура управления.

Продукции Сi?Ai организуются таким образом, что каждое действие Ai, если оно непрерывно выполняется при нормальных условиях, обеспечивает истинность некоторого условия более высокого уровня в TR-дереве. Проход по TR-дереву можно рассматривать как адаптивный. Если некоторое непредвиденное событие в среде управления изменяет результат предыдущих действий, алгоритм возвращается назад к условию правила более низкого уровня, и работа по достижению всех целей высокого уровня возобновляется. Аналогично, если в среде выполнения задачи случается нечто непредвиденное, то управление автоматически перейдет к действию, связанному с истинным условием. TR-деревья могут создаваться с помощью алгоритмов планирования, которые используют общепринятые в искусственном интеллекте методы редукции целей. Начиная от цели верхнего уровня, планировщик находит действия, результат которых приводит к достижению этой цели. Предусловия этих действий образуют новое множество подцелей, и эта процедура исполняется рекурсивно. Процесс завершается, когда предусловия конечных узлов выполняются в текущей среде. Таким образом алгоритм планирования выполняет редукцию цели верхнего уровня к текущему состоянию. Конечно, действия часто имеют побочные эффекты, и планировщик должен тщательно следить за тем, чтобы каждое действие не изменяло предусловия действий более высокого уровня TR-дерева. Таким образом, редукция целей связана с удовлетворением ограничений за счет использования различных стратегий переупорядочения действий.

Итак, алгоритмы TR-планирования используются для построения планов, листья которых соответствуют текущему состоянию среды. Обычно они не позволяют строить

Глава 7. Сильные методы решения задач 317

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

В [Benson, 1994] и [Nilsson, 1995] описывается использование адаптивного планирования для ряда прикладных областей, включая управление распределенными агентами-роботами и построение тренажера для пилотов. В [Klein и др., 1999], [Klein и др., 2000] адаптивный планировщик используется для построения и испытания портативной управляющей системы для ускорителя пучков заряженных частиц. В этих работах область применения адаптивного планирования обосновывается следующим образом.

Ускоритель пучков - это динамическая и зашумленная система.

На процесс настройки ускорителя часто влияют стохастические процессы, радио

помехи или осцилляция источника пучков.

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

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

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

7.4.4. Планирование: пример NASA

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

В этом разделе будет описан планировщик для механизма рассуждений на основе моделей. Вернемся к примеру из [Williams и Nayak, 1996], описанному в подразделе 7.3.2. Система Livingstone - это реактивный диспетчер конфигурации, использующий компонентную модель двигательной установки космического корабля для определения действий по ее реконфигурации (рис. 7.23).

Каждый компонент системы двигателей можно представить в виде последовательности переходов, описывающей поведение этого элемента в рабочем, аварийном режимах и переходы между этими режимами, а также стоимость и вероятность переходов (рис. 7.24). На рис. 7.24 элементы open и closed представляют нормальные рабочие режимы, a stuck open и stuck closed - аварийные. Команда open имеет единичную стоимость и вызывает переход от режима closed к open, а команда close - наоборот. Аварийные переходы переводят клапан из нормального рабочего режима в один из аварийных режимов с вероятностью 0,01.

Поведение элемента в каждом из режимов описывается формулами пропозициональной логики, а переходы между режимами - формулами пропозициональной логики при ограниченном времени. Это описание можно использовать для моделирования цифровых и аналоговых устройств [deKleer и Williams, 1991], [Weld и deKleer, 1990], а также программного обеспечения реального времени на основе модели параллельных реактивных систем [Manna и Penueli, 1992]. Модель системы переходов космического корабля - это композиция систем переходов его компонентов. При этом множество состояний конфигурации космического корабля определяется как прямое произведение состояний его компонентов. Предполагается, что системы переходов всех компонентов действуют синхронно, т.е. каждый переход состояний космического корабля связан с переходом состояний его компонентов. Диспетчер конфигурации, основанный на модели, использует модель переходов системы как для идентификации текущей конфигурации космического корабля в режиме оценивания (РО), так и для перевода корабля в новое состояние в режиме реконфигурации (РР). В РО поэтапно генерируются все переходы космического корабля в состояние, совместимое с текущими наблюдениями. Например, на рис. 7.25 показана ситуация, при которой в предыдущем состоянии левый двигатель запускается нормально, а в текущем состоянии отсутствует тяга. Задача РО - идентифицировать состояние, в которое может перейти корабль с учетом этого наблюдения. На рисунке показаны два возможных перехода, соответствующих неисправности одного из клапанов главного двигателя. Неисправные клапаны обведены кружочками. При этом можно также учитывать многие другие переходы, включая маловероятные двойные отказы.

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

Глава 7. Сильные методы решения задач 319

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

Оба режима (РО и РР) являются реактивными (см. раздел 6.4). В РО текущая конфигурация определяется на основе предыдущей конфигурации и текущих наблюдений. В РР рассматриваются лишь те команды, которые обеспечивают достижение цели в следующем состоянии. При этом ключевую роль играет предположение о синхронности переходов. Альтернативой является последовательное моделирование множества переходов для отдельных компонентов. Однако в этом случае текущая и целевая конфигурация могут оказаться далеко друг от друга, и возможность ограничить вывод небольшим фиксированным числом состояний будет сведена на нет. Поэтому в модели переходы считаются синхронными. Если переходы в программно-аппаратном обеспечении не синхронны, система Livingstone исходит из предположения, что все поочередные переходы корректны и поддерживают достижение

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

желаемой конфигурации. В системе Burton, развивающей основные возможности Livingstone, это предположение отсутствует. В системе Burton планировщик определяет последовательность управляющих воздействий, производящих все желаемые переходы [Williams и Nayak, 1997]. NASA использует архитектуру Burton в проекте Tech Sat 21.

В системе Livingstone не нужно генерировать все переходы и, соответственно, управляющие команды. Требуются только наиболее вероятные переходы и оптимальная команда управления. Для их эффективного вычисления задачи РО и РР необходимо переформулировать как задачи комбинаторной оптимизации. В такой постановке в РО поэтапно генерируются наиболее вероятные траектории корабля. Затем в РР определяется команда наименьшей стоимости, которая переводит корабль из наиболее вероятной текущей конфигурации к конфигурации, соответствующей желаемой цели. Задачи комбинаторной оптимизации решаются с помощью алгоритма поиска до первого наилучшего соответствия (best-first). Более формальное описание РО и РР, а также детальное описание алгоритмов поиска и планирования содержится в [Williams и Nayak, 1996,1996а].

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

Экспертные системы, основанные на правилах, строятся в виде продукционных систем. Вне зависимости от того, основан конечный продукт на данных или на цели, моделью программы является продукционная система, генерирующая граф поиска (глава 5). В главах 14 и 15 будут представлены оболочки экспертных продукционных систем, написанные на языках PROLOG и LISP соответственно. Эти оболочки позволяют реализовать поиск на основе цели. Правила могут включать степень надежности, что обеспечивает возможность эвристического поиска.

Представленный в этой главе материал можно дополнить рядом работ. Особенно рекомендуем подборку оригинальных публикаций по системе MYCIN [Buchanan и Shortliffe, 1984]. Для робастной реализации поиска на основе данных можно использовать программное обеспечение CLIPS, распространяемое NASA [Giarratano и Riley, 1989].

К важным книгам по общей инженерии знаний относятся [Hayes-Roth и др., 1984], [Waterman, 1986], [Alty и Coombs, 1984], [Johnson и Keravnou, 1985], [Harmon и др., 1988] и [Negoita, 1985]. Советуем также прочитать [Ignizio, 1991], [Mockler и Dologite, 1992] и [Durkin, 1994].

Поскольку экспертные системы должны обладать обширными знаниями в конкретной предметной области, важным источником знаний для них являются описания примеров из этой области. Книги из этой категории включают [Klahr и Waterman, 1986], [Keravnou и Johnson, 1986], [Smart и Langeland-Knudsen, 1986], [Coombs, 1984], [Prerau, 1990]. Особенно рекомендуем книгу [Durkin, 1994] из-за ее многочисленных практических предложений по созданию экспертных систем.

Разработан ряд методов для извлечения знаний. Подробная информация по отдельным методологиям представлена в [McGraw и Harbison-Briggs, 1989] и [Chorafas, 1990], а также в [Mockler и Dologite, 1992].

Рассуждения на основе примеров являются ответвлением более ранних исследований группы Шенка (Schank) из Йельского университета по сценариям (см. подразделы 6.1.3 и 6.1.4). Книга [Kolodner, 1993] является всеобъемлющим введением в эту область знаний, а также предлагает ценные взгляды на разработку и проектирование подобных систем. В работах [Leake, 1992,1996] содержатся важные комментарии по реализации объяснений в систе-

Глава 7. Сильные методы решения задач 321

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

Рассуждения на основе моделей берут начало в явном представлении логических цепочек и областях математики, изучающих процессы обучения [Brown и Burton, 1978], [Brown и VanLehn, 1980], [Brown и др., 1982]. Более современные исследования представлены в [Hamscher и др., 1992] и [Davis и др. 1982]. В [Skinner и Luger, 1995] и других работах по агентным архитектурам [Russell и Norvig, 1995] описываются гибридные экспертные системы, в которых взаимодействие множества подходов к решению проблем может создать синергетический эффект.

В разделе, посвященном планированию, описаны некоторые из структур данных и методы поиска, предназначенные для создания планировщиков общего назначения. По этой тематике можно также порекомендовать описание ABSTRIPS или ABstract для генератора отношений STRIPS [Sacerdotti, 1974] и системы NOAH для нелинейного или иерархического планирования [Sacerdotti, 1975], [Sacerdotti, 1977]. Более современные планировщики описаны в разделе 15.3 и работе [Benson и Nilsson, 1995].

Метапланирование - это метод рассуждения не только о плане, но и о процессе планирования. Это играет важную роль в разработке экспертных систем. В качестве первоисточников можно посоветовать литературу по системам Meta-DENDRAL [Lindsay и др., 1980] и Teiresias [Devis, 1982]. Непрерывно взаимодействующие с окружающей средой планировщики, т.е. системы, моделирующие изменяющееся окружение, описаны в [McDermott, 1978].

Дальнейшие исследования включают оппортунистическое планирование, использующее метод классной доски, и планирование, основанное на объектно-ориентированном описании [Smoliar, 1985]. Несколько обзоров по области планирования содержатся в словарях [Ватт и Feigenbaum, 1989] [Cohen и Feigenbaum, 1982] и энциклопедии по искусственному интеллекту [Shapiro, 1987]. Вопросы нелинейного и частично упорядоченного планирования представлены в [Russel и Norvig, 1985]. К этой области относится и работа [Allen и др., 1990].

Наше описание и анализ рассуждений на основе моделей, а также алгоритмы планирования взяты из [Williams и Nayak, 1996,1996а]. Мы благодарны авторам, а также издательству AAAI Press за разрешение описать эти исследования в своей книге.

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

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

Вернемся к упражнению 1. Создайте на русском языке или псевдокоде 15 правил "если...,

то..." (отличных от описанных в разделе 7.2) для представления отношений в этой предметной области. Постройте граф, представляющий взаимосвязи этих 15 правил.

Рассмотрите граф из упражнения 2. Какой поиск вы рекомендуете использовать: на

основе данных или на основе цели? Поиск в ширину или в глубину? Каким образом

здесь могут помочь эвристики поиска? Обоснуйте ответы на эти вопросы.

Выберите другую область для разработки экспертной системы. Ответьте на вопросы

1-3 для этого приложения.

Реализуйте экспертную систему, используя коммерческую оболочку. Особенно рекомендуем оболочку CLIPS [Giarratano и Riley, 1989].

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

Оцените оболочку, которую вы использовали при выполнении упражнения 5. Каковы

ее сильные и слабые стороны? Что в ней можно улучшить? Подходит ли она для решения вашей задачи? Для каких задач предназначен этот инструментарий?

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

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

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

Прочтите и прокомментируйте статью [Devis и др., 1982].

Прочтите одну из ранних статей о рассуждениях на основе моделей, посвященную

обучению детей арифметике [Brown и Burton, 1978] или электронике [Brown и

VanLehn, 1980]. Прокомментируйте этот подход.

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

Используйте коммерческое программное обеспечение (найдите в Internet) для построения

системы рассуждений на примерах из упражнения 10. Если нет готового программного

обеспечения, постройте такую систему на языках PROLOG, LISP или Java.

Прочтите и прокомментируйте статью [Kolodner, 1991a].

Опишите остальные аксиомы границ, необходимые для четырех операторов

pickup, putdown, stack и unstack, упомянутых в правилах 4-7 из раздела 7.4.

Используйте операторы и аксиомы границ из предыдущего упражнения для генерации пространства поиска, показанного на рис. 7.19.

Покажите, как можно использовать списки add и delete для замены аксиом границ при генерации состояния 2 на основе состояния 1 в разделе 7.4.

Используйте списки добавления и вычеркивания для генерации пространства поиска

из рис. 7.19.

Спроектируйте автоматический контроллер, который мог бы использовать списки

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

Укажите не менее двух несовместимых (по предусловиям) подцелей в операторах из

мира блоков (рис. 7.19).

Прочтите исследование ABSTRIPS [Sacerdotti, 1974] и объясните, как управлять линейными (или несовместимыми) подцелями при планировании задач.

В подразделе 7.4.3 был представлен планировщик, созданный Нильсоном и его учениками в Стэндфордском университете [Benson и Nillson, 1985]. Адаптивное планирование позволяет описывать продолжительные действия, т.е. такие, которые остаются истинными в течение определенных временных периодов. Почему системы адаптивного планирования предпочтительнее планировщиков типа STRIPS? Постройте адаптивный планировщик на языках PROLOG, LISP или Java.

Прочтите статьи [Williams и Nayak, 1996], [Williams и Nayak, 1996a] и обсудите системы планирования на основе моделей.

Расширьте схему представления в пропозициональном исчислении, введенную в

[Williams и Nayak, 1996a, С. 973] для описания переходов состояний двигательной

установки.

323

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

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

- Бертран Рассел (Bertrand Russel)

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

возможно лишь приближение к истине.

- Аристотель (Aristotle)

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

- Альберт Эйнштейн (Albert Einstein)

8.0. Введение

Процедуры вывода, описанные в частях I и II, а также большинство процедур из части III основаны на модели рассуждения, используемой в исчислении предикатов: из корректных предпосылок с помощью обоснованных правил вывода можно получить новые гарантированно корректные заключения. Однако, как было показано в главе 7, существует много ситуаций, для которых такой подход не годится. Зачастую полезные заключения должны быть получены из неудачно сформулированных и неопределенных данных с использованием несовершенных правил вывода.

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

325

Для демонстрации проблемы рассуждения в условиях неопределенности рассмотрим правило 2 экспертной системы диагностики автомобиля, представленной в разделе 7.2:

если

двигатель не вращается и

фары не горят,

то

проблема в аккумуляторе или проводке.

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

если

проблема в аккумуляторе или проводке,

то двигатель не вращается и фары не горят.

Если чудо не произойдет, при неисправном аккумуляторе ни освещение, ни двигатель работать не будут!

Эта экспертная система обеспечивает пример абдуктивного рассуждения. Формально абдукция означает, что из P®Q и О можно вывести Р. Абдукция является необоснованным (unsound) правилом вывода, означающим, что заключение не обязательно истинно для каждой интерпретации, при которой истинны предпосылки (раздел 2.2).

Хотя абдукция и является необоснованной, она часто используется при решении проблем. "Логически корректная" версия правила об аккумуляторе не очень важна при диагностике автомобильных неисправностей, поскольку предпосылка "проблема в аккумуляторе" в реальной задаче является целью, а заключение - наблюдаемыми симптомами, с которыми необходимо работать. Тем не менее правило может быть использовано абдуктивно, подобно правилам во многих экспертных системах. Неисправности или болезни вызывают (имплицируют) симптомы, а не наоборот; но диагноз должен ставиться от симптомов к причинам, их вызвавшим.

В системах, основанных на знаниях, с правилом часто связывается фактор уверенности для измерения степени доверия его заключению. Например, правило P®Q (.9) выражает следующее: "Если вы верите, что Р истинно, то О будет выполняться в 90% случаев". Таким образом, эвристические правила могут выражать политику доверия.

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

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

326

В разделе 8.3 вводятся стохастические подходы к неточному выводу. Эти приемы основаны на теореме Байеса, относящейся к рассуждениям о частоте событий на основе априорной информации о них. В заключение приводятся стохастические модели, представленные с помощью байесовских сетей доверия (belief network).

8.1. Абдуктивный вывод, основанный на логике

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

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

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

8.1.1. Логика немонотонных рассуждений

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

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

327

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

Немонотонные системы решают все три вопроса. Во-первых, системы рассуждений часто сталкиваются с отсутствием знаний о предметной области. В данном случае эти знания важны. Предположим, у нас нет знаний о предикате р. Отсутствие знания означает, чтолш не уверены в истинности р или мы уверены, что р не является истинным1} На этот вопрос можно ответить несколькими способами. Система PROLOG (см. главу 14) использует предположение о замкнутости мира и считает ложью все те утверждения, истинность которых не может доказать. Человек часто выбирает альтернативный подход, допуская истинность утверждения, пока не будет доказано обратное.

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

Основа человеческих рассуждений - знание о традиционном ходе вещей в мире. Большинство птиц летает. Родители, как правило, любят и поддерживают своих детей. Выводы делаются на основе непротиворечивости рассуждения с предположениями о мире. В этом разделе обсуждаются модальные операторы, такие как is consistent with (согласуется с) и unless (если не) для реализации рассуждений, основанных на предположениях.

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

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

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

328

При реализации немонотонного рассуждения можно расширить логику с помощью оператора unless. Этот оператор поддерживает вывод на основе предположения о ложности аргумента. Допустим, имеется следующее множество выражений из логики предикатов.

р(Х) unless q(X) ®r(X),

P(Z),

r(W)®s(W).

Первое правило означает, что г(Х) можно вывести, если истинно р(Х), и мы не верим, что истинно q(X). Если эти условия выполняются, мы выводим г(Х), а используя г(Х), можем вывести s(X). Впоследствии, если обнаружится, что q(X) истинно, г(Х) и s(X) должны быть отменены. Заметим, что оператор unless связан скорее с понятием веры, чем истинности. Впоследствии изменение значения аргумента с "вероятно, ложь либо неизвестно" на "точно либо вероятно истина" может вызвать отмену всех выводов, зависящих от этих предположений. Расширяя логику за счет рассуждений на основе предположений, которые позже могут быть отменены, мы вводим в механизм рассуждений элемент немонотонности.

Описанная выше схема рассуждений может быть использована также для описания правил умолчания [Reiter, 1980]. Замена р(Х) unless q(X) -» г(Х) на р(Х) unless ab р(Х) ® r{X), где ab p(X) - это abnormal p(X), означает, что при отсутствии аномалии, такой как птица с перебитым крылом, можно сделать вывод, что если X - птица, то X может летать.

Другой модальный оператор для расширения логических систем рассматривается в [McDermott и Doyle, 1980]. Авторы усиливают логику предикатов первого порядка модальным оператором М, который помещается перед предикатом и читается как "не противоречит". Введем следующие предикаты: good_student - быть хорошим студентом, study_hard - прилежно учиться, graduates - окончить ВУЗ. Тогда предложение

VX good_student{X) л М study_hard(X) ® graduates(X)

может быть прочитано следующим образом: для любого X, где X - хороший студент, если факт, что X прилежно учится, не противоречит остальной информации, то X закончит ВУЗ. Конечно, основной проблемой здесь является точное определение значения "не противоречит остальной информации".

Сначала заметим, что утверждение "не противоречит остальной информации" может оказаться неразрешимым. Причина в том, что модальный оператор формирует супермножество для уже неразрешимой системы (см. подраздел 2.2.2), и таким образом сам будет неразрешимым. Существуют два способа преодоления неразрешимости. Первый - использование метода доказательства от противного. В нашем примере можно попробовать доказать выражение not(study_hard(X)). Если не удастся доказать, что X не учится, то можно предположить, что X учится. Этот подход часто используется в PROLOG-подобной реализации логики предикатов. К сожалению, метод доказательства от противного может слишком ограничить область интерпретации.

Второй подход к проблеме непротиворечивости заключается в выполнении эвристического и ограниченного (по времени или по памяти) поиска истинности предиката (в нашем примере - study_hard{X)). Если поиск не приводит к доказательству ложности предиката, можно предположить, что он истинен. При этом следует понимать, что утверждение graduates и все основанные на нем заключения в дальнейшем могут быть отменены.

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

При реализации немонотонного рассуждения можно расширить логику с помощью оператора unless. Этот оператор поддерживает вывод на основе предположения о ложности аргумента. Допустим, имеется следующее множество выражений из логики предикатов.

р(Х) unless q(X) ->r(X),

P(Z),

r(W)->s(W).

Первое правило означает, что г(Х) можно вывести, если истинно р(Х), и мы не верим, что истинно q(X). Если эти условия выполняются, мы выводим г(Х), а используя г(Х), можем вывести s(X). Впоследствии, если обнаружится, что q(X) истинно, г(Х) и s(X) должны быть отменены. Заметим, что оператор unless связан скорее с понятием веры, чем истинности. Впоследствии изменение значения аргумента с "вероятно, ложь либо неизвестно" на "точно либо вероятно истина" может вызвать отмену всех выводов, зависящих от этих предположений. Расширяя логику за счет рассуждений на основе предположений, которые позже могут быть отменены, мы вводим в механизм рассуждений элемент немонотонности.

Описанная выше схема рассуждений может быть использована также для описания правил умолчания [Reiter, 1980]. Замена р(Х) unless q(X) -» г(Х) на р(Х) unless ab р(Х) -> r{X), где ab p(X) - это abnormal p(X), означает, что при отсутствии аномалии, такой как птица с перебитым крылом, можно сделать вывод, что если X - птица, то X может летать.

Другой модальный оператор для расширения логических систем рассматривается в [McDermott и Doyle, 1980]. Авторы усиливают логику предикатов первого порядка модальным оператором М, который помещается перед предикатом и читается как "не противоречит". Введем следующие предикаты: good_student - быть хорошим студентом, study_hard - прилежно учиться, graduates - окончить ВУЗ. Тогда предложение

VX good_student{X) л М study_hard(X) -> graduates(X)

может быть прочитано следующим образом: для любого X, где X - хороший студент, если факт, что X прилежно учится, не противоречит остальной информации, то X закончит ВУЗ. Конечно, основной проблемой здесь является точное определение значения "не противоречит остальной информации".

Сначала заметим, что утверждение "не противоречит остальной информации" может оказаться неразрешимым. Причина в том, что модальный оператор формирует супермножество для уже неразрешимой системы (см. подраздел 2.2.2), и таким образом сам будет неразрешимым. Существуют два способа преодоления неразрешимости. Первый - использование метода доказательства от противного. В нашем примере можно попробовать доказать выражение not(study_hard(X)). Если не удастся доказать, что X не учится, то можно предположить, что X учится. Этот подход часто используется в PROLOG-подобной реализации логики предикатов. К сожалению, метод доказательства от противного может слишком ограничить область интерпретации.

Второй подход к проблеме непротиворечивости заключается в выполнении эвристического и ограниченного (по времени или по памяти) поиска истинности предиката (в нашем примере - study_hard{X)). Если поиск не приводит к доказательству ложности предиката, можно предположить, что он истинен. При этом следует понимать, что утверждение graduates и все основанные на нем заключения в дальнейшем могут быть отменены.

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

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

"X good_student(X) ? М study_hard(X) ® graduates(X)

"Xparty_person (X) ? М not[study_hard{X)) ® not(graduates(X))

good_student(peter)

party_person(peter),

где party_person - любитель вечеринок. Из этого множества выражений можно вывести как заключение, что он окончит ВУЗ, так и заключение, что он его не окончит (если нет более точной информации о привычках Петра и не известно, прилежен ли он в учебе)!

Одним из методов рассуждения, позволяющих избежать таких противоречивых результатов, является отслеживание связывания переменных, используемых в модальном операторе "не противоречит". Таким образом, единожды связав значение peter с предикатом study_hard или not(study_hard), система должна предотвратить связывание этого значения с противоположным по смыслу предикатом. Другие системы немонотонной логики [Mcdermott и Doyle, 1980] являются еще более консервативными и предотвращают любые заключения из таких потенциально противоречивых множеств выражений. Возможна и другая аномалия.

"Yvery_smart(Y) ? М not(study_hard(Y)) ® not(study_hard(Y))

"X not(very_smart(X)) ? М not(study_hard(X)) ® not(study_hard{X)),

где very_smart - очень умный.

Из этих выражений можно вывести новое выражение.

"Z М not(study_hard(Z)) ® not(study_hard{Z)).

Последующие исследования семантики оператора "не противоречит" направлены на решение проблем с такими аномальными рассуждениями. Одним из дальнейших расширений является логика, обеспечивающая автоматическое образование понятий (autoepistemic logic) [Moore, 1985].

Другой немонотонной логической системой является логика умолчания (default logic), созданная Рейтером [Reiter, 1980]. Логика умолчания использует новое множество правил вывода вида

A{Z) ?: B(Z) ® C(Z),

которое читается так: если A(Z) доказуемо и если оно не противоречит знаниям, позволяющим предположить S(Z), можно вывести C(Z).

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

"Xgood_student(X) ?: study_hard(X) ® graduates(X) "Yparty(Y) ?: not(study_hard(Y)) ® not( graduates(Y)).

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

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

Логика умолчания позволяет использовать в качестве аксиомы для дальнейших рассуждений любую теорему, выведенную в рамках правдоподобного расширения. Но, чтобы установить, какое расширение должно использоваться при дальнейшем решении задачи, необходимо обеспечить управление процессом принятия решений. Логика умолчания ничего не говорит о выборе возможных правдоподобных расширений из базы знаний. Подробнее эти темы рассмотрены в работах [Reiter и Criscuolo, 1981] и [Touretzky, 1986].

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

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

8.1.2. Системы поддержки истинности

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

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

В процессе поиска желательно отступить назад прямо в точку пространства, где возникла проблема, и откорректировать решение в этом состоянии. Этот подход называется возвратом с учетом зависимостей. Рассмотрим пример немонотонного рассуждения. Нам необходимо прийти к заключению р, которое мы не можем вывести прямо. Однако существует правдоподобное предположение q, которое, будучи истинным, приводит к р. Таким образом, предполагая q истинным, мы выводим р. Продолжаем рассуждение и на основе истинности р выводим г us. Двигаясь еще дальше, уже без учета р, г или s выводим истинность г и и. И, наконец, доказываем, что прежнее предположение q является ложным. Что делать в данной ситуации?

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