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

Pro OD

РОССИЙСКАЯ АКАДЕМИЯ НАУК ДАЛЬНЕВОСТОЧНОЕ ОТДЕЛЕНИЕ ИНСТИТУТ АВТОМАТИКИ И ПРОЦЕССОВ УПРАВЛЕНИЯ

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

САЮОДОВ Владимир Викторович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОК® 'ПРЕОБРАЗОВАНИЯ ПРИКЛАДНЫХ СЕМАНТИЧЕСКИХ СЕТЕЙ В БАЗЫ ПРАВИЛ

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

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

Владивосток - 19СЗ

Работа выполнена в Институте автоматики и процессов управления Дальневосточного отделения РАЕ

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

А. С. Кдеавв

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

А. Л. Синявский

- кандидат технических наук &Н. Уоатюк

БодуДво предприятие: Тихоокеанский океанологический

институт Дальневосточного отделения РАН {г. Владивосток)

Заамта ооотоитоя р_» ¿иЛ^ 1993 г. в .' часов

на заседании Специализированного совета К 003.30.01 в Иаституте автоматики и процессов отравления Дальневосточного отделения

РАН по адресу:

690041, г. Владивосток, ул. Радио, Б

С диссертацией южно ознакомиться в библиотеке Инотитута

автоматики и процессов управления ПВО РАЕ

£ '

Автореферат разослан " J " 1993 г.

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

Е ^ Коган

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

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

Наибольшие успехи в разработке методов компиляции языков представления знаний были достигнута для систем продукция, к "настоящему времени разработаны методы анализа систем продукций, повышаищке скорость вывода; метода компиляции правил з программы; - метода оптимизации . систем продугсдай; методы компиляции Пролбг-програкм и т.п. Однако основным недостатком систем продукций является высокая трудоемкость формирования баз знаний, что делает этот класс моделей представления неприемлемым, когда объем базы-знаний достаточно. Ее лик. Известные же пз литературы метода компиляции для языков представления зпашгй уровня выиэ систем продукций носят слишком частный характер я не применимы за пределами тех задач, для решения которых они разработаны. Поэтому актуален поиск обидах методов ко'тиляции языков представления знаний высокого уровня.

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

Для разработки методов компиляции необходимо определить класс модных язнков и объектный язык. Класс входных языков дол-кон обеспечивать низкую трудоемкость процгеса форифезметя ста знаний и иметь шрокую область применения. В качестве клавса входных ям-'коь рзСотч шершни " гф-леладоге. гемпчтглоск;:«" '-игл

(ПСС>, которые удовлетворяют этим требованиям.

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

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

Для^ достижения поставленной в диссертационной работе цели необходимо решить следующие задачи:

- разработать" язык спацвйосеции коыпвляцга прикладных семантических сетей в базы деклбративных.правил; '•■... .

- разработать метод реализации ксгашляздров щшьифюнх сецавтг гаческих сетей в базы декларативных правил} : ! ■/ ;

- разработать методы оптимизации объэкпшхСаз декларативных^ правил при комшиищиа; v •■'•; • ..! - . :

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

Научная новизна работы состоят в следующем: -

-впервые решена задача комшишщз! баз званий для ршрокого класса моделей представления знаний и задач на этих моделях;

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

Практическая ценность работа заключается в следующем: . * :

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

- разработан ряд прикладных и инструментальных систем, в том чис-№ медицинская диагностическая экспертная система Консультант-2, компиляторы баз знаний в бвзы правил Скиф, Коллапс и Коллапс-0 и друх'ие. •

Экспертная система . ОС) Консультант-2 внедрено на одном из "•кораблей Тихоокеанского флоте и проверена в условиях Длительного автономного плавания;: _ ' / Ч' -

К0мгш!Яторы Сккф, Коллапс и Коллалс-Ороализова^ • автором

диссертации и были использовннн ö тлструиваякыгои «яеввеве *№н-сульгадт-4 для создания экспертных стстом медицинской лиапюстики.

Результата диссертационной работы использовались при проведают лабораторных практикумов "Метода компиляции баз внвша* для' студентов кафедры шформатшга и про'грамадого обеспечения ЭШ математического 'факультета Дальневосточного государственного университета, а таюве при выполнения ими дипломных работ.

