Введение к работе
Актуальность проблемы. Текущий период развития информатики можно назвать периодом интеллектуализации, когда информационные системы, предназначенные для анализа определенных предметных областей, стали в значительной степени использовать не только данные, но и знания. Под последними обычно понимают эмпирические закономерности предметной области» а также способы их. получения и использования в результате правдоподобного вывода (ПВ). Правдоподобный вывод, в отличие от чисто дедуктивного (достоверного), характеризуется тем. что не всегда получает истинные заключения из истинных посылок.
В связи с этим актуальными становятся две взаимосвязанные проблемы: (1) обучение в компьютерных информационных системах, то есть проблема создания методов получения эмпирических закономерностей из эмпирических данных с помощью ЭШ; (2) оценивание обоснованности результатов обучения или. более кироко, правдоподобного вывода (ПВ).
В данной диссертационной работе эти проблемы исследуются в рамках разработок по интеллектуальным информационным системам, основанным на так называемом ДСМ-методе автоматического порождения гипотев (ДСИ-АПГ), развиваемом R К. Финном и его группой в ВИНИТИ
гкт и ah ссср.*}
*)Финн В. К. Правдоподобные выводы и правдоподобные рассуждения // 3 Итоги науки и техники. Сер. Теория вероятностей Математическая статистика. Теоретическая кибернетика. Т.28.- it:ВИНИТИ. 1988.- 0.3-84.
Цель работы Целью диссертационной работы является исследование различных аспектов обоснованности гипотез в ДСМ-АПГ. в том числе перенос средств интеллектуальных систем указанного типа (действовавших ранее лишь на простейшем типе представления данных - множествах) на сложноструктурированные данные - графы и гиперграфы, исследование сложностных аспектов порождения и обоснования гипотез в ДСМ-АПГ, а также устойчивости ДСМ-гипотез.
В результате проведенных исследований разработаны средства решения вадачи "Структура соединения - биологическая активность" с помощью интеллектуальных систем типа ДСМ, использующих графовое представление данных, а также методы отбора гипотез по оценкам устойчивости в задачах технологической диагностики.
Методы исследования. В работе широко применялись методы диск ретной математики: теории автоматического обучения, теории графов, комбинаторной теории, математической логики и теории алгоритмической сложности.
Научная новизна. В работе получены следующие новые результаты:
на основе разработанной алгебры сходства и различия множеств гиперграфов интеллектуальные системы типа ДСМ распространены на случай этого более сложного типа данных;
введено понятие структурной немонотонности, позволяющее описывать эффекты изменения реаультатов правдоподобного вывода при изменении представления данных. Исследованы возможности структурной немонотонности в ДСМ-АПГ при переходе от дескрипторного описания к графовому;
- предложена комбинаторная интерпретация поиска гипотез в
ДСМ-АПГ для случая дескрипторного представления данньк, позволяющая сравнивать ДСМ-АПГ с другими системами автоматического обучения, а также эффективно решать некоторые задачи ДСМ-АПГ;
определена алгоритмическая сложность некоторых задач ДСМ-АПГ, для некоторых из которых указаны эффективные алгоритмы, а для других доказана принципиальная трудновычислимость (в смысле NP- или #Р- полноты);
введены числовые оценки устойчивости ДСК-гипотез ч случайности при подборе данных. Введенные оценки могут использоваться также и в других системах правдоподобного вывода, использующего операциональное понимание сходства нечисловых объектов. Исследованы различные свойства этих оценок, в том числе возможности их эффективной вычислимости.
Практическая ценность. Перенос средств ДС?<ЬАПГ на гиперграфовую структуру данных на основе разработанной алгебры сходства и различия дал возможность проводить более тонкий анализ свойств структурированных объектов, чем это позволяют делать теоретико-множественные (дескрипторные) языки представления. Особое значение указанные средства имеют для решения вадач фармакологии: прогноз свойств лекарственных веществ на основании информации об их химическом строении (задача "Структура - Активность") и автоматического синтеза лекарств. В частности, использование графовой структуры данных дает более адекватные результаты, чем использова-^ ние известных дескрипториых языков типа ФКСП. в задачах, связанных » с прогнозом биологических свойств химических соединений и автома-
тическим синтезом лекарств.
Анализ алгоритмической сложности правдоподобного вывода в ДСП -АПГ дает возможность создавать эффективные алгоритмические средства, с помощью которых возможно получение более обоснованных ДСЙ-гипотез на основании больших массивов данных.
Анализ устойчивости ДСМ-гипотез позволяет эффективнее отбирать гипотезы о структурных причинах свойств объектов из предметной области, в меньшей степени зависящие от произвола при подборе исходных данных. При решении задачи "Условия синтеза - свойства полимера" использование индексов устойчивости помогло осуществлять отбор наиболее полезных гипотез о технологических и сырьевых причинах дефектов полимеров: наличия включений, общэго несоответствия параметрам ТУ и ГОСТа
, Реализация и внедрение результатов исследований. На основе разработанной алгебры сходства и различия множеств гиперграфов были созданы алгоритмические средства, послужившие основой для переноса ДСМ-АПГ на графовую структуру данных для исследования проблемы "Структура - Активность". С помощью этих средств были исследованы структурные причины биологических свойств химических веществ из ряда индолов, что подтверждается справкой о внедрении. На основе введенных определений оценок устойчивости были предложены алгоритмы их вычисления. Оценки устойчивости использовались для отбора гипотез в задаче-технической диагностики - при анализе технологических причин дефектов полимеров, производимых в НПО "ПЛАСТМАССЫ", что тоже подтверждается справкой о внедрении.
- 5~
Апробация работы. Результаты исследований докладывались на всесоюзном семинаре "Молекулярные графы и' их применения в химических исследованиях" (Одесса,1987), Всесоюзной школе-семинаре "Семиотические аспекты формализации интеллектуальной деятельности" (Боржоми,1988), Первой всесоюзной конференции по искусственному интеллекту (Переславль-Залесский, 1S88), Обшемосковском сеиинаре по искусственному интеллекту, семинарах ВИНИТИ, механико-математического факультета МІ'У, МИАН и ВЦ АН СССР. По диссертации опубликовано 5 работ, приведенные в прилагаемом ниже списке литературы.
Структура и объем работы. Диссертационная работа состоит из 4 глав, введения и заключения. Объем диссертации 134 страницы машинописного текста В диссертации приведено 2 рисунка. Список литературы включает 79 наименований.