Вступление
Как то мне посчастливилось выбирать тему дипломной работы по специальности программная инженерия, и я выбрал написание экспертной системы, причем именно на языке Пролог. Хоть в промышленном программировании он почти не используется, он интересен в теоретическом плане позволяет самым быстрым способом прикоснуться к интеллектуальным системам(ИС). Также сам язык интересен в спортивном плане, так как заставляет мыслить в непривычной манере, отличной от процедурного программирования и ООП, что является хорошой тренировкой для мозгов.
Использовалась реализация Prolog — Visual Prolog, с встроенными библиотеками GUI. Но если
вы хотите написать GUI на Qt/C++, то в документации есть инструкция, как импортировать программу в DLL, и скомпилировать ее вместе с C/C++ проектом. Отсюда следует, что совместить можно и с другими языками.
Вообще когда я работал над этим проектом, я не нашел примеров достаточно не примитивных, но в то же время и не настолько больших, как навороченные научные примеры. Поэтому данная статья может оказаться очень хорошей помощью начинающим, и людям желающим написать хотя бы немного похожее на ИС.
Описание назначения системы: есть набор параметров, которым должен соответствовать кардиосигнал(ЭКГ), по которым можно определить заболевание. Человек отвечает на вопросы системы(в режиме диалога), и система, выступая в качестве эксперта по кардиозаболеваниям, делает выводы о потенциальном заболевании человека.
Т.е. данный код можно рассматривать как каркас(prolog-фреймворк), для создания экспертных систем из других областей, просто подставив свои правила, свои данные. Правила, по которым осуществляется вставка будут описаны ниже.
Исчисление предикатов первого порядка и язык Пролог
Язык Пролог реализует логическую парадигму программирования, идея которой – использование вычислительной техники для логического вывода из декларативного описания предметной области. Это отличает его от процедурных языков программирования, которые описывают четко определенные последовательные действия. Поэтому процедурные языки не подходят для написания ЭС, и если и используются, то только как вспомогательные модули. Также отличительной особенностью языка Пролог, является использование для описания программы подмножества языка логики первого порядка, на котором удобно и проще чем к другим, переходит с естественного языка описания мира человеком. При создании ЭС это является одной из важных проблем – как перевести знания предметной области на ограниченный формальный язык, сохранив при этом информативность вкладываемую человеком. Также существует простая возможность перевести знания обратно из формального к естественной форме, вследствие интуитивной понятности и простоты, по сравнению с логикой второго порядка или другими математическими исчислениями.
Языковые конструкции Пролога можно представить в виде импликаций вида:
A1, A2, …, An <= B1, B2, …,Bm (n>=0, m>=0) (1)
где Ai и Bi – атомарные формулы Fi(t1, t2, …, tk) или отрицание Fi(t1, t2, …, tk), где tk – термы(индивидная константа, переменная или результат применения функции)
В Прологе все отношения записываются как факты и правила, где n=1 в формуле (1), для повышения эффективности логического вывода. Правилам соответствует формула, называемая формулой Хорна:
A<=B1, B2, …, Bm ,где m>0 (2)
Фактам соответствует формула (2) при m=0:
A<= (3)
Формулой, которую нужно доказать в процессе механизма вывода, является формула (1) при n=0, m>0, называется целью или запросом:
<= B1, B2, …Bm (4)
Из этих языковых конструкций состоит вся программа на Прологе.
Например, следующее знание, в виде предложения на естественном языке – “Сын Ани любит Машу” можно записать в виде факта:
любит(сын(аня), маша)а предложение “Аня любит всех, кого любит Оля” в виде:
(любит(аня,X)<=любит(оля,X))Или рассуждение “Каждый человек смертен. Конфуций — человек”:
(человек(конфуций)& (смертен(X)<=человек(X)) <= смертен(конфуций)Также Пролог предоставляет средства для определения рекурсивных структур данных, таких как деревья и списки, что приносит дополнительные возможности для удобного описания соответствующих знаний.
Таким образом, видно, что Пролог предоставляет гибкий, простой и интуитивно понятный язык для описания знаний.
Но дальше встает вопрос о выборе реализации этого языка, и было решено целесообразным разрабатывать ЭС на расширении языка Пролог – Visual Prolog.
Visual Prolog
Visual Prolog – диалект языка Пролог с объектно-ориентированным расширением вместе с интегрированной средой разработки. Эта среда обеспечивает поддержку создания графических интерфейсов и многих других библиотек. Язык Пролог довольно популярный для создания ЭС, с простым синтаксисом, схожим по смыслу с отношениями предметной области и фактами. Вообще сам интерпретатор языка Пролог можно рассматривать как ЭС в терминах логики предикатов первого порядка, в которой пользователь задает вопрос в виде цели, истинность которой нужно доказать. Это декларативный язык, в нем описывается, что нужно получить, вместо последовательного алгоритма, прекрасно подходит для описания знаний небольшой ЭС. По сравнению с альтернативными средами AMZI Prolog и SWI-Prolog, предоставляет очень эффективный интерфейс взаимодействия с другими языками как с помощью компоновки объектных файлов или с помощью динамической загрузки DLL-библиотек, как других языков, так и как самостоятельный DLL-модуль. Также Visual Prolog хорошо документирована, имеет множество примеров. Также существует мнение, что выбор языка реализации, способа представления знаний и метода формирования рассуждений вторичны, по сравнению со знаниями эксперта, и влияют лишь на механизм их успешного использования. Тем не менее, наличие литературы с использованием пролога как средства создания ЭС говорит о пригодности его использования, по крайней мере в небольших системах.
Проектирование ЭС
В литературе принято разделять ЭС на несколько основных, мало зависящих друг от друга компонентов: базу знаний, механизм вывода и интерфейс с пользователем.
Существует 2 типа организации экспертных систем: на правилах и на фактах.
Знания ЭС на правилах записывается в виде продукционных правил. Левая часть каждого правила содержит какаю-то альтернативу решения вопроса, а правые части (посылки) специфицируются другими правилами. Единственное исключение – когда правило проверяет наличие в базе данных информации, например ответа на вопрос. Алгоритм работы механизма вывода сводится к сопоставлению, затем при множестве вариантов выбирается нужный в соответствии с заложенным принципом разрешения конфликта и в конце применяется выбранное правило и все начинается сначала. Плюсы у такой организации в том, что очень легко добавлять правила в систему без влияния на другие правила, а дополнять и модифицировать легко, так как программисту нужно просто вставить нужное правило в подходящий блок правил. Также такая организация имеет ограничения, а именно придется организовывать неестественный алгоритм сохранения трассировки или использовать для нее переменную в правилах, но это нарушит удобство модификации правил, так как для каждого предиката правила придется организовывать сохранения трассировки. Также это нарушит читабельность программы и возможность модификации вообще механизма вывода, так как вместе с информацией о правилах будет содержаться учет обхода посредством действия механизма вывода. Дополнительно Пролог не позволяет сохранять правила в файл базы данных и читать правила из базы данных, что не позволило бы обновлять базу знаний во время работы программы. Листинг 1 приводит пример такой организации базы знаний.
Листинг 1
diag("SIRS"):-
diag2("SIRS").
diag("Sepsis"):-
diag("SIRS"),
have("Sepsis character").
diag("Hard sepsis"):-
diag("Sepsis"),
have("Hard sepsis character").
diag("Shock sepsis"):-
diag("Hard sepsis"),
have("Shock sepsis character").
diag("MOF"):-
diag("Hard sepsis"),
have("MOF sepsis character").
diag("MOF"):-
diag("Shock sepsis"),
have("MOF sepsis character").Как видно из листинга 1, механизм вывода полностью должен управляться встроенным в Пролог стандартным механизмом вывода.
ЭС организованные на логике (на фактах) более гибкие, так как в отличие от прямой связи правил, они организованы на ссылочной (косвенной) методике описания связей правил. Связи записываются в виде термов, например номеров правил, а не вложенных друг друга правил. Такая запись больше соответствует строгой записи в виде предложений логики предикатов, что и делает механизм вывода таких правил более гибким. В отличие от организации на правилах, поиск решения Пролога менее зависим от процесса логического вывода очередного правила, так как появляется возможность помимо вывода выполнять еще какие-то действия, например, пройтись по альтернативному дереву решений или вовсе изменить ход вывода и вернуться к исходному положению сохранив все данные об этом.
Также как и в организации на правилах здесь действует цикл: сопоставление – разрешение конфликта — переход к очередному правилу, но поскольку механизм вывода управляется опосредовано удобно в процессе выводить информацию о поиске решения и изменять этот формат без изменения базы знаний. Главное преимущество организации на логике в том, что можно сделать так, чтобы переменные, которые сопоставляются в процессе вывода, автоматически доступны в механизме вывода, и их можно было выводить вместе цепочкой последних правил, которые выведены к текущей цели. Но для этого нужно дополнительно предусмотреть механизм привидения типов для разных типов правил. Также база знаний хранится в виде фактов, поэтому ее можно сохранять или читать с файла на носителе. Систему на фактах тяжелее модифицировать и отлаживать чем на правилах, так как механизм вывода управляется значениями переменных и термами, например в виде номера правила, что вносит дополнительные возможности для ошибок.
Также в механизме вывода становится больше влияющих на этот процесс переменных, порой рекурсивного типа и довольно взаимосвязанных, что усложняет разработку, и отлов ошибок, но это цена за гибкость которую она предоставляет. Также система на фактах работает эффективнее и быстрее чем на правилах, что особенно важно для громоздких ЭС реального времени, или даже для распределенных ЭС реального времени.
Большая ЭС для медицинской диагностики в случае поступления больных в критическом состоянии, особенно если используется одновременно множеством врачей, тоже должна укладываться в строгие временные рамки.
Еще систему на фактах тяжелее тестировать из-за ее зависимости от фактов, так как в системе на правилах просто ошибка отразилась бы на механизме вывода, и это сразу бы стало видно, но на фактах скорее всего продолжит дальше работать.
В итоге, так как разрабатываемая система должна обладать информативностью к пользователю, а именно должен выводиться в процессе логического вывода обоснованный ответ на вопрос — почему системе понадобилась затребованная информация, чтобы пользователь знал — на какой стадии поиска решений он находится, что нельзя обеспечить без сохранения трассировки поиска. Также в конце, после ответа на вопрос, пользователь должен иметь возможность увидеть дерево доказательства для найденных решений. Учитывая все параметры системы, самым рациональным мне показалась система на правилах, так как ее можно сохранять на диск и ее механизм вывода легче будет организовать. Также знания по диагностике сердечнососудистых заболеваний, оказалось довольно трудно формализовать из-за их семантической взаимосвязанности, особенно в тех местах, где смысл заключений правил подразумевал учет дополнительной информации, для каждого свой. Поэтому при выборе механизма обмена разнотипным данными между предикатами был отдан расчет на логический способ организации.
Также существует 2 типа – логического вывода: обратный и прямой логический вывод. В сложных системах медицинских консультаций еще применяют комбинацию этих типов: какое-то множество знаний выводится одним типом, а на его основе уже применяется другой.
Прямой вывод заключается в нахождении следствия на основе множества фактов и последующего вывода из новых следствий других заключений. Он эффективен когда существует множество связанных на разных уровнях гипотез, которые нужно доказать или когда множество аксиом для вывода много больше гипотез.
Обратный вывод устроен наоборот, сначала выбирается гипотеза, которую нужно доказать, а затем происходит попытка доказать посылку этой гипотезы, пока не будет найдена очередная посылка в качестве аксиомы.
В ЭС рассуждения на правилах, реализованы методом обратного логического вывода, который использует Пролог. Был выбран такой вариант, так как в отличие от прямого вывода, он эффективнее работает при данных знаниях, поскольку количество целевых вершин много больше фактов и нет конкурирующих гипотез (они независимы).
Реализация
На языке Пролог правила реализованы в виде предиката rule. Каждое правило имеет свой номер и название, которое является гипотезой (заключением), которую нужно доказать. Условию правила соответствует неявное утверждение, которое полностью определяет истинность гипотезы.
Условие правила:
Colclusion(K)=C1(K) and (C2(K) or C3(K)) and C4(K)C1(K) = Истинны все заключения правил с номерами, записанных в первом списке для K-ого правила
С2(K) = Истинно хотя бы одно правило из второго списка для K-ого правила
С3(K) = Истинно ровно N(K) заключений правил из второго списка для K-ого правила
C4(K) = Предикат для K-ого правила(предикат doc(K)), который описывает пользователь.
Если любой список пуст, значит соответствующее утверждение истинно.
При этом в предикат для C4 можно вписать любые другие предикаты, но при этом они не должны нарушать логический смысл заключения. Для поддержки отрицания, какого-то существующего заключения в базе знаний можно вписать сюда и его.
Механизм вывода обеспечивает применение правил в нужной последовательности и сохраняет трассировку.
Главные принцип вывода – чтобы доказать истинность заключения, доказать последовательно все его заключения в первом списке, затем доказать заключения второго списка и в конце проверить истинность предиката соответствующего номеру текущего правила. Для проверки второго списка, в случае нахождения хотя бы одного истинного правила, будут проверены все дальше идущие правила до конца списка.
Описание предикатов
В общем, принцип кодирования знаний реализован на Прологе с помощью двух предикатов в следующем виде:
rule(K,”Текст заключения — имя правила”, Id, List1, List2, N)
doc(K)
K — номер правила
Id — Идентификатор данных для данного правила
List1 – первый список номеров правил
List2 – второй список номеров правил
N – число истинных заключений
Причем rule всегда записывается как факт, без переменных, и его истинность, как было сказано, определяет помимо списков, соответствующий предикат doc.
Вот несколько примеров записи знаний:
rule(93,«TASH — TASH-score 43% »,tashSc10,[47],[],0)
rule(33,«TASH – Избыток оснований – есть сумма баллов»,none,[],[29,30,31,32],1).
В предикате doc, могут использоваться любые другие предикаты, что дает возможность сопоставить тексту утверждения правила множество любых ситуаций, которые можно описать посредством Пролога.
Таким образов все знания записываются с помощью этих двух предикатов.
В предикатах doc в основном вызываются функции пользовательского интерфейса, так как некоторые правила по смыслу неразрывно связаны с ответом пользователя или в них проводятся проверки на допустимые значения.
Например, предикаты doc для правил, истинность которых зависит от интервала, в котором находится суммарный балл, делают соответствующие проверки.
Предикат doc для диагностирования заболеваний сепсиса использует дополнительный предикат docc, позволяющий не задавать пользователю лишних вопросов. Например, если признак требует наличия хотя бы двух признаков, при отрицательном ответе уже на два признака система не должна задавать еще вопросы, так как очевидно что признак не может быть истинным. Для этого в предикате docc предусмотрена проверка на наличие в базе данных более двух отрицательных ответов. Также нет смысла задавать третий вопрос, если уже есть ответ на два вопроса, достаточных для установления истинности результирующего признака.
Предикат kolNeg(Количество) ищет количество отрицательных ответов в базе данных для данной группы признаков. Для этого он сначала ищет всевозможные признаки данной группы признаков, чтобы не перепутать их с другими группами, а затем считает их из множества в базе данных с помощью предиката kol_neg_list_in_db, работающего со списком признаков данной группы.
Примеры кода
Проект большой, поэтому приведу наиболее важные отрывки.
Листинг 2 — Список правил
rule(11,"Sepsises - SIRS призн. 1: t>38C или t<36С",sirsPr1,[],[],0).
rule(12,"Sepsises - частота сердечных сокращений>90",sirsPr2,[],[],0).
rule(13,"Sepsises - частота дыхания>20 или PaCO2<32mmHg",sirsPr3,[],[],0).Листинг 3 — Список фактов
fact1(sirsPr1,"SIRS","SIRS призн. 1: t>38C или t<36С").
fact1(sirsPr2,"SIRS","частота сердечных сокращений>90").
fact1(sirsPr3,"SIRS","частота дыхания>20 или PaCO2<32mmHg").
fact1(sirsPr4,"SIRS","кол-во лейкоцитов>12.000/mm>3, <4.000/mm>3 или >10% band").— Список логических следствий
tash_score(1,tashSc1,0,8,"Вероятность прогноза <5%").
tash_score(2,tashSc2,9,9,"Вероятность прогноза 6%").
tash_score(3,tashSc3,10,10,"Вероятность прогноза 8%").Листинг 4 — Машина вывода
sizeList([],0):-!.
sizeList([_|T],Size):-
sizeList(T,SizeTail),
Size=SizeTail+1.
append_der_list([],List,List).
append_der_list([H|L1],List2,[H|L3]):-
append_der_list(L1,List2,L3).
any2(NeedSize,NeedSize,_,[],[],_):-!.
any2(_,_,[],[],[],_):-!.
any2(NeedSize,Size,[H|T1],[H|T2],[FirstDer|OtherDer],Why):-
Nomer=[H],
go(Nomer,UnderFirstDer,Why),
rule(H,Text,_,_,_,_),
FirstDer=tree(Text,unmarked,UnderFirstDer,0),%der(H,UnderFirstDer),
Size1=Size+1,!,
any2(NeedSize,Size1,T1,T2,OtherDer,Why).
any2(NeedSize,Size,[_|T1],List,OrDer,Why):-
!,any2(NeedSize,Size,T1,List,OrDer,Why).
go([],[],_):-!.
go([H|T],[FirstDer|OtherDer],Why):-
rule(H,Name,_,ListAnd,ListOr,KolOr),
NewWhy=[Name|Why],
go(ListAnd,UnderFirstDer,NewWhy),
goOr(ListOr,KolOr,_,OrDer,NewWhy),
append_der_list(UnderFirstDer,OrDer,TwoDers),
FirstDer=tree(Name,unmarked,TwoDers,0),
asserta(why_trace(NewWhy)),
doc(H,NewWhy),
go(T,OtherDer,Why).
goOr([],_,[],[],_):-!.
goOr(ListOr,KolOr,ListYes,OrDer,Why):-
KolOr<>0,
any2(KolOr,0,ListOr,ListYes,OrDer,Why),
sizeList(ListYes,KolOr).
goOr(ListOr,0,ListYes,OrDer,Why):-
any2(100000,0,ListOr,ListYes,OrDer,Why),
sizeList(ListYes,KolListYes),
KolListYes>0.Листинг 5 — вывод конечных следствий
tashQuestion(Id):-
fact2(Id,_,Prisnak,_),
pos(Prisnak),!.
tashQuestion(Id):-
fact2(Id,_,Prisnak,_),
neg(Prisnak),fail,!.
tashQuestion(Id):-
fact2(Id,_,Prisnak,Ball),
not(neg(Prisnak)),
not(pos(Prisnak)),
dialog_ynw(Prisnak,Ans),
tash_in_data_base(Ans,Prisnak,Ball),!.
tash_in_data_base("y",Prisnak,Ball):-
asserta(pos(Prisnak)),sum_tash(Sum1),Sum2=Sum1+Ball,asserta(sum_tash(Sum2)),!.
tash_in_data_base("n",Prisnak,_):-
asserta(neg(Prisnak)),!,fail.
tash_in_data_base(_,_,_):-
write("nTASH-not correct answer"),!,fail.
oneQuestion(Id):-
fact1(Id,_,Prisnak),
pos(Prisnak),!.
oneQuestion(Id):-
fact1(Id,_,Prisnak),
not(neg(Prisnak)),
question_sepsis(Prisnak),!.Выводы
Надеюсь, эта статья поможет начинающим построить свою экспертную систему.
Автор: Ramin
