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

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

СОЛОВЬЕВ Сергей Юрьевич

МАТЕМАТИЧЕСКИЕ МЕТОДЫ И ПРИНЦИПЫ ПОСТРОЕНИЯ АВТОМАТИЗИРОВАННЫХ СИСТЕМ ИНЖЕНЕРИИ ЗНАНИЙ

05.13.16 - применение вычислительной техники, математического моделирований и математических методов в.научных исследованиях

АВТОРЕФЕРАТ

диссертации на соискание' ученой степени доктора физико-математических наук

Тверь - 1996

Работа выполнена на кафедре информатики Тверского государственного университета

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

наук, профессор А.Н.Сотников

Официальные оппоненты:

- доктор физико-математических наук, профессор Н.К.Жиганов

- доктор физико-математических наук, профессор И. Г. Ма.пьковский

- доктор технических наук, доцент В. Ф. Хорошевский

Ведущая организация - Институт системного анализа РАН

Защита состоится " <2 ? " ОсгОЮЛ_ 1996 г. в ^ часов

на заседании специализированного совета Д.063.97.01 при ТвГУ по адресу: 170013, Тверь, ул.Желябова. 33

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

Автореферат разослан " " исаЛ__ 1996г.

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

кандидат физ. -мат. наук, доцент в-А-Хижняк

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

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

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

Концепция экспертных систем была сформулирована в 70-е годы (Дж. Фейгенбаум, М.Минский, Д.А.Поспелов). Ядро экспертной системы - ее базу знаний - составляют формализованные знания, а остальные блоки системы реализуют функции преобразования знаний и определяются не столько содержимым знаний, сколько свойствами их формальных структур.

До середины 80-х годов во всем мире шел интенсивный процесс создания инструментальных средств для разработки экспертных систем. Параллельно, но с гораздо более скромными результатами шел процесс разработки практически полезных экспертных систем: МУСIII, ОЕНЭКАЬ, ... Постепенно выяснилось, что главная проблема экспертных систем - это проблема формирования конкретных баз

- г -

знаний.

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

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

В инженерии знаний естественным образом сложилась практика оформления продуктивных методов опроса в виде программных систем. Так. методика репертуарных решеток породила целое * семейство автоматизированных систем, предназначенных для опроса эксперта (AQUINAS, KRITON, SIMER и т.д.). В то же время процесс разработки такого рода программных продуктов, названных в диссертации автоматизированными системами инженерии знаний (АСИЗ), развивается во многом стихийно, и зачастую господствует упрощенный подход, вообще исключающий когнитолога из технологии формирования баз знаний.

В связи с этим назрела настоятельная необходимость в разработке общей концепции АСИЗ, которая позволяла бы:

(1) стандартизовать подходы к реализации АСИЗ, что совершенно необходимо для их практического применения,

(2) развивать проблематику АСИЗ как самостоятельное научное направление.

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

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

Основными задачами исследования, определенными поставленной целью, являются:

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

- разработка новых семейств и конкретных методов реализации АСИЗ, основанных на различных подходах к организации опросов эксперта;

- разработка и обоснование математических методов построения АСИЗ;

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

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

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

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

диссертации и представляемые на защиту:

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

- разработаны и исследованы новые методы

— построения АСИЗ и формирования баз знаний;

— отладки баз знаний.

- разработаны и обоснованы математические методы, предназначенные для использования в АСИЗ,

— формализм простых систем альтернатив для решения переборных задач и реализации баз знаний;

— методы восстановления формальных грамматик для решения возникающих в АСИЗ подзадач индуктивного вывода.

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

Внедрение результатов работы. Результаты диссертационной работы использованы при выполнении ряда НИР и ОКР по заказам ВНИИПВТИ ГКВТИ СССР и ИПУ Минприбора и АН СССР; при выполнении задания 1.2.2.6.3 Комплексной Программы научно-технического прогресса стран членов СЭВ (1986-1990 гг.), а также в учебном процессе на факультете вычислительной математики и кибернетики Московского государственного университета им.М.В.Ломоносова.

Апробация результатов работы. Результаты диссертационной

работы докладывались и обсуждались на Международных-конференциях ШУСБ-Эб (Будапешт, 1986), "Экспертные системы и распознавание образов" (Новосибирск, 1987), "Проблемы и применения Искусственного интеллекта" (Варна, 1987), на Всесоюзной конференции "Автоматизация производства систем программирования" (Таллин, 1986), на 1-й, 2-й и 3-й Всесоюзных конференциях по искусственному интеллекту (Переславль-Залесский, 1988; Минск, 1990; Тверь, 1992), на республиканских конференциях "Интерактивные системы и их практическое применение" (Кишинев, 1984), "Логико-комбинаторные методы в искусственном интеллекте и распознавании образов" (Кишинев, 1985). "Автоматизация и роботизация призвод-ства с применением микропроцессорных средств" (Кишинев, 1986), "Молодежь, Наука, Производство" (Кишинев, 1986), на семинарах в ВЦ РАН, МГУ им.М.В.Ломоносова, ИТК РАН. ИПЙ РАН, ИСА РАН, ИПС РАН, ИМ с ВЦ АН МССР.

