Прямой и обратный вывод

6.2. Прямой и обратный вывод в экспертных системах продукционного типа

Любая экспертная система продукционного типа должна со­держать три основные компоненты: базу правил, рабочую память и механизм вывода.

База правил (БП) — формализованные с помощью правил продукций знания о конкретной предметной области.

Рабочая память (РП) — область памяти, в которой хранится множество фактов, описывающих текущую ситуацию, и все пары атрибут-значение, которые были установлены к определенному моменту. Содержимое РП в процессе решения задачи изменяется обычно, увеличиваясь в объеме по мере применения правил. Другими словами, РП — это динамическая часть базы знаний, со­держимое которой зависит от окружения решаемой задачи. В простейших ЭС хранимые в РП факты не изменяются в процессе решения задачи, однако существуют системы, в которых допус­кается изменение и удаление фактов из РП. Это системы, работающие в условиях неполноты инфор­мации.

Механизм вывода выполняет две основные функции:

• просмотр существующих в рабочей памяти фактов и правил из БП, а также добавление в РП новых фактов;

• определение порядка просмотра и применения правил. По­рядок может быть прямым или обратным.

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

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

Рекомендуемые материалы

Для выполнения указанных функций механизм вывода вклю­чает компоненту вывода и управляющую компоненту.

Компонента вывода. Ее действие основано на применении правила логического вывода Modus Ponendo Ponens. Суть приме­нения этого правила в продукционных системах состоит в следу­ющем. Если в РП присутствует истинный факт А и в БП сущест­вует правило вида «ЕСЛИ А, ТО В», то факт В признается истин­ным и заносится в РП. Такой вывод легко реализуется на ЭВМ, однако при этом часто возникают проблемы, связанные с рас­познаванием значений слов, а также с тем, что факты могут иметь внутреннюю структуру и между элементами этой структу­ры возможны различного рода связи. Например, пусть имеется факт А — «Автомобиль Иванова - белый» и правило «ЕСЛИ Ав­томобиль — белый, ТО Автомобиль легко заметить ночью». Че­ловек легко выведет заключение «Автомобиль Иванова легко за­метить ночью», но это не под силу ЭС чисто продукционного ти­па. Она не сможет сформировать такое заключение, потому что А не совпадает точно с антецедентом правила. Подобная пробле­ма уже затрагивалась, когда рассматривались различия логики высказываний и логики предикатов. Кроме того, невысокая ин­теллектуальная мощность продукционных систем обусловлена тем, что человек выводит заключения, имея в своем распоряже­нии все свои знания, т.е. БЗ огромного объема, в то время как ЭС способны вывести сравнительно небольшое количество заклю­чений, используя заданное множество правил. Из сказанного можно сделать вывод о том, что компонента вывода в ЭС долж­на быть организована так, чтобы быть способной функциониро­вать в условиях недостатка информации.

Управляющая компонента. Она определяет порядок примене­ния правил, а также устанавливает, имеются ли еще факты, кото­рые могут быть изменены в случае продолжения работы. Механизм вывода работает циклически, при этом в одном цикле может сработать только одно правило. Схема цикла приведена на рис. 6.1. В цикле выполняются следу­ющие основные операции:

• сопоставление — образец (антецедент) правила сравнивает­ся с имеющимися в РП фактами;

• разрешение конфликтного набора — выбор одного из не­скольких правил в том случае, если их можно применить одно­временно;

• срабатывание правила — в случае совпадения образца неко­торого правила из базы правил с фактами, имеющимися в рабо­чей памяти, происходит срабатывание правила, при этом оно от­мечается в БП;

• действие — изменение содержимого РП путем добавления туда заключения сработавшего правила. Если в заключении со­держится директива на выполнение некоторой процедуры, по­следняя выполняется.

Рис. 6.1. Схема цикла работы механизма вывода

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

Особенностью ЭС является то, что они не располагают про­цедурами, которые могли бы построить в пространстве состоя­ний сразу весь путь решения задачи. Траектория поиска решения полностью определяется данными, получаемыми от пользовате­ля в процессе логического вывода.

Рассмотрим простейшие примеры прямого и обратного выво­да в системах продукционного типа.

Пример прямого вывода. Пусть в БП имеются следующие пра­вила:

