Синтез графов смежности в машинном обучении глобальных структур алгебраических байесовских сетей

• Автор: Фильченков, Андрей Александрович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Санкт-Петербург
• Количество страниц: 339 с. : ил.

Глава 1. Структурный подход в моделировании знаний с неопределенностью
§1.1. Моделирование неопределенности знаний с помощью мер истинности
§ 1.2. Вероятностные графические модели в искусственном интеллекте
§ 1.3. Деревья смежности в представлении систем данных и знаний
§1.4. Проблемы машинного обучения в искусственном интеллекте
Выводы по главе
Глава 2. Основы теории алгебраических байесовских сетей
§ 2.1. Элементы логико-вероятностного подхода
§ 2.2. Системы графов и гиперграфов
§ 2.3. Фрагмент знаний АБС
§ 2.4. АБС и глобальный вывод в них
Выводы по главе
Глава 3. Глобальные структуры алгебраической байесовской сети
§3.1. Минимальные графы смежности
§ 3.2. Связность и ащикличность минимального графа смежности
§ 3.3. Структура множества минимальных графов смежности
§ 3.4. Машинное обучение графов смежности
Выводы по главе
Глава 4- Комплекс программ для вычислительных экспериментов
§ 4.1. Состав комплекса программ
§ 4.2. Основные элементы представления данных
§ 4.3. Реализация машинного обучения вторичной структуры АБС
§ 4.4. Руководство пользователя и примеры
Выводы по главе
Заключение
Литература
Список иллюстраций

Актуальность темы. Д.А. Поспелов и В.Н. Захаров относили к интеллектуальным методам и технологиям управления в том числе мягкие вычисления, распределенный искусственный интеллект и методы и технологии инженерии знаний и рассуждений на знаниях. Вероятностные графические модели (ВГМ) как область искусственного интеллекта (ИИ) можно отнести к выделенным категориям. Для моделей этого класса общим является локализация вычислений, основанная на принципе декомпозиции и предположениях об условной независимости. ВГМ представляют собой граф, узлам которого приписаны случайные элементы, а ребра определенным образом отображают зависимости между ними.
Алгебраические байесовские сети (АБС), предложенные В.И. Городецким, представляют собой логико-вероятностную графическую модель, опирающуюся на логико-вероятностный подход в интерпретации, выдвинутой Н. Нильссоном для теоретических основ и приложений ИИ. Ключевым отличием АБС является представление неопределенности, в том числе, через интервальные оценки вероятности истинности пропозициональных формул. Проблема представления неопределенности знаний освещалась в работах В.Н. Вагина, A.C. Нариньяни, Г.С. Осипова, Д.А. Поспелова, В.Б. Тарасова, Н.Г. Ярушкиной, A. Dempster, D. Dubois, J. Pearl, R. Fagin, J. Halpern, K. Korb, H. Prade, G. Shafer, L. Zadeh и многих других.
Теория ВГМ нуждается в моделях, методах и алгоритмах машинного (автоматического) обучения’, в частности, автоматического синтеза глобальных структур таких моделей и автоматического построения оценок их параметров по исходным данным. Комплексная проблема глобального обучения АБС заключается в алгоритмизации синтеза глобальных структур АБС. Среди них выделяют первичную структуру, представляющую собой набор максимальных по включению фрагментов знаний (ФЗ), и вторичную структуру, в данной работе рассматриваемую как граф, построенный над элементами первичной структуры и обладающий особым свойством магистральной связности.
Одной из проблем машинного обучения глобальных структур АБС (глобального обучения АБС) является синтез по заданной первичной структуре АБС ее вторичной структуры, которая необходима для осуществления алгоритмов апостериорного логико-вероятностного вывода, эффективного поддержания глобальной непротиворечивости такой сети и визуализации АБС в виде графа. Проблема синтеза вторичной структуры АБС по заданной первичной структуре является актуальной и нерешенной.
Обоснование актуальности исследований также содержит формальную сторону: тема настоящего диссертационного исследования ассоциирована с пунктом 35 «Когнитивные системы и технологии, ..., искусственный интеллект, ..., принятие решений при многих критериях» Программы фундаментальных научных исследований государственных академий наук на 2013-2020 годы (утверждена Распоряжением Правительства РФ от 03.12.2012 г. № 2237-р) в части «теоретические и технологические основы, алгоритмическое обеспечение и
1 Машинное обучение — одна из областей ИИ, связанная с разработкой моделей и алгоритмов, позволяющих вычислительной машине делать предсказания, основываясь на примерах или предыдущем опыте-[1-70] - - - - -- —

и на уровне всей сети, причем для всех возможных вариантов свидетельств [57,58,62,65-67,70,71,86].
Работа с интервальным оценками осуществляется за счет решения ряда задач линейного программирования [14] по согласованию оценок конъюнктов (в случае скалярного и неточного свидетельств оценки получаются накрывающими). При этом в случае интервальных оценок АБС задает семейство распределений [67,71]. Если же фрагменты знаний задаются со скалярными оценками, то вероятностная декомпозиция реализуется за счет предположения, что распределения, задаваемыми двумя фрагментами знаний, условно независимы при распределении, задаваемом подфрагментом знаний, являющимся пересечением исходных.
Алгебраические байесовские сети все еще не получили такого же распространения, как байесовские сети доверия, что объясняется тем, что соответствующий математический аппарат, в особенности алгоритмы машинного обучения, развит еще не полностью. Тем не менее, для алгебраических байесовских сетей предложено применение в классификации текстов [27], поиске ассоциативных правил [18], распознавании изображений, моделировании скрытых марковских моделей [1,31,32,39,41,42,126] и байесовских сетей доверия [60,74]. Важным являются также алгоритмы, предложенные для обработки направленных циклов в байесовских сетях доверия за счет их представления через алгебраические байесовские сети [78,80,83]