Экспертные системы с представлением знаний на основе логики предикатов

К логическим моделям относятся:

• логика высказываний;
• логика предикатов первого порядка;
• логика Хорна в языке Prolog и ему подобных системах;
• логика предикатов высших порядков;
• трехзначная логика;
• логика возможных миров;
• модальные логики;
• теория нечетких множеств;
• нечеткая логика;
• лингвинистические переменные.

Язык логического программирования PROLOG

 

Пролог (Prolog) — язык логического программирования, основанный на логике дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.

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

Язык, предназначенный  для формализации знаний, должен иметь  собственный синтаксис и располагать  средствами для выражения связей между объектами реального мира. Указанному требованию удовлетворяет  язык исчисления предикатов или логики первого порядка. Логика предикатов рассматривает отношения между  утверждениями и объектами.

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

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

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

• индексированную базу данных фраз, которые можно использовать для представления правил, процедур или данных;
• универсальный механизм сопоставления, который позволяет выполнять сопоставление данных и шаблонов, включающих переменные, и возвращать подстановку, которая может обеспечить их совпадение;
• стратегию управления (поиск в глубину — depth-first search), основанную на правилах нисходящего поиска (фразы, которые размещены в базе данных ближе к "голове", обрабатываются первыми) и вычислении слева направо (подцели обрабатываются в том порядке, в котором они перечислены в списке).

 

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

Структура программы  на Prolog

 

Программа на языке PROLOG включает следующие основные разделы:

• описание имен и структур объектов (domains);
• описание предикатов – названий отношений, существующих между объектами (predicates);
• раздел целевых утверждений (goal), который может отсутствовать; в этом случае программа будет запрашивать целевое утверждение при запуске;
• описание фактов и правил, описывающих отношения (clauses).
• Имена объектов (констант) в PROLOG пишутся с маленькой буквы, а переменных – с большой.

 

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

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

Запросы к Prolog программе

 

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

Простые запросы, не содержащие переменных, называют да-нет-вопросами. Они допускают лишь два возможных ответа: “Yes” или “No”. В случае ответа “Yes” говорят, что запрос завершился успехом, цель достигнута.

Как правило, в системе, предназначенной для  выполнения операторов PROLOG, применяется  интерпретатор, хотя в некоторых  системах может вырабатываться компилированный код. Общая структура системы PROLOG показана на рисунке 2. Пользователь взаимодействует с системой PROLOG, вводя запросы в форме предикатов и получая ответы.  Предикативная база данных содержит предикаты, представленные в виде правил и фактов, которые были в нее введены и в результате сформировали базу знаний. Интерпретатор предпринимает попытки определить, следует ли предикат запроса, введенный пользователем, из базы данных. Если запрос сформулирован как факт и этот факт находится в базе данных, интерпретатор возвращает ответ yes, а если этот факт в базе данных отсутствует — возвращает ответ no.

 

 

Рисунок 2. Общая организация системы PROLOG

 

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

 

Рисунок 3. Поиск в глубину и поиск  в ширину применительно к дереву произвольной формы

 

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

Когда голова предиката согласована, система  PROLOG предпринимает попытку согласовать  тело правила , что приводит к созданию подцели. Затем система  PROLOG  осуществляет попытку согласовать эту подцель с другими выражениями и в конечном итоге согласует ее с фактом. На этомв се цели, подлежащие согласованию, исчерпываются, и система PROLOG отвечает “yes”, если первоначальный запрос является истинным.

Базы данных и  знаний на прологе

 

Факты, описанные в разделе clauses, можно рассматривать, как статическую  базу данных (БД). Эти факты являются частью кода программы и не могут  быть оперативно изменены. Для создания динамической базы данных в PROLOG предусмотрен специальный раздел database. Предикаты в этом разделе могут иметь такую же форму представления, что и в статической части PROLOG -программы, но должны иметь другое имя.

Главное достоинство БД на PROLOG, как и любой другой БД, заключается в возможности быстрого выборочного доступа к информации.

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

Пример ЭС, базирующейся на логике предикатов

 

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

 

Рисунок 4. Древовидная  структура базы знаний для выбора породы собак

 