Структура работы и ее содержание. Диссертационная работа состоит из введения, шести глав основного содержания, заключения и списка литературы. Объем основного содержания - 242 стр., библиография - 65 наименований.

Публикации. По теме диссертации опубликовано свыше 35 работ. Основное содержание диссертации отражено в 25 работах автора, которые приведены в конце автореферата.

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

Основное внимание в работе сосредоточено на разработке математических основ и методов конструирования автоматизи- ' рованных систем инженерии знаний.

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

В первой главе диссертации

"АВТОМАТИЗИРОВАННЫЕ СИСТЕМЫ ИНЖЕНЕРИИ ЗНАНИЙ" рассматриваются основные аспекты задачи формирования баз знаний, здесь же предлагаются и обосновываются принципы построения АСИЗ.

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

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

- знания эксперта не имеют модульной структуры;

- наиболее существенные знания эксперта носят невербализованный характер;

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

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

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

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

Основной прием опроса методом сопоставления состоит в том, что когнитолог (или АСИЗ) предъявляет эксперту ряд решений и предлагает рассмотреть некоторый конкретный вопрос об их сходстве и/или различии. Полученные при этом объяснения позволяют Формировать атрибуты для описания объектов проблемной области, а также правила принятия решений.

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

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

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

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

<=

Эксперт <0

Блок настройки позволяет подготовить АСИЗ к работе в конкретной проблемной области. Настройка осуществляется когнитологом на основании предварительного исследования проблемной ■ области. Непосредственным результатом настройки является база сведений о проблемной области.

Интерфейс извлечения знаний ориентирован на интерактивное взаимодействие с экспертом. Этот программный блок:

- реализует сценарий опроса эксперта - сценарий извлечения знаний;

- использует в своей работе базу сведений о проблемной области;

- протоколирует все действия эксперта, формируя базу протоколов опроса.

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

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

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

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

- выделение продуктивной части протокола;

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

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

В отдельных случаях для оценки применимости и выделения

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

Во второй главе диссертации

"МЕТОД ПРОСТЫХ СИСТЕМ АЛЬТЕРНАТИВ" излагается и обосновывается метод организации и обработки данных, предназначенный для решения переборных задач, возникающих в АСИЗ.

Простой системой альтернатив (ПА-системой) называется тройка конечных множеств (S,С,А), где S - множество основных фактов, С - множество вспомогательных фактов (S П с = и), А -

совокупность подмножеств из Н = S и С. Элементы <ht.....hn> из А

называются альтернативами.

По определению функция f : Н —» {0,1} удовлетворяет

ПА-системе R, если для любой альтернативы <hj..... hm> из А

имеет место равенство f(bj) + f(hm) = 1. Множество функций, удовлетворяющих ПА-системе R, обозначается F(R).

ПА-система R порождает множества d(R) и K(R), элементами которых являются подмножества фактов: d(R) = (f(H) I f e F(R)},

K(R) = {f(S) | f e F(R)}, где f(Y) = (x e Y I f(x) = 1}. Множество К(R) называется классом распознавания ПА-системы. Элементы класса распознавания описывают (путем перечисления) допустимые комбинации основных фактов.

Формализм простых систем альтернатив•включает в себя:

(1) исследование выразительных возможностей ПА-систем;

(2) алгоритм логического вывода в ПА-системах;

(3) способ конструирования ПА-систем.

(1) Универсальный характер ПА-систем устанавливает доказанная

Теорема. Для любого множества К0 с 2s существует ПА-система R = (S, С, А) такая, что K(R) = К0.

(2) Алгоритм логического вывода в ПА-системах предназначен для вычисления по заданным множествам L" и L+ из S

множества установленных (основных) фактов S+ = Н+ Л S и

множества опровергнутых (основных) фактов S" = Н" П S,

где Н* = Л q , Н* = Л (Н \ q), q e Q.L q е QL

QL = {q e Q(R) | L+ С q, L" Л q = 0}.

Полное решение задачи логического вывода сводится к решению системы булевых целочисленных уравнений, что приводит к неэффективным алгоритмам экспоненциальной сложности. В связи с этим в ПА-системах для решения задачи логического вывода применяется алгоритм, основанный на применении фиксированного набора правил вывода/преобразования альтернатив. Правила позволяют относить некоторые факты к множествам и+ и 1Г; предварительно необходимо положить U+ = L+, U" = L~. Основу логического вывода в ПА-системах составляют четыре правила. Правило 1. <..., hn.t, hk, hk4l. ...> е А

hk е U-_

<•••• bk_i, hk+1, ...> е А

Правило 2. <hj.....tik.j, hk, hk + 1,'____ hm> e a

e Г_

.....hkM, .... hm) с и-

j

Правило 3. <Ь> е а

е г

Правило 4. < > е А

