Обратной цепочки рассуждений.
Управление стратегией вывода с помощью
Выбор стратегий вывода решений.
Лекция 8
(См. пример Ch 18 Ex. Pr1)
Разработка правил для ЭС базируется на двух известных концепциях - прямой и обратной цепочках рассуждений. Каждая концепция определяет стратегию выбора в конкретных условиях.
Стратегия обратного вывода используется в следующих случаях. В некоторых задачах имеется всего несколько решений при наличии огромных объемов входной информации. В этом случае целесообразно в каждый момент времени рассматривать только одно из возможных решений, а затем собрать и проверить все свидетельства, которые могут его подтвердить или опровергнуть.
Наиболее известными ЭС с обратным выводом являются MYCIN, системы, сделанные на ее основе, и PROSPECTOR. MYSIN предназначена для идентификации вируса, вызвавшего болезнь. Программы этой группы обычно ограничиваются диагностикой болезней отдельных систем организма. Для каждой такой системы существует всего несколько разновидностей вирусов, вызывающих конкретную болезнь, поэтому здесь подходит обратный вывод. PROSPECTOR использует сходную стратегию обратного вывода. Рассматривая по очереди несколько внутренних моделей рудных месторождений, система отыскивает модель, которой более всего соответствуют имеющиеся данные. Проиллюстрируем обратный вывод на примере простой программы “Птица, зверь или рыба”. В этом гипотетическом примере пространства входных данных и пространство возможных решений невелики. Поэтому можно использовать две стратегии: прямую и обратную.
"Птица, зверь или рыба" (ПЗР) - это написанная на языке Пролог простая программа - игра-загадка. Пользователь задумывает конкретное животное. Система пытается угадать его, задавая вопросы, чтобы получить недостающую информацию.
Типичный диалог для программы:
Вопрос Ответ
У него есть волосы? Нет
Оно дает молоко? Нет
У него есть перья? Нет
У него есть клыки? Нет
Оно ест мясо? Да
Оно плавает? Да
У него есть щупальца? Да
Задуманное животное - осьминог!
Программа ПЗР ведет четкий и разумный диалог, запрашивая у пользователя необходимую информацию, которой она еще не располагает.
Такого рода систем существует много. Они являются классификационными ЭС.
Программа с обратной цепочкой рассуждений включает группу правил, каждое из которых описывает одно животное, четко указывая, какая именно информация нужна системе, чтобы прийти к выводу, что именно данное конкретное животное является искомым ответом.
Например:
animal_is (octopus) if
not (it_is(mammal)) and
it_is (carnivorous) and
positive (does,swim),
positive (has, tentacles),!.
Оно расшифровывается следующим образом:
Животное - осьминог, если это не млекопитающее, это плотоядное, умеет плавать, имеет щупальцы.
Сходные правила имеются для всех животных, которых предстоит классифицировать программе.
В данной программе правила просто применяются одно за другим, начиная с вершины дерева. В процессе такого сканирования ответ, безусловно, будет найден, если только правило для идентификации задуманного животного существует.
Если располагать правила по-разному, то будут происходить различные диалоги, причем одни из них могут быть длиннее, другие короче. Важен порядок следования правил animal_is. Если речь идет о настоящей большой ЭС, то правила надо располагать таким образом, чтобы минимизировать количество задаваемых вопросов. Поэтому, если животное X – наиболее подходящий ответ, а животное Y - следующее по приоритету, то правило для определения животного X должно находиться в программе первым, а правило для определения животного Y - за ним.
Еще имеется одно правило, которое срабатывает, если ответ не получен:
animals_is (uncnown).
Все правила animal_is поддерживаются соподчиненными правилами классификации животных.
Например:
it_is (mammal) if
positive (has,hair),!.
it_is (mammal) if
positive (does,give_milk),!. и другие.
Читается это так: животное - млекопитающее, если оно имеет Шерсть; животное - млекопитающее, если оно дает молоко.
Следует заметить, что правила positive и negative используются для проверки конкретных атрибутов животных, которые могут быть обнаружены в процессе диалога.
В программе задействован механизм вопросов-ответов. Рассмотрим его более подробно:
Прежде всего необходимо иметь факты, называемые xpositive и xnegative, которые становятся реальной формой ответно-вопросной информации, когда они поступают в базу данных. Они объявляются в разделе database.
database
xpositive (symbol,symbol)
xnegative (symbol,symbol)
Это обусловлено тем, что в Прологе допустимо помещать в базу данных в процессе выполнения программы только те предложения, которые представлены простыми фактами. Раздел Clauses для предикатов, объявленных в database, не должен содержать правила - только факты. Предикаты positive и negative не могут использоваться для этой цели, потому что есть правила, связанные с ними. Первое из них заставляет систему непосредственно просмотреть информацию, уже включенную в базу данных. Если атрибут в ней найден процесс заканчивается. Второе правило инициирует поиск отрицания того, что мы пытаемся установить, и если его также нет в базе данных, то вызывается правило ask. К этому моменту система определила, что не располагает нужной информацией, поэтому она вынуждена задать вопрос пользователю. Любой полученный ответ запоминается с целью непосредственного или последующего применения. Взаимосвязь между xpositive и positive определяется следующим образом:
positive(X,Y) if xpositive(X,Y),!.
Т.е. xpositive эквиалентен в базе данных positive. Аналогично определяется negative
negative(X,Y) if xnegative(X,Y),!.
Еще одно правило для positive - пользователь дает информацию о том, существует ли что-либо, противоречащее факту:
positive(X,Y) if
not (xnegative(X,Y)) and ask(X,Y,yes).
Для negative имеем, соответственно:
negative(X,Y) if
not (xpositive(X,Y)) and ask(X,Y,no).
Предикат ask - задает вопрос и организует ответы, если ответ начинается с y - то это yes, если n - no.
Таким образом, имеется по два правила для positive и negative.
Разберем структуру вопросов, порождаемых правилом ask:
1.has it wings (Есть ли у него крылья?);
2.has it teeth (Есть ли у него зубы?);
3.does it bite (Кусается ли оно?).
Все, что программа помещает в базу данных, всегда имеет вид пары, состоящей из глагола и атрибута, например
xpositive (has,wings).
Так как программа хранит данные в таком виде, легко создать грамматически правильное предложение для предъявления его пользователю, просто поставив слово "оно" между глаголом и атрибутом. Пользователь, вероятно, введет слова "да" или "нет" в ответ на запрос, а запоминающее правило remember введет информацию в базу данных посредством одного из двух предикатов:
xpositive (verb,atribute)
xnegative (verb,atribute)
Для записи утверждений используется встроенный предикат assertа. При этом утверждение помещается в начало базы данных (assertz(X) – в конец).
Для того, чтобы очистить базу данных от утверждений последнего диалога, которые могут повлиять на вывод в последующем, используют предикат clear_facts:
clear_facts:-
write("\n\n Please press the space bar to exit \n"),
retractall(_,dbasedom),readchar(_).
Или :
clear_facts:-
retract(xpositive(_,_),fail.
clear_facts:-
retract(xnegative(_,_),fail.
clear_facts:-
write("\n\n Please press the space bar to exit \n"),
readchar(_).
Таким образом поступает приглашение прервать работу с программой, для этого предлагается нажать клавишу пробел. При этом происходит очистка базы данных. При этом используются встроенные предикаты: retract(X) (удаляет утверждение из базы данных сопоставимое с X); retractall(X) (удаляет все утверждения сопоставимые с X).
И, наконец, для запуска программы (для описания цели) используется предикат run. Он описывается двумя правилами. Первое определяет животное, если хватает для этого информации. Второе – срабатывает, если невозможно определить животное.
Таким образом программа производит выбор среди множества гипотез. Сначала каждое животное рассматривается как одна гипотеза. В любой момент времени программа работает только с одной гипотезой. В том случае, если необходимо работать с несколькими гипотезами вводятся меры определенности (вероятности).
Полная версия программы следующая:
database
xpositive(symbol, symbol)
xnegative(symbol, symbol)
predicates
animal_is(symbol)
it_is(symbol)
ask(symbol, symbol, symbol)
remember(symbol, symbol, symbol)
positive(symbol, symbol)
negative(symbol, symbol)
clear_facts
run
clauses
animal_is(cheetah) :- it_is(mammal),
it_is(carnivore),
positive(has, tawny_color),
positive(has, dark_spots).
animal_is(tiger) :- it_is(mammal),
it_is(carnivore),
positive(has, tawny_color),
positive(has, black_stripes).
animal_is(giraffe) :- it_is(ungulate),
positive(has, long_neck),
positive(has, long_legs),
positive(has, dark_spots).
animal_is(zebra) :- it_is(ungulate), positive(has,black_stripes).
animal_is(ostrich) :- it_is(bird),
negative(does, fly),
positive(has, long_neck),
positive(has, long_legs),
positive(has, black_and_white_color).
animal_is(penguin) :- it_is(bird),
negative(does, fly),
positive(does, swim),
positive(has, black_and_white_color).
animal_is(albatross) :-
it_is(bird), positive(does, fly_well).
it_is(mammal) :- positive(has, hair).
it_is(mammal) :- positive(does, give_milk).
it_is(bird) :- positive(has, feathers).
it_is(bird) :- positive(does, fly), positive(does,lay_eggs).
it_is(carnivore) :- positive(does, eat_meat).
it_is(carnivore) :-
positive(has, pointed_teeth),
positive(has, claws),
positive(has, forward_eyes).
it_is(ungulate) :-
it_is(mammal), positive(has, hooves).
it_is(ungulate) :-
it_is(mammal), positive(does, chew_cud).
positive(X, Y) :-
xpositive(X, Y), !.
positive(X, Y) :-
not(xnegative(X, Y)),
ask(X, Y, yes).
negative(X, Y) :-
xnegative(X, Y), !.
negative(X, Y) :-
not(xpositive(X, Y)),
ask(X, Y, no).
ask(X, Y, yes) :-
!, write(X, " it ", Y, '\n'),
readln(Reply),
frontchar(Reply, 'y', _),
remember(X, Y, yes).
ask(X, Y, no) :-
!, write(X, " it ", Y, '\n'),
readln(Reply),
frontchar(Reply, 'n', _),
remember(X, Y, no).
remember(X, Y, yes) :- assertz(xpositive(X,Y)).
remember(X, Y, no) :- assertz(xnegative(X,Y)).
clear_facts :-
write("\n\nPlease press the space bar to exit\n"),
retractall(_, dbasedom), readchar(_).
run :-
animal_is(X), !,
write("\nYour animal may be a (an) ",X),
nl, nl, clear_facts.
run :-
write("\nUnable to determine what"),
write("your animal is.\n\n"), clear_facts.