, Апробация работы. Основные положения диссертации докладывались н обсукдвлисъ на Республиканской школе-семинаре "Технология разработка экспертных систем" (Кишинев, 1987 г.). Всесоюзной школе-совещании "Проблемы проектирования экспертных систем" (Москва, 1988 г.). Всесоюзной конференции по , искусственному интеллекту (Переславль-Заяесскяй, . 1988 г.),. Республиканской школе-семинаре "Црдблемы применения экспертных систем в народном хозяйстве". (Кишшев, 1939 г.), III Всесоюзной конференции по искусственному интеллекту (Тверь, 1992 г.).

. Осноааые результата опубликованы в 12.работах.

. Структура и объем/работы. Диссертационная работа состоит из введения, * четырех глав и заключения, списка литературы, вклкчащего 116 наименований, и приложения. Работа содержат 136 страниц основного текста," 7 рисунков. .

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

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

Вторая глава диссертации посвящена разработке языка спецификации компиляции прикладных семантических сетей в базы правил и экспериментальному исследованию характеристик разработанного метода прэобразования прикладных семантических сетей в базы правил. . .. Дяя декоративных языков, для котсрах по определена операционная семантика,, з частности для. ПСС, нэ применимы определения понятий-"интерпретатор" и "компилятор", a farano связи мевду ними, данные А.П.' Ершовым с помовд>о.-принципа- смешанных ¡вычислений. Для того, чтобы использовать указанное результаты, полученные А.П.Ерзгавым, необходимо" предлокить •■способ определения операционной . семантика .• -для у...декларативных-. языков..-.'. Будем использовать'- в качестве; опврэгшртой'- сёмактшйг языка 'из. класса

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

В атом предположении пусть - описание метода.решения за- . дачи ЭС с базой знаний (БЗ) на языке ПСС о, причем само это описание метода выполнено на ЯОДП й. Будем называть ^ - интерпретатором БЗ, представленной на языке о. Если выполнить на процессоре языка Л с данными Я0 - БЗ на языке о и 0. - исходными данными. задачи, то будет получен результат У решения задачи>30. . "

Компилятором БЗ на языке о будем называть такой языковой процессор, который преобразует БЗ Ка на языке о в базу правил: (БП) Рн на языке Я такую, что, если БП Ри "выполнить на процессоре языка Я с данными 0, то будет получен результат У" - тот же, что и для интерпретатора БЗ. ^ .

Определим форму представления БЗ, объектной БП и языка описания метода решения задачи. Будем считать, что БЗ Ка имеет форму семантической сети, (гаперграс^а с размеченными вершинами и дугами), а семантическая сеть представлена набором конституент -атомных формул с константными аргументами: вершины семантической-сети „представлены одашэстными атомными формулами,'1 а дуги -многоместными, причем предикатный символ в. атомной формуле совпадает с меткой класса представляемой вершины (дуги),, а-аргумент (аргументы) - с индивидуальной меткой вершины (с набором индивидуальных меток вершин, образующих дугу). Через РКВ обозначим множество предикатных символов, использованных в этом наборе. Объектная БП Рд продставляется на языке Я описания декларативных продукций. Очегадно, что она будет сформулирована в терминах другого набора предикатных символов (обозначим его РОВ). Согласно принципу смешанных вычислений язык описания интерпретатора БЗ должен совпадать с объектным языком й, Поэтому в качестве языка описания операционной семантики языка о будем использовать ЯОДП Я. Каждое правило, описывающее процесс логического рассуждения, в общем случае имеет вид: ,

