Реферат: Особенности реализации экспертных систем на базе логической модели знаний
Реферат: Особенности реализации экспертных систем на базе логической модели знаний
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. В нем принята обратная
стратегия вывода. Полностью реализованы все средства описания знаний
языка-предиката, в т.ч. и кванторами для порождения новых высказываний
используется операция резолюции.В качестве процедуры поиска решения,
позволяющей устранить монотонность и комбинаторный взрыв используют поиск в
иерархически упорядоченном пространстве состояний.
Список литературы
Для
подготовки данной работы были использованы материалы с сайта http://www.parny.by.ru/