<<
>>

2.3.2ПРЯМОЙ И ОБРАТНЫЙ ВЫВОДВ ЭКСПЕРТНЫХ СИСТЕМАХПРОДУКЦИОННОГО ТИПА

Любая экспертная система продукционного типа должна со­держать три основные компоненты: базу правил, рабочую память и механизм вывода.
88База правил (БП) — формализованные с помощью правил продукций знания о конкретной предметной области.
Рабочая память (РП) — область памяти, в которой хранится множество фактов, описывающих текущую ситуацию, и все пары атрибут-значение, которые были установлены к определенному моменту.
Содержимое РП в процессе решения задачи изменяется обычно, увеличиваясь в объеме по мере применения правил. Другими словами, РП - это динамическая часть базы знаний, со­держимое которой зависит от окружения решаемой задачи. В простейших ЭС хранимые в РП факты не изменяются в процессе решения задачи, однако существуют системы, в которых допус­кается изменение и удаление фактов из РП. Это системы с немо­нотонным выводом, работающие в условиях неполноты инфор­мации.
Механизм вывода выполняет две основные функции:
• просмотр существующих в рабочей памяти фактов и правил из БП, а также добавление в РП новых фактов;
• определение порядка просмотра и применения правил. По­ рядок может быть прямым или обратным.
Прямой порядок — от фактов к заключениям. В экспертных си­стемах с прямыми выводами по известным фактам отыскивается заключение, которое из этих фактов следует. Если такое заключе­ние удается найти, оно заносится в рабочую память. Прямые вы­воды часто применяются в системах диагностики, их называют выводами, управляемыми данными.
Обратный порядок вывода - от заключений к фактам. В систе­мах с обратным выводом вначале выдвигается некоторая гипоте­за о конечном суждении, а затем механизм вывода пытается най­ти в рабочей памяти факты, которые могли бы подтвердить или опровергнуть выдвинутую гипотезу. Процесс отыскания необхо­димых фактов может включать достаточно большое число шагов, при этом возможно выдвижение новых гипотез (целей). Обрат­ные выводы управляются целями.
Для выполнения указанных функций механизм вывода вклю­чает компоненту вывода и управляющую компоненту.
Компонента вывода. Ее действие основано на применении правила логического вывода Modus Ponendo Ponens. Суть приме­нения этого правила в продукционных системах состоит в следу­ющем. Если в РП присутствует истинный факт А и в БП сущест­вует правило вида «ЕСЛИ А, ТО B», то факт В признается истин­ным и заносится в РП. Такой вывод легко реализуется на ЭВМ,
89однако при этом часто возникают проблемы, связанные с рас­познаванием значений слов, а также с тем, что факты могут иметь внутреннюю структуру и между элементами этой структу­ры возможны различного рода связи. Например, пусть имеется факт А — «Автомобиль Иванова — белый» и правило «ЕСЛИ Ав­томобиль — белый, ТО Автомобиль легко заметить ночью». Че­ловек легко выведет заключение «Автомобиль Иванова легко за­метить ночью», но это не под силу ЭС чисто продукционного ти­па. Она не сможет сформировать такое заключение, потому что А не совпадает точно с антецедентом правила. Подобная пробле­ма уже затрагивалась, когда рассматривались различия логики высказываний и логики предикатов. Кроме того, невысокая ин­теллектуальная мощность продукционных систем обусловлена тем, что человек выводит заключения, имея в своем распоряже­нии все свои знания, т.е.
БЗ огромного объема, в то время как ЭС способны вывести сравнительно небольшое количество заклю­чений, используя заданное множество правил. Из сказанного можно сделать вывод о том, что компонента вывода в ЭС долж­на быть организована так, чтобы быть способной функциониро­вать в условиях недостатка информации.
Управляющая компонента. Она определяет порядок примене­ния правил, а также устанавливает, имеются ли еще факты, кото­рые могут быть изменены в случае продолжения работы (при не­монотонном выводе). Механизм вывода работает циклически, при этом в одном цикле может сработать только одно правило. Схема цикла приведена на рис. 2.3. В цикле выполняются следу­ющие основные операции:
• сопоставление — образец (антецедент) правила сравнивает­ ся с имеющимися в РП фактами;
• разрешение конфликтного набора — выбор одного из не­ скольких правил в том случае, если их можно применить одно­ временно;
• срабатывание правила — в случае совпадения образца неко­ торого правила из базы правил с фактами, имеющимися в рабо­ чей памяти, происходит срабатывание правила, при этом оно от­ мечается в БП;
• действие — изменение содержимого РП путем добавления туда заключения сработавшего правила. Если в заключении со­ держится директива на выполнение некоторой процедуры, по­ следняя выполняется.
Рис.2.3. Схема цикла работы механизма вывода
Поскольку механизм вывода работает циклически, следует знать о способах завершения цикла. Традиционными способами являются либо исчерпание всех правил из БП, либо выполнение некоторого условия, которому удовлетворяет содержимое рабо­чей памяти (например, появление в ней какого-то образца), либо комбинация этих способов.
Особенностью ЭС является то, что они не располагают про­цедурами, которые могли бы построить в пространстве состоя­ний сразу весь путь решения задачи. Траектория поиска решения полностью определяется данными, получаемыми от пользовате­ля в процессе логического вывода.
Рассмотрим простейшие примеры прямого и обратного выво­да в системах продукционного типа.
Пример прямого вывода. Пусть в БП имеются следующие пра­вила:
Правило 1. «ЕСЛИ Двигатель не заводится И Фары не горят, ТО Сел аккумулятор».
Правило 2. «ЕСЛИ Указатель бензина находится на нуле, ТО Двигатель не заводится».
Предположим, что в рабочую память от пользователя ЭС поступили факты: Фары не горят и Указатель бензина находится на нуле.
Рассмотрим основные шаги алгоритма прямого вывода.
1. Сопоставление фактов из РП с образцами правил из БП. Правило 1 не может сработать, а Правило 2 срабатывает, так как образец, совпадающий с его антецедентом, присутствует в РП. 90912. Действие сработавшего Правила 2. В РП заносится заклю­ чение этого правила — образец Двигатель не заводится.
3. Второй цикл сопоставления фактов в РП с образцами пра­ вил. Теперь срабатывает Правило 1, так как конъюнкция условий в его антецеденте становится истинной.
4. Действие Правила 1, которое заключается в выдаче пользо­ вателю окончательного диагноза — Сел аккумулятор.
5. Конец работы (БП исчерпана).
Пример прямого вывода с конфликтным набором. Теперь допу­стим, что в БП кроме Правила 1 и Правила 2 присутствует Пра­вило 3:
«ЕСЛИ Указатель бензина находится на нуле, ТО Нет бензина».
В РП находятся те же факты, что в предыдущем примере.
В результате сопоставления в первом же цикле возможно применение двух правил — Правила 2 и Правила 3, т.е. возникает конфликтный набор и встает задача выбора: какое из этих правил применить первым. Если выберем Правило 2, то в РП добавится факт Двигатель не заводится и на следующем шаге опять возник­нет конфликтный набор, так как можно будет применить Прави­ло 1 и Правило 3. Если будет выбрано Правило 1, то к заключе­нию Сел аккумулятор придем за два шага. При любом другом выборе порядка применения правил к этому же заключению при­ходим за три шага. Если завершение цикла работы ЭС наступает после просмотра всех правил, то число шагов будет равно трем, причем порядок применения правил не будет иметь какого-либо значения.
Пример обратного вывода. Предположим, что в БП имеется два правила (Правило 1 и Правило 2), а в РП — те же факты, что в предыдущих примерах с прямым выводом.
Алгоритм обратного вывода содержит следующие шаги.
1. Выдвигается гипотеза окончательного диагноза — Сел акку­ мулятор.
2. Отыскивается правило, заключение которого соответствует выдвинутой гипотезе, в нашем примере — это Правило 1.
3. Исследуется возможность применения Правила 1, т.е. ре­ шается вопрос о том, может ли оно сработать. Для этого в рабо­ чей памяти должны присутствовать факты, совпадающие с образ­ цом этого правила. В рассматриваемом примере Правило 1 не может сработать из-за отсутствия в РП образца Двигатель не заво­ дится. Этот факт становится новой целью на следующем шаге вывода.
92
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, не связан­ное с поставленной целью, вообще не затрагивалось в процессе вывода. Этот факт свидетельствует о более высокой эффективно­сти обратных выводов по сравнению с прямыми, так как при об­ратных выводах существует тенденция исключения из рассмотре­ния правил, не Имеющих отношения к поставленной цели.
93
Правило 1
Правило 2
Факты
Факты
Рис. 2.4. Простейший фрагмент структуры И-ИЛИ-графа
В экспертных системах процедуры управления логическим выводом закрыты не только для пользователя, но и для инжене­ра по знаниям, однако о них необходимо иметь представление, чтобы корректно интерпретировать результаты. Для этого нужно знать, в каком виде хранятся знания и как выбираются началь­ная точка поиска, правила разрешения конфликтов, структуру, с помощью которой хранятся знания. Например, в известном се­мействе ЭС OPS применяется стратегия прямых выводов, эф­фективность которых существенно повышается благодаря ис­пользованию алгоритма согласования RЕТЕ при генерации кон­фликтного набора. Суть этого алгоритма сводится к следующе­му: каждый раз при добавлении в РП нового образца проверяет­ся правило, в котором он используется, и если образец удовле­творяет антецеденту некоторого правила, то он запоминается именно в этом качестве. В конфликтный набор правило включа­ется только в том случае, если добавление образца удовлетворя­ет всем условиям. Для разрешения конфликтов в системах се­мейства OPS, а также в других системах с прямыми выводами широкое распространение получил метод разрешения конфлик­тов LEX, в котором предпочтение отдается правилам со ссылкой на самый последний сгенерированный образец. Если таких пра­вил несколько, то среди них выбирается правило с наибольшим числом условий в антецеденте.В больших ЭС продукционного типа все множество знаний обычно хранится в виде древовидной структуры, называемой И-ИЛИ-графом. Фрагменты такой структуры приведены на рис. 2.4 и 2.5. Классическая форма продукций предполагает наличие в антецеденте только связки И. На практике классическая форма может быть расширена, например, введением связки ИЛИ в ус­ловную часть либо включением в антецедент вычислений на ос­новании содержимого рабочей памяти и т.п. Если существует множество правил, из которых выводится одно и то же заключе-
Заключения