если □Р,(Х1 . .лоРьа1};л.рр( (Х1 . .ларп(хп,К1,.. .Хк) *:

Здесь Р).....Р^ЬКВ, р?,...,рг[,г7(,...,д^РМ, ,.. ,...„т^

- векторы переменках, причем, если. X - множество переменных, шсодедгс в '¡-т-кторц ДГ . в х " мнозсестг-о иерсл-чнных, входя-гиг: в |>>т:-,:>: .1......' ■ г * п - п или :'Я'лг о-.'рк.<ч-

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

В ЯОДП тлеется только две Форш организации циклов: цикл по дашшм и рекурсия! Это приводит к громоздкости описания достаточно сложных процессов рассукдэния. Поэтому для расширения выразительных возможностей язык описания ДП был расширен рядом макроопрэрэторов циклов, сводимых к конструкциям ЯОДП. К ним

п п

относятся макроконъшкция макродтаьшкцял , макросумма

иакроцикл по целочисленному индексу <2о (с ... ой я Макроцикл по целочисленным подмножествам <Зо а=П,п! ... о<3.

, Язык, полученный в результате рзсзгаренкя ЯОДП макрооператорами, назван языком МАКРОКШРО. Сперйцкв сведения макрооператора к эквивалентной форда на ЯОДП будем называть макрорасширением М8!фОО!1ЭрВТОрз. •

\ Определение синтаксиса и семантики ышсрооператоров является рекурсивным. После макрорасширения всех какрооператоров получаются прабило, не содержа®» макрооператоров, йсхсдане правиле на Цзыке. МАКРОРЕПРО будут считаться синтаксически праБлльшми, если полученная из них- после макрорасширения совокупность кравил ссот-ввтствхвт синтаксису языка ЯОДП я каядое правило этой совокупности.имеет вид (*). Поскольку при каздом макрсрвсашрзнии исключается один макрооператор, вся последовательность преобразований за-вёршазтся за коночное число шагов, т.е. рекурсивное'определение семантики макроопораторов корректно.

••; Опрэдэлш семантику языка МАКРОРЕПРО, основанную на принципе смешанных вычислений, с поморю принципа резолюции. На кавдом шаге вивода снЗкрзотся прзшло из БП, атомная формула из базы фактов и вычисляется резольвента для зтей нары (осли оно мокэт бить вычислена). Если резольвентой является привяло с гмпустам условием, то' ета резольвента добавляйся в ЕЛ- Если резольвента имеет пустое условие,'' то' вг.9 Формул« заключения

добавляются в базу фактов. . .

-Предположим, что база фактов разбита па дав иэпвросвкпгашося части - БЗ и БД. Если ВЗ Ка на ясыкз о участвует в выводе, а исходные датшня задачи д залерканы, то п процесса' илголшния интерпретатора- БЗ. на процессоре ягтеа ' фэрагруетея остаточная БП" Рд. Если имеет место "полноте" компиляции БЗ, и том

а

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

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

Таким образом, семантика языка' МАКРОРЕПРО, основанная на принципе смешанных вычислений, определяет процесс получения по программе, записанной на языке МАКРОРЕПРО, и .БЗ множества объектных правил. Программа на языке МАКРОРЕПРО является компилятором БЗ, параметры ыахросператоров называются параметрами интерпретации, язык МАКРОРШРО спецификации связи входных и выходных данных является языком спецификации компиляции (GK).

Каадое объектное правило имеет, в общем случае, вид;

если Dp1(xl,XJ,...,Xk) cpn(xn,X1t¿..,Xk) л . •- /

_Fs(X1,.,.,Xk.x1,...,sn) то , (**>

где jtf,...,Xfc - вектора значений переменных из X(f...,Xh, полу-, ченные при вычислении резольвент правила (*) с входными данными -

яг »

конституантами, представляющими БЗ, a tf.....tn- векторы термов,

полученные из векторов термов t (,... ,tr¡ в результате подстановки

вместо порайонных из Xf,...,Xh их значений Xf,...,Xfc.

Предположим, что с использованием языка МАКРОРЕПРО описана спецификация компилятора БЗ в БП. Тогда для того, чтобы получить остаточную БП по СК, разработчик должен для каздого правила спецификации вычислить резольвента со всеми возможными значениями исостояния БЗ, выполняя по мере необходимости макрорасширения мэкрооиераторов. После того, как процесс вычисления резольвент зоканчивеется, из множества полученных правил извлекается' объектная БП. Опнсапянй процесс в дальнейшем будем называть формированиям'остаточной БП по ПК и БЗ.

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

наблюдений бального в различимо моменты болезни. Задача состоит з постановке диагноза и его обосновании. Состояние БЗ было представлено семантической сетью, содержавшей 413 впршин, связанных между собой 2045 псгердугами, причем "дна гипардуга связнраэт между собой в среднем очоло 5 вершин. Спещф^ация компиляции, разработанная для ПСС, состояла из 17 правил на языке МАКРОРЕПРО. БП . эс . была . еформярована путем "ручного" преобразования состояния ЕЗ в БП та егггчтфикацгп кегзшляцки. Объектная БП содержала около ПОС правил. Разработка системы вн-доэтэна бригадой ив 3 разработчиков, трудоемкость составила окм.го Зв ч?л/кесяисг!. Ня поствРовш' дизггрзя для одной историк • бшгезяи :<? Консулы???-?. в затрачивала 25 очеуад

процессорного зремена на К -1054.

Третья глава диссертации пэгвяаена разрэботаэ да

реализации хгадтлнтсров ЛСО. в блзч дгчлгарйтгйшх яррчйл и . .экспэряйбтггяьчо«? гссдадоваииэ разравэтгяенх с помощь*' этих ' методов кемпалдворов. •

Получение дат большое БЗ остаточных БП »»ручную мокет оказаться очень трудоемким, хром? того, отладка и сопровохайп»'* остаточных ЕП при модификация БЗ продегавляетея посгаточн" кретг-.лявнм преет"СОМ, тробОЛМГКХ-тр:дазптр§т. Поэтому *Г';1бХ07Ш--•ко разработать мйтгц построении •••омтатятора по СК. Этот метол базируется яа тр&ксОормацгозюй ег;.:.~яг-псо нзмка СК.

Опрдалям трансфор'рциоапзг»)' сетитс/ я?нка «ДКг'ОГЕТПг'О глаюглчйо тому, как пг'О 'тпядло?.?!:? л.П.Ерепвдм для оящгтят-ааг* я.зякоп. Дя* языки Р. может бить определена тргн"фс-р"пШ1опная семягигке !7„ текак образе?, что если гапояйт. ячтортр'пэтор ВЗ яг.зха а па лроиоссоро к , 'п кччост рззудтт'н-' будот получено генорлрухлзоу распярвнпе' Г^ по языке й гакоп, что ес.тп ёго Г^ шгэяопсь' п-л процессоре '??'л;.э я а дьтпг.:?®, -котортзги ЯВЛГЧТГ-: Йз Ка, ТО результатов буд-зт БП Р„ т лг.мкп р.

е •¡V-: С рОЗУ-ГТ^аТОМ ГНЬТМЛОТГОЯ 1ЩТС<ТГ'р'чТП,Гог.-':- Ти на

пру-?'-;^ с дакядаа» которл-ш является 83 ?'с>

является ««».тмгаорои гл, прсдстаг-гангчг ня яж:г с, г П»1 45 "■'.'К': Р, причем сем гаяпплятер зяше-п йа ягш«* ¡т-'Лйрор-'.т-ц.л.йпя «¡«."»ятек»» ,7дов.потгорчот уологгю: П(^1,(ку,о)) одалстрк- о*?го уапопяя

опг>т.'»л."<,л'Т связь тр'^я сеу-ятйкичя л:л;:сгз МДК^'П'ЛЗ'О -•

*оц*рзго'.~.вяаЯ Я, осг'.^стасй пч ппипцйгш см^эгпп«: вччио.?^"?;^ (Г'п тртУсрмастчгоЛ '' '

ю

Кавдое правило ЯОДП моаяо трактовать двояко. Первая трактовка соответствует операционной семантике Я ЯОДП, когда доступны и БЗ и БД. В этом случае правилами вида (*) прадставлен интерпретатор БЗ. Вторая трактовка соответствует семантике Мв, основанной на принципе смешанных вычислений, когда БЗ доступна, а БД задержана. При трансформационной семантике 1ГЙ правилу СК вида (*) соответствует правило компилятора вида:

если ир/х}) л...л ПРаГХа; л

то'"если л...л арп(хп,ХХк) л

Рг(Х},...,Х^,х1.....хп) то >1)

Кавычки ограничивают строку символов, в которую должны быть

подставлены значения .переменных из векторов При

выполнении правило (*1) вырабатывает в качестве следствия строку символов, совпадающую с правилом на ЯОДП вида (**).

Особо отметим два частных случря правил вида {*). Первый случай - в правило (*) п=0, т.е. оно иыэет вид если аР1(Х1)*...*аРь(Хъ) а то Я,^,)*'.'^^). <*?>

В етом случав три семантики правила (л*) совпадают: правило вида1 (*2) можно трактовать в соответствии о семантикой ЯОДП. как. правило компилятора периода анализа, так как при его выполнении элементы объектной БП не вырабатываются, И второй случай, когда в ' правиле (*) Ь=0, т.о. оно клюет вид

если ар1(х1)л...лсрп(хп), л ¡'2(х1,., .,хп) то Ч1(^i)л^•^AЧ1ll(tшJ^ (*3) В этом случае в' трано$ормацио:шой семантике \1п правилу СК вида (*3) не соответствует правило вида (*1), т.к. правило <*3) само является элементом объектной БП.

