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

р- 5 СЕН

российская академия наук

институт проблем информатики

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

ПРОНИНА Инна Генриховна

УДК 681.3.016

МЕТОДЫ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА ПОДДЕРЖКИ ПРОДУКЦИОННЫХ БАЗ ЗНАНИЙ, СОДЕРЖАЩИХ ПРАВИЛА С ИНТЕРВАЛЬНЫМИ ЗНАЧЕНИЯМИ ХАРАКТЕРИСТИК В ПРЕДИКАТАХ

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

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва - 1994

Работа выполнена в Институте проблем информатики Российской

Академии Наук

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

И.Г.Поспелов

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

И.П.Кузнецов кандидат технических наук В .Ф.Хорошевский

Ведущая организация - МИФИ

Защита состоится "_"_ 1994 года в_час на

заседании специализированного совета Д 003.56.01 при Институте пробле] информатики Российской Академии Наук по адресу: 117334, ГСП-г.Москва, В-334, ул. Вавилова, д. 30/6.

С диссертацией можно ознакомиться в библиотеке Института проблем информатики РАН.

Автореферат разослан августа 1994 года.

Ученый секретарь специализированного совета доктор технических наук

С.Н.Гринченко

I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Экспертные системы (ЭС), появившиеся в конце 60-х годов в качестве исследовательских проектов (MYCIN, PROSPECTOR, CASNET, DENDRAL), к настоящему времени стали одной из серьезных коммерческих отраслей информационной индустрии. Рынок программного обеспечения в этой области стабильно и быстро расширяется. Устойчивый интерес к технологии ЭС обусловлен тем, что они позволяют решать так называемые слабо формализуемые задачи, что до недавнего времени было исключительной прерогативой людей . Кроме того, аккумулируя практический опыт специалистов в определенной проблемной области, ЭС делают их знания и опыт доступными для использования другими людьми, позволяют быстро и эффективно проводить процесс обучения.

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

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

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

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

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

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

-3 -

При этом решаются следующие задачи:

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

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

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

4. Программная реализация и внедрение системы поиска противоречий (СПП) как компоненты инструментальной ЭС ЭКРАН (ИЭС ЭКРАН).

5. Анализ способов взаимодействия ЭС и СУБД, разработка принципов организации интерфейса ИЭС ЭКРАН с внешней СУБД.

6. Разработка СУБД, способной функционировать как автономно, так и во взаимодействии с ЭС.

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

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

- разработана модель системы продукций с интервальными значениями характеристик в предикатах (ИСП); дано оригинальное определение непротиворечивой системы продукций;

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

- определены понятия полной и частичной противоречивости ИСП, обоснован механизм их выявления;

- определены условия формирования параллельных пространств вывода при поиске противоречий в ИСП, введены понятия информативных и неинформативных пространств; предложен принцип сужения множества параллельных пространств вывода;

- предложен метод организации взаимодействия ЭС и СУБД т обеспечения информационной поддержки работы машины вывода.

Практическая ценность и внедрение результатов работы. Результата проведенных исследований использованы при разработке:

- системы поиска противоречий в составе инструментальной ЭС ЭКРАЬ Использование СПП позволило сократить время отладки БЗ и повысит качество проводимых экспертиз за счет своевременного и полного выявления противоречий в продукционных БЗ;

- СУБД общего назначения и системы создания отчетов в составе ИЭС ЭКРАН;

- ИЭС ЭКРАН-ХТС - интегрированной ЭС синтеза теплообменных систем установок первичной переработки нефти;

- ЭС синтеза теплообменных систем;

- автоматизированной обучающей ЭС ИПИЛОГ;

- автоматизированной информационно-аналитической системы (АИАС) "Контроль хода выполнения Долговременной программы комплексного развития производительных сил Дальневосточного экономического района, Читинской области и Бурятской АССР";

- автоматизированной информационной системы "Банки данных России";

- автоматизированной информационной системы "Токсичные отходы цветной металлургии";

- АИАС "Утилизация технологического сырья на территории РСФСР

ИЭС "ЭКРАН" сдана в Казанский ФАП, а прикладные системы вне дрены и используются в ИЛИ РАН, ЦНИИПроекте, НИХТИ, Российски химико-технологическом университете, АО "ЭТМ", Академии технических наук РФ. Результаты практического внедрения подтверждены справками о внедрении.

Апробация работы. Основные положения работы докладывались на научном семинаре ЦРДЗ "Экспертные системы. Базы знаний и данных' (Москва, 1992), на научном семинаре Московского Дома научно-технической пропаганды "Экспертные системы на персональных компьютерах" (Москва, 1990), на Всесоюзной конференции "Диалог Человек-ЭВМ" (Свердловск, 1989), на всесоюзных совещаниях "Проблемы применения вычислительной техники и автоматизированных систем в управлении комплексным социально-экономическим развитием регионов"

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

