Методы и средства верификации баз знаний в интегрированных экспертных системах

Смирнов, Виталий Валерьевич

Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

кандидата технических наук: Смирнов, Виталий Валерьевич
город: Москва
год: 2006
специальность ВАК РФ: 05.13.11

Диссертация по информатике, вычислительной технике и управлению на тему «Методы и средства верификации баз знаний в интегрированных экспертных системах»

Автореферат диссертации по теме "Методы и средства верификации баз знаний в интегрированных экспертных системах"

На правах рукописи

Смирнов Виталий Валерьевич

МЕТОДЫ И СРЕДСТВА ВЕРИФШСАЦИИ БАЗ ЗНАНИЙ В ИНТЕГРИРОВАННЫХ ЭКСПЕРТНЫХ СИСТЕМАХ

05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

Москва-2006

Работа выполнена в Московском инженерно-физическом институте (государственном университете)

Научный руководитель: доктор технических наук, доцент

Рыбина Галина Валентиновна

Официальные оппоненты: доктор технических наук, профессор

Фоминых Игорь Борисович

кандидат физико-математических наук Аверкин Алексей Николаевич

Ведущая организация: Московский энергетический институт

(технический университет)

Защита состоится « 8 » ноября 2006 г. в 15 час. 00 мин. на заседании диссертационного совета Д 212.130.03 в МИФИ по адресу: 115409, г. Москва, Каширское шоссе, дом 31.

С диссертацией можно ознакомиться в библиотеке МИФИ. Автореферат разослан «(¡£> октября 2006 г.

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

Учёный секретарь диссертационного совета

Шумилов Ю.Ю.

¿006/L

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

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

Значительный вклад в исследование и решение проблем построения экспертных систем и ИЭС в целом внесли отечественные учёные О.И.Ларичев, Д.А.Поспелов, Э.В.Попов, Г.С.Осипов, Г.В.Рыбина, А.П.Еремеев, И.Б.Фоминых, Т.А.Гаврилова, "В.Ф.Хорошевский, В.Л.Стефанюк, Н.Г.Яруш-кина, В.Б.Тарасов, А.Н.Аверкин, А.С.Нариньяни и др., а также целый ряд зарубежных учёных P. Jackson, F.Hayes-Roth, D.Waterman, T.Nguyen, A.Preece, F.Coenen, J.Tsai, PMeseguer, J.Vanthienen и др.

Диссертационное исследование посвящено решению проблемы верификации баз знаний в рамках задачно-ориентнрованной методологии автоматизированного построения прикладных ИЭС, предложенной Г.В. Рыбиной в середине 90-х годов, и созданной на ее основе автоматизированной технологии, включающей инструментарий нового поколения - программный комплекс АТ-ТЕХНОЛОГИЯ.

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

Однако, адекватных методов и средств верификации баз знаний в прикладных ИЭС в настоящее время практически не существует, поэтому диссертация посвящена исследованию проблемы верификации баз знаний в ИЭС и разработке программных средств, предназначенных для автоматизации процессов обработки недостоверной и ошибочной информашн^щ^щ^^ЩЩ^Для таких систем базах знаний. ^ р£.!'■»

С.-Петербур! ОЭ

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

Для достижения поставленной цели в диссертации решены следующие основные задачи.

1. На основе анализа существующих методов и средств верификации баз знаний экспертных систем построена обобщенная модель обнаружения аномалий в базах знаний экспертных систем.

2. Разработаны методы обнаружения статических и динамических аномалий в поле знаний и базе знаний ИЭС, предусматривающие совместную обработку неопределенных, неточных и нечетких знаний.

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

4. Разработаны инструментальные программные средства верификации поля знаний и базы знаний, включенные в состав комплекса АТ-ТЕХНОЛОГИЯ третьего поколения.

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

Объект и предмет исследования. Объектом исследования являются интегрированные экспертные системы. Предметом исследования являются методы верификации поля знаний и базы знаний в интегрированных экспертных системах.

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

Научная новизна. В диссертации получены следующие новые результаты.

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

2. Разработан оригинальный метод обнаружения статических аномалий в поле знаний и базе знаний ИЭС, позволяющий учитывать случаи одновременного присутствия неопределенных, неточных и нечетких знаний.

3. Разработан оригинальный метод обнаружения динамических аномалий в поле знаний и базе знаний ИЭС, который предусматривает совместную обработку неопределенных, неточных и нечетких знаний.

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

5. Созданы оригинальные инструментальные программные средства верификации поля знаний и базы знаний в ИЭС.

б. Разработан «мастер» автоматизированной корректировки поля знаний и базы знаний, использующий данные протокола верификации об обнаруженных статических аномалиях в поле знаний и базе знаний в процессе построения ИЭС.

Основные научные результаты, выносимые на защиту.

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

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

3. Оригинальный подход к построению и исполнению плана верификации поля знаний, основанный на комбинированном использовании критериев охвата и метазнаний.

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

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

Разработанные в диссертации инструментальные программные средства верификации поля знания и базы знаний в составе комплекса АТ-ТЕХНОЛОГИЯ использованы при разработке отдельных компонентов для нескольких ИЭС, что подтверждается актами об использовании.

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

Реализация результатов диссертации. Разработанные инструментальные программные средства верификации и корректировки поля знаний и базы знаний в ИЭС включены в состав инструментального комплекса АТ-ТЕХНОЛОГИЯ третьего поколения и обеспечивают программную поддержку этапов верификации и корректировки поля знаний и базы знаний в жизненном цикле построения ИЭС.

Разработанные инструментальные программные средства верификации и корректировки поля знаний и базы знаний использованы при создании исследовательского прототипа ИЭС для проектирования и моделирования корпоративных информационно-вычислительных сетей, применяемого в исследованиях и разработках ФГУП «Концерн Системпром» (акт об использовании). Это по-

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

Метод и алгоритмы обнаружения статических аномалий использованы при разработке компонента анализа целостности и согласованности медицинских знаний в области эндоскопии, который входит в состав программных средств, обеспечивающих выполнение задач накопления медицинских знаний в рамках поддержки элементов «электронной истории болезни» в эндоскопическом отделении ЦКБ Гражданской авиации (акт об использовании).

Созданные инструментальные средства в составе комплекса АТ-ТЕХНОЛОГИЯ использовались в учебном процессе Московского инженерно-физического института (МИФИ) и Российского Государственного социального университета (РГСУ) (акт о внедрении), а также при создании разделов учебного пособия «Инструментальный комплекс АТ-ТЕХНОЛОГИЯ для поддержки разработки интегрированных экспертных систем» (авторы Рыбина Г. В., Пыша-гин С. В., Смирнов В. В., Левин Д. Е., Душкин Р. В., М.: МИФИ, 2001).

Апробация результатов. Основные результаты диссертации докладывались и обсуждались на национальных конференциях по искусственному интеллекту (Переславль-Залесский, 2000; Коломна 2002), Международном семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2005), ежегодных «Научных сессиях МИФИ» с 1998 по 2006 гг.

Публикации. Основные результаты диссертации опубликованы в шести печатных трудах, в том числе в одной статье в журнале, включённом ВАК РФ в перечень ведущих рецензируемых научных журналов и изданий.

Структура и объём работы. Диссертация состоит из введения, четырёх разделов, заключения, списка использованной литературы (125 наименований) и приложений. Основная часть диссертации содержит 141 страницу машинописного текста, включая 42 рисунка, 24 таблицы.

Содержание работы

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

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

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

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

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

В целом современные методы обнаружения логических ошибок в базах знаний ориентированы в большей степени не на выявление конкретных ошибок, а на обнаружение логических аномалий, каждая из которых является признаком появления ошибок, относящихся к отдельной группе. В выполненных до настоящего времени исследованиях в области верификации баз знаний используются несколько отличающиеся друг от друга классификаций аномалий, предложенных А. Ргеесе, F. Coenen, J.Vanthienen и др. Однако, как правило, различают статические аномалии, проявляющиеся в отдельных правилах или при их сравнении, и динамические аномалии, проявляющиеся в цепочках правил.

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

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

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

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

учитывающих случаи представления в базах знаний экспертных систем НЕфакторов знаний (термин НЕ-факторы впервые введен А.С.Нариньяни в середине 80-х годов). Показано, что такие случаи учитываются все еще не достаточно полно, причем у исследователей не выработано единого взгляда на природу и способы проявления знаний, содержащих НЕ-факторы (исключением является НЕ-фактор нечеткость, для которого в настоящее время существует более или менее универсальное определение).

