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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР АКАДЕМИЯ НАУК СССР

ПО НАУКЕ И ТЕХНИКЕ

ВСЕСОЮЗНЫЙ ИНСТИТУТ НАУЧНОЙ И ТЕХНИЧЕСКОЙ ИНФОРМАЦИИ

(ВИНИТИ)

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

КУЗНЕЦОВ Сергей Олегович

УДК 519.767

ПОВЫШЕНИЕ ОБОСНОВАННОСТИ ГИПОТЕЗ В ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ СПЕЦИАЛЬНОГО ТИПА

Специальность 05.13.17 Теоретические основы информатики

АВТОРЕФЕРАТ

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

МОСКВА 1990

Работа выполнена во Всесоюзном институте научной и технической информации Государственного комитета по науке и технике и Академии Наук СССР.

Научный руководитель:

доктор технических наук, профессор Игорь Алексеевич БОЛЬШАКОВ

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

доктор технических наук, профессор Дмитрий Александрович ПОСПЕЛОВ, кандидат технических наук Илья Борисович МУЧНИК

Ведущая организация: Институт проблем передачи информации АН СССР

заседании Специализированного совета Д 003.02.01 во Всесоюзном институте научной и технической информации по адресу: 125219, Москва, ул. Усиевича, д. 20а

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

Автореферат разослан « 14— » г.

Защита состоится

года в Ю часов на

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

ПЕТРОВА Лидия Андреевна

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

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

В связи с этим актуальными становятся две взаимосвязанные проблемы: (1) обучение в -компьютерных информационных системах, то есть проблема создания методов получения эмпирических закономерностей из эмпирических данных с помощью ЭВМ; (2) оценивание обоснованности результатов обучения или. более сироко, правдоподобного вывода (ПВ).

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

*)Финн В. К. Правдоподобные выводы и правдоподобные рассуждения // 3 Итоги науки и техники. Сер. Теория вероятностей Математическая статистика. Теоретическая кибернетика. Т.28.- Л:ВИНИТИ, 1988,- 0.3-84.

Цель работы. Целью диссертационной работы является исследование различных аспектов обоснованности гипотез в ДСМ-АПГ, в том числе перенос средств интеллектуальных систем указанного типа (действовавших ранее лишь на простейшем типе представления данных - множествах) на сложноструктурированные данные - графы и гиперграфы, исследование сложностных аспектов порождения и обоснования гипотез в ДСМ-АПГ, а также устойчивости ДСМ-гипотез.

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

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

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

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

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

- предложена комбинаторная интерпретация поиска гипотез в ДСМ-АПГ для случая дескрипторного представления данных, позволяющая сравнивать ДСМ-АПГ с другими системами автоматического обучения, а также эффективно решать некоторые задачи ДСМ-АПГ;

