3.2. Логические системы на продукциях

Логические системы на продукциях (сиcтемы продукций) исторически связаны продукционным формализмом Поста [14]. Однако практические реализации систем продукций используют менее стройную формальную систему, достаточно просто реализуемую на эВМ. Это позволило создать относительно простые и популярные экспертные системы на продукциях с неопределенностями вероятностного и нечеткого типа.

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

(n _i ) Q; P; A  B; N,

где (n_i ) - имя продукции ; Q -предметная область; P и N -пред- и постусловие выполнения продукции ; А В – ядро продукции в импликативной логической форме “Если А, то в".

35

П р и м е р: "(покупка); экономика; наличие денег;

Если цель - покупка вещи, то действие - заплати деньги;

вычти деньги из наличности".

З нания в форме продукций в системах продукций в общем случае представляют из себя структурированную БЗ, состоящую из связанных локальных БЗ, составленных из БД и БП (рис.3.1). Каждая локальная БЗ имеет идентификатор (n₁, n₂₁, n₂₂, …) и указатели связности (с₁₁, с₂₁, …), которые необходимы для фиксации структуры БЗ. МВ обеспечивает получение результата по целевому запросу путем реализации соответствующей процедуры вывода (поиска) в локальных БД и БП. Область применения Q обычно определяется для всей БЗ или локальных БЗ. Пред- и постусловия Р и N могут быть установлены для каждой продукции.

БД в системе продукций содержат набор известных фактов F_i, i = 1,…, n в форме: триплетов "объект - атрибут - значение" ("жажда - температура - 40⁰"); арифметических выражений (а = в + с); логических выражений (а > 0).

БП состоят из набора правил – ядер продукций – в форме

(F_k1  F_k2 V F_k3 V…  F_kn)  F_a1,

36

где F_ki - факты- условия (консеквенты), агрегатированные связками  и V ("и" и "или"); F_a1 - факт-заключения (акеседент) один на правило;  - отношение импликации (Если - то).

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

МВ содержит набор процедур для принятия решений в случае решения конкретной задачи по целевому запросу путем логического вывода по схеме (см. рис. 3.1) - для любой локальной БЗ:

просматривается БД и, если целевой факт F_g содержится в БД (сопоставление), результат вывода положительный, т.е. следует выполнение правила и действие, а, если F_g нет в БД, ведется поиск этого факта в консенвентах или акцедентах правил из БП;

при нахождении F_g в консенвентах правил путем сопоставления производится поиск в БД недостающих в правилах известных фактов – консенвентов и в качестве результата выбирается факт-акседент того правила, у которого оказываются известными все факты-консенвенты условий части правила (прямой поиск);

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

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

Системы продукций различаются по типу в зависимости от доступности фактов в БЗ: детерминированные и недетерминированные с неопределенностями в форме неточностей, вероятностей и коэффициентов уверенности. Соответственно МВ должны иметь разные процедуры вывода: непосредственно определяющие результат в виде фактов и вычисляющие оценки достоверности результирующих фактов: степени принадлежности, вероятности, коэффициенты уверенности.

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

37

многозначными (альтернативными).

П р и м е р: (F_k1  F_k2)  F_a – однозначное детерминированное правило;

(F₁  F_k2)  F_a1 , но реже F_a2 – многозначное детерминированное правило.

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

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

П р и м е р: Если "объект = паровой котел" и

"атрибут = температура пара и

"значение = 120 градусов" (F_k)

то "объект = заслонка" и

"атрибут=открытие заслонки"

"значение=на угол 40 градусов" (F_а)

П р и м е р: Если "объект = паровой котел"

Т  120 ⁰+t_п (F_k)

то "объект = заслонка"

d₃ = d₃ +20⁰ (F_a)

Для работы с правилами, приведенными в примере 2, можно использовать простой интерпретатор, сопоставляющий символьные значения компонентов F_k и F_a , а для правила из примера 3 требуется интерпретатор, способный вычислять арифметические и логические выражения. Последнее реализуется намного сложнее.

Рассмотрим подробно процедуры прямого и обратного вывода, кратко описанные ранее и являющиеся основными при поиске решения с помощью МВ и БЗ.

Прямой вывод. Пусть имеется БД с известными фактами: А, В, С, F, G, H и БП с правилами: F  B  Z; C  D  F; A  D. Задача вывода - определить существование Z в БЗ, т.е. вывести Z из известных фактов БД и правил БП.

На рис. 3.2 рассмотрена схема, соответствующая прямому выводу.

Здесь в БП содержатся три правила, а в БД перед выводом – известные факты (истинные): A, F, G, C, H, B. Пусть задача состоит в определении истинности факта Z. При прямом выводе МВ всегда начинает с первого правила:

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

38

факт из правой части (заключение) как известный (+D);

в торой раз просматривает оставшиеся правила, находит второе правило с известной левой частью, выполняет его и добавляет в БД факт F;

третий раз просматривает БП и выполняет первое правило, добавляя в БД факт Z;

делает вывод о том, что Z истинен, так как он появился в БД.

Обратный вывод. Для иллюстрации обратного вывода на рис. 3.3 приведена схема вывода для БП с четырьмя правилами. При этом задача ставится такая же: доказать истинность факта Z.

При обратном выводе МВ исходит из правила с целевым фактом Z в правой части:

39

найдя правило с Z в правой части (первое правило), проверяет его выполнимость: правило невыполнимо, так как неизвестен факт F;

считая F новой целью, находит правило с F в правой части (второе правило) и проверяет его выполнимость: правило невыполнимо, так как неизвестен факт D;

считая D новой целью, находит правило с D в правой части (третье правило) и проверяет его на выполнимость: правило выполняется, так как факт А известен;

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

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

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

2. В системах с малыми БП (100 - 300 правил) прямой вывод, как правило, предпочтительнее, так как. просмотр такой БП и вывод возможны в реальном времени.

3. В системах с большими БП (>300 правил) более эффективен обратный вывод, так как выделенная группа правил, как правило, не бывает большой (<10 - 20 правил), а остальные правила в выводе не участвуют.

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