дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
(current-node ?name) (node (name ?name) (type answer) (answer ?— node и факт, соответствующий узлу ответа. (defrule answer- node-guess-is-correct ?node <- (current-node ?name) (node (name ?name) (type answer)) ?answer <- (answer yes) — > (assert (ask- try-again)) (retract ?node ?answer)) (defrule answer-node-guess-is- incorrect ?node <- (current-node ?name) (node (name ?name) (type answer)) ?answer <- (answer по) — > (assert (replace-answer-node ?name)) (retract ?node ?answer)) Для определения того, желает ли пользователь продолжить работу, используются три приведенных ниже правила. Правило ask — try — again выводит вопрос "Try again?" (Сделать еще одну попытку. Еще раз отметим, что запуск правила bad — answer осуществляется, если на вопрос не дан ответили по. Если пользователь даст на вопрос "Try again?" ответ yes, то правило one — more — time переустанавливает факт current-node на корневой узел, чтобы можно было снова начать процесс выдвижения предположений. Если пользователь даст ответ по, то факты, представляющие дерево решений, сохраняются в файле animal dat с помощью команды save — facts. (defrule ask-try-again (ask-try-again) (not (answer ?)) — > (assert (answer (ask-уев-or-по "Try again?")))) (defrule one-more-time ?phase <- (ask-try-again) ?answer <- (answer yes) => (retract ?phase Глава 12. Примеры проектов экспертных систем 966 (assert (current-node root))) (defrule по ?phase <- (ask-try-again) ? answer <- (answer по) — > (retract ?phase ?answer) (save-facts "animal.dat" local node)) (defrule replace-answer-node ?phase <- (replace-answer-node ?name) ?data <- (node (name ?name) (type answer) (answer ?value)) (retract ?phase) Определить, каким должно быть предположение (printout t "What is the animal? ") (bind ?new-animal (read)) Узнать, какой вопрос соответствует этому предположению (printout t "What question when answered yes ") (printout t "will distinguish " crlf " а ") (printout t ?new-animal " from а " ?value "? ") (bind ?question (readline)) (printout t "Now I can guess " ?new-animal crlf) Создать новые узлы, полученные в результате обучения (bind ?newnode1 (gensym*)) (bind ? newnode2 (gensym*)) (modify ?data (type decision) (question ? question) (yes-node ?newnode1) (по ?newnode2)) (assert (node (name ?newnode1) (type answer) (answer ?new-animal))) (assert (node (name ?newnodel) (type answer) (answer Наконец, если пользователь ответит, что идентификация животного в узле ответа является неверной, то с помощью следующего правила добавляется новый узел принятия решений, которое позволяет провести обучение дерева решений 12.3. Деревья решений Пошаговая трассировка программы обучения дерева решений За функционированием этой программы обучения деревьев решений можно понаблюдать, отслеживая ее выполнение. Предположим, что правила поддержки дерева решений загружены и создан файл animal содержащий факты, которые представляют начальное дерево решений в таком случае следующий диалог показывает состояние системы после выполнения команды reset: CLIPS> (watch facts)J CLIPS> (watch rules)J CLIPS> (reset) J > f — ООО а total of 1 activation. CLIPS> В связи с отсутствием факта корневого узла было активизировано правило initialize. Запуск правила initialize разрешен, поэтому загружаются факты, составляющие дерево решений. Обратите внимание на то, что часть вывода в приведенных ниже трассировках обозначена отступами для удобства чтения. CLIPS> (run 1)J FIRE 1 initialize f — О, > f-1 (node (name root) (type decision) (question "Is the animal warm- blooded?" ) Определить, желает ли игрок предпринять еще одну попытку (assert (ask-try-again))) С помощью правила replace — answer — node формируется вопрос о том, как следует идентифицировать данное животное и какой вопрос позволяет получить информацию, с помощью которой данное животное можно отличить от животного, название которого идентифицировалось до сих пор в дереве решений как допустимый ответ. Старый узел ответа заменяется узлом принятия решений и двумя узлами ответа, созданными для представления ответов на вопрос, вновь освоенный в результате обучения. С помощью функции gensym* (которая вырабатывает уникальный символ при каждом ее вызове) подготавливаются имена каждого из двух новых узлов ответа. После этого в список фактов вносится факт ask — try — again для определения того, должен ли быть выполнен еще один прогон программы Глава 12. Примеры проектов экспертных систем (yes-node node1) (по node2) (answer nil)) > f-2 (node (name node1) (type decision) (question "Does the animal purr?") (yes node по node4) (answer nil)) > f-3 (node (name node2) (type answer) (question nil) (уея-node nil) (по nil) (answer snake)) > f-4 (node (name node3) (type answer) (question nil) (yes-node по nil) (answer cat)) > f-5 (node (name node4) (type answer) (question nil) (yes-node nil) (no-node nil) (answer dog)) > б root) CLIPS> (agenda)J 0 ask-decision-node-question: f-6,f-1, For а total of 1 activation. CLIPS> В правиле initialize для загрузки фактов в дерево решений используется функция load- facts. В качестве факта current — node задается факт корневого узла. Корневой узел — это узел принятия решений, поэтому активизируется правило ask — decision — node — Запуск этого правила и связанного с ним правила proceed — to — yes — branch разрешен, поэтому формируется следующий диалог CLIPS> (run 2) 1 FIRE 1 ask-decision-node-question: f-6,f- 1, Is the animal warm-blooded? (yes or no) yesJ — > f-7 (answer yes) FIRE 2 proceed-to-yes-branch: f-6,f-l,f-7 < б (current-node root) < f-7 (answer yes) > f-8 (current-node node1) CLIPS> (agenda)J 0 ask-decision-node-question: f-8,f-2, For а total of 1 activation ° CLIPS> С корневым узлом принятия решений связан вопрос "Is the animal warm — blooded?" (Является ли животное теплокровным) Поскольку ответ на 12.3. Деревья решений 969 этот вопрос является положительным, под действием правила proceed — to- yes — branch текущим узлом становится узел, находящийся слева отданного узла принятия решений (узел node1). Узел node1 также является узлом принятия решений, поэтому снова активизируется правило as k — deci s ion-node — ques- После того как будет разрешен запуск очередных двух правил, формируется следующий диалог CLIPS> (run 2) ! FIRE 1 ask- decision-node-question: f-8,f-2, Does the animal purr? (yes or по > f-9 (answer по) FIRE 2 proceed-to-no-branch: f-8,f-2,f-9 < f-8 (current-node node1) < f-9 (answer по) > f-10 (current-node node4) CLIPS> (agenda)J 0 ask-if-answer-node-is-correct: f-10,f-5, For а total of 1 activation. CLIPS> С узлом принятия решений связан вопрос "Does the animal purr?" (Это животное мурлыкает) Поскольку ответ на вопрос является отрицательным, под действием правила proceed — to — no — branch текущим узлом становится узел, находящийся справа от узла принятия решений (узел node4). Узел node4 является узлом ответа, поэтому активизируется правило ask — if-- answer-node — is — correct. После того как будет разрешен запуск этого правила и следующего за ним правила, формируется такой диалога no) FIRE 2 answer-node-guess-is-incorrect: f-10,f-5, f — 11 > f-12 (replace-answer-node node4) < f-10 (current-node node4) < f- 11 (answer по) CLIPS> (agenda)J 0 replace answer node: f 12,f 5 For а total of 1 activation. CLIPS> 970 Глава 12. Примеры проектов экспертных систем > Прежде всего с помощью команды (replace-answer — node node4) извлекается управляющий факт. Затем определяется приемлемое предположение наряду стем, какой вопрос к пользователю должен служить для определения приемлемого предположения. Узел неверного ответа модифицируется и становится узлом принятия решений, а затем формируются два узла ответов для этого нового узла принятия решений. Наконец в список фактов вносится управляющий факт ask — try — again для определения того, нужно ли идентифицировать еще С этим узлом ответа связано предположение, что искомым животным является собака. Нов данном случае предположение неверно, поэтому активизируется правило replace — answer-node для определения приемлемого ответа. После того как будет разрешен запуск этого правила, формируется следующий диалог CLIPS> (run 1)J FIRE 1 replace-answer-node: f-12,f-5 < f- 12 (replace-answer-node node4) What is the animal? birdJ What question when answered yes will distinguish а bird from а dog? Does the animal fly?J Now I can guess bird < f-5 (node (name node4) (type answer) (question nil) (yes-node nil) (по nil) (answer dog)) > f-13 (node (name node4) (type decision) (question "Does the animal fly?") (yes-node gen1) (по gen2) (answer dog)) (node (name gen1) (type answer) (question nil) (yes-node по nil) (answer bird)) > f-15 (node (name gen2) (type answer) (question nil) (yes-node nil) (по nil) (answer dog)) > f-16 (ask- try-again) CLIPS> (agenda)J О ask-try-again: f-16, For а total of 1 activation. CLIPS> 12.3. Деревья решений 971 одно животное. После того как будет разрешен запуск правила ask — try-again, а затем правила по — more, формируется следующий диалог CLIPS> (run 2) 1 FIRE 1 ask-try-again: f-16, Try again? (yes or по) noJ > f-17 (answer по 2 по-тоге: f-16,f-17 < f-16 (ask-try-again) < f-17 (answer по (agenda)J CLIPS> С помощью правила ask — try — again система задает пользователю вопрос о том, нужно ли предпринять еще одну попытку идентификации. Ответ на этот вопрос является отрицательным, поэтому с помощью правила по — more снова происходит сохранение дерева решений в файле animal . dat. После завершения этого сеанса файл animal dat имеет такую форму (node (name root) (type decision) (question "Is the animal warm-blooded?" ) (yes-node node1) (по- node node2) (answer nil)) (node (name nodel) (type decision) (question "Does the animal purr?") (yes-node node3) (по node4) (answer nil)) (node (name node2) (type answer) (question nil) (yes-node nil) (по nil) (answer snake)) (node (name node3) (type answer) (question nil) (yes-node nil) (по nil) (answer cat)) (node (name node4) (type decision) (question "Does the animal fly?") (yes-node gen1) (по gen2) (answer dog)) (node (name gen1) (type answer) (question nil) (yes-node nil) (по nil) (answer bird)) (node (name gen2) (type answer) (question nil) (yes- node nil) (no-node nil) (answer dog)) 972 Глава 12. Примеры проектов экспертных систем Обратный логический вывод Система CLIPS в составе средств своей машины логического вывода непосредственно не реализует обратный логический вывод. Тем не менее обратный логический вывод может быть эмулирован с использованием правил прямого логического вывода системы CLIPS. В настоящем разделе будет показано, как можно создать на языке простую систему обратного логического вывода. Следует отметить, что язык CLIPS разработан для применения в качестве языка прямого логического вывода, поэтому если для решения некоторой задачи в большей степени приемлем подход на основе обратного логического вывода, то следует использовать язык, в котором обратный логический вывод непосредственно реализован в составе средств машины логического вывода, такой как PROLOG. В настоящем разделе система обратного логического вывода CLIPS будет создана с учетом описанных ниже возможностей и ограничений. ° Факты будут представлены как пары "атрибут — значение. ° Обратный логический вывод будет начинаться с внесения в список фактов единственного начального атрибута goal (цель. ° В качестве условия в антецеденте правила будет проверяться только равенство атрибута конкретному значению. ° Единственным действием в антецеденте правила будет присваивание значения единственного атрибута. ° Если значение атрибута goal не может быть определено с помощью правил, то программа обратного логического вывода будет запрашивать предоставление значения для этого атрибута. Атрибутам не может присваиваться неопределенное значение. ° Атрибут может иметь только единственное значение. Гипотетические рассуждения о различных значениях атрибутов, полученных на основе разных правил, не поддерживаются. ° Неопределенность не будет представлена. Алгоритм работы программы обратного логического вывода Прежде чем приступить к разработке механизма обратного логического вывода и осуществлению с помощью языка CLIPS попыток реализации подхода, Узел ответа node4 заменен узлом принятия решений, который ссылается на два новых узла ответа. Кроме того, теперь применяемое по умолчанию значение nil, автоматически присваиваемое некоторым слотам конструкции de f после сохранения фактов стало заданным явно. Обратный логический вывод 973 основанного на правилах, необходимо рассмотреть процедурный алгоритм. Для определения значения атрибута goal с использованием подхода на основе обратного логического вывода с возможностями и ограничениями, описанными выше, может применяться следующая процедура на псевдокоде procedure Solve Goal(goal) goal: the current goal to be solved if value of the goal attribute is known Return the value of the goal attribute. end if for each rule whose consequent is the goal attribute do call Attempt Rule with the rule if Attempt Rule succeeds then Assign the goal attribute the value indicated by the consequent of the rule ° Return the value of the goal attribute. end if end do Ask the user for the value of the goal attribute. Set the goal attribute to the value supplied by the user. Return the value of the goal attribute. end procedure Атрибут goal передается процедуре Solve Goal в качестве параметра. Эта процедура определяет значение атрибута goal и возвращает его. Вначале в процедуре Solve Goal проверяется, известно ли уже значение атрибута goal. Это значение уже могло быть присвоено в консеквенте другого правила или задано пользователем программы обратного логического вывода. Если данное значение действительно известно, происходит его возврат. Если же значение атрибута неизвестно, тов процедуре Solve Goal предпринимается попытка определить это значение путем поиска правила, в консеквенте которого данному атрибуту присваивается значение. В процедуре Solve Goal осуществляются попытки проверить каждое правило, в консеквенте которого атрибуту goal присваивается значение до тех пор, пока проверка одного из правил не завершится успешно. Для проведения таких попыток каждое правило с желаемым атрибутом goal передается процедуре Attempt которая будет подробно рассматриваться немного позже. Если проверка антецедента правила, рассматриваемого в очередной попытке, оканчивается успешно, то считается, что правило успешно прошло проверку в противном случае проверка считается Глава 12. Примеры проектов экспертных систем неудачной. Если проверка правила завершилась успешно, то значение атрибута в консеквенте правила присваивается атрибуту goal и возвращается процедурой Solve Goal. Если же проверка правила оканчивается неудачей, то предпринимается попытка проверить следующее правило, в консеквенте которого присваивается значение атрибуту goal. Если ни одна из проверок правил не завершается успешно, то для определения значения атрибута goal должен быть передан запрос пользователю. В таком случае процедура Solve Goal возвращает значение, предоставленное пользователем. Для определения того, выполнены ли условия в антецеденте правила, применяется процедура Attempt Rule. Если условия в антецеденте правила выполнены, то консеквент правила может использоваться для присваивания значения атрибуту Псевдокод этой процедуры приведен ниже. procedure Attempt Rule(rule) rule: rule to be attempted to solve goal for each condition in the antecedent of the rule do call Solve Goal with condition attribute if the value returned by solve goal is not equal to the value required by the condition then Return unsuccessful. end if end for Return successful end procedure Работа процедуры Attempt Rule начинается с проверки первого условия правила и попытки доказать его после этого осуществляются попытки доказать остальные условия правила. Для определения того, выполнено ли условие, процедура Attempt Rule должна иметь информацию о том, какое значение имеет атрибут, проверяемый в данном условии. Для определения этого значения рекурсивно вызывается процедура Solve Goal. Если значение, возвращенное процедурой Solve Goal, неравно значению, возвращенному при проверке условия, то процедура Attempt Rule завершает свою работу и возвращает значение, свидетельствующее о неудаче (напомним, что в условиях проверяется только равенство. В противном случае проверяется очередное условие правила. Если выполнены все условия правила, то процедура Attempt Rule оканчивает свою работу, возвращая значение, свидетельствующее об успешном завершении. Обратный логический вывод 975 Представление правил обратного логического вывода в языке CLIPS Ив данном случае первым шагом к решению задачи становится определение того, как должны быть представлены знания. Система CLIPS не осуществляет автоматически обратный логический вывод, поэтому удобнее всего было бы представлять правила обратного логического вывода как факты, для того чтобы антецеденты и консеквенты правил можно было проверять с помощью правил, действующих в качестве механизма обратного логического вывода. Конструкция deftemplate, предназначенная для представления правил обратного логического вывода, показана ниже. Эта конструкция будет храниться в конструкции de fmodule с именем BC (которая приведена в конце данного подраздела, после описания всех конструкций de f необходимых для данной машины обратного логического вывода. (deftemplate ВС::rule (multislot if) (multislot Антецедент и консеквент каждого правила должны храниться в слотах if и then соответственно. Каждый антецедент содержит либо одну пару "атрибут значение" в приведенном ниже формате, либо ряд таких пар "атрибут — значение", соединенных символом and. приведенное на рис. 12.2. Данное дерево можно легко представить в виде правил, в которых применяются пары "атрибут — значение" (см. выше. Ниже приведен псевдокод таких преобразованных правил. Глава 12. Примеры проектов экспертных систем 976 Такой способ представления обеспечивает значительную гибкость при манипулировании правилами обратного логического вывода. Например, если определено, что атрибут main — course имеет значение poultry, то факты (rule (if main-course is red-meat) (then best-color is red)) (rule (if main-course is fish) (then best-color is white)) Атрибутами, используемыми в этих правилах, являются main — course, meal — is — turkey и best — color. Атрибут main — course соответствует ответу, определяемому с помощью вопроса из дерева решений "What is the main course?" (Что является основным блюдом) Атрибут meal — is — 1ыгЕеу соответствует ответу, определяемому с помощью вопроса "Is the main course turkey?" (Является ли основным блюдом индейка) Обратите внимание на то, что ребро дерева решений, определяющее, что наиболее подходящий тип вина неизвестен, не представлено в виде правила, поскольку одно из ограничений рассматриваемой программы обратного логического вывода состоит в том, что с ее помощью нельзя представить неизвестные значения. Если основным блюдом не является такое блюдо, для которого в правилах предусмотрен ответ, то пользователю поступает запрос указать значение атрибута best- color. Следующая конструкция бей показывает, как можно представить правила, касающиеся выбора наиболее подходящего вина, с помощью формата правил обратного логического вывода. Эти факты, определяющие правило, не являются неотъемлемой частью машины обратного логического вывода, поэтому размещаются в модуле MAIN (напомним, что модуль МАХИ импортирует конструкции из всех других модулей, поэтому конструкция de f template с именем rule также будет в нем видимой. (deffacts MAIN::wine-rules (rule (if main-course is red-meat) (then best-color is red)) (rule (if main-course is fish) (then best-color is white)) (rule (if main-course is poultry and meal-is- turkey is yes) (then best-color is red)) (rule (if main-course is poultry and meal-is-turkey is по) (then best-color is white))) 12.4. Обратный логический вывод 977 могут быть удалены из списка фактов для указания на то, что соответствующие правила неприменимы, а факты (rule (if main-course is poultry and meal is — turkey is yes) (then best-color is red)) (rule (if main- course is poultry and meal-is-turkey is помогут быть соответствующим образом модифицированы с получением фактов (rule (if meal-is-turkey is yes) (then best-color is red)) (rule (if meal-is-turkey is по) (then best-color is white)) для указания на то, что первое условие этих двух правил было выполнено. По мере осуществления обратного логического вывода вырабатываются подцели, предназначенные для определения значений атрибутов. Для представления информации об атрибутах goal потребуется определенный факт. Представление атрибутов goal будет осуществляться с использованием упорядоченных фактов, которые имеют следующий формат (deftemplate ВС::goal (slot Первоначально атрибутом goal становится атрибут best — color, который может быть представлен с помощью конструкции de f f acts: (deffacts MAIN::initial-goal (goal (attribute best-color))) После определения значений атрибутов их необходимо сохранить с помощью следующей конструкции de f template: (deftemplate ВС::attribute (slot name) (slot value)) Теперь, после определения всех конструкций de f template, можно привести определение модуля ВС, как показано ниже. Напомним, что при загрузке файла с конструкциями, которые должна содержать конструкция defmodule, другие конструкции должны быть определены прежде, чем содержащие их конструкции. Глава 12. Примеры проектов экспертных систем 978 (defmodule BC (export deftemplate rule goal attribute)) Машина обратного логического вывода на языке CLIPS Машина обратного логического вывода может быть реализована с использованием двух множеств правил. Первая группа правил применяется для выработки целей, при достижении которых выявляются значения атрибутов, и для передачи запроса пользователю, чтобы он предоставил значения атрибутов, если эти значения невозможно определить с помощью правил. Вторая группа правил осуществляет операции обновления. К числу операций обновления относятся операции модификации правил после выполнения их условий и операции удаления целей после их достижения. Первое множество правил приведено ниже. (defrule ВС::attempt-rule (goal (attribute ?g-name)) (rule (if ?а-пате 9?) (пате $?)) (not (attribute (name а) (not (goal (attribute а) — > (assert (goal (attribute а) (defrule ВС::ask- attribute-value ?goal <- (goal (attribute ?g-name)) (not (attribute (name ?g-name))) (not (rule (then пате ?))) => (retract ?goal) (printout t "What is the value of " пате "? ") (assert (attribute (name ?g-name) (value (read))))) С помощью правила attempt-rule осуществляется поиск правил, антецеденты которых задают значение атрибута для атрибута goal. Первый шаблон сопоставляется с фактом goal. Во втором шаблоне происходит поиск всех правил, в антецедентах которых присваивается значение атрибуту goal. В третьем шаблоне проверяется, определено ли уже значение атрибута goal. С помощью четвертого шаблона подтверждается, что цель определения значения атрибута еще не достигнута. Для каждого найденного правила в правой части правила attempt-rule в список фактов вносится цель определения значения атрибута, проверенного в первом условии правила. Правило ask — attribute — value весьма напоминает правило attempt— rule. Первые два шаблона этого правила идентичны. А в третьем шаблоне про. Обратный логический вывод 979 (defrule ВС::goal-satisfied (declare (salience 100)) ?goal <- (goal (attribute ?g-name)) (attribute (name ?g-name)) — > (retract ?goal)) (defrule ВС::rule-satisfied (declare (salience 100)) (goal (attribute ?g-name)) (attribute (name а) (value а) ?rule <- (rule (if а is а пате is ?g-value)) (retract ?rule) (assert (attribute (name ?g- name) (value ?g-value)))) (defrule ВС::remove-rule-по-match (declare (salience 100)) (goal (attribute ?g-name)) (attribute (name а) (value а) ?rule <- (rule (if ?а-пате is -а пате is ?g-value)) (retract ?rule)) (defrule ВС::modify-rule- match (declare (salience 100)) (goal (attribute ?g-name)) (attribute (name а) (value а) ?rule <- (rule (if ?а-пате is а- value and веряется, что отсутствуют оставшиеся правила, которые могут использоваться для определения значения атрибута goal. В таком случае пользователю передается запрос, чтобы он сам задал значение этого атрибута. В список фактов вносится факт, представляющий значение атрибута, и извлекается факт goal, относящийся к этому атрибуту. Для обновления правил обратного логического вывода и целей, которые представлены как факты, используются приведенные ниже четыре правила. Этим правилам присвоена значимость, равная 100, для того чтобы обновления происходили до того, как будут сделаны какие-либо попытки вырабатывать новые цели или запрашивать у пользователя значения атрибутов Глава 12. Примеры проектов экспертных систем 980 9?rest-if) |