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

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

ЗАБЕЖАЙЛО МИХАИЛ ИВАНОВИЧ

КОМБИНАТОРНЫЕ СРЕДСТВА ФОРМАЛИЗАЦИИ ЭМПИРИЧЕСКОЙ ИНДУКЦИИ

05.13.17-теоретические основы информатики

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

13 МАЙ 2015

Москва-2015

005568377

005568377

Диссертационная работа выполнена в Отделе теоретических и прикладных проблем информатики Федерального государственного бюджетного учреждение науки «Всероссийский институт научной и технической информации Российской академии наук (ВИНИТИ РАН)»

Научный консультант Доктор технических наук, профессор,

Заслуженный деятель науки РФ ФИНН Виктор Константинович

Официальные оппоненты Чл.-корр. РАН, д.т.н., профессор ЖЕЛТОВ

Сергей Юрьевич, Генеральный директор ФГУП «Государственный научно-исследовательский институт авиационных систем».

Д.ф-м.н., профессор ОСИПОВ Геннадий Семенович, Институт системного анализа РАН, заместитель директора по научной работе

Д.ф-м.н., профессор ВЕНИАМИНОВ Евгений Михайлович, Институт лингвистики Российского Государственного Гуманитарного Университета, заведующий Кафедрой математики, логики и интеллектуальных систем в гуманитарной сфере

Ведущая организация Федеральное государственное автономное

образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)».

Защита состоится 25 июня 2015 г. в 13:00 на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр им. А.А.Дородницына Российской академии наук», расположенном по адресу: 119991, г.Москва, ул.Вавилова, Д. 40.

С диссертацией можно ознакомиться в библиотеке ФГБУН «ВЦ РАН» а также на сайте http://vwwv.ccas.ru/.

Автореферат разослан ¿-?- 2015 года.

Ученый секретарь

диссертационного совета Д 002.017.02 д.ф-м.н., профессор

В.В.Рязанов

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

