Геловани В.А. и др. Интеллектуальные системы поддержки принятия решений в нештатных ситуациях

Подождите немного. Документ загружается.

2.2.

Модели представления знаний 61

определенных элементов в области рассуждений. Например, «мужчи-

на» — это семантическая категория, состоящая из имен всех мужчин,

имеющихся в БД.

Каждый элемент рассуждений D может быть задан как список

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

на D, допускает в качестве аргументов только те элементы, которые

обладают определенными свойствами.

В дальнейшем универсум рассуждений будет считаться универсаль-

ной семантической категорией, обозначаемой UNIV.

Имена, даваемые категориями, могут определяться произвольно

и являются синтаксическими объектами. Для задания теоретико-мно-

жественных отношений между семантическими категориями строится

граф семантических категорий или просто семантический граф.

Семантический граф G есть конечный граф, вершинами которого

служат семантические категории. Дуги G указывают теоретико-множе-

ственные отношения:

1) Категория С, является частью категории С, (обозначение: С, С Cj),

если X С С,

X С Cj для каждого х из области UNIV.

2) Категория С, равна категории С, (обозначение: С,- = Cj), если

С, С С, и С, С С,.

3) Категория С, не пересекается с категорией Cj (обозначение:

C,Q)Cj,

если

C,nCj—

Висяшле вершины графа G называются примитивными категориями.

Отношение равенства, здесь введенное, допускает разбиение ка-

тегории С на конечное число подмножеств СьСг, ...,С„ таких, что

выполняются равенства:

1) UC-С;

1=1

2) С,

С, =

О,

