Содержание к диссертации
Введение
1. Анализ современного состояния в области верификации баз знаний экспертных систем 12
1.1. Место верификации в жизненном цикле экспертных систем 13
1.2. Основные понятия и определения в области верификации баз знаний экспертных систем 24
1.3. Проблемы верификации БЗ ЭС 26
1.3.1. Анализ причины появления ошибок в БЗ ЭС 26
1.3.2. Проблема верификации баз знаний, содержащих различные виды НЕ-факторов 28
1.3 3. Проблема практической решаемости задач верификации 33
1.3.4. Проблемы верификации БЗ ЭС на этапе структурирования знаний 34
1.4. Классификация и сравнительный анализ методов верификации баз знаний экспертных систем 37
1.4.1. Методы обнаружения аномалий 39
1.4.2. Методы обнаружения статических аномалий, использующие непосредственный анализ правил 40
1.4.3. Методы обнаружения статических аномалий, основанные на таблицах (матрицах) 40
1.4.4. Вычислительная сложность алгоритмов обнаружения статических аномалий 41
1.4.5. Методы обнаружения динамических аномалий, основанные на логике первого порядка 41
1.4.6. Методы обнаружения аномалий, основанные на графах 42
1.4.7. Методы обнаружения аномалий, использующие метазнания 44
1.4.8. Использование таблиц (матриц) при обнаружении динамических аномалий 44
1.4.9. Вычислительная сложность алгоритмов обнаружения динамических аномалий 45
1.4.10. Методы обнаружения аномалий, учитьшающие наличие в БЗ знаний, содержащих НЕ-факторы 46
1.4.11. Методы доказательства правильности БЗ ЭС 47
1.4.12. Сокращение перебора в методах верификации БЗ 47 1 4.13. Общая классификация методов верификации БЗ 49
1.5. Классификация и сравнительный анализ средств верификации баз знаний экспертных систем 49
1.6. Особенности верификации БЗ ИЭС в рамках ЗОМ 54
1.7. Постановка задачи диссертационного исследования 56
Выводы 57
2. Теоретические основы разработки средств верификации поля знаний и базы знаний в процессе построения статических ИЭС 58
2.1. Обобщенная модель обнаружения аномалий в БЗ 58
2.2. Метод обнаружения статических аномалий в ПЗ и БЗ, основанный на таблицах решений 64
2.3. Метод обнаружения динамических аномалий в ПЗ и БЗ, основанный на сетях Петри 84 Выводы 94
3. Проектирование и программная реализация средств верификации поля знаний и базы знаний 95
3.1. Анализ системных требований на разработку средств верификации, функционирующих в составе комплекса АТ-ТЕХНОЛОГИЯ 95
3.2. Проектирование средств обнаружения статических аномалий в ПЗ и БЗ 100
3.3. Проектирование средств обнаружения динамических аномалий в ПЗ и БЗ 102
3.4. Проектирование средств формирования и исполнения плана верификации ПЗ и БЗ 104
3.5. Реализация компонентов верификации ПЗ и БЗ 105
3.6. Проектирование и реализация средства визуализации протокола верификации ПЗ или БЗ 106
3.7. Мастер корректировки ПЗ и БЗ 109
Выводы 115
4. Экспериментальная проверка методов, алгоритмов и средств верификации поля знаний и базы знаний иэс. внедрение разработанных программных средств 117
4.1. Экспериментальная проверка методов и алгоритмов верификации ПЗ и БЗ 117
4.2. Сравнение характеристик реализованных средств верификации ПЗ и БЗ с существующими средствами обнаружения статических аномалий 120
4.3. Сравнение характеристик реализованных средств верификации ПЗ и БЗ с существующими средствами обнаружения динамических аномалий 122
4.4. Экспериментальная проверка средств верификации ПЗ и БЗ 123
4.5. Использование разработанных программных средств при создании ИЭС КИВС 124
4.6. Использование разработанных программных средств в области медицинской диагностики 126
4.7. Применение средств верификации БЗ ИЭС в учебном процессе МИФИ и РГСУ 128 Выводы 130
Выводы по диссертации 131
Литература
- Проблема верификации баз знаний, содержащих различные виды НЕ-факторов
- Методы обнаружения динамических аномалий, основанные на логике первого порядка
- Метод обнаружения статических аномалий в ПЗ и БЗ, основанный на таблицах решений
- Проектирование средств обнаружения динамических аномалий в ПЗ и БЗ
Введение к работе
Особенности верификации традиционных (простых продукционных) экспертных систем (ЭС), связанные с их назначением, архитектурой и жизненным циклом, требуют проведения отдельных исследований в области верификации ЭС. Как известно, ЭС ориентированы на тиражирование опыта высококвалифицированных специалистов в областях, где качество принятия решений традиционно зависит от уровня экспертизы, например, медицина, юриспруденция, геология, экономика, военное дело, в частности, ЭС применяются для решения таких критических задач, как управление воздушным движением, ядерными реакторами и системами оружия.
ЭС предназначены для решения неформализованных задач, к которым относятся задачи, обладающие одной или несколькими из следующих характеристик: задачи не могут быть заданы в числовой форме; цели не могут быть выражены в терминах точно определенной числовой функции; не существует алгоритмического решения задачи; алгоритмическое решение существует, но его нельзя использовать из-за ограниченности ресурсов (время, память).
Главное архитектурное отличие ЭС от других программных средств - это наличие базы знаний (БЗ). С конца 70-х годов проблемы построения БЗ становятся центральными в исследованиях по искусственному интеллекту. При этом, такие процедуры, как анализ предметной области, получение знаний и их структурирование, выполняемые инженером по знаниям, традиционно считаются "узким местом" проектирования ЭС и усилия разработчиков направлены на создание инструментальной программной поддержки деятельности инженера по знаниям и эксперта.
Важной особенностью современного состояния исследований и разработок в области ЭС является значительный рост внимания к вопросам верификации БЗ ЭС, по которой чаще всего понимается обнаружение логических ошибок в представлении знаний. Постоянная потребность в верификации БЗ ЭС в течение всего жизненного цикла ЭС связана с трудностями получения знаний из их основного источника, которым, как известно, является эксперт. Результаты исследований в области ЭС показали, что суть трудностей «отбора» знаний эксперта состоит в их «дискретности», неполноте и плохой структурированности. Кроме того, требуется контроль за возможными ошибками, допускаемыми экспертом при извлечении из него знаний. Таким образом, целый ряд трудностей верификации БЗ ЭС, обусловленных спецификой технологических процессов разработки ЭС, таких как сложность получения и структурирования экспертных знаний, многообразие используемых языков представления знаний, отсутствие общепризнанных методов оценки результатов верификации БЗ и др., делает исследования в области верификации БЗ ЭС значимыми и актуальными.
Для нового поколения современных ЭС характерна способность сочетать решение неформализованных задач с задачами, решаемыми традиционными программами, что создает дополнительные трудности проверки правильности создаваемых для них БЗ. К таким системам, в частности, относятся системы типа интегрированных ЭС (ИЭС), где эти трудности связанны с масштабируемостью архитектуры ИЭС, позволяющей расширять функциональность систем с помощью дополнительных подсистем, что приводит к возрастанию числа стадий и итераций в моделях жизненного цикла построения отдельных компонентов ИЭС и повышению доли недостоверной и ошибочной информации.
В проведенных автором исследованиях использован практический опыт разработки прикладных интегрированных ЭС на основе задачно-ориентированной методологии (ЗОМ) и автоматизированной технологии, включающей инструментарий нового поколения АТ-ТЕХНОЛОГИЯ, в результате которого был выявлен ряд проблем, связанных с процессами верификации БЗ ИЭС. Основными из этих проблем являются значительные объемы содержащейся в БЗ ИЭС информации, приводящие к существенным вычислительным затратам, трудоемкость привлечении экспертов к процессам верификации БЗ ИЭС, необходимость учета неопределенных, неточных, нечетких и других видов недостоверных знаний, эксплицитно проявляющихся в рассуждениях экспертов. Однако, адекватных методов и средств верификации БЗ прикладных ИЭС в настоящее время практически не существует, поэтому исследование и разработка методов и средств верификации БЗ ИЭС, является актуальным.
Целью диссертации является исследование и разработка методов и инструментальных программных средств верификации БЗ ИЭС в рамках ЗОМ, повышающих степень автоматизации процессов построения поля знаний и БЗ для ИЭС.
Для достижения поставленной цели в диссертации решены следующие основные задачи.
1. На основе анализа существующих методов и средств верификации БЗ ЭС построена обобщенная модель обнаружения аномалий в БЗ ЭС.
2. Разработаны методы обнаружения статических и динамических аномалий в поле знаний и БЗ ИЭС, предусматривающие совместную обработку неопределенных, неточных и нечетких знаний.
3. Выполнен анализ системных требований и проектирование инструментальных программных средств верификации и корректировки поля знаний и БЗ в соответствии с ЗОМ.
4. Разработаны инструментальные программные средства верификации поля знаний и БЗ, включенные в состав комплекса АТ-ТЕХНОЛОГИЯ третьего поколения.
5. Проведена экспериментальная апробация предложенных алгоритмов и разработанных инструментальных программных средств верификации поля знаний и БЗ для задач медицинской диагностики и проектирования корпоративных информационно-вычислительных сетей.
Для решения поставленных задач в диссертации использованы методы искусственного интеллекта (модели и методы представления и обработки знаний, методы инженерии знаний), нечеткая математика, теория множеств, теория графов, теория построения трансляторов, технология разработки программного обеспечения.
В диссертации получены следующие новые результаты.
1. Построена обобщенная модель обнаружения аномалий в БЗ ЭС на основе выполненного анализа существующих методов и средств верификации БЗ ЭС.
2. Разработан оригинальный метод обнаружения статических аномалий в поле знаний и БЗ ИЭС, позволяющий учитывать случаи одновременного присутствия неопределенных, неточных и нечетких знаний.
3. Разработан оригинальный метод обнаружения динамических аномалий в поле знаний и БЗ ИЭС, который предусматривает совместную обработку неопределенных, неточных и нечетких знаний.
4. Впервые проведены исследования особенностей применения средств верификации на различных стадиях жизненного цикла построения ИЭС, влияющих на формирование и выполнение плана обнаружения аномалий.
5. Созданы оригинальные инструментальные программные средства верификации поля знаний и БЗ в ИЭС.
6. Разработан «мастер» автоматизированной корректировки поля знаний и БЗ, использующий данные протокола верификации об обнаруженных статических аномалиях в поле знаний и БЗ в процессе построения ИЭС.
В результате выполненных исследований разработаны модели, методы, алгоритмы и инструментальные программные средства, позволяющие снизить трудоемкость верификации и корректировки поля знаний и БЗ в процессе разработки прикладных ИЭС.
Основные научные результаты, выносимые на защиту: 1. Новая обобщенная модель обнаружения аномалий в БЗ ЭС, построенная на основе выполненного анализа существующих методов и средств верификации БЗ ЭС.
2. Оригинальные методы верификации поля знаний и БЗ в ИЭС, ориентированные на обнаружение как статических, так и динамических аномалий в поле знаний и БЗ, а также совместную обработку неопределенных, неточных и нечетких знаний.
3. Оригинальный подход к построению и исполнению плана верификации поля знаний, основанный на комбинированном использовании критериев охвата и метазнаний,
4. Комплекс инструментальных программных средств верификации и корректировки поля знаний и БЗ.
Практическая значимость проведенных исследований и полученных результатов заключается в разработке методов верификации поля знаний и БЗ, которые могут применяться для обнаружения нарушений целостности и согласованности в знаниях, представленных в виде объектов и правил, содержащих утверждения типа «объект-атрибут-значение-коэффициенты». Важной особенностью предложенных методов является возможность обработки значительных объемов информации, включающей, в том числе, неопределенные, неточные и нечеткие знания. Способность к обнаружению нарушений в большом объеме знаний достигается за счет комбинированного использования критериев охвата и метазнаний, что подтверждается результатами проведенных экспериментов.
Разработанные в диссертации инструментальные программные средства верификации поля знания и БЗ в составе комплекса АТ-ТЕХНОЛОГИЯ использованы при разработке отдельных компонентов для нескольких ИЭС, что подтверждается актами об использовании.
Во введении обоснована актуальность темы диссертации, её научная новизна и практическая значимость, сформулирована цель диссертационного исследования.
В первом разделе представлен анализ современного состояния в области верификации БЗ ЭС. Рассмотрены процессы верификации, как составляющие процессов жизненного цикла программного обеспечения вообще и ЭС, в частности. Показана роль верификации БЗ ЭС в процессах тестирования ЭС. Выделены проблемы, связанные с верификацией БЗ ЭС. В том числе, рассмотрены проблема верификации БЗ, содержащих различные виды НЕ-факторов, проблема «комбинаторного взрыва» при верификации БЗ ЭС, требующая пристального внимания при разработке ИЭС, в связи с тем, что создаваемые БЗ могут достигать достаточно больших объемов, проблемы верификации БЗ ЭС на этапе структурирования знаний. Приведены основные понятия и определения в области верификации программного обеспечения и показана их специфика для случая создания БЗ ЭС.
В диссертационном исследовании показано, что большинство современных методов верификации БЗ ЭС ориентированы в большей степени не на выявление конкретных ошибок, а на обнаружение логических аномалий, каждая из которых является признаком появления ошибок, относящихся к отдельной группе. Предложенная в диссертации классификация аномалий послужила основой для сравнения возможностей разнообразных методов и средств верификации БЗ ЭС по их способностям к обнаружению аномалий различных типов.
В диссертации также показано, что, несмотря на внешнее многообразие способов внутреннего представления знаний, на основе которых реализованы конкретные методы обнаружения аномалий, большинство методов основано на разновидностях правил, таблиц, логических моделей или графов. При этом значительное внимание в диссертации уделено анализу способов внутреннего представления, учитывающих случаи представления в БЗ ЭС НЕ-факторов знаний (термин НЕ-факторы впервые введен А.С.Нариньяни в середине 80-х годов). Показано, что такие случаи учитываются все еще не достаточно полно, причем у исследователей не выработано единого взгляда на природу и способы проявления знаний, содержащих НЕ-факторы (исключением является НЕ-фактор нечеткость, для которого в настоящее время существует более или менее универсальное определение).
В диссертации рассмотрена проблема «комбинаторного взрыва», возникающая с ростом объемов создаваемых БЗ, которая наиболее ощутима в алгоритмах обнаружения динамических аномалий, обладающих экспоненциальной временной вычислительной сложностью по отношению к количеству правил. Однако, предложенные на сегодня способы сокращения количества анализируемых комбинаций, среди которых наиболее распространенные основаны на индексации правил, включающей разбиение на кластеры, и использовании метазнаний, как правило, определяются особенностями конкретных видов внутреннего представления знаний.
В диссертации также исследованы вопросы, связанные с процессами верификации на этапе структурирования знаний, на котором информация, полученная от экспертов или других источников, структурируется, образуя поле знаний - полуформализованное описание знаний о предметной области в том виде, в каком его выразил инженер по знаниям (например, в виде графа, таблицы, диаграммы или др.). Поскольку структура поля знаний в одних случаях определяется конкретной методологией построения экспертных систем, в других - специально «изобретается» инженером по знаниям для конкретной проблемной области, то одной из возникающих на данном этапе проблем является применимость для верификации поля знаний уже существующих методов и программных средств.
Представленные в первом разделе диссертации проблемы верификации, связанные с представлением различных НЕ-факторов знаний и «комбинаторным взрывом», рассмотрены, прежде всего, с точки зрения верификации поля знаний, что имеет важное значение при использовании ЗОМ, включающей в жизненный цикл построения ИЭС этап структурирования информации, извлеченной из нескольких источников знаний (эксперты, естественно-языковые тексты, базы данных). Эти процессы характеризуются значительными объемами обрабатываемой информации, приводящими к существенным вычислительным затратам, постоянной потребностью в привлечении экспертов к процессу верификации поля знаний, необходимостью одновременного учета неопределенных, неточных и нечетких знаний, эксплицитно проявляющихся в рассуждениях экспертов. Однако, адекватных методов верификации, обеспечивающих решение данной группы проблем, в настоящее время не существует.
В конце первого раздела диссертации приводятся результаты анализа отечественных и зарубежных программных средств поддержки процессов верификации БЗ ЭС. Выделены базовые группы и рассмотрены функциональные возможности этих средств, связанные с особенностями реализации различных подходов к проверке целостности и согласованности знаний, обнаружению как статических, так и динамических аномалий, а также способы реализации отдельных методов выявления аномалий.
Показано, что несмотря на обилие созданных для этих целей различных программных средств, функционирующих как в составе многочисленных оболочек ЭС, так и автономно от других компонентов поддержки разработки ЭС, включая средства, предназначенные только для автоматизации этапа тестирования, в настоящее время, практически, не существует инструментальных программных средств, ориентированных на поддержку процессов верификации на всех этапах жизненного цикла разработки не только ИЭС, но и традиционных ЭС, не говоря уже о создании специальных средств обнаружения аномалий в поле знаний и БЗ проектируемых систем.
На основе выполненного в первом разделе диссертации анализа существующих методов и средств верификации БЗ ЭС делается вывод об актуальности темы диссертационного исследования, направленного на разработку эффективных методов и инструментальных программных средств верификации, повышающих степень автоматизации процессов построения поля знаний и БЗ для широкого класса прикладных ИЭС, в том числе проектируемых на основе ЗОМ.
Сформулирована цель и поставлены конкретные задачи диссертационного исследования. Во втором разделе диссертации рассматриваются теоретические вопросы разработки специальных методов верификации, ориентированных на выявление аномалий и предназначенных для использования на различных стадиях жизненного цикла разработки ИЭС. Под аномалиями понимаются наблюдаемые нарушения в поле знаний или БЗ.
Проведенный анализ существующих методов верификации БЗ ЭС позволил построить обобщенную модель обнаружения аномалий и использовать ее для разработки методов верификации поля знаний и БЗ в рамках ЗОМ.
Описан предложенный метод обнаружения аномалий статических аномалий, основанный на расширенных таблицах решений (РТР). По сравнению с существующими методами верификации БЗ, основанными на табличном представлении анализируемой информации, применение РТР позволяет обрабатывать поле знаний и БЗ, содержащие выделенные виды НЕ-факторов: неопределенность, неточность, нечеткость. В процессе построения РТР производится поиск нарушений целостности, а сформированная РТР используется для поиска нарушений согласованности.
Описан предложенный метод обнаружения аномалий динамической несогласованности, основанный на раскрашенных сетях Петри. По сравнению с существующими методами верификации БЗ, основанными на сетях Петри, сеть Петри формируется по РТР.
Особенностью разработанных методов обнаружения аномалий является то, что для каждого из них определено множество типовых действий, которые используются при формировании общего плана верификации поля знаний (или БЗ), что в целом позволяет снизить объем вычислений для текущих действий за счет проверки условий, зависящих от заданного критерия охвата и результатов предыдущих действий. К таким результатам относятся данные об уже выявленных аномалиях в правилах, а также в атрибутах и значениях атрибутов.
Третий раздел диссертации посвящен вопросам реализации в комплексе АТ-ТЕХНОЛОГИЯ инструментальных программных средств, обеспечивающих верификацию и корректировку поля знаний и БЗ с использованием разработанных методов обнаружения аномалий.
В процессе разработки были учтены требования последних версий комплекса АТ-ТЕХНОЛОГИЯ, основным из которых является реализация программных средств в виде компонентов, представляющих собой СОМ-объекты, выполняющие установленные правила обмена сообщениями с остальными компонентами комплекса, а также содержащие функции, обеспечивающие связь с типовыми проектными процедурами (ТПП), которые активизируются специальными средствами интеллектуальной поддержки разработки ИЭС. В связи с этим, разработанные в диссертации программные средства предназначены для поддержки двух ТПП «Верифицировать поле знаний» и «Верифицировать базу знаний», представляющих собой набор типовых действий инженера по знаниям на этапе верификации.
В диссертации представлена общая архитектура программных средств верификации и корректировки поля знаний и БЗ, описаны компоненты верификации поля знаний и БЗ и особенности компонент функционирования в составе комплексе АТ-ТЕХНОЛОГИЯ.
Четвертый раздел диссертации посвящен экспериментальной проверке и использованию разработанных программных средств для верификации и корректировки поля знаний и базы знаний в процессе разработки прикладных ИЭС.
Представлены результаты экспериментальной проверки разработанных программных средств, выполненной на данных, полученных при разработке нескольких приложений, связанных с задачами проектирования и медицинской диагностики. Выполнено сравнение реализованных программных средств с несколькими средствами обнаружения статических аномалий.
Описано применение средств верификации БЗ ИЭС при разработке прототипа ИЭС для проектирования и моделирования информационно-вычислительных сетей для ФГУП Концерн «Системпром». Представлено использование методов и алгоритмов обнаружения статических аномалий при разработке компонента анализа целостности и согласованности медицинских знаний в области эндоскопии. Компоненты входят в состав программных средств, обеспечивающих выполнение задач накопления медицинских знаний в рамках поддержки элементов «электронной истории болезни» в эндоскопическом отделении ЦКБ Гражданской авиации.
В заключении приводятся основные выводы и результаты диссертации. В приложение вынесены: акты об использовании результатов диссертационного исследования; примеры фрагментов поля знаний и БЗ, использованные для экспериментальной проверки разработанных средств верификации поля знаний и БЗ; тестовые примеры работы средств верификации и корректировки поля знаний и БЗ.
Достоверность научных результатов подтверждена экспериментальными данными проведенного тестирования разработанных программных средств, а также сравнением полученных результатов с данными, приведенными в научной литературе.
Основные результаты диссертации докладывались и обсуждались на национальных конференциях по искусственному интеллекту (Переславль-Залесский, 2000; Коломна 2002), Международном семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2005), ежегодных «Научных сессиях МИФИ» с 1998 по 2006 гг.
Основные результаты диссертационного исследования опубликованы в шести печатных трудах, в том числе в одной статье в журнале, включённом ВАК РФ в перечень ведущих рецензируемых научных журналов и изданий, в трех сборниках трудов.
Проблема верификации баз знаний, содержащих различные виды НЕ-факторов
В настоящее время существует значительное число разнообразных представлений знаний, которые используются как в языках представления знаний, так и для формирования ПЗ. В частности, разнообразие языков представления знаний связано с их способностью представления различных видов НЕ-факторов (термин впервые введен А.С.Нариньяни в середине 80-х годов), под которыми понимаются, например, следующие [52]: - неопределенность, обусловленная тем, что не все объекты и связи между ними можно априорно полностью определить, - неточность, вследствие которой, в частности, числовые и иные количественные оценки, заданные в виде интервалов допустимых значений, - некорректность ряда определений и закономерностей, занесенных в БЗ или полученных на основании конечной совокупности наблюдений за эмпирическими фактами, - неоднозначность выводов, - недетерминированность ряда положений, - нечеткость, возникающая в случае, когда эксперт пытается количественно охарактеризовать качественные понятия и отношения, которые он использует в своих рассуждениях.
Можно привести достаточно большое число определений и других известных НЕ-факторов, однако, в настоящее время более или менее универсальное определение существует только для одного из отмеченных НЕ-факторов - нечеткости [11]. Трудности верификация БЗ ЭС, в которых представлены знания, содержащие различные виды НЕ-факторов, связаны с тем, что для остальных НЕ-факторов у исследователей не выработано единого взгляда на их природу и способы проявления в экспертных знаниях, и, кроме того, преобразование НЕ-факторов друг в друга не всегда возможно [53].
Значительное число работ, посвященных проблеме построения полных и непротиворечивых БЗ, связано с проблемами обнаружения нарушений в БЗ, относящихся к НЕ-факторами неполнота и не-непротиворечивостъ Анализ таких работ показывает тесную связь этих НЕ-факторов с основными группами аномалий в БЗ ЭС.
О полноте знаний в БЗ говорится в целом ряде работ, например, [4,5,42,47,53,56,57,58], в частности, в связи с тестированием (верификацией) ЭС, например, [4,42,56,47,59]. Понятие «полнота» может трактоваться по-разному.
В классических логических системах свойство полноты обычно формулируется следующим образом [8]: для множества формул с заданными свойствами исходная система аксиом и правил вывода должна обеспечить вывод всех формул, входящих в это множество. В ИИ применяются формулы в виде конструкции предикат-аргумент [60], синтаксис которых можно представить следующим образом: утверждение "= предикат ( аргумент ),.., аргумент )
Здесь применима следующая формулировка свойства полноты в терминах некоторой системы утверждений [61]: все истинные утверждения, которые формулируются на языке некоторой системы утверждений могут быть доказаны в этой системе (семантическая полнота); присоединение к некоторой системе утверждений в качестве аксиомы какого-то недоказуемого в ней утверждения ведет к противоречию (синтаксическая полнота).
Также существуют различные трактовки понятия «непротиворечивость». Как отмечено в работе [61], закон противоречия впервые сформулировал Аристотель, который утверждал: "Невозможно, чтобы одно и то же в одно н то же время было и не было присуще одному и тому же в одном и том же отношении". С формальной точки зрения противоречия - это аналитически ложные положения, представляющие собой "логическую ложь" при произвольной предметной интерпретации логических переменных, а поэтому неспособные выражать объективных истин [61].
В логике формулируют четыре смысла непротиворечивости: непротиворечивость относительно отрицания, тривиальная непротиворечивость, непротиворечивость в смысле Поста, семантическая непротиворечивость. При этом, как отмечено в работе Д.А.Поспелова, в классических логических системах свойство непротиворечивости сводится к тому, что исходная система аксиом и правил вывода не должна давать возможность выводить формулы, не принадлежащие заданному множеству с выбранными свойствами. Следует отметить, что непротиворечивость может рассматриваться как частный случай полноты, которая в этом случае понимается как неполнота в широком смысле [8].
Существуют также различные более узкие трактовки полноты и непротиворечивости, относящиеся непосредственно к свойствам баз знаний ЭС, некоторые из которых представлены в таблице 1.3.
Таким образом, отсутствие единого взгляда исследователей на НЕ-факторы, в частности, на неполноту и не-непротиворечивостъ БЗ ЭС, тесно связанные с различными группами аномалий в БЗ ЭС, создает проблему для однозначного определения критериев верификации БЗЭС.
В следствие различных точек зрения на природу НЕ-факторов, существуют их различные классификации. Так как исследования данной диссертации выполнены в рамках ЗОМ, в соответствии с которой знания извлекаются из разных источников (эксперты, естественноязыковые тексты, базы данных), то в данной диссертации за основу взята классификация НЕ-факторов, предложенная в работах [53,55], в которой выделены 2 группы НЕ-факторов в зависимости от возможности их выявления в знаниях эксперта на
основе комбинированного метода приобретения знаний (КМПЗ), применяемого в рамках ЗОМ и включающего модели, методы и процедуры извлечения знаний из экспертов и проблемно-ориентированных текстов, их последующего структурирования и верификации с целью автоматизированного построения адекватной, полной и непротиворечивой БЗ о проблемной области.
Методы обнаружения динамических аномалий, основанные на логике первого порядка
В целом ряде методов обнаружения динамических аномалий в БЗ использована логика первого порядка. Такие методы обычно основаны на предположениях или имитации логического вывода.
Одним из методов обнаружения динамических аномалий в БЗ, основанных на логике первого порядка является метод, использующий идеи так называемой Assumption-based Truth Maintenance System (ATMS) [99], т.е. системы поддержания правильности, основанной на предположениях. Алгоритмы, реализующие данный метод, находят множество предположений, которые должны приводить каждую гипотезу БЗ к истине. Такие множества предположений называют метками гипотез. Метка L(h) для гипотезы h - это выражение, которое является минимальной дизъюнктивной нормальной формой. Каждый элемент такого выражения является решением. Конъюнкция меток именуется окружением для й, Е{И). БЗ считается противоречивой, если существуют окружения гипотез, включенные в это ограничение таким образом, что их объединение непротиворечиво. Избыточность вычисляется путем расчета вклада каждого правила г, включающего h в L{h ). Если вклад г нулевой или предполагается вклад других правил, то правило г является избыточным и может быть удалено. Примерами средств верификации, использующих идеи ATMS являются KB-Reducer [100], МЕСОШ [101], COVER [102] и COVERAGE [65].
Другим методом обнаружения динамических аномалий в БЗ, является метод, сочетающий логику первого порядка с имитацией расширенного прямого вывода, при котором допустимо достижение специального факта «ложь». В данном методе несогласованность определяется с помощью ограничений целостности, накладываемых на входные значения и представленных с помощью правил, в заключениях которых содержится факт «ложь». Когда выполняется ограничение целостности, факт, приведший к заключению «ложь» показывается эксперту для оценки причин несогласованности БЗ. Данный метод использован в системе COVADIS [103]. Существуют и другие способы имитации вывода при верификации БЗ, например, в работе [57] применяется гипертвод, в работе [104] используется имитация обратного вывода.
В ряде работ для обнаружения динамических аномалий в БЗ использовано представление анализируемой информации в виде графов. Применяются графы различного вида. Например, в системе CHECK [96] применяется граф зависимостей правил, что позволяет обнаружить циклы, в системе SVEPOA[105] для обнаружения динамических аномалий используется граф зависимости данных, в работе [45] проверка непротиворечивости БЗ методами линейного программирования выполняется на основе Байесовской сети.
Так как значительное число работ посвящено методам верификации БЗ, основанным на сетях Петри, например [68,103,106], поэтому рассмотрим особенности этих методов более подробно.
Существует целый ряд классов сетей Петри. Сеть Петри [107] С представляет собой четверку вида С= Р,Т,1,0 , где Р={рьР2,-5Рп} конечное множество мест, п 0; Т={1],Т2,...,1т} - конечное множество переходові т 0, причем множество мест и множество переходов не пересекаются (РпТ=0); I: Т- -Р - отображение из переходов в комплекты мест (I называется входной функцией); О: T- Q - отображение из переходов в множество Q (О называется выходной функцией), где множество Q зависит от класса сетей Петри. Например, в простых (ординарных) сетях Петри Q=P. Маркировка сети Петри есть функция, отображающая множество позиций Р в множество N, которое зависит от класса сети Петри. Маркировка сети Петри предназначена для моделирования ее динамических характеристик. Маркировка сети Петри может быть комплектом, т.е. конечной совокупностью объектов, в которой могут встречаться одинаковые объекты. Выходная функция сети Петри может содержать пост-операцию, т.е. операцию изменения структуры сети Петри путем вставки или удаления мест или переходов. Распространенные классы сетей Петри могут быть сгруппирован по типу маркировки и типу выходной функции. Рассмотрим особенности основных группы сетей Петри. Группа 1. N - {true,false} О: Т-»Р. Примерами классов сетей Петри данной группы являются системы условие-действие, элементарные сети, машина состояний. Группа 2. N - множество целых чисел, О: Т-»Р. Примером сетей данной группы являются сети место-переход.
Группа 3. N - является комплектом, О: Т-»Р. В качестве примеров сетей данной группы Быстпают сети Петры высокого уровня, сети окружение-отношение, сети изделии (Product Nets), сети предикат-переход, раскрашенные сети Петри.
Группа 4. N - является комплектом, О: T-»D,T »P. Примером сетей данной группы являются динамические сети Петри.
Метод обнаружения динамических аномалий в БЗ, в котором комбинируются сети Петри, представление информации в виде матриц и имитация обратного вывода, использован для верификации БЗ в системе DAPS [104]. Процесс верификации состоит из трех шагов. На первом шаге выполняется преобразование БЗ в раскрашенную сеть Петри, по которой формируются матрицы входа и выхода, позволяющие выбрать потенциально аномальные правила путем анализа количества входящих и исходящих дуг. На втором шаге выполняется просмотр сети Петр для того, чтобы выделить входные условия потенциально аномальных правил. На третьем шаге выявляются реальные аномалии с помощью анализа входных условий, которые определяются с помощью имитации обратного вывода, начинающегося с потенциально аномальных правил.
Метод обнаружения статических аномалий в ПЗ и БЗ, основанный на таблицах решений
Анализ работ в области верификации БЗ, представленный в разделе 1., показал, что в ранних методах верификации при обнаружении статических аномалий в качестве формализмов внутреннего представления знаний применялись различные виды табличного представления (таблицы решений, таблицы связей правил и др.). Однако, и в более поздних методах использованы разновидности таблиц решений, но уже в сочетании с другим формализмами (например, графы, сети Петри и др.), что особенно характерно для методов обнаружения динамических аномалий. Такой подход развивается и в данной работе, причем особенностью разработанных методов является то, что для обнаружения статических аномалий используются таблицы решений, которые также являются источником информации для метода обнаружения динамических аномалий, основанного на сетях Петри, который описан в следующем разделе.
Ниже будут описаны статические аномалии, для обнаружения которых в диссертации использованы таблицы решений. Сначала дадим определения нарушениям целостности, основные из которых представлены на Рис. 1.6. К ним относятся недостижимые заключения, неверные значения атрибутов, лишние if-условия, Не использованные значения атрибутов, атрибуты без ссылок.
Недостижимые заключения (отсутствие правил, приводящих к значениям целевых атрибутов). Данная аномалия имеет место, в случаях, когда некоторые значения атрибутов, участвующих в действиях правил не используются ни в каких действиях правил или встречаются в действиях таких правил, которые ни когда не могут быть выполнены. Например, следующее правило не выполнимо: IF Х=1 & Х=2 THEN Y=3.
Неверные значения атрибутов - значения атрибутов, которые не соответствуют ограничениям, наложенным на множества значений атрибутов. Например, из-за ограничения X є [2,5] в правиле IF X=l THEN Y=3 значение атрибута X является неверным.
Лишние if-условия - наличие таких подмножеств утверждений в посылках правилах, которые не влияют на результат применения правил. Например, в правиле IF Х=1 & Х=1 THEN Y=3 одно из утверждений «Х=1» является лишним if-условием.
Не использованные значения атрибутов - значения атрибутов, на которые нет ссылок ни в посылках, ни в действиях правил. Атрибуты без ссылок - атрибуты, которые не использованы ни в одном правиле (частный случай неиспользованных значений атрибутов).
Представленные выше определения статических аномалий соответствуют нарушениям целостности. Ниже будут даны определения статическим нарушениям согласованности, для которых предварительно будут введено понятия нормализации, определены основные типы утверждений и функции их сравнения.
Определения будут даны для правил, которые представлены в следующем виде, который буем назвать нормализованным: РІЛР2Л...ЛР,.І- Р,лРніл...лРь (2.1) где Pi, Д-утверждения правила
Для того, чтобы правила ПЗ или БЗ преобразовать в правила вида (2.1) требуется выполнить нормализацию, например, используя преобразования, представленные в работе [68]. Если правило имеет следующий вид PivP2v...vPj.i- Р Р л.-.лРк, (2.2) то преобразование производится следующим образом: PlVP2V...vPj.i- PJAPJ+iA...APk s-,( PivPav„.vPj.) v (РучР л-.лРк) = (-iPlV-iP2V...V-iPj.i) V ( PjA Pj+іЛ...лРк) 4(-,PlV(PjA PJ+IA...APk)] Л [(-,P2V(PjA Pj+iA APk)] Л...Л [(-.PJ.JV JA Pj+іЛ...лР )] =[(Pl- (PjA PJ+lA...APt) ] A [(P2- (PjA Pj+іА...лРк)] A...A [(PjJ-KPjA PJ+lA...APk)]. Для правил более сложного вида, чем (2.2) преобразования выполняются аналогичным образом.
Особенностью анализируемого представления знаний является то, что утверждения Pi,. Д в правилах ПЗ и БЗ представляют собой пары типа «атрибут-значение», снабженные коэффициентами, позволяющими представить НЕ-факторы неопределенность, неточность и нечеткость, которые в соответствии с ЗОМ эксплицитно проявляются в рассуждениях эксперта. Основываясь на результатах работ ЛЗаде, утверждения Рі, Д можно рассматривать как частные случаи обобщенного ограничения вида «a isr R», в котором isr является переменной связкой, определяющей способ, которым R ограничивает переменную (атрибут) а [120,121].
Среди всего многообразия ограничений вида «a isr R» в диссертации рассматриваются только случаи представления достоверных знаний и НЕ-факторов неопределенность, неточность и нечеткость, предусмотренных в ЗОМ. В связи с этим примем, что каждое утверждение Р, которое используется в посылках и действиях правил имеет следующую структуру Р=(аД), где а - конкретный атрибут, R - ограничение, накладываемое на атрибут а, которое проверяется в посылке правила или устанавливается в действии правила и может включать операцию сравнения # є { =Y Y YY2sY Yin }» значения v (число или символ) или (д (функция принадлежности) и коэффициенты. Все операции, кроме = используются только в посылке правил. В том, случае, когда в утверждении имеет место операция in , v представляет собой интервал числовых значений, т.е. v=[vl,v2]. Функция принадлежности ц может использоваться в ограничениях только в сочетании с операцией = .
Ниже рассматриваются основные типы утверждений Рі, Д, предусмотренные в ЗОМ. «Достоверное» утверждение имеет место, если ограничение, накладываемое на а, еще зависит значения v, и а является числовым или символьным атрибутом, т.е. R=(#,v).
«Неопределенное» утверждение характеризуется наличием одного коэффициента уверенности tle[0..1], обозначающего вероятность того, что результат сравнения а с v является верным, т.е. R=(#,v,tl), или присутствием двух коэффициентов уверенности t2, іЗє[0..1], соответствующих необходимой (t2) и возможной (t3) вероятности того, что результат сравнения а и v является верным, т.е. R=(#,v,t2,t3), х - числовой или символьный атрибут;
«Неточное» утверждение имеет место, когда числовой атрибут а сравнивается числом v, определенным с точностью до коэффициента і4є[0..1], который является относительной погрешностью измерения числового значения v, т.е. R=(#,v,t4)
«Нечеткое» утверждение содержит лингвистическую переменную а, которая сравнивается с функцией принадлежности u, R=(#,u). Введем определение равных утверждений,
Определение. Два ограничения Ri и R2, связанные с одним и тем же атрибутом в утверждениях правил, равны, если совпадают операции и все коэффициенты в этих ограничениях. Такое равенство будем обозначать как RJ RJ.
В ПЗ, формируемом с использованием средств инструментального комплекса АТ-ТЕХНОЛОГИЯ, предназначенного для построения прикладных ИЭС на основе ЗОМ, в результате извлечения знаний из эксперта, то есть основного источника знаний, операция сравнения # в утверждениях принимает только значение - , поэтому далее ограничимся рассмотрением утверждений только такого типа.
Проектирование средств обнаружения динамических аномалий в ПЗ и БЗ
Интерфейсы компонента обнаружения динамических аномалий в ПЗ или БЗ по сети Петри на Рис. 3.6, из которого видно, что компонент использует РТР, а также дополнительную информацию из ПЗ (или БЗ) для формирования сети Петри, обмениваясь при этом информацией с компонентом исполнения плана верификации.
При обнаружении динамических аномалий в ПЗ, компонент формирует ограничения на начальную и конченую раскраску сети, которые устанавливаются на основе признаков, позволяющих отнести утверждения в правилах к соответствующим элементам моделей решения типовых задач. Тем самым удается сократить количество анализируемых цепочек, т.е. уменьшить объем вычислений. Типовые действия по выявлению динамических аномалий представлены в разделе 2.
По сравнению с фрагментами протокола верификации, формируемыми компонентами обнаружения статических аномалий, данный компонент добавляет в протокол записи об аномальных цепочках правил, в каждой из которых содержатся ссылки на все правила, образующие данную цепочку. Средства визуализации протокола верификации (раздел 3.6) позволяют выполнить быстрый переход к режиму редактирования любого правила, представленного в записи протокола об аномальной цепочке правила, что особенно удобно, для длинных цепочек правил.
В случае использования критерия охвата правил, все правила, входящие в любую аномальную цепочку, исключаются из дальнейшего анализа, тем самым при наличии значительного количества аномальных цепочек скорость анализа сети Петри значительно увеличивается.
Особенность разработанных средств обнаружения статических и динамических аномалий заключается в использовании компонентов построения и исполнения плана верификации, который может изменяться в зависимосга от исходных настроек, состоящих из множества искомых типов аномалий и выбранного критерия охвата, за счет чего, с одной стороны, изменяется полнота формируемых протоколов верификации баз знаний, а с другой -скорость получения результатов. Так как в процессе исполнения плана верификации проверяются условия выполнения отдельных действий, то порядок обнаружения аномалий оказывается зависимым от множества аномалий, обнаруженных в результате предшествующих действий, что в целом позволяет исключить действия, не существенные с точки зрения критериев охвата, сократив тем самым время обработки данных.
Проектирование средств формирования и исполнения плана верификации поля знаний и базы знаний включает в себя разработку компонента ввода настроек плана верификации ПЗ или БЗ, компонента построения плана верификации ПЗ или БЗ, компонента исполнения плана верификации ПЗ или БЗ, а также организацию взаимодействия этих компонент друг с другом и с компонентами обнаружения и корректировки нарушений в ПЗ и БЗ. Схема взаимодействия компонент, участвующих в формировании и исполнении плана верификации ПЗ или БЗ показана на диаграмме (Рис. 3.7).
Для предоставления инженеру по знаниям возможности влиять на процесс построения плана верификации ПЗ или БЗ, реализован пользовательский интерфейс, позволяющий задать множество типов искомых аномалий и критерий охвата путем указания на экранной форме соответствующих флагов. В процессе построения плана верификации флаги влияют на отбор типовых действий. Флаги настроек плана верификации представлены в таблице 3.1.
Тестирование БЗ ЭС включает процесс улучшения качества (refinement) БЗ, под которым, обычно, понимается внесение изменений в БЗ при возникновении некорректных решений. Процесс улучшения качества БЗ включает в себя следующие этапы: - определение правил или отдельных условий, приводящих к не верным решениям, - создание списка возможных изменений в БЗ, - выбор наиболее эффективных изменений в БЗ.
Традиционно, процесс улучшения качества БЗ ЭС выполняется на этапах реализации, отладки и тестирования, опытной эксплуатации и внедрения [3]. В рамках ЗОМ [7] возможно начать процесс улучшения качества БЗ ЭС уже на этапе построения ПЗ, так как на данном этапе предусмотрено проведение верификации ПЗ, а формируемый при этом протокол верификации может быть использован для улучшения качества ПЗ.
Протокол верификации ПЗ содержит информацию о нарушениях в структурах ПЗ, соответствующих определенным типам аномалий со ссылками на фрагменты ПЗ, в которых обнаружены нарушения, и ссылками на список возможных изменений в ПЗ для устранения обнаруженных нарушений.
Для выбора наиболее эффективных изменений из списка возможных изменений ПЗ, устраняющих статические нарушения, в комплексе АТ-ТЕХНОЛОГИЯ применяется мастер корректировки ПЗ, который содержит знания о способах исправления нарушений в ПЗ, полученных из опыта применения инструментального комплекса АТ-ТЕХНОЛОГИЯ для разработки прикладных интегрированных экспертных систем. Мастер последовательно активизирует шаги устранения нарушений для каждой из следующих групп статических нарушений в ПЗ: - недопустимых значений атрибутов, - значений атрибутов, на которые нет ссылок, - атрибутов, на которые нет ссылок, - замыканий правил, - избыточных правил,