Публикации. По материалам диссертационной работы опубликовано 8 печатных работ.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. Общий объем диссертации - 136 страниц, список литературы содержит 79 наименований. В работе 16 рисунков и 2 таблицы.

II. СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассматриваются продукционные системы, которые оперируют с п переменными (атрибутами), а каждая продукция Р имеет вид:

Вр(х) Ар(х),

где х = (XI.....хп) - набор значений переменных (точка п-мерного пространства), а посылка (условие) продукции Вр(х) и заключение Ар(х) суть предикаты, т.е. функции на п-мерном пространстве со значениями в множестве {ИСТИНА,ЛОЖЬ). Обозначим множества истинности посылки и заключения продукции Р через Вр и Ар соответственно: Вр= {х: Вр(х) = ИСТИНА}; Ар= {х: Ар(х) = ИСТИНА}.

Продукция Р, рассматриваемая как предикат, истинна на множестве Тр = (-.Вр) (Вр г\ Ар) и ложна на множестве Бр = Вр п

Назовем множество Трэф = Вр п Ар (1)

эффективным множеством истинности продукции Р.

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

Определение 1: СП называется непротиворечивой, если для каждого входящего в нее правила Р найдется набор значений атрибутов х такой, что:

- правило Р применимо к х ( х еВр)

-¿г({х})*0,

где I/ ({х}) - результирующее "состояние мира", полученное на основе применения процедуры логического вывода к состоянию {х} в рассматриваемой СП.

Доказано, что, используя (1), определение 1 можно переформулировать следующим эквивалентным способом:

Определение Г: СП называется непротиворечивой, если для каждого входящего в нее правила Р

ТРэф (2)

где Т = пр Т^- множество истинности СП.

Приведенное определение непротиворечивости допускает эффективную проверку по крайней мере для одного достаточно распространенного класса продукционных экспертных систем - интервальных СП (ИСП). Для удобства их описания введено несколько определений. Брусом В ={х:у] называется подмножество п-мерного пространства, представимо-го как декартово произведение п сегментов (открытых, замкнутых или полуоткрытых интервалов) по п переменным. Брус задается двумя точками х,у - концами его диагонали. Обозначим через щВ проекцию бруса В на ось

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

Полосой С называется брус, неограниченный в обе стороны по всем направлениям кроме одного:

С = { (-оо,...,-оо,а|,-оо,...,-оо) : (+оо,...,+оо,Ь{,+оо,...,+оо)}.

Продукция, у которой область истинности посылки - брус, а область истинности заключения - полоса называется интервальной. В дальнейшем рассматриваются только СП, состоящие исключительно из интервальных продукций. Показано, что к интервальным продукциям могут быть сведены и продукции несколько более общего вида: В1(х) ОЯ В2(х) ОЯ...ОЯ В^(х) А(х), где области истинности предикатов В],В2,...,В^,А - брусы.

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

оценка метода показала, что он мало пригоден для практического использования из-за большого объема вычислений.

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

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

На этапе обратного вывода в качестве начального приближения берется Т^эф = {(-оо,...,-оо):(оо,...,оо)}. Из множества продукций выбираете: очередная продукция Р, которая становится корнем выстраиваемого дерева обратного вывода, а ее заключение - А^ - целью для обратного вывода. (В качестве корней перебираются поочередно все продукции СП, не вошедшие в протестированные ранее непротиворечивые цепочки обратного вывода). Пересечение тЯ^ф гч ф дает следующее приближение 7"*3ф . Затем выбирается неактивизированная продукция О, для которой выполняется условие:

31 б 1,п: я^эф С (-оо; 00) И с ^Т^ф (3)

Это условие есть условие активизации продукции в режиме обрат ного вывода. Пересечение Г^эф и ^эф дает следующее приближена Т^эф, соответствующее цепочке продукций (Р,0), и т.д. Если на шаге при подключении к цепочке {Р,0,...,Ы} продукции Б окажется, что

^эф=^эф^^эф = 0. (4)

то это означает, что цепочка продукций {Р,С2,...,8} содержит противореча Тестирование текущей цепочки обратного вывода заканчивается либо в случае обнаружения противоречия , либо если в СП не осталось ни одной неактивизированной продукции, удовлетворяющей условию (3).