{ф

Из категорий с использованием операций пересечения (), объединения ()

и дополнения () можно получить так называемые булевы категориальные

выражения, которые сильно увеличивают вьфазительные возможности

семантических категорий (Дж. Минкер и Дж. Мак-Скимин) [88, 90]. При-

меры булевых категориальных выражений: растение животное, студент

молодой.

Важным видом семантической информации является назначение

ограничений, связанных с семантическими категориями, для аргументов.

Эти ограничения запоминаются в пространстве семантических форм.

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

являются ли вопрос и дизъюнкты из БД несовместимыми, т. е. семан-

тические формы определяют, какие константы или функции могут быть

подставлены в качестве аргументов некоторого множества п-ок. Для за-

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

записи утверждений и общих правил.

62 Глава 2. Представление знаний в системах поддержки решений

Г. Хендрикс называет подобный механизм очерчиванием (delin-

eation), который позволяет уменьшить перебор при поиске нужной ин-

формации и резко повысить эффективность механизмов вывода.

Таким образом, в семантической сети можно выделить следующие

структурные компоненты:

— семантический граф, который определяет теоретико-множественные

отношения между семантическими категориями;

— база данных, состоящая из утверждений и общих правил (законов),

представленных в виде дизъюнктов;

— пространство семантических форм, которое определяет семантичес-

кие ограничения, наложенные на аргументы реляционных п-ок;

— словарь, который определяет для каждого элемента области, каждого

функционального имени и предикатного имени ту семантическую

категорию, членом которой он является.

В настоящее время аппарат семантических сетей щироко исполь-

зуется в практике представления знаний. Его достоинствами являются:

большие выразительные возможности, естественность и наглядность си-

стемы знаний, представленной графически, близость структуры сети,

представляющей систему знаний, семантической структуре фраз есте-

ственного языка.

Общая идея использования ориентированных графов для предста-

вления знаний нашла различное воплощение у разных исследователей

Этим объясняется отсутствие единой терминологаи и формально опре-

деляемой семантики для методов представления знаний, основанных

на семантической сети.

2.3.

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

2.3.1.

Основные определения

Продукции наряду с фреймами являются наиболее популярны.ми

средствами представления знаний в ИС. Продукции, с одной сторо-

ны,

близки к логическим моделям, что позволяет организовать на них

эффективные процедуры вывода, а с другой стороны, более наглядно от-

ражают знания, чем классические логические модели. В них отсутствуют

жесткие ограничения, характерные для логических исчислений, что дает

возможность изменять интерпретацию элементов продукции.

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

вида [77]:

(i);

Q; Р; А^В; N.

Здесь i — имя продукции, с помощью которого данная продукция выде-

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

некоторая лексема, отражающая суть данной продукции (например, «по-

купка книги» или «набор кода замка»), или порядковьгй номер продукции

в их множестве, хранящемся в памяти системы.

Элемент Q характеризует сферу применения продукции. Такие сфе-

ры легко выделяются в когнитивных структурах человека. Наши знания

2.3.

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

как бы «разложены по полочкам». На одной «полочке» хранятся знания

о том, как надо готовить пищу, на другой — как добраться до работы

т.

п. Разделение знаний на отдельные сферы позволяет экономить время

на поиски нужных знаний. Такое же разделение на сферы в базе зна-

ний ИС целесообразно и при использовании для представления знаний

продукционных моделей.

Основным элементом продукции является ее ядро: А ^ В. Интер-

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

стоит слева и справа от знака секвенции >. Обычное прочтение ядра

продукции выглядит так: ЕСЛИ А, ТО В, более сложные конструк-

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

ЕСЛИ А, ТО Bi, ИНАЧЕ Bj Секвенция может истолковываться в обыч-

ном логическом смысле как знак логического следования В из истин-

ного А (если А не является истинным выражением, го о В ничего

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

пример А описывает некоторое условие, необходимое для того, чтобы

можно бьшо совершить действие В.

Элемент Р есть условие применимости ядра продукции. Обычно Р

представляет собой логическое выражение (как правило, предикат). Ко-

гда Р принимает значение «истина», ядро продукции активизируется.

Если Р ложно, то ядро продукции не может быть использовано. Напри-

мер,

если в продукции «НАЛИЧИЕ ДЕНЕГ; ЕСЛИ ХОЧЕШЬ КУПИТЬ

ВЕЩЬ X, ТО ЗАПЛАТИ В КАССУ ЕЕ СТОИМОСТЬ И ОТДАЙ ЧЕК

ПРОДАВЦУ» условие применимости ядра продукции ложно, т. е. денег

нет, то применить ядро продукции невозможно.

Элемент N описывает постусловия продукции. Они актуализируются

только в том случае, если ядро продукции реализовалось. Постусловия

продукции описывают действия и процедуры, которые необходимо вы-

полнить после реализации В. Например, после покупки некоторой вещи

в магазине необходимо в описи товаров, имеющихся в этом магазине,

уменьшить количество вещей такого типа на единицу. Выполнение N

может происходить сразу после реализации ядра продукции.

Если в памяти системы хранятся некоторые продукции, то они

образуют систему продукций. В системе продукций должны быть заданы

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

происходит актуализация продукций и выбор для выполнения той или

иной продукции из числа актуализированных.

В ряде ИС используются комбинации сетевых и продукционных

моделей представления значений.

таких моделях декларативные знания

описываются в сетевом компоненте модели, а процедурные знания —

в продукционном.

этом случае говорят о работе продукционной системы

над семантической сетью [70].

2.3.2.

Классификация ядер продукции

51дра продукции можно классифицировать по различным основа-

ниям Прежде всего все ядро делится на два больших типа: детерми-

нированные и недетерминированные. В детерминированных ядрах при

64 Глава 2.

Представление знаний

системах поддержки решений

актуализации ядра и при выполнимости А правая часть ядра выполня-

ется обязательно; в недетерминированных ядрах В может выполняться

и не выполняться. Таким образом, секвенция ^ в детерминирован-

ных ядрах реализуется с необходимостью, а в недетерминированных —

с возможностью. Интерпретация ядра в этом случае может, например,

выглядеть так: ЕСЛИ А, ТО ВОЗМОЖНО В.

Возможность может определяться некоторыми оценками реализации

ядра. Например, если задана вероятность выполнения В при актуали-

зации А, то продукция (в простейшем случае продукция состоит лишь

из ядра) может быть такой: ЕСЛИ А, ТО С ВЕРОЯТНОСТЬЮ р РЕ-

АЛИЗОВАТЬ В. Оценка реализации ядра может быть лингвистической,

связанной с понятием терм-множества лингвистической переменной,

например: ЕСЛИ А, ТО С БОЛЬШОЙ ДОЛЕЙ УВЕРЕННОСТИ В.

Возможны иные способы задания оценки реализации ядра.

Детерминированные продукции могут быть однозначными и аль-

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

тернативные возможности выбора, которые оцениваются специальными

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

лингвистические оценки, экспертные оценки и т. п. (например, ЕСЛИ А,

ТО ЧАЩЕ ВСЕГО НАДО ДЕЛАТЬ В^ РЕЖЕ Bj)-

Особым типом являются прогнозирующие продукции, в которых

описываются последствия, ожидаемые при актуализации А, например

ЕСЛИ Л, ТО С ВЕРОЯТНОСТЬЮ р МОЖНО ОЖИДАТЬ В.

Дальнейшую классификацию ядер продукции можно провести, опи-

раясь на типовую схему СППР (рис. 2.8). Если х и у обозначают любой

из блоков рисунка (О, Д, 3, Л), то ядро Ах ^ By означает, что ин-

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

ции В посылается в блок у. Комбинации х и у, осмысленные с точки

зрения ИС, отмечены в табл.

2.1

знаком «+».

Рассмотрим часто встречающийся тип продукции Ад > Вз- В этом

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

хранящейся в базе знаний. При сетевом представлении это могут быть

фрагменты семантической сети, при логических моделях

—

формулы того

или иного исчисления. Тогда смысл продукции Аз ^ Вз состоит в замене

одного фрагмента базы знаний

другим.

Для актуализации этой продукции

необходимо, чтобы в базе знаний существовал фрагмент, совпадающий

с А. При поиске в базе знаний А играет роль образца, а процедура такого

поиска называется поиском по образцу.

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

для представления знаний используется семантическая сеть и продукция.

Поиск А в базе знаний организуется различными способами. Можно,

например, сначала искать вершину а. Если в базе знаний такой верши-

ны нет, то поиск по образцу заканчивается неудачей. Если вершина а

найдена, то ищутся все выходящие из нее дуги, помеченные отноше-

нием Дз, так как в образце справа от этой дуги стоит вершина ж,

на месте которой в базе знаний может находиться любая вершина. Если

2.3.

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

Данные (Д) ^

лг

Объект(О)

к.

Логика

поиска

решений (Л)

лг

Знания (3)

Рис.

2.8

из а не выходит ни одной дуги, помеченной отношением Rg, то по-

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

происходит переход во все вершины, с которыми вершину а связывает

отношение -Rg, т. е. возникает параллельный процесс поиска. В приме-

ре произойдет переход от вершины а к вершинам Ь и /, из которых

начнется поиск выходящих из них дуг, помеченных отношением Rg,

ведущих в любую вершину, так как в образце далее стоит вершина,

которой соответствует свободная переменная у. Далее процесс продол-

жается аналогичным образом. В примере поиск по образцу оказывается

успешным. После нахождения А в семантической сети происходит заме-

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

трансформированная сеть.

Продукция Ад ^ Вд может соответствовать процедуре нахождения

закономерностей по эмпирическим данным. Логический блок на осно-

вании просмотра и анализа данных выдвигает гипотезы о наличии

Таблица 2.1

В ""-^^

о - объект

Д - данные

3 ~ знания

Л - логика

О - объект

Д - данные

3 - знания

Л - логика

66 Глава 2.

Представление знаний

системах поддержки решений

закономерностей и, убедившись в их приемлемости и достаточной обо-

снованности, записывает их в базу знаний. Аналогично можно интегри-

ровать и иные типы продукций.

2.3.3.

Управление системой продукций

При выполнении условия применимости ядер продукции для данной

группы продукции возникает дилемма выбора той продукции, которая

в данной ситуации будет активизирована. Решение этой задачи возлага-

ется на систему управления системой продукций. Если, например, ИС

реализована на ЭВМ с параллельной архитектурой, то из фронта готовых

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

параллельных ветвей может одновременно в данной ситуации выполнять

ЭВМ. Но независимо от количества актуализированных продукций задача

альтернативного выбора остается.

Задача управления характерна не только для систем продукций,

но и для всех систем, где необходимо выполнение параллельных про-

цессов с учетом имеющегося технического ресурса [75, 121]. Возможны

два пути ее решения: централизованный и децентрализованный. При

централизованном управлении выполнением продукций решение об ак-

туализации принимается специальной системой управления, а при децен-

трализованном определяется складывающейся в этот момент ситуацией.

Если порядок выполнения продукций произволен, то решение определя-

ется текущей ситуацией или системой управления; если порядок важен,

то в продукциях должна содержаться информация о требованиях к этому

порядку. Если в постусловиях продукции, которая должна выполняться

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

для ЭВМ, то она реализуется как обычный алгоритм.

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

1) Принцип «стопки книг».

Этот принцип основан на идее, что наиболее используемая про-

дукция является наиболее полезной. Готовые продукции как бы обра-

зуют «стопку», в которой порядок определяется накопленной часто-

той использования в прошлом. На самом верху «стопки» находится

продукция, которая использовалась чаще всех. При актуализации не-

которого фронта готовых продукций для исполнения выбирается та

продукция (или те продукции при наличии параллельных технических

устройств), у которой частота использования максимальна. Подобный

принцип управления особенно хорош, когда частота исполнения под-

считывается с учетом некоторой ситуации, в которой ранее исполня-

лась продукция, и это исполнение имело положительную оценку. При

такой обратной связи метод стопки книг может превратиться в обу-

чающуюся процедуру, адаптирующуюся к тем задачам, которые возни-

кают во внешней среде. Управление по принципу стопки книг целе-

сообразно применять, если продукции относительно независимы друг

от друга, например, когда каждая из них есть правило вида «ситуа-

ция (А) > действие (В)». Именно такой случай имеет место в планиру-

ющих системах для роботов.

2.3.

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

2) Принцип наиболее длинного усповия.