Проблема эмпирической индукции, сформулированная, в частности, как задача обучения на прецедентах, хорошо известна специалистам, характеризуется разнообразием методов ее решения и обширной литературой1. Однако, большинство имеющихся публикаций по этой тематике ориентированы на обработку числовых данных. Отдельной и сравнительно мало изученной областью является проблематика извлечения зависимостей из данных (описаний прецедентов), представленных нечисловыми объектами (множествами сущностей и отношениями на них - графами, цепочками символов конечного алфавита и т.п. реляционными структурами) и характеризуемых дополнительно числовыми значениями ряда существенных параметров. Поиск (извлечение из исходно заданных выборок прецедентов) зависимостей вида объект=>свой-СТВА на нечисловых объектах, характеризуемых в том числе и числовыми параметрами, представляет собою важную и актуальную область как теоретических, так и прикладных исследований в рамках интеллектуального анализа данных. Ее особый статус как самостоятельной сферы исследований в области искусственного интеллекта (так называемой проблематики phenomenal data mining) начал активно изучать J.McCarthy. Помимо нечисловой (неметрической) природы анализируемых зависимостей, весьма важной здесь оказывается возможность оперировать в том числе и с малыми (статистически незначимыми) выборками прецедентов (примеров-объектов, которые наделены целевыми свойствами, и контрпримеров-объектов, которые не обладают целевыми свойствами), причем оперировать так, чтобы иметь достаточные основания для принятия порождаемых результатов (извлекаемых из данных эмпири-

1 Так, например, только в монографии Кайберг Г. Вероятность и индуктивная логика. - М.: Прогресс, 1978. - 374 С. список литературы содержит более 1000 наименований.

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

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

Центральным объектом исследования является сформированная в диссертационной работе процедурная схема порождения зависимостей на прецедентах нечислового характера. Демонстрируется (в том числе - путем доказательства ряда строгих формальных утверждений) корректность такой схемы, построены оценки сложности вычислений входящих в нее комбинаторных задач.

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

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

Одним из наиболее известных и весьма детально развитых направлений в области разработки математических моделей и методов машинного обучения на прецедентах является проблематика так называемой Теории статистического обучения (statistical learning theory - SLT) - см., например, как уже ставшие классическими работы В.Н.Вапника иА.Я. Червоненкиса, так и ряд новейших достижений, в частности, результаты К.В.Воронцова по теории надежности обучения на прецедентах и др.. Ключевой проблемой Теории статистического обучения является формирование оценок вероятности ошибки при переносе (экстраполяции) построенных на обучающей выборке зависимостей на новые (не входящие в эту выборку) объекты. Однако в случае малых (статистически не значимых) выборок здесь на сегодняшний день имеется целый ряд еще не решенных вопросов.

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

В более широком контексте (т.е. в ситуации, когда для порождения зависимостей из данных используются не только метрические модели и алгоритмы - см., например, работы D.Michie, T.Mitchell, C.M.Bishop, P.Langley, M.Mohri и

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

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

- нейронные сети (см., например, работы Т.Кохонена, М.СИеНег, В.В.Круглова, Д.Рутковской и др.), где при поиске решения используется специальный вариант математических моделей многопараметрической нелинейной оптимизации, и

- генетические алгоритмы (см. работы Л.А.Гладкова, Д.Рутковской. Л.Шаги-кина и др.), где решение задач оптимизации при выборе наиболее подходящего класса зависимостей ищется моделированием локальных процедур случайного выбора, вариации и\или комбинирования анализируемых параметров по аналогии с механизмами естественного отбора в живой природе.

Однако, в анализе связей вида объект => свойства при поиске ответа на вопрос «почему возникает анализируемое явление?», предлагаемый нейронными сетями и генетическими алгоритмами вариант ответа вида «такой результат дал нам используемый алгоритм расчета» вряд ли сможет убедить независимого эксперта в наличии достаточных оснований для принятия полученных соответствующим инструментарием результатов.

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

б

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

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

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

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

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

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

7

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

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

а затем, если потребуется,

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

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

- представлен вариант реализации приближенного ДСМ-метода в режиме параллельных вычислений.

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

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

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

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

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

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

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

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

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

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

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

2. Идентифицирован и исследован специальный класс комбинаторных объектов (диаграмм взаимной вложимости классов эквивалентности различных

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

3. Процедурная конструкция ДСМ-метода расширена на новые типы данных (структурные описания нечисловых объектов, дополненные числовыми значениями существенных параметров).

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

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

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

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

Область исследования, согласно Паспорту специальности 05.13.17 - «Теоретические основы информатики»:

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

ю

- моделирование формирования эмпирического знания (п.7);

- исследование и когнитивное моделирование интеллекта, включая моделирование поведения, моделирование рассуждений различных типов (п. 8);

а также

- исследование информационных структур, разработка и анализ моделей информационных ... структур (п.2);

- исследование и разработка средств представления знаний (п.4).

В соответствии с обозначенными в формуле специальности 05.13.17 -«Теоретические основы информатики» направлениями, область данного исследования характеризуют в том числе и:

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

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

Достоверность и обоснованность. Апробация работы.

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

Основные положения и результаты работы докладывались и обсуждались на всероссийских и международных конференциях, конгрессах, чтениях и семинарах. В том числе - на Международных конференциях НТИ (ВИНИТИ РАН), Национальных конференциях с международным участием «Искусственный интеллект» (Российская ассоциация искусственного интеллекта), Конференциях и семинарах IEEE (США), Российско-британской конференции «Идеи Д.С. Милля об индукции и логике наук о человеке и обществе в когнитивных исследованиях и системах искусственного интеллекта» (РГГУ), научных семинарах ВИНИТИ РАН, МФТИ, ВМК МГУ, ВЦ РАН, ИПУ РАН и др..

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

По теме диссертации опубликовано 37 работ2 (см. Список публикаций), в том числе 17 - в изданиях из списка ВАК и 2 - в изданиях IEEE. Личный вклад автора. В диссертационной работе представлены только результаты, которые полученные лично автором: исследование проблематики восстановления зависимостей по прецедентам, формулировки и доказательства утверждений, постановки задач, методы и алгоритмы их решения. Из совместных публикаций в диссертацию включены лишь результаты автора. Структура и объем работы. Диссертационная работа состоит из Введения, 8 Глав (в т.ч. - 4 приложений к Разделу 8.4.2), Заключения, и Списка литературы (525 наименований). В работе - 20 рисунков и 18 таблиц (в т.ч. - таблиц с результатами экспериментов в приложениях). Общий объём работы - 440 стр. (в т.ч., 26 стр.- пояснения схемы работы ДСМ-ИАД на примерах в Главе 7, 123 стр. - обзор приложений в Главе 8, а также 34 стр. - Список литературы).

2 Без учета переводов и перепечаток.

Основные математические результаты работы представлены в Разделах 2.1 и 3.1, Главах 4 и 5, а также в Разделах 8.6 и 8.8. Сформулированы и доказаны более 100 строгих утверждений (теорем, лемм и др.), которые вместе с набором соответствующих алгоритмов характеризуют различные математические аспекты формализации комплекса эвристик эмпирической индукции.

Содержательные свойства используемых эвристик анализируются в Разделах 2.2,3.2 и 6.4. Подробный обзор приложений представлен в Главе 8.

Содержание работы.

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

Все основные задачи данного диссертационного исследования естественным образом вытекают из представленного в этой Главе обзора проблем, характерных для анализируемой области ИАД (в ее текущем состоянии).

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

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

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

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

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

1) множество (примеров) объектов, обладающих целевыми свойствами, и множество3 (контрпримеров) объектов, не обладающих целевыми свойствами,

2) новый объект (или же некоторое явным образом представленное множество таких объектов).

Требуется:

оценить наличие (или отсутствие) целевых свойств у нового объекта (новых объектов из заданного множества), т.е.

3) дать соответствующий прогноз (о наличии целевых свойств) и