Основные системные данные
Рис. 2.5. Фрагмент структуры И-ИЛИ-графа продукционной экспертной системы 9495
Начало поиска
ние, то, выполнив операцию дизъюнкции над всеми заключени­ями, полученными с помощью этих правил, можно показать от­ношение между результатом отдельного вывода и данными, на основании которых делается вывод.
С помощью И-ИЛИ-графа обратный вывод в ЭС продукци­онного типа можно представить как проблему поиска определен­ного пути на графе. Выбор одной из связок ИЛИ соответствует разрешению конфликтного набора, при этом не безразличен по­рядок оценки условий в антецеденте, соединенных связкой И. Задачи и стратегии поиска на И-ИЛИ-фафах широко освещены в литературе [4, 5] и не будут рассматриваться здесь подробно. Однако следует остановиться на способах повышения эффектив­ности поиска, так как в системах, имеющих практическую цен­ность, насчитываются сотни правил, и следует знать, с помощью каких стратегий управления выводом можно минимизировать время решения задач.
Стратегия поиска в глубину. При выборе очередной подцели в процессе обратного вывода предпочтение всегда, когда возмож­но, отдается той, которая соответствует следующему, более де­тальному уровню описания задачи. Например, система диагнос­тики, сделав на основании известных симптомов предположение о причинах неисправности, будет запрашивать уточняющие при­знаки и симптомы до тех пор, пока полностью не подтвердит (оп­ровергнет) выдвинутую гипотезу. Пример организации поиска в глубину показан на рис. 2.6, где цифрами обозначены номера ша­гов поиска.
Стратегия поиска в ширину. При поиске в ширину сначала анализируются все симптомы (факты), находящиеся на одном уровне пространства состояний задачи, даже если они относятся к разным целям (подцелям), и только после этого происходит пе­реход к поиску симптомов следующего уровня. На рис. 2.7 пока­заны шаги поиска в ширину, обозначенные номерами, указанны­ми в вершинах. На рисунке представлена стратегия обратного вывода на том же И-ИЛИ-фафе, который приведен и на рис. 2.6. Алгоритм поиска в глубину более эффективен в отношении вре­мени поиска и обработки знаний, однако он характеризуется бо­лее высоким риском потери перспективных решений по сравне­нию с поиском в ширину.
Разбиение на подзадачи. Декомпозиция дает положительный эффект только для хорошо структурированных областей знаний,
Факты

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

