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

Август 23, 2022

Главная
Информатика
Продукционные системы

Содержание

2. Нотация процедур в виде последовательности правил (предложена математиком Постом) Правило продукции - правило вида ЕСЛИ ТО
3. Пример Определение максимума и минимума из некоторого набора чисел с использованием продукционной системы, чтобы проиллюстрировать разницу
4. Порядок следования правил существенен ПРОДУКЦИОННАЯ СИСТЕМА Рабочая область: А(1) = 4; А(2) = 7; ... ;
5. Порядок следования правил несущественен ПРОДУКЦИОННАЯ СИСТЕМА Рабочая область: А(1) = 4; А(2) = 7; ... ;
6. Если так тщательно определять правила, то можно вводить новые функции в программу просто путем добавления соответствующих
7. Другой вариант управляющей структуры, которая не подходит для данного решения Управляющая структура: Поочередно пробовать все правила,
8. Общий вид продукционного правила (i); Q; P; A⇒ B; N A⇒ B - ядро продукции (основной
9. Как это работает Рабочая память (working memory) содержит описание текущего состояния мира в процессе рассуждений. Это
10. Прямой вывод Правило 1 ЕСЛИ Вася имеет шерсть и Вася ест мясо, ТО Вася - кот.
11. Обратный вывод Способ, при котором на основании фактов, требующих подтверждения, чтобы выступить в роди заключения, исследуется
12. Конфликтный набор Пусть имеется еще одно правило: Правило 3 ЕСЛИ Вася имеет шерсть, ТО Вася -
13. Классификация ядер продукций
14. Недетерминированные ядра Возможность может определяться некоторыми оценками реализации ядра. Например, ЕСЛИ А, ТО с вероятностью р
16. Другая классификация ядер
17. Ах ⇒ Ву будет означать, что информация об А берется из блока х, а результат срабатывания
18. ПРИМЕР1 1) АБЗ ⇒ ВБЗ. В этом случае А и В - некоторые фрагменты информации из
19. Иллюстрация поиска по образцу в базе знаний Фрагмент семантической сети: Продукция:
20. АБД ⇒ ВБЗ Может соответствовать процедуре нахождения закономерностей по эмпирическим данным Логический блок на основании просмотра
21. Управление системой продукций Проблема: какая из продукций должна быть активизирована? Этим вопросом и должно заниматься система
22. Стратегии управления продукционной системой Принцип «стопки книг» Особенно хорош, когда частота использования подсчитывалась с учетом некоторой
23. Стратегии управления продукционной системой Принцип наиболее длинного условия Целесообразно применять в тех случаях, когда знания и
24. KSj - knowledge source
25. HEARSAY-II KS1 - Форма волны (временная диаграмма) акустического сигнала KS2 - Фонемы или возможные звуковые сегменты
26. Стратегии управления продукционной системой Принцип приоритетного выбора Этот принцип связан с введением статических и динамических приоритетов
27. Стратегии управления продукционной системой Управление по именам Пусть СП - простейшая, состоит только из ядер. (1)
28. Факторы популярности продукционных моделей Подавляющая часть человеческих знаний может быть записана в виде СП. Разделение знания
30. Скачать презентацию

Слайд 2

Нотация процедур в виде последовательности правил (предложена математиком Постом)
Правило продукции -

правило вида
ЕСЛИ < условие> ТО <действие>
Продукционная система состоит из 3-х элементов:
классов и отношений (рабочей области);
правил;
управляющей структуры
Классы и отношения трактуются как «база данных», которая, по существу, содержит декларативные знания. В некоторых ИС используются комбинации сетевых и продукционных моделей. В них декларативные знания описываются в сетевой части, а процедурные - в продукционной
Набор правил:
ЕСЛИ < условие> ТО <действие>
Управляющая структура определяет какое правило будет проверено следующим. Часто управляющую структуру называют интерпретатором правил, а базу данных - рабочей памятью. Имеет очень важное значение
<Условие> - это проверка состояния базы данных, а <действие> некоторым образом видоизменяет содержимое базы данных.

Слайд 3

Пример
Определение максимума и минимума из некоторого набора чисел с использованием продукционной

системы, чтобы проиллюстрировать разницу в подходах. Рабочая область содержит числа от А(1) до А(10); N - количество рассматриваемых элементов, I - текущее значение индекса проверяемого числа
2 варианта:
Порядок следования правил существенен.
Порядок следования правил несущественен.

Слайд 4

Порядок следования правил существенен
ПРОДУКЦИОННАЯ СИСТЕМА
Рабочая область:
А(1) = 4; А(2) = 7;