4) предъявить достаточные основания (неоспоримые аргументы), которые позволяют принять этот прогноз.

3 В исходном состоянии, - возможно, пустое.

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

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

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

В Разделе 2.1 предложена схема формализации задачи обучения на прецедентах, выполненной алгебраическими средствами. В основе этой конструкции - анализ структурного сходства описаний прецедентов (примеров, характеризуемых наличием целевых свойств, и контрпримеров, характеризуемых их отсутствием), в котором понятие собственно сходства формализуется как бинарная алгебраическая операция. Каждая такая операция ® для всех элементов множества исходно заданных прецедентов обязана удовлетворять трем классическим условиям (порождать на множестве О. полурешетку): а®а = а а®Ь = Ь®а

(а®Ь)®с = а®(Ь®с) = а®Ь®с. На базе операции сходства ® определяется отношение сходства Я®, которое характеризуемое непустыми результатами вычисления этой операции: а Я®Ь (т.е. <а,Ь> е К®) имеет место тогда и только тогда, когда а®Ь ф I- 0 -1 (где 1-0-1 есть пустой объект того же типа, что а и Ь).

С помощью отношения R® на множестве описаний исходно заданных прецедентов «одного знака»4 строятся классы сходства вида:

Т(а) = {Ь | a R®b }.

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

a®b = v

выделяются соответствующие подклассы сформированных классов сходства:

Ev(a) = {b | а ® b = v}.

Показано, что справедливо: Утверждение 2.1.1

Каждый подкласс Ev(a) как подмножество исходно заданного множества прецедентов Q есть класс эквивалентности.

□

Также показано (Следствие 2.1.2) что пространство толерантности <£2,R®> может быть представлено в виде объединения всех порождаемых указанным выше способом классов эквивалентности ЕУ(С1,®). При этом каждый подобный класс эквивалентности может быть порожден специальным оператором Clos®: 2П —>• 2П, реализующим один и тот же набор действий при работе с различными типами описаний прецедентов:

имея объекты а,Ь, ... , с из Q а также их сходство v= ((a®b)®... ®с) найти все оставгииеся в Cl объекты d;, сходство которых с имеющимся v есть именно этот объект v.

Показано, что этот оператор Clos0 для любых О, О, и Oj из 2П удовлетворяет

известным условиям:

(i) О с Clos0(O)

(ii) О, s Oj влечет Clos0(Oi) с Clos®{Oj)

(iii) Clos&(Clos®(OJ) = Clos\0)

т.е. является оператором замыкания. С помощью оператора Clos® могут быть восстановлена структура покрытия классами эквивалентности описаний прецедентов как уже построенных классов сходства, так и всего заданного множества прецедентов £2.

4 Т.е. отдельно - на примерах и контрпримерах.

Таким образом демонстрируется, что задача извлечения зависимостей из имеющихся эмпирических данных может быть формализована как задача восстановления и последующего анализа взаимных пересечений классов эквивалентности £V(Î2,®) и Evf(Q,®), реконструируемых на структурных описаниях прецедентов противоположных знаков - примеров (£2+) и контрпримеров (Q.~). (Система отношений эквивалентности, возникающая в рассматриваемой ситуации, оказывается производной как от выбранного формального уточнения содержательных представлений о сходстве в виде той или иной конкретной алгебраической операции ®, так и от текущей структуры имеющейся выборки прецедентов Î2).

Задача прогнозирования свойств новых прецедентов, в таком контексте формализуется как задача формирования множеств Eq+(Cl,®) и Eq~(£2,®) всех классов эквивалентности £V(Q,®) и £V(Q,<8>) отдельно на каждом множестве прецедентов обоих знаков С2+ и Q" и последующей проверки вложимости описания нового прецедента Оо хотя бы в один из классов эквивалентности EvF(Cl,®) одного знака а (ае {+,-}) и, одновременно, невложимости ни в один из классов эквивалентности £^""(£2,®) противоположного знака (т.е. невложимости для всех Evia(Cl,®) е Ес^(П,Щ ). При этом вложимость описания нового объекта Оо в класс эквивалентности Еу:а(П,Щ, образованный прецедентами Ou,Он,... ,Ois, понимается следующим образом:

On ® On ® ... ® Ois = V/ = {Ou ® Ou ® ... ® Ois) ® Оо Определяя естественный порядок с (по вложимости подмножеств исходно заданного множества прецедентов Па) на множествах Eq'^Q,®) восстанавливаемых из исходной выборки классов эквивалентности EKa(Q,<3) каждого знака а (ае {+,-}), можно сформировать диаграммы частичного порядка:

Da = < Eqa(Q.,®), с >. Структура и взаимосвязи изучаемых диаграмм противоположного знака < Eqa(n,<8>), g > и < Eq~a (£2,®), s > определяют все основные особенности

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