Трансформационная семантика макрооператоров языка МАКРОРЕПРО совпадает с их операционной семантикой. - , .»

Предположим, что с использованием языка МАКРОРЕПРО построена спецификация компилятор» БЗ в БП. Рассмотрим, как с ее помощью построить разу правил компилятора БЗ в БП.

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

_ • Если для каждого макро-

•о»«ра 1"оря для пгех привил СК знпчош'я N порачетроп интернротацип Со пыле ли^о рч»-т1 с ^тиую-щм наибольшим значениям я из

СОСТОЯНИЯ БЗ, то ЯГ^.ГЙо.Ш} * ЖЩИ^^.К^.О).

Затем, используя выбранные значения параметров интерпретации, необходимо получить макрорасширения всех макрооператоров. Преобразованная спецификация будет состоять только из правил вида (*). Затем все правила спецификации приводятся к виду (*1). В результате всех указанных преобразований текст спецификации превращается в БП компилятора (правила вида (*1) и (*2)) и начальное состояние объектной Ш (правила вида (*3)).

Работа компилятора в форме БП организуется следуицим обра зом. Компилятор получает на вход БЗ, которая представлена набором атомных формул с константными аргументами. Правила периода акали за вида (*2) формируют конституэнта, которые используются компи лятором в качестве промежуточных результатов, п правила компиля ции вида (*1) (правила периода генерации) формируют строки символов - правила вида (**). Полученные правила добавляют к правилам начального состояния БП вида (*3). После завершения работы компилятора объектная БП представляет собой текст объектной БП на ЯОДП.