... ; А(10) = 21;
N = 10; I=1; MAX= А(1) ; MIN = А(1)
Правила:
IF I>N THEN writeln (MAX,MIN); STOP;
IF А(I) > MAX THEN MAX:= А(I);
IF А(I) < MIN THEN MIN:= А(I);
If i<=N then I:=I+1
Управляющая структура:
Поочередно пробовать правила до конца. Затем следовать к началу списка правил и повторить все заново. Закончить процесс, когда встретится оператор STOP. Правило срабатывает, если выполняется условие.

Слайд 5

Порядок следования правил несущественен
ПРОДУКЦИОННАЯ СИСТЕМА
Рабочая область:
А(1) = 4; А(2) = 7;

... ; А(10) = 21;
N = 10; I=1; MAX= А(1) ; MIN = А(1)
Правила:
IF (I ≤ N) & (А(I) > MAX) THEN MAX:= А(I);
IF (I ≤ N) & (А(I) < MIN) THEN MIN:= А(I);
IF I>N THEN writeln (MAX,MIN); STOP;
IF (I ≤ N) & (А(I) ≤ MAX) & (А(I) ≥ MIN) THEN I:=I+1
Управляющая структура:
Поочередно пробовать правила до конца. Затем следовать к началу списка правил и повторить все заново. Закончить процесс, когда встретится оператор STOP. Правило срабатывает, если выполняется условие.

Слайд 6

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

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

Слайд 7

Другой вариант управляющей структуры, которая не подходит для данного решения
Управляющая структура:
Поочередно

пробовать все правила, пока одно из них не сработает. Затем повторить процесс снова. Закончить, когда встретится оператор STOP.
Очень важно ПРАВИЛЬНО определять управляющую структуру!

Слайд 8

Общий вид продукционного правила
(i); Q; P; A⇒ B; N
A⇒ B -

ядро продукции (основной элемент продукции). Это правило ЕСЛИ А, ТО В.
Более сложные конструкции ядра допускают правила вида ЕСЛИ А, ТО В1, ИНАЧЕ В2.
При этом секвенция (⇒) может трактоваться в обычном смысле (логическом) как знак логического следования В из истинного А (если А - ложь, то о В ничего сказать нельзя).
Возможны и другие интерпретации ядра, например, А описывает некоторое условие, необходимое для совершения В.
i - имя продукции, с помощью которого данная продукция выделяется из всего множества продукций. Это может быть просто порядковый номер или лексема, отражающая суть продукции, например, «ПОКУПКА АВТОМОБИЛЯ», «ПЛАНЫ НА ВЕЧЕР» и т.д.
Q - характеризует сферу применения продукции. Разделение знаний на сферы применения позволяет эффективно организовать поиск нужных знаний.
P - условие применимости ядра продукции . Обычно это логическое выражение или предикат. Если Р - истина, то ядро продукции активизируется, иначе оно нее может быть использовано.
Пример: Р – «НАЛИЧИЕ ДЕНЕГ»; если хочешь купить вещь Х, то заплати за нее в кассу и отдай чек продавцу.
N - постусловия продукции. Могут активизироваться лишь при реализации ядра. Постусловия описывают действия и процедуры, которые необходимо выполнить после реализации В.
Например, после покупки вещи в магазине уменьшить количество вещей такого типа на 1.

Слайд 9

Как это работает
Рабочая память (working memory) содержит описание текущего состояния мира

в процессе рассуждений. Это описание является образцом, который сопоставляется с условной частью продукции с целью выбора соответствующих действий при решении задачи. Если условие некоторого правила соответствует содержимому рабочей памяти, то может выполняться действие, связанное с этим условием. Действия продукционных правил предназначены для изменения содержимого рабочей памяти.
Управляющая структура продукционной системы: рабочая память инициализируется начальным состоянием задачи. Текущее состояние представляется набором образцов в рабочей памяти. Эти образцы сопоставляются с условиями продукционных правил, что порождает подмножество правил вывода, называемое конфликтным набором (conflict set). Продукции, содержащиеся в конфликтном наборе, называют допустимыми. Возникает проблема разрешения конфликта (conflict resolution).
Активизация правила означает выполнение его действия. При этом изменяется содержимое рабочей памяти. После того как правило сработало, цикл управления повторяется для модифицированной рабочей памяти. Процесс заканчивается, если содержимое рабочей памяти не соответствует никаким условиям.

Слайд 10

Прямой вывод
Правило 1 ЕСЛИ Вася имеет шерсть
и
Вася ест мясо,
ТО Вася - кот.
Правило

2 ЕСЛИ Вася - хищник,
ТО Вася ест мясо.
В рабочую область заносится «Вася имеет шерсть» и «Вася – хищник». Рассматривается возможность применения представленных выше правил.
Сначала механизм вывода сопоставляет образцы из условной части правил с образцами, хранимыми в рабочей памяти. Если образец присутствует в рабочей области, то условная часть истинна. Для правила 1 она - ложь, а для правила 2- истина. Следовательно, образец «Вася ест мясо» заносится в рабочую область. При попытке вторично применить правила 2 выбывает, потому что уже использовалось, Правило1 даст истинный результат, поскольку теперь в БД присутствует нужный образец. Вывод - Вася - кот. Останов из-за отсутствия правил.