Рис. 1. Классификация аномалий в базах знаний экспертных систем.

Поэтому одним из проявлений этой проблемы является довольно узкая направленность методов верификации баз знаний с точки зрения учета конкретных видов НЕ-факторов знаний. Наиболее развитыми являются методы верификации, ориентированные на базы знаний, содержащие неопределенные знания (например, предложенные в работах Т. Nguyen, P.Meseguer и др.), или предназначенные для баз знаний, в которых присутствуют нечеткие знания (например, предложенные в работах S.J.H.Yang, J. В. Vanthienen и др.). При

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

В диссертации было показано, что с ростом объемов создаваемых баз знаний возникает проблема «комбинаторного взрыва», которая наиболее ощутима в алгоритмах обнаружения динамических аномалий, обладающих экспоненциальной временной вычислительной сложностью по отношению к количеству правил. Однако, предложенные на сегодня способы сокращения количества анализируемых комбинаций, среди которых наиболее распространенные основаны на индексации правил, включающей разбиение на кластеры (например, системы IMVER, EZ-Xpert и др.), и использовании метазнаний (проект VALID и др.), как-правило, определяются особенностями конкретных видов внутреннего представления знаний.

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

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

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

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

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

• реализация процессов обнаружения основных групп аномалий, включая, с одной стороны, нарушения целостности и согласованности, а с другой - статические и динамические аномалии;

• осуществление поиска аномалий для случаев, когда поле знаний или база знаний содержат неопределенные, неточные и нечеткие знания;

• со1фащение количества анализируемых комбинаций при обработке больших объемов информации;

• использование информации о выявленных аномалиях для улучшения поля знаний или базы знаний проектируемых ИЭС;

• поддержка функций обнаружения аномалий как в поле знаний, так и в базе знаний прикладных ИЭС, построение которых осуществляется средствами комплекса АТ-ТЕХНОЛОГИЯ.

Сформулирована цель и поставлены конкретные задачи диссертационного исследования.

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

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

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

Объект^10, NameO, Ь),где 10 - порядковый номер объекта, NameO - имя объекта, L - список атрибутов, причем атрибут объекта представлен в виде: Атрибут(1А, NameA, Туре), где IA - порядковый номер атрибута, NameA - имя атрибута, Туре - тип атрибута, который имеет вид: Twj(IT,NameT,U), где IT -номер типа атрибута, NameT - имя типа атрибута, U - список конкретных значений атрибута, либо интервал значений, определяемый максимальным и минимальным значениями атрибута.

IIpaewioQRJnc,Cons), где IR - порядковый номер правила, Inc - посылка правила, которая содержит список утверждений (пар типа «атрибут-значение»), связанных между собой логическими отношениями конъюнкции и дизъюнкции, Cons - действие правила, которое содержит список утверждений, т.е. атрибутов с присваиваемыми им значениям.

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

Так, для представления неопределенных знаний с утверждениями связывается коэффициент уверенности t е [0,1] или интервал уверенности [tl,t2] tl,t2 е [0,1], а представление неточных знаний обеспечивается за счет привязки к утверждениям коэффициентов относительной погрешности числовых значений t е [0,1].

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

Поле знаний в задачно-ориентированной методологии построения ИЭС играет важную роль, обеспечивая, с одной стороны, внутреннее представление основных понятий и отношений проблемной области, выявленных из системы

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

В данном случае рассматривался язык представления знаний инструментального комплекса АТ-ТЕХНОЛОГИЯ, важной особенностью которого является возможность представления неопределенных, неточных и нечетких знаний. В случае представления неопределенных знаний утверждения в посылках и действиях правил снабжаются коэффициентами уверенности, а именно: ОБЪБКТ1.АТРИБУТ1 = "Значение!" УВЕРЕННОСТЬ Коэффициент] ОБЪЕКТ2.АТРИБУТ2= "Значений" УВЕРЕННОСТЬ [Коэффициент2, КоэффициентЗ] Для представления неточных знаний утверждения в правилах содержат коэффициенты относительной погрешности и имеют следующий вид: ОБЪЕКГЗ.АТРИБУТЗ= "ЧисловоеЗначение" ТОЧНОСТЬ Коэффициент4 Кроме того, в посылках правил в утверждениях с числовыми атрибутами наряду с операцией '=' могут использоваться и другие операции сравнения.

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

ОБЪЕКТ4.АТРИБУТ4= "ЗначеииеЛингвистическойПеременной" ЗначениеЛингвистическойПеременной: {(х1,ц1),(х2,ц2),...,(хп,цп)} Опишем теперь разработанные методы обнаружения аномалий, отметив при этом, что для внутреннего представления анализируемой информации как поля знаний, так и базы знаний в диссертации использованы единые формализмы, поэтому обработка поля знаний и базы знаний выполняется на основе одних и тех же представленных ниже методов.

Для обнаружения аномалий нарушений целостности и статической несогласованности в поле знаний и базе знаний в диссертации разработан метод, в рамках которого внутреннее представление знаний основано на таблицах решений. В традиционных методах обнаружения статических аномалий, основанных на табличном представлении информации (в частности, Т. Nguyen, В J.Cragun, HJ.Steudel, J.Vanthienen и др.), значения в ячейках таблицы решений могут быть неопределенными, истинным или ложньм в зависимости от используемых в правилах утверждений. В разработанном в диссертации методе применяется расширенная таблица решений (РТР), в ячейках которой располагаются числовые коэффициенты, что позволяет учитывать случаи, когда в поле знаний или в базе знаний одновременно представлены неопределенные, неточные и нечеткие знания, а также случаи, когда утверждения в правилах представляют собой ограничения на числовые значения атрибутов (содержат операции сравнения).

РТР определяется пятеркой вида РТР = <R, AV, Р, S, W>, где R= {Rg}, g=l,..,kl - множество правил;

AV={AVq}, q=l,.., k2 - множество пар «атрибут-значение», участвующих в правилах, AVq=<Aq, V^, Aq-конкретный атрибут, Vq - одно из значений атрибута А<,;

Р = <Pins, Pcons> - множество утверждений в правилах, причем Pins = {Рго}, m=l,..,k3 - множество утверждений в посылках правил, Рт= <AYqra,Tm>-конкретное утверждение, AVqm 6 AV, Tm - множество коэффициентов, приписываемых AVqm в утверждении Pm; Peons = {Р„}, n=l,..,k4 -множество утверждений в действиях правил, Pn = <AVqnTn> - конкретное утверждение, AVqn е AV, Т„ - множество коэффициентов, приписываемых AVqn в утверждении Р„;

S = <Sins, Scons> - множество состояний пар «атрибут-значение», в правилах, причем Sins = {Smg}, m=l,..,k3, g=l,..,kl множество состояний пар «атрибут-значение» в посылке правил, Smg - конкретное состояние, являющееся целым числом, Scons = {Sng}, n=l,..,k4, g=l,..,kl - множество состояний пар «атрибут-значение» в действии правил, Sng - конкретное со-стояние^ являющее ся целым числом;

W'ns

• матрица, являющаяся объединением отображений Wins и

W--

W™"5, где Wins: R х AV -» Sins .и Wcons: Rx AV -> Scons, причем каждому утверждению Pm ставятся в соответствие состояния из множества {Smg}, g=l,..,kl, каждому утверждению Р„ ставятся в соответствие состояния из множества {Sng},g=l,..,kl.

Покажем, как определяются состояния Smg е Sins и Sng е Scons. Они принимают значение -1, если соответствующая пара «атрибут-значение» не участвует в посылке и действии правила, соответственно. Smg > 0 и Sng > 0, если соответствующая пара «атрибут-значение» участвует в посылке или действии правил, причем значения Smg = 0 и Sng = 0 имеют место, если с утверждением не связаны коэффициенты. Для участвующей в посылке правила пары «атрибут-значение», снабженной коэффициентами, соответствующее состояние определяется следующим образом:

Smg = t> если Tm = {t}, где t - коэффициент уверенности;

