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

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

• • задание значений переменных, используемых в продукциях;
• • сами правила-продукции;
• • механизм интерпретации правил.

Значения переменных обычно задаются в так называемой рабочей базе данных (РБД) рабочей памяти — в виде набора конкретных фактов, формат которых согласуется с форматом правил. Совокупность правил-продукций является сердцем системы и называется базой знаний или правил (БЗ/БП). Механизм интерпретации правил как раз и является механизмом вывода (МВ).

Рассмотрим механизм вывода в продукционной системе.

Как следует из сказанного, под продукционной системой (ПС) понимается совокупность В каждом цикле интерпретации выполняются следующие процессы:

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

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

РБД — наборы фактов, описывающих текущие состояния предметной области;

БЗ — модель предметной области;

МВ — модель механизма принятия решений (вывода) — прямой аналог человеческим рассуждениям.

Таким образом, обобщенный алгоритм работы ПС состоит:

• • из задания модели текущего состояния предметной области (прямой диалог, моделирование, генерация, интерполяция и т. д.);
• • интерпретации текущего состояния предметной области РБД на БЗ и выработки вариантов решения;
• • выбора варианта решения и выдачи его на выход системы для пользователя;
• • изменения состояния модели предметной области — рабочей памяти — путем выполнения действий и процедур, рекомендованных в правых частях правил.

Самое замечательное в этом механизме то, что управление процессом вывода осуществляется путем изменения состояния РБД и не затрагивает БЗ.

Стратегии управления выводом решения это управляющий компонент ПС. Он определяет порядок применения правил и устанавливает, имеются ли еще факты в РБД, которые могут быть изменены для продолжения работы. Основных стратегий вывода — две: прямая — «ЛЧП —> ПЧП» (левая часть правила —> правая часть правила) и обратная (ПЧП —> ЛЧП).

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

Процесс управления состоит из выполнения четырех основных операций:

• 1) сопоставления (образец правила сопоставляется с имеющимися фактами в РБД);
• 2) выбора (если в конкретной ситуации могут быть применены сразу несколько правил, т. е. правила конфликтуют за возможность первого применения, то из них выбирается наиболее подходящее);
• 3) срабатывания (если образец правила при сопоставлении совпал с какими-либо фактами из РБД, то соответствующее правило срабатывает);
• 4) изменения состояния РБД на новое (РБД изменяется путем добавления в нее заключения сработавшего правила. Если в правой части содержится еще и указание на какие-либо действия, то они выполняются настолько, насколько это возможно).

Прямая стратегия «ЛЧП —> ПЧП» соответствует стратегии вывода «снизу-вверх» и осуществляется от ситуации к цели. Алгоритм вывода при этом следующий: 1) определяется ситуация, в которой выполняется условие в левой части (если), и делается логический вывод согласно констатирующей части (то); 2) полученный вывод понимается как условие, выполнение которого следует определить, но условной части другого правила и т. д.

Пример 4.1

Рыбак собирается на рыбалку. При этом он рассуждает по следующей схеме.

• 1. Если вода в реке поднимается, то рыба выходит на мель.
• 2. Если вода в реке опускается, то рыба уходит в глубину.
• 3. Если лето влажное, то вода в реке поднимается.
• 4. Если лето сухое, то вода в реке опускается.
• 5. Если рыба выходит на мель, то следует применять легкую блесну.
• 6. Если рыба уходит в глубину, то следует применять тяжелую блесну.

Лето выдалось влажное — какую блесну брать на рыбалку?

Мы будем решать эту задачу по алгоритму «снизу-вверх».

(1) В условной части заданных правил ищем условие, совпадающее с исходной ситуацией «лето влажное» (правило 3). Делаем вывод: «вода в реке поднимается». (2) Принимаем этот вывод как новое условие, следствие которого следует определить, и ищем соответствующее правило (правило 1). Делаем вывод: «рыба выходит на мель». (3) В условной части правил ищем совпадение для ситуации «рыба выходит на мель» (правило 5). Окончательный вывод: «блесну следует брать легкую».