. Для проведения экспериментального исследования характеристик предложенного в.диссертации метода реализации.компиляторов ПСС в базы декларативных правил были разработаны два компилятора .баз медащпнских знаний в БП Скиф и Коллапс. Компилятор Скиф был реализован па ЕС ЭВМ. Для его реализации использовались язык РЕПРО, являющийся ЯОДП, и. язык Паскаль. Реализация .компилятора Скиф .на,ЕС ЭВМ ограничивала-сферу использования генерируемых ЗС. Поэтому была Енполнзна реализация подобного компилятора, получившего название Коллапс, на персональном компьютере (ПК). Для реализации компилятора Коллапс использовались те т самые языки. Трудоемкость разработки компилятора Скиф составила около Б. чел/мосяцев, а компилятора Коллапс -'4 чел/месяца. осе разработки осуществлялись автором диссертации.

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

Компилятор Скиф сгонэрярор.ал по БЗ медацтскую д«шчгоста-чоскуя ЭС, время постановки диагноза для которой оостяр."яло и сроднен около 43 секунд, процессорного промони нч ?п<"-в. Гят'Г)<> положат** вполне устраивало врачей, хотя, конечно, полутпппя актоматичоски X несколько уступала ра-.'рн^отат?'^ "Г'руш'у." ";С Кэн^ультплт-".

1й

Основным недостатком -¿ет-ода гибкой компиляции является большое число правил в объектной БП. Так,число правил в 30 при генерации ее компилятором Коллапс оказалось примерно' в четыре раза большим, чем при разработке ее "ручным" способом.

Разработанные компиляторы БЗ в БП помимо исследовательского имели еще и практическое значение, они были использована а рамках инструментального комплекса Консультант-4 для создания медицинских диагностических экспертных систем»

Четвертая глава диссертации цосвящеиа разработке, методов оп-■гтаяя&нии компиляции прикладных семантических сетей в базы декла-ратигстых правил на языке РЕГ1Р0 и экспериментальному исследованию разработанного с помощью этого метода оптимизированного компилятора. ■ . • . .

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

Известны два основных критерия оптимазащш: по объему требуемой памяти и по затратам времени. Мерой объема требуемой памяти будем считать число правил в объектной БП. Число объектных правил в ЗС при фиксированной . сшщфасацил компиляции определяется объемом исходной БЗ: чз.%: больше аввкэнгов б есходной БП, тем больше будет правил ь объектной БЗ. . Поэтому одним из возможных путей онтгалйзации является сшшжио зависимости числа пропил в объектной БП от чйсла элементов в БЗ. 'Под затрата.«! iipirf.it;ни в данной работа понимается вре.чл вывода. Одним из. путей повышения скорости вывода является ваделэякэ частик, случаен, для которых Мажет быть достигнута более высокая скорость вывода.