Smg е {Na}, a=l,..,k5, Na?£ 0, если Tm = {tl,t2}, где tl - нижняя граница интервала уверенности, t2 - верхняя граница интервала уверенности, Na- номер одного из интервалов уверенности среди непересекающихся интервалов, образованных точками пересечения интервалов уверенности данного утверждения в различных правилах;

Smg е {Na}, a=l,..,k6, Na ф 0, если Tm = {t} , где t - коэффициент точности, Na - номер одного из возможных непересекающихся интервалов допустимых значений среди интервалов, образованных 1раницами диапазонов допустимых значений в различных правилах;

Smg = td : Hmx<=max(|id), d=l,..,k7 , если Tra = {(tb цО, (t2, » (td-ь !Лм)> (td) Umax), (t (t+1, Hd+i).-, (tk7, Цк7)}, где td e [0..1] - значение, на котором кусочно-линейная функция принадлежности принимает максимальное значение |дтах;

Smg= (td+td+l)/2, если H<f=Hd+l=IW

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

Аналогичным образом определяются состояния утверждений в действиях правил.

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

Рис. 2. Общая схема метода обнаружения аномалий статической несогласованности и нарушений целостности.

Нормализация правил выполняется с помощью алгоритма, при применении которого исходный набор правил преобразуется в набор правил следующего вида: PiAP2A...APmA...APi Р1лР2л...аРпа...аРь Pm е Pins, m=l,..,i, Pn е Peons, n=l,..,k.

Алгоритм заполнения РТР включает в себя обнаружение нарушений целостности, а при фильтрации столбцов РТР производится выявление циклических правил и недостижимых заключений. Так как эти алгоритмы выполняют последовательный просмотр исходного множества правил и множества столбцов РТР, то они обладают линейной временной вычислительной сложностью по отношению к количеству правил, что соответствует аналогичным методам верификации баз знаний, предложенным в работах Т. Nguyen, J. Vanthienen и др.

Обнаружение противоречивых, избыточных и пересекающихся правил выполняется при сравнении столбцов РТР друг с другом с помощью разработан-

ного в диссертации алгоритма. Он обладает квадратичной временной вычислительной сложностью, что соответствует аналогичным методам верификации баз знаний, в частности, Т. Nguyen, J. Vanthienen и др. и может приводить к заметным временным затратам при большом количестве правил. В связи с этим, для сокращения перебора в данном алгоритме применяется критерий охвата правил (аналог критерия охвата операторов, используемого при тестировании традиционных программ), который заключается в том, что в одном правиле может быть обнаружено не более одной аномалии. Иными словами, если правило уже отнесено к какой-либо аномалии, то оно исключается из дальнейшего анализа. Критерий охвата правил может учитываться или не учитываться в процессе анализа поля знаний или базы знаний в зависимости от требований для текущей стадии разработки ИЭС.

В диссертации предложен метод обнаружения аномалий динамической несогласованности, основанный на раскрашенных сетях Петри (РСП). По сравнению с существующими методами верификации базы знаний, основанными на сетях Петри, например, J.H.Park, S.J.H.Yang и др., в данном случае при их формировании используется РТР.

РСП представлена пятеркой вида РСП = <Р, S, Т, L, Мо>, где

Р = {Pr}, r=l,..,il - множество мест, в котором Рг - конкретное место, соответствующее утверждению в посылке или действии правила, т.е. Р = Pins и Peons;

S - множество цветов, соответствующее множеству коэффициентов (состояний), приписываемым утверждениям в РТР, S = {Sn}, n=l,...,i2, Sn - конкретный коэффициент;

Т = {Tg}, g=l,..,i3 - множество переходов, соответствующих столбцам исходной РТР;

' L = (Wins, W00"5) - множество дуг сети, где Wins и W°ons - множества дуг, ведущих, соответственно, от мест к переходам (матрица входных состояний) и от переходов к местам (матрица выходных состояний);

Mo = {mj}, j=l,..,i6 - начальная маркировка сети, mj=(Pj,Sj), Pj е Р, Sj е S.

Разработанный метод обнаружения динамических аномалий включает следующие основные действия: заполнение РСП по РТР, проверку критериев наличия аномалий, добавление записей в протокол верификации (Рис. 3)

Критерии наличия аномалий определены с помощью функции проверки достижимости маркировки и функции сравнения маркеров в РСП.

Пусть M={mj}, j=l,..,i7 маркировка РСП, где nij=(Pj,Sj), Pj е Р, Sj е S и пусть m е М, тогда функция достижимости Reach(m) определена следующим образом:

{1, если ш е Мо,

Reach(m')+1, если Вт' е М: Reach(m') >0 л 3t е Т, 0, иначе.

Пусть mi~(Pi, AV|), ш2=(Р2, AV2), тогда функция сравнения маркеров определена следующим образом:

Г 1+1РГР2|,АУ1=АУ2 Сг(тьт2) = Н 2, А^Аг л У^Уг 0, иначе.

Поиск аномалий по РСП выполняется путем проверки критериев, представленных в Таблице 1. В отличие от существующих методов верификации баз знаний, основанных на сетях Петри, критерии не предназначены для выявления статических аномалий, так как статические аномалии обнаруживаются методом, основанным на РТР.

Рис. 3. Общая схема метода обнаружения аномалий динамической несогласованности.

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

Разработанные в диссертации алгоритмы проверки критериев наличия аномальных цепочек правил обладают экспоненциальной вычислительной сложностью по отношению к количеству правил, что соответствует аналогичным методам верификации баз знаний, использующих сети Петри, например 1.Н.Рагк, 8.1.Н.Уап§ и др. Поэтому в диссертации применяются два способа решения проблемы «комбинаторного взрыва» для этих алгоритмов.

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

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

Таблица 1.

Аномалия Критерий

Противоречивые цепочки правил Зтьт2еМ: Reach(mi)>l, Reach(m2)>2, Cr(mi,m2)>l

Циклические цепочки правил ЭпмеМо.тгеМ: Reach(m2)>2, Cr(mbm2)>0

Избыточные цепочки правил 3mi,m2,mi',m2'eM,ti,t2eT: Reach(mi)>2, Reach(m2)>2, Reach(mi')>l, Reach(m2')>l, Reach(mi)=Reach(m2), Reach(mi')<Reach(mt), Reach(m2')<Reach(m2), t| Ф t2> Cr(mi,m2)=l, mi,m2,mi',m2'gMo, Reach(mi)=Reach(m2), mi'[ti)mi, m2'[t2)m2

Пересекающиеся цепочки правил 3mi,m2eM: Reach(mi)>l, Reach(m2)>2, (Reach(mi) ^ Reach(m2) ACr(mi,m2)=l

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

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

В третьем разделе диссертации рассматриваются вопросы реализации в комплексе АТ-ТЕХНОЛОГИЯ инструментальных программных средств, обеспечивающих верификацию и корректировку поля знаний и базы знаний с использованием разработанных методов обнаружения аномалий.

В процессе разработки были учтены требования последних версий комплекса АТ-ТЕХНОЛОГИЯ, основным из которых является реализация программных средств в виде компонентов, представляющих собой СОМ-объекты, выполняющие установленные правила обмена сообщениями с остальными компонентами комплекса, а также содержащие функции, обеспечивающие связь с типовыми проектными процедурами (ТПП), которые активизируются специаль-

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

Общая архитектура программных средств представлена на Рис. 4, в соответствии с чем основными средствами поддержки процессов верификации поля знаний и базы знаний являются следующие компоненты: компонент формирования РТР, компонент обнаружения нарушений согласованности, компонент формирования сети Петри, компонент обнаружения динамических аномалий. Базовые средства верификации реализованы как отдельные компоненты, поскольку активизация каждого из них определяется различными условиями, наиболее существенные из которых связаны с настройками на множество искомых типов аномалий и конкретный критерий охвата. В качестве основных средств корректировки поля знаний и базы знаний применяются редактор поля знаний и базы знаний и «мастер» корректировки.

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

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

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

Аналогичным образом происходит функционирование компонентов верификации в случае активизации ТПП «Верифицировать базу знаний», при этом производится поиск аномалий в базе знаний в формате языка представления знаний комплекса АТ-ТЕХНОЛОГИЯ или другого инструментального средства.

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

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

Средство формирования плана верификации поля знаний или базы знаний

J Компонент ^ ввода настроек

Компонент

□ построения плана

Протокол верификации

План верификации

Средства обнаружения аномалий в поле знаний или базе знаний

Компонент исполнения плана верификации

Средства обнаружения статических аномалий

Компонент формирования РТР

Компонент обнаружения нарушений согласованности

РТР

Средства обнаружения динамических аномалий

Компонент формирования сети Потри

Компонент обнаружения динамических аномалий

Компонент визуализации протокола верификации

Редактор поля знаний или базы знаний

База знаний на ЯПЗ комплекса АТ-ТЕХНОЛОГИЯ

Мастер корректировки поля знаний или базы знаний

Рис. 4. Архитектура средств верификации и корректировки поля знаний и базы знаний для инструментального комплекса АТ-ТЕХНОЛОГИЯ.

Следует отметить, что за счет использования средств формирования и исполнения плана обеспечивается более высокий уровень автоматизации процессов верификации в целом. Например, по сравнению с известным проектом VALID в комплексе АТ-ТЕХНОЛОГИЯ не требуется явным образом выбирать средства поддержки требуемых методов верификации, так как набор используемых компонентов определяется настройками на искомые типы аномалий.

Кроме того, ускорение процесса корректировки поля знаний и базы знаний обеспечено специальным компонентом - «мастером» (Рис.4), в котором учтены несколько типовых действий для устранения аномалий статической несогласованности и нарушений целостности. «Мастер» поддерживает следующие группы типовых действий: устранение значений атрибутов, на которые нет ссылок; исправление недопустимых значений атрибутов; устранение атрибутов, на которые нет ссылок; устранение лишних условий в посылках правил; устранение замыканий правил; устранение избыточных правил; устранение пересечений правил; устранение противоречивых правил; устранение правил с недостижимыми заключениями.

Четвертый раздел диссертации посвящен экспериментальной проверке и использованию разработанных программных средств для верификации и корректировки поля знаний и базы знаний в процессе разработки прикладных ИЭС.

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

В процессе апробации были получены следующие результаты. Разработанные средства верификации способны обнаруживать присутствующие во фрагментах поля знаний и базы знаний статические и динамические аномалии. Время обработки и используемая оперативная память оказываются приемлемым для практического применения (поиск статических аномалий в базе знаний, включающей 1296 правил, выполнялся меньше 4 с. при использовании приблизительно 15 Мб оперативной памяти на компьютере PentiumlV 1600 МГц, а процесс обнаружения динамических аномалий во фрагменте базы знаний, содержащем 427 правил, на том же компьютере занял около 30 минут с использованием' приблизительно 390 Мб оперативной памяти).

Эксперименты показали, что применение критериев охвата позволяет сократить время поиска аномалий, которое уменьшается при увеличении количества аномальных правил. На Рис. 5 представлены экспериментальные зависимости времени поиска статических аномалий во фрагментах базы знаний прототипа ИЭС, предназначенного для поддержки проектирования корпоративных информационно-вычислительных сетей, с различной долей аномальных правил от общего числа правил при использовании критерия охвата правил. На Рис. 6 показаны аналогичные зависимости, полученные для случаев выявления динамических аномалий.

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

t,c

2,5

—О—Нет аномальных правил

1,5

-О-Аномальных правил 20%

'Аномальных правил 30%

0,5

200 400 600 800 1000 1200 п

Рис. 5. Зависимости времени поиска статических аномалий от количества правил во фрагментах базы знаний с различной долей аномальных правил.

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

Разработанные инструментальные программные средства верификации и корректировки поля знаний и базы знаний использовались при разработке прототипа ИЭС для проектирования и моделирования информационно-вычислительных сетей для ФГУП Концерн «Системпром». Обнаруженные в процессе разработки прототипа ИЭС аномальные правила в базе знаний составили в среднем 24% от общего числа правил, затем большинство из них было исправлено с помощью «мастера» корректировки, а оставшаяся часть откорректирована с использованием «редактора» базы знаний. Созданные средства включены в состав прототипа ИЭС с целью поддержки дальнейшего пополнения и модификации базы знаний в процессе эксплуатации системы.

Метод и алгоритмы обнаружения статических аномалий также использовались при разработке компонента анализа целостности и согласованности медицинских знаний в области эндоскопии, который входит в состав программных средств, обеспечивающих выполнение задач накопления медицинских знаний в рамках поддержки элементов «электронной истории болезни» в эндоскопическом отделении ЦКБ Гражданской авиации. Использование компонента анализа целостности и согласованности медицинских знаний повысило степень автоматизации процесса проверки правильности медицинских протоколов в эндоскопическом отделении. Проверка протоколов эндоскопических исследований

позволяет ежемесячно выявлять в них следующие нарушения, влияющие на правильность отчетов эндоскопического отделения: 5-7 нарушений порядка следования заключений; 2-10 несоответствий названия канала госпитализации и названия подразделения, откуда поступил пациент; 1-2 дублирования основных реквизитов пациентов и др.

—О—Нет аномальных правил -сз—Аномальных правил 8% —й—Аномальных правил 11%

400 П

Рис. б. Зависимости времени поиска динамических аномалий от количества правил во фрагментах базы знаний с различной долей аномальных правил.

Инструментальные средства верификации, включенные в состав комплекса АТ-ТЕХНОЛОГИЯ, использовались в учебном процессе Московского инженерно-физического института и Российского Государственного социального университета, а также при создании разделов учебного пособия Московского инженерно-физического института «Инструментальный комплекс АТ-ТЕХНОЛОГИЯ для поддержки разработки интегрированных экспертных систем» (авторы Рыбина Г. В., Пышагин С. В., Смирнов В. В., Левин Д. Е., Душкин Р. В. М.: МИФИ, 2001). .

В заключении приводятся основные выводы и результаты диссертации. В приложение вынесены:

- акты об использовании результатов диссертационного исследования;

- примеры фрагментов поля знаний и базы знаний, использованные для экспериментальной проверки разработанных средств верификации поля знаний и базы знаний;

- тестовые примеры работы средств верификации и корректировки поля знаний и базы знаний.

Основные результаты работы

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

2. Разработаны оригинальные методы обнаружения статических и динамических аномалий в поле знаний и базе знаний ИЭС, предусматривающие совместную обработку неопределенных, неточных и нечетких знаний.

3. Разработаны инструментальные программные средства верификации и корректировки поля знаний и базы знаний в ИЭС, включенные в состав инструментального комплекса АТ-ТЕХНОЛОГИЯ третьего поколения.

4. Созданные инструментальные программные средства верификации и корректировки поля знаний и базы знаний использованы при создании исследовательского прототипа ИЭС для проектирования и моделирования корпоративных информационно-вычислительных сетей, применяемого в исследованиях и разработках ФГУП «Концерн Системпром» (акт об использовании).

5. Метод и алгоритмы обнаружения статических аномалий использованы при создании компонента анализа целостности и согласованности медицинских знаний в эндоскопическом отделении ЦКБ Гражданской авиации (акт об использовании).

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

7. Разработанные инструментальные средства верификации и корректировки поля знаний и базы знаний в ИЭС в составе комплекса АТ-ТЕХНОЛОГИЯ использовались в учебном процессе Московского инженерно-физического института и Российского Государственного социального университета (акт о внедрении).

Основные публикации по теме диссертации

1. Кустикова И.А., Рыбина Г.В., Смирнов В.В.. Об одном подходе к автоматизированному построению базы знаний для интегрированных экспертных систем; аспекты тестирования // б-я Национальная конференция по искусственному интеллекту с международным участием - КИИ-98. Сборник научных трудов в трех томах. Т.1.-М.: РАИИ, 1998. С. 138-145.

2. Рыбина Г.В., Смирнов В.В. Методы и средства верификации баз знаний в современных экспертных системах // 8-я Национальная конференция по искусственному интеллекту с международным участием - КИИ-2002. Труды конференции. Т.1. -М.: Физматлит, 2002. С. 446-454.

3. Смирнов В.В. Применение спецификаций при верификации баз знаний экспертных систем // Научная сессия МИФИ-2003. Сборник научных трудов. В 14 томах. Т.З. - М.:МИФИ, 2003. С.158-159.

4. Рыбина Г.В., Смирнов В .В. Особенности выявления статических аномалий в базах знаний, содержащих отдельные виды НЕ-факторов // Ш-й Международный научно-практический семинар «Интегрированные модели и мягкие вычисления в искусственном интеллекте». - М.: Физматлит, 2005. С. 358-363.

5. Рыбина Г.В., Смирнов В .В. Методы и алгоритмы верификации баз знаний в интегрированных экспертных системах // Новости искусственного интеллекта. — 2005, № 3. С.7-19.

6. Рыбина Г.В., Смирнов В.В. Планирование процедур верификации баз знаний в интегрированных экспертных системах // Инженерная физика. - 2006, № 3. С. 53-65.

Принято к исполнению 05/10/2006 Исполнено 05/10/2006

Заказ № 712 Тираж: 100 экз.

Типография «11-й ФОРМАТ» ИНН 7726330900 Москва, Варшавское ш., 36 (495) 975-78-56 www.autoreferat.ru

лооей:

Оглавление автор диссертации — кандидата технических наук Смирнов, Виталий Валерьевич

Введение

1. АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ В ОБЛАСТИ ВЕРИФИКАЦИИ БАЗ ЗНАНИЙ ЭКСПЕРТНЫХ СИСТЕМ

1.1. Место верификации в жизненном цикле экспертных систем

1.2. Основные понятия и определения в области верификации баз знаний экспертных систем

1.3. Проблемы верификации БЗ ЭС

1.3.1. Анализ причины появления ошибок в БЗ ЭС

1.3.2. Проблема верификации баз знаний, содержащих различные виды НЕ-факторов 28 1.3 3. Проблема практической решаемости задач верификации 33 1.3.4. Проблемы верификации БЗ ЭС на этапе структурирования знаний

1.4. Классификация и сравнительный анализ методов верификации баз знаний экспертных систем

1.4.1. Методы обнаружения аномалий

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

1.4.3. Методы обнаружения статических аномалий, основанные на таблицах (матрицах)

1.4.4. Вычислительная сложность алгоритмов обнаружения статических аномалий

1.4.5. Методы обнаружения динамических аномалий, основанные на логике первого порядка

1.4.6. Методы обнаружения аномалий, основанные на графах

1.4.7. Методы обнаружения аномалий, использующие метазнания

1.4.8. Использование таблиц (матриц) при обнаружении динамических аномалий

1.4.9. Вычислительная сложность алгоритмов обнаружения динамических аномалий

1.4.10. Методы обнаружения аномалий, учитывающие наличие в БЗ знаний, содержащих НЕ-факторы

1.4.11. Методы доказательства правильности БЗ ЭС

1.4.12. Сокращение перебора в методах верификации БЗ 47 1 4.13. Общая классификация методов верификации БЗ

1.5. Классификация и сравнительный анализ средств верификации баз знаний экспертных систем

1.6. Особенности верификации БЗ ИЭС в рамках ЗОМ

1.7. Постановка задачи диссертационного исследования 56 Выводы

2. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РАЗРАБОТКИ СРЕДСТВ ВЕРИФИКАЦИИ ПОЛЯ ЗНАНИЙ И БАЗЫ ЗНАНИЙ В ПРОЦЕССЕ ПОСТРОЕНИЯ СТАТИЧЕСКИХ ИЭС

2.1. Обобщенная модель обнаружения аномалий в БЗ

2.2. Метод обнаружения статических аномалий в ПЗ и БЗ, основанный на таблицах решений

2.3. Метод обнаружения динамических аномалий в ПЗ и БЗ, основанный на сетях Петри 84 Выводы

3. ПРОЕКТИРОВАНИЕ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СРЕДСТВ ВЕРИФИКАЦИИ ПОЛЯ ЗНАНИЙ И БАЗЫ ЗНАНИЙ

3.1. Анализ системных требований на разработку средств верификации, функционирующих в составе комплекса АТ-ТЕХНОЛОГИЯ

3.2. Проектирование средств обнаружения статических аномалий в ПЗ и БЗ

3.3. Проектирование средств обнаружения динамических аномалий в ПЗ и БЗ

3.4. Проектирование средств формирования и исполнения плана верификации ПЗ и БЗ

3.5. Реализация компонентов верификации ПЗ и БЗ

3.6. Проектирование и реализация средства визуализации протокола верификации

ПЗ или БЗ

3.7. Мастер корректировки ПЗ и БЗ 109 Выводы

4. ЭКСПЕРИМЕНТАЛЬНАЯ ПРОВЕРКА МЕТОДОВ, АЛГОРИТМОВ И СРЕДСТВ ВЕРИФИКАЦИИ ПОЛЯ ЗНАНИЙ И БАЗЫ ЗНАНИЙ ИЭС. ВНЕДРЕНИЕ РАЗРАБОТАННЫХ ПРОГРАММНЫХ СРЕДСТВ

4.1. Экспериментальная проверка методов и алгоритмов верификации ПЗ и БЗ

4.2. Сравнение характеристик реализованных средств верификации ПЗ и БЗ с существующими средствами обнаружения статических аномалий

4.3. Сравнение характеристик реализованных средств верификации ПЗ и БЗ с существующими средствами обнаружения динамических аномалий

4.4. Экспериментальная проверка средств верификации ПЗ и БЗ

4.5. Использование разработанных программных средств при создании ИЭС КИВС

4.6. Использование разработанных программных средств в области медицинской диагностики

4.7. Применение средств верификации БЗ ИЭС в учебном процессе МИФИ и РГСУ 128 Выводы 130 Выводы по диссертации 131 Литература 132 Приложения

Введение 2006 год, диссертация по информатике, вычислительной технике и управлению, Смирнов, Виталий Валерьевич

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

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

Главное архитектурное отличие ЭС от других программных средств - это наличие базы знаний (БЗ). С конца 70-х годов проблемы построения БЗ становятся центральными в исследованиях по искусственному интеллекту. При этом, такие процедуры, как анализ предметной области, получение знаний и их структурирование, выполняемые инженером по знаниям, традиционно считаются "узким местом" проектирования ЭС и усилия разработчиков направлены на создание инструментальной программной поддержки деятельности инженера по знаниям и эксперта.

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

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

В проведенных автором исследованиях использован практический опыт разработки прикладных интегрированных ЭС на основе заданно-ориентированной методологии (ЗОМ) и автоматизированной технологии, включающей инструментарий нового поколения АТ-ТЕХНОЛОГИЯ, в результате которого был вьивлен ряд проблем, связанных с процессами верификации БЗ ИЭС. Основными из этих проблем являются значительные объемы содержащейся в БЗ ИЭС информации, приводящие к существенным вычислительным затратам, трудоемкость привлечении экспертов к процессам верификации БЗ ИЭС, необходимость учета неопределенных, неточных, нечетких и других видов недостоверных знаний, эксплицитно проявляющихся в рассуждениях экспертов. Однако, адекватных методов и средств верификации БЗ прикладных ИЭС в настоящее время практически не существует, поэтому исследование и разработка методов и средств верификации БЗ ИЭС, является актуальным.

Целью диссертации является исследование и разработка методов и инструментальных программных средств верификации БЗ ИЭС в рамках ЗОМ, повышающих степень автоматизации процессов построения поля знаний и БЗ для ИЭС.

Для достижения поставленной цели в диссертации решены следующие основные задачи.

1. На основе анализа существующих методов и средств верификации БЗ ЭС построена обобщенная модель обнаружения аномалий в БЗ ЭС.

2. Разработаны методы обнаружения статических и динамических аномалий в поле знаний и БЗ ИЭС, предусматривающие совместную обработку неопределенных, неточных и нечетких знаний.

3. Выполнен анализ системных требований и проектирование инструментальных программных средств верификации и корректировки поля знаний и БЗ в соответствии с ЗОМ.

4. Разработаны инструментальные программные средства верификации поля знаний и БЗ, включенные в состав комплекса АТ-ТЕХНОЛОГИЯ третьего поколения.

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

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

1. Построена обобщенная модель обнаружения аномалий в БЗ ЭС на основе выполненного анализа существующих методов и средств верификации БЗ ЭС.

2. Разработан оригинальный метод обнаружения статических аномалий в поле знаний и БЗ ИЭС, позволяющий учитывать случаи одновременного присутствия неопределенных, неточных и нечетких знаний.

3. Разработан оригинальный метод обнаружения динамических аномалий в поле знаний и БЗ ИЭС, который предусматривает совместную обработку неопределенных, неточных и нечетких знаний.

5. Созданы оригинальные инструментальные программные средства верификации поля знаний и БЗ в ИЭС.

6. Разработан «мастер» автоматизированной корректировки поля знаний и БЗ, использующий данные протокола верификации об обнаруженных статических аномалиях в поле знаний и БЗ в процессе построения ИЭС.

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

Основные научные результаты, выносимые на защиту: 1. Новая обобщенная модель обнаружения аномалий в БЗ ЭС, построенная на основе выполненного анализа существующих методов и средств верификации БЗ ЭС.

2. Оригинальные методы верификации поля знаний и БЗ в ИЭС, ориентированные на обнаружение как статических, так и динамических аномалий в поле знаний и БЗ, а также совместную обработку неопределенных, неточных и нечетких знаний.

4. Комплекс инструментальных программных средств верификации и корректировки поля знаний и БЗ.

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

Разработанные в диссертации инструментальные программные средства верификации поля знания и БЗ в составе комплекса АТ-ТЕХНОЛОГИЯ использованы при разработке отдельных компонентов для нескольких ИЭС, что подтверждается актами об использовании.

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

В первом разделе представлен анализ современного состояния в области верификации БЗ ЭС. Рассмотрены процессы верификации, как составляющие процессов жизненного цикла программного обеспечения вообще и ЭС, в частности. Показана роль верификации БЗ ЭС в процессах тестирования ЭС. Выделены проблемы, связанные с верификацией БЗ ЭС. В том числе, рассмотрены проблема верификации БЗ, содержащих различные виды НЕ-факторов, проблема «комбинаторного взрыва» при верификации БЗ ЭС, требующая пристального внимания при разработке ИЭС, в связи с тем, что создаваемые БЗ могут достигать достаточно больших объемов, проблемы верификации БЗ ЭС на этапе структурирования знаний. Приведены основные понятия и определения в области верификации программного обеспечения и показана их специфика для случая создания БЗ ЭС.

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

В диссертации также показано, что, несмотря на внешнее многообразие способов внутреннего представления знаний, на основе которых реализованы конкретные методы обнаружения аномалий, большинство методов основано на разновидностях правил, таблиц, логических моделей или графов. При этом значительное внимание в диссертации уделено анализу способов внутреннего представления, учитывающих случаи представления в БЗ ЭС НЕ-факторов знаний (термин НЕ-факторы впервые введен А.С.Нариньяни в середине 80-х годов). Показано, что такие случаи учитываются все еще не достаточно полно, причем у исследователей не выработано единого взгляда на природу и способы проявления знаний, содержащих НЕ-факторы (исключением является НЕ-фактор нечеткость, для которого в настоящее время существует более или менее универсальное определение).

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

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

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

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

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

Сформулирована цель и поставлены конкретные задачи диссертационного исследования.

Проведенный анализ существующих методов верификации БЗ ЭС позволил построить обобщенную модель обнаружения аномалий и использовать ее для разработки методов верификации поля знаний и БЗ в рамках ЗОМ.

Описан предложенный метод обнаружения аномалий статических аномалий, основанный на расширенных таблицах решений (РТР). По сравнению с существующими методами верификации БЗ, основанными на табличном представлении анализируемой информации, применение РТР позволяет обрабатывать поле знаний и БЗ, содержащие выделенные виды НЕ-факторов: неопределенность, неточность, нечеткость. В процессе построения РТР производится поиск нарушений целостности, а сформированная РТР используется для поиска нарушений согласованности.

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

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

Заключение диссертация на тему "Методы и средства верификации баз знаний в интегрированных экспертных системах"

Выводы по диссертации

4. Созданные инструментальные программные средства верификации и корректировки поля знаний и базы знаний использованы при создании исследовательского прототипа ИЭС для проектирования и моделирования корпоративных информационно-вычислительных сетей, применяемого в исследованиях и разработках ФГУП «Концерн «Системпром» (акт об использовании).

Библиография Смирнов, Виталий Валерьевич, диссертация по теме Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

1. Люгер Д.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание.: Пер. с англ. - М.: Издательский дом «Вильяме», 2003. - 320 с.

2. Частиков А. П., Белов Д. Л., Гаврилова Т.А. Разработка экспертных систем. Среда CLIPS. СПб.: БХВ, 2003.-608 с.

3. Попов Э.В. Экспертные системы. Решение неформализованных задач в диалоге с ЭВМ. -М.: Наука, 1987.-441 с.

4. Попов Э.В., Фоминых И.Б., Шапот М.Д. Статические и динамические экспертные системы: Учеб. Пособие. М.: Финансы и статистика, 1996. - 320 с.

5. Осипов Г.С. Приобретение знаний интеллектуальными системами: Основы теории и технологии. -М.:Наука. Физматлит, 1997. 112 с.

6. Рыбина Г.В. Задачно-ориентированная методология автоматизированного построения интегрированных экспертных систем для статических проблемных областей. // Известия РАН Теория и системы управления. № 5,1997, С. 129-137.

7. Рыбина Г.В. Автоматизированное построение баз знаний для интегрированных экспертных систем // Изв. РАН. Теория и системы управления. № 5,1998, С.152-166.

8. Кандрапшна Е.Ю., Литвинцева Л.В., Поспелов Д.А. Представление знаний о времени и пространстве в интеллектуальных системах / Под ред. Д.А.Поспелова. М: Наука. Гл. ред. физ.-мат. лит. 1989. - 328 с.

9. Рыбина Г.В. Проектирование систем, основанных на знаниях. Учебное пособие. -М.:МИФИ, 1997. -104 с.

10. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб: Питер, 2001.-384 с.

11. А.Н.Аверкин, А.Ф.Блишун, И.З.Батыршин и др. Нечеткие множества в моделях управления и искусственного интеллекта / Под ред. Д.А. Поспелова. М.:Наука, 1986.312 с.

12. Buchanan B.G., Barstow D., Bechtel R. et al. Constructing an expert system // Building Expert Systems (Eds.: Hayes-Roth F„ Waterman D.A., Levat D.). MA, Addison-Wesley, 1983. P.127-167.

13. IEEE Standard Dictionary of Electrical and Electronics Terms, 6th Edition // Institute of Electrical and Electronics Engineers, 1993. 1278 p.

14. Software Engineering Standards Collection //N.J., Piscataway, IEEE Press, 1999. V. 1-4.

15. Awad E.M. Building Expert Systems Principles, Procedures, and Applications. - MN, West Publishing Co., 1996.-638 p.

16. Santos E J. Verification and validation of Bayesian knowledge-bases // Data & Knowledge Engineering. Elsevier. 2001. V.37. P.307-329.

17. Молокова O.C. Методология анализа предметных областей. Новости искусственного интеллекта. 1992. № 3. С. 11-60.

18. Рыбина Г.В. Инструментарий нового поколения для построения интегрированных экспертных систем // 9-я Нац. Конф. По ИИ с межд. Участием КИИ-2004. Труды конференции. В 3-х томах-М.: Физматлит, 2004, С.621-629.

19. Рыбина Г.В. Инструментальные средства нового поколения для построения прикладных интеллектуальных систем // Авиакосмическое приборостроение. 2004, № 10. С.14-23.

20. Leemans P., Treur J., Willems М. A semantical perspective on verification of knowledge // Data & Knowledge Engineering. Holland, Amsterdam: Elsevier Science Publishers В. V. 2002. V. 40, № 1. P.33-70.

21. Cardevosa J., Juisto N. General Overview of the VALID Project // Proceedings of the European Symposium on the Validation and Verification of Knowledge-Based Systems (EVROVAV '93). Madrid, Universidad Politecnica de Madrid, 1993. P. 53-67.

22. Harmelen F. Applying rule-base anomalies to KADS inference structures // Decision Support Systems. 1998. V.21. № 4. P. 271-280.

23. Coenen F.P., Bench-Capon T.J.M. Maintenance of Knowledge Based Systems: Theory, Tools and Techniques. London: Academic Press, 1993. - 322 p.

24. Davis R. TEIRESIAS: Applications of Meta Level Knowledge // Knowledge-Based Systems in Artificial Intelligence. New York, McGraw Hill, 1982. P. 229-490.

25. Андерсон P. Доказательство правильности программ. M.: Мир, 1982. - 163 с.

26. Абрамова Н.А., Баталина Т.С., Гегемов Н.А., Коврига С.В. Новый математический аппарат для анализа внешнего поведения и верификации программ. Препринт. Российская Академия наук. Институт проблем управления. М.: 1998.

27. Apt R., Olderog. E.-R. Introduction to program verification. // Formal Description of Programming Concepts (Eds.: Neuhold E. J., Paul M.). New York, Springer-Verlag, 1991. P. 363429.

28. Neubert S. and Maurer F.: A Tool for Model Based Knowledge Engineering. In Proceedings of the 13th International Conference AI, Expert Systems, Natural Language (Avignon'93), May 24-28, Avignon, 1993.

29. Green, C.J.R., Keyes M.M. Verification and Validation of expert systems // Proceedings of the Western Conference on Expert Systems (WESTEX'87). Calif., Los Alamitos, IEEE CS Press, 1987. P. 38-43.

30. Geissman J.R., Schultz RD. Verification and Validation Expert Systems. // AI Expert. 1988. P. 26-33.

31. Ayel M. and Vignollet L. SYCOJET and SACCO, two tools for verifying expert systems // International Journal of Expert Systems: Research and Applications. 1993. V.6. № 3. P. 357-382.

32. Lopez B. CONKRET: a control knowledge refinement tool // Validation, Verification and Test of Knowledge-Based Systems. New York, Wiley, 1991, P. 191-206.

33. Politakis P.G. Politakis P.G. Empirical Analysis for Expert Systems (Research Notes in Artificial Intelligence). London, Financial Times Prentice Hall, 1998. 160 p.

34. Smith S., Kandel A. Verification and Validation of Rule-based Expert Systems. USA, FL, Boca Raton, CRC Press. 1993. 203 p.

35. Ларичев О.И., Болотов A.A. Система ДИФКЛАСС: построение полных и непротиворечивых баз экспертных знаний в задачах дифференциальной классификации // НТИ. Серия 2 Информационные процессы и системы., 1996. № 9. С.9-15.

36. Harmelen F., Fensel D. Formal Methods in Knowledge Engineering. // The Knowledge Engineering Review. 1995. V.10. №. 4. P. 345-360.

37. Зейденберг B.K., Зимарев A.H., Степанов A.M. и др. Англо-русский словарь по вычислительной технике: Ок. 42 000 терминов. / Под ред. Е.К. Масловского. М.: Рус.яз., 1990.-800 с.

38. Канер С., Фолк Д., Нгуен Е.К. К. Тестирование программного обеспечения. М.: "ДиаСофт", 2000.-544 с.

39. Nguyen T.A. Perkins W.A., Laffey T.J., Pecora D. Knowledge Base Verification. // AI Magazine, 1987. V. 8. №. 2. P. 69-75.

40. Clegg C., Warr P., Green T. et al. People and computers: how to evaluate your company's new technology. USA, NY, New York, Halsted Press, 1988. 245 p.

41. Preece A. D. Validation of Knowledge-Based Systems: The State-of-the-Art in North America // Journal of Communication and Cognition Artificial Intelligence, 1994. V.l 1. № 4. P. 381-413.

42. Towell G.G., Shavlik J.W., Noordewier M.O. Refinement of Approximate Domain Theories by Knowledge-Based Neural Networks // Proceedings of the Eighth National Conference on Artificial Intelligence. Boston, MA, 1990. P. 861-866.

43. Хьюигг К. Открытые системы. Реальность и прогнозы искусственного интеллекта: Сб. статей; пер. с англ. / Под ред. и с предисл. ВЛ.Стефанюка. М.: Мир, 1987. С. 85-102.

44. Ларичев О.И., Моргоев В.К. Проблемы, методы и системы извлечения экспертных знаний // Изв. АН СССР. Автоматика и телемеханика. М.:Наука, 1991, С. 3-26.

45. Simon Н.А. Information-processing theory of human problem solving // Handbook of learning and cognitive processing. Human Information Processing. Ed. Ectes, LEA, 1978. V 5. P. 271-295.

46. Kihlstrum J. The cognitive unconscious. // Science, 1987. V. 237. P. 1445-1451.

47. Ларичев О.И. Компьютерная имитация человеческих рассуждений в задачах классификации. НТИ. Серия 2 Информационные процессы и системы. 1996, № 9, С. 1-4.

48. Нариньяни А.С. Недоопределенность в системах представления и обработки знаний // Изв. АН СССР. Техн. кибернетика. 1986. № 5. С. 3-28.

49. Душкин Р.В., Рыбина Г.В. Об одном подходе к автоматизированному извлечению, представлению и обработке знаний с НЕ-факторами // Известия АН. Теория и системы управления, 1999, № 5. С.34-44.

50. Рыбина Г.В. Приобретение знаний, содержащих НЕ-факторы // Новости искусственного интеллекта. 2004, № 2. С.82-94.

51. Cragun B.J., Steudel H.J. A decision-table-based processor for checking completeness and consistency in rule-based expert systems // International Journal of Man-Machine Studies (UK). 1987. V. 26. №5. P. 633-648.

52. Зыкова C.A. Колчин А.Ф. Методы и средства верификации знаний в интеллектуальных системах, основанных на правилах. // В кн. КИИ-92. Третья конференция по искусственному интеллекту. Сборник научных трудов в 2-х томах. Т.1., Тверь 1992. С. 27-30.

53. Garg-Janardan С., Salvendy G. A conceptual framework for knowledge elicitation. Int. J. Man-Machine St. 1987. V.26. P. 521-531.

54. Джексон П. Введение в экспертные системы. М.: Издательский дом «Вильяме», 2001 -624 с.

55. Ильин В.В. Критерии научности знания. М.: Высшая школа, 1989.- 127 с.

56. Фуремс Е.М. Гнеденко Jl.C. STEPCLASS система извлечения экспертных знаний и проведения экспертизы для решения диагностических задач // НТИ. Информационные процессы и системы. 1996. № 9. С.16-20.

57. Тулупьев A.J1., Городецкий В.И. Алгебраические байесовские сети: поддержание непротиворечивости баз знаний. // Доклады международной конференции «Знания, диалог, решение-95» (KDS-95).-Jbrra, 1995. С. 151-159.

58. Городецкий В.И., Тулупьев A.JI. Непротиворечивость баз знаний с количественными мерами неопределенности. // В кн. КИИ-98. Шестая нац. конференция с межд. участием. Сборник научных трудов в 3-х томах. Пущино, 1998, Т.1. С. 100-107.

59. Preece A. A new approach to detecting missing knowledge in expert system rule bases // International Journal of Man-Machine Studies 1993. V. 38. P. 661-688.

60. Калинина E.A., Рыбина Г.В. Применение технологии Data Mining для автоматизированного построения баз знаний интегрированных экспертных систем // 7-ая нац. конф. по ИИ с межд. участием КИИ'2000. М.:ФИЗМАТЛИТ, 2000. С. 119-127.

61. Hicks R. С. The TRIMM Methodology for maintainable rule-based systems // Heuristics: The Journal of Intelligent Technologies. 1995. V. 8. №. 4. P. 15-24.

62. Yang S.J.H., Tsai J.J.P., Chen C.-C. Fuzzy Rule Base Systems Verification Using High-Level Petri Nets // IEEE Trans. Knowl. Data Eng. 2003. V. 15. № 2. P.457-473.

63. Vanthienen J., Wets G., Fuzzy Decision Tables: Modeling and V&V Issues // 12th European Conference on Artificial Intelligence. ECAI-96 workshop (W2). Validation, Verification and Refinement of KBS, Budapest, 1996. P.36-40.

64. Гэри M., Джонсон Д., Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.-416 с.

65. Levy A.Y., Rousset М.-С., CARIN: A Representation Language Combining Horn Rules and Description Logics // Proceedings of European Conference on Artificial Intelligence. Budapest, Hungary, 1996. P. 323-327.

66. Waterman D.A. User-oriented systems for capturing expertise: a rule-base approach // Expert systems in the microelectronic age. Edinburgh: Edinburgh University Press, 1979. P.26-34.

67. Simon H.A. Problem formulation and alternative generation in the decision making process // Utility and risk theory. MA, Boston, Kluwer, 1991. P. 77-84.

68. Chandrasekaran, B. Towards a functional architecture for intelligence based on generic information processing tasks // Proceedings of the 10th DCAI. Italy, Milan, 1987. P. 1183-1192.

69. Breuker I., Wielinda B. KADS: structured knowledge acquisition for expert systems // Proceedings of Expert Sytems and their Applcations, 1985. V. 2. P.887-900.

70. McDermott J. Preliminary steps towards a taxonomy of problem-solving methods. // Automating Knowledge Acquisition for Expert Systems (Ed.:Marcus S.). Boston, Kluwer, 1988. P.225-255.

71. Kelly, G.A. The Psychology of Personal Constructs. New York: Norton. 1955. - 187 p.

72. Boose J. H. A knowledge acquisition program for expert systems based on personal construct psychology // International Journal of Man-Machine Studies. 1985. V.23. P.495-525.

73. Larry E.W, Ford J. M. Structuring Interviews with Experts During Knowledge Elicitation // International Journal of Intelligent Systems. New York, John Wiley & Sons, Inc. 1993. V.8. P.71-90.

74. Boose, J.H. & Bradshaw, J.M Expertise transfer and complex problems: using AQUINAS as a knowledge acquisition workbench for knowledge-based systems // International Journal of Man-Machine Studies. 1987. V.26. P.3-28.

75. Meseguer P., Preece A. Verification and Validation of Knowledge-Based Systems with Formal Specifications. // Knowledge Engineering Review. 1995. V.10. № 4. P.331-343.

76. Spivey J.M. Understanding Z: Specification language and its formal semantics. United Kingdom, Cambridge University Press, 1988. - 144 p.

77. Sheppard D. An introduction to formal specification with Z and VDM. New York, McGraw-Hill, 1994.-398 p.

78. Fensel D., Van Harmelen F. A Comparison of Languages which Operationalize and Formalize KADS Models of Expertise // The Knowledge Engineering Review, 1994, V.9. № 2. P. 105-146.

79. Chandrasekaran В., Josephson J., Keuneke A., Herman D. Building routine planning systems and explaining their behavior // Int. J. Man-Mach. St. 1989. V 30. № 4. p. 377-398.

80. Alexander J. H., Freiling M.J., Shulman S. J. et al. Ontological analysis: an ongoing experiment. // Int. J. Man-Mach. St. 1987. V.26, № 4. P. 473-485.

81. Voss A, Karbach W. Implementing KADS Expertise Models with Model-K // IEEE Expert: Intelligent Systems and Their Applications, 1993, V. 8. №. 4. P. 74-81.

82. Wetter Т.: First-order logic foundation of the KADS conceptual model // Current trends in knowledge acquisition. Amsterdam, IOS Press, 1990. P. 356-375.

83. Van Harmelen F., Balder J. R. (ML)2: a formal language for KADS models of expertise // Knowledge Acquisition Journal. 1992. V. 4. № 1. P. 127-161.

84. Langevelde, I. A. Philipsen, Jan Treur: Formal Specification of Compositional Architectures // Proceedings of the 10th European Conference on Artificial Intelligence (ECAI'92). Vienna, 1992. P. 272-276.

85. Giunchiglia F., Traverso P. A system for multi-level mathematical reasoning. // Artificial Intelligence in Mathematics Conference Proceedings. Oxford University Press, 1994. P. 119-134.

86. Wilder М. Review: EZ-Xpert RAD Comes to Expert Systems // PC AI Magazine. V.12 № 1, 1998. P.39-41.

87. Nguyen, T.A., Perkins, W.A., Laffey, T.J., et al. Checking an Expert System's Knowledge Base for Consistency and Completeness // Proceedings of the Ninth International Joint Conference on Artificial Intelligence, CA, Los Angeles, 1985, P. 375-378.

88. Ларичев О.И., Мечитов А.И., Мошкович Е.М., и др. Система выявления экспертных знаний в задачах классификации // Изв. АН СССР. Техн. кибернетика. 1987. № 2. С. 74-94.

89. Ларичев О.И., Нарыжный Е.В. Компьютерное обучение экспертным правилам в задачах классификации. НТИ. Серия 2 Информационные процессы и системы. 1996, № 9. с 4-9.

90. Kleer J. An assumption based TMS // Artificial intelligence. 1986. V. 28, № 2. p.127-162.

91. Ginsberg A. Knowledge-Base Reduction: A New Approach to Checking Knowledge Bases for Inconsistency & Redundancy // Proceedings of the Seventh National Conf. on Artificial Intelligence (АААГ88). USA. CA. Menlo Park: AAAI-Press. 1988. V.2. P.585-589.

92. Preece, A.D. Towards a Methodology for Evaluating Expert System // Expert Systems, 1990. V.7 № 4. P. 215-223.

93. Rousset M.-C. On the consistency of knowledge bases: the COVADIS system // Computational Intelligence. 1988. V.4. P. 166-170.

94. Park J.H., Seong P.H. An integrated knowledge base development tool for knowledge acquisition and verification for NPP dynamic alarm processing systems // Annals of Nuclear Energy. Oxford, Pergamon, 2002. V. 29. №. 4. P. 447-463.

95. Prakash, R. G. Mahabala, H.N. SVEPOA: A Tool to Aid Verification and Validation of OPS5-based AI Applications // International Journal of Expert Systems. 1993. V.6. № 2, P. 193236.

96. Meseguer P. A new method to checking rule bases for inconsistency: A Petri net approach // Proceedings of the 9th European Conference on Artificial Intelligence (ECAI-90). Stockholm, Pitman Publishing, 1990. P. 437-442.

97. Котов В. E. Сети Петри. M.: Наука, 1984. - 160 с.

98. Chang С., Combs J., Stachovitz R. A report on Expert system Validation Associate (EVA) // Expert Systems with Applications, 1990, V.l. P. 217-230.

99. Смирнов B.B. Применение спецификаций при верификации баз знаний экспертных систем // Научная сессия МИФИ-2003. Сборник научных трудов. В 14 томах. Т.З. -М.:МИФИ, 2003. С.158-159.

100. Groot P., ten Teije A., Van Harmelen F. Formally verifying dynamic properties of KBS // Proceedings of the 11th European Workshop on Knowledge Acquisition, Modeling, and Management (EKAW'99). Springer-Verlag, 1999. P. 157-172.

101. Breuker J., Van de Velde W. The CommonKADS Library for Expertise Modelling. The Netherlands, Amsterdam, IOS Press. 1994. p. 372.

102. Forgy C. L. RETE: A fast algorithm for the many pattern / many object pattern match problem. //Artificial Intelligence. 1982. V.19. № 1. P. 17-37.

103. Coenen F.P. An Advanced Binary Encoded Matrix Representation for Rulebase Verification. Journal of Knowledge-Based Systems. 1995. V.8. № 4. P.201-210.

104. Вагин B.H. He-факторы знания и нетрадиционные логики. // Третья международная школа-семинар по искусственному интеллекту для студентов и аспирантов (Браславская школа-1999). Сборник научных трудов. Беларусь, 1999. С. 10-14.

105. Quinlan J.R. Induction of Decision Trees // Machine Learning Journal. 1986. № 1. P.81-106.

106. Van Melle W.J. System aids in constructing consultation programs. Mich., Ann Arbor, UMI Research Press, 1981.-185 p.

107. Shortliffe E. H., Scott A. C., Bischoff M. B. et al. ONCOCIN: An expert system for oncology protocol management // Proceedings of Seventh International Joint Conference on Artificial Intelligence. Canada, ВС, Vancouver, 1981. P.876-881.

108. Preece A. D., Talbot S and Vignollet L. Evaluation of Verification Tools for Knowledge-Based Systems // International Journal of Human-Computer Studies. Academic Press Limited, 1997. V. 47, P.629-658.

109. Рыбина Г.В., Смирнов B.B. Планирование процедур верификации баз знаний в интегрированных экспертных системах // Инженерная физика. 2006, № 3. С. 53-65.

110. Zadeh L.A. A Theory of Approximate Reasoning // Machine Intelligence. New York: Halstead Press, 1979. P.149-194.

111. Турксен И.Б. О вкладе Лотфи Заде в соверменную науку // Новости искусственного интеллекта. 2001. V. 44-45. № 2-3. С.12-15.

112. Рыбина Г.В., Смирнов В.В. Методы и алгоритмы верификации баз знаний в интегрированных экспертных системах // Новости искусственного интеллекта. 2005, № 3. С.7-19.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00