В самых общих чертах алгоритм выполнения иерархического построения и проверки гипотез (НАТ-алгоритм) может быть представлен следующим образом. Предположим, имеется дерево гипотез, которые могут быть активизированы на основе части имеющихся данных. Активизированные гипотезы предполагают наличие и других данных, помимо тех, что были использованы для их отбора, которыми мы можем располагать или которые можно дополнительно затребовать.
НАТ-алгоритм
(1) Считать исходные данные.
(2) Для каждой исследуемой гипотезы сформировать оценку, которая показывает, какая часть исходных данных учитывается этой гипотезой.
(3) Определить ту гипотезу (узел) л, которая имеет наивысшую оценку.
(4) Если п— терминальный узел, то завершить выполнение алгоритма. В противном случае выделить в пространстве гипотез два подпространства К и L Подпространство К должно содержать дочерние узлы п, а подпространство L — узлы-конкуренты п на том же уровне дерева.
(5) Собрать дополнительные данные, которые можно использовать для анализа гипотез в подпространстве К, и провести оценку гипотез на основе этих дополнительных данных. Пусть k— наивысшая оценка гипотез из К, а l— наивысшая оценка гипотез из L
(6) Если k выше, чем /, то положить п = k. В противном случае положить n = /.
(7) Перейти к п. 4.
13.2. Структурированные объекты в CENTAUR
Для того чтобы понять алгоритм работы программы CENTAUR, нужно хотя бы в общих чертах представлять себе ту предметную область, на которую ориентирована эта программа. CENTAUR выполняет практически те же задачи, что и разработанная ранее система PUFF (см. [Кит et al, 'I978J, [Aikins et al., 1984]}. Система PUFF предназначалась для диагностики нарушения работы дыхательных органов. В качестве исходных данных, как правило, использовались результаты анализа объема выдыхаемого воздуха и скорость движения воздуха при выдохе (этот анализ выполняется с помощью спирографа).
13.2.1. Структура фреймов в CENTAUR
Основная идея, положенная в основу системы CENTAUR, состоит в том, что фреймо-подобные структуры обеспечивают явное представление предметной области, которое может быть использовано для формирования суждений с помощью порождающих правил. Такое описание предметной области позволяет разделить стратегические знания о том, как управлять процессом формирования суждений, и ситуационные знания о том, какой вывод можно сделать из имеющегося набора фактов. Теоретически это позволит отделить ситуационные знания, специфичные для конкретной предметной области, а значит, создать систему, которую можно будет приспособить для работы в разных областях.
При таком подходе порождающие правила могут быть просто включены в структуру фрейма в качестве значения одного из слотов. Связывание правил со слотами фрейма создает возможность организации единого механизма функционирования правил на основе естественного группирования. Другие слоты в данном фрейме образуют в явном виде контекст применения правила.
В CENTAUR используются три типа фреймоподобных структур: прототипы, компоненты и факты. Из 24 прототипов двадцать один представляет определенные заболевания органов дыхания, один — знания, общие для всех заболеваний этого вида, а еще два — знания, в определенной мере независимые от предметной области. Это знания о том, как запустить консультирующую программу и просмотреть имеющиеся свидетельства. Таким образом, знания организуются вокруг самих диагностических категорий. Альтернативный вариант, используемый в большинстве других систем, — заложить эти знания в неявной форме в набор неструктурированных правил.
Прототипы в программе CENTAUR содержат знания и объектного, и метауровня. Из них организована сеть, фрагмент которой представлен на рис. 13.1. Верхний уровень иерархии занимает прототип CONSULTATION (консультация), который управляет всеми стадиями процесса проведения консультаций (ввод исходных данных, активизация гипотез и т.п.). Затем следует слой прототипов, представляющих определенные патологические состояния, такие как RESTRCTIVE LUNG DESEASE (легочные заболевания), OBSRTUCTIVE AIRWAYS DESEASE (заболевания верхних дыхательных путей) и т.п. И на самом нижнем уровне категории заболеваний разделяются, во-первых, на конкретные заболевания, а во-вторых, по степени остроты. Так, категория заболеваний верхних дыхательных путей (OBSRTUCTIVE AIRWAYS DESEASE) может быть разделена на подкатегории MILD (мягкие), MODERATE (умеренные), MODERATELY SEVERE (умеренной остроты) и SEVERE (острые). А конкретные виды заболеваний, представленные на этом уровне, — ASTHMA (астма), BRONCHITIS (бронхит) и EMPHYSEMA (эмфизема).
Каждый прототип имеет слоты для некоторого набора компонентов, которые содержат указатели на субфреймы знаний на объектном уровне. В каждом прототипе заболеваний органов дыхания существуют слоты, представляющие результаты анализов легких, причем каждый из этих слотов также является фреймом с собственными правами и собственной внутренней структурой. Например, фрейм OBSRTUCTIVE AIRWAYS DESEASE (заболевания верхних дыхательных путей) включает 13 компонентов, каждый из которых имеет собственное наименование, характеризуется диапазоном допустимых значений и степенью (мерой) важности. В дополнение к этому фрейм компонента часто содержит специальный слот, называемый "inference rules" (правила вывода), в котором хранятся порождающие правила формирования логического вывода на основе значения этого компонента. Если компонент не содержит такого рода правил или правило по каким-либо причинам не может обработать значение компонента, программа обращается с вопросом к пользователю. Такую меру предосторожности в отношении набора правил можно рассматривать как процедурную связь определенного вида. Процедурная связь обычного вида потребовала бы включение в программу довольно значительного по объему фрагмента LISP-кода.
Факты, с которыми работает программа, представляются фреймами, каждый из которых имеет шесть слотов. В них содержится информация о наименовании параметра, его значении, степени достоверности, источнике, классификации и обоснованности.
Помимо знаний, специфичных для предметной области, в прототипах имеется и управляющий слот. В нем представлены знания метауровня о том, как использовать этот структурный элемент знаний. Этот слот содержит LISP-выражения, предназначенные для
конкретизации прототипа— установки множества компонентов, значения которых должны быть определены;
реагирования на подтверждение или отклонение прототипа; реакция программы заключается в том, что задается множество прототипов, которые следует активизировать на следующем шаге;
вывода сообщения, в котором приводится окончательное заключение.
Каждый управляющий слот можно рассматривать как консеквентную часть правила, условная часть которого сопоставима с ситуацией, описанной компонентами прототипа
13.2.2. Правила, включенные в прототипы
Нелишне напомнить, что именно компоненты прототипа представляют большую часть знаний объектного уровня, специфичных для определенной предметной области, поскольку в структуре этого типа содержится информация о лабораторных исследованиях, результаты которых должны быть использованы при диагностировании того или иного конкретного заболевания. Эти компоненты являются значениями слотов прототипов, представляющих заболевания, и в то же время имеют собственную внутреннюю структуру и являются прототипами со своими собственными правами. Таким образом, оказывается, что в составе прототипа имеются не только порождающие правила, но и другие прототипы. Можно с полным правом утверждать, что система прототипов имеет по крайней мере двухмерную организацию в дополнение к иерархической организации, представленной в явном виде в терминах типов и подтипов заболеваний. Структуры данных, которые могут быть включены сами в себя, принято называть рекурсивными.
В CENTAUR используется пять типов правил.
Правила логического вывода. Связаны с компонентами, представляющими клинические параметры, и задают возможные способы определения их значений.
Правила активизации. Это антецедентные правила, связанные с клиническими параметрами, которые служат для выдвижения прототипов в качестве гипотез с некоторой степенью правдоподобности.
Правша обработки остаточных фактов. После того как система придет к какому-нибудь заключению в форме набора подтвержденных прототипов, эти правила стараются оценить, как это заключение согласуется с фактами, неучтенными при формировании заключения (остаточными фактами).
Уточняющие правила. Эти правила предполагают проведение дополнительных лабораторных анализов. После выполнения этих правил будет сформировано окончательное множество прототипов с указанием, какой из них учитывает тот или иной из имеющихся фактов, причем каждый факт должен быть учтен по крайней мере одним прототипом.
Правша вывода. Эти правила переводят информацию, представленную в прототипах, на "человеческий" язык и представляют ее пользователю.
Другие слоты содержат обычную информацию, необходимую для учета, — имя автора, сведения об источнике информации и о текущей ситуации, которые затем используются при формировании объяснения, почему данный прототип был активизирован.
Как видно, в системе CENTAUR в основу классификации правил положены функции, выполняемые с их помощью. В системе PUFF, реализованной на базе оболочки EMYCIN, все правила считаются правилами логического вывода, хотя многие из них и не имеют непосредственного отношения к логическому выводу. Например, большая группа правил предназначена для сбора информации, используемой в качестве свидетельств, или для установки значений по умолчанию. Кроме того, контекст применения правил в CENTAUR представлен в явном виде, поскольку правила являются значениями слотов. Например, в системе PUFF правила для оценки значений клинических параметров индексированы по наименованию параметра, которое появляется в консеквентной части правила, т.е. использован тот же принцип, что и в системе MYCIN. В системе CENTAUR правила оценки определенных параметров хранятся в виде значения одного из слотов в прототипе компонента, представляющего этот параметр, и применяются только в контексте этого прототипа, т.е. в том случае, если прототип активизирован.
Ниже, в главе 18, будет показано, что дальнейшее углубление такого "распределенного" подхода к организации порождающих правил приводит к созданию нового класса систем, получивших название систем с доской объявлений (blackboard systems). Но уже на опыте эксплуатации системы CENTAUR исследователи убедились в преимуществах явного связывания правил с контекстом их применения. Это не только упрощает процесс программирования экспертной системы, но и помогает при формировании объяснений, почему в конкретной ситуации были использованы определенные правила (более подробно об этом — в главе 16).
