Продукционный способ представления знаний

Продукционный способ представления знаний

4. ПРОДУКЦИОННАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ

4.1. Представление знаний продукциями

Термин «продукция» принадлежит американскому логику Эмилю Леону Посту [17]. В понимании Поста в качестве продукции выступала только та ее часть, которая сейчас называется ядром (А → В, ЕСЛИ А ТО В).

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

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

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

Основным элементом продукции является ее ядро: А → В. Интерпретация ядра продукции может быть различной и зависит от того, что стоит слева и справа от знака импликации → (⇒). Обычное прочтение ядра продукции выглядит так: ЕСЛИ A ТО B. Более сложные конструкции ядра допускают в правой части альтернативный выбор, например, ЕСЛИ А ТО B₁, ИНАЧЕ B₂. Основание импликации (условие, А) называется антецедентом, следствие (действие, В) – консенквентом.

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

Таблица истинности для импликации

А	В	А → В
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

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

Р есть условие применимости ядра продукции. Обычно Р представляет собой логическое выражение. Когда Р принимает значение «истина», ядро продукции активизируется. Если Р ложно, то ядро продукции не может быть использовано. Например, если в продукции «НАЛИЧИЕ ДЕНЕГ; ЕСЛИ ХОЧЕШЬ КУПИТЬ ВЕЩЬ X, ТО ЗАПЛАТИ В КАССУ ЕЕ СТОИМОСТЬ И ОТДАЙ ЧЕК ПРОДАВЦУ» условие применимости ядра продукции ложно, т.е. денег нет, то применить ядро продукции невозможно.

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

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

Наибольшее распространение продукционные системы нашли при создании экспертных систем.

4.2. Вывод в продукционных системах

Существуют два типа выполнения систем продукций: прямой и обратный [17, 19].

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

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

Существуют также системы с двунаправленными выводами.

Прямой вывод рекомендуется использовать в следующих случаях [23]:

— все или большинство исходных данных заданы в постановке задачи (например, в экспертной системе PROSPECTOR);

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

— сформировать цель или гипотезу очень трудно (например, в экспертной системе DENDRAL изначально мало информации о возможной структуре соединения).

Обратный вывод рекомендуется использовать в следующих случаях:

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

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

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

4.3. Системы активизации продукций

При выполнении условия применимости одновременно для нескольких продукции возникает дилемма выбора продукции или их группы (в случае возможности параллельной обработки), которая в данной ситуации будет активизирована в целях наискорейшего достижения поставленной цели. Решение этой задачи возлагается на систему активизации продукций [17, 19].

Приведем несколько стратегий управления выполнением продукций.

1. Принцип «стопки книг». Основан на идее, что наиболее часто используемая продукция является наиболее полезной. Готовые продукции как бы образуют «стопку», в которой порядок определяется накопленной частотой использования продукций в прошлом. На самом верху «стопки» находится продукция, которая использовалась чаще всех. Из некоторого набора продукций с истинными условиями для исполнения выбирается та продукция или продукции, у которых частота использования максимальна. Подобный принцип управления особенно хорош, когда частота исполнения подсчитывается с учетом некоторой ситуации, в которой ранее применялась продукция, и это имело положительную оценку. При такой обратной связи метод стопки книг может превратиться в обучающуюся процедуру, адаптирующуюся к тем задачам, которые возникают во внешней среде. Управление по принципу стопки книг целесообразно применять, если продукции относительно независимы друг от друга.

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

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

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

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

ЕСЛИ «погода теплая» И «идет снег»
ТО продукции, у которых в А имеется «отдых на улице», следует активизировать раньше, чем продукции, содержащие в A «отдых в помещении»

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

6. Принцип декомпозиции (разбиения задачи на подзадачи). Подразумевает разбиение набора продукций на сферы применения.

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

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

Например, пусть система продукций представлена четырьмя простейшими продукциями:

(а) А → В;
(б) B ∧ D → A;
(в) A ∨ B → C;
(г) А ∧ D → С.

Если выполняется А, то в набор активируемых продукций включает продукции с именами (а) и (в), а если выполняются B и D, то продукции с именами (б) и (в). Для устранения подобной недетерминированности может быть введена некоторая грамматика для имен продукций: (а) → (в); (б) → (в); (б) → (г). Тогда, если в некоторый момент была выполнена продукция с именем (в) или (г), то новые продукции выполняться не будут (т.к. применение новых продукций не приведет к истинности новых фактов). Если же в некоторый момент выполнилась продукция с именем (а), то после следует выполнить продукцию с именем (в) (т.к. применение продукции (б) не приведет к истинности новых фактов, а применение продукции (г) в лучшем случае дублирует результат продукции (в)).

4.4. Достоинства и недостатки продукционной модели знаний

Достоинства продукционной модели знаний [17, 4, 2].

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

2. Простота создания и понимания отдельных правил.

3. Простота пополнения и модификации базы знаний (набора продукций).

4. Простота механизма логического вывода.

5. Разбиение системы продукций на сферы (декомпозиция) позволяет эффективно использовать ресурсы и сократить время поиска решения.

6. Возможность реализации немонотонного логического вывода и обработки противоречивых фактов.

7. Возможность параллельной и асинхронной обработки правил.

Недостатки продукционной модели знаний.

1. Отсутствует теоретическое обоснование в построении продукционных систем. В основном при их построении используются эвристические приемы.

2. Следствие из недостатка 1. При большом числе продукций процедура проверки непротиворечивости правил и корректности работы системы становится крайне сложной. Именно поэтому число продукций, с которыми работают реальные информационные системы, не превышает тысячи.

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

Источник

Продукционная модель представления знаний

