Точно Не проект 2 / Не books / Источник_1

Если Р(х) – следствие посылки Q, которая не имеет свободных вхождений х, то из нее выводится xP(x).

Применение рассмотренных правил вывода состоит в простом сопоставлении посылок правил с утверждениями, содержащимися в базе знаний, и добавлении в базу знаний получаемых заключений.

Рассмотрим пример. Пусть имеются формулы:

Требуется вывести следствие этих формул x(Q(x) S(x)). Процесс вывода изображен в виде диаграммы на рисунке 3.1.

Данную диаграмму можно рассматривать как схему поиска решения в БЗ. При этом начальное состояние БЗ соответствует формулам (3.2) и (3.3). Операторы, преобразующие одно состояние БЗ в другое, задаются множеством правил вывода. Условие окончания поиска представлено фор-

мулой x(Q(x) S(x)).

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

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

Отметим, что в исчислении предикатов доказательство выводимости формулы из совокупности посылок сводится к установлению общезначимости формулы (3.2) или противоречивости (3.1). Верно и обратное утверждение: в исчислении предикатов первого порядка всякая общезначимая формула является теоремой, т.е. для нее существует вывод, в котором эта формула является последней. Данное утверждение представляет собой теорему о полноте в широком смысле, которую в 1930г. предложил выдающийся немецкий математик К. Гёдель. Кроме понятия полноты в широком смысле, есть еще понятие полноты исчисления в узком смысле. Исчисление называется полным в узком смысле, если к системе его аксиом нельзя присоединить без противоречия не выводимую в нем формулу. Исчисление предикатов не является полным в узком смысле, так как к его системе аксиом можно добавить без противоречия недоказуемую в нем формулу xP(x) xP(x) [8].

Рисунок 3.1 – Диаграмма вывода x(Q(x) S(x))

Исчисление предикатов – неразрешимая формальная система, т.е. не существует эффективной процедуры, позволяющей узнать по данной формуле, возможен ли ее вывод в исчислении предикатов или нет (теорема А. Черча, 1936). Формула выводима, если она общезначима. Следовательно, исчисление предикатов первого порядка неразрешимо относительно общезначимости. Иными словами, не существует общего метода для установления общезначимости любых формул исчисления предикатов первого порядка. Тем не менее, если, на самом деле, некоторая формула общезначима, то для нее существует процедура проверки общезначимости. Поэтому исчисление предикатов – полуразрешимая ФС.

3.2.4. Логики высокого порядка и псевдофизические логики

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

числения предикатов записать некоторые выражения естественного языка. Например, “В каких отношениях находятся объекты x и y?” или “Два объекта x и y равны, если и только если все их свойства попарно совпадают”. Описание указанных предложений можно выполнить с помощью

следующих формул: PP(x, y)и x y ((x y) ( P P(x) P(y))). Данные формулы используют кванторы по предикатным буквам и

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

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

Методы вывода логики первого порядка могут быть адаптированы к логике высокого порядка. Однако здесь нет прямого переноса. В логике высокого порядка разрешаются многократные возвраты к точкам выбора альтернативных подстановок (унификаторов), что приводит к большой разветвленности дерева вывода. Применение логики высокого порядка для автоматического доказательства теорем стало возможным благодаря разработке алгоритма унификации высокого порядка [70]. Известны соответствующие системы доказательства теорем логики высокого порядка, например, TPS [58], HOL [66]. Тем не менее, многие вопросы построения конструктивных процедур вывода для логики высокого порядка остаются открытыми.

Важным элементом логических моделей представления знаний являются псевдофизические логики [36]. Данные логики учитывают особенности восприятия окружающей действительности человеком. Выделяют следующие виды псевдофизических логик:

-временная логика – изучает взаимосвязь временных отношений;

-пространственная логика – изучает пространственные отношения;

-каузальная логика – изучает взаимосвязь отношений “причинаследствие”;

-логика действий – рассматривает отношения типа субъект-действие или действие-место.

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

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

3.3.Продукционные модели

3.3.1.Продукционные системы

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