Каждая из диаграмм вида < Еда(П,®), с > простыми действиями может быть дополнена до решетки-, достаточно расширить множество Еда(С1,®) следующим набором новых элементов - самим множеством С2а, всеми его одноэлементными подмножествами и пустым множеством 1.0л прецедентов из £2а. (Теоретико-множественный случай чуть позднее - в Разделе 4.2 Главы 4 - детально представлен Утверждениями 4.2.36-37). Там же показано (Примеры 4.2.38-39V что порождаемые рассматриваемым способом решетки в общем случае (следуя, например, Г.Гретцеру) не являются дистрибутивными, т.к. могут содержать в виде подрешеток так называемые Пентагон и диамант - известные решетки ЭТ5 и Мз.

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

В Разделе 2.3 представлено общее описание и наивная семантика ДСМ-метода. Приведены ссылки на построенную В.К.Финном, Д.П.Скворцовым и О.М.Аншаковым дедуктивную имитацию процедурной конструкции теоретико-множественной версии ДСМ-метода средствами специального класса

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

Глава 3 посвящена описанию процедурной структуры ДСМ-метода -формальному уточнению представленных в Главе 2 базовых элементов развиваемого подхода:

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

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

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

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

В Разделе 3.1 рассмотрены варианты математической формализации понятия сходства на различных типах данных (множествах, графах, цепочках символов конечного алфавита, векторах числовых значений параметров, ...),

5 См выше в Разделе 2.1 обсуждение достаточности оснований для принятия результатов обучения на прецедентах.

цель которых - порождение (в явной или неявной форме) соответствующего отношения толерантности (сходства).

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

Формализация сходства на векторах числовых параметров, дополняющих структурное описание прецедентов, выполняется по следующей схеме: представляется естественным предположить, что каждому структурному «носителю» изучаемых свойств анализируемых прецедентов соответствует область постоянства «физического механизма» обусловленности этих свойств в том числе и на принимающих числовые значения релевантных параметрах. Т.е. в множестве всех таких параметров существуют определенные подмножества релевантных целевому эффекту параметров, дополнительно характеризуемые релевантными эффекту числовыми значениями именно этих (выделенных) параметров. Односвязность области постоянства «физического механизма» причинности означает, что для любой пары С1 и С2 векторов числовых значений параметров, попавших в такую область, должна существовать возможность найти расположенный «между ними» вектор Сп, также попадающий в искомую область постоянства «механизма причинности». В свою очередь, понятие

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

- упорядочив по возрастанию (или по убыванию) числовых значений одного из параметров Л; («оси монотонности») множество С столбцов матрицы Xх исходно заданных прецедентов, можно выделить все подмножества С^ множества столбцов-прецедентов С*, на которых числовые значения, соответствующие каждому подмножеству И^ множества параметров К, изменяются сопутствующим образом (ко-монотонно). В такой ситуации естественно считать сходными все прецеденты (столбцы), попадающие в конкретный участок ко-монотонности изменения числовых значений релевантных параметров (определяемый соответствующей монотонной матрицей ц=ЛихСи). При этом одновременно берутся максимальные по вложению множества строк , обеспечивающих ко-монотонные изменения числовых значений в строках матрицы ц=ЛихСц на всем множестве образующих ее столбцов Сц. Фактически

- сходство пары прецедентов характеризуется здесь некоторым множеством столбцов-прецедентов, располагающимся между этими (проверяемыми на сходство) столбцами в смысле упорядочения значений одного из параметров (строк исходной матрицы-универсума Xх) и выделения содержащей по крайней мере две строки м-матрицы в Л™, вдоль строк которой числовые значения релевантных параметров между сходными столбцами изменяются сопутствующим образом (ко-монотонно). Классы эквивалентности исходных прецедентов будут характеризоваться здесь максимальными по вложению (в универсуме А") множествами столбцов каждой такой м-матрицы.

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

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

- затем на множествах м-матриц (порожденных в исходном универсуме Л") строится бинарная операция -Н* покомпонентной склейки7. Имеет место: Лемма 3.1.2.11

На множестве цСХ") всех м-матриц исходно заданного универсума Л" операция -РЬ удовлетворяет условиям коммутативности и ассоциативности.

□

Однако, приведен Пример 3.1.2.17. демонстрирующий, что на произвольных подмножествах из ц(Ата) операция -Н* не является идемпотентной. Тем не менее, если, стартовав с одно-столбцовых подматриц8 матрицы-универсума

, (индуктивно) формировать специальное подмножество /)от(Л^) с порождая новые элементы Оот(Ха) применением операции -Н* только к уже имеющимся в Оот{Хх) элементам, то для Оот{Хх) операция А* удовлетворяет и условию идемпотентности. Т.е. имеет место (определяющая корректность уточнения сходства на множестве Оот(Ха) посредством операции А»): Георема 3.1.2.15

Алгебра р = <£>о/и(Х),-Н*> есть нижняя полурешетка.

□

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

' В таком случае результат операции - пустое множество м-матриц.

'Каждая м-матрица из первого множества с каждой м-матрицей из второго.

! Т.е., фактически, с описаний исходных объектов-прецедентов.

гии и абдуктивного объяснения), используемого в рамках формируемой формализации эмпирической индукции, обсуждаются в Разделе 3.2.2. Общие свойства правил правдоподобного вывода ДСМ-метода (условия их применимости, рациональность, инвариантность процедурного ядра при работе с различными типами данных и др.) анализируются в Разделе 3.2.3. Явный вид решающих предикатов и собственно правил правдоподобного вывода (в том числе - для операций с теоретико-множественными и числовыми данными) подробно представлен к Разделах 3.3.1-3. Показано, как предложенная в Разделе 2.1 базовая процедурная схема формализации задачи эмпирической индукции алгебраическими средствами может быть описана однозначно интерпретируемыми логико-математическими средствами представленной в Разделе 3.2.1 системы логических языков. Таким образом обеспечены возможности для обоснования корректности предлагаемой алгебраической формализации рассматриваемой версии задачи обучения на прецедентах в том числе и путем построения (средствами соответствующих формальных теорий см. выше - Раздел 2.3) проблемно-ориентированной дедуктивной имитации.

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

В Главе 4 анализ комбинаторных свойств диаграмм вложимости классов эквивалентности начинается с изучения теоретико-множественного случая описания прецедентов. Исходные данные: алфавит и={а1,а2,... ,ап}- универсум образующих, а £2 = {Ои Ог,... , О™} с 2и\0 - множество объектов - слов (т.е. непустых множеств образующих), построенных над универсумом и. Операция сходства ® пары слов О-, и 0\ определяется как их теоретико-множественное пересечение п (выдает общее для этих слов подмножество образующих алфавита и). На подмножествах алфавита и и множества всех слов £2 определяются два отображения:

5 : 2П 2и и g■.2v->2n , такие, что: « каждому подмножеству слов из О сопоставляет общее для них множество букв из и, а£ каждому подмножеству букв из и сопоставляет подмножество слов из £2, в которые все эти буквы входят одновременно. Показано, что 5 и ^ на и и П представляют собою соответствия Галуа, а их произведения и (до) порождают соответствующие замыкания Галуа. (Таким образом оператор замыкания СШт(0), введенный ранее в Разделе 2.1, уточняется здесь до оператора g(s(0)) — замыкания Галуа на множестве слов £2).

Показано, что для каждой задачи КлЭкв(1],С1,Щ о порождении всех классов эквивалентности прецедентов из О может быть сформулирована двойственная ей задача АлЭкв(и*,£2\®), где каждой букве (образующей) из и сопоставляется соответствующее слово из £2", в свою очередь перечисляющее все слова из исходного множества прецедентов £2, в которые входит эта буква, а двойственный алфавит и* кодирует своими образующими все слова из £2. Взаимосвязи прямой и двойственной задач о порождении рассматриваемых нами классов эквивалентности демонстрирует Теорема 4.2.5

В множестве £д(и,£2,®) классов эквивалентности для задачи КлЭкв(1]£1,Щ элемент, содержащий ровно к штук прецедентов из £2, существует тогда и только тогда, когда в двойственном множестве классов для задачи

ЛлЭкв(1Г,£2\®) существует такой элемент, который сформирован ровно к образующими из двойственного алфавита и*.

□

В соответствии со Следствием 4.2.6 и Леммой 4.2.7 аналогичное утверждение верно и при соотнесении классов £#(1Г,£2",®) и £<7(11,£2,®). Описанный эффект имеет прямые аналогии с эффектами двойственности в линейном программировании и позволяет упростить доказательства ряда утверждений о вычислительной сложности переборных задач, связанных с формированием рассматриваемых диаграмм вложимости классов эквивалентности.

Далее в Главе 4 сформулирован и доказан комплекс утверждений, которые определяют вычислительную сложность основных комбинаторных задач,

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

Задача о числе классов эквивалентности, порождаемых на исходных множествах и и £2, принадлежит классу #РС - т.е. перечислительно полна.

□

Таким образом, число порождаемых классов эквивалентности растет экспоненциально быстро с увеличением характерных размеров исходных данных. Далее показано (Теоремы 4.2.12-13 и Следствия 4.2.14-19). что обе границы диаграмм Ва рассматриваемого здесь типа порождаются процедурами полиномиальной вычислительной сложности.

Сводимостью задачи о выполнимости произвольной булевской функции показано (в т.ч. - доказательством ряда промежуточных утверждений - Лемм 4.2.21-26 и Следствия 4.2.27). что имеют место следующие два утверждения: Теорема 4.2.20

Задача о наличии класса эквивалентности, который порождается ровно заданным числом образующих исходного алфавита II, принадлежит классу АТРС -№>-полных переборных задач. Следствие 4.2.28

Задача о классе эквивалентности, определяемая условием Теоремы 4.2.20. принадлежит также и классу #РС перечислительно полных задач.

□

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

рактерных размеров множеств U и £2). Далее (с учетом Теоремы 4.2.S о двойственности) аналогичные результаты (о принадлежности тем же классам комбинаторно трудных задач) доказаны и для задачи о поиске класса эквивалентности, который сформирован ровно заданным числом прецедентов из исходного множества £2: Следствие 4.2.29

