Сб. Фев 24th, 2024

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

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

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

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

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

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

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

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

Обрат­ные выводы управляются целями.
 

 

 

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

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

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

В цикле выполняются следу­ющие основные операции:

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

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

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

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

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

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

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

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

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

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

  1.  Сопоставление фактов из РП с образцами правил из БП. Правило 1 не может сработать,
  2. а Правило 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 не может сработать из-за отсутствия в РП образца Двигатель не заво­дится. Этот факт становится новой целью на следующем шаге вывода.
  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, а также в других системах с прямыми выводами широкое распространение получил метод разрешения конфлик­тов LEX, в котором предпочтение отдается правилам со ссылкой на самый последний сгенерированный образец. Если таких пра­вил несколько, то среди них выбирается правило с наибольшим числом условий в антецеденте.В больших ЭС продукционного типа все множество знаний обычно хранится в виде древовидной структуры, называемой И-ИЛИ-графом. Фрагменты такой структуры приведены на рисунках. Классическая форма продукций предполагает наличие в антецеденте только связки И. На практике классическая форма может быть расширена, например, введением связки ИЛИ в ус­ловную часть либо включением в антецедент вычислений на ос­новании содержимого рабочей памяти и т.п. Если существует множество правил, из которых выводится одно и то же, то, выполнив операцию дизъюнкции над всеми заключениями, полученными с помощью этих правил, можно показать от­ношение между результатом отдельного вывода и данными, на основании которых делается вывод.

Заключения

Основные системные данные

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

Начало поиска

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

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

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

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

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

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

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

 

Ads Blocker Image Powered by Code Help Pro

Обнаружен блокировщик рекламы! Пожалуйста, обратите внимание на эту информацию.

We\'ve detected that you are using AdBlock or some other adblocking software which is preventing the page from fully loading.

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

Пожалуйста, добавьте tehnar.info к вашему белому списку блокирования объявлений или отключите программное обеспечение, блокирующее рекламу.

Powered By
Best Wordpress Adblock Detecting Plugin | CHP Adblock