В системах продукций знания представляются с помощью наборов правил вида: “если А, то В “. Здесь А и В могут пониматься как “ситуация – действие”, “причина – следствие”, “условие – заключение” и т.п. Часто правило-продукцию записывают с использованием знака логического следования:

A B.

Однако не следует отождествлять правило-продукцию и отношение логического следования. Дело в том, что интерпретация продукции зависит от того, что стоит слева и справа от знака логического следования. Часто под А понимается некоторая информационная структура (например, фрейм), а под В – некоторое действие, заключающееся в ее трансформации (преобразовании). Логическая интерпретация рассматриваемого выра-

жения накладывает жесткие ограничения на смысл символов А и В, которые должны рассматриваться как ППФ. Поэтому понятие продукции шире логического следования.

В качестве примера рассмотрим правило, взятое из базы знаний экспертной системы MYCIN [53], предназначенной для диагностики инфекционных заболеваний.

Если

1)место выделения культуры – кровь, и

2)реакция микроорганизма – грамотрицательная, и

3)форма микроорганизма – палочка, и

4)пациент относится к группе риска,

то

5) с уверенностью (0,6) название микроорганизма – pseudomonia aerugino-

sa.

Условие правила состоит из четырех фактов, соединенных союзом “и”. Если все четыре факта имеют место, то верным будет следствие правила. С каждым правилом связывается некоторое число, принимающее значение в диапазоне от -1 до 1, выражающее степень достоверности следствия и называемое коэффициентом уверенности. Это означает, что система работает с неточными и ненадежными фактами. Некоторые методы работы с неточными знаниями рассматриваются в параграфе 4.2 .

В базе знаний системы MYCIN факты представляются с помощью триплета: объект–атрибут–значение. Так, рассмотренное выше правило содержит пять фактов, которые можно представить в виде таблицы 3.1

Таблица 3.1 – Представление фактов

Если в процессе активизации правила первые четыре факта окажутся истинными, то в базу знаний будет помещен новый факт, представляемый триплетом объект–атрибут–значение. Одним из преимуществ хранения фактов в виде триплетов является повышение эффективности процедур поиска в базе знаний, так как появляется возможность упорядочения фактов по объектам и атрибутам.

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

приоритет правила продукции;Bc – предусловие применимости ядра продукции, представляющее предикат, при выполнении которого активизируется ядро продукции; Ac – постусловия продукции, определяющие действия и процедуры, которые необходимо выполнить после выполнения ядра продукции.

В общем случае продукционная система включает следующие компоненты:

- базу продукционных правил; - базу данных (рабочую память); - интерпретатор.

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

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

Интерпретатор реализует логический вывод. Процесс вывода является циклическим и называется поиском по образцу. Рассмотрим его в упрощенной форме. Текущее состояние моделируемой предметной области отражается в рабочей памяти в виде совокупности образов, каждый из которых представляется посредством фактов. Рабочая память инициализируется фактами, описывающими задачу. Затем выбираются те правила, для которых образцы, представляемые предпосылками правил, сопоставимы с образами в рабочей памяти. Данные правила образуют конфликтное множество. Все правила, входящие в конфликтное множество могут быть активизированы. В соответствии с выбранным механизмом разрешения конфликта активизируется одно из правил. Выполнение действия, содержащегося в заключении правила, приводит к изменению состояния рабочей памяти. В дальнейшем цикл управления выводом повторяется. Указанный процесс завершается, когда не окажется правил, предпосылки которых сопоставимы с образами рабочей памяти (рисунок 3.2).

Рисунок 3.2 – Продукционная система

Таким образом, процесс вывода, основанный на поиске по образцу, состоит из четырех шагов:

-выбор образа;

-сопоставление образа с образцом и формирование конфликтного набора правил;

-разрешение конфликтов;

-выполнение правила.

Поясним процесс функционирования продукционной системы на простом примере сортировки строки, состоящей из букв а, b и с [77]. Правила сортировки представлены на рисунке 3.3. Если образец, заданный предпосылкой правила, сопоставим с частью сортируемой строки, то правило активизируется. В результате этого подстрока, которая совпала с условием правила, замещается подстрокой из заключительной части правила.