Правило 1. «ЕСЛИ Двигатель не заводится И Фары не горят, ТО Сел аккумулятор».

Правило 2. «ЕСЛИ Указатель бензина находится на нуле, ТО Двигатель не заводится».

Предположим, что в рабочую память от пользователя ЭС поступили факты: Фары не горят и Указатель бензина находится на нуле.

Рассмотрим основные шаги алгоритма прямого вывода.

1. Сопоставление фактов из РП с образцами правил из БП. Правило 1 не может сработать, а Правило 2 срабатывает, так как образец, совпадающий с его антецедентом, присутствует в РП.

2. Действие сработавшего Правила 2. В РП заносится заклю­чение этого правила — образец «Двигатель не заводится».

3. Второй цикл сопоставления фактов в РП с образцами пра­вил. Теперь срабатывает Правило 1, так как конъюнкция условий в его антецеденте становится истинной.

4. Действие Правила 1, которое заключается в выдаче пользо­вателю окончательного диагноза — «Сел аккумулятор».

5. Конец работы (БП исчерпана).

Пример прямого вывода с конфликтным набором. Теперь допу­стим, что в БП кроме Правила 1 и Правила 2 присутствует Правило 3:

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

Пример обратного вывода. Предположим, что в БП имеется два правила (Правило 1 и Правило 2), а в РП — те же факты, что в предыдущих примерах с прямым выводом.

Алгоритм обратного вывода содержит следующие шаги.

1. Выдвигается гипотеза окончательного диагноза — «Сел аккумулятор».

2. Отыскивается правило, заключение которого соответствует выдвинутой гипотезе, в нашем примере — это Правило 1.

3. Исследуется возможность применения Правила 1, т.е. ре­шается вопрос о том, может ли оно сработать. Для этого в рабо­чей памяти должны присутствовать факты, совпадающие с образ­цом этого правила. В рассматриваемом примере Правило 1 не может сработать из-за отсутствия в РП образца «Двигатель не заводится». Этот факт становится новой целью на следующем шаге вывода.

4. Поиск правила, заключение которого соответствует новой цели. Такое правило есть — Правило 2.

5. Исследуется возможность применения Правила 2 (сопос­тавление). Оно срабатывает, так как в РП присутствует факт, сов­падающий с его образцом.

6. Действие Правила 2, состоящее в занесении заключения «Двигатель не заводится» в РП.

7. Условная часть Правила 1 теперь подтверждена фактами, следовательно, оно срабатывает, и выдвинутая начальная гипо­теза подтверждается.

8. Конец работы.

При сравнении этого примера с примером прямого вывода нельзя заметить преимуществ обратных выводов перед прямыми.

 Пример обратного вывода с конфликтным набором. Предполо­жим, что в БП записаны Правило 1, Правило 2, Правило 3 и Пра­вило 4:

«ЕСЛИ Засорился бензонасос, ТО Двигатель не заводится». В РП присутствуют те же самые факты: «Фары не горят» и «Ука­затель бензина находится на нуле».

В данном случае алгоритм обратного вывода с конфликтным набором включает следующие шаги.

1. Выдвигается гипотеза «Сел аккумулятор».

2. Поиск правила, заключение которого совпадает с постав­ленной целью. Это Правило 1.

3. Исследуется возможность применения Правила 1. Оно не может сработать, выдвигается новая подцель «Двигатель не заво­дится», соответствующая недостающему образцу.

4. Поиск правил, заключения которых совпадают с новой подцелью. Таких правил два — Правило 2 и Правило 4. Если вы­берем Правило 2, то дальнейшие шаги совпадают с примером без конфликтного набора. Если выберем Правило 4, то оно не срабо­тает, так как в РП нет образца «Засорился бензонасос». После этого будет применено Правило 2, что приведет к успеху, но путь ока­жется длиннее на один шаг.

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