Если представить отдельное правило в виде прямоугольника, темная часть которого означает условие, а светлая — заключение, то прямая стратегия отобразится в виде как на рис. 4.1.

Рис. 4.1. Стратегия «снизу-вверх» для приведенного примера

В общем случае правило удобно изображать в виде графа-дерева. Если оно имеет несколько условий (Р_г) и одно заключение (Л), то граф будет иметь вид как на рис. 4.2. Но правило может содержать и несколько заключений, и несколько действий.

Рис. 4.2. Структура правила

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

• • по условиям: P_i п Р_} = 0;
• • по заключениям: А_{ п А_} = А;
• • по действиям: D, n D_; = D и т. д.

С учетом возможных пересечений БЗ может быть представлена древовидной структурой типа И/ИЛИ-графа, которая очень хорошо показывает связи между результатами вывода по отдельным правилам (рис. 4.3). Дугой помечена связь типа «И».

Рис. 43. Древовидная структура И/ИЛИ-графа.

Вывод происходит «снизу-вверх» от состояния к цели. В случае подтверждений условий фактами БД осуществляется подъем к некоторому заключению, которое является условием (вместе с заключениями по другим правилам) для получения другого заключения — более высокого уровня. В случае альтернативного развития вывода («ИЛИ») выполняется генерация конфликтного набора правил и его разрешение с помощью метаправил, а затем происходит «подъем» далее. Данная стратегия вывода называется прямой, или стратегией «от состояния к цели». Могут быть варианты этой стратегии:

• а) возвратная, когда возврат осуществляется к первому правилу, т. е. одна и та же продукция применяется до тех пор, пока это требуется;
• б) безвозвратная, когда каждая продукция применяется один раз.

Вторая стратегия вывода — обратная — «сверху-вниз» (или от цели

к состоянию). Обратный вывод аналогичен прямому, но возникают дополнительные проблемы ограничения конфликтных наборов правил и выбора алгоритма разрешения конфликтов. Есть и другие проблемы, например, оценки условий в условной части. Все они решаются по-разному в рамках соответствующих инструментальных систем продукционного типа.

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

Пример 4.2

Допустим, что в базе знаний имеются правила: П1 * AaBaC^D,.

112 DaF^G,.

ПЗ AaJ^G,.

П4 В -> С,.

П5 Е->Я, П6 L -> /,.

П7 G -> Я.

Дано: А и F — истинны.

Доказать, что Я — истинно.

Алгоритм:

• 1. Ищем правило, где Я в правой части — П7.
• 2. Я будет истинным, если G — истинно; ищем продукцию, где G в правой части, их две — П2 и ПЗ. G, таким образом, будет истинным, если истинна хотя бы одна из конъюнкций в П2 и ПЗ. В П2: F= И по условию, но неясно Д в ПЗ: А = И по условию, неясно J.
• 3. Ищем продукцию, в которой D является целью. Это П1. Здесь А истинно, но условию, В и С неизвестны.
• 4. Из П5: В = Я, так как F= И по условию.
• 5. Из П4: так как В = Я, то и С = И.
• 6. Обратимся к П1. Все высказывания в левой части здесь истинны, следовательно, D — И.
• 7. Так как D = Я, то из П2: G = Я.
• 8. Из П7: Я = Я, что и требовалось доказать.

Теперь мы можем обобщить обе стратегии вывода на продукциях. В обоих случаях алгоритм начинается с сопоставления исходной ситуации: в первом случае — с условием (если), во втором — с целью (то). В результате могут быть активизированы сразу несколько правил (в нашем примере — 112 и ПЗ). Если образуется «конфликтное множество», то оно разрешается различными способами, но — по заданному критерию выбора. Выбранное правило выполняется, что позволяет осуществить необходимые действия (о действиях — ниже). Обобщенная стратегия показана на рис. 4.4.

Рис. 4.4. Стратегия управления выводом на продукциях

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

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