Программирование на языке Пролог для искусственного интеллекта - Иван Братко

Резюме

• И/ИЛИ-граф — это формальный аппарат для представления задач. Такое представление является наиболее естественным и удобным для задач, которые разбиваются на независимые подзадачи. Примером могут служить игры.

• Вершины И/ИЛИ-графа бывают двух типов: И-вершины и ИЛИ-вершины.

• Конкретная задача определяется стартовой вершиной и целевым условием. Решение задачи представляется решающим деревом.

• Для моделирования оптимизационных задач в И/ИЛИ-граф можно ввести стоимости дуг и вершин.

• Процесс решения задачи, представленной И/ИЛИ-графом, включает в себя поиск в графе. Стратегия поиска в глубину предусматривает систематический просмотр графа и легко программируется. Однако эта стратегия может привести к неэффективности из-за комбинаторного взрыва.

• Для оценки трудности задач можно применить эвристики, а для управления поиском — принцип эвристического поиска с предпочтением. Эта стратегия более трудна в реализации.

• В данной главе были разработаны прологовские программы для поиска в глубину и поиска с предпочтением в И/ИЛИ-графах.

• Были введены следующие понятия: 

  И/ИЛИ-графы

  И-дуги, ИЛИ-дуги

  И-вершины, ИЛИ-вершины

  решающий путь, решающее дерево

  стоимость дуг и вершин

  эвристические оценки в И/ИЛИ-графах

  "возвращенные" оценки

  поиск в глубину в И/ИЛИ-графах

  поиск с предпочтением в И/ИЛИ-графах

И/ИЛИ-графы и связанные с ними алгоритмы поиска являются частью классических механизмов искусственного интеллекта для решения задач и реализации машинных игр. Ранним примером прикладной задачи, использующей эти методы, может служить программа символического интегрирования (Slagle 1963). И/ИЛИ-поиск используется в самой пролог-системе. Общее описание И/ИЛИ-графов и алгоритма можно найти в учебниках по искусственному интеллекту (Nilsson 1971; Nilsson 1980). Наша программа поиска с предпочтением — это один из вариантов алгоритма, известного под названием АО*. Формальные свойства АО*-алгоритма (включая его допустимость) изучались несколькими авторами. Подробный обзор полученных результатов можно найти в книге Pearl (1984).

Nilsson N.J. (1971). Problem-Solving Methods in Artificial Intelligence. McGraw-Hill.

Nilsson N.J. (1980). Principles of Artificial Intelligence. Tioga; also Springer-Verlag.

Pearl J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.

Slagle J.R. (1963). A heuristic program that solves symbolic integration problems in freshman calculus. In: Computers and Thought (E. Feigenbaum, J. Feldman, eds.). McGraw-Hill. 

Глава 14

Экспертные системы

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

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

14.1. Функции, выполняемые экспертной системой

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

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

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

• решение задач с использованием знаний о конкретной предметной области — возможно, при этом возникнет необходимость иметь дело с неопределенностью

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

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

14.2. Грубая структура экспертной системы

При разработке экспертной системы принято делить ее на три основных модуля, как показано на рис. 14.1:

(1) база знаний,

(2) машина логического вывода,

(3) интерфейс с пользователем.

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

Рис. 14.1. Структура экспертной системы.

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

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

(1) Выбрать формальный аппарат для представления знаний.

(2) Разработать механизм логического вывода, соответствующий этому формализму.

(3) Добавить средства взаимодействия с пользователем.