Методы поиска в иерархии пространств

Если пространство поиска не только бесконечно или слишком велико, но и сложно организовано, метод «генерация-проверка» применить ко всему пространству поиска как единому целому часто невозможно. В таких случаях стремятся пространство поиска разбить тем или иным способом на ряд подпространств приемлемого размера и сложности, допускающих применение тех или иных методов поиска в одном пространстве. Наглядным примером такого поиска может служить задача прокладки маршрута движения из одного пункта в другой, при решении которой сначала определяется последовательность промежуточных пунктов, маршруты между которыми затем уточняются с помощью карт более мелкого масштаба.

Поиск в факторизуемых пространствах. Пространство поиска называют факторизуемым, если оно разбивается на непересекающиеся подпространства (области поиска, классы) частичными (неполными) решениями. Примерами действующих систем, в которых реализован этот способ поиска, являются системы Heuristic DENDRAL и Meta-DENDRAL, предназначенные для определения структуры химических молекул по масс-спектрограммам. Необходимость в создании этих систем обусловлена тем, что человеку очень трудно представить себе по масс-спектру структуру молекулы, включающей от 100 до 300 элементов.

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

Во время фазы планирования DENDRAL по масс-спектрограмме выдает списки нужных и запрещенных оснований (хороший список –GOODLIS и плохой список – BADLIST), классифицирующие вещество с помощью знаний по масс-спектрографии, закодированных в форме продукций.

Многие из правил-продукций планировщика весьма эффективно сужают область поиска, не только ограничивая поиск типом соединения, но и количественными характеристиками. Например, знание о том, что спектр содержит 8С, 16Н, 1О, сокращает число возможных структур с 698 до 3, так как в список BADLIST будут занесены все структуры, кроме содержащих этил-кетон-3.

Генератор структур в DENDRAL работает в составе системы, но может использоваться и автономно в диалоге с химиком, предоставляя ему информацию и возможность задавать дополнительные ограничения трех типов: графические (исключить заданного типа структуры); синтаксические (исключить неправдоподобные по валентности структуры); семантические (учесть данные, полученные в других проверках).

Возможности этой системы были проверены путем использования порожденных ею правил для предсказания масс-спектров новых молекул. Система не только повторно открыла уже известные правила масс-спектрометрии для двух классов молекул, но и неизвестные для трех родственных семейств структур.

Возможности факторизации пространства поиска в данном случае обусловлены спецификой предметной области, поскольку тот или иной набор признаков, характеризующих масс-спектр молекулы, резко сужает возможный состав соответствующего множества топологических структур молекулы.

Ассоциативный и каузальный поиск решения. Основные замечания в адрес систем MYCIN и PROSPECTOR состояли в следующем:

а) отсутствие прямого моделирования стратегий рассуждений, используемых экспертами, что снижает доверие к заключениям;

б) отсутствие использования знаний, заложенных в причинно-следственных (каузальных) отношениях, что снижает достоверность заключений.

Иначе говоря, ставился вопрос о построении причинно-следственной модели объекта экспертизы (в данном случае – заболевания) и о воспроизведении на ее основе человеческого способа рассуждений, осуществляемых специалистом. Без осознаваемых пользователем картины заболевания и причинно-следственных связей между рассматриваемыми явлениями ему сложно понять и, значит, поверить в даваемые ему системой рекомендации.

В некоторых системах эти вопросы были частично решены введением метаправил, формирующих для пользователя как бы обобщенную картину рассуждений. В системах INTERNIST и CASNET были предприняты попытки решить эти проблемы прямым способом.

Система INTERNIST разработана в Питтсбургском университете (США). Прототип создан в 1974 году и с тех пор совершенствуется и используется. Создана и новая версия этой системы (CADUCEUS). Одно из замечательных свойств этой системы состоит в том, что процесс постановки диагноза явно приближается к модели человеческого мыслительного процесса, позволяя тем самым установить взаимосвязь между конкретными болезнями (причинами) и их проявлениями. Система INTERNIST решает только задачу постановки диагноза, но не лечения. Процесс постановки диагноза включает две стадии:

а) ограничение пространства диагностирования путем выбора правдоподобных гипотез о возможных заболеваниях (дифференциальная модель диагностирования);

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

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

Знания о заболеваниях в системе INTERNIST представлены деревом заболеваний (его фрагмент показан на рис. 4.5). Уровни дерева заболеваний связаны между собой отношением тип-разновидность.

Рис. 4.5. Фрагмент «дерева заболеваний» системы INTERNIST

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

В результате ввода данных о симптомах порождаются модели заболевания, используемые как гипотезы. Модель порождается добавлением четырех списков:

а) симптомы наблюдаемые, но не относящиеся к заболеванию;

б) симптомы не зарегистрированные, но которые должны быть;

в) симптомы наблюдаемые и относящиеся к заболеванию;

г) симптомы ожидаемые, но не зарегистрированные.

Каждая модель оценивается по значимости и планируется дальнейшая постановка диагноза с учетом класса симптомов.

Система CASNET (Causal ASsociational NETwork) разработана в первой половине 70-х годов в Рутгерском университете (США) для исследования стратегий диагностирования на основе психологических и функциональных моделей заболеваний. В качестве предметной области при разработке этой системы была выбрана глаукома из-за ее локальности и относительной структурной простоты.

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

Знания в CASNET представляются четырьмя слоями, три из которых описывают собственно болезнь, а четвертый – схемы ее лечения. Центральное место в модели болезни занимает описание патофизиологических состояний в форме семантической сети. Узлами сети представлены физиологические состояния, а дугами – причинные связи и переходы между состояниями заболевания. Маршрут от начального до конечного состояния отражает полный цикл течения болезни (по нарастанию). Ниже слоя описания патофизиологических состояний находится слой наблюдений, связанный со слоем состояний ассоциативными связями. Здесь узлами сети являются симптомы и наблюдения, по отдельности или совокупно ассоциирующиеся с патофизиологическими состояниями. Выше слоя описания патофизиологических состояний находится слой категорий заболеваний, связанный с патофизиологическими состояниями классификационными связями. Через категории заболеваний патофизиологические состояния связываются со схемами лечения, способ реализации которых уточняется по данным из слоя наблюдений. Причинным, ассоциативным и классификационным связям приписываются весовые коэффициенты.

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

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

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

Таким образом, система INTERNIST является примером поиска решения по байесовскому принципу – путем выдвижения гипотез на основе введенных данных о пациенте с последующей их оценкой с использованием дополнительных симптомов. Заболевание здесь рассматривается в виде статичной категории и диагноз представляется как отнесение пациента к одной или нескольким категориям. Хотя такой подход и позволяет эффективно идентифицировать заболевания, он не дает представления о развитии заболевания и, значит, не дает убедительного объяснения выдаваемым заключениям.

Примененный в системе CASNET подход имеет ряд своих преимуществ:

а) представление процесса заболевания в явном виде позволяет отслеживать состояния пациента в процессе заболевания, и значит, анализировать реакции на лечение;

б) каузальные маршруты, завершающиеся на подтвержденных состояниях, дают объяснение диагноза, а неподтвержденные состояния указывают на возможное развитие болезни;

в) каузальные маршруты не только делают объяснения системы понятными для клинициста, но и повышают достоверность идентификации, ибо динамика намного информативнее статики.

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

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

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

Контрольные вопросы и задания

1. Что такое префиксная нормальная форма и для чего формулы ИП преобразуют в эту форму?

2. Перечислите по порядку шаги процесса преобразования произвольной формулы ИП в эту форму.

3. Что такое функция Сколема и для чего осуществляется сколемизация префиксной нормальной формы формулы ИП?

4. Изложите правило введения функций Сколема в формулу ИП.

5. Что такое клаузальная форма формулы ИП? Как связана клаузальная форма с конъюнктивной нормальной формой (КНФ)?

6. Как формулируется задача в ИП и к чему сводится ее решение? Как формулируется задача в ИП для ее решения методом «от противного»?

7. Что такое резолюция? Опишите последовательность действий при решении задачи ИП методом резолюций. Нарисуйте блок-схему алгоритма решения задачи ИП методом резолюций.

