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

П РОДУКЦИИ В ИСКУССТВЕННОМ ИНТЕЛЛЕКТЕ Продуция = + Для каждого правила имеется предварительное условие. Если предварительное условие выполняется, то правило может быть применено. Применение правила изменяет базу данных. Н. Нильсон В состав каждого правила входит некоторое условие. Правило может быть применено, если условие выполнено. Применение правила изменяет состояние рабочей памяти. Г. С. Осипов Продукцию можно представлять себе состоящей из двух частей: условия применимости и указания на то, как следует преобразовать текущую ситуацию. В. Л. Стефанюк Продукционная модель или модель, основанная на правилах, позволяет представить знания в виде предложений типа «Если (условие) то (действие)» Т.А. Гаврилова, В.Ф. Хорошевский

П РОДУКЦИИ В ИСКУССТВЕННОМ ИНТЕЛЛЕКТЕ В общем виде под продукцией понимается выражение вида: ( i ); Q ; Р ; А => В ; N. Здесь i имя продукции… Элемент Q характеризует сферу применения продукции… Основным элементом продукции является ее ядро: А=>В. А описывает некоторое условие, необходимое для того, чтобы можно было совершить действие В. Варианты: ЕСЛИ A, ТО В9670 ЕСЛИ A, ТО В1 ИНАЧЕ В2 Элемент Р есть условие применимости ядра продукции… Элемент N описывает постусловия продукции… Они описывают действия и процедуры, которые необходимо выполнить после реализации В. Д.А.Поспелов

Е ЩЕ ПРОДУКЦИИ Продукция Э.Поста и А.А.Маркова: ab ba Продукции Н.Хомского: S NP Aux VP VP Verb NP Правило языка Пролог: sibling(A,B) :-father(X,A),father(X,B)

С УТЬ ПОНЯТИЯ ПРОДУКЦИИ Продукция состоит из описания двух ситуаций. Левая часть продукции – описание ситуации, в которой продукция применима Правая часть продукции – описание ситуации, которая возникает поле ее применения

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

О ПРЕДЕЛЕНИЕ ПРОДУКЦИИ – СЛЕДУЮЩИЙ ШАГ Продукция представляет собой пару образцов (левая и правая часть продукции). Продукция применима к ситуации, если эта ситуация сопоставима с левой частью этой продукции. Результат применения продукции – ситуация, являющаяся результатом конкретизации правой части продукции, причем правая часть должна быть конкретизирована таким же образом, каким была конкретизирована левая часть в процессе сопоставления с ситуацией.

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

М ОЖЕТ БЫТЬ МНОГО РАЗНЫХ МНОЖЕСТВ СИТУАЦИЙ / КОНКРЕТИЗАТОРОВ S NP Aux VP VP Verb NP ϕ ψ

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

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

Э КСТЕНСИОНАЛЬНОЕ VS ИНТЕНСИОНАЛЬНОЕ S -образец ϕ: X S является частным случаем S -образца ψ: Y S Экстенсиональное определение Всякая ситуация, сопоставимая с образцом ϕ, сопоставима также с образцом ψ Итенсиональное определение Существует морфизм : X Y такой, что диаграмма коммутативна S XY ϕ ψ

Э КСТЕНСИОНАЛЬНОЕ VS ИНТЕНСИОНАЛЬНОЕ Продукция S X T является частным случаем продукции S Y T Экстенсиональное Если продукция ( ϕ,σ) преобразует ситуацию α в ситуацию β, то и продукция (ψ,τ) преобразует α в β Итенсиональное Существует морфизм : X Y такой, что диаграмма коммутативна S X Y ϕ ψ ϕ ψ σ τ T σ τ

Э КСТЕНСИОНАЛЬНОЕ VS ИНТЕНСИОНАЛЬНОЕ Композиция продукций Экстенсиональное Композиция двух продукций преобразует ситуацию α в ситуацию β, если существует ситуация δ такая, что первая продукция преобразует α в δ, а вторая преобразует δ в β. Итенсиональное Композиция продукций и это продукция, где - декартов квадрат

П ОРЯДОК НА МНОЖЕСТВЕ ОБРАЗЦОВ S X Y ϕ ψ

Н АИМЕНЬШЕЕ ОБОБЩЕНИЕ σ: Z S - наименьшее обобщение ϕ : X S и ψ: Y S : S X Y Z ϕ ψ λμ σ S X Y Z' ϕ ψ λ'λ'μ'μ' σ'σ' ZX τ λ'λ' λ YZ μ μ'μ'τ

Н АИМЕНЬШЕЕ ОБОБЩЕНИЕ σ: Z S - наименьшее обобщение ϕ : X S и ψ: Y S : S X Y Z ϕ ψ λμ σ S X Y Z' ϕ ψ λ'λ'μ'μ' σ'σ' S Z σ σ'σ' τ

Н АИБОЛЬШИЙ ЧАСТНЫЙ СЛУЧАЙ S X Y Z ϕ ψ λμ σ S X Y Z' ϕ ψ λ'λ'μ'μ' σ'σ' S Z σ: Z S – наибольший частный случай ϕ : X S и ψ: Y S : σ σ'σ' τ

П ОЧЕМУ КАТЕГОРИИ Частично упорядоченное множество Категория

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

- КАТЕГОРИЯ ( F,η,μ) - монада в категории Set, X – счетное множество (переменных), ( U – конечное подмножество X ). Для определим : для любого Категория : объекты – множества вида, морфизмы – отображения вида.

П РИМЕРЫ - КАТЕГОРИЙ Одна бинарная операция – умножение Одно тождество: x ( yz )=( xy ) z (ассоциативность) Образец: AxB Конкретизация: x CD, AxB ACDB S NP Aux VP VP Verb NP

П РИМЕРЫ - КАТЕГОРИЙ Одна бинарная операция – умножение Тождества: x ( yz )=( xy ) z (ассоциативность) xy = yx (коммутативность) x 2 =x (идемпотентность) Образец: { A,B,x } Конкретизация: x { C,D }, { A,B,x } { A,B,C,D }

П РИМЕРЫ - КАТЕГОРИЙ Произвольный набор операций – f, g, h,… Тождеств нет Образец: f ( A, g ( x), B ) Конкретизация: x h ( C,D), f ( A, g ( x), B ) f ( A, g ( h ( C,D)), B )

П РОДУКЦИОННАЯ СЕТЬ Продукционная база из S в T : ( S, T, P ) S, T – объекты, P – множество продукций из S в T. Продукция: ( ϕ,ψ,P ) ϕ : X S, ψ: Y T – морфизмы, P – продукционная база из X в Y ϕ ψ P S NP Aux VP VP Verb NP X S T Y

Р АЗЛОЖЕНИЕ В ПРОИЗВЕДЕНИЕ n-барный образец: морфизм ϕ:X 1 xX 2 x…xX nS Продукция: ( ϕ,ψ,(P 1,P 2,…P n ) ) ϕ:X 1 xX 2 x…xX nS, ψ :Y 1 xY 2 x…xY nS - n-барные образцы, P i - продукционная база из X i в Y i ϕ ψ x x

С ЛУЧАЙ - КАТЕГОРИЙ Если, то

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

В ЫВОДЫ Построенная математическая теория продукционных систем позволяет : определять математические понятия, описывающие объекты и действия над ними и изучать их свойства; строить алгоритмы функционирования продукционной системы; изучать продукционные системы специального вида с дополнительными свойствами; развивать системы поддержки программирования продукционных систем - все это в форме, не зависящей от данных, с которыми работает система.

Спасибо за внимание