Для построения БЗ на основе предложений-фактов Пролога зададим три предиката:

• - topic -устанавливающий классификацию верхнего уровня дерева структуры БЗ;
• - rule - определяющий связи объектов с древовидной структурой и набором характеристик собак;
• - cond - определяющий характеристики пород для данной ЭС.

 Текст  основного модуля программы ЭС  приводится в Приложении 1.

Предикат topic определяет тип породы (короткошерстная  или длинношерстная). Предикат rule указывает  название породы, порядковый номер  породы (правила) и список номеров  характеристик пород. В предикате cond определяются сами характеристики. Предикатом, определяющим цель программы, является предикат do_exspert_ job, открывающий  окно ЭС и задающий меню режимов  работы ("начало консультаций"/"выход"). После выбора режима консультации пользователь может запросить классификацию, используемую в ЭС, или начать процесс выбора. Последовательность ответов пользователя фиксируется в предикатах базы данных yes и no. Правила erase и clear выполняют очистку БД. Поиск данных по образцу, за данному пользователем, осуществляется при помощи правила check. Организация диалога при помощи меню исключает возможные ошибки пользователя. Результатом диалога - консультации будет либо сообщение о выборе породы собаки, либо ответ о невозможности выбора при заданных пользователем требованиях.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

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

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

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

 

 

 

 

 

 

 

 

Список  литературы

 

 

1. Д. Джарратано. Экспертные системы: принципы разработки и программирование : Д. Джарратано, Г. Райли. – 4-е издание. – М.: ООО "И.Д. Вильямс", 2007.
2. П. Джексон. Введение в экспертные системы [Текст]: П. Джексон - М.: ООО "И.Д. Вильямс", 2001.
3. А.Н. Адаменко, А.М. Кучуков. Логическое программирование и Prolog СПб.: БХВ—Петербург, 2003.
4. И. Братко. Алгоритмы искусственного интеллекта на языке PROLOG. М.: «Вильямс», 2004.
5. Экспертная система – Википедия // Режим доступа: http://ru.wikipedia.org/wiki/Экспертные_системы
6. Представление знаний – Википедия // Режим доступа: http://ru.wikipedia.org/wiki/Представление_знаний
7. Инженерия знаний – Википедия // Режим доступа: http://ru.wikipedia.org/wiki/Инженерия_знаний

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1

/* Программа EXPERT2 */

#M

include "menu2.pro"

domains

CONDITIONS = BNO *

HISTORY = RNO *

RNO, BNO, FNO = INTEGER

CATEGORY = SYMBOL

database

/* Предикаты базы данных */

rule(RNO, string, CATEGORY, CONDITIONS)

cond(BNO, string)

yes(BNO)

 no(BNO)

topic(string)

predicates

/* Предикаты системы пользовательского  интерфейса */

 do_expert_job

show_menu

do_consulting

process(integer)

trangoal(integer,CATEGORY)

info(CATEGORY)

goes(CATEGORY)

listopt

erase

 clear

eval_reply(char)

/* Предикаты механизма  вывода */

 go(HISTORY, CATEGORY)

check(RNO, HISTORY, CONDITIONS)

notest(BNO)

inpo(HISTORY, RNO, BNO, STRING)

do_answer(HISTORY, RNO, STRING, BNO, INTEGER)

 goal

do_expert_job.

clauses

/*------- Предикаты системы  пользовательского интерфейса --------*/

 do_expert_job :-

makewindow(1,$0A,$0B," СОБАКА - ДРУГ ЧЕЛОВЕКА ",

0,0,25,80),

show_menu,

nl,write(" Нажмите клавишу пробела ... "),

readchar(_),

exit.

show_menu :-

menu(10,20,$13,$13,

 [" Консультация", " Выход из системы "],

"", 1,Choice),

 process (Choice).

process(1) :-

consult("dogs.dba"),

do_consulting.

process(2) :-

removewindow,

exit.

do_consulting :-

goes(Mygoal),

go([],Mygoal),

 !.

do_consulting :-

nl, write(" Извините, я не  могу Вам помочь."),