Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Глобальная БД




Продукционные системы

Основными компонентами продукционных систем являются:

1. Глобальная БД (рабочая память, база)

2. Множество продукционных правил (база для правил, память правил, правила)

3. Система управления (интерпретатор, управление, механизм логического вывода, дедуктивная машина)

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

Основными операциями, реализуемыми в БД, являются:

· Поиск фрагмента данных по образцу

· Исключение данных

· Добавление данных

Основными параметрами, определяющими организацию конкретной БД, являются:

· объем и характер данных

· тип операции над ними

· тип процесса, реализованного в продукционной системе

Два типа процесса:

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

· Параллельный. Когда в БД необходимо хранить несколько связанных между собой результатов.

Множество продукционных правил

Описывает процедурное содержание знаний, заложенных экспертом данной предметной области в систему. И каждое хранимое правило представлено в виде:

(i); Q; P; A B; N

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

1. редактирование глобальной БД

2. обращение во внешнюю среду

3. воздействие на аппарат активации (переход к следующему правилу по условию)

4. редактирование совокупности продукционных правил

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

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

В простейшем случае условия применимости каждого продукционного правила проверяются для каждого текущего состояния глобальной БД.

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

Продукционное правило переходит в новое состояние, для которого выполняется процедура проверки и выбора. Вычислительный процесс останавливается, когда достигнуто целевое состояние БД.

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

Известно несколько способов разрешения конфликта.

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

II подход. Выбираются правила с наивысшим приоритетом.

III подход. Выбираются правила в порядке возрастания.

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

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

· безвозвратный

· пробный

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

В пробных стратегиях два режима:

· режим с возвращением (при выборе правила определяется некая точка возврата и если последовательные вычисления приведут к трудностям построения решения, то процесс вычисления переходит к предыдущей точки, где выбирается другое правило и процесс продолжается)

· управление поиском на графе (предусматривается запоминание результатов применения всех возможных правил).

 

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

По способу применения продукционных правил выделяют два типа продукционных систем:

· прямые

· обратные

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

«ЕСЛИ Указатель бензина находится на нуле, ТО Нет бензина».

В РП находятся те же факты, что в предыдущем примере.

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

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

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

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

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

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

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

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

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

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

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

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

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

«(ЕСЛИ Засорился бензонасос, ТО двигатель не заводится».

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

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

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

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

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

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

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

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

 

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

 

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

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

 

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

 

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

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

 

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

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

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

 

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

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

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

 

 




Поделиться с друзьями:


Дата добавления: 2015-06-27; Просмотров: 829; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.063 сек.