- определена алгоритмическая сложность некоторых задач ДСМ-АПГ, для некоторых из которых указаны эффективные алгоритмы, а для других доказана принципиальная трудновычислимость (в смысле ИР- или #Р- полноты);

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

Практическая цепкость. Перенос средств ДС?<ЬАПГ на гиперграфовую структуру данных на основе разработанной алгебры сходства и различия дал возможность проводить более тонкий анализ свойств структурированных объектов, чем это позволяют делать теоретико-множественные (дескрипторные) языки представления. Особое ена-чение указанные средства имеют для решения вадач фармакологии: прогноз свойств лекарственных вешрств на основании информации об их химическом строении (вадача "Структура - Активность") и автоматического синтеза лекарств. В частности, использование графовой структуры данных дает более адекватные результаты, чем использоваЛ ние известных дескрипториых языков типа ФКСП. в задачах, связанных Й с прогнозом биологических свойств химических соединений и автома-

тическим синтезом лекарств.

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

Анализ устойчивости ДСМ-гипотез позволяет эффективнее отбирать гипотезы о структурных причинах свойств объектов из предметной области, в меньшей степени зависящие от произвола при подборе исходных данных. При решении задачи "Условия синтеза - свойства полимера" использование индексов устойчивости помогло осуществлять отбор наиболее полезных гипотез о технологических и сырьевых причинах дефектов полимеров: наличия включений, общэго несоответствия параметрам ТУ и ГОСТа

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

- б -

Апробация работы. Результаты исследований докладывались на всесоюзном семинаре "Молекулярные графы и' их применения в химических исследованиях" (Одесса,1987), Всесоюзной школе-семинаре "Семиотические аспекты формализации интеллектуальной деятельности" ( Боржоми,1988), Первой всесоюзной конференции по искусственному интеллекту (Переславль-Залесский, 1S88), Об гае московском семинаре по искусственному интеллекту, семинарах ВИНИТИ, механико-математического факультета МГУ, Ю1АН и ВЦ АН СССР. По диссертации опубликовано 5 работ, приведенные в прилагаемом ниже списке литературы.

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

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

Во введении обосновывается актуальность выбранной темы, приводится краткий обзор состояния работ по оценке обоснованности правдоподобного вывода, поиску сходства сложноструктурированных объектов, дается краткое описание принципов ДСЫ-АПГ, определяется цель исследования, дается общее описание построения диссертационной работа

Первая глава посвящена вопросам переноса средств ДСЫ-АПГ на новый тип данных - множества гиперграфов с упорядоченными метками. Сначала дается дается описание правил ДСЫ-АПГ. Система ДСЫ-АПГ 8 предназначена для анализа связи структуры объектов с их свойства-

ми. Основное методологическое допущение, лежащее в основе ЯСМ-АПГ состоит в том, что общность свойств ряда объектов есть проявление общности структуры объектов, а последнее может быть выявлено с помощью адекватного языка представления данных. Поэтому основой правил правдоподобного вывода (ПИВ) в ДСМ-АПГ является понятие сходства объектов. Сходство понимается вдесь не в метрическом смысле, а в операциональном: объекты А и В сходны, если результат аП В применения соответствующей операции сходства П не есть пустой объект В ЛСЙ-АПГ в качестве потенциальных причин связи (зависимости) структур объектов с их свойствами могут рассматриваться не только парные, но и п-арные сходства объектов, поэтому необходимо однозначное выражения сходства п объектов через бинарную операцию П .

Входом системы ДСМ-АПГ является множество положительных примеров (эмпирических фактов о положительной корреляции некоторых объектов.и исследуемого свойства V) и отрицательных примеров (фактов об отрицательной корреляции).

Действия ДСМ-АПГ в общих чертах выглядят следующим образом. На первом шаге действия система выделяет сходства положительных примеров (общие части их описаний) и проверяет, не являются ли они также сходствами отрицательных примеров. Если проверки такого рода, а также, быть может, и некоторые другие, для некоторой общей части Ь положительных примеров проходят успешно, то И считается положительной гипотезой о причине исследуемого свойства V (положительной гипотезой первого рода) и мояет использоваться на следующем этапе для прогнозирования наличия свойства V у новых объектов, структуры которых известны, а свойства - нет. Аналогичным образок поролщаюггся отрицательные гипотезы первого рода На втором этапе

требуется сделать прогноз о том, будут или нет некоторые предъявленные системе объекты обладать свойством V. Этот прогноз осуществляется на основе анализа вхождений положительных и отрицательных гипотез первого рода (причин) в предъявляемые объекты. Если имеет место вхождение лишь положительных причин при отсутствии отрицательных или псе входящие в объект отрицательные причины "слабее"• (в некотором смысле) положительных причин, то ДСМ-АПГ будет прогнозировать проявление свойства V у предъявляемых обт?ектов. Если ситуация противоположная, то прогноз будет отрицательным. Наконец, если положительные и отрицательные причины "сталкиваются", то имеет место ситуация противоречия. Если ни та ни другая ситуация не имеет места, то прогноз средствами ДСМ-АГГГ не возмокен.

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

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

нения булевой алгебры. Показано, что операции сходства и соединения задают на Н-множествах дистрибутивную решетку, то есть для любых И-множеств X. У» Ъ имеют место соотношения (I).

хПх - х, х11х - X, ХПУ - УПХ,

Х1!У - УУХ, (I)

хП(уПг) - (хПу)Пг,

хУсуУг) - (хи^Уг.

(хП^и х - х,

хЛ(у1к) - (хГЫ! (хЛгь

Для Ы-множеств вводятся операции псевдоразности, имитирующие булеву» разность. Исследуется вопрос, какие свойства из списков (II) - (IV) выполняются для введенных псевдорааностей для произвольных Я-множеств X, У, 1 (их аналоги выполняются для булевых операций):

ХЧО - X,

(х1]у)\г

С х\2) и (,

(П)

АХ -

У$£ Х\У при У /

хчуЦг), сх\у)\гэ х\(у1]2), (хчу)\г -.хч<уУг)..

