Введение к работе
Актуальность темы. Д.А. Поспелов и В.Н. Захаров относили к интеллектуальным методам и технологиям управления в том числе мягкие вычисления, распределенный искусственный интеллект и методы и технологии инженерии знаний и рассуждений на знаниях. Вероятностные графические модели (ВГМ) как область искусственного интеллекта (ИИ) можно отнести к выделенным категориям. Для моделей этого класса общим является локализация вычислений, основанная на принципе декомпозиции и предположениях об условной независимости. ВГМ представляют собой граф, узлам которого приписаны случайные элементы, а ребра определенным образом отображают зависимости между ними.
Алгебраические байесовские сети (ABC), предложенные В.И. Городецким, представляют собой логико-вероятностную графическую модель, опирающуюся на логико-вероятностный подход в интерпретации, выдвинутой Н. Нильссоном для теоретических основ и приложений ИИ. Ключевым отличием ABC от других моделей является представление неопределенности через интервальные оценки вероятности истинности пропозициональных формул. Проблема представления неопределенности знаний освещалась в работах В.Н. Вагина, Ю.Р. Валькмана, А.С. Нариньяни, Г.С. Осипова, Д.А. Поспелова, В.В. Тарасова, Н.Г. Ярушкиной, A. Dempster, D. Dubois, J. Pearl, R. Pagin, J. Halpern, K. Korb, H. Prade, G. Shafer, L. Zadeh и многих других.
Теория ВГМ нуждается в моделях, методах и алгоритмах машинного (автоматического) обучения1, в частности, автоматического синтеза глобальных структур таких моделей и автоматического построения оценок их параметров по исходным данным. Комплексная проблема глобального обучения ABC заключается в алгоритмизации синтеза глобальных структур ABC. Среди них выделяют первичную структуру, представляющую собой набор максимальных по включению фрагментов знаний (ФЗ), и вторичную структуру, в данной работе рассматриваемую как граф, построенный над элементами первичной структуры и обладающий особым свойством магистральной связности.
Одной из проблем машинного обучения глобальных структур ABC (глобального обучения ABC) является синтез по заданной первичной структуре ABC ее вторичной структуры, которая необходима для осуществления алгоритмов апостериорного логико-вероятностного вывода, эффективного поддержания глобальной непротиворечивости такой сети и визуализации ABC в виде графа. Проблема синтеза вторичной структуры ABC по заданной первичной структуре является актуальной и нерешенной.
Обоснование актуальности исследований также содержит формальную сторону: тема настоящего диссертационного исследования ассоциирована с пунктом 35 «Когнитивные системы и технологии, .. ., искусственный интеллект, ..., принятие решений при многих критериях» Программы фундаментальных научных исследований государственных академий наук на 2013-2020 годы (утверждена Распоряжением Правительства РФ от 03.12.2012 г. Ж- 2237-р) в части «теоретические и технологические основы, алгоритмическое обеспечение и программный инструментарий вероятностных графических моделей, логико-вероятностных графических моделей, ... ».
1 Машинное обучение — одна из областей ИИ, связанная с разработкой моделей и алгоритмов, позволяющих вычислительной машине делать предсказания, основываясь на примерах или предыдущем опыте (Alpaydin Е. Introduction to Machine Learning. 2nd Ed. Cambridge, MS: The MIT Press, 2010. 537 p.)
Степень разработанности темы. В работах А.Л. Тулупьева в качестве вторичной структуры ABC рассматриваются деревья смежности, для которых были предложены алгоритмы глобального логико-вероятностного вывода и эффективного поддержания глобальной непротиворечивости. Также в них был предложен подход к устранению отдельных простых циклов графа смежности, и, совместно с соавторами (в первую очередь, с соискателем А.А. Фильченковым) — подход к синтезу множества минимальных графов смежности. А.В. Сироткин формализовал понятие магистральной связности как специфического свойства графов смежности. В.В. Опарин выдвинул идею одного из вариантов синтеза минимального графа смежности, сводящуюся к использованию жадного алгоритма.
Исследованиями по выявлению и устранению цикличности гиперграфов занимались В.В. Быкова, С. Beeri, G. Dirac, R. Pagin, M. Goodman, D. Maier, A. Mendelzon, N. Robertson, D. Rose, P. Seymour, R. Tarjan, J. Ullman, M. Yannakakis и многие другие. Так, известны алгоритмы выявления цикличности гиперграфа и классы алгоритмов ее устранения, которые мотивировали часть подходов к решению задач диссертационного исследования.
Объект исследования — система глобальных структур ABC как специальных графов и гиперграфов. Предмет исследования — вторичная структура ABC, формализуемая как граф смежности, и машинное обучение этой структуры посредством синтеза графов смежности.
Цель диссертационного исследования — решить одну из проблем алгоритмизации глобального обучения ABC, а именно — проблему синтеза вторичной структуры ABC по ее первичной структуре. Достижение цели осуществляется за счет решения совокупности следующих задач:
1) выявить критерии существования связной вторичной структуры и, отдельно,
ацикличной вторичной структуры над заданной первичной структурой ABC по кос
венным признакам (т.е. не предполагающим непосредственное построение вторичной
структуры);
-
разработать методы преобразования первичной структуры ABC к структуре, над которой существует ацикличная вторичная структура, и указать факторы, ограничивающие применимость таких методов;
-
выявить свойства минимальных по числу ребер графов смежности, которые могут выступать в качестве вторичной структуры ABC и существующие над произвольной первичной структурой, описать структуру такого множества и вывести формулы для расчета мощности множества минимальных графов смежности и числа ребер такого графа;
-
разработать систему алгоритмов синтеза множества минимальных графов смежности, а также подмножеств этого множества, адаптированных к таким особенностям алгоритмов логико-вероятностного вывода в теории ABC, как число шагов в пропага-ции свидетельства между узлами графа и распараллеливаемость этой пропагации;
-
реализовать описанные алгоритмы синтеза вторичной структуры ABC, а также анализа и преобразования первичной структуры в прототипе комплекса программ для вычислительных экспериментов.
Методология и методы исследования. Работа носит теоретический характер и выполнена преимущественно в рамках теории конечных графов, в том числе теории гиперграфов и ее приложений в информатике. Работа опирается на методологию дедуктивного и индуктивного обоснования утверждений в отношении специальным об-
разом формализованных объектов и сведения новых нерешенных задач к известным задачам, уже получившим решение. Кроме того, используются объекты и методы алгебры, теории вероятностей и вероятностной логики, теории вычислительной сложности, комбинаторики, теории множеств, в частности, теории частично упорядоченных множеств. В программно-технологической части исследования используются принципы структурного и объектно-ориентированного программирования и Java-технологии.
Научная новизна. Все результаты, выдвигаемые на защиту, являются новыми.
Предложены система алгоритмов синтеза глобальных структур ABC, алгоритмы выявления существования связного графа смежности и ацикличного графа смежности над данной первичной структурой ABC, алгоритмы преобразования первичной структуры к такой, над которой существует ацикличный граф смежности, алгоритмы синтеза множества минимальных графов смежности, а также синтеза особых его подмножеств, доказана корректность указанных алгоритмов.
Дана оценка мощности множества минимальных графов смежности, доказана корректность матроидного представления семейства магистрально связных графов с заданным над ними отношением независимости, доказано совпадение множеств минимальных и нередуцируемых графов смежности. Предложено описание минимального графа смежности, допускающее как синтез такого графа, так и синтез всего множества таких графов, а также систематизация глобальных структур ABC на основе формализации через графы и гиперграфы. Доказано существование преобразования первичной структуры ABC к первичной структуре, над которой существует дерево смежности, как известными прежде, так и предложенными в диссертационном исследовании методами.
Разработаны программные компоненты, дополняющие существующий комплекс программ для работы с ABC и реализующие алгоритмы синтеза вторичной структуры ABC, алгоритмы выявления существования дерева смежности над заданной первичной структурой ABC и ее преобразования к структуре допускающей, над которой существует дерево смежности.
Степень достоверности и апробация результатов. Достоверность полученных в диссертационном исследовании результатов обоснована корректностью применения методов соответствующих математических дисциплин. Существенным аргументом в пользу достоверности является работоспособность прототипа комплекса программ, пополненного реализацией приведенных в теоретической части алгоритмах.
Результаты диссертационного исследования докладывались и обсуждались на следующих научных мероприятиях: 1) Научная сессия НИЯУ МИФИ-2011 (1-5 февраля 2011 г., Москва); 2) VI Междунар. науч.-практ. конф-я «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (16-19 мая 2011 г., Коломна); 3) VII С.-Петерб. межрегион, конф-я «Информационная безопасность регионов России (ИВРР-2011)» (26-28 октября 2011 г., С.-Петерб); 4) VI Междунар. науч.-практ. конф-я «Современные информационные технологии и 1Т-образование» (12-14 декабря 2011 г., Москва); 5) Научная сессия НИЯУ МИФИ-2012 (30 января-4 февраля 2012 г., Москва); 6) Всеросс. науч. конф-я по проблемам информатики СПИСОК-2012 (25-27 апреля 2012 г., С.-Петерб.); 7) VI Междунар. науч.-технич. конф-я молодых специалистов, аспирантов и студентов «Математическое и компьютерное моделирование естественнонаучных и социальных проблем» (21-24 мая 2012 г., Пенза); 8) XV Междунар. конф-я по мягким вычислениям и измерениям (SCM'2012) (25-27 июня 2012 г., С.-Петерб.); 9) 1-й Междунар. симпозиум «Гибридные и синергетические интеллекту-
альные системы: теория и практика» (29 июня - 2 июля 2012 г., Калининград); 10) The 6th Russian Summer School in Information Retrieval (RuSSIR 2012) (August 6-10, 2012. Yaroslavl, Russia); 11) 35-я конф-я молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы» (19-25 августа 2012 г., Петрозаводск); 12) 5-я росс, мультиконф-я по проблемам управления/конф-я «Информационные технологии в управлении-2012» (ИТУ-2012) (9-11 октября 2012 г., С.-Петерб.); 13) Юбилейная XIII С.-Петерб. междунар. конф-я «Региональная информатика (РИ-2012)» (24-26 октября 2012 г., С.-Петерб.); 14) Междунар. (44-я Всеросс.) молодежная школа-конф-я «Современные проблемы информатики-2013) (27 января - 2 февраля 2013 г., Екатеринбург); 15) Научная сессия НИЯУ МИФИ-2013 (1-6 февраля 2013 г., Москва); 16) Всеросс. науч. конф-я по проблемам информатики СПИСОК-2013 (23-26 апреля 2013 г., С.-Петерб.). Кроме того, результаты диссертационного исследования докладывались на Санкт-Петербургском городском научном семинаре «Информатика и компьютерные технологии» в 2013 году и на заседании Ученого совета СПИИРАН в 2013 году.
Исследования по тематике диссертации были поддержаны: 1) грантом РФФИ, проект Ж- 09-01-00861-а «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью», 2) грантом РФФИ, проект Ж- 12-01-00945-а «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», 3) грантом Правительства Санкт-Петербурга для победителей конкурса грантов Санкт-Петербурга для студентов, аспирантов, молодых ученых, молодых кандидатов наук 2010 г., Ж- 2.1/03-06/018, 4) грантом РФФИ, проект 12-01-31202 мол_а «Развитие теории графов смежности для автоматического обучения баз знаний с неопределенностью на основе алгебраических байесовских сетей», 5) грантом РФФИ, проект 12-01-16030-моб_з_рос «Косвенные признаки цикличности вторичной структуры алгебраической байесовской сети» для представления на научном мероприятии «1-й Международный симпозиум "Гибридные и синергетические интеллектуальные системы: теория и практика (ГиСИС'12)"». Соискатель является руководителем проектов Ж-Ж- 3-5.
Теоретическая и практическая значимость исследования. Результаты диссертационного исследования развивают теоретическую и технологическую базу для решения задач в системах поддержки принятия решений, в частности для представления и обработки неточной, неполной, нечисловой информации о соотношении вероятностей истинности утверждений, на основе которых принимаются решения, и для комбинирования или агрегирования такой информации из источников, степени доверия к которым могут различаться или быть неизвестными. Кроме того, полученные результаты в отношении минимальных по числу ребер графов смежности имеют теоретическую значимость для раздела теории графов, связанного с графами смежности. Результаты исследований вошли в научные отчеты СПИИРАНа по следующим НИР: «Логико-вероятностный подход и его обобщения в моделировании, обработке и обучении баз фрагментов знаний с неопределенностью в интеллектуальных системах», шифр BNet-2008, номер государственной регистрации 01200852455, «Методология построения интеллектуальных систем поддержки принятия решений на основе баз фрагментов знаний с вероятностной неопределенностью», номер государственной регистрации 01200963057, «Развитие теории алгебраических байесовских сетей и родственных им логико-вероятностных графических моделей систем знаний с неопределенностью», номер государственной регистрации 01201259408.
Полученные результаты могут использоваться в учебном процессе для студентов, специализирующихся в области информатики и родственных ей дисциплин. В частности, результаты были включены в программы спецкурса «Теория байесовских сетей» и (частично) спецкурса «СУБД, интерфейс и интеллектуальные модели в комплексах программ» математико-механического факультета СПбГУ.
Публикации. По теме диссертации было сделано 58 публикаций и приравненных к ним научных работ, из них 22 статьи (из которых 6 единоличных) в изданиях из «Перечня рецензируемых научных журналов и изданий для опубликования основных научных результатов», утвержденного ВАК, 25 статей и докладов на научных конференциях (из которых 9 единоличных), 11 зарегистрированных программ ЭВМ и алгоритмов (3 — в РОСПАТВНТе и 8 — в ОФЭРНиО/ЦИТиСе). В дополнение к перечисленному материалы диссертационного исследования нашли отражение в 15 тезисах научных конференций и 5 прошедших госрегистрацию в ЦИТиС научных отчетах.
Личный вклад А.А. Фильченкова в ключевых публикациях с соавторами кратко характеризуется следующим образом: В [1] ему принадлежит доказательство теоремы о матроидном представлении, а также теорема о совпадении множеств минимальных и нередуцируемых графов смежности и доказательство ее корректность на основе теоремы о матроидном представлении; в [2] — формулировки и доказательства утверждений и лемм о свойствах торакса; в [3] — теорема о циклах в минимальных графах смежности и ее доказательство; в [5] — основные утверждения и леммы, их доказательство и доказательство теоремы о множестве минимальных графов смежности; в [10] — доказательство теоремы о совпадении множеств минимальных и нередуцируемых графов смежности, не основывающееся на корректности теоремы о матроидном представлении; в [19] — формулировка утверждений о связности первичной структуры и их доказательства; в [8] — описание задач глобального обучения ABC и подходов к их решению; в [9, 12] — алгоритмы выявления цикличности первичной структуры и доказательства их корректности; в [6] — формализация третичной структуры и описание ее свойств; в [11] — методы устранения циклов и доказательство их корректности; в [14] — моделирование процесса распространения свидетельств по графу смежности распространением свидетельств по родительскому графу над множеством непустых сепараторов; в [16] — новое, уточненное доказательство теоремы о циклах в минимальных графах смежности; в [18] — формулировки основных утверждений и идеи их доказательства, а также описание алгоритма и доказательство его корректности; в [21] — алгоритмы, а также доказательство их корректности; в [20] — представление первичной стурктуры ABC как гиперграфа и сведение задачи преобразования такой структуры к ациклической к задачам, решаемым методами графовой декомпозиции.
Более подробно личный вклад А.А. Фильченкова в совместных публикациях и приравненных к ним работах описан в тексте диссертации.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списков используемой литературы и иллюстраций. Нумерация разделов, рисунков, формул, структурных элементов текста ведется отдельно для каждой главы. Общий объем работы составляет 339 страниц. Список используемой литературы содержит 371 источник.