С диссертации предлокени дез «шшшрукцих преобразования: "ослабление зависимости числа объоятных правил от числа компонент ИЗ" и "сяециализпция •.-празпя _ •«яшлятора"» направленные на у»«пьа&нко количества •овьёк.тшх правил б гоазр»фуё№х БП ЭС и ?<ромони-работы ЭС.

. опткмалирувдво 'дреобразоваико .^ослаблешто зависимости числа сбтет:гпых. -ирзиул 'р? ." числа .• г.ижчиы?. БЗ" , СОЗЬЗ) состоит в кя;лого'крг1в;:ла.'ко^ду;.ирра к. такому" рилу', что его

правило будет генерировать по БЗ объектные правила, число которых не будет зависеть от числа некоторых компонент БЗ, от которого око зависело при использовании первоначального правила.

Опишем оптимизирующее преобразование ОЗБЗ формально. Пусть правило компилятора имеет вид:

Если л.,.л о* Л...Л

Рп_,ап_,иш; Л ~Рп(Хпи{А)) л...Л *Рг(Хи(А)) л

То "Если ор^иУ,; Л ... Л ) Л

ар'^хШ^(А)) Л . . . л"ор^хтиУти(А)) Л Р-Гх.и.. .ШгЧ1У,и.. .иуи(А))

с * Л Т. Л

то А ... Л . • ш

где □ - пусто или знак отрицания О; Р,,...,Рг - предикатные символы, соответствующие дугам ПСС, описывающим БЗ; X-множества переменных, соответствующие вершинам БЗ; У(,...,Уп -мнокества переменных, включающие переменные из множеств ХГ...,Х ГУ4сХ(и ... ихг); Х^(А) . - множество переменных, включающее переменные из множеотва Х( и переменную А, соответствующую

некоторым вершинам БЗ ; рг,...,рт,дг.....- предикатные

символы, соответствующие дугам ПСС, описываицим БЛ; .г,,...,хп -множества переменных, соответствующие вершинам БД; г/Помножает) переменных, включающее переменные из множеств х} й У^; Р< - логические формулы над переменными: I^ - термы, включающие переменные из множеств XХг и г,,...,дп. Тогда, если Хп II ... и ^ с и ... I) (, то результатом применения оптимизирующего преобразования ОЗБЗ к правилу (I) будут' правила двух типов - правило периода компиляции (2) и правила периода генерации (3) и (4), приведенные ниже.

Правило периода.компиляции (2) имеет вид:

Если (П&'р.(ХЛ)(А))) * ( & ЛР.(ХЛНЛ)}) То , .их ЛНА)).

Правило периода генерации: Если аР,(Х,) л ... л л ц<-яг,я:1и...ШГп_,;Г) *

т'{и...ш:п_(иш; л л)хги(л))

То "ЕСЛ1 ф,гг,йуг) л ... л ^иг^,) '*

гу^.и,..иг иу.и...иу

с I . 1Я I ТД

л ... А прп(хпиУтША))

то А ... А Яа(гаг , (3)

Если aP/V Л ... л nPt_,fXt_(; л л л

. f & W.u...их ,иШ1)}) * FJX.U^.MX иШИ)))

* ' ,1.1 г

То "Если opffx,UГ, J Л ... Л ср № uyj_f; л F„(x,ii...Ux UY.[}..MYJJ(a)) л

с I П г П

ff

□p.fx.ur.uaj л ... л qp fx ur.Ua; л ( a=Ä(i])

J J J ^ ** Я j* j

то W л ... *qd(td)" , = (4)

гдэ a - переменная, область значений которой совпадает с областью' значений переменной А; А(г1 - индексированная переменная, принимающая значения из области значений перомонной А, а ц -функция, значением которой является мощность мнокества, определяемого аргументами..

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

