Реферат: Особенности реализации экспертных систем на базе логической модели знаний

1.Понятие логическоймодели знаний.

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

Формальнаятеория задаетсявсегда четверкойсимволов S=<B, F,A, R>, где

В- конечное множествобазовых символов, иначе — алфавиттеории S;

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

А- выделенноемножествоправил, называемыхаксиомамитеории, т. е.множествоаприорно истинныхформул.

R- конечное множествоотношений { r1,r2,…, rn} между формулами, называемымиправиламивывода. Длялюбого riсуществуетцелое положительноечисло j, такое, что для каждогомножества, состоящегоиз j формул, идля каждойформулы F эффективнорешается вопросо том, находятсяли эти j-формулыв отношенииri сформулой F. Еслиriвыполняется, то F называютнепосредственнымследствиемF-формул по правилуri.

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

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

Формальнаятеория наз.разрешимой, если существуетэффективнаяпроцедура, позволяющаяузнать длялюбой заданнойформулы, существуетли её вывод втеории S.

Формальнаятеория S наз.Непротиаворечивой, если не существуеттакой формулыА, что и А, и неА выводимы вданной теории.

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

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

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

Кдругим недостаткамлогическоймодели относят:

— “монотонность”;

— “комбинаторныйвзрыв”;

— слабостьструктурированностиописаний.

2.Характеристикаязыка предикатовпервого порядка.Особенностипредставлениязнаний.

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

Синтаксисязыка предикатоввключает: предикативныесимволы, символыпеременных, константы (?), а также разделители( ), [ ], “, ‘.

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

Атомарнаяформула:

Является( Иванов, спец.—поЭВМ)

предикативныйтерм1 терм2

символ

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

Изформул можносоставитьпредложениес помощью логическихсвязок: конъюнкция, дизъюнкция, импликация, отрицание.

Конъюнкция( )используетсядля образованиясоставных фраз:

Учится( Иванов, эк.-университет) располагается( эк.-университет, Киев )

ППФ, построенныес помощью связкиконъюнкция, наз-ся простоконъюнкциями.

Дизъюнкция(  ) реализуетфункцию неисключающего“или”.

Находятся( Иванов, аудит.-147)И находится( Иванов, библиотека).

ППФ, построенныес помощью связкидизъюнкция, наз-ся дизъюнкциями.

Связкаимпликация(  ) используетсядля представленияутверждениятипа “если, то”.

Владеть( Иванов, машина-1) марка( машина-1, “BMW”).

ППФ, построеннаяпутем соединенияформул с помощьюсвязки импликация, наз-ся импликацией.

Леваясторона импликацииназ-ся антецедент, правая — конциквент.Импликацияимеет значение“истина”, еслиантецеденти конциквентимеют значения“истина”, либоантецедентимеет значение“ложь” независимоот конциквента.В остальныхслучаях импликацияимеет значения“ложь”.

ППФсо знаком отрицания( ~ ) пред ней наз-сяотрицанием.

Вязыке предикатоватомная формуламожет приниматьтолько истинныезначения, тольколожные значения, а также в зависимостиот значенийпеременных, которые в неевходят, либоитсина, либоложь. Для того, чтобы при исчислениипредикатовможно быломанипулироватьзначениямипеременных, потребовалосьввести понятие“квантор”.

Квантор- это операция, в которой участвуютвсе значенияпеременнойодного предиката.

Кванторслужит дляуказания меры, в какой экземплярыпеременной(?), то есть константыдолжны бытьистинными, чтобы все значенияв целом былиистинными.

Различаютквантор общности иквантор сущестовования. Еслиперед предикатомзаписан квантор длякакой-то переменной, напр. (х), то это означает, что значениепредиката будетистинным тольков том случае, если все значенияпеременнойх будут истинными.

(х)( специалист-по-ЭВМ(х) программист)

Еслиперед предикатомзаписан квантор, напр.(х), тодля истинностипредикатадостаточно, чтобы тольконекотрые значенияпеременной, по крайней мереодно, были истинными.

(х)( специалист-по-ЭВМ(х) оптимист(х))

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

(х)(y) ( служащий(х) руководитель(y, х))

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

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

3.Аппарат логическоговывода.

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

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

“Modusponens” — используетсядля созданияиз ППФ вида АППФ вида В

(А  В). (“турникет”)интерпретируетсякак “следовательно”.

Операцияспециализации.Суть — позволяетдоказать, чтоесли некоторомуклассу обьектовприсуще к.-л.свойство, толюбой обьектданного классабудет обладатьэтим свойством.Для всех обьектовкласса исп.свойство А, следовательно

x)W(x), A L*W(A) (?)

Операция— унификация.Использ-ся длядок-ва теории, содержащихквантиоризированныеформулы приводятв соответствиеопределенныеподвыраженияформы путемнахожденияподстановок.

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

Дляприменениярезолюции ППФдолжны бытьпереведеныв клаузальнуюформу путемупрощения, азатем представленов форме дизьюнкции.Процесс преобразованиясводится кследующ. основнымэтапам:

1— исключениесимволов импликациииз формул иограничениеобласти действиясимвола отрицания

2— разделениепеременных, т.е. замена однойсвязаннойкванторомпеременной, кот. встречаетсяв выражениинесколько раз— различнымиименами

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

4— преобразованиепредположенийв префикснуюформу, т.е. в ППФне остаетсякванторовсуществования.Каждый кванторобщности имеетсвою переменную, поэтому всекванторы общностиможно переместитьв начало ППФи считать, чтообласть действиякаждого кванторавключает всюППФ.

5— приведениематрицы кконьюнктивнойнормальнойформе, т.е. коньюнкцииконечногомножествадизьюнкций.

6— исключениекванторовобщности. Этовозможно, т.к.всепеременные, оставшиесяна этом этапеотносятся кквантору общности.

7— исключениесимволов коньюнкции.В результатематрица остаетсятольков виде дизьюнкций, над которымивозможно проведениеопераций резлюции.

4.Особенностимашинной реализацииязыка предикатовпервого порядка.

Машиннаяреализацияязыка предикатапервого порядкаимеет ряд серьезныхпроблем, которыесвязаны суниверсальностьюаппарата логическоговывода. 1-я проблема— монотонностьрассуждений(в процесселогическоговывода нельзяотказатьсяот промежуточногозаключения, если становятсяизвестнымидополнительныефакты, которые свидетельствуюто том, что полученныена основе этогозаключениярешения неприводят кжелаемомурезультату.2-я проблема —комбинаторныйвзрыв ( в процесселогическоговывода невозможноприменятьоценочныекритерии длявыбора очередногоправила. Безсистемноеприменениеправил в рассчетена случайноедоказательствоприводит ктому, что возникаетмного лишнихцепочек ППФ, активных вопределенныймомент времени.Это чаще всегоприводит кпереполнениюрабочей памяти.

Впроцессе исследованийпо отысканиюэффективныхпроцедур машиннойреализацииязыка предикатанаметилось2 основныхподхода(кон.60-х гг.):

1— Отбрасываетсяпринцип универсальностиязыка предикатаи производитсяпоиск конкретныхпроцедур, эффективныхдля конкретнойпредметнойобласти. В этомслучае в БЗвводилисьобширные знанияпредметнойобласти. Наиболеетипичныйпредставитель— LISP

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

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