(Ш)

с хчу) - (х\г)\у, хч(уИг) - (хчу)П(х\2), (хПг)\г&сх\г)П(у\2), (хПу)\га(хч2)/1(У\2),

(х/]у)\г - (Х\2)Пскг),

ХЧУГЬ) - (ХЧУ)Ц (ХЧ2).

К\(Х\У) - У\(У\Х), (IV)

Показано, что свойства (11) выполняются для всех девяти введенных операций псевдоразности, свойства (IV) не выполняются ни для одной из введенных операций, а свойства из (III) выполняются для одних операций и не выполняются для других. Правила ДСМ-АПГ формулируются далее для новой структуры данных - И-множеств гиперграфов с частично-упорядоченными метками и приводятся результаты машинного эксперимента по использованию ДСМ-правил для новой структуры;данных в задаче "Структура - Активность" - анализе структурных причин биологических активностей химических соединений из ряда индолов.

Глава 2 посвящена вопросам структурной немонотонности, . то

есть изменениям в результатах правдоподобного вывода при изменении способа представления данных. Понятие немонотонного вывода было введено Дж. МакКарти и Р. Рейтером для моделирования логики здравого смысла

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

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

Изучаются возможности различных типов структурной немонотонности в ДСЫ-АПГ в задаче поиска гипотез о структурных причинах свойств при переходе от дескрипторного (булевого) описания к графовому. Рассматривается как гомоморфный, так и негомоморфный типы переходов. Устанавливается слабая зависимость возможностей тех или иных типов структурной немонотонности от гомоморфности преобразований представления данных. Если для гипотез 1-го рода при гомоморфном преобразовании из графового описания в дескриптор-

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

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

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

Доказана возможность эффективной (полиномиальной)" реализации алгоритмов решения задач о существовании ДСМ-гипотез, для которых Ы-1>к (в отсутствии примеров противоположного знака), 1>к, где Ь -размер гипотезы, 1 - число подтверждающих ее примеров, к - параметр. Показана также труднораврешимость (МР-полнота) вадач поиска гипотез для которых Ь-к, 1- к, Ь+1-к, а также некоторых других.

Предлагается также комбинаторная интерпретация поиска ДСМ-гипотез для случая представления объектов и свойств множествами, а алгебры сходства - булевой алгеброй. Входным данным ДСМ-АПГ в этом случае соответствует при этом некоторый четырехдольный граф, а ДСМ-гипо-тезам - полные двудольные подграфы этого графа, максимальные по вложению. Исследуются перечислительные задачи, связанные с поиском дам-гипотез. ГЬжазано, что вадача "найти число всех ДСМ-гипотез", является полной. Показало также, что «V-полными являются задачи определения числа ДСМ-гипотез' с Г>як, Г-чк , где f (11, 1, Ь+1), Ч - параметр, 0<ч<1. Шкааано, как результат о трудноразрешимое™ (#Р - полноте) задач определения числа гипотез может использоваться при построении эффективного алгоритма построения всех гипотез относительно причин множества свойств.

■ В главе 4 вводятся оценки (индексы) устойчивости ДСМ-гипотез первого рода по отношению к составу и объему множества исходных данных. Использование оценок такого рода основывается на идеях, родственных идеям, лежащим в основе некоторых методов непараметрической статистики - бутстрепа и метода складного ножа. Эти методы раннее применялись к числовым данным в предположении существования некоторого вероятностного распределения. В ДСМ-АПГ не используется какой-либо вероятностной модели, а данные имеют нечисловой характер.

Пусть ДСМ-гипотева И имеет множество подтверждающих примеров X - Щ,.,. ,Хп>, то есть И - »0-. .П Хп и множество X - максимальное из обладающих этим свойством. Шдсемейство х'- Ш.... ,Х5> семейства X назовем подтверждающим гипотезу И, если хШ... Л Хб -к Долю подсемейств X, подтверждающих И среди всех подсемейств X,

назовем интегральным индексом устойчивости И, а долю подсемейств семейства X размера к среди всех подсемейств размера к назовем индексом устойчивости уровня к. В работе исследуется поведение этих индексов устойчивости при пополнении множества исходных данных новыми примерами. Указаны границы и- асимптотические пределы изменения индексов устойчивости при пополнении базы данных. Исследуются вопросы алгоритмической сложности задач вычисления индексов устойчивости. Показано, что задача вычисления индексов устойчивости #Р-полна Приведен алгоритм, позволяющий<вычислять значения индексов устойчивости за время, линейное от значения индексов. Приводятся результаты машинного эксперимента по использованию индексов устойчивости гипотез для отбора гипотез в задаче технологической диагностики - анализе причин дефектов полимеров при их- промышленном производстве (связанных с невыполнением нормативов по ТУ, ГОСТу, а также отклонением по наличию включений).

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