Если DPfa,; Л ... л ap(_rfx{_r> л ptatuw) л

То "Если qp(fx,UYf) * ... * (xJ_1UYJ^f) * PjdjUYAHA}) л . .UxmUrfU.. MYmU(A))~ то qf(tf) л ... л qjta)" . (Ь)

Если ил ограничений целостности предметной-области известно, что SfjCjf и где - множество значений, принимаемых переменной

А в етомной формуле P((X{UCA}Jf V - множество.значений переменной А из атомлой формулы PfXUiA)), то в результате специализации по Перемчкной А правило (Б) будет преобразовано к. приведению.? шшэ правилам периоде-гаг.-рчции (G-3). ,

Если аР,(Х,) Л ... *\i(F,X:%) Л \i(PitXt:fil) *

H-N1 '

V H101 л ( & р(ШЛШ)Л л лр(ХЖАШ)) л. fcrf ' .-. 1 . '■

F,/iflJ.,.U.yj<-/iflJ^.;. , г

т. uptг.г(1)У() '- ... ^ upj^iXj^^j) л.

F-(:rfU...to Uy,U...U7 Ufa;; л p rar.ur.UiaJJ л

it I 1ft . » nl J J J .

N

( & а*А(ъ)) то g/v A A W" (6)

Если uP/X,; a ... л aPt_f«t_(; л цГРД:»; л а

Г - ¡мг;»» л ifj^f л pJx^fA)) л ..ихгиш;

.То "Если ap^xJST,) Л ... Л ср (я иг ; Л . Р2гя>и...ихтиг}и...иу)яиш> Л

р ,'г иу иш; TO q/t,; А ... Л qd(tdr (7)

ЕСЛИ ар,«-*,; А ... л aP4_fat_t) л ЦГР.Х.-Я; л А

h

K-nwi л л ( &. pt(xtu(A[),]}) л p2afu...uxruuij.w; То "Если рр,J а ... a а

; , p2fxfu..,.UTmur,u.'..uyjjfa;; a p^^ur^ufa;; а

1 я?' •' • .

-(- v -arAM). то q1 (t,) a ... л qd(td)" (8)

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

Для проведения экспериментального исследования характеристик предложенных методов оптимизации был разработан компилятор Коллапс-О. Оптимизированный компилятор Коллапс-0 получен после применения провоженных бт'шизирувдих преобразовашй! к правилам компилятора Коллапс. Проведение оптимизации базы прпг-ил компилятора и ее реализация заняли около 2 чел/месяцев. Измерешга характеристик компилятора Коллапс-0 проводилось для того жз самого состояния БЗ, что и для компилятора Коллапс.

Оп тонизированный компилятор на построение готовой к эксплуатации ЭС затратил, в 1.4 раза больше времени, чем нэоптимизированный для того , же состояния БЗ. Объем объектной Б11 уменьшился в 2.7 раза, а постановка диагноза для одной, истории болезни проводится ЗС, сгенерированной компилятором Коллапс-0, в 1.8 раза быстрое, чем ЗС, сгенерированной компилятором Коллапс.

. ЗАКЛЮЧЕН!®

Таким образом, п диссертации получены следу пега ochoeiqis ро-зуль'т аты

.1. РазработаТг^зык_МАКР0РЕПГ0 .спецификации компиляции прикладных семанпйеских сетей в бэ?я- декларативных прзвил. Прэдлотян способ оггроделения оперпцксчгноЯ соратники языков, о"нсъыгах пв

пршследных соматических сетях. С помощью принципа резолюции определены операционная семантика языка ЫАКРОРШРО, основанная На принципе смешанных вычислений, н способ получения остаточной базы. декларативных правил по спецификации компиляции, записанной на языке МАКРОРЕПРО, и базе знаний в вида прикладной семантической сети. - . .••';

2. Разработан матодреализации компюшторовприкладных ;се- ' мантическвх сетей в базы декларативных правил. Определена трансформационная семантика языка ЫАКРОРЕПРО, поксзана еесвязь с операционной семантикой и семантикой, основанной на принципе cmo-ианных'вычислений, языка МАКРОРЕПРО. Разработав способ получения компилятора по спецификации кокппляции на языка МАКРОРШРО. Дока-зена теорема о корректности компиляторов,' полученных этиа способом. - ' ■ : ; , '.." ; -V,

3. Разработаны, метода оптимизации объектных.баз декларативных правил при компиляции. Предлокзны оптимизирующие преобразования: "ОСЛ83ЛЭЮТЭ зависимости числа обьектных правнл от числа кон-т гопент базы знаний" и "отввдалгоация правал конпилятора'', направленные на уменьшение количества празил в объектной базе правил и врекеш вывода по объектной базе правая. Показано, что предложенные оптЕмязирупдае преобразозаниякорректны, а ;а прймзнение. к правилам компилятора приводит к 'получению не иенее эфДектишшх объектная баз правил. ;/ •• -, .•-'