При выборе подходящей продукции возможна коллизия: на шаге 1 существует множество продукций {(^ , )-1,к, 1<к<т], удовлетворяющих (3) для одного и того же ¡. В этом случае цепочка вывода продолжается в "параллельных пространствах вывода" с использованием механизма возврата (бэктрэкинга).

Одним из результатов процедуры обратного вывода является сформированное исходное состояние Ьд (множество значений исходных атрибутов). Если Ъд = 0, то это означает, что рассматриваемая цель А^ недостижима.

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

£ (5)

Пересечете и дает следующее приближение Г^ф. Далее выбирается неактивизированная продукция N. удовлетворяющая (5), и определяется Г^эф и т.д. Если на шаге I при подключении к цепочке {Р,...,М} продукции Б выполнится условие ( 4), то это означает, что цепочка продукций {Р,...,8} содержит противоречие.

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

Определение 2. ИСП полностью противоречива, если при подключ! нии к цепочке логического вывода какой-либо продукции 8 выполняется условие (4). ИСП частично противоречива, если при подключении к цепо чке логического вывода какой-либо продукции Р выполняется условие: 31 б 1,п: с (-со;оо ) и

тг^ п 71; Д с ти^ для прямого вывода (6)

или щВ" С (-оо;оо о для обратного вывода (7)

Подключение условий (6) и (7) к условию (4) в методе целенапрг вленного перебора позволяет одновременно осуществлять поиск полных е частичных противоречий в ИСП.

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

На определенных этапах логического вывода методом целенапра: ленного перебора текущее пространство вывода, определяемое множество) Гэф формирующих его продукций, может распадаться на ряд параллельны подпространств {7^, к = 1,х, г < гп), для обхода и тестирования когорт используется процедура возврата бэктрэкинг.

Определение 3. Подпространством логического вывода из эффективного множества истинности Тэф называется такое множество с Гэф для которого процедура логического вывода из всех точек х е 7^ одинакова.

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

а) для прямого вывода:

УР е П^ и V/ е 1,п: если пуГ^ с (-«?, оо), то т^Т^ с 7Г|ВР

б) для обратного вывода:

УР е П^ Зj такое, что 7^7^ с {-<хт, со) и 7^ЛР с 7^7^ и УО е Пк, О * Р : = {-со, со)

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

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

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

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

продукций: = { С^, Ы1,а, а < т ], при этом \fTfc с Пк. Образующиеся в процессе логического вывода параллельные пространства можно разделить на два класса: информативные и неинформативные.

Определение 4. Пространство логического вывода информативно, если Уге1,Г. Ъ^ <2 Ъг

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

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

Рассмотрены особенности формирования информативных пространств для определения частичных противоречий. В этом случае Пк (и соответствующие им Ъ^) должны быть дополнены множествами продукций П'к для которых выполняются условия: УР е П'^ : 3 } е 1,п такое, что а (-оо, оо) и с (-оо, со), и Гк п -тАр * 0, где П'к с Пк.

Информативное пространство в этом случае определяется следующим образом: пространство вывода Гк информативно, если У г е1,г. Ъ^ссЛ^ или Ъ\ <2 Тг Описана пошаговая процедура распараллеливания пространства логического вывода и определения его информативного подмножества по нескольким переменным.

В последнем разделе главы приводится алгоритм поиска противоречий в ИСП, основанный на методе целенаправленного перебора.

В третьей главе описана система поиска противоречий (СПП) в ИСП, разработанная на основе подходов, изложенных в главе 2. СПП входит в состав ИЭС ЭКРАН и представляет собой формальный механизм поддержки работы эксперта.

Возможности СПП ЭКРАН:

1. Семантический анализ БЗ:

- построение цепочек вывода в параллельных пространствах;

- анализ цепочек на полную и частичную непротиворечивость;

- определение конфликтных пространств вывода для частично противоречивых цепочек;

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

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

- выявление в БЗ недостижимых целей;

- определение циклов;

- определение выводимых запрашиваемых атрибутов.

2. Синтаксический анализ БЗ:

- контроль за соблюдением форматов записей файлов БЗ;

- контроль согласованности между файлами БЗ.

3. Просмотр БЗ в различных режимах.

Описана архитектура СПП ЭКРАН, основу которой составляют следующие подсистемы: внешний интерфейс; синтаксический анализ БЗ статический семантический анализ БЗ; динамический семантический анализ БЗ; просмотр БЗ.

В четвертой главе описаны принципы взаимодействия ЭС с внен ней СУБД, а также СУБД общего назначения ЭКРАН, способная функци» пировать как в комплекс с ЗС, так и автономно.

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

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

- динамическая организация;

- использование общего пула памяти для обмена информацией между ЭС и СУБД;