Этот принцип заключается в выборе из фронта готовых продукций

той, у которой стало истинным наиболее «длинное» условие выполни-

мости ядра. Этот принцип опирается на соображение «здравого смысла»,

что частные правила, относящиеся к узкому классу ситуаций, важнее об-

щих правил, относящихся к широкому классу ситуаций, так как первые

учитывают больше информации о ситуации, чем вторые. Трудность ис-

пользования данного принципа состоит в том, что надо заранее упорядо-

чить условия по вхождению друг в друга по отношению «частное-общее».

Исследование систем продукции упорядоченных подобным образом, при-

вело к появлению понятия К-систем, оказавшихся более богатой моделью

процессов, чем классические алгоритмические модели [64], однако не га-

рантирующих однозначного результата, получаемого за конечное число

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

ние по принципу наиболее длинного условия в продукциях, образующих

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

знания и сами продукции хорошо структурированы привязкой к типовым

ситуациям, на которых задано отношение типа «частное-общее».

3) Принцип метапродукций.

Основано на идее ввода в систему продукций специальных мета-

продукций, задачей которых является организация управления в системе

продукций при возможности неоднозначного выбора из фронта готовых

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

ванный из американской системы MYCIN-TEIRESTAS, предназначен-

ной для диагностики инфекционных заболеваний. ЕСЛИ инфекция есть