Рассматривая исходную и отсортированную строки как начальное и конечное состояние задачи, а продукционные правила как операторы, преобразующие одно состояние в другое, приходим к выводу, что поиск решения в продукционных системах соответствует поиску в пространстве состояний. На рисунке 3.3 изображено дерево состояний задачи. Здесь вершины дерева соответствуют промежуточным состояниям сортируемой строки, а ребра – правилам-продукциям.

Продукционные системы были предложены американским математиком Э. Постом (1943) и рассматривались как модель организации вычислительного процесса. При этом правило-продукция трактовалось как оператор замены одной цепочки литер в некотором слове на другую цепочку. Систему продукций можно рассматривать как формальную систему с алфавитом А = а1, а2,…., аn , конечным множеством аксиом и конечным множеством правил вывода, имеющих вид

Pi : i s s i ,i 1,2,..., k ,

где i , i , s – слова алфавита А. Применение данного правила к некото-

рой цепочке литер, состоящей из слов i и s , означает вычеркивание i и приписывание i . Указанная замена соответствует подстановке, являющейся основным оператором нормальных алгоритмов Маркова [25] .

Множество продукций

1.ba ab 2. ca ac 3. cb bc

Рисунок 3.3 – Сортировка строки с помощью правил-продукций

Интересные результаты были получены А.Ньюэллом и Г.Саймоном при разработке системы GPS. Они установили, что правила-продукции соответствуют элементам знаний, накапливаемым в долговременной памяти человека. Такие элементы знаний активизируются, если возникает соответствующая ситуация (по образцу). Новые элементы знаний могут накапливаться в памяти без необходимости перезаписывания уже существующих элементов. Рабочая память продукционных систем аналогична кратковременной памяти человека, которая удерживает в центре внимания текущую ситуацию. Содержимое рабочей памяти, как правило, не сохраняется после решения задачи. Благодаря указанной аналогии, продукционные модели представления знаний получили широкое распространение в экспертных системах, моделирующих решение задач человеком-экспертом в той или иной области.

Широкое применение продукционных моделей определяется следующими основными достоинствами:

универсальностью, практически любая область знаний может быть представлена в продукционной форме;

модульностью, каждая продукция представляет собой элемент знаний о предметной области, удаление одних и добавление других продукций выполняется независимо;

декларативностью, продукции определяют ситуации предметной области, а не механизм управления;

естественностью процесса вывода заключений, который во многом аналогичен процессу рассуждений эксперта;

асинхронностью и естественным параллелизмом, который делает их весьма перспективными для реализации на параллельных ЭВМ.

Однако продукционные модели не свободны от недостатков:

процесс вывода имеет низкую эффективность, так как при большом числе продукций значительная часть времени затрачивается на непроизводительную проверку условий применения правил;

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

3.3.2.Управление выводом в продукционных системах

Входе решения проблемы машина вывода (интерпретатор) выполняет две задачи – собственно логический вывод и управление выводом. Логический вывод в продукционных системах не отличается особой сложностью и реализуется на основе процедуры поиска по образцу, описанной выше.

Управление выводом в продукционных системах предполагает решение двух вопросов [53]:

1)с чего следует начинать процесс вывода;

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

Ответ на первый вопрос приводит к прямой и обратной цепочке рассуждений, а на второй вопрос – к механизмам разрешения конфликтов в продукционных системах.

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

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

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

На рисунке 3.4 представлен пример поиска, управляемого данными, на множестве продукций, записанных в виде формул пропозициональной логики. Здесь на каждом шаге работы машины вывода применяется простая стратегия разрешения конфликтов: активизируется последнее из успешно сопоставленных правил. Порядок сопоставления правил соответствует их номерам.

Множество правил-продукций

Рисунок 3.4 – Прямой вывод в продукционных системах

На рисунке 3.5,а изображен граф решения. Вершины графа соответствуют высказываниям, а ребра – соответствующим правилам ввода. Процесс вывода начинается с размещения множества исходных фактов L, M и N в рабочей памяти и заканчивается, когда в рабочую память будет помещена целевая вершина Goal. Направление вывода обозначено рядом с графом и соответствует движению от стартовой к целевой вершине, т.е. от исходных данных (высказывания L,M и N). Поэтому такой вывод называют выводом, управляемым данными.

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