СТОП (Задача логического вывода не разрешима) Алгоритм логического вывода заканчивает свою работу либо в результате применения правила 4, либо тогда, когда первые три правила не приносят новой информации о множествах А, и" и II". В последнем случае решением задачи является множества V* = Б Г) 1Г и V" = Б П и". В общем случае V" с Б*. V" с Б", но V* * Б\ и V" * Б". Последнее обстоятельство вполне приемлемо для практического использования систем альтернатив, если при формировании ПА-системы и при ее использовании применяется один и тот же алгоритм логического вывода.

(3) Для конструирования ПА-систем И = (Б,С,А) применяются независимые модули знаний - ПА-системы = (Б,.^^)

(1=1...п). для которых С! П = с (1 * о). При этом

Б = Б, и ... и Бп. С = С, и ... и Сп, А = А, и ... и Ап. Метод конструирования ПА-систем из модулей знаний основывается на следующем утверждении:

Для любого модуля I?! имеет место вложение

Ш П Б! I БЕ К(Ш С К(И1). В диссертации предложены и обоснованы эффективные конструкции альтернатив для представления модулей знаний типа: альтернатива, несовместимость, запрет, модуль импликации и продукции; для каждого модуля знаний исследованы варианты его

функционирования в ходе логического вывода.

Модуль альтернативы Еа = (Б,0,Аа), где Аа = {Б}. К(Иа) = {{э} | з е Б }.

1).Если э е Ь+ для некоторого э из-Б. то Б \ {э} с и-.

2).Если Б \ (б) с ь- для некоторого б из Б, то э е и+.

Модуль несовместимости Кн = (Б,(с},Ан), где Ан = {Б и (с)}. К№н) = {0} и {{э} | б е Б }.

Если э е ь+ для некоторого б из Б, то Б \ {б} с и-.

Модуль несовместимости фактов .., обозначается [11!_____Ьт].

Модуль запрета И3 для Б = ..... зт} есть ПА-система

(2, {С!.....ст}.А3), где А3 = {[Й!, с, ]----[Бт. ст]. <С1...., ст>}.

К№3) = 2Э \ {Б}. Если 3 \ (э) с ь+ для некоторого б, то э е Г. Модуль запрета для фактов Б1...Бт обозначается ЗАПРЕТ^,.. , ет) _ Модуль импликации И,, для Б = {з0, Б1..... зт} есть ПА-система (Б, {С!.....ст}, Аи), где

Аи = {[З^С!].....[зт,ст], <з0.с1.....с1П>}.

К(Ии) = 2Э \ {Б!.....Би}.

1).ЕСЛИ {Б!.....Эц} С 1\ ТО Б0 Ё и+.

2) . Если Б0 £ Ь" И {Б!, . . . , Б!. ! + 1..... Эй) с I/, то Б! Е Ч".

Продукция 1?п для Б = {э0, Э!..... зт} есть ПА-система

