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

Размещено на http://www.allbest.ru/

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

управление выбор стратегия поиск

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

Управление посредством выбора стратегии поиска: на основе данных или от цели

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

Такое представление рассуждений на основе данных подчеркивает их соответствие модели продукционной системы. 'Текущее состояние мира" (это исходные данные, которые приняты как истина или выведены как истина с помощью правил вывода) помещается в рабочую память. Затем в цикле "распознавание-действие" текущее состояние сравнивается с упорядоченным набором продукций. Если эти данные соответствуют условиям одного из правил вывода (унифицируются с ними), применение этого правила добавляет новую порцию информации к текущему состоянию мира, изменяя рабочую память.

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

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

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

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

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

Продукционное множество:

1. pqцель

2. rsp

3. wrq

4. tuq

5. vs

6. началоvrq

Последовательность выполнения

Просмотренная часть пространства:

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

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

Продукционное множество:

1. pqцель

2. rsp

3. wrq

4. tuq

5. vs

6. началоvrq

Последовательность выполнения:

Просмотренная часть пространства:

Рис. 2. Поиск от цели в продукционной системе

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

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

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

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

Рис. 3. Двунаправленный расширенный поиск

Рис. 4. Двунаправленный поиск, отсекающий большую часть пространства, исследуемую при однонаправленном поиске

Управление поиском с помощью структуры правил

Структура правил в продукционной системе, включая различия между условием и действием, а также порядок проверки условий, определяет метод исследования пространства. Описывая исчисление предикатов как язык представления, мы подчеркивали декларативный характер его семантики. Таким образом, выражения исчисления предикатов всего лишь определяют истинные отношения в области формулировки задачи и не делают никаких утверждений относительно порядка интерпретации их компонентов. Следовательно, некоторое частное правило может иметь вид X(foo(X)goo(Х)moo(Х)). Согласно правилам исчисления предикатов альтернативная форма того же правила может быть такой X(foo(X)moo(Х) goo(Х)). Эквивалентность этих двух выражений может быть продемонстрирована с помощью таблицы истинности.

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

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

Несмотря на то что выражения X(foo(X)goo(Х)moo(Х)) и X(foo(X)moo(Х) goo(Х)) логически эквивалентны, при реализации поиска они обрабатываются не одинаково.

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

Управление поиском через разрешение конфликтов

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

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

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

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

Преимущества продукционных систем

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

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

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

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

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

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

Независимость от выбора языка. Модель управления продукционной системой не зависит от представления правил и рабочей памяти, если это представление поддерживает сравнение с образцами. Мы описали продукционные правила как импликации исчисления предикатов вида А => В, где истинность А и правило вывода модус поненс позволяют сделать заключение В. Существует немало преимуществ применения логического представления знаний и обоснования правил вывода, однако модель продукционной системы может работать и с другими представлениями.

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

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

Размещено на Allbest.ru