Продукционные модели впервые были предложены Эмилем Постом (Emil Leon Post) в 1943г.

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

Первое применение продукций в системах искусственного интеллекта датируется 1972г.

Продукционная модель – модель представления знаний, основанная на правилах, позволяющая представить знания в виде предложений типа:

«Если [условие], то [действие]».

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

База данных содержит факты, описывающие входные данные и состояние системы.

База правил содержит набор продукционных правил в общем виде:

«Если[условие], то [действие]».

Условия, также как и действия, могут быть связаны между собой союзами И, ИЛИ, также может использоваться логическое отрицание НЕ. Например:

«Если[условие 1] или [условие 2], то [действие 1] и [действие 2] «.

На практике редко можно встретить правила, в которых более двух условий или действий.

• Условная часть (IF–part) правила называется антецедентом (antecedent) —
является шаблоном (образцом), по которому можно определить, в какой момент необходимо использовать (активировать) данное правило;
• Часть действия (THEN–part) называется консеквентом (consequent) — описывает соответствующий шаг решения.

Иногда продукционные правила задают в несколько ином виде:

Если , то ,

D_i — фактор достоверности (0,1) или фактор уверенности (0,100).

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

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

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

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

• БЗ продукционной системы;
• Рабочая память;
• Цикл управления «распознавание–действие».

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

В управляющем цикле распознавание–действие осуществляется сравнение образцов из рабочей памяти с условными частями правил из БЗ.

Допустимые продукции (т.е. согласованные с текущим состоянием рабочей памяти) помещаются в конфликтное множество.

После чего осуществляется процесс разрешения конфликтов.

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

Пример продукционной системы №1.

Пример №2.

Пусть в базе правил имеются следующие продукции:

p ЕСЛИ клиент работает на одном месте более двух лет, ТО клиент имеет постоянную работу.
p ЕСЛИ клиент имеет постоянную работу И клиенту более 18 лет И клиент НЕ имеет финансовых обязательств, ТО клиент может претендовать на получение кредита.

В базе данных имеются 2 факта: клиенту более 18 лет, клиент не имеет финансовых обязательств.

Цепочка вывода показывает, как на основании правил и исходных фактов выводится заключение о возможности получения кредита в данном случае.

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

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

Однако указанная черта влечет за собой важную проблему, связанную с управлением порядка применения правил, образующих конфликтное множество.

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

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

Стратегии поиска в глубину и в ширину мы рассмотрим подробнее немного позднее.

А сейчас выделим более сложные для реализации стратегии разрешения конфликтов:

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

2)Принцип наиболее длинного условия. Заключается в выборе из конфликтного множества той продукции, у которой стало истинным наиболее «длинное» условие. Этот принцип опирается на соображение «здравого смысла», что частные правила, относящиеся к узкому классу ситуаций, важнее общих правил, относящихся к широкому классу ситуаций, так как первые учитывают больше информации о ситуации, чем вторые. Трудность использования данного принципа состоит в том, что надо заранее упорядочить условия по вхождению друг в друга по отношению «частное-общее». Управление по принципу наиболее длинного условия в продукциях, целесообразно применять в тех случаях, когда знания и сами продукции хорошо структурированы по привязкам к типовым ситуациям, на которых задано отношение типа «частное-общее».

3)Принцип метапродукций. Принцип основан на идее ввода в систему продукций специальных метапродукций (метаправил).

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

Таким способом в базе знаний вводится определенное структурирование и упорядочивание правил.

• ЕСЛИ кредитный рейтинг клиента высокий И клиент является клиентом банка, ТО сначала применить правила для льготных условий предоставления кредита.
• ЕСЛИ существуют правила, в условиях которых не упоминается текущая цель И существуют правила, в условиях которых упоминается текущая цель, ТО сначала следует активизировать первые из перечисленных правил.

4)Принцип «классной доски». При реализации данного принципа в ИС выделяется специальное рабочее поле памяти — аналог классной доски. На этой «доске» параллельно выполняющиеся процессы находят информацию, инициирующую их запуск, и выносят в эту область информацию о своей работе, которая может оказаться полезной для своих процессов.

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

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

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

7)α-β-алгоритм (Эвристический алгоритм с оценкой f (v) = g(v) + h(v)). С помощью этого алгоритма исходная задача сводится к уменьшению пространства состояний путем удаления в нем ветвей, неперспективных для поиска успешного решения, т. е. просматриваются только те вершины, в которые можно попасть в результате следующего шага, после чего неперспективные направления исключаются. Например, в БЗ продукционной системы, заполненной знаниями о животном мире, не следует искать животных, не относящихся к млекопитающим, в направлении, берущем начало от вершины, определяющей млекопитающих. Данная стратегия является определенным компромиссом между поиском в ширину и поиском в глубину. Для ее успешной реализации следует располагать дополнительными эвристическими знаниями, которые используются при выборе перспективных направлений.

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

Исходные данные

Цель

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

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

Исходные данные

Цель

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

Прямая цепочка рассуждений применяется в следующих случаях:

1) на основании имеющихся фактов необходимо определить тип объекта или явления, выдать рекомендацию, определить диагноз и т.п.

2) все или большинство данных заданы в пространстве задачи

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

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

Обратная цепочка рассуждений применяется в следующих случаях:

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

2) цель поиска явно присутствует в постановке задачи или может быть легко сформулирована

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

4) исходные данные не приводятся в задаче, но подразумевается, что они должны быть известны или могут быть легко получены.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теперь можем непосредственно перейти к рассмотрению стратегий поиска в пространстве состояний.

n OPEN — список, который содержит выбранные, но необработанные узлы;

n CLOSED — список, который содержит обработанные узлы.

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

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

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

Источник