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

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

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. Аппарат логического вывода.


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


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


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


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


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


"(x) W(x), A L*W(A) (?)


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

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

Слов:1524
Символов:12693
Размер:24.79 Кб.