А ЛГЕБРАИЧЕСКАЯ ТЕОРИЯ ПРОДУКЦИОННЫХ СИСТЕМ ЧАСТЬ II: ПРИЛОЖЕНИЯ А.В.Жожикашвили ИППИ РАН

П РИКЛАДНЫЕ СИСТЕМЫ Система Задача системы Что добавлено ЗНАТОКПрограммируемая оболочка Базовая система МЕТА-ЭСКонсультация по разработке экспертной системы для решения некоторой задачи Пример заполненной базы знаний СВАЯВыбор свай и расчета их несущей способности Широкое использование присоединенных процедур СЕЙСМООценка времени и силы возможного землетрясения Нечеткие данные, динамические данные КОДЕКСВыявление конструкций со значением обусловленности Изменился формат данных Продукционная сеть

С ИТУАЦИИ, ОБРАЗЦЫ, СОПОСТАВЛЕНИЕ Ситуация То, на что воздействует продукция, что она преобразует. В результате действия продукции возникает новая ситуация. Образец Неполное описание ситуации, в котором часть деталей опущено. Конкретизация образца Добавление к образцу недостающей информации, что превращает его в ситуацию. Можно получить различные ситуации. Конкретизатор То, что добавляется к образцу. Множество конкретизаторов Все, что в принципе можно добавить к образцу. Сопоставление ситуации с образцом Проверка того, существует ли конкретизатор, превращающий данный образец в данную ситуацию. Результат – сопоставима/не сопоставима и найденный конкретизатор.

П РОДУКЦИИ Продукция состоит из двух образцов – левой и правой части продукции. Левая часть описывает ситуацию, в которой продукция применима, правая – ситуацию, которая возникнет после ее применения. Применение продукции к ситуации состоит из двух шагов. Первый шаг – сопоставление ситуации с левой частью продукции. Если сопоставление невозможно – продукция не применима. Второй шаг – конкретизация правой части продукции с использованием того же конкретизатора, который был найден при сопоставлении ситуации с левой частью.

О БРАЗЕЦ И ПРОДУКЦИЯ НА ЯЗЫКЕ МНОЖЕСТВ И ОТОБРАЖЕНИЙ Множество ситуаций S Множество конкретизаторов X S-образец Продукция из S в T ST X s x ϕ s=φ(x)s=φ(x) s x t ϕ ψ t =ψ( x )

О Т СИСТЕМЫ ОБРАЗЦОВ – К ТЕОРИИ КАТЕГОРИЙ Задать систему образцов – это значит определить следующее: какие множества могут выступать в качестве множеств ситуаций/конкретизаторов какие отображения могут выступать в качестве образцов Класс образцов замкнут относительно композиции и содержит тождественные отображения. Задать систему образцов – это значит задать конкретную категорию, т.е. подкатегорию категории множеств указать, какие морфизмы могут играть роль ситуаций Уточнение: задать систему образцов – это значит задать категорию указать, какие морфизмы могут играть роль ситуаций

Т ЕОРЕТИКО - КАТЕГОРНЫЕ ОПРЕДЕЛЕНИЯ S IX S X ϕ ϕ α β S IX ϕ α β T ψ S X ϕ T ψ S -образец Сопоставление ситуации с образцом Продукция из S в T Применение продукции к ситуации

Т ЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ ПРОДУКЦИОННЫХ СИСТЕМ Нижний уровень – уровень данных. Представляет собой программную реализацию категории. Верхний уровень – уровень продукций. Представляет собой реализацию алгоритмов работы системы продукций. Для доступа к продукциям верхний уровень использует только процедуры, экспортируемые нижним уровнем, т.е. он написан в терминах теории категорий

Н ИЖНИЙ УРОВЕНЬ – УРОВЕНЬ ДАННЫХ Должны быть описаны структуры данных, служащие для представления ситуаций, образцов и конкретизаторов. Должны быть определены функции, реализующие основные операции над ними, прежде всего - операцию сопоставления и конкретизации.

Н ИЖНИЙ УРОВЕНЬ – УРОВЕНЬ ДАННЫХ Должны быть описаны структуры данных, служащие для представления ситуаций, образцов и конкретизаторов. Должны быть определены функции, реализующие основные операции над ними, прежде всего - операцию сопоставления и конкретизации. На языке теории категорий: Должны быть описаны структуры, кодирующие морфизмы категории. Должны быть определены операции над морфизмами, прежде всего – две базовые функции: composition и factor: composition: (β,φ) α factor: (α,φ) β S IX ϕ α β

Н ИЖНИЙ УРОВЕНЬ – УРОВЕНЬ ДАННЫХ На нижнем уровне, в частности, должны быть учтены: тип данных, преобразуемых продукциями: логические выражения, база данных, содержащая факты, текстовые данные; характер данных: нечеткие, динамические.

В ЕРХНИЙ УРОВЕНЬ – УРОВЕНЬ ПРОДУКЦИЙ Решаются следующие задачи: Программируется алгоритм вывода на продукциях. Наряду с обычной логикой работы продукционной системы на верхнем уровне может быть запрограммирована какая- либо более сложная схема вывода. Далее будет рассказана продукционная сеть. На верхнем уровне могут быть реализованы алгоритмы анализа продукционной базы, процедуры оптимизации продукционной базы. На верхнем уровне могут быть реализованы процедуры автоматического создания продукционной базы, например, основанные на обобщении решения конкретных задач.

