Реализация экспертной системы на языке

Реализация экспертной системы на языке Пролог Рассмотрим два варианта реализации ЗС, один из которых основан на продукционной модели представления знаний, а другой - на фреймовой модели. 1. Представление знаний правилами В качестве примера выберем задачу диагностики. Пусть, требуется установить причину неисправности электрической плиты, оборудованной нагревательным элементом, контрольной лампочкой и выключателем. Плита подключена к источнику напряжения с помощью электрического кабеля, который обеспечивает передачу тока. Набор правил "неисправность-причина" представим в виде графа (рисунок 1).
Простейший способ построения ЗС на Прологе - использование механизма поиска решений, заложенного в Пролог-системе. Для этого представим правила в виде предикатов языка Пролог: /* структура правила: причина:- неисправность */ нагреватель(неисправен):-лампа(светится), плита(холодная). /* г1 */ вьыключатель(не_включен):-тока(нет). /* г2 */ напряжения(нет):- тока(нет). /* гЗ */ тока(нет):- плита(холодная), лампа(не_светится). /* г4 */ лампа(неисправна):-лампа(не_светится), плита(горячая). /* г5 */ Рисунок 1 - Сеть вывода Определить причину поломки злектрической плити можно, указав обна-руженные неисправности й обеспечив проверку вьшолнимости каждой из возможных гипотез. Например: /* вариант 1 */ лампа(не_светится). /*фактьґ/ плита(холодная). причина(нагреватель(неисправен)). /*гипотезы*/ причина(выключатель(не_включен)). причина(напряжения(нет)). причина(лампа(неисправна)). найти(Х): - причина(Х), саІІ(Х). /*проверка гипотез*/ Для того чтобы узнать, какая из гипотез неисправности выполняется, необходимо задать вопрос: ? - найти(Х). Получив такой вопрос, Пролог-система выполнит необходимый обратный поиск с помощью встроенного механизма вывода и вернет ответ: X = выключатель(не_включен); X = напряжения(нет). Недостатком рассмотренного варианта программы является необходимость внесения обнаруженных неисправностей непосредственно в текст программы в виде фактов. Устранить указанный недостаток можно, запросив значения соответствующих неисправностей у пользователя в процессе выполнения программы: /* вариант 2 */ лампа(не_светится): - спроси('Ламла не светится ?'). плита(холодная): - спроси('Плита холодная ?'). лампа(светится): - спроси('Лампа светится ?'). плита(горячая): - спроси('Плита горячая ?'). спроси(Вопрос): - white(Вопрос), read('да'). В этом случае система будет задавать вопросы пользователю относительно неизвестных фактов. Так как ответы пользователя не запоминаются, то возможно повторение вопросов. Для запоминания ответов можно воспользоваться встроенным предикатом assert. Дальнейшие улучшение программы связано с упрощением формы записи правил. Запись правил в форме предикатов языка Пролог неудобна для пользователя. Представим правила в более естественной форме. Например: Правило 1: если лампа(светится) и плита(холодная) то нагреватель(неисправен). Для представления правил в такой форме определим операторы: определить_операторы: - ор(920, хfу, и), ор(950, хfу, то), ор(960, fx, если), ор(970, хfх,':'). ? - определить_операторы. С помощью введенных операторов правило 1 представляется структурой, изображенной на рисунке 2. Остальные правила рассматриваемого примера запишутся в виде: правило 2: если тока(нет) то выключатель(не_включен). правило 3: если тока(нет) то напряжения(нет). правило 4: если плита(холодная) и лампа(не_светится) то тока(нет). правило 5: если лампа(не_светится) и плита(горячая) то лампа(не_исправна). Рисунок 2 - Структура, соответствующая правилу В ходе вывода метаинтерпретатор должен установить причину неисправности, проверяя различные гипотезы. Представим возможные гипотезы в форме: Имя_факта: Факт. Тогда в соответствии с введенными правилами база данных возможных причин неисправности (гипотез) запишется в виде: h1 : причина(нагреватель(неисправен)). h2 : причина(выключатель(не_включен)). hЗ : причина(напряжения(нет)). h4: причина(лампа(неисправна)) Кроме этого, перечислим наблюдаемые признаки, на основе которых метаинтерпретатор должен установить причину неисправности. h1 : признак(лампа(светится)). h2 : признак(плита(холодная)). hЗ : признак(лампа(не_светится)). h4 : признак(плита(горячая)). Введение признаков позволит метаинтерпретатору задавать необходимый вопрос пользователю, если в базе данных нет значения соответствующего признака. Реализуем метаинтерпретатор в виде предиката найти(Н), где Н -возможная гипотеза, которую требуется подтвердить или опровергнуть. При этом возможны четыре случая: гипотеза Н подтверждается фактом, уже известным системе; гипотеза Н соответствует следствию одного из правил, тогда для подтверждения гипотезы необходимо доказать справедливость предпосылок правила; гипотеза Н, доказываемая на некотором шаге вывода, представляет собой конъюнкцию условий правила, т.е. Н1 и Н2, тогда необходимо доказать достижимость конъюнкции подцелей: найти(Н1) и найти(Н2); гипотеза Н сопоставима с одним из признаков, на основе которых устанавливаются причини неисправности, тогда необходимо задать соответствующий вопрос пользователю. Для того чтобы исключить повтор вопросов, ответы пользователя будем запоминать в базе данных в виде фактов сообщено(Факт, 'да\нет'). Запоминание соответствующих фактов в базе данных будем выполнять с помощью предиката assert. Гипотезы, относительно которых можно зада­вать вопросы, определяются с помощью предиката запрашиваемая(Н). Такие гипотезы сопоставимы с признаками. С учетом сказанного, метаинтерпретатор опишется следующей совокупностью правил языка Пролог: /* обратный вывод */ /* вариант 1 */ найти(Н): - Факт : Н. % случай 1 найти(Н): - Правило : если Н1 то Н, найти(Н1). % случай2 найти(Н1 и Н2): - найти(Н1), найти(Н2). % случай З найти(Н): - запрашиваемая(Н), % случай 4 сообщено(Н, да). % вопрос уже был найти(Н): - запрашиваемая(Н),% случай 4
not сообщено(Н, _), % вопроса не было спроси(Н). запрашиваемая(Н): - Факт : признак(Н). спроси(Н): - nl, write(Н), write ('?'), % вопрос read(О), ответ(Н, О).
ответ(Н, да): - assert(сообщено(Н, да)),! % добавить в БД ответ(Н, по): - assert(сообщено(Н, нет)),!, fail. ответ ответ(Н, _): - write ('правильный ответ: да, нет'), спроси(Н). % повторить вопрос Вызов метаинтерпретатора с целью проверки всех гипотез выполняется следующим образом: /* ЭС для решения задами диагностики */ инициализация: - retractall(сообщено( _,_)). диагностика(Н):- инициализация, Факт: причина(Н), найти(Н). Дальнейшее совершенствование разработанной программы связано с включением возможности ответов на вопросы типа "почему?" и "как?". Возможный сценарий диалога с ЗС при ответе на вопрос "почему?" приведен в таблице 7.1. Таблица 7.1 - Ответы на вопросы "почему?" Вопрос или ответ системы Ответ или вопрос пользователя лампа(светится)? плита(холодная)? пытаюсь доказать тока(нет) с помощью правила: правило 4 плита(холодная)? питаюсь доказать выключатель(не_включен) с помощью правила: правило 2 плита(холодная)? Моя гипотеза: выключатель(не_включен) плита(холодная)? Вы задаете слишком много вопросов Плита(холодная)? нет почему почему почему почему да Для того чтобы реализовать указанный диалог, необходимо переопределить предикат найти(Н). Введем в этот предикат второй аргумент, который будет представлять стек из имен доказываемых гипотез и имен правил. Тогда, анализируя содержимое стека, можно будет организовать соответствующий диалог. В момент вызова предиката найти в стек помещается имя доказываемой гипотезы. найти(Н, [Н]). Так как при обратном выводе в Пролог - системе осуществляется поиск в глубину, то в стеке фиксируется путь, состоящий из имен правил, обеспечивающих подтверждение основной гипотезы. Введение второго аргумента в предикат найти требует следующих переопределений: /* вариант2*/ найти(Н, Стек)-Факт: Н. найти(Н, Стек): - Правило: если Н1 то Н, найти(Н1, [Правило | Стек]). Стек) найти(Н1 и Н2, Стек): - найти(Н1, Стек), найти(Н2, Стек). найти(Н, Стек): запрашиваемая(Н), сообщено(Н, да). найти(Н, Стек): запрашиваемая(Н), not сообщено(Н, _ ), спроси(Н, Стек) В связи с необходимостью ввода вопроса "почему?" в предикаты спроси и ответ добавляется дополнительный аргумент: спроси(Н, Стек): - nl, write (Н), write ('?'), read (О), ответ(Н, О, Стек). ответ(Н, да, Стек): - assert (сообщено(Н, да)), !. ответ(Н, нет, Стек): - assert (сообщено(Н, нет)), !. ответ(Н, почему, [ ]): - !, nl, write ('Вы задаете слишком много вопросов'), спроси(Н, []). ответ(Н, почему, [Н]): - !, nl, write ('моя гипотеза :'), write (Н), спроси(Н, [ ]). ответ(Н, почему, [Правило | Стек]): - !, Правило : если Н1 то Н, nl, write('пытаюсь доказать'), write (Н), nl, write('с помощью правила : '), write (Правило), спроси(Н, Стек). ответ(Н, _ , Стек): - write('правильный ответ : да, нет, почему'), спроси(Н, Стек). Формирование ответа на вопрос "как?" требует дополнительных изменений предиката найти. При ответе на вопрос "как?" система должна, по сути, построить дерево вывода. Например, если пользователя интересует, как была подтверждена гипотеза выключатель(не_включен), то система должна обеспечить отображение дерева вывода, изображенного на рисунке 3. Такое дерево можно представить в форме вложенных правил, условия и заключения которых конкретизированы: правило 2 : если правило 4 : если сообщено(плита(холодная)) и сообщено (лампа(не_светится)) то тока(нет) то выключатель(не_включен). Рисунок 3 - Дерево вывода Пусть Д обозначает дерево вывода целевого утверждения Н. Тогда построение дерева вывода выполним на основе следующих правил: если сообщено(Н), то Д = сообщено(Н); если имеется Факт : Н, то Д = Факт : Н; если имеется правило Правило : если Н1 то Н, и если Д1 - дерево вывода для Н1, то Д = Правило : если Д1 то Н; если доказывается гипотеза Н = Н1 и Н2, то дерево вывода Д = Дерево1 и Дерево2, где Дерево1 - дерево вывода гипотезы Н1, а Дерево2 - гипотезы Н2. Переопределим предикат найти, добавив третий аргумент, представляющий дерево вывода: найти(Н, Стек, Дерево). Воспользовавшись введенными выше правилами построения дерева вывода, получим: /* правило 1 */ найти(Н, Стек, сообщено(Н)):- сообщено(Н, да). найти(Н, Стек, сообщено(Н)):- запрашиваемая(Н), not сообщено(Н, _), спроси(Н, Стек). /* правило 2 */ найти(Н, Стек, Факт : Н):- Факт : Н. /* правило З */ найти(Н, Стек, Правило : если Д1 то Н):- Правило : если Н1 то Н, найти [Правило\Стек,], Д1 /* правило4 */ найти (Н1 й Н2, Стек, Дерево 1 и Дерево 2):- найти (Н1, Стек, Дерево 1), найти(Н2, Стек, Дерево2). Теперь можно будет выяснять у системы, как было получено то или иное заключение. Чтобы реализовать эту возможность, введем предикат как(Н, Дерево), где Н - интересующее пользователя заключение, а Дерево - дерево вывода заключения, формируемое предикатом найти. Определяя предикат как(Н, Дерево), учтем два случая: % Дерево можно построить как(Н, Дерево):- как1(Н, Дерево),!. % Дерево нельзя построить как(Н, _}:- nl, write(Н), write ( 'не доказано'). Здесь предикат как1(Н, Дерево) определяется с помощью правил, аналогичных правилам, используемых в определении предиката найти: как1(Н, сообщено(Н)):-!, nl, write (Н), write ('было введено'). /* правило1 */ как1(Н, Факт : Н):-!, nl, write (Н), write ( 'является фактом'), write (Факт). /* правило2 */ как1(Н, Правило : если _ то Н):- !, nl, write (Н), write ( 'было доказано с помощью'), Правило : если Н1 то Н, отобрази_правило(Правило : если Н1 то Н). /*правилоЗ */
как1(Н, Правило : если Дерево ):-как (Н, Дерево). /*правило4 */ как1(Н, Дерево1 и Дерево2 то _):- как ( Н, Дерево1); как ( Н, Дерево2). /*правило5 */ отобрази_правило(Правило : если Н1 то Н):— nl, write (Правило), write (':'), nl, write ('если'), write (Н1), nl, write ('то'), write (Н)
Вызов предиката как(Н.Дерево) будем выполнять из предиката объясни(Дерево), после вызова предиката найти(Н, [Н], Дерево): /* ЗС для решения задач диагностики*/ инициализация:- retractall(сообщено(_,_)). диагностика:- инициализация, Факт : причина(Н), найти(Н, [Н], Дерево), nl, nl, write ( 'решение:'), write (Н), объясни(Дерево), возврат. Здесь предикат объясни(Дерево) определяется так: объясни(Дерево):- nl, nl, write ( 'объяснить ? [цель/п]:'), read(Н), (Н\=no, І, как(Н, Дерево), объясни(Дерево)),!. Предикат возврат обеспечивает доказательство альтернативных гипотез: возврат:- nl, nl, write (' следующее решение ?:'), read(no). Процесс диагностики неисправностей начинается с вызова основного предиката диагностика. Ниже приведен возможный диалог с системой: ?-диагностика. лампа(светится)? нет. плита(холодная)? да. лампа(не_светится)? да. решение: выключатель(не_включен) объяснить?[цель/п]: выключатель(не_включен). выключатель(не_включен) было доказано с помощью правило 2: если тока(нет) то выключатель(не_включен) объяснить?[цель/п]: тока(нет). тока(нет) было доказано с помощью правило 4: если плита(холодная) й лампа(не_светится) то тока(нет). объяснить?[цель/п]: плита(холодная). плита(холодная) б ыло сообщено объяснить?[цель/п]: нет. решение: напряжения(нет) объяснить?[цель/п]: нет. плита(горячая)? почему. пытаюсь доказать лампа(не_исправна) с помощью правила: правило 5 плита(горячая)? нет. нет. Здесь ответы пользователя набраны курсивом. Рассмотренная ЭС может работать. только с такими утверждениями, которые либо истинны, либо ложны. Во многих случаях требуется учитывать неопределенность фактов и правил. Для работы в условиях неопределенности с правилами и фактами можно связать соответствующие коэффициенты уверенности. Например, Правило1: если лампа(светится) и плита(холодная) то нагреватель(неисправен) cf 0.8. Здесь cf – инфиксный оператор, посредством которого задастся коэффициент уверенности. Оператор сf определяется с помощью директивы: :- ор(940, xfx, cf). 2. Представление знаний фреймами В ЭС, основанных на правилах, знания сосредоточены исключительно в базе правил, а база данных представляет собой пассивное множество фактов. Фреймовая модель представления знаний обеспечивает лучшую структурированность фактов, более экономное использование памяти, а также активизацию фактов. Характерными отличиями фреймовой модели представления знаний являются: наследование по иерархии фреймов, наличие присоединенных процедур, наличие значений по умолчанию и др. Рассмотрим простейшие возможности представления экспертных знаний совокупностью фреймов. При этом фрейм будем представлять в виде объекта с множеством атрибутов (слотов): объект --атрибут1 : значение1 --атрибут2 : значение2 --… --атрибут_п : змачение_п. Если рассматривать знаки "--" и ":" как операторы языка Пролог (ор(910, хfх,:), ор(910, хfу, --)), то такому описанию объекта будет соответствовать структура, изображенная на рисунке 4. Данная структура представляет терм языка Пролог (n = 3): объект - - ((атр1 : з1) - - ((атр2 : з2) - - (атр3 : з3))).
Рисунок 4 - Структура, соответствующая списку свойств Доступ к значениям атрибутов объекта будем осуществлять с помощью предиката объект(О,А,3), где О - переменная, обозначающая объект; А -соответствующий атрибут объекта; 3 - значение атрибута. Предикат объект(О,А,3) определяется рекурсивно:
объект(О, А, 3):- О - - Атрибуты, поиск(А, 3, Атрибуты),!. поиск(А, З, А : 3). поиск(А, З, А : 3 — Атрибуты1). % утверждение 2 поиск(А, З, А1 : 31 - - Атрибуты1):- % утверждение З поиск(А, 3, Атрибуты1). Здесь первое определение обеспечивает отделение имени объекта от его атрибутов с помощью оператора О — Атрибуты. Переменная Атрибуты после выполнения данного оператора будет представлять правое поддерево древовидной структуры, изображенной на рисунке 4.