Задача о наличии класса эквивалентности, который сформирован ровно заданным числом прецедентов из исходного множества £2 , принадлежит классам

NPC (iW-полных) и #РС перечислительно полных переборных задач.

□

При переходе к другим (рассмотренным в Разделе 3.1) типам данных наследуется большинство полученных для теоретико-множественного случая экспоненциально быстро растущих оценок сложности вычислений. Так для мультимножеств (как показывает Следствие 4.3.5) сохраняются результаты, установленные Теоремами 4.2.5, 4.2.10, 4.2.12-13, 4.2.20 и 4.2.35 (включая соответствующие Леммы и Следствия).

Далее доказана принадлежность классам NPC и #РС аналогичных задач о классах эквивалентности, содержащих заданное число прецедентов, и о числе классов эквивалентности при описании исходных прецедентов как цепочками символов конечного алфавита (Следствие 4.3.6), так и графами (Следствие4.3.7).

Для представления исходных данных векторами числовых значений параметров показано, что задача о поиске какого-либо класса эквивалентности исходно заданных прецедентов полиномиально разрешима (Теорема 4.3.10), однако задача о числе таких классов (как и в ранее рассмотренных случаях) находится в классе #РС - перечислительно полных задач (Теорема 4.3.11). Тем не менее, в случае отсутствия совпадающих элементов в строках исходной матрицы-универсума А^1 с ростом ее размеров число классов эквивалентности растет полиномиально быстро (Теорема 4.3.12). Также, как и ранее, задачи о поиске границ множества классов эквивалентности и существовании классов эквивалентности, образованных не более\не менее чем заданным числом прецеден-