П РИМЕР РЕАЛИЗАЦИИ НА ВЕРХНЕМ УРОВНЕ ФУНКЦИИ ПРИМЕНЕНИЯ ПРОДУКЦИИ (defun apply_production(prd sit) (let ((conc (factor sit (cadr prd)))) (if conc (composition conc (car prd)) ) ) )

В ЗАИМОСВЯЗЬ ПРИКЛАДНЫХ СИСТЕМ ЗНАТОК СВАЯ СЕЙСМО Нечеткость, динамика База знаний МЕТА-ЭС База знаний КОДЕКС Уровень продукций Уровень данных PROMPTER Продукционная сеть Формат данных Автоматическое формирование образцов

П РОГРАММИРУЕМАЯ ОБОЛОЧКА З НАТОК - ФАКТЫ Система выводит новые факты из уже известных. Примеры фактов: тип сваи, который следует использовать – свая-стойка (СВАЯ) уровень воды в колодцах является пониженным ( СЕЙСМО ) расторжение брака производится в органах записи актов гражданского состояния (ЮРИСТ) Общий вид факта: = тип_сваи= свая-стойка уровень_воды_в_колодцах=пониженный место_расторжения_брака=ЗАГС

П РОГРАММИРУЕМАЯ ОБОЛОЧКА З НАТОК - ФАКТЫ Общий вид правила: Если АТРИБУТ 1 = ЗНАЧЕНИЕ 1 И АТРИБУТ 2 = ЗНАЧЕНИЕ 2 … И АТРИБУТ n-1 = ЗНАЧЕНИЕ n-1 ТО АТРИБУТ n = ЗНАЧЕНИЕ n Пример правила из системы СВАЯ Если тип_схемы_напластования = 1 И грунт_слоя 1 = сжимаемый И грунт_слоя 2 = малосжимаемый ТОтип_сваи = свая-стойка.

Нечеткие данные - СЕЙСМО ЕСЛИ сейсмогенерирующий_слой_с_пониженным_сопротивлением = нет И аналог_данной_области = Фрунзенский_полигон ТО сейсмогенерирующий_слой_повышенной_трещиноватости = да ЕСЛИ сейсмогенерирующий_слой_с_пониженным_сопротивлением = нет И аналог_данной_области = Фрунзенский_полигон ТО сейсмогенерирующий_слой_повышенной_трещиноватости = да:0.2, нет:0.8 Как строится категория: морфизм: композиция:

Динамические данные - СЕЙСМО P – множество возможных контекстов. f p означает, что факт имеет место в контексте. Будем говорить, что, если. P – упорядоченное множество. Будем считать его решеткой. Тогда Примеры контекстных решеток: Подмножества множества с операциями,. Логические выражения с операциями, &. Вещественные числа с обычным порядком {0,1}

Динамические данные - СЕЙСМО От категории С можно перейти к категории. Здесь - категория с одним объектом, множеством эндоморфизмов которого выступает решетка P с операцией в качестве композиции. морфизм: композиция:

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

Реализация категории Образец Если (X), то (Y) Продукция Если (X), то (Y) УСЛОВИЕ: (X); ЗАКЛЮЧЕНИЕ: (Y) Функция factor Аргумент 1: Аргумент 2: Результат: (Если международным договором Российской Федерации установлены иные правила, чем те, которые предусмотрены гражданским законодательством, то применяются правила международного договора.) (если (X), то (Y)) ((X (международным договором Российской Федерации установлены иные правила, чем те, которые предусмотрены гражданским законодательством)) (Y (применяются правила международного договора.)))

П РОДУКЦИОННАЯ СЕТЬ Продукционная база 1 Продукционная база 2 Продукционная база 3 Наборы продукций

Продукционная сеть - пример (x в_случае.doc) (y) (u разделитель_если_то.doc) (v) УСЛОВИЕ: (x) (y); ЗАКЛЮЧЕНИЕ: (u) (v) в случае при условии … (x глагол_нвр_3 л.doc) … в_случае.doc разделитель_если_то.doc

Разбор отдельных слов \WORDS (w) ю т (w) у т (w) а т (w) и т \PATTERN (w) е т \EXCEPT л е т \ENDPATTERN … глагол_нвр_3 л.doc

Выводы Дано концептуальное описание продукции как элемента систем представления знаний в искусственном интеллекте. Работа такой продукции состоит из двух последовательных шагов: сопоставления и конкретизации. Подобным образом устроенные продукции описаны на языке теории категорий. Продукция на этом языке строится из морфизмов категории, а операции, связанные с продукциями, представляют собой операции над морфизмами, основная из которых – определение одного из морфизмов в равенстве φψ=σ, если известны два других. Предложена технология построения продукционных систем, разделяющую реализацию категории и создание алгоритмов работы с продукциями. Речь идет не только о стандартных механизмах вывода, но и о более сложных алгоритмах. На примерах реальных систем показано, как, меняя только категорию, можно менять тип и характер данных, с которыми работает система. Меняя же алгоритмы верхнего уровня, можно переходить к более сложным алгоритмам вывода, решающим задачи, трудно поддающиеся решению с помощью классических продукционных систем.