Слайд 11

Обратный вывод
Способ, при котором на основании фактов, требующих подтверждения, чтобы выступить

в роди заключения, исследуется возможность применения правила, пригодного для подтверждения, называется ОБРАТНЫМ выводом.
Пусть цель - это то, что «Вася – кот».
Можно ли использовать Правило1, чтобы подтвердить этот факт?
«Вася имеет шерсть» существует в рабочей области, следовательно, достаточно подтвердить тот факт, что «Вася ест мясо». Но если «Вася ест мясо» – новая цель, то ее тоже надо подтвердить правилом. Исследуется возможность применения Правила 2. Условная часть правила на данный момент истинна, следовательно, подтверждение получено.
В случае обратного вывода условием останова является либо достижение первоначальной цели, либо то, что правил больше нет.

Слайд 12

Конфликтный набор
Пусть имеется еще одно правило:
Правило 3 ЕСЛИ Вася имеет шерсть,
ТО Вася -

млекопитающее
Условие останова – «Вася – кот»
Выбор применяемого правила оказывает прямое влияние на эффективность работы системы:и если применить П3, то нужен дополнительный вывод.
В реальной продукционной системе это грандиозная проблема. Если на каждом этапе логического вывода существует множество применимых правил, то оно носит название КОНФЛИКТНОГО НАБОРА, а выбор одного из них называется разрешением конфликта.
Эта же проблема характерна и для обратного вывода.
Правило 4 ЕСЛИ Вася принадлежит семейству кошачьих,
ТО Вася ест мясо.
Цель - «Вася – кот»
Чтобы подтвердить, что «Вася ест мясо», надо попробовать правила 2 или 4.
Если сразу обратиться к Правилу 2, то это удачный выбор, так как сразу можно исследовать Правило1 и подтвердить цель.
Если сначала обратиться к Правилу 4, то в рабочей области отсутствует образец «Вася принадлежит семейству кошачьих» и не существует правила его подтверждающего. Следовательно, выбор неудачен. Только со второго захода через Правило 2 можно подтвердить цель «Вася ест мясо».

Слайд 13

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

Слайд 14

Недетерминированные ядра
Возможность может определяться некоторыми оценками реализации ядра.
Например,
ЕСЛИ А,

ТО с вероятностью р РЕАЛИЗОВАТЬ В (прогнозирующие продукции)
Лингвистическая оценка реализации:
ЕСЛИ А, ТО с большей долей уверенности В.
Существуют и другие способы оценки реализации.

Слайд 15

Слайд 16

Другая классификация ядер

Слайд 17

Ах ⇒ Ву будет означать, что информация об А берется из блока

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

Слайд 18

ПРИМЕР1
1) АБЗ ⇒ ВБЗ.
В этом случае А и В - некоторые

фрагменты информации из БЗ. При сетевом представлении это могут быть фрагменты семантической сети, в случае логического представления - формулами того или иного исчисления.
При этом смысл АБЗ ⇒ ВБЗ заключается в замене одного фрагмента базы знаний другим.
Для активизации этой продукции необходимо, чтобы в базе знаний существовал фрагмент, совпадающий с А. А играет роль образца, мы имеем дело с процедурой поиска по образцу (pattern matching - сопоставление с образцом).

Слайд 19

Иллюстрация поиска по образцу в базе знаний
Фрагмент семантической сети:
Продукция:

Слайд 20

АБД ⇒ ВБЗ
Может соответствовать процедуре нахождения закономерностей по эмпирическим данным
Логический

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

Слайд 21

Управление системой продукций
Проблема: какая из продукций должна быть активизирована?
Этим вопросом и

должно заниматься система управления.
Если ИС реализована на ЭВМ с параллельной архитектурой, то из множества готовых продукций (фронта готовых продукций) может выбираться не одна продукция, а столько, сколько параллельных ветвей может выполнять ЭВМ. Но независимо от количества актуализированных продукций, проблема выбора остается.
2 пути решения задачи управления:
централизованный: решение об актуализации принимает специальная система управления;
децентрализованный: решение об актуализации продукции определяется складывающейся в этот момент ситуацией
Если порядок выполнения продукций важен, то в продукциях должна содержаться информация о требованиях к этому порядку. Если в постусловии продукции указывается имя той продукции, которая должна выполняться следующей, продукционная система превращается в обычную программу.

Слайд 22

Стратегии управления продукционной системой
Принцип «стопки книг»
Особенно хорош, когда частота использования подсчитывалась

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

