ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 4, с. 91-102
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ
УДК 004.827
МЕТОДЫ И АЛГОРИТМЫ ВЕРИФИКАЦИИ БАЗ ЗНАНИЙ В ИНТЕГРИРОВАННЫХ ЭКСПЕРТНЫХ СИСТЕМАХ*
© 2007 г. Г. В. Рыбина, В. В. Смирнов
Москва, МИФИ (государственный ун-т) Поступила в редакцию 16.11.05 г., после доработки - 05.09.06 г.
Представлены краткий анализ и сравнение методов верификации экспертных систем и традиционных программ. Показаны особенности верификации баз знаний интегрированных экспертных систем, описаны методы и алгоритмы обнаружения статических и динамических аномалий в поле знаний.
Введение. В последнее десятилетие среди исследований и разработок в области интеллектуальных систем, в частности, экспертных систем (ЭС), значительное внимание уделяется вопросам верификации создаваемых баз знаний (БЗ). Следует отметить, что когда концепция разработки ЭС ориентировалась преимущественно на автономное изолированное функционирование традиционных (простых продукционных) ЭС, построенных только на основе эксклюзивных знаний экспертов, основные направления исследований в области верификации БЗ были связаны с анализом их различных свойств, в том числе статических и динамических свойств БЗ, структур вывода, НЕ-факторов и т.п., а также с изучением особенностей различных формализмов для представления анализируемой информации, в качестве которых обычно выступали правила, множества дизъюнктов Хорна, таблицы (матрицы), байесовские сети, сети Петри, графы зависимостей данных, метазнания, логика первого порядка и т.д. [1]. С дальнейшим развитием инструментальных средств для ЭС, позволяющих эффективно разрабатывать большие БЗ, стала возрастать популярность методов верификации БЗ ЭС, использующих различные способы сокращения перебора [2-4] и ориентированных на более тесную интеграцию с методами улучшения качества ЭС [5].
Однако в практике создания интегрированных ЭС (ИЭС), в частности на основе задачно-ориенти-рованной методологии (ЗОМ) [6] и автоматизированной технологии, включающей инструментарий нового поколения - комплекс АТ-ТЕХНОЛОГИЯ [7], оказалось, что объемы информации, полученной на этапах структурирования, т.е. построения поля знаний (ПЗ) [6], и построения собственно БЗ, с одной стороны, могут быть весьма значительными, а с другой - включать недостоверные знания, содержащие отдельные виды НЕ-факторов, эксплицитно проявляющихся в знаниях эксперта (наи-
* Работа выполнена при финансовой поддержке РФФИ (проект < 03-01-00924).
более распространенные из них - неопределенность, неточность, нечеткость, недоопределенность [8, 9]). Кроме того, процессы разработки ИЭС характеризуются, как правило, наличием большого количества стадий и итераций, что значительно усложняет верификацию ПЗ и БЗ. Тем не менее, адекватных подходов и методов для верификации ПЗ и БЗ в ИЭС в настоящее время практически не существует. Поэтому цель работы - описание предложенных в рамках ЗОМ и реализованных в составе средств комплекса АТ-ТЕХНОЛОГИЯ третьего поколения специальных методов и алгоритмов верификации ПЗ и БЗ в ИЭС, основанных на ассимиляции традиционных подходов к верификации ЭС с технологией тестирования сложных программных систем.
1. Анализ и сравнение методов верификации ЭС и традиционных программ. Разработка любого программного обеспечения включает его тестирование, которое не выделяют в отдельный процесс, так как оно обычно является частью других процессов жизненного цикла (ЖЦ) создания программного обеспечения. В соответствии с международным стандартом ISO/IEC 12207 ЖЦ программного обеспечения объединяет следующие процессы:
основные (приобретение, поставка, разработка, функционирование и сопровождение);
поддерживающие (документирование, конфигурирование, менеджмент конфигурации, оценка качества, верификация, валидация, анализ связей, аудит и разрешение проблемы);
организационные (менеджмент, инфраструктура, усовершенствование и тренинг).
Следует отметить, что в целом разработка программного обеспечения включает такие виды тестирования, как аудит кода, инспекция кода, разбор (walkthrough) кода и т.п., причем в процессе функционирования программ возможны операционное тестирование, анализ граничных значений (стрессовое тестирование) и т.д., а при верификации
программ используются аудит кода, анализ ограничений, проверка утверждений пользователя и др.
Тестирование традиционных (простых продукционных) ЭС также может выполняться на всех этапах ЖЦ параллельно с процессом разработки и содержать этапы тестирования исходных данных,, верификации и валидации [10]. Тестирование исходных данных осуществляется для проверки семантической корректности элементов, составляющих БЗ ЭС, верификация - для контроля правильности построения ЭС (без учета требований пользователя к системе), целью валидации является оценка соответствия ЭС требованиям пользователя. Кроме того, верификация, оставаясь одним из этапов тестирования ЭС, часто рассматривается как часть процесса валидации [11] или как составляющая единого процесса верификации и валидации ЭС (обозначается как V&V) [12].
Названные этапы тестирования ЭС могут быть разбиты на более мелкие, что позволяет показать их связь с базовыми этапами ЖЦ ЭС, как это проиллюстрировано в табл. 1.
В настоящее время существует несколько точек зрения на понятие верификации ЭС. В широком смысле под верификацией, выполняющейся, как правило, параллельно с процессом разработки ЭС, понимается проверка соответствия требованиям каждого этапа ее ЖЦ [10]. С позиции представления и обработки знаний верификация ЭС предполагает обнаружение логических ошибок в представлении знаний [10, 13] и структурах вывода [13]. В ряде случаев, рассматривая верификацию ЭС по аналогии с верификацией традиционных программ, ее трактуют как доказательство правильности БЗ [14].
Следует отметить, что результат верификации как традиционных программ, так и ЭС - выявление определенных отклонений от ожидания, которые относятся к одному из следующих типов:
ошибка (bug, crash, exception, fault, defect, error) -нарушение нормальной работы программы [15, 16] или ЭС [17, 18];
мутация - предполагаемое резкое изменение поведения программы при наличии мелких ошибок, незначительное изменение в программе или единичная ошибка, допущенная в процессе проектирования ЭС [10];
аномалия - нечто, наблюдаемое в ЭС, которое отклоняется от ожидания (например, избыточность, противоречивость, неполнота [13]).
Другими словами, аномалии рассматриваются как некоторый признак (или набор признаков), показывающий факт наличия определенных типов ошибок или мутантов в ЭС. Например, в работе [17] аномалии названы "симптомами предполагаемых ошибок".
Выделяются две основных группы аномалий: нарушения согласованности и нарушения целостности БЗ ЭС [17, 19, 20]. Как показано на рис. 1, к нарушениям согласованности относятся такие типы аномалий, как противоречивость, наличие циклов, избыточность, наличие пересечений, а к нарушениям целостности - неполнота (в узком смысле), отсутствие ссылок, некорректность.
Поскольку в настоящее время существуют различные трактовки понятия неполноты, то поясним более детально, что понимается под неполнотой в данной работе. В классической логике неполнота - нарушение свойства полноты, т.е. для множества формул с заданными свойствами исходная система аксиом и правил вывода должна обеспечить вывод всех формул, входящих в это множество. Если рассматривается некоторая система утверждений, то неполнота означает, что не все истинные утверждения, которые формулируются на языке этой системы утверждений, могут быть в ней доказаны (нарушение семантической полноты). Под неполнотой также понимается один из НЕ-факторов [21]. В случае, если исследование процессов верификации БЗ ограничивается только
Таблица 1
Этапы жизненного цикла ЭС Этапы тестирования ЭС
Идентификация Получение знаний Структурирование знаний Формализация Реализация Отладка и тестирование Опытная эксплуатация и внедрение Тестирование исходных данных Тестирование исходных данных, инспекция Тестирование исходных данных, инспекция, статическая верификация, формальное доказательство Тестирование исходных данных, инспекция, статическая верификация, формальное доказательство Инспекция, статическая верификация, формальное доказательство, оценивание, выборочное тестирование, ревизия БЗ, улучшение БЗ Инспекция, статическая верификация, формальное доказательство, оценивание, выборочное тестирование, ревизия БЗ, улучшение БЗ Оценивание, выборочное тестирование, ревизия БЗ, улучшение БЗ
Г Типы аномалий ^ гПримеры статических"1 г Примеры
Рис. 1. Классификация аномалий в БЗ ЭС.
анализом представления и обработки знаний, применяется узкая трактовка неполноты, которая означает наличие определенных отклонений от ожидаемого поведения (например, неполная база знаний не позволяет формировать непротиворечивое решение для любой ситуации в рамках ограниченной проблемной области [22]). В [10] обнаружение неполноты в БЗ включает поиск в ней конфликтных, избыточных и пересекающихся правил.
В данной работе неполнота БЗ (в узком смысле) интерпретируется как отсутствие правил, приводящих к определенным значениям целевых атрибутов. В соответствии с [20], если аномалии в продукционных БЗ проявляются при сопоставлении отдельных правил, то их называют статическими, а если в цепочках правил - динамическими. Следует отметить, что нарушения согласованности могут быть как статическими, так и динамическими, а нарушения целостности относятся только к статическим. С учетом вышеизложенного, в работе под верификацией ЭС будет пониматься процесс обнаружения определенных отклонений от ожидания в БЗ ЭС.
Возможны различные классификации методов верификации БЗ ЭС: по применимости на различных этапах ЖЦ, по использованию для обнаружения статических и динамических аномалий, по способности учитывать наличие в БЗ ЭС определенных НЕ-факторов и др. В [1] авторами была предложена достаточно универсальная классифи-
кация, связанная с формализмами представления анализируемой информации.
В общем случае все методы верификации БЗ ЭС включ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.