8. Свяжите решение задачи ИП методом резолюций с преобразованием КНФ формулы ИП в дизъюнктиную нормальную форму (ДНФ). Что будет получено в результате этого преобразования, если применение метода резолюций приводит к пустой резольвенте?

9. Объясните, для чего нужны преобразование формулы ИП в префиксную нормальную форму, сколемизация этой формы, преобразование в клаузальную нормальную форму с точки зрения подготовки применения метода резолюций.

10. Опишите процесс преобразования предложений клаузальной нормальной формы в предложения Хорна.

11. Как в виде предложений Хорна представляются запрос, правило и факт? Как записываются запрос, правило и факт в языке Пролог?

12. Что такое дизъюнктивно-конъюнктивное дерево (ДК-дерево)? В каком случае вершины, дочерние данной вершине, связываются конъюнкцией, а в каком случае – дизъюнкцией?

13. Как следует понимать каждый из случаев предыдущего пункта при декларативном и императивном (процедурном) толковании правил, представленных ДК-деревом?

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

15. Напишите программу на языке Турбо-Пролог, осуществляющую поиск вариантов выполнения заказа на обед, сформулированного в терминах «первое блюдо», «второе блюдо», «третье блюдо» с использованием категорий «мясное», «рыбное», «овощное», при заданном пользователем программы ограничении на суммарную стоимость обеда. Содержание ресторанного меню представьте в программе как набор фактов.

16. Что необходимо, чтобы организовать поиск решения на построенном вами ДК-дереве в безвозвратном и в пробном режимах управления (с возвращением и с поиском на графе)? Выберите и обоснуйте наиболее подходящий для данного случая режим управления поиском с учетом затрат на выбор правила и на управление.

17. Как можно организовать решение задачи, изложенной в предыдущих двух пунктах, путем двустороннего поиска – одновременно в прямом и обратном направлениях?

18. Является ли система продукций для решения задачи, изложенной в предыдущих трех пунктах, разложимой? Если нет, то можно ли сделать ее разложимой, поделив заранее расходы на обед между первым, вторым и третьим блюдами?

19. Охарактеризуйте особенности ПО, особенности знаний о ПО, особенности задачи, рассматривамой в предыдущих четырех пунктах по признакам и уровням их сложности.

20. Отнесите метод поиска, примененный в пунктах 15 и 16, к соответствующей категории и обоснуйте ваш ответ:

– методы поиска в одном пространстве;

– методы поиска в иерархии пространств;

– методы поиска в условиях неопределенности;

– методы поиска в динамических пространствах;

– методы поиска на основе нескольких моделей.

21. В чем состоит принципиальное отличие ДК-дерева, используемого для поиска в пространстве состояний, от ДК-дерева, используемого для поиска методом редукции?

22. Что выступает в качестве решения задачи на ДК-дереве, используемом для поиска в пространстве состояний, и что – на ДК-дереве, используемом для поиска методом редукции?

23. Какой из упомянутых в предыдущих двух пунктах методов вы использовали для решения задачи о ресторанном заказе? Обоснуйте ваш ответ.

24. Можно ли истолковать ваш метод решения задачи о ресторанном заказе как реализацию метода генерация-проверка? Почему?

25. Можно ли пространство поиска при решении задачи о ресторанном заказе представить в виде иерархии подпространств? Попробуйте применить для этого иерархию видов блюд либо их категорий по стоимости.

26. Можно ли факторизовать пространство поиска при решении задачи о ресторанном заказе? Обоснуйте ваш ответ. По каким признакам это следует сделать, если факторизация возможна?

27. Проанализируйте принципы организации и работы систем INTERNIST и CASNET с точки зрения решаемых задач (целей), применяемых методов поиска и сокращения перебора при поиске решений.

5. Приобретение знаний [10, 11]

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

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

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

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

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

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

В этом разделе рассматривается сценарий процесса приобретения знаний и определяются главные моменты в этом процессе, обсуждаются доступные сегодня средства формирования знаний и исследуются направления и перспективы автоматизации приобретения знаний.