Слайд 23

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

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

Слайд 24

KSj -
knowledge source

Слайд 25

HEARSAY-II
KS1 - Форма волны (временная диаграмма) акустического сигнала
KS2 - Фонемы

или возможные звуковые сегменты акустического сигнала
KS3 - Слоги, которые могут быть составлены из фонем
KS4 - Возможные слова, результат анализа первого KSi
KS5 - Возможные слова, результат анализа второго KSi - (обычно рассматриваются слова из различных частей данных)
KS6 - Генерация возможных последовательностей слов
KS7 - Связывание последовательности слов в фразы

Слайд 26

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

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

Слайд 27

Стратегии управления продукционной системой
Управление по именам
Пусть СП - простейшая, состоит только

из ядер.
(1) А ⇒ В;
(2) В & D ⇒ A
(3) A ∨ B ⇒ D
(4) D ⇒ C
Система продукций недетерминирована. Если выполняется А, то фронт готовых продукций включает продукции с именами (1) и (3), а если В и D, то (2), (3), (4).
Для устранения недетерминированности может быть введена грамматика для имен:
(1) ⇒ (2);
(2) ⇒ (2);
(3) ⇒ (4)
Тогда если в некоторый момент будет выполнена продукция с именем (2), то новые продукции выполняться не будут.
Если же выполнилась (1), то после нее смогут выполняться (2) и (4). Но левые части таковы, что неоднозначность возникает лишь тогда, когда В и D одновременно выполнимы. С помощью грамматики можно задать однозначный алгоритмический процесс.

Слайд 28

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

виде СП.
Разделение знания и управления. Преимущество такого разделения заключается в простоте изменения базы знаний, при котором не надо менять код программы управления. И, наоборот, можно менять код управляющей программы, не трогая набор правил вывода.
Управление на основе образцов (pattern-directed control). Правила в продукционной системе могут запускаться в любой последовательности. Описание задачи, представляющее текущее состояние мира, определяет конфликтное множество, и, следовательно, конкретный путь поиска и решения. Существуют возможности эвристического управления поиском.
СП являются модульными. За небольшим исключением, удаление или добавление продукций не приведет к изменениям в остальных продукциях. Между продукционными правилами отсутствует синтаксическое взаимодействие. Правила могут только влиять на активизацию других правил, изменяя образец в рабочей памяти. Правила не могут «вызывать» другие правила непосредственно, как подпрограммы. При этом они не могут устанавливать значения переменных в других продукционных правилах. Область действия переменных этих правил ограничена отдельным правилом. Эта синтаксическая независимость позволяет инкрементно разрабатывать экспертные системы путем последовательного добавления, удаления или изменения знаний (правил) системы.

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

Содержание

Нотация процедур в виде последовательности правил (предложена математиком Постом)Правило продукции -

ПримерОпределение максимума и минимума из некоторого набора чисел с использованием продукционной

Порядок следования правил существененПРОДУКЦИОННАЯ СИСТЕМАРабочая область:А(1) = 4; А(2) = 7;

Порядок следования правил несуществененПРОДУКЦИОННАЯ СИСТЕМАРабочая область:А(1) = 4; А(2) = 7;

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

Другой вариант управляющей структуры, которая не подходит для данного решенияУправляющая структура: Поочередно

Общий вид продукционного правила(i); Q; P; A⇒ B; NA⇒ B -

Как это работаетРабочая память (working memory) содержит описание текущего состояния мира

Прямой выводПравило 1 ЕСЛИ Вася имеет шерсть и Вася ест мясо, ТО Вася - кот.Правило

Обратный выводСпособ, при котором на основании фактов, требующих подтверждения, чтобы выступить

Конфликтный наборПусть имеется еще одно правило:Правило 3 ЕСЛИ Вася имеет шерсть, ТО Вася -

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

Недетерминированные ядраВозможность может определяться некоторыми оценками реализации ядра. Например, ЕСЛИ А,

Другая классификация ядер

Ах ⇒ Ву будет означать, что информация об А берется из блока

ПРИМЕР11) АБЗ ⇒ ВБЗ.В этом случае А и В - некоторые

Иллюстрация поиска по образцу в базе знаний Фрагмент семантической сети:Продукция:

АБД ⇒ ВБЗ Может соответствовать процедуре нахождения закономерностей по эмпирическим даннымЛогический

Управление системой продукцийПроблема: какая из продукций должна быть активизирована?Этим вопросом и

Стратегии управления продукционной системойПринцип «стопки книг» Особенно хорош, когда частота использования подсчитывалась

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

KSj - knowledge source

HEARSAY-II KS1 - Форма волны (временная диаграмма) акустического сигналаKS2 - Фонемы

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

Стратегии управления продукционной системойУправление по именам Пусть СП - простейшая, состоит только

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

Похожие презентации