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

1 0 9 1

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОЗДША ТРУДОВОГО КРАСНОГО аЧАМЕНИ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им.М.В.ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

На правах рукописи УЖ 519.81

ГИНКУЛ Геннадий Петрович

ИГРОВОЙ ПОДХОД К ФОРМИРОВАНИЮ БАЗ ЗНАНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ

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

АВТОРЕФЕРАТ

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

МОСКВА-1991

■■ „у | ) л • / < Л

Работа выполнена на кафедре Алгоритмических языков факультета Вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова.

Научный руководитель: кандидат физико-математических наук, доцент Пилъшдков В. Н.

Официальные опоненты: доктор физико-математических наук, профессор Любимский Э. 3. кандидат физико-математических наук, ст. научный сотрудник Юфа В. М.

Ведущая организация: Вычислительный Центр АН СССР

Защита состоится "■!£> " НОЛ<Ь№ 1991 г. в ^7 час. на заседании Специализированного совета Д. 053.05. 38 N 4 по математике при МГУ им. М. В. Ломоносова по адресу 119899, г. Москва, ГСП, Ленинские горы, МГУ,_ факультет вычислительной математики и кибернетики, ауд. .

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан " QfcTj 1991 г.

Ученый секретарь Совета, профессор

Н. П. Трифонов

г;.Г • •• 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы и публикации. По теме диссертации опубликовано 10 печатных работ. Результаты работы докладывались на Неддународных конференциях "Распознавание образов и экспертные системы" - Новосибирск, 1987 и "Теория и применение искусственного интеллекта" - Созополь (НР£). 1989, I и II Всесоюзных конференциях по искусственному интеллекту (Переславль-Залесс-ккй, 1988; К:нек, 1990), на республиканских конференциях (Кишинев. 1986, 1987, 1988, 1989; Рига, 1990). Результаты докладывались также на научных семинарах факультета вычислительной математшси и кибернетики МГУ им. К В. Ломоносова, на научных семинарах Института математики с ВЦ АН РМ.

Структура п объем диссертации. Диссертация состоят из введения, трех глав, заклэтеК-'я и библиографии.

Основной текст диссертационной работы изложи на 105 страницах н включает 6 рисунков и список литературы, насчитывал^ 55 наименований.

- б -

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

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

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

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

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

нером по знаниям.

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

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

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

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

Во второй главе работы излагаются основная идея предлагаемого а диссертации подхода к приобретению знаний. Разработан-

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

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

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

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

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

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

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

Основное место во второй главе диссертации отведено подробному описанию двух экспертных игр: "Черный ящик" и "Буриме". Эти игры относятся к классу ' тестовых игр. Основная идея тестовых игр связана с отгадыванием какого-либо объекта путем целенаправленного задавания ■ наводящих вопросов. Р'йор : тросов-ходов, приводящих к цели, есть, по существу, тест для отгадывания задуманного объекта, и Задача эксперта заключается в том, чтобы построить как можно более короткий тес

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

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

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

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

Для проведения экспертной игры "Буриме" необходимо иметь

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

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

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

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

Процедура анализа протоколов игры "Буриме" получает на входе последовательность попыток и формирует по ним '{/ИЛИ дерево. Промежуточные вершшы дерева соответствуют синдромам (ИЛИ-вершины) и их определениям (И-зграмны). Дальнейшая работа с построенным деревом предполагает, что найденные шдромы должны получить наименования, после чего все дерем или его ча^ть можно представить в виде продукций.

Третья глава диссертации посвящена практической реализа-

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

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

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

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

файлы.

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

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

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

Система КАПРИЗ реализована на языке ЛИСП для ПЭВМ типа IBM PC.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Г. П. Гинкул, Соловьев С. Е- Подход к формированию баз знаний. В сб. Автоматизация производства с применением микропроцессорных средств, Кишинев, 1986. с. 36 .

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

3. Г. П. Гинкул. Экспертные игры для формирования баз знаний. В сб. Технология разработки экспертных систем. Кишинев,

1987. с. 46-48

4. Г. П. Гинкул. Игровые алгоритмы для работы с эюзпертом. В сб. Диалоговые средства в АСУ. Кишинев, 1988. с. 130-132 .

5. Г. П. Гинкул. Игровой подход к работе с экспертом. Тез. докл. Всесоюзной конфер. по искусств, интеллекту. Шсква,

1988. с. 338-342 .

6. Г. П. Гинкул. Об одном алгоритме формирования баз знаний. Тез. докл. Респ. научно-практич. конф. "Применение экой.-мат. методов и выч. техники в планировании и управлении нар. хоз-вом. Кишинев, 1988. с. 12-13 .