pelvic-abcess и имеются продукции, входящие в состав фронта, в которых

в условии А упоминается grampos-rods, ТО продукции, у которых в А име-

ется enterobacteriaceae, следует активизировать раньше, чем продукции,

содержащие в А gramposrods.

В примере метапродукция опирается на факт вхождения опреде-

ленных продукций во фронт готовых продукций. Конечно, условием,

записанным в метапродукции, может выступать и некоторое утверждение

о невхождении определенных продукций во фронт готовых продукций.

4) Принцип «классной доски».

Основан на идее спусковых функций

[121].

При реализации принци-

па «классной доски» в ИС вьщеляется специальное рабочее поле памяти

—

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

их при необходимости. На этой «доске» параллельно выполняющиеся

процессы находят информацию, инициирующую их запуск, на нее же

они и выносят информацию о своей работе, которая может оказаться

полезной для других процессов.

Как правило, на «классной доске» вьщелены специальные ноля

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

для разных сфер применения продукций, специальные поля для записи

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

адресованы другим продукциям. С принципом «классной доски» может

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

68 Глава 2. Представление знаний в системах поддержки решений

он требует проверки некоторых условий, которые фиксируют в рабочем

поле памяти, а также другие принципы управления.

Если система продукций работает над некоторой сетевой моделью

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