Заключения
Рис. 2.7. Поиск в ширину при обратном выводе
Для ее успешной реализации следует располагать дополнитель­ными эвристическими знаниями, которые используются при выборе перспективных направлений. Впечатляющий пример применения варианта этой стратегии продемонстрирован раз­работчиками системы Deep Blue, сумевшей обыграть лучшего шахматиста планеты.
<< | >>
Источник: Андрейчиков Александр Валентинович Андрейчикова Ольга Николаевна. ИНТЕЛЛЕКТУАЛЬНЫЕИНФОРМАЦИОННЫЕСИСТЕМЫ. 2004

Еще по теме 2.3.2ПРЯМОЙ И ОБРАТНЫЙ ВЫВОДВ ЭКСПЕРТНЫХ СИСТЕМАХПРОДУКЦИОННОГО ТИПА:

  1. 1.5 Два типа «священнических богословий» и два типа Храма: «исторический» и эсхатологический
  2. Обратная связь
  3. Глава 8. Обратная сторона луны
  4. ДВИЖЕНИЕ ТУДА И ОБРАТНО
  5. Статья 1190. Обратная отсылка
  6. Поддерживайте обратную связь с пациентом.
  7. Положительное подкрепление. Обратная связь.
  8. Подсознательный характер экспертных знаний
  9. Роль экспертно-криминалистических подразделений
  10. С Об истребовании потерянного (обратном завладении им) (vindicatio)
  11. Повторяющиеся решения. Построение баз экспертных знаний
  12. Положительная обратная связь и крайне отрицательные результаты
  13. Трудности получения экспертных знаний
  14. Лекция 6 ПОВТОРЯЮЩ ИЕСЯ РЕШЕНИЯ ПОСТРОЕНИЕ БАЗ ЭКСПЕРТНЫХ ЗНАНИЙ
  15. 6. 2.10. Экспертная диагностика стилей руководства
  16. Технологии искусственного интеллекта и экспертные системы
  17. § 99. ПослЪднш, обратный походъ изъ Индіи въ ГГереію (326 — 325)
  18. Обратная сторона "революции интеллектуалов": формирование устойчивого низшего класса
  19. Глава 13 МЕТОДЫ ПСИХОФИЗИОЛОГИЧЕСКОЙ ДИАГНОСТИКИ, ПРИМЕНЯЕМЫЕ ДЛЯ РЕШЕНИЯ ЭКСПЕРТНЫХ ЗАДАЧ