(Б, {С!..... ст, 6.1,....Ап). где

Ап » {[31,01,(3!].....[Зт,ст,с1т], <Э0,С1,(11.....Ст,(1т>}.

К(1?п) •= 2Э \ {в!.....Бт}. Если (з,.....зт> с ь+, то в,, е и*.

В третьей главе диссертации

"ИНСТРУМЕНТАЛЬНАЯ ЭКСПЕРТНАЯ СИСТЕМА ФИАКР" излагаются принципы организации программной системы, предназначенной для формирования и отладки баз знаний. Система ФИАКР

поддерживает внутренне представление баз знаний в виде ПА-систем и реализует соответствующий алгоритм' логического вывода.

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

В системе ФИАКР множество основных фактов состоит из дескрипторов свойств - троек (<ПОДСИСТЕМА>, <АТРИБУТ>, <ЗНАЧЕНИЕ>) и так называемых флагов, предназначенных для организации работы самой экспертной системы. Всего в системе существуют пять разновидностей флагов, позволяющих задавать необязательные атрибуты, подсистемы и модули знаний, а также позволяющих указывать цели консультации и управлять процедурой опроса пользователя.

Штатные возможности системы ФИАКР предоставляют возможность формировать в базе модули знаний пяти типов: альтернатива, несовместимость, запрет, продукция и модуль импликации. Альтернатива задает полный ряд попарно несовместимых фактов, из которых для каждой проблемной ситуации имеет место ровно один. Модули несовместимости задают неполные ряды взаимоисключающих свойств. Модули запрета позволяют, в частности, задавать * комбинации дескрипторов свойств, которые в таком сочетании никогда в природе не встречаются. Последние два из перечисленных модулей реализуют различные типы зависимостей вида "ЕСЛИ ..., ТО

...". При этом модуль импликации опровергает одну из посылок при опровергнутом следствии и наличии всех остальных посылок.

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

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

Для оперативной корректировки знаний в состав системы ФИАКР включены: редактор атрибутов и подсистем, редактор модулей знаний, редактор анкет, редактор целей. Непосредственно формированием базы знаний занимается конструктор модулей. Именно этот программный блок формирует множество вспомогательных фактов и размещает альтернативы в файлах базы знаний.

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

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

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

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

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

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

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

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

В системе ФИАКР методы отладки подразделяются следующим образом:

Отладка

Тестирование

Исследование -- статическое

— динамическое

Тестирование базы знаний предполагает проверку ее свойств на заданном множестве примеров. В системе ФИАКР понятие примера естественным образом расширено с целью контроля промежуточных выводов.

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

ФИАКР. Результаты проверки запоминаются в базе тестов. По окончании прогонки эксперт имеет возможность детально проанализировать имеющиеся отклонения в поведении базы знаний. Применение базы тестов позволяет уменьшить трудоемкость отладки.

Для оценки полноты набора тестов в системе ФИАКР используются два критерия. Первый из них состоит в том, что каждый дескриптор свойства должен входить по-крайней мере в один тест. Второй критерий состоит в том, что каждый модуль знания должен использоваться при выводе хотя бы одного теста.

Статические методы исследования предназначены для проверки количественных и качественных свойств баз знаний. Эти методы исходят из особенностей представления основных фактов и модулей знаний. В подсистема отладки реализует 13 проверок проблемно-независимых свойств баз знаний.

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

Множество фактов Г называется конфликтным описанием по отношению к заданной базе знаний (суть - ПА-системе). если логический вывод для множеств Ь+ = Г и Ь" = 0 приводит к применению правила 4. Конфликтное описание Е называется минимальным, если любое его подмножество фактов не является конфликтным описанием.

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

В четвертой главе диссертации

"МЕТОДЫ ВОССТАНОВЛЕНИЯ ФОРМАЛЬНЫХ ГРАММАТИК"

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

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

Источник - это устройство, которое располагает языком Ьи (языком источника). На каждом такте своей работы источник передает одно новое слово из Ьи на вход анализатора. Фактически источник формирует последовательность множеств \ 1 > 1}, где

Й! состоит из предложений, переданных на первом, втором.....

1-м тактах. Множества называются образцами.

Анализатор - это устройство, которое на 1-м такте своей работы применяет к образцу Й! метод восстановления М и строит конечное множество грамматик М(£21).

Задача грамматического вывода называется разрешимой для языка источника Ьи, последовательности образцов {{^ | 1 > 1} и метода восстановления М, если существует число п, ' при котором множество решающих грамматик М(й„) содержит грамматику Си такую/ что Ь(СИ) = Ьи.

В диссертации задача грамматического вывода рассматриваются для случая:

- контекстно-свободных (КС) языков.Ьи;

- полных положительных последовательностей образцов, в которых для любого о > 1,существует т = ти.Ьи) такое, что

■ { х е ьи | |х| \ 3 } с ои;

- методов восстановления, предполагающих использование. двух

самостоятельных процедур:

— метода структурирования, который по известному образцу й строит конечную П-сеть (П-сети), порождающую элементы Й;

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

Переход от КС-грамматик к П-сетям основывается на ряде утверждений, доказанных в диссертации.

КС-грамматика й = <Ы,I, Р,Б> называется нормальной (НКС-грамматикой). если

(а) в Р имеется правило Б —» причем в остальных правилах вывода терминал # не встречается;

(б) в Р отсутствуют е-правила, за исключением, быть может, правила Э —> е;

(в) в Р отсутствуют цепные правила;

(г) в Р отсутствуют бесполезные правила;

(д) в N отсутствуют простые нетерминалы;

(е) С не содержит структурно эквивалентных нетерминалов. Теорема. Для любой КС-грамматики С существует

НКС-грамматика Сн такая, что Ь(СН) = Ь((]) и {#}.

В связи с КС-грамматиками рассматриваются П-сети вида <М,№,р,д>, где

(а) М - множество вершин;

(б) № -множество -ориентированных ребер вида (т,т')х, причем . метка ребра X есть символ некоторого алфавита;

(в) р и я - выделенные вершины из М, которые называются соответственно входным и выходным полюсами.

В П-сети Т пара вершин р' и q' определяет р-элемент Т(р'.я') = <М',V,р', д'), если: Т(р'.д') является р-сетью, и

любой путь [р,ц] в Т, содержащий внутренние вершины сети Т(р',Я'), проходит через р' и ч'.

Доказано, что каждой НКС-грамматике й можно взаимно однозначным образом сопоставить (бесконечную) П-сеть Т, причем каждому нетерминалу (с точностью до изоморфизма р-элементов) взаимно однозначно соответствует некоторый р-элемент.

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

Две р-сети Т' и Т" связаны отношением ~п если р-сети П(Т',п) и П(Т",п) изоморфны.

Доказано, что для любой П-сети Т. построенной по НКС-грамматике С, существует число Е = Е(С), Е(С) > 0, такое, что два р-элемента Т и Т" П-сети Т изоморфны тогда и только тогда, когда Т ~Е Т".

Отсюда следует, что НКС-грамматику в = I,Р,Б> можно восстановить (с точностью до переименования нетерминалов) по конечной П-сети Т' такой, что Т ~к Т, где Т - П-сеть, построенная по грамматике Б, К = Е(0 + |Ш11.

Последнее утверждение является обоснованием метода обобщения, который по известной сети Т строит множество решающих грамматик для Е ='1..М. где М - максимальная глубина р-элементов в Т.

В диссертации рассматриваются методы структурирования (1) регулярных грамматик и (2) однозначных КС-грамматик, а также \ (3) эвристический метод обобщения, рассчитанный на общий класс КС-грамматик.

(1) Для регулярных грамматик П-сеть Т = <М,И, р, строится по образцу й следующим образом:

М = {{х) I ху е й для некоторого у & I* } и Ш = {(ш.ш')а I X е ш Е М, ха е га' е М }; р = (е); Ч = й .

Доказано, что задача грамматического вывода разрешима для регулярного языка источника Ьи> полной положительной последовательности образцов {£>! I 1 > 1} и метода восстановления,

/

состоящего из последовательного применения метода структурирования (1) и универсального метода обобщения.

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

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

Л-сетью называется П-сеть вида:

и Ь IV X! У

V V»! X

У1 ' V

V X

V! ■ - №

где и, , V, У1.х, у - цепочки, уу^Х) * е, ад * е, е, иу * е.

Операция суммирования ■ заданных П-сетей состоит в отождествлении вершин. Две вершины отождествляются, если они находятся в одинаковом положении на путях, соединяющих полюса и порождающих одинаковые цепочки. Кроме того, отождествляются входные и выходные полюса заданных П-сетей.

В общем случае по результатам структурирования образца строится несколько П-сетей и к каждой из них применяется метод обобщения.

Доказано, что задача грамматического вывода разрешима для однозначного КС-языка источника Ьи, полной положительной последовательности образцов | 1 > 1} и описанного метода восстановления однозначных КС-грамматик.

(3) Эвристический метод фиксирует, механизм нахождения общей структуры двух терминальных цепочек - цепочки ХдА^ ... хп_! Апхп _ которая считается выводимой в искомой грамматике. Кроме того, считается,, что среди нетривиальных общих структур содержатся правые части правил для основного нетерминала. После вычисления правил для основного нетерминала задача структурирования рекурсивно сводится к структурированию цодобразцов для вновь построенных нетерминалов. Фактически. эвристический метод позволяет строить нерекурсивные грамматики, эквивалентные некоторой конечной П-сети, к которой на следующем этапе восстановления применяется универсальный метод обобщения.

В пятой главе диссертации

"МЕТОДЫ РЕАЛИЗАЦИИ АВТОМАТИЗИРОВАННЫХ"СИСТЕМ'ИНЖЕНЕРИИ ' ЗНАНИЙ, ОСНОВАННЫЕ НА СОПОСТАВЛЕНИИ РЕШЕНИЙ"

рассматриваются методы реализации АСИЗ, ориентированные на различные классы задач и разные способы представления знаний:

(1) игровая реализация метода репертуарных решеток;

(2) языки образов для организации диалога с экспертом в АСИЗ;

(3) метод ролевых диалогов;

(4) метод синтеза схем управления;

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

(1) Игровой метод реализации сценария извлечения знаний методом репертуарных решеток состоит в разделении этапов принятия решений и их документирования.

На этапе принятия решений АСИЗ последовательно предъявляет эксперту различные тройки решений. Задача эксперта состоит в том, чтобы разбить решения каждой тройки на два класса, содержащих соответственно одно контрастное и два сходных решения. На этапе документирования эксперт вводит названия атрибутов и их значений, объясняя тем самым ранее сделанные разбиения.

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

ЯХТ и мостов".

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

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

(3) Ролевой диалог соотносит профессиональное умение эксперта с некоторой общеизвестной сферой деятельности. Совмещение глобальных контекстов двух видов деятельности:

- позволяет АСИЗ "заимствовать" общеизвестную терминологию для формулировки заданий эксперту;

- придает диалогу с экспертом эмоциональную окраску;

- позволяет реализовать естественную управляющую стратегию сценария извлечения знаний.

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

выявления знаний о задачах выбора.

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

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

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

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

Независимо от конкретной формулировки ситуация первого типа содержит:

- наименования двух товаров;

- описание некоторого дефекту существующей совокупности критериев;

- меню реплик, предусматривающих пути устранения указанного дефекта.

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

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

- наименование только одного товара;

- характеристику этого товара на основе существующей в данный момент совокупности критериев;

- формулировку одного из трех заданий:

(а) указать главное преимущество товара;

(б) указать существенный недостаток товара;

(в) указать определяющее свойство товара.

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

Применимость сценария "Рекламный агент" определяется прежде

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

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

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

Действием называется тройка <Name,Pred, Post>, где

(а) Name - имя действия;

(б) Pred - предусловие действия, суть - класс ситуаций;

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

Схемой управления называется сеть <M,W,p,q>, в которой в качестве меток ребер используются действия, причем все ребра, исходящие из входного плюса р, помечены действием s, а все ребра, входящие в q, помечены действием f.

Схему управления <М,W,p, q> можно рассматривать как

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

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

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

Этап 2. Рассматривая имена действий как терминальные символы, построить с помощью метода восстановления регулярных грамматик множество решающих праволинейных грамматик М(С).

Этап 3. Выбрать из множества М(0 наилучшую грамматику и построить для нее конечный автомат.

Этап 4. Выявить пред- и постусловия действий и завершить таким образом преобразование конечного автомата в искомую схему управления.

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

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

Невербализованный характер личных знаний . помимо задачи "ЧТО сказать?" ставит перед экспертом задачу "КАК сказать?".

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

Этап 1. Предложить эксперту сформулировать вопросительное предложение - цепочку (1 - по известным на него ответам В!. .... Вн-

Этап 2. Предложить эксперту для каждой заготовки В! (1=1...Ю ввести с клавиатуры цепочку - ответ на вопрос 0. в полной форме.

•Этап 3. Из множества полных ответов {1^, .... выделить атрибут как неизменную часть полных ответов, и значения атрибута как варьирующую часть соответствующих полных ответов.

Этап 4. Предложить эксперту провести корректировку полученных имен.

В программной реализации метода доводки имен на этапе 2 подключается • процедура предсказания, которая предлагает свой вариант очередного полного ответа. При этом эксперту представляется возможность исправить предсказанный ответ. Метод предсказания ответов существенно использует эвристический метод восстановления КС-грамматик.

В шестой главе диссертации -

"ИГРОВЫЕ МЕТОДЫ РЕАЛИЗАЦИИ АВТОМАТИЗИРОВАННЫХ ' СИСТЕМ ИНЖЕНЕРИИ ЗНАНИЙ" рассматривается особое семейство АСИЗ, предназначенных для

извлечения знаний о закономерностях проблемной области и правилах принятия решений. В экспертных играх:

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

- сценарий извлечения знаний задается правилами компьютерной игры (для эксперта правила определяют игровую цель и средства ее достижения).

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

В диссертации рассматриваются версии конкретных экспертных игр: (1)' "Черный ящик", (2) "Буриме" и (3)' "Угадай-ка".

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

с

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

В игре "Черный ящик" протокол игровых действий эксперта представляет собой матрицу ставок ||С(р, ¿¡)||. где р - элементы множества решений, з = 1... К - номер тура игры.

Основная гипотеза метода анализа протоколов игры "Черный ящик" состоит в том, что эксперт, корректируя ставки в 1-ом туре, учитывает все известные к этому моменту факты описания. Соответственно программная реализация поддерживает эту гипотезу и сохранять на экране факты Ф]......

В игре "Черный ящик" самое неблагоприятное поведение эксперта состоит в том, что в первых турах игры он расчетливо "покупает" факты, не вкладывая в истраченные очки смысл ставок на выигрыш. В общем случае неблагоприятная стратегия поведения проявляется в виде свойства функции Р(Л): Р(Л) = Ь для 3 < К, где - сумма ставок С(р,□), сделанных в ¿¡-ом туре игры.

В связи с этим когнитологу необходимо прежде всего определить номер тура Н, начиная с которого эксперт начинает существенно использовать свои знания. Критерием выбора является величина Г(3) - I.

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

множестве [Н,К] имеет либо унимодальный, либо неубывающий характер.

По результатам анализа протокола эксперт имеет возможность

сформировать

продукции: ЕСЛИ и ... и ТО р

с коэффициентом уверенности W(p,m), где W(p,J)

- нормированное значение ставки на решение

р в j-м туре игры; ш = шах argmax W(p,j)

H<J<K

и/или запреты: ЗАПРЕТ{Ф^^.....J>j, р),

для р и i таких, что С(р, i-l) * О и С(р, 1) = 0.

(2) Игра "Буриме" начинается с того, что компьютер предъявляет эксперту одно из решений и предлагает отгадать задуманный набор фактов, составляющих его описание. Количество фактов описания - число ND - сообщается заранее.

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

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

является описание Ъ, присутствовавшее на экране в начале построения Ъх.

Метод анализа протоколов игры "Буриме" основывается на трех гипотезах, фиксирующих способ представления знаний и приемы рассуждений эксперта:

- Каждому описанию соответствует дерево вывода в некоторой продукционной системе.

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

- Новое описание как правило, генерируется из базового описания Ъ посредством замены одного из его поддеревьев.

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

В игре "Буриме" выявление формальных структур знаний основано на эвристической процедуре свертки протокола в И/ИЛИ-дерево, допускающее альтернативное представление ИЛИ-вершин. Процедура является рекурсивной и использует в качестве исходных данных последовательность описаний ' ...,

Метод свертки существенно опирается на гипотезы о способе представления и использования знаний.

И/ИЛИ-дерево, полученное в результате свертки протокола, необходимо уточнить и конкретизировать. Эту работу выполняет когнитолог при участии эксперта. Обычно восстановленное дерево

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

Функциональные возможности редактора обеспечивают:

- наглядное представление И/ИЛИ-дерева;

- именование промежуточных вершин, представленных в И/ИЛИ-дереве;

- уточнение структуры И/ИЛИ-дерева; при этом редактор берет на себя обработку вариантов представления ИЛИ-вершин - доказано, что альтернативы для представления ИЛИ-вершин образуют ПА-систему.

- документирование выявленных продукций в соответствии с требованиями входного языка системы ФИАКР.

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

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

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

В игре "Угадай-ка" протокол действий эксперта можно рассматривать как последовательность пар <Ч1, Рр (1=1...Т). где V1 есть или 1 Фг в зависимости от проверки наличия в описании факта Ф1# Р! - множество решений, вычеркнутых экспертом по результатам предъявления и проверки.

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

Первый (полный) вариант извлечения знаний исходит из того, что, исключая в 1-ом туре игры решение р. эксперт опирается на всю информацию о примере, доступную ему в данный момент: V! & ... & V). В этом случае вычеркивание является следствием проявления модуля знаний ЗАПРЕТ^.....У1, р).

Второй (усеченный) вариант интерпретации протокола предполагает, что эксперт ' опирается только на самые последние сведения о примере, поэтому в основе его действий лежит

ЗАПРЕТ(У^ р)

Все остальные способы интерпретации протокола сводятся к поиску компромисса между первым и вторым вариантами.

Поскольку каждый факт, предъявленный экспертом для проверки, связан с тем или иным атрибутом, то протокол игры "Угадай-ка" можно рассматривать как анкету опроса - еще один тип

модулей знаний, извлекаемых из протокола игры. Кроме того, протокол игры "Угадай-ка" можно рассматривать как готовую трассу логического вывода - тест для подсистемы отладки баз знаний.

3. ЗАКЛЮЧЕНИЕ

Сформулируем основные результаты, полученные в диссертационной работе:

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

- ориентация на извлечение знаний посредством автоматизированного опроса эксперта под общим контролем когнитолога (инженера по знаниям);

- информационная и инструментальная поддержка деятельности когнитолога по анализу протоколов опроса и формированию баз знаний.

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

- блок опроса эксперта;

- блок оценки эффективности опроса;

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

2. В интересах реализации АСИЗ разработан формализм простых

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

- доказана теорема об универсальности выразительных возможностей:

- разработаны алгоритмы логического вывода;

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

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

- поддерживающей внутреннее представление баз знаний в виде простых систем альтернатив;

- содержащей подсистему отладки баз■ знаний, построенную на принципах АСИЗ;

- допускающей представление знаний, полученных с помощью АСИЗ.

4. В интересах реализации АСИЗ разработаны и обоснованы методы восстановления формальных грамматик по заданному образцу -конечному множеству синтаксически правильных предложений. Восстановление контекстно-свободных грамматик предложено рассматривать как последовательное выполнение этапа структурирования образца в виде П-сети с помеченными ребрами и этапа обобщения полученной структуры. Разработаны: методы структурирования для -регулярных и однозначных контекстно-свободных грамматик, эвристический метод структурирования, а также универсальный метод обобщения. Доказаны теоремы о корректности предложенных методов.

5. Предложены и исследованы новые методы построения АСИЗ, основанные на принципе сопоставления решений. В ряде АСИЗ . реализованы:

- игровая версия метода репертуарных решеток;

- методы ролевых диалогов;

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

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

6. Предложена методология экспертных игр, основанная на принципе заочной консультации. Отличительными признаками этого класса АСИЗ являются:

- поддержка диалога с экспертом в форме компьютерной игры;

- ориентация на извлечение знаний о закономерностях проблемной области и правилах принятия решений.

Предложен и исследован ряд конкретных экспертных игр, выявлены критерии оценки продуктивности опроса эксперта.

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

Результаты диссертационной работы использованы при выполнении НИР "Разработка инструментальной экспертной системы ФИАКР-РАФОС" и "Развитие функциональных возможностей инструментальной экспертной системы ФИАКР" (заказчик - Институт проблем управления Минприбора и АН СССР),

НИР "Создание решателей и подсистем отладки баз знаний, опирающихся на идеи классификации и аналогии" (шифр "Кижуч-АН") и "Создание инструментальных средств для общения с экспертами при приобретении знаний" (шифр "Кинескоп-АН"; генеральный заказчик - секция прикладных проблем АН СССР), ОКР "Создание инструментальных программных средств при извлечении знаний" (тема "КОНТАКТ"), и "Разработка инструментальных средств создания и поддержки проблемно-ориентированных баз знаний" (темы "СРЕДА" и "БАЗА"; заказчик - Всесоюзный институт проблем вычислительной техники и информатизации Государственного Комитета СССР по вычислительной технике и информатике), задания 6.3 "Экспертные системы в сельском хозяйстве" проблемы 1.2.2 "Экспертные вычислительные системы" Комплексной Программы научно-технического прогресса стран членов СЭВ 1986. 1990 гг.,

а также в учебном процессе на факультете вычислительной математики и кибернетики Московского государственного университета им. М. В.Ломоносова.

Основные результаты диссертации опубликованы в работах:

1. Соловьев С.Ю. Подход к восстановлению контекстно-свободных языков. Сб. Автоматизация производства пакетов прикладных программ. Таллин, 1980. с.126-129

2. Соловьев С.Ю. Метод восстановления Ы(1)-грамматик. Сб. Прикладная математика и математическое обеспечение ЭВМ. Изд-во Моск. ун-та, 1980. с.92-93

3. Соловьев С.Ю. Об одной конструктивной процедуре грамматичес-

кого вывода. Вестник Моск.ун-та. Сер. 15. Вычислит, математика и кибернетика. N 3, 1980. с.44-48

4. Соловьев С. Ю. Методы восстановления контекстно-свободных грамматик. Сб. Вопросы теоретического и прикладного программирования. Изд-во Моск. ун-та, 1980. с.82-87

5. Соловьев С. Ю.,Соловьева Г.М. Представление знаний в системах альтернатив. Сб. Логико-комбинаторные методы в искусственном интеллекте и распознавании образов. Кишинев, 1985. с.11-15

6. Соловьев С. Ю. Постановка задачи грамматического вывода. Сб. Математические исследования. Вып.81. Кишинев: Штиинца, 1985. с. 135-143

7. Соловьев С.Ю., Соловьева Г.М. Методы отладки баз знаний в системе ФИАКР. Сб. Автоматизация и роботизация производства с применением микропроцессорных средств. Кишинев, 1986. с.36-37

8. Соловьев С. Ю., Смирнов В.А. Соловьева Г.М. Фролов Ф.В. Экспертная система ФИАКР-Т. Сб. Моделирование и оптимизация в задачах планирования и управления. Мат.исслед. вып.87. Кишинев: Штиинца. 1986. с.157-161

9. Соловьев С.Ю., Гинкул Г. П. Об одном подходе к формированию баз знаний. Сб. Молодежь, Наука, Производство. Кишинев: Штиинца, 1986. с. 270

10. Соловьев С.Ю., Соловьева Г.М. Инструментальная экспертная система ФИАКР. ГосФАП ОТ 26.11.86 ИГР 50860001141. 300с.

И. Соловьев С. Ю., Соловьева Г.М. Инструментальная экспертная система для мини-ЭВМ. Препринт ИМ с ВЦ АН МССР, Штиинца, 1986. 36с.

12. Соловьев С.Ю,. Солрвьева Г.М. Вопросы применения метода альтернатив для представления знаний. Изв. АН СССР, Техн.киб.

N 5, 1987. С.80-92

13. Соловьев С.Ю.. Соловьева Г.М. Входной язык системы ФИАКР. Сб. Программное обеспечение вычислительных комплексов. Мат.исслед.вып. 104. Кишинев: Штиинца, 1988. с.110-116

14. Соловьев С.Ю. Блок объяснений в системе ФИАКР. Труды 1 Всес. конф. по 'искусственному интеллекту. Н: ВИНИТИ, 1988. с. 516-520

15. Соловьев С.Ю., Соловьева Г.М. Архитектура экспертной системы ФИАКР. Сб. Теория и практика программирования. Мат.исслед. вып. 107. Кишинев: Штиинца, 1989. с.111-128

16. Соловьев С.Ю., Соловьева Г.М. Вопросы организации баз знаний в системе ФИАКР. Сб. Экспертные системы: состояние и перспективы. М: Наука, 1989. с.47-54

17. Соловьев С.Ю., Соловьева Г.М. Коммерческая система ФИАКР. Справочник. Искусственный интеллект. Кн. 1. Системы общения и экспертные системы. М: Радио и связь, 1990. с.362-369

18. Соловьев С.Ю. Реализация машины вывода в системах альтернатив. Труды 2 Всес.конф. по искусственному интеллекту.. Том 1. Минск, 1990. с.170-172

19. Соловьев С.Ю.. Гинкул Г. П. Методы формирования признаковых моделей проблемных областей. Сб.трудов 3 конф. по искусственному интеллекту. Том 1. Тверь. 1992. с. 99-101

20. SolowlevS., Solowieva G. Method of Alternanive for Knowledge Representanlon. Proceedings of the 4th International Meeting of Young Computer Scientists IMYCS-86. Budapest, 1986. c. 253-257

21. SolowlevS., Pechersky J., Solowieva G. The Principles of Expert Recognition Systems Design. Internanional Journal of

Pattern Recognition and Artificial Intelligence. Vol 3. N 1, 1989. pp.113-119

22. Solowiev S., Andrlenko, G., Anarlenko, N. Ginkul G. Automatizated Means for Knowledge Acquisition. Computer Science Journal of Moldova. Vol. 1, N 1, 1993. pp. 42-50

23. Solowiev S.. Ginkul G. Automatizated Elicititing of Expert Knowledge. Intelligent Systems In Education, R.I.T., Rochester, USA. 1994. pp.130-137

24. Solowiev S., Ginkul G. CAPRICE: Knowledge Acquisition Tool Based on Game Approach. Computer Science Journal of Moldova. Vol. 2, N 2, 1994. pp.140-150

25. Solowiev S. Some Properties of Model of Plausible Reasoning. Proceedings of Japan-CIS Symposium on Knowledge Base Softwaring Engineering, 1994. p. 202