tob, оказываются полиномиально разрешимыми (Теоремы 4.2.14, 16, 18 и Следствия 4.3.15.17). Наконец, как и в случаях обработки ранее уже рассмотренных типов данных, доказана Теорема 4.3.19

Задача о существовании класса эквивалентности, который образован ровно заданным количеством описываемых числовыми векторами исходных прецедентов, принадлежит классу ЛГР-полных переборных задач - NPC.

О

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

В Главе 5 обсуждается разработанный автором диссертационного исследования метод дискретной оптимизации перебора вариантов при восстановлении (по исходно заданной выборке) диаграмм вложимости классов эквивалентности прецедентов, описываемых множествами признаков (теоретико-множественный случай). Вводится понятия базиса замыканий Галуа - замыканий (вида s(?(a)) - см. ранее, Раздел 4.2) всех однобуквенных подмножеств алфавита U. Сформулирован критерий представимости каждого элемента диаграммы вложимости соответствующими ему элементами такого базиса: Теорема 5.2.3

Множество образующих и = {аь а2, ... , at-} исходного алфавита ¿/порождает некоторый класс эквивалентности £"„(П,п) на исходном множестве прецедентов Q, тогда и только тогда, когда для входящих в базис для и соответствующих замыканий Галуа [{ai}]t/,n: i

U [(ai)] uxi ={а,, а2,... ,ак}.

/•I

□

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

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

Каркас любого псевдо-дерева (как и каркас всей восстанавливаемой по исходным данным диаграммы) порождается полиномиально сложной процедурой. Утверждение 5.2.12

Каркас однозначным образом сопоставлен соответствующему псевдо-дереву.

□

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

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

Предложен алгоритм НПС9, обеспечивающий целенаправленный исчерпывающий перебор всех элементов соответствующих диаграмм вложимости классов эквивалентности. Корректность алгоритма НПС демонстрирует Утверждение 5.3.1

Алгоритм НПС обеспечивает полноту и точностью при восстановлении диаграммы вложимости сходств, порождаемых на исходных множествах и и £2 :

1) порождает все принадлежащие ей сходства (с указанием для каждого из них всех ближайших к нему по вложимости элементов восстанавливаемой диаграммы), и

2) не порождает никаких других (не являющихся элементами восстанавливаемого множества сходств) объектов.

□

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

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

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

'Алгоритм Направленного Перебора Сходств (порождающих восстанавливаемые классы эквивалентности).

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

В Разделе 5.4 представлено строгое обоснование корректности разработанного метода последовательных приближений (так называемого приближенного ДСМ-метода). Описан механизм управления порождением (в том числе - в режиме параллельных вычислений) последовательных приближений заданной точности для восстанавливаемых диаграмм. Механизма управления точностью основан на утверждении о представимости восстанавливаемых диаграмм вложимости объединениями каркасов всех допустимых рангов10:

Теорема 5.4.2.

Диаграмма Б(и,Я) взаимной вложимости сходств (классов эквивалентности), порожденных на множестве прецедентов П , представима как объединение

П

= и

7=1

каркасов ОК0)о замыканий всех возможных рангов / на алфавите и (|1Г| = п).

□

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

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

30

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

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

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

