Прямой цепочки рассуждений.
Управление стратегией вывода с помощью
Часто при анализе какой-либо проблемы используются списки вопросов, позволяющих последовательно уточнить задачу. Если такие структуры заложить в программу, то она не будет ЭС, т. к. мы получим дерево решений, "встроенное" в программу. Однако сам стиль вывода используется в ЭС и называется прямым выводом. Существует несколько крупномасштабных экспертных систем, реализующих такую стратегию:
XCON -система, позволяющая фирме DEC подбирать для клиентов конфигурацию компьютеров VAX, и DENDRAL - знаменитая система химического анализа.
Прямой вывод применим в тех ситуациях, когда число потенциальных
решений неуправляемо, а количество блоков данных, определяющих начальное состояние, невелико.
Например, имеется огромное число способов сборки сложного компьютера из модульных компонентов. Эта сложность возникает в связи с наличием большого числа перестановок плат в гнездах. При каждой перестановке возникают конкретные требования к соединительным кабелям.
Это пример проблемы, имеющей большое пространство решений при малом пространстве входных данных. Входные данные представляют собой просто список компонентов, из которых надо собрать компьютер.
Стратегия прямого вывода должна на основе использования данных и правил привести к правильному заключению. Суть ее состоит в том, что задается последовательность вопросов, построенных таким образом, что каждый из них позволяет отбросить большую группу потенциальных ответов, благодаря чему значительно сужается пространство поиска. Так продолжается до тех пор, пока не останется один определенный ответ. Если на каждом шаге отбрасывается половина возможных ответов, то прямой вывод по эффективности не уступает двоичному поиску.
Проиллюстрируем прямой вывод на постой программе "Птица, зверь
или рыба".
Эта программа использует правила верхнего уровня и механизмы задания вопросов низкого уровня. Механизмы задания вопросов аналогичны версии программы с обратной цепочкой рассуждений. А правила верхнего уровня отличаются.
Суть метода прямой цепочки рассуждений заключается в изобретении вопросов, позволяющих на каждом шаге отбросить большое количество возможных ответов, так что правильный ответ может быть установлен быстро. При этом задаваемые при каждой проверке вопросы целиком зависят от возможных ответов. А различные ответы (т. е. если были задуманы разные животные) подразумевают необходимость использования разных проверок.
Блок-схема, поясняющая алгоритм работы программы выглядит следующим образом:
Рис.15. Базовая схема классификации
Изучение блок-схемы ПЗР с прямой цепочкой рассуждений показывает, что вне зависимости от выбранного маршрута поиска требуется не более 4-х проверок. Это отражено в структуре правил:
guess_animal if find_animal, have_found (X),
write ("Задуманное вами животное - ", X), nl, !.
find_animal
if test1 (X),test2 (X, Y),test3 (X, Y, Z),test4 (X, Y, Z, _), !.
find_animal.
В проверке предусмотрены 4 правила проверки: test1,..., test4. Они должны охватить все, что может выясниться при первой, второй, третьей, четвертой проверках. Например, третья проверка управляет всем, что происходит на глубине 3 шага. Тест test3 представляет собой правило с несколькими предложениями. В зависимости от того, какое из предложений задействовано, могут быть заданы следующие вопросы:
Живет на земле? Live on land?
Имеет полосы? Has stripes?
Имеет щупальца? Has tentacles?
Летает? Does it fly?
Таким образом по мере углубления проверки требуется все больше аргументов для учета результатов предыдущих проверок.
Правила проверки предполагают перечисление всех возможностей. Различные комбинации аргументов в задействованном правиле отражают всю историю вывода до указанного места. Например, test1 может успешно завершиться одним из двух способов:
test1 (m) животное - млекопитающее;
test1 (n) животное - не млекопитающее.
Для теста test2 возможны следующие комбинации значений аргументов:
test2 (m, c) млекопитающее и плотоядное;
test2 (m, n) млекопитающее и не плотоядное;
test2 (n, w) не млекопитающее и плавает;
test2 (n, n) не млекопитающее и не плавает.
Для проверок третьего уровня имеется еще больше возможностей:
test3 (m, c, s) млекопитающее, плотоядное, с полосами;
test3 (m, c, n) млекопитающее, плотоядное, без полос;
test3 (m, n, l) млекопитающее, не плотоядное, живет на суше;
test3 (m, n, n) млекопитающее, не плотоядное, не живет на суше;
test3 (n, w, t) не млекопитающее, плавает, имеет щупальца;
test3 (n, w, n) не млекопитающее, плавает, не имеет щупалец;
test3 (n, n, f) не млекопитающее, не плавает, летает;
test3 (n, n, n) не млекопитающее, не плавает, не летает.
Для test4 имеется меньшее число возможных значений установок для аргумента, поскольку лишь в двух случаях требуется более трех проверок: когда test3 успешно завершается как test3 (m, n, l) или как test3 (n, w, n). Во всех остальных случаях животное уже идентифицировано. Имеем:
test4 (m, n, l, s) млекопитающее, не плотоядное, живет на суше, с полосами
test4 (m, n, l, n) млекопитающее, не плотоядное, живет на суше, без полос
test4 (n, w, n, f) не млекопитающее, плавает, без щупалец, имеет крылья
test4 (n, w, n, n) не млекопитающее, плавает, без щупалец, без крыльев.
Полная структура тестовых правил имеет следующий вид:
test1 (m) if it_is (mammal),!.
test1 (n).
test2 (m, c) if it_is (carnivorous),!.
test2 (m, n).
test2 (n, w) if positive (does, swim),!.
test2 (n, n).
test3 (m, c, s) if positive (has, stripes), asserta (have_found (tiger)),!.
test3 (m, c, n) if asserta (have_found (cheetah)).
test3 (m, n, l) if negative (does, swim),
negative (does, fly),!.
test3 (m, n, n) if asserta (have_found (blue_whale)).
test3 (n, n, f) if positive (does, fly),
asserta (have_found (eagle)),!.
test3 (n, n, n) if asserta (have_found (ostrich)).
test3 (n, w, t) if positive (has, tentacles),
asserta (have_found (octopus)),!.
test3 (n, w, n).
test4 (m, n, l, s) if positive (has, stripes),
asserta (have_found (zebra)),!.
test4 (m, n, l, n) if asserta (have_faund(giraffe)).
test4 (n, w, n, f) if positive (has, feathers),
asserta (have_found (penguin)),!.
test4 (n, w, n, n) if asserta (have_found (sardine)).
Отметим, что проверки проводятся с помощью предикатов it_is, positive, negative, описанных в ПРЗ с обратной цепочкой.
Как возникает окончательный ответ ? Когда при поиске по какому-либо маршруту достигается основание дерева решений, факт, идентифицирующий животное, помещается в базу данных. Например, последний предикат в правиле test3 (m, c, s). Это означает, что искомое животное - тигр. Позднее помещенный в базу данных этот факт будет использован в качестве ответа.
Далее, правило find_animal требует выполнения всех четырех проверок, хотя иногда требуется всего лишь три. Эксперименты с программой показывают, что в некоторых случаях основание дерева достигается на уровне test3, и в базу данных помещается ответ. Однако, правило find_animal, продолжая свою "работу", пытается удовлетворить test4, что невозможно.
Это не имеет большого значения, так как мы уже поместили ответ в такое место, откуда сможем его получить. Система возвращается назад и успешно выполняет второе предложение правила find_animal. Затем другие части правила guess_rule обеспечивают распечатку ответа.
5.3.Сравнение двух стратегий вывода.
Программный код, используемый для структуры с обратной цепочкой рассуждений, выполнен по принципу "сверху-вниз" или "от цели". Это связано с тем, что именно цель определяет структуру правила высшего уровня. Точно так же можно объяснить и принцип "сверху-вниз" - в проекте прежде всего нужно сосредоточиться на том, чего мы хотим достичь, т. е. сформулировать цели, и уж затем представить их в виде иерархии более простых задач.
Прямая цепочка иногда называется суждением "снизу-вверх" или от данных. Она предусматривает работу с данными, а не с какой-либо целью или гипотезой.
Проведение опроса в обеих стратегиях оправдано. В прямой цепочке число вопросов может быть меньше, но они могут показаться пользователю непонятными (необычными). При использовании обратной цепочки:
число вопросов больше, но сама модель выглядит более понятной.
Выводы:
1. Программный код с обратной цепочкой более ясный. Все правила хорошо читаются. Они соответствуют интуитивному представлению человека о том, как описывать предметы, являющиеся частью иерархии.
2. Этот программный код легче модифицировать и расширять. Для того, чтобы добавить в структуру еще одно животное, его достаточно определить. При использовании прямой цепочки для этого необходимо переделывать все правила.
3. Встроенный механизм вывода языка Пролог также использует обратный вывод, поэтому программный код с обратной цепочкой легче развивать.