» 4. Проведено экспериментальное исследование; характеристик разработанных методов преобразования прикладных секантичэскихое-' тай в базы декларативных правнл. Шказещо. что првдиожвнныо методы обладают невысокой трудоешсостью разработки компиляторов, применимы для компиляции больших баз: Ьнарй, 'а объбкгнкэ базц правил обладают приемлемой скорость» вывода.: В ходе исследования разработан ряд прикладных и инструкаитгльных систем« в том /шолэмеда-цинская даагностичзскся экспертная CEcieaa Копсультант-2, компиляторы баз знаний в базы правилСкиф, Коллапс' и Коллапс-0 и другие. . -V .-'у, л ' .' ■"■'.••-•"■■■.''-' ;

Основные результаты диссертации опубликованы, в работах: ' . I. 1£игоренко T.tf.i :Заяц;Г:А.,/^^ Клещев i.,C. Лйфйц: ¿.Й.„ Самсонов В.В.; Coporam B.C.; Черняховская Н.Ю./.Перспективы внедрения на кораблях мёдшинской екешртяой системы в!Сонсультант-2" // брдЛНОНЙвДЯЩШСКИв1939, К.2i Ci■ 49-50.:: . 2. Ег-еткфревп'Т.А., Юкген А.С., Клименко'И.А., Лкфикц А.Я..1

- Савушкиаа М.Ю. .Самсонов B.B* и др. Инструментальный, комплекс Консультант-4 для создания экспертаык систем иедицинской диагностики: Препринт. Владивосток: ЙАПУ ДВО АН СССР, 1991. 27 с.

3. Иванов A.M., Клещей A.C., Лифвиц А.Я., Самсонов В.В., /Сапвлкша Т.Г., Че^щяховская M.D. Средства я методы отладки баз знаний// ! Проблемы применения . экспертных систем. в народном хозяйстве? Тез. докл. Республ. иколы-свмшара. Кишинев, 1989. 0.82-86.

• /4. Иванов A.M., Самсонов В.В., Черняховская М.Ю. Результаты /опытной эксплуатации экспертной системы Консультент-2// Методы а средства создания и исследования экспертных систбм. Владивосток: JB0 АН СССР, 1991. С. 118-129.

V б. Клащев A.C.Лифниц А.Я., Самсонов В.В., Сорокин B.C., -Чврняховсюая М.Ю. Предварительные результаты анализа экспертной системы Консультент-2 на архивном материале// Всесоиз. кокф. по искусственному интеллекту: Тез. докл. Т.2. М.: АН СССР, 1988. .;С.347-352; •

; 6. Клещев. A.C., Оамсовов В.В.', Черняховская M.D. Медицинская экспертная система Консультент-2.. Представление званий: Препринт. Владивосток: ИАПУ ДВНЦ АН СССР, 1987. 44 с. •.

7. Клзщев A.C., Самсонов В.В. МАКРОРЯ1РО - язык спецификация Номгоияцго Саз знаний в-базы правил:. Препринт. Владивосток: ДВО РАН, I992V 25 с.

8. Самсонов В.В. Эксперимент по реализации экспертной системы Консультант-2 методом трансляции базы знаний из глубинного представления в поверхностное// Технология разработки экспартнза систем: Тев. докл. республ. школы-семинара. Кишинев, 1987, С. 116-120, ; . • •

9. Gsmcohob В.В., Сорокин B.C., Черняховская М.Ю. Экспериментальная медицинская экспертная система Консулыгвнт-2// Проблемы проектирования экспертных систем: Тез. докл. Всесовз. школы-ссвещаняя. 4,2. Москва, 1988. С.238-239. 7 ■

10. Самсонов В.В. Разработка и исследование гибкого компилятора баз знаний Скиф? Препринт. Владивосток: ДВО РАН, 1992. 38 в:

; II. Самсонов В.В. Разработка.и исследование. оптимизировались Го. компилятора баз знаний в базы правил: Препринт. Владивосток: ДВО РАЙ, 1992.,32 С.

12. Самсонов В.В. Разработка и исследование гибкого компилятора бэп знаний я бвзн прявял// III Всесопз. когар. по искусственному пителлпк-у: Сб. нэуч. тр. т.Л. Тнорь, 1992. С.135-140. '