1. Правила правдоподобного вывода (ППВ) ДСМ- метода автоматического порождения гипотез (ДСМ-АПГ) распространены на новый тип данных - множества гиперграфов с упорядоченными метками вершин и гиперребер. Этот тип данных является более общим, чем ранее исследовавшиеся в теории и практике ДСМ-АПГ,

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

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

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

4. В связи с возможностью различных представлений данных об одних и тех же объектах введено понятие структурной немонотонности, позволяющее отражать изменения в результатах ГОШ при переходе от менее точного способа представления данных к более точному и наоборот. Указаны типы структурной немонотонности, возможные в ДСМ -АПГ. Эффекты немонотонности изучены на примере анализа структурных причин и прогноза биологических свойств химических соединений ив ряда индолов.

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

6. В связи с тем, что сложность алгоритмов, реализующих ППВ. влияет обратным образом на обоснованность вывода, изучена эффективность алгоритмов поиска гипотез и определения числа гипотез различного вида Доказан ряд результатов о трудновычислимости (в смысле НР- и полноты, используемых в теории вычислительной сложности) и полиномиальной разрешимости задач нахождения и определения числа гипотез определённого вида Эти результаты имеют значение для практической реализации ДСМ-АПГ в виде программных систем. Положительные результаты о полиномиальной вычислимости да-

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

7. Введено понятие устойчивости ДСМ- гипотез. Показано родство этого понятия с некоторыми понятиями непараметрической статистики. Проведен анализ пределов изменения индексов устойчивости при пополнении базы данных новыми фактами. Изучены вычислительные характеристики задачи определения индексов устойчивости, в частности, доказана ее л?-полнота Построен алгоритм, в «числящий индексы устойчивости за линейное от величины индексов время. Приведены результаты применения индексов устойчивости в задаче- анализа связи технологических условий синтеза полимеров с их свойствами: наличием включений, соответствием ГОСТу и ТУ. Показано, что введенные индексы устойчивости могут применяться при отборе гипотез в задачах технической диагностики, сокращая число гипотез, используемых для принятия решений.

ЛИТЕРАТУРА ПО ДИССЕРТАЦИЙ

1. Кузнецов С. О. О решетке на множествах графов с частично-упорядо-ченными пометками// Тезисы докладов школы-семинара "Семиотические аспекты формализации интеллектуальной деятельности". Боржоми, 1988.- М: ВИНИТИ, 1988, Т.1.- С. 204-207.

2. Кузнецов С. О. Определение сходства на гиперграфах как основа правдоподобного вывода на структурированных данных// Тезисы

докладов Всесоюзной конференции по искусственному интеллекту Переяславль-Залесский, 1988.- lt ВИЖГИ - 1988, Т. 1.- С. 442-448. 3. Кузнецов С. 0. Интерпретация на графах и сложностные характеристики задач поиска закономерностей определенного вида// ИТИ. Сер. 2.- 1989, N1. - С. 23-28. Í. Кузнецов С. 0., йинн В К. Распространение процедур экспертных систем типа ДСМ на графы// Известий АН СССР Сер. Техническая Кибернетика. - 1988, N5. - С. 4-11. 5. Кузнецов С.О., Мельников И'И. Исследование проблемы "Структура-Активность" с помощью ДСМ-АПГ при использовании графового представления молекул.// Тезисы докладов VIII Всесоюзной конференции "Использование вычислительных машин в спектроскопии молекул и химических исследованиях". - Новосибирск. - 1989. - С. 275-276.

Сдано в набор 03.08.90 Подписано в пвчвть 20.0Т.80 Т- 110Б7

Формат 60*30 1/16 Печать офсетная Еум.офс,№

Усл.тчл. 1,0 Усл.*р,-отт. 1,013 Уч.-взд.л. 0,64 Тир, 100 na, Зек. 6242

Прсшжсйстввшю-иэаательсиЯ комбинат ВИНИТИ 140010, Люберцы 10, Московской оба.. Октябрьски* проспект, 403