принимать специальные меры защиты от «порчи знаний» работающими

продукциями. Для этого также используется рабочее поле памяти, куда

временно переносится фрагмент знаний, которым оперируют продукции.

Этот фрагмент фиксируется на специальном поле «классной доски».

5) Принцип приоритетного выбора.

Этот принцип связан с введением статических или динамических

приоритетов на продукции Статические приоритеты могут формировать-

ся априори на основании сведений о важности продукционньгх правил

в данной проблемной области. Эти сведения, как правило, представляют

собой информацию, извлекаемую из эксперта. Динамические приорите-

ты вырабатываются в процессе функционирования системы продукций-

и могут отражать, например, такой параметр, как время нахождения

продукции во фронте готовых продукций. К данному типу управления

относится задание последовательности приоритетов с помощью специ-

альной каузальной семантической сети

[126].

В этом случае задается

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

складывающимися ситуациями и в каждой вершине которого задана

функция выбора очередной продукции из фронта готовых продукций.

Если продукции работают над семантической сетью, приоритеты

могут формироваться не в системе продукций, а в сети [25].

Как и при логическом выводе, существуют два типа выполнения

систем продукций: прямой и обратный. В первом случае поис!^ идет

от левых частей продукций, т. е. проверяются условия А и актуализиру-

ются те продукции, для которых А имеет место; во втором — от изна-

чально заданных В, по которым определяются необходимые для В зна-

чения А, которые, в свою очередь, отождествляются с правыми частями

ядер продукций в системе. Два этих метода часто называют восходящим

и нисходящим методами реализации системы продукций.

6) Управление по именам.

Основано на задании для имен продукций, входящих в некото-

рую систему, некоторой формальной грамматики или другой процедуры,

обеспечивающей сужение фронта готовых продукций и выбор из него

очередной продукции для выполнения.

Например, пусть система продукций представлена четырьмя про-

стейшими продукциями, состоящими лишь из ядерных частей:

(а) А^В;

(б) А&В ^ D;

(в) Aw В > U;

(г) D^C.

таком виде система продукций явно недертерминирована. Если выпол-

няется А, то фронт готовых продукций включает продукции с именами

(а) и (в), а если выполняется В и D, то три последние продукции.

2.3.

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

Для устранения подобной недетерминированности может быть введена

некоторая грамматика для имен продукций.

(а) > (б);

(в) ^ (б);

(а) ^ (г).

Тогда если в некоторый момент была выполнена продукция с именем (б),

то новые продукции выполняться не будут. Если же в некоторый момент

выполнилась продукции с именем (а), то после нее смогут выполняться

продукции с именем (б) или (г). Но левые части ядер в этих продукциях

таковы, что неоднозначность возникает лишь в случае, когда В и D

одновременно выполнены. С помощью грамматики для имен продукций