В экспертных системах процедуры управления логическим выводом закрыты не только для пользователя, но и для инжене­ра по знаниям, однако о них необходимо иметь представление, чтобы корректно интерпретировать результаты. Для этого нужно знать, в каком виде хранятся знания и как выбираются началь­ная точка поиска, правила разрешения конфликтов, структуру, с помощью которой хранятся знания. Например, в известном се­мействе ЭС OPS применяется стратегия прямых выводов, эф­фективность которых существенно повышается благодаря ис­пользованию алгоритма согласования RЕТЕ при генерации кон­фликтного набора. Суть этого алгоритма сводится к следующе­му: каждый раз при добавлении в РП нового образца проверяет­ся правило, в котором он используется, и если образец удовле­творяет антецеденту некоторого правила, то он запоминается именно в этом качестве. В конфликтный набор правило включа­ется только в том случае, если добавление образца удовлетворя­ет всем условиям. Для разрешения конфликтов в системах се­мейства OPS, а также в других системах с прямыми выводами широкое распространение получил метод разрешения конфлик­тов LЕХ, в котором предпочтение отдается правилам со ссылкой на самый последний сгенерированный образец. Если таких пра­вил несколько, то среди них выбирается правило с наибольшим числом условий в антецеденте.

В больших ЭС продукционного типа все множество знаний обычно хранится в виде древовидной структуры, называемой И-ИЛИ-графом. Фрагменты такой структуры приведены на рис. 6.2 и 6.3. Классическая форма продукций предполагает наличие в антецеденте только связки И. На практике классическая форма может быть расширена, например, введением связки ИЛИ в ус­ловную часть либо включением в антецедент вычислений на ос­новании содержимого рабочей памяти и т.п. Если существует множество правил, из которых выводится одно и то же заключение, то, выполнив операцию дизъюнкции над всеми заключени­ями, полученными с помощью этих правил, можно показать от­ношение между результатом отдельного вывода и данными, на основании которых делается вывод.

Рис. 6.2. Простейший фрагмент структуры И-ИЛИ-графа

Рис. 6.3. Фрагмент структуры И-ИЛИ-графа продукционной ЭС

С помощью И-ИЛИ-графа обратный вывод в ЭС продукци­онного типа можно представить как проблему поиска определен­ного пути на графе. Выбор одной из связок ИЛИ соответствует разрешению конфликтного набора, при этом не безразличен по­рядок оценки условий в антецеденте, соединенных связкой И. Однако следует остановиться на способах повышения эффектив­ности поиска, так как в системах, имеющих практическую цен­ность, насчитываются сотни правил, и следует знать, с помощью каких стратегий управления выводом можно минимизировать время решения задач.

Стратегия поиска в глубину. При выборе очередной подцели в процессе обратного вывода предпочтение всегда, когда возмож­но, отдается той, которая соответствует следующему, более де­тальному уровню описания задачи. Например, система диагнос­тики, сделав на основании известных симптомов (фактов) предположение о причинах неисправности, будет запрашивать уточняющие при­знаки и симптомы (факты) до тех пор, пока полностью не подтвердит (оп­ровергнет) выдвинутую гипотезу. Пример организации поиска в глубину показан на рис. 6.4, где цифрами обозначены номера ша­гов поиска.

Стратегия поиска в ширину. При поиске в ширину сначала анализируются все симптомы (факты), находящиеся на одном уровне пространства состояний задачи, даже если они относятся к разным целям (подцелям), и только после этого происходит пе­реход к поиску симптомов следующего уровня. На рис. 6.5 пока­заны шаги поиска в ширину, обозначенные номерами, указанны­ми в вершинах. На рисунке представлена стратегия обратного вывода на том же И-ИЛИ-графе, который приведен и на рис. 6.4. Алгоритм поиска в глубину более эффективен в отношении вре­мени поиска и обработки знаний, однако он характеризуется бо­лее высоким риском потери перспективных решений по сравне­нию с поиском в ширину.

Люди также интересуются этой лекцией: 1.3. Микроорганизмы трансформирующие органические соединения.

Рис. 6.4. Поиск в глубину при обратном выводе

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

a-b-алгоритм. С помощью этого алгоритма исходная задача сводится к уменьшению пространства состояний путем удале­ния в нем ветвей, неперспективных для поиска успешного решения, т.е. просматриваются только те вершины, в которые
можно попасть в результате следующего шага, после чего непер­спективные направления исключаются. Например, в БЗ про­дукционной системы, заполненной знаниями о животном мире, не следует искать животных, не относящихся к млекопитающих, в направлении, берущем начало от вершины, определяю­щей млекопитающих. Данная стратегия является определенным компромиссом между поиском в ширину и поиском в глубину.

Рис. 6.5. Поиск в ширину при обратном выводе

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