- архивирование запросов к БД;

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

- два способа пересылки данных из БД в ЭС: автоматический или через пользователя;

- использование расширенного модуля обработки запросов СУБД ЭКРАН.

Описаны принципы организации сильной связи между ИЭС ЭКРАН и СУБД ЭКРАН, а также разработанная СУБД ЭКРАН, способная функционировать как в комплексе с ЭС, так и автономно. Основные характеристики СУБД ЭКРАН: реляционный тип; возможность организации словарей с целью компактного хранения данных; мощный язык запросов, позволяющий работать в одном запросе с полями нескольких таблиц; возможности гибкого определения разнообразных связей между таблицами (связи 1:1, 1:М, позиционная связь, связь через условие); возможности сортировки БД и генерации отчетов.

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

-16 -

III. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Предложены два метода выявления противоречий в ИСП: метод полиогс и метод целенаправленного перебора. Показаны преимущества второго метода по сравнению с первым.

3. Разработана стратегия целенаправленного перебора для поиска противоречий в ИСП, основанная на введенном понятии эффективного множества истинности продукции; определены понятия полной и частичной противоречивости ИСП, обоснован механизм их выявления.

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

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

6. Разработана архитектура системы поиска противоречий в интервальных продукционных системах, реализованная в СПП ЭКРАН.

7. На основе анализа существующих методов взаимодействия ЭС и Б] предложено две схемы межсистемного взаимодействия ЭС с СУБД общегс назначения. Предложены принципы организации интерфейса ЭС с СУБЛ позволяющие повысить эффективность межсистемного взаимодействия. Разработано программное обеспечение СУБД ЭКРАН, СПП ЭКРАН 1 системы создания отчетов ЭКРАН ОТЧЕТ.

8. Результаты исследований были использованы при разработке ряда внедренных систем.

По теме диссертации опубликованы следующие работы:

1. Адамович И.М., Поспелова ЛЛ„ Пронина И.Г. ЭКРАН - инструмент дл создания интегрированных экспертных систем в области технической диагностики, проектирования, автоматизированного обучения //"Системы ]

средства информатики". Ежегодник РАН. Выпуск 4-й. - Москва, "Наука", 1993. - с.229-242.

2. Иванов В.Д., Поспелова Л .Я., Пронина И.Г. Интеллектуальная фактографическая база данных для управления крупной инвестиционной программой //Проблемы создания и использования фактографических баз данных. Тез. докл. Всесоюзн. совещ. специалистов в обл. научн.-технич. информации, 19-21 дек.1989 г. - Москва, 1989. -с.120-122.

3. Иванов В.Д., Пронина И.Г. Создание автоматизированной системы упреждающего контроля за ходом реализации крупной региональной инвестиционной программы //Проблемы применения вычислительной техники и автоматизированных систем в управлении комплексным социально-экономическим развитием регионов. Тез.докл.Всесоюз.научн.-технич.совещ., 4-8 сент.1989 г. -Донецк, 1989. - с.149-151.

4. Поспелов И.Г., Поспелова Л .Я., Пронина И.Г. Алгоритм поиска противоречий в продукционных ЭС и синтез программ тестирования проектируемых технических устройств//"Системы и средства информатики". Ежегодник РАН. Выпуск 5-й. - Москва, "Наука", 1993. - с.5-14.

5. Поспелов И.Г., Поспелова Л Л., Пронина И.Г. Система поиска противоречий в продукционных ЭС как альтернатива синтезу программ тестирования проектируемых технических устройств // Экспертные системы. Базы знаний и данных. Матер.семинара. - М.:ЦРДЗ, 1992. - с.57-63.

6. Поспелова Л .Я., Пронина И.Г. Инструмент разработки экспертных систем ЭКРАН //Экспертные системы на персональных компьютерах. Матер, семинара. - М.: МДНТП, 1990. - с.75-78.

7. Поспелова Л Л., Пронина И.Г., Черных С. А. Использование экспертных обучающих систем в учебных курсах по искусственному интеллекту, математической логике, автоматизации проектирования, дефектоскопии рельсов, диагностике средств вычислительной техники//Восток-Запад по новым информационным технологиям в образовании. Тез.докл.конф., 6-9 апр.1992 г. -Москва, 1992. -с.53-54.

8. Пронина И.Г., Иванов В.Д. Интегрированная экспертная система для управления ходом реализации строительной части долговременной программы развития производительных сил Дальнего Востока //Диалог "Человек-ЭВМ". Тез.докл.конф„ 4-9 сент.1989 г. - Свердловск, 1989. 4.1-с.57-59.