можно задать однозначный алгоритмический процесс.

Продукционным моделям не хватает строгой теории. Пока на практи-

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

При задании модели проблемной области в виде совокупности продук-

ций нельзя быть уверенным в ее полноте и непротиворечивости. Причина

неудач создания теории кроется в расплывчатости понятия продукции,

в той интерпретации, которая приписывается ядру, а также в различных

способах управления системой продукций. Переход к алгоритмической

схеме мало что дает, так как при этом исключается основное свойство

продукционных систем — их модульность и проистекающая из этого

асинхронность и параллельность выполнения продукций в системе.

Следует ожидать, что теория продукционных систем появится не ра-

нее,

чем будут созданы эффективные теории параллельных информацион-

ных процессов [71]. Но некоторые результаты можно получить на основе

существующих методов оптимального управления [63], введя ряд ограни-

чений на понимание продукций и систем продукций.

Другая проблема практического применения продукционных дмоде-

лей — переход от статических систем к динамическим, меняющим состав

продукций в системе или перестраивающим алгоритм управления выбо-

ром продукций из фронта готовых продукций в зависимости от текущих

ситуаций. Такие системы продукций называются адаптивными, или си-

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

срабатывания продукций имеет решающее значение [79]. Достичь этого

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

торых должны быть стратегии различного уровня сложности и быстроты

срабатывания

[103].

2.3.4. Отличительные особенности продукционных систем

Термин «продукция» введен американским логиком Э. Постом. В по-

нимании Поста в качестве продукции выступала только та ее часть, ко-

торую теперь называют ядром. Запись «ЕСЛИ А, ТО В» трактовалась

как оператор замены цепочки А цепочкой В в некотором входном слове,

т. е. продукции были тем, что позже стали именовать подстановками

и использовать при описании различных уточнений понятия алгоритма.

Например, подстановки являются основным оператором в нормальных

70 Глава 2. Представление знаний в системах поддержки решений

алгоритмах Маркова. Поэтому в языке программирования Рефал, осно-

ванном на идее такой модели уточнения понятия алгоритма, оператор

подстановки играет основную роль. Идея продукции используется в язы-

ках логического программирования, нашедших применение в ИС. Среди

языков подобного типа наиболее известен Пролог. Продукционный под-

ход стал стилем нового этапа программирования.

Системы продукций широко распространены в экспертных систе-

мах [60].

Популярность продукционных моделей определяется несколькими

факторами.

1) Подавляющая часть человеческих знаний может быть записана

в виде продукций.

2) Системы продукций являются модульными. За небольшим ис-

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

в остальных продукциях.

3) При необходимости системы продукций могут реализовывать лю-

бые алгоритмы и, следовательно, способны отражать любое процедурное

знание, доступное ЭВМ.

4) Наличие в продукциях указателей на сферу применений продук-

ции позволяет наиболее эффективно организовать память, сократив вре-

мя поиска в ней необходимой информации. Классификация сфер может

быть многоуровневой, что еще более повышает эффективность поиска

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

5) При объединении систем продукций и сетевых представлений

получаются средства, обладающие большой вычислительной мощностью.

6) Естественный параллелизм в системе продукций, асинхроуность

их реализации делают продукционные системы удобной моделью вычи-

слений для ЭВМ новой архитектуры, в которой идея параллельности

и асинхронности является центральной.

Продукционные модели имеют по крайней мере два недостатка. При

большом числе продукций становится сложной проверка непротиворечи-

вости системы продукций. Это заставляет при добавлении новых продук-

ций тратить много времени на

npoBepicy

непротиворечивости новой систе-

мы.

Из-за присущей системе недетерминированности (неоднозначного

выбора выполняемой продукции из фронта активизированных продук-

ций) возникают принципиальные трудности при проверке корректности

работы системы. Считается, что если в ИС число продукций достигает

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

правильно функционировать. Именно поэтому число продукций, с кото-

рым, как правило, работают современные ИС, не превышает тысячи.