В Главе 8 представлены: 1) обзор примеров приложений разработанных в диссертационной работе математических конструкций (Разделы 8.6.1-2) при решении ряда задач управ-

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

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

• анализе свойств физиологически активных веществ (Разделы 8.2.1 -3);

• автоматической обработке больших коллекций полнотекстовых документов (Разделы 8.3.1-4);

• геологическом прогнозировании нефтегазоносности территорий (Разделы 8.4.1-2);

• предконкурсной экспертизе сложных технических проектов (Раздел 8.7)

и др..

Основные математические результаты работы (более 100 сформулированных и доказанных утверждений - теорем, лемм, следствий и др.) представлены в Разделах 2.1 и 3.1, Главах 4 и 5, а также Разделах 8.6.1-2 и 8.8.

Обсуждению содержательных характеристик формализуемых эвристик (индуктивного обучения, выводов по аналогии и абдуктивного объяснения) посвящены Разделы 2.2,3.2 и 6.4. Подробный обзор приложений представлен в Главе 8.

Основные результаты и выводы

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

Получены следующие результаты:

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

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

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

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

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

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

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

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

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

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

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

Публикации по теме диссертации в изданиях из списка ВАК:

1. Забежайло М.И. Ненаследуемость эмпирического противоречия в ДСМ-методе и немонотонные рассуждения // Научно-техническая информация, Сер.2. - 1984. -N11.-0.14-17.

2. Забежайло М.И К проблеме расширения ДСМ-метода автоматического порождения гипотез на данные с числовыми параметрами // Научно-техническая информация. Сер.2.- 1992.-N11.-C.H-21

3. Забежайло М.И. К проблеме расширения ДСМ-метода автоматического порождения гипотез на данные с числовыми параметрами II // Научно-техническая информация. Сер.2. - 1993. - N2. - С.6-16.

4. Забежайло М.И. Формальные модели рассуждений в принятии решений: приложения ДСМ-метода в системах интеллектуального управления и автоматизации научных исследований И Научно-техническая информация, Сер.2. - 1996. - N5-6. - С.20-32.

5. Забежайло М.И. О комбинаторной природе одной задачи оптимизации // Научно-техническая информация, Сер.2. - 1996. - N1. - С.19-27.

6. Забежайло М.И. К проблеме формализации метода геологических аналогий. // Известия РАН. Сер. Теория и системы управления. - 1997. -N2,- С.151-164.

7. Забежайло М.И., Емеленко М.Н., Липчинский Е.А., Максин М.В. К пониманию термина "прикладная семиотика" // Научно-техническая информация, Сер.2 -1998.-N1.-С. 11-18.

8. Забежайло М.И. К проблеме автоматического понимания полнотекстовых документов в информационном поиске. // Известия РАН. Сер. Теория и системы управления. - 1998. - N5. - С.167-176.

9. Забежайло М.И. Интеллектуальный анализ данных — новое направление развития информационных технологий // Научно-техническая информация, Сер. 2.- 1998. -№8.-С. 6-17.

10. Забежайло М.И. О функциональности отношения причинности, используемого в ДСМ-рассуждениях // Научно-техническая информация. Сер.2. - 2013. — N7.-С.1-7.

11. Забежайло М.И. О некоторых возможностях управления перебором в ДСМ-ме-тоде//Искусственный интеллект и принятие решений. —2014. — Часть I: № 1, С.95 -110.

12. Забежайло М.И. О некоторых возможностях управления перебором в ДСМ-ме-тоде // Искусственный интеллект и принятие решений. - 2014. — Часть II: № 3, С.З -21.

13. Забежайло М.И., Синякова Е.В. К вопросу об «интеллектуальности» интеллектуального анализа данных // Научно-техническая информация. Сер. 2. - 2014. - № 3. - С. 1-9.

14. Забежайло М.И. Приближенный ДСМ-метода на примерах И Научно-техническая информация. Сер.2.-2014.-№10, С. 1-12.

15. Забежайло М.И. К вопросу о достаточности оснований для принятия результатов интеллектуального анализа данных средствами ДСМ-метода // Научно-техническая информация. Сер.2. - 2015. -№1. - С. 1-9.

16. Забежайло М.И. О некоторых оценках сложности вычислений в ДСМ-рассужде-ниях // Искусственный интеллект и принятие решений. - 2015. - Часть I: №1. - С. 3-17.

17. Забежайло М.И. О некоторых оценках сложности вычислений в ДСМ-рассуждениях // Искусственный интеллект и принятие решений. - 2015. - Часть II: №2 (в печати).

Другие публикации по теме диссертации:

18. Zabezhailo M.I. et al. Reasoning Models for Decision Making: Applications of JSM-Method for Intelligent Control Systems//Architectures for Semiotic Modeling and Situation Analysis in Large Complex Systems. - Proc. of the Workshop of 1 Oth (1995) IEEE Symp. on Intelligent Control (Eds.: J.Albus, A.Meystel, D.Pospelov, T.Reader). - 27 -29 August 1995, Monterey, CA../ AdRem, Inc., 1995. - Pp. 99-108.

