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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если <X₁, X₂, ... X_n>, то <{Y₁, D₁}, ... {Y_m, D_m}>,

где: X_i,Y_i - логические выражения,

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) исходные данные не приводятся в задаче, но подразумевается, что они должны быть известны или могут быть легко получены.

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

- язык OPS 5,

- EXSYS Professional,

- Kappa,

- Clips.

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

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

Правило 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 теперь подтверждена фактами, следовательно, оно срабатывает, и выдвинутая начальная гипо­теза подтверждается.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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