19. Zabezhailo M.I. To the Scalable Technology of Automated Document Understanding Based on Quasi-Axiomatic Theories.// Proc. 1997-th International Conference on Intelligent Systems and Semiotics "A Learning Perspective" - ISAS'97 (NIST, Gaithersburg, MD, September 22-25, 1997). - NIST Special Publications. - N918. - 1997. - Pp.100102.

20. Забежайло М.И., Финн B.K., Козлова С.П., Катамадзе Т.Г., Авидон В.В., Рабин-ков А.А. Об одном методе автоматического формирования гипотез и его программной реализации // НТИ, Сер.2. - 1982. - N4. - С.20-26.

21. Забежайло М.И., Финн В.К., Авидон В.В., Катамадзе Т.Г., Блинова В.Г., Бодягин Д.А., Рабинков А.А. Об экспериментах с базой данных с неполной информацией посредством ДСМ-метода автоматического порождения гипотез // НТИ, Сер.2. -1983. - N2. - С.28-32.

22. Забежайло М.И., Ивашко В.Г., Кузнецов С.О., Михеенкова М.А., Хазановский К.П., Аншаков О.М. Алгоритмические и программные средства ДСМ-метода автоматического порождения гипотез. //НТИ, Сер.2. - 1987. -N10. - С.1-13.

23. Забежайло М. И. Новые информационные технологии и системы НТИ // НТИ, Сер. 2. — 1990. — №5. — С. 2—9.

24. Забежайло М.И. Некоторые тенденции в развитии интеллектуальных систем // Программные продукты и системы. - 1990. -N 4. - С.86-94.

25. Забежайло М.И. Интеллектуальные системы и задача восстановления эмпирических зависимостей структурно-числового характера // Итоги науки и техники. Сер." Информатика". Т. 15 "Интеллектуальные информационные системы" - М: ВИНИТИ.-1991.-С. 102-114.

26. Забежайло М.И. Новые информационные технологии в научных исследованиях и технологических разработках // НТИ. Сер. 2.- 1992.- № 6.-С.1-11.

27. Забежайло М.И. Интеллектуальные системы: на пути к новым поколениям. // Новости искусственного интеллекта. N1, 1992. - С.8-24.

28. Забежайло М.И. (Zabezhailo M.I.) The extension of the JSM-method: plausible reasoning dealing with numeric data // Новости Искусственного Интеллекта. Специаль-

ный выпуск: Международная конференция по искусственному интеллекту "Восток-Запад - 93" (Artificial Intelligence News. Special issue: EWAIC-93, Moscow, 79 Sept. 1993). 1993.

29. Забежайло М.И. Формальные модели рассуждений в принятии решений: приложения ДСМ-метода в системах интеллектуального управления и автоматизации научных исследований //НТИ, Сер.2. - 1996. - N5-6. - С.20-32.

30. Забежайло М.И. О комбинаторной природе одной задачи оптимизации // НТИ, Сер.2,- 1996,-N1.-С.19-27.

31. Забежайло М.И., Емеленко М.Н., Липчинский Е.А., Максин М.В. К разработке платформенно-независимой версии программной системы, реализующей ДСМ-метод автоматического порождения гипотез// Труды 3-й Международной конференции "НТИ-'97: Информационные ресурсы, интеграция, технологии" (Москва, 26-28 ноября 1997 г.), М.: ВИНИТИ, Часть 1, С.91-93.

32. Забежайло М.И. Информационный поиск в полнотекстовых документах: некоторые проблемы и перспективы. //Новости искусственного интеллекта. - 1998. -N.I.- С. 24-59

33. Забежайло М.И. Data Mining & Knowledge Discovery in Data Bases: предметная область, задачи, методы и инструменты // Труды 6-ой национальной конференции по искусственному интеллекту с международным участием. - Пущино. - 1998. -Том 1. - С. 592-600.

34. Zabezhailo M.I., Finn V.K., Leybov A.E.,Melnikov N.I., Pankratova E.S. CBR-tech-nology in the chemical safety control // Proc. EWCBR'94 (France, November 7-11, 1994).- 1994.

35. Zabezhailo M.I., Finn V.K. Intelligent Information Systems. - International Forum on Information and Documentation (FID, The Hague, Netherlands). - 1996. - V21. - N2. -Pp.21-31.

36. Zabezhailo M.I. On the Application of the Semiotic Modelling Technique in the Problem of Clearing Payments Control.// Proc. 12th European Conference on Artificial Intelligence (ECAI'96, Budapest, 11-16 August, 1996). - Workshop N30 "Applied Semiotics". Pp. 17-21.

37. Zabezhailo M.I., Finn V.K., Gergely T. JSM-method as an Instrument for Semiotic Modelling: Application to Geological Forecasting.// Proc. 12th European Conference on Artificial Intelligence (ECAI'96, Budapest, 11-16 August, 1996). - Workshop N